شفرة هامينغ

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

تُنشئ الخوارزمية العامة التالية رمز تصحيح خطأ واحد (SEC) لأي عدد من البتات. وتتلخص الفكرة الرئيسية في اختيار بتات تصحيح الأخطاء بحيث يكون ناتج عملية XOR للفهرس ( XOR لجميع مواضع البتات التي تحتوي على 1) مساويًا للصفر. نستخدم المواضع 1، 10، 100، إلخ (بالنظام الثنائي) كبتات تصحيح الأخطاء، مما يضمن إمكانية ضبط بتات تصحيح الأخطاء بحيث يكون ناتج عملية XOR للفهرس للرسالة بأكملها مساويًا للصفر. إذا استقبل المُستقبِل سلسلة نصية ناتج عملية XOR للفهرس فيها صفر، فإنه يستنتج عدم وجود أي تلف، وإلا، فإن ناتج عملية XOR للفهرس يُشير إلى موضع البت التالف.

يمكن استنتاج خوارزمية من الوصف التالي:

1. قم بترقيم البتات بدءًا من 1: البت 1، 2، 3، 4، 5، 6، 7، إلخ.
2. اكتب أرقام البتات بالنظام الثنائي: 1، 10، 11، 100، 101، 110، 111، إلخ.
3. جميع مواضع البتات التي تمثل قوى العدد اثنين (لها بت واحد 1 في الشكل الثنائي لموضعها) هي بتات التكافؤ: 1، 2، 4، 8، إلخ. (1، 10، 100، 1000)
4. جميع مواضع البتات الأخرى، التي تحتوي على بتتين أو أكثر من النوع 1 في الشكل الثنائي لموضعها، هي بتات بيانات.
5. يتم تضمين كل بت من بتات البيانات في مجموعة فريدة من 2 أو أكثر من بتات التكافؤ، كما هو محدد بواسطة الشكل الثنائي لموضع البت الخاص به.
   1. يغطي بت التكافؤ 1 جميع مواضع البتات التي تحتوي على أقل بت ذي أهمية: البت 1 (بت التكافؤ نفسه)، 3، 5، 7، 9، إلخ.
   2. يغطي بت التكافؤ 2 جميع مواضع البت التي تحتوي على البت الأقل أهمية الثاني : البتات 2-3، 6-7، 10-11، إلخ.
   3. تغطي بتة التكافؤ 4 جميع مواضع البتات التي تحتوي على البتة الثالثة الأقل أهمية: البتات 4-7، 12-15، 20-23، إلخ.
   4. يغطي بت التكافؤ 8 جميع مواضع البت التي تحتوي على البت الأقل أهمية الرابع : البتات 8-15، 24-31، 40-47، إلخ.
   5. بشكل عام، يغطي كل بت تكافؤ جميع البتات التي يكون فيها ناتج عملية AND المنطقية بين موضع التكافؤ وموضع البت غير صفري.

إذا كانت بايت البيانات المراد ترميزها هي 10011010، فإن كلمة البيانات (باستخدام _ لتمثيل بتات التكافؤ) ستكون __1_001_1010، وكلمة الترميز هي 011100101010.

إن اختيار الزوجية، سواء كانت زوجية أو فردية، غير ذي صلة، ولكن يجب استخدام نفس الاختيار لكل من التشفير وفك التشفير.

يمكن توضيح هذه القاعدة العامة بصريًا:

موضع البت		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	...
بتات البيانات المشفرة		ص1	ص2	د1	ص4	د2	د3	د4	ص8	د5	د6	د7	د8	د9	d10	د11	ص16	د12	د13	د14	د15
تغطية بت التكافؤ	ص1
	ص2
	ص4
	ص8
	ص16

يظهر هنا 20 بتًا مُشفّرًا فقط (5 بتات للتكافؤ، و15 بتًا للبيانات)، لكن النمط يستمر بلا نهاية. السمة الأساسية لرموز هامينغ، والتي يمكن ملاحظتها بالعين المجردة، هي أن كل بت مُحدد يقع ضمن مجموعة فريدة من بتات التكافؤ. للتحقق من وجود أخطاء، يتم فحص جميع بتات التكافؤ. يُحدد نمط الأخطاء، الذي يُسمى متلازمة الخطأ ، البت المُخطئ. إذا كانت جميع بتات التكافؤ صحيحة، فلا يوجد خطأ. وإلا، فإن مجموع مواقع بتات التكافؤ الخاطئة يُحدد البت المُخطئ. على سبيل المثال، إذا أشارت بتات التكافؤ في المواضع 1 و2 و8 إلى وجود خطأ، فإن البت 1+2+8=11 يكون خاطئًا. إذا أشار بت تكافؤ واحد فقط إلى وجود خطأ، فإن بت التكافؤ نفسه يكون خاطئًا.

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

