مسافة هامينغ

مكعب ثنائي مكون من 3 بتات لإيجاد مسافة هامينغ

مثالان على المسافات: المسافة بين 100 و011 هي 3؛ والمسافة بين 010 و111 هي 2

المسافة الدنيا بين أي رأسين هي مسافة هامينغ بين السلسلتين الثنائيتين.

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

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

مسافة هامينغ بين سلسلتين متساويتين في الطول من الرموز هي عدد المواضع التي تختلف فيها الرموز المتناظرة. ^{[ 1 ]}

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

• " ka rol in " و " ka thr in " تساوي 3.
• " k a r ol in " و " k e rs in " هي 3.
• " ك أثر في " و" ك أول في " هو 4.
• 0000 و 1111 يساوي 4.
• 2 17 3 8 96 و 2 23 3 7 96 يساوي 3.

بالنسبة لطول ثابت n ، تُعدّ مسافة هامينغ مقياسًا على مجموعة الكلمات ذات الطول n (المعروفة أيضًا باسم فضاء هامينغ )، حيث إنها تُحقق شروط عدم السلبية والتناظر، وتكون مسافة هامينغ بين كلمتين تساوي صفرًا إذا وفقط إذا كانت الكلمتان متطابقتين، كما أنها تُحقق متباينة المثلث أيضًا: ^{[ 2 ].} في الواقع، إذا حددنا ثلاث كلمات a و b و c ، فعندما يكون هناك فرق بين الحرف i من a والحرف i من c ، فلا بد من وجود فرق بين الحرف i من a والحرف i من b ، أو بين الحرف i من b والحرف i من c . وبالتالي، فإن مسافة هامينغ بين a و c لا تتجاوز مجموع مسافتي هامينغ بين a و b وبين b و c . يمكن أيضًا اعتبار مسافة هامينغ بين كلمتين a و b بمثابة وزن هامينغ لـ a − b لاختيار مناسب للمؤثر −، تمامًا كما يمكن اعتبار الفرق بين عددين صحيحين بمثابة مسافة من الصفر على خط الأعداد.

بالنسبة للسلسلتين الثنائيتين a و b، فإن مسافة هامينغ تساوي عدد الآحاد ( عدد العناصر ) في عملية XOR بين a و b . ^{[ 3 ]} يُعرف الفضاء المتري للسلاسل الثنائية ذات الطول n ، مع مسافة هامينغ، باسم مكعب هامينغ ؛ وهو مكافئ، كفضاء متري، لمجموعة المسافات بين الرؤوس في رسم بياني مكعب فائق . يمكن أيضًا اعتبار السلسلة الثنائية ذات الطول n متجهًا في${\displaystyle \mathbb {R} ^{n}}$من خلال التعامل مع كل رمز في السلسلة كإحداثي حقيقي؛ مع هذا التضمين، تشكل السلاسل رؤوس مكعب فائق الأبعاد n ، وتكون مسافة هامينغ للسلاسل مكافئة لمسافة مانهاتن بين الرؤوس.

تُستخدم مسافة هامينغ الدنيا، أو المسافة الدنيا (ويُرمز لها عادةً بـ d _min )، لتعريف بعض المفاهيم الأساسية في نظرية الترميز ، مثل رموز كشف الأخطاء ورموز تصحيح الأخطاء . على وجه الخصوص، يُقال إن الرمز C يكشف الأخطاء من الرتبة k إذا، وفقط إذا، كانت مسافة هامينغ الدنيا بين أي كلمتين من كلماته المشفرة تساوي k + 1 على الأقل. ^{[ 2 ]}

على سبيل المثال، لنفترض وجود رمز يتكون من كلمتين "000" و"111". المسافة بين هاتين الكلمتين هي 3، وبالتالي فإن اكتشاف الخطأ فيها k = 2. هذا يعني أنه إذا انقلب بت واحد أو بتان، يمكن اكتشاف الخطأ. أما إذا انقلبت ثلاثة بتات، فإن "000" تصبح "111" ولا يمكن اكتشاف الخطأ.

