مسافة هامينغ

dist_counter = 0

for n in range(len(string1)):

if string1[n] != string2[n]:

التعريف

• مسافة هامينغ بين "kain" و"kain" تساوي 3.
• مسافة هامينغ بين "krin" و"krin" تساوي 3.
• مسافة هامينغ بين "kin" و"kin" تساوي 4.
• مسافة هامينغ بين و تساوي 4.
• مسافة هامينغ بين 2396 و2396 تساوي 3.

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

التطبيقات

وفي هذا السياق، يُستعمل مفهوم مسافة هامينغ وتحليل وزن هامينغ للبتات في الكثير من التخصصات مثل علوم الحاسوب والاتّصالات، وبالأخص في نظرية المعلومات، ونظرية الترميز، والتعمية. في مجال الاتصالات، تُستعمل مسافة هامينغ لحساب عدد البتات المقلوبة في كلمة ثنائية ذات طول ثابت كتقدير للخطأ، ولذلك يُطلق عليها أحيانًا مسافة الإشارة. بالنسبة لسلاسل q-ary على أبجدية بحجم q ≥ 2، تُطبّق مسافة هامينغ في حالة القناة المتماثلة q-ary، بينما تُستعمل مسافة لي في مفاتيح إزاحة الطور أو بشكل عام في القنوات المعرضة لأخطاء التزامن لأن مسافة لي تمتلك نسبة خطأ ±1. إذا كانت 𝑞 = 2 أو 𝑞 = 3، فإن المسافتين تتطابقان لأن أي زوج من العناصر من 𝑍 / 2 𝑍 أو 𝑍 / 3 𝑍 يختلف بمقدار 1، ولكن تختلف المسافات بالنسبة لقيم 𝑞 الأكبر.

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

return __builtin_popcountll(x ^ y);

}:

return dist;

وعلى صعيد آخر، }يُمكن بدلا من ذلك استخدام أمر التجميع من خلال دالة جوهرية على النحو التالي// Hamming distance for 32-bit integers

• int hamming_distance32(unsigned int x, unsigned int y)
• {
• return __builtin_popcount(x ^ y);
• }

dist_counter += 1

ومن ناحية أخرى، return dist_counterأو بصورة مختصرة:sum(char1 != char2 for char1, char2 in zip(string1, string2, strict=True))تحسب الدالة hamming_distance، التي تم تنفيذها باستخدام لغة بايثون 3، مسافة هامينج بين سلسلتين (أو كائنات قابلة للتكرار أخرى) متساويتين في الطول عن طريق إنشاء تسلسل من القيم المنطقية التي تشير إلى عدم التطابق والتطابقات بين المواضع المقابلة في المدخلين، ثم جمع التسلسل مع القيم True وFalse، والتي يتم تفسيرها على أنها واحد وصفر على التوالي.def hamming_distance(s1: str, s2: str) -> int:

• """Return the Hamming distance between equal-length sequences."""
• if len(s1) != len(s2):
• raise ValueError("Undefined for sequences of unequal length.")

إضافةً إلى ذلك، return sum(char1 != char2 for char1, char2 in zip(s1, s2))حيث تدمج دالة zip مجموعتين متساويتين في الطول في أزواج.