بتات التكافؤ	إجمالي البتات	بتات البيانات	اسم	معدل
2	3	1	Hamming(3,1) ( رمز التكرار الثلاثي )	1/3 ≈ 0.333
3	7	4	هامينغ (7،4)	4/7 ≈ 0.571
4	15	11	هامينغ (15،11)	11/15 ≈ 0.733
5	31	26	هامينغ (31،26)	26/31 ≈ 0.839
6	63	57	هامينغ (63,57)	57/63 ≈ 0.905
7	127	120	هامينغ (127،120)	120/127 ≈ 0.945
8	255	247	هامينغ (255،247)	247/255 ≈ 0.969
9	511	502	هامينغ (511,502)	502/511 ≈ 0.982
...
م	${\displaystyle n=2^{m}-1}$	${\displaystyle k=2^{m}-m-1}$	هاميم${\displaystyle (2^{m}-1,2^{m}-m-1)}$	${\displaystyle (2^{m}-m-1)/(2^{m}-1)}$

المصفوفة ${\displaystyle \mathbf {G}$ :={\begin{pmatrix}{\begin{array}{c|c}I_{k}&-A^{\text{T}}\\\end{array}}\end{pmatrix}}} تسمى مصفوفة المولد (الأساسية) لرمز خطي ( n , k )،

و${\displaystyle \mathbf {H}$ :={\begin{pmatrix}{\begin{array}{c|c}A&I_{nk}\\\end{array}}\end{pmatrix}}} تسمى مصفوفة فحص التكافؤ .

هذا هو بناء G و H بالشكل القياسي (أو المنهجي). وبغض النظر عن الشكل، يجب أن تستوفي G و H في رموز الكتل الخطية الشروط التالية

${\displaystyle \mathbf {H} \,\mathbf {G} ^{\text{T}}=\mathbf {0} }$، مصفوفة جميع عناصرها أصفار. ^{[ 6 ]}

بما أن [7,  4,  3] =  [ n , k , d ] = [2m ⁻ 1 , ^2m − 1 − m , 3]، فإن مصفوفة التحقق من التكافؤ H لرمز هامينغ تُنشأ عن طريق سرد جميع الأعمدة ذات الطول m التي تكون مستقلة مثنى مثنى.          

إذن، H هي مصفوفة يكون طرفها الأيسر جميع العناصر غير الصفرية المكونة من n عنصرًا، حيث لا يهم ترتيب هذه العناصر في أعمدة المصفوفة. أما طرفها الأيمن فهو مصفوفة الوحدة من الرتبة ( n  - k ) . 

لذا يمكن الحصول على G من H عن طريق أخذ منقولة الجانب الأيسر من H مع مصفوفة الوحدة k - مصفوفة الوحدة على الجانب الأيسر من G. 

مصفوفة مولد الشفرة${\displaystyle \mathbf {G} }$ومصفوفة التحقق من التكافؤ${\displaystyle \mathbf {H} }$نكون:

${\displaystyle \mathbf {G}$ :={\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&0&1&1&1&1\end{pmatrix}}_{4,7}}

و