يُقال إن الشفرة C تُصحِّح k خطأً إذا كان لكل كلمة w في فضاء هامينغ الأساسي H ، توجد كلمة رمزية واحدة على الأكثر c (من C ) بحيث تكون مسافة هامينغ بين w و c على الأكثر k . بعبارة أخرى، تكون الشفرة مُصحِّحة k خطأً إذا كانت أقصر مسافة هامينغ بين أي كلمتين رمزيتين فيها على الأقل 2k + 1. يُفهم هذا أيضًا هندسيًا على أنه أي كرات مغلقة نصف قطرها k مركزها كلمات رمزية مختلفة تكون منفصلة. ^{[ 2 ]} تُسمى هذه الكرات أيضًا بكرات هامينغ في هذا السياق. ^{[ 4 ]}

على سبيل المثال، لنفترض نفس الشفرة المكونة من 3 بتات، والتي تتألف من كلمتي التشفير "000" و"111". تتكون فضاء هامينغ من 8 كلمات: 000، 001، 010، 011، 100، 101، 110، و111. تقع كلمة التشفير "000" وكلمات الخطأ أحادي البت "001"، "010"، "100" جميعها ضمن مسافة هامينغ تساوي 1 من كلمة "000". وبالمثل، تقع كلمة التشفير "111" وكلمات الخطأ أحادي البت الخاصة بها "110"، "101"، و"011" جميعها ضمن مسافة هامينغ تساوي 1 من كلمة "111" الأصلية. في هذه الشفرة، يقع الخطأ أحادي البت دائمًا ضمن مسافة هامينغ تساوي 1 من الشفرة الأصلية، ويمكن تصحيح الشفرة بخطأ واحد ، أي k=1 . بما أن مسافة هامينغ بين "000" و "111" هي 3، وهذه تشكل المجموعة الكاملة من الكلمات المشفرة في الكود، فإن الحد الأدنى لمسافة هامينغ هو 3، وهو ما يحقق 2k+1 = 3 .

وبالتالي، فإنّ الشفرة ذات مسافة هامينغ الدنيا d بين كلماتها المشفرة تستطيع اكتشاف d - 1 خطأ على الأكثر، وتصحيح ⌊( d - 1)/2⌋ خطأ. ^{[ 2 ]} ويُطلق على هذا الرقم الأخير أيضًا نصف قطر التعبئة أو قدرة الشفرة على تصحيح الأخطاء . ^{[ 4 ]}

سُميت مسافة هامينغ نسبةً إلى ريتشارد هامينغ ، الذي قدم المفهوم في ورقته البحثية الأساسية حول رموز هامينغ ، بعنوان "رموز كشف الأخطاء وتصحيحها" ، عام 1950. ^{[ 5 ]} يُستخدم تحليل أوزان هامينغ للبتات في العديد من التخصصات، بما في ذلك نظرية المعلومات ، ونظرية الترميز ، وعلم التشفير . ^{[ 6 ]}

يُستخدم في الاتصالات لحساب عدد البتات المقلوبة في كلمة ثنائية ثابتة الطول كتقدير للخطأ، ولذلك يُطلق عليه أحيانًا اسم مسافة الإشارة . ^{[ 7 ]} بالنسبة للسلاسل المكونة من q بت على أبجدية حجمها q  ≥  2، تُطبق مسافة هامينغ في حالة القناة المتناظرة المكونة من q بت ، بينما تُستخدم مسافة لي لتقنية مفتاح إزاحة الطور أو بشكل عام للقنوات المعرضة لأخطاء التزامن لأن مسافة لي تأخذ في الحسبان أخطاء ±1. ^{[ 8 ]} إذا${\displaystyle q=2}$أو${\displaystyle q=3}$تتطابق المسافتان لأن أي زوج من العناصر من${\textstyle \mathbb {Z} /2\mathbb {Z} }$أو${\textstyle \mathbb {Z} /3\mathbb {Z} }$تختلف بمقدار 1، لكن المسافات تختلف بالنسبة للأحجام الأكبر${\displaystyle q}$.

