قانون هادامارد

الموسوعة الحرة

مصفوفة كود هادامارد المُعزز [32، 6، 16] لكود ريد-مولر (1، 5) لمسبار الفضاء مارينر 9 التابع لناسا
عمليات XOR : هنا تمثل الحقول البيضاء 0 والحقول الحمراء 1

شفرة هادامارد هي شفرة تصحيح أخطاء سُميت نسبةً إلى عالم الرياضيات الفرنسي جاك هادامارد، وتُستخدم لاكتشاف الأخطاء وتصحيحها عند إرسال الرسائل عبر قنوات شديدة التشويش أو غير موثوقة. في عام 1971، استُخدمت هذه الشفرة لإرسال صور للمريخ إلى الأرض من مسبار مارينر 9 التابع لوكالة ناسا . [ 1 ] نظرًا لخصائصها الرياضية الفريدة، لا تقتصر استخدامات شفرة هادامارد على المهندسين فحسب، بل تُدرس أيضًا بشكل مكثف في نظرية الترميز والرياضيات وعلوم الحاسوب النظرية . تُعرف شفرة هادامارد أيضًا باسم شفرة والش ، وعائلة والش ، [ 2 ] وشفرة والش-هادامارد [ 3 ] تكريمًا لعالم الرياضيات الأمريكي جوزيف ليونارد والش .

المواصفات الرياضية لرمز هادامارد معقدة نوعًا ما، وقد وُصفت في قسم "الإنشاءات ". وهو مثال على رمز خطي بطول2م{\displaystyle 2^{m}}على أبجدية ثنائية . لسوء الحظ، هذا المصطلح غامض إلى حد ما، حيث تفترض بعض المراجع طول الرسالة.ك=م{\displaystyle k=m}بينما يفترض آخرون طول الرسالة بـك=م+1{\displaystyle k=m+1}في هذه المقالة، تسمى الحالة الأولى رمز هادامارد بينما تسمى الحالة الثانية رمز هادامارد المعزز .

تتميز شفرة هادامارد بأن كل كلمة رمزية غير صفرية لها وزن هامينغ يساوي بالضبط2ك-1{\displaystyle 2^{k-1}}وهذا يعني أن مسافة الكود هي أيضًا2ك-1{\displaystyle 2^{k-1}}في تدوين نظرية الترميز القياسية لرموز الكتل ، يُعد رمز هادامارد[2ك،ك،2ك-1]2{\displaystyle [2^{k},k,2^{k-1}]_{2}}-code، أي أنه رمز خطي على أبجدية ثنائية ، وله طول كتلة2ك{\displaystyle 2^{k}}طول الرسالة ( أو بُعدها)ك{\displaystyle k}، والمسافة الدنيا2ك/2{\displaystyle 2^{k}/2}. طول الكتلة كبير جدًا مقارنة بطول الرسالة، ولكن من ناحية أخرى، يمكن تصحيح الأخطاء حتى في الظروف الصاخبة للغاية.

يُعدّ كود هادامارد المُعزّز نسخةً مُحسّنةً قليلاً من كود هادامارد؛ وهو[2ك،ك+1،2ك-1]2{\displaystyle [2^{k},k+1,2^{k-1}]_{2}}وبالتالي، يتمتع بمعدل أفضل قليلاً مع الحفاظ على المسافة النسبية لـ1/2{\displaystyle 1/2}ولذلك يُفضّل استخدامه في التطبيقات العملية. في نظرية الاتصالات، يُطلق عليه ببساطة رمز هادامارد، وهو نفسه رمز ريد-مولر من الدرجة الأولى على الأبجدية الثنائية. [ 4 ]