${\displaystyle \mathbf {H}$ :={\begin{pmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\end{pmatrix}}_{3,7}.}

وأخيرًا، يمكن تحويل هذه المصفوفات إلى رموز غير منهجية مكافئة من خلال العمليات التالية: ^{[ 6 ]}

• تبديل الأعمدة (تبديل الأعمدة)
• عمليات الصفوف الأولية (استبدال صف بمجموعة خطية من الصفوف)

مثال

من المصفوفة أعلاه، لدينا 2k ⁼ 24 ⁼ 16 كلمة رمزية. لنفترض${\displaystyle {\vec {a}}}$ليكن متجه صف من بتات البيانات الثنائية،${\displaystyle {\vec {a}}=[a_{1},a_{2},a_{3},a_{4}],\quad a_{i}\in \{0,1\}}$كلمة السر${\displaystyle {\vec {x}}}$لأي من متجهات البيانات الستة عشر الممكنة${\displaystyle {\vec {a}}}$يُعطى بواسطة الضرب القياسي للمصفوفات${\displaystyle {\vec {x}}={\vec {a}}G}$حيث يتم إجراء عملية الجمع بتردد 2.

على سبيل المثال، لنفترض${\displaystyle {\vec {a}}=[1,0,1,1]}$باستخدام مصفوفة المولد${\displaystyle G}$من الأعلى، لدينا (بعد تطبيق باقي القسمة على 2، على المجموع)،

${\displaystyle {\vec {x}}={\vec {a}}G={\begin{pmatrix}1&0&1&1\end{pmatrix}}{\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}={\begin{pmatrix}1&0&1&1&0&1&0\end{pmatrix}}}$

يمكن بسهولة توسيع ترميز هامينغ [7,4] إلى ترميز [8,4] بإضافة بت تكافؤ إضافي أعلى الكلمة المشفرة (7,4) (انظر Hamming(7,4) ). ويمكن تلخيص ذلك بالمصفوفات المعدلة التالية:

${\displaystyle \mathbf {G}$ :={\begin{pmatrix}1&1&1&0&0&0&0&1\\1&0&0&1&1&0&0&1\\0&1&0&1&0&1&0&1\\1&1&0&1&0&0&1&0\end{pmatrix}}_{4,8}}

و

${\displaystyle \mathbf {H}$ :={\begin{pmatrix}1&0&1&0&1&0&1&0\\0&1&1&0&0&1&1&0\\0&0&0&1&1&1&0\\1&1&1&1&1&1&1&1\end{pmatrix}}_{4,8}.}

لاحظ أن المصفوفة H ليست في الصيغة القياسية. وللحصول على المصفوفة G، يمكن استخدام عمليات الصف الأولية للحصول على مصفوفة مكافئة للمصفوفة H في صيغة منتظمة.

${\displaystyle \mathbf {H} =\left({\begin{array}{cccc|cccc}0&1&1&1&1&0&0&0\\1&0&1&1&0&1&0&0\\1&1&0&1&0&0&1&0\\1&1&1&0&0&0&0&1\end{array}}\right)_{4,8}.}$

على سبيل المثال، يُمثل الصف الأول في هذه المصفوفة مجموع الصفين الثاني والثالث من المصفوفة H في شكلها غير المنتظم. وباستخدام البنية المنتظمة لرموز هامينغ المذكورة أعلاه، تصبح المصفوفة A واضحة، ويُكتب الشكل المنتظم للمصفوفة G على النحو التالي:

${\displaystyle \mathbf {G} =\left({\begin{array}{cccc|cccc}1&0&0&0&0&1&1&1\\0&1&0&0&1&0&1&1\\0&0&1&0&1&1&0&1\\0&0&0&1&1&1&1&0\end{array}}\right)_{4,8}.}$

يمكن اختزال الشكل غير المنتظم لـ G إلى شكل صف (باستخدام عمليات الصف الأولية) ليطابق هذه المصفوفة.

إن إضافة الصف الرابع تحسب فعليًا مجموع جميع بتات كلمة الترميز (البيانات والتكافؤ) كبت التكافؤ الرابع.

على سبيل المثال، يتم ترميز العدد 1011 (باستخدام الصيغة غير المنتظمة لـ G في بداية هذا القسم) إلى 01 1 0 011 0، حيث تمثل الأرقام الزرقاء البيانات، والأرقام الحمراء بتات التكافؤ من ترميز هامينغ [7,4]، والرقم الأخضر هو بت التكافؤ المضاف بواسطة الترميز [8,4]. يجعل الرقم الأخضر تكافؤ كلمات الترميز [7,4] زوجيًا.

وأخيرًا، يمكن إثبات أن الحد الأدنى للمسافة قد ازداد من 3 في رمز [7,4] إلى 4 في رمز [8,4]. لذا، يمكن تعريف هذا الرمز بأنه رمز هامينغ [8,4].

لفك تشفير رمز هامينغ [8,4]، تحقق أولاً من بت التكافؤ. إذا أشار بت التكافؤ إلى وجود خطأ، فسيشير تصحيح الخطأ الفردي (رمز هامينغ [7,4]) إلى موقع الخطأ، بينما يشير "عدم وجود خطأ" إلى بت التكافؤ. إذا كان بت التكافؤ صحيحًا، فسيشير تصحيح الخطأ الفردي إلى عملية XOR الثنائية لموقعَي الخطأ. إذا كان الموقعان متساويين ("لا يوجد خطأ")، فهذا يعني إما عدم حدوث خطأ في البت المزدوج، أو أنه قد ألغى نفسه. وإلا، فقد حدث خطأ في البت المزدوج.