{

ومن ناحية أخرى، ستحسب دالة C التالية مسافة هامينغ لعددين صحيحين (يُعتبران قيمتين ثنائيتين، أي تسلسلين من البتات). يتناسب وقت تشغيل هذا الإجراء مع مسافة هامينغ وليس مع عدد البتات في المُدخلات. تحسب الدالة القيمة المطلقة أو لكل بت من المُدخلين، ثم تجد وزن هامينغ للنتيجة (عدد البتات غير الصفرية) باستخدام خوارزمية ويغنر (1960) التي تعثر على البت غير الصفري ذي الترتيب الأدنى وتُزيله بشكل متكرر. تدعم بعض المُجمّعات دالة __builtin_popcount التي يُمكنها حساب ذلك باستخدام أجهزة مُعالجة مُتخصصة عند توفرها.int hamming_distance(unsigned x, unsigned y)

{

• // We then count the bit set to 1 using the Peter Wegner way
• val = val & (val - 1); // Set to zero val's lowest-order 1
• }
• // Return the number of differing bits

مثال

إضافةً إلى ذلك، توضح الدالة التالية، والمكتوبة بلغة بايثون 3، مسافة هامينغ بين سلسلتين نصيتين:def hamming_distance(string1: str, string2: str) -> int:

• """Return the Hamming distance between two strings."""
• if len(string1) != len(string2):
• raise ValueError("Strings must be of equal length.")

int dist = 0;

وفي السياق ذاته، // The ^ operators sets to 1 only the bits that are different

for (unsigned val = x ^ y; val > 0; ++dist)

الخصائص

علاوةً على ذلك، بالنسبة للسلاسل الثنائية (أ) و(ب)، تساوي مسافة هامينغ عدد الآحاد (عدد السكان) في عملية إكس أور (ب) يُعرف الفضاء المتري للسلاسل الثنائية بطول يساوي n من السلاسل، مع مسافة هامينغ، باسم مكعب هامينغ؛ والذي يكافئ، كفضاء متري به مجموعة المسافات بين الرؤوس في رسم بياني لمكعب فائق. يمكن كذلك التعبير عن سلسلة ثنائية طولها يساوي n كمتجه في . بمعاملة كل رمز في السلسلة كإحداثي حقيقي؛ وبهذا التضمين، تُشكل السلاسل رؤوس مكعب فائق له n من الأبعاد، وتكون مسافة هامينغ للسلاسل مكافئة لمسافة مانهاتن بين الرؤوس.

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

// Hamming distance for 64-bit integers

وفي هذا السياق، int hamming_distance64(unsigned long long x, unsigned long long y)

{

التاريخ

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

اكتشاف الأخطاء وتصحيحها

وعلى صعيد آخر، تعمل مسافة هامينغ كأداة أساسية لتحديد الأخطاء في أنظمة تخزين أو نقل البيانات من خلال مقارنة البيانات المستلمة مع البيانات المرسلة الأصلية، إذ تساعد مسافة هامينغ في تحديد عدد تقلبات البتات أو الأخطاء التي حدثت أثناء عملية الإرسال. تُستعمل مسافة هامينغ الدنيا (أو الحد الأدنى للمسافة) (ويُشار إليها عادةً بالرمز dmin) لتعريف بعض المفاهيم الأساسية في نظرية التعمية، مثل أكواد كشف الأخطاء وتصحيحها. وبشكل خاص، يُقال عن الكود (ج) أنه يكشف الأخطاء (ك) فقط إذا كانت مسافة هامينغ الدنيا بين أي كلمتين من كلماته الرمزية تساوي ك+1 على الأقل. فمثلًا، لنفترض أن الكود يتكون من كلمتن أو رمزين هما "000" و"111".، فإن مسافة هامينغ بين هاتين الكلمتين هي 3، وبالتالي يكون معامل كشف الأخطاء ك=2. هذا يعني أنه إذا تم قلب بت واحد أو قلب بتين، يمكن اكتشاف الخطأ. إذا تم قلب ثلاثة بتات، فإن "000" يصبح "111" ولا يمكن اكتشاف الخطأ.

من جانب آخر، وبالتالي، فإن الكود الذي تبلغ أدنى مسافة هامينغ بين كلماته د لا يمكنه اكتشاف أخطاء بين كلماته إلا إذا كان الخطأ يساوي د-1 على الأكثر، ويمكنه تصحيح أخطاء ⌊(د-1)/2⌋. ويُسمى هذا الرقم الأخير كذلك نصف قطر التعبئة أو قدرة الكود على تصحيح الأخطاء.

من جهة ثانية، يُمكن اعتبار الكود (ج) هو كود تصحِيح الأخطاء ك إذا وُجدت لكل كلمة ل في فضاء هامينغ هـ، كلمة رمز ج واحدة على الأكثر (من ج)، بحيث تكون مسافة هامينغ بين ل وج تساوي ك على الأكثر. بمعنى آخر، يكون الرمز مُصحِّحًا للأخطاء ك إذا كانت مسافة هامينغ الدنيا بين أي كلمتين من كلماته الرمزية تساوي 2ك+1 على الأقل. يُمكن صياغة ذلك هندسيًا كذلك إذا افترضنا وجود كرات مغلقة نصف قطرها يساوي ك، وفي مركزها كلمتان رمزيتان منفصلتان. تُسمى هذه الكرات كذلك بكرات هامينغ.

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