تعتمد رموز هادامارد عادةً على بناء سيلفستر لمصفوفات هادامارد ، ولكن يُستخدم مصطلح "رمز هادامارد" أيضًا للإشارة إلى الرموز المُنشأة من مصفوفات هادامارد عشوائية ، والتي ليست بالضرورة من نوع سيلفستر. وبشكل عام، لا يكون هذا النوع من الرموز خطيًا. وقد تم إنشاء هذه الرموز لأول مرة بواسطة راج تشاندرا بوس وشارادشاندرا شانكار شريكاندي في عام 1959. [ 5 ] إذا كان n هو حجم مصفوفة هادامارد، فإن الرمز يحتوي على مُعاملات.(ن،2ن،ن/2)2{\displaystyle (n,2n,n/2)_{2}}وهذا يعني أنه رمز ثنائي غير خطي بالضرورة، يتكون من 2 ^n كلمة رمزية بطول كتلة n ومسافة دنيا n /2. ينطبق مخطط البناء وفك التشفير الموصوف أدناه على أي قيمة n عامة ، ولكن خاصية الخطية والتطابق مع رموز ريد-مولر تتطلب أن تكون n قوة للعدد 2 وأن تكون مصفوفة هادامارد مكافئة للمصفوفة التي تم إنشاؤها بطريقة سيلفستر.

يُعدّ رمز هادامارد رمزًا قابلًا للفك محليًا ، مما يُتيح استعادة أجزاء من الرسالة الأصلية باحتمالية عالية ، وذلك بالنظر إلى جزء صغير فقط من الكلمة المُستلمة. وهذا يُتيح تطبيقات في نظرية التعقيد الحسابي ، وخاصةً في تصميم البراهين القابلة للتحقق الاحتمالي . نظرًا لأن المسافة النسبية لرمز هادامارد هي 1/2، فإنه عادةً ما يُمكن التوقع باستعادة جزء من الخطأ لا يتجاوز 1/4. مع ذلك، باستخدام فك التشفير القائم على القوائم ، يُمكن حساب قائمة قصيرة من الرسائل المرشحة المحتملة، بحيث لا يتجاوز طولها 1/2.12-ϵ{\displaystyle {\frac {1}{2}}-\epsilon }لقد تضررت بعض البتات في الكلمة المستلمة.

في تقنية الوصول المتعدد بتقسيم الشفرة (CDMA)، تُعرف شفرة هادامارد بشفرة والش، وتُستخدم لتحديد قنوات الاتصال الفردية . من الشائع في أدبيات CDMA الإشارة إلى كلمات الشفرة بـ"الشفرات". يستخدم كل مستخدم كلمة شفرة مختلفة، أو "شفرة"، لتعديل إشارته. ولأن كلمات شفرة والش متعامدة رياضيًا ، فإن الإشارة المشفرة بشفرة والش تظهر كضوضاء عشوائية لمحطة طرفية متنقلة تدعم CDMA ، ما لم تستخدم تلك المحطة نفس كلمة الشفرة المستخدمة لتشفير الإشارة الواردة . [ 6 ]

تاريخ

يُستخدم مصطلح "رمز هادامارد" بشكل شائع للإشارة إلى هذا الرمز في المراجع العلمية. مع ذلك، يُشار إلى هذه الرموز التصحيحية للأخطاء في الاستخدام الحديث باسم "رموز والش-هادامارد".

وهناك سبب لذلك:

لم يخترع جاك هادامارد الشفرة بنفسه، لكنه قام بتعريف مصفوفات هادامارد حوالي عام 1893، قبل وقت طويل من تطوير أول شفرة لتصحيح الأخطاء ، وهي شفرة هامينغ ، في الأربعينيات من القرن العشرين.

يعتمد رمز هادامارد على مصفوفات هادامارد، وعلى الرغم من وجود العديد من مصفوفات هادامارد المختلفة التي يمكن استخدامها هنا، إلا أنه عادةً ما يتم استخدام بناء سيلفستر لمصفوفات هادامارد فقط للحصول على كلمات رمز هادامارد.

طوّر جيمس جوزيف سيلفستر طريقة بناء مصفوفات هادامارد في عام 1867، وهي طريقة تسبق في الواقع عمل هادامارد على مصفوفات هادامارد. ولذلك، فإن تسمية "شفرة هادامارد" محل خلاف، وتُسمى أحيانًا "شفرة والش" ، تكريمًا لعالم الرياضيات الأمريكي جوزيف ليونارد والش .