تُستخدم مسافة هامينغ أيضًا في علم التصنيف كمقياس للمسافة الجينية. ^{[ 9 ]}

مع ذلك، عند مقارنة سلاسل نصية ذات أطوال مختلفة، أو سلاسل نصية لا تقتصر على الاستبدالات فحسب، بل تشمل أيضًا الإضافات أو الحذف، قد يكون استخدام مقياس أكثر دقة مثل مسافة ليفنشتاين أكثر ملاءمة. ^{[ 10 ] : 32}

الدالة التالية، المكتوبة بلغة بايثون 3، تُرجع مسافة هامينغ بين سلسلتين نصيتين:

def hamming_distance ( string1 : str , string2 : str ) -> int :"""أرجع مسافة هامينغ بين سلسلتين.""""إذا كان طول ( السلسلة1 ) لا يساوي طول ( السلسلة2 ):raise ValueError ( "يجب أن تكون السلاسل متساوية الطول." )dist_counter = 0for n in range ( len ( string1 )):إذا كان string1 [ n ] != string2 [ n ]:dist_counter += 1إرجاع عداد المسافة

ستحسب دالة C التالية مسافة هامينغ لعددين صحيحين (يُعتبران قيمتين ثنائيتين، أي سلاسل من البتات). يتناسب زمن تشغيل هذه الدالة طرديًا مع مسافة هامينغ وليس مع عدد البتات في المدخلات. تحسب الدالة عملية XOR الثنائية بين المدخلين، ثم تجد وزن هامينغ للنتيجة (عدد البتات غير الصفرية) باستخدام خوارزمية ويغنر (1960) التي تحدد وتُزيل البت غير الصفري الأدنى قيمة بشكل متكرر. تدعم بعض المترجمات الدالة __builtin_popcount التي يمكنها حساب ذلك باستخدام معالجات متخصصة عند توفرها.

int hamming_distance ( unsigned x , unsigned y ) { int dist = 0 ;// يقوم عامل ^ بتعيين البتات المختلفة فقط إلى 1 for ( unsigned val = x ^ y ; val > 0 ; ++ dist ) { // ثم نحسب البت الذي تم تعيينه إلى 1 باستخدام طريقة بيتر ويغنر val = val & ( val - 1 ); // يتم تعيين أقل قيمة لـ val وهي 1 إلى الصفر }// إرجاع عدد البتات المختلفة return dist ; }

يُعد استخدام تعليمة عدّ السكان ( popcount ) في لغة التجميع بديلاً أسرع. وتتيح بعض المترجمات، مثل GCC وClang، هذه التعليمة عبر دالة مضمنة.

// مسافة هامينغ للأعداد الصحيحة 32 بت int hamming_distance32 ( unsigned int x , unsigned int y ) { return __builtin_popcount ( x ^ y ); }// مسافة هامينغ للأعداد الصحيحة 64 بت int hamming_distance64 ( unsigned long long x , unsigned long long y ) { return __builtin_popcountll ( x ^ y ); }

• أقرب سلسلة
• مسافة داميراو-ليفنشتاين
• المسافة الإقليدية
• مشكلة جاب-هامنج
• قانون غراي
• مؤشر جاكارد
• مسافة جارو-وينكلر
• مسافة ليفنشتاين
• مسافة ماهالانوبيس
• مسافة مانهايم
• مؤشر التشابه لسورنسن
• ذاكرة موزعة متفرقة
• سلم الكلمات

•  تتضمن هذه المقالة موادًا متاحة للعموم من المعيار الفيدرالي 1037C ، إدارة الخدمات العامة . مؤرشفة من الأصل بتاريخ 22 يناير 2022.
• فيجنر، بيتر (1960). "تقنية لحساب الآحاد في الحاسوب الثنائي" . اتصالات رابطة آلات الحوسبة . 3 (5): 322. doi : 10.1145/367236.367286 . S2CID 31683715 . 
• ماكاي، ديفيد جيه سي (2003). نظرية المعلومات، والاستدلال، وخوارزميات التعلم . كامبريدج: مطبعة جامعة كامبريدج . ISBN 0-521-64298-1.