استُخدم رمز هادامارد المُعزز خلال مهمة مارينر 9 عام 1971 لتصحيح أخطاء نقل الصور. وكانت القيم الثنائية المستخدمة خلال هذه المهمة بطول 6 بتات، والتي مثّلت 64 قيمة من تدرجات الرمادي .

بسبب محدودية جودة محاذاة جهاز الإرسال في ذلك الوقت (نتيجة لمشاكل حلقة تتبع دوبلر)، كان الحد الأقصى لطول البيانات المفيدة حوالي 30 بت. وبدلاً من استخدام رمز التكرار ، تم استخدام رمز هادامارد [32، 6، 16].

يمكن تصحيح أخطاء تصل إلى 7 بتات لكل كلمة من 32 بت باستخدام هذه الطريقة. بالمقارنة مع رمز التكرار 5 ، فإن خصائص تصحيح الأخطاء في رمز هادامارد هذا أفضل بكثير، ومع ذلك فإن معدله مماثل. كانت خوارزمية فك التشفير الفعالة عاملاً مهماً في قرار استخدام هذا الرمز.

كانت الدائرة المستخدمة تُسمى "الآلة الخضراء". وقد اعتمدت على تحويل فورييه السريع الذي يُمكنه زيادة سرعة فك التشفير بمقدار ثلاثة أضعاف. ومنذ تسعينيات القرن الماضي، توقف استخدام هذا التشفير في برامج الفضاء بشكل شبه كامل، كما أن شبكة ناسا للفضاء السحيق لا تدعم نظام تصحيح الأخطاء هذا لأطباقها التي يزيد قطرها عن 26  مترًا.

الإنشاءات

على الرغم من أن جميع رموز هادامارد مبنية على مصفوفات هادامارد، إلا أن بنيتها تختلف اختلافًا طفيفًا باختلاف المجالات العلمية والمؤلفين والاستخدامات. فالمهندسون، الذين يستخدمون هذه الرموز لنقل البيانات، ونظريو الترميز ، الذين يحللون الخصائص القصوى للرموز، عادةً ما يرغبون في أن يكون معدل الترميز أعلى ما يمكن، حتى لو كان ذلك يعني أن البنية تصبح أقل أناقة من الناحية الرياضية.

من ناحية أخرى، بالنسبة للعديد من تطبيقات رموز هادامارد في علوم الحاسوب النظرية، ليس من المهم جدًا تحقيق المعدل الأمثل، وبالتالي يفضل استخدام تركيبات أبسط لرموز هادامارد لأنها يمكن تحليلها بشكل أكثر أناقة.

البناء باستخدام المنتجات الداخلية

عند إعطاء رسالة ثنائيةx∈{0،1}ك{\displaystyle x\in \{0,1\}^{k}}من الطولك{\displaystyle k}تقوم شفرة هادامارد بتشفير الرسالة إلى كلمة رمزيةملك(x){\displaystyle {\text{Had}}(x)}باستخدام دالة ترميزملك:{0،1}ك→{0،1}2ك.{\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}.} تستخدم هذه الدالة الضرب الداخلي⟨x،y⟩{\displaystyle \langle x,y\rangle }من متجهينx،y∈{0،1}ك{\displaystyle x,y\in \{0,1\}^{k}}والذي يُعرَّف على النحو التالي:

⟨x،y⟩=∑أنا=1كxأناyأنا تعديل 2.{\displaystyle \langle x,y\rangle =\sum _{i=1}^{k}x_{i}y_{i}\ {\bmod {\ }}2\,.}

ثم ترميز هادامارد لـx{\displaystyle x}يُعرَّف بأنه تسلسل جميع الضرب الداخلي معx{\displaystyle x}:

ملك(x)=(⟨x،y⟩)y∈{0،1}ك{\displaystyle {\text{Had}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{0,1\}^{k}}}

كما ذكرنا سابقًا، يُستخدم كود هادامارد المُعزز عمليًا لأن كود هادامارد نفسه مُهدرٌ إلى حدٍ ما. وذلك لأنه إذا كان الجزء الأول منy{\displaystyle y}يساوي صفرًا،y1=0{\displaystyle y_{1}=0}إذاً، فإن الناتج الداخلي لا يحتوي على أي معلومات على الإطلاق حولx1{\displaystyle x_{1}}وبالتالي، يستحيل فك التشفير بالكاملx{\displaystyle x}من تلك المواضع الخاصة بالكلمة السرية فقط. من ناحية أخرى، عندما تقتصر الكلمة السرية على المواضع التيy1=1{\displaystyle y_{1}=1}لا يزال من الممكن فك التشفير بالكاملx{\displaystyle x}لذا، من المنطقي حصر ترميز هادامارد في هذه المواضع، مما يؤدي إلى ترميز هادامارد المُعزز لـx{\displaystyle x}؛ إنه،pHad(x)=(⟨x،y⟩)y∈{1}×{0،1}ك-1{\displaystyle {\text{pHad}}(x)={\Big (}\langle x,y\rangle {\Big )}_{y\in \{1\}\times \{0,1\}^{k-1}}}.

البناء باستخدام مصفوفة مولدة

يُعدّ رمز هادامارد رمزًا خطيًا، ويمكن توليد جميع الرموز الخطية بواسطة مصفوفة مولدة.جي{\displaystyle G}هذه مصفوفة بحيثملك(x)=x⋅جي{\displaystyle {\text{Had}}(x)=x\cdot G}ينطبق على الجميعx∈{0،1}ك{\displaystyle x\in \{0,1\}^{k}}، حيث الرسالةx{\displaystyle x}يُنظر إليه على أنه متجه صف ، ويُفهم ضرب المتجه في المصفوفة في فضاء المتجهات فوق الحقل المنتهيF2{\displaystyle \mathbb {F} _{2}}على وجه الخصوص، توجد طريقة مكافئة لكتابة تعريف الضرب الداخلي لرمز هادامارد باستخدام مصفوفة المولد التي تتكون أعمدتها من جميع السلاسل النصية.y{\displaystyle y}من الطولك{\displaystyle k}، إنه،

جي=(↑↑↑y1y2...y2ك↓↓↓).{\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\y_{1}&y_{2}&\dots &y_{2^{k}}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}\,.}

أينyأنا∈{0،1}ك{\displaystyle y_{i}\in \{0,1\}^{k}}هوأنا{\displaystyle i}المتجه الثنائي رقم -th بترتيب معجمي . على سبيل المثال، مصفوفة المولد لرمز هادامارد ذي البعدك=3{\displaystyle k=3}يكون:

جي=[000011110011001101010101].{\displaystyle G={\begin{bmatrix}0&0&0&0&1&1&1&1\\0&0&1&1&0&0&1&1\\0&1&0&1&0&1&0&1\end{bmatrix}}.}

المصفوفةجي{\displaystyle G}هو(ك×2ك){\displaystyle (k\times 2^{k})}المصفوفة - وتؤدي إلى المؤثر الخطيملك:{0،1}ك→{0،1}2ك{\displaystyle {\text{Had}}:\{0,1\}^{k}\to \{0,1\}^{2^{k}}}.

يتم الحصول على مصفوفة المولد لرمز هادامارد الموسع عن طريق تقييد المصفوفةجي{\displaystyle G}إلى الأعمدة التي يكون إدخالها الأول واحدًا. على سبيل المثال، مصفوفة المولد لرمز هادامارد المُعزز ذي البُعدك=3{\displaystyle k=3}يكون:

جي′=[111100110101].{\displaystyle G'={\begin{bmatrix}1&1&1&1\\0&0&1&1\\0&1&0&1\end{bmatrix}}.}

ثمpHad:{0،1}ك→{0،1}2ك-1{\displaystyle {\text{pHad}}:\{0,1\}^{k}\to \{0,1\}^{2^{k-1}}}هو تحويل خطي معpHad(x)=x⋅جي′{\displaystyle {\text{pHad}}(x)=x\cdot G'}.

بشكل عامك{\displaystyle k}، مصفوفة المولد لرمز هادامارد الموسع هي مصفوفة فحص التكافؤ لرمز هامينغ الموسع ذي الطول2ك-1{\displaystyle 2^{k-1}}والأبعاد2ك-1-ك{\displaystyle 2^{k-1}-k}مما يجعل رمز هادامارد المُعزز هو الرمز الثنائي لرمز هامينغ الموسع. وبالتالي، فإن طريقة بديلة لتعريف رمز هادامارد هي من خلال مصفوفة فحص التكافؤ الخاصة به: مصفوفة فحص التكافؤ لرمز هادامارد تساوي مصفوفة المولد لرمز هامينغ.

البناء باستخدام مصفوفات هادامارد العامة

تُستخلص رموز هادامارد من مصفوفة هادامارد H ذات الأبعاد n × n . وبالتحديد، فإن 2^ n كلمة رمزية للرمز هي صفوف H وصفوف −H . وللحصول على رمز على الأبجدية {0,1}، يُطبق التحويل −1 ↦ 1، 1 ↦ 0، أو بصورة مكافئة، x ↦ (1 − x )/2، على عناصر المصفوفة. إن كون أقصر مسافة للرمز هي n /2 ناتج عن الخاصية المميزة لمصفوفات هادامارد، وهي أن صفوفها متعامدة. وهذا يعني أن صفين مختلفين في مصفوفة هادامارد يختلفان في n /2 موضعًا بالضبط، وبما أن نفي الصف لا يؤثر على التعامد، فإن أي صف في H يختلف عن أي صف في −H في n / 2 موضعًا أيضًا، إلا إذا تطابقت الصفوف، فحينها يختلفان في n موضعًا.        

للحصول على كود هادامارد المُعزز أعلاه باستخدامن=2ك-1{\displaystyle n=2^{k-1}}، يجب أن تكون مصفوفة هادامارد المختارة H من نوع سيلفستر، مما ينتج عنه طول رسالة يبلغسجل2⁡(2ن)=ك{\displaystyle \log _{2}(2n)=k}.

مسافة

مسافة الشفرة هي أقصر مسافة هامينغ بين أي كلمتين مختلفتين، أي أقل عدد من المواضع التي تختلف فيها كلمتان مختلفتان. ولأن شفرة والش-هادامارد شفرة خطية ، فإن المسافة تساوي أقل وزن هامينغ بين جميع كلماتها غير الصفرية. جميع كلمات شفرة والش-هادامارد غير الصفرية لها وزن هامينغ يساوي بالضبط2ك-1{\displaystyle 2^{k-1}}بناءً على الحجة التالية.

يتركx∈{0،1}ك{\displaystyle x\in \{0,1\}^{k}}إذا كانت الرسالة غير صفرية، فإن القيمة التالية تساوي تمامًا نسبة المواضع في الكلمة المشفرة التي تساوي واحدًا:

بروy∈{0،1}ك[(ملك(x))y=1]=بروy∈{0،1}ك[⟨x،y⟩=1].{\displaystyle \Pr _{y\in \{0,1\}^{k}}{\big [}({\text{Had}}(x))_{y}=1{\big ]}=\Pr _{y\in \{0,1\}^{k}}{\big [}\langle x,y\rangle =1{\big ]}\,.}

حقيقة أن القيمة الأخيرة هي بالضبط1/2{\displaystyle 1/2}يُطلق عليه مبدأ المجموع الجزئي العشوائي . ولإثبات صحته، نفترض دون فقدان للعمومية أنx1=1{\displaystyle x_{1}=1}ثم، عند اشتراط قيمy2،...،yك{\displaystyle y_{2},\dots ,y_{k}}، الحدث يعادلy1⋅x1=ب{\displaystyle y_{1}\cdot x_{1}=b}بالنسبة للبعضب∈{0،1}{\displaystyle b\in \{0,1\}}.اعتمادا عليx2،...،xك{\displaystyle x_{2},\dots ,x_{k}}وy2،...،yك{\displaystyle y_{2},\dots ,y_{k}}احتمال أنy1=ب{\displaystyle y_{1}=b}يحدث بالضبط1/2{\displaystyle 1/2}وبالتالي، في الواقع، فإن جميع الكلمات المشفرة غير الصفرية في شفرة هادامارد لها وزن هامينغ نسبي1/2{\displaystyle 1/2}وبالتالي، فإن المسافة النسبية بينهما هي1/2{\displaystyle 1/2}.

المسافة النسبية لرمز هادامارد المُعزز هي1/2{\displaystyle 1/2}كذلك، لكنها لم تعد تتمتع بخاصية أن كل كلمة رمزية غير صفرية لها وزن بالضبط1/2{\displaystyle 1/2}منذ الكل1{\displaystyle 1}متجه s12ك-1{\displaystyle 1^{2^{k-1}}}هي كلمة رمزية من كلمات رمز هادامارد المعزز. وذلك لأن المتجهx=10ك-1{\displaystyle x=10^{k-1}}يشفر إلىpHad(10ك-1)=12ك-1{\displaystyle {\text{pHad}}(10^{k-1})=1^{2^{k-1}}}علاوة على ذلك، كلماx{\displaystyle x}ليس صفرًا وليس متجهًا10ك-1{\displaystyle 10^{k-1}}ينطبق مبدأ المجموع الجزئي العشوائي مرة أخرى، والوزن النسبي لـملك(x){\displaystyle {\text{Had}}(x)}هو بالضبط1/2{\displaystyle 1/2}.

إمكانية فك التشفير محليًا

الرمز القابل للفك محليًا هو رمز يسمح باستعادة بت واحد من الرسالة الأصلية باحتمالية عالية من خلال النظر فقط إلى جزء صغير من الكلمة المستلمة.

الرمز هوq{\displaystyle q}-استعلام قابل للفك محليًا إذا كانت بتة الرسالة،xأنا{\displaystyle x_{i}}يمكن استعادتها عن طريق التحققq{\displaystyle q}أجزاء من الكلمة المستلمة. أو بتعبير أدق، شفرة.ج:{0،1}ك→{0،1}ن{\displaystyle C:\{0,1\}^{k}\rightarrow \{0,1\}^{n}}، يكون(q،دلتا≥0،ϵ≥0){\displaystyle (q,\delta \geq 0,\epsilon \geq 0)}- قابلة للفك محلياً، إذا وُجد مُفكِّك احتمالي،د:{0،1}ن→{0،1}ك{\displaystyle D:\{0,1\}^{n}\rightarrow \{0,1\}^{k}}، بحيث (ملاحظة:Δ(x،y){\displaystyle \Delta (x,y)}يمثل مسافة هامينغ بين المتجهاتx{\displaystyle x}وy{\displaystyle y}) :

∀x∈{0،1}ك،∀y∈{0،1}ن{\displaystyle \forall x\in \{0,1\}^{k},\forall y\in \{0,1\}^{n}}،Δ(y،ج(x))≤دلتان{\displaystyle \Delta (y,C(x))\leq \delta n}يشير ذلك إلى أنPر[د(y)أنا=xأنا]≥12+ϵ،∀أنا∈[ك]{\displaystyle Pr[D(y)_{i}=x_{i}]\geq {\frac {1}{2}}+\epsilon ,\forall i\in [k]}

النظرية 1: رمز والش-هادامارد هو(2،دلتا،12-2دلتا){\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )}- قابلة للفك محليًا للجميع0≤دلتا≤14{\displaystyle 0\leq \delta \leq {\frac {1}{4}}}.

اللمة 1: بالنسبة لجميع الكلمات المشفرة،ج{\displaystyle c}في رمز والش-هادامارد،ج{\displaystyle C}،جأنا+جج=جأنا+ج{\displaystyle c_{i}+c_{j}=c_{i+j}}، أينجأنا،جج{\displaystyle c_{i},c_{j}}تمثل البتات فيج{\displaystyle c}في مناصبأنا{\displaystyle i}وج{\displaystyle j}على التوالي، وجأنا+ج{\displaystyle c_{i+j}}يمثل البت في الموضع(أنا+ج){\displaystyle (i+j)}.

برهان اللمة 1

يتركج(x)=ج=(ج0،...،ج2ن-1){\displaystyle C(x)=c=(c_{0},\dots ,c_{2^{n}-1})}كن كلمة السر فيج{\displaystyle C}يتوافق مع الرسالةx{\displaystyle x}.

يتركجي=(↑↑↑ز0ز1...ز2ن-1↓↓↓){\displaystyle G={\begin{pmatrix}\uparrow &\uparrow &&\uparrow \\g_{0}&g_{1}&\dots &g_{2^{n}-1}\\\downarrow &\downarrow &&\downarrow \end{pmatrix}}}لتكن مصفوفة المولد لـج{\displaystyle C}.

بحسب التعريف،جأنا=x⋅زأنا{\displaystyle c_{i}=x\cdot g_{i}}ومن هذا،جأنا+جج=x⋅زأنا+x⋅زج=x⋅(زأنا+زج){\displaystyle c_{i}+c_{j}=x\cdot g_{i}+x\cdot g_{j}=x\cdot (g_{i}+g_{j})}من خلال بناءجي{\displaystyle G}،زأنا+زج=زأنا+ج{\displaystyle g_{i}+g_{j}=g_{i+j}}لذلك، بالاستبدال،جأنا+جج=x⋅زأنا+ج=جأنا+ج{\displaystyle c_{i}+c_{j}=x\cdot g_{i+j}=c_{i+j}}.

برهان النظرية 1

لإثبات النظرية 1 سنقوم بإنشاء خوارزمية فك التشفير وإثبات صحتها.

الخوارزمية

المدخلات: الكلمة المستلمةy=(y0،...،y2ن-1){\displaystyle y=(y_{0},\dots ,y_{2^{n}-1})}

لكلأنا∈{1،...،ن}{\displaystyle i\in \{1,\dots ,n\}}:

  1. يختارج∈{0،...،2ن-1}{\displaystyle j\in \{0,\dots ,2^{n}-1\}}بشكل عشوائي منتظم.
  2. يختارك∈{0،...،2ن-1}{\displaystyle k\in \{0,\dots ,2^{n}-1\}}بحيثج+ك=هـأنا{\displaystyle j+k=e_{i}}، أينهـأنا{\displaystyle e_{i}}هوأنا{\displaystyle i}متجه الأساس القياسي رقم -th وج+ك{\displaystyle j+k}هي عملية XOR الثنائية لـج{\displaystyle j}وك{\displaystyle k}.
  3. xأنا←yج+yك{\displaystyle x_{i}\gets y_{j}+y_{k}}.

الناتج: رسالةx=(x1،...،xن){\displaystyle x=(x_{1},\dots ,x_{n})}

إثبات صحة النتائج

لأي رسالة،x{\displaystyle x}وتلقى الخبرy{\displaystyle y}بحيثy{\displaystyle y}يختلف عنج=ج(x){\displaystyle c=C(x)}على الأكثردلتا{\displaystyle \delta }جزء من البتات،xأنا{\displaystyle x_{i}}يمكن فك شفرتها باحتمالية لا تقل عن12+(12-2دلتا){\displaystyle {\frac {1}{2}}+({\frac {1}{2}}-2\delta )}.

بحسب المبرهنة 1،جج+جك=جج+ك=x⋅زج+ك=x⋅هـأنا=xأنا{\displaystyle c_{j}+c_{k}=c_{j+k}=x\cdot g_{j+k}=x\cdot e_{i}=x_{i}}. منذج{\displaystyle j}وك{\displaystyle k}إذا تم اختيارها بشكل عشوائي، فإن احتمالyج≠جج{\displaystyle y_{j}\not =c_{j}}هو على الأكثردلتا{\displaystyle \delta }وبالمثل، فإن احتمال أنyك≠جك{\displaystyle y_{k}\not =c_{k}}هو على الأكثردلتا{\displaystyle \delta }بحسب حد الاتحاد ، فإن احتمال أن يكون أيyج{\displaystyle y_{j}}أوyك{\displaystyle y_{k}}لا تتطابق البتات المقابلة فيج{\displaystyle c}هو على الأكثر2دلتا{\displaystyle 2\delta }إذا كان كلاهماyج{\displaystyle y_{j}}وyك{\displaystyle y_{k}}يتوافق معج{\displaystyle c}إذاً، ستنطبق اللمة 1، وبالتالي، ستكون القيمة الصحيحة لـxأنا{\displaystyle x_{i}}سيتم حساب الاحتمال. وبالتالي، فإن الاحتمالxأنا{\displaystyle x_{i}}إذا تم فك تشفيرها بشكل صحيح، فهي على الأقل1-2دلتا{\displaystyle 1-2\delta }. لذلك،ϵ=12-2دلتا{\displaystyle \epsilon ={\frac {1}{2}}-2\delta }ولـϵ{\displaystyle \epsilon }أن تكون إيجابياً،0≤دلتا≤14{\displaystyle 0\leq \delta \leq {\frac {1}{4}}}.

لذلك، فإن قانون والش-هادامارد هو(2،دلتا،12-2دلتا){\displaystyle (2,\delta ,{\frac {1}{2}}-2\delta )}يمكن فك تشفيرها محليًا لـ0≤دلتا≤14{\displaystyle 0\leq \delta \leq {\frac {1}{4}}}.

الأمثلية

بالنسبة لـ k  ≤  7، فقد ثبت أن رموز هادامارد الخطية هي الأمثل من حيث الحد الأدنى للمسافة. [ 7 ]

انظر أيضاً

مراجع

  1. ↑ مالك، مسعود (2006). "رموز هادامارد". نظرية الترميز (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 2020-01-09.
  2. ↑ أمادي، م.؛ مانزولي، أومبرتو؛ ميراني، ماريا لويزا (17-11-2002). "حول تخصيص رموز والش ورموز شبه متعامدة في نظام DS-CDMA متعدد الموجات الحاملة مع فئات متعددة من المستخدمين". المؤتمر العالمي للاتصالات، 2002. GLOBECOM'02. IEEE . المجلد 1. IEEE . الصفحات 841-845 . doi : 10.1109/GLOCOM.2002.1188196 . ISBN   0-7803-7632-3.
  3. ↑ أرورا، سانجيف ؛ باراك، بواز (2009). "القسم 19.2.2". التعقيد الحسابي: منهج حديث . مطبعة جامعة كامبريدج . ISBN 978-0-521-42426-4.
  4. ↑ غورو سوامي، فينكاتيسان (2009). فك تشفير القوائم للرموز الثنائية (ملف PDF) . ص 3. 
  5. ↑ بوز، راج تشاندرا ؛ شريكاندي، شارادشاندرا شانكار (يونيو 1959). "ملاحظة حول نتيجة في نظرية بناء الشفرات". المعلومات والتحكم . 2 (2): 183-194 . CiteSeerX 10.1.1.154.2879 . doi : 10.1016/S0019-9958(59)90376-6 . 
  6. ↑ لانغتون، شاران [في ويكي بيانات] (2002). "دليل CDMA التعليمي: دليل مبسط لمبادئ الاتصالات" (ملف PDF) . من المعقد إلى الواقع. مؤرشف (ملف PDF) من الأصل بتاريخ 20 يوليو 2011. تم الاطلاع عليه بتاريخ 10 نوفمبر 2017 .
  7. ↑ جافي، ديفيد ب.؛ بويوكليف، إيليا. "الرموز الخطية الثنائية المثلى ذات البعد سبعة على الأكثر" . مؤرشف من الأصل بتاريخ 8 أغسطس 2007. تم الاطلاع عليه بتاريخ 21 أغسطس 2007 .

للمزيد من القراءة