تعريف فضاء هامينغ
بشكل رسمي، فضاء هامينغ ذو الأبعاد *n* على الأبجدية *q* (حيث *q* هي قوة عدد أولي) هو ببساطة المجموعة الديكارتية *q**n*. بعبارة أخرى، هو مجموعة كل التتابعات المرتبة المكونة من *n* رمزًا، حيث يأتي كل رمز من مجموعة مكونة من *q* عناصر. الحالة الأكثر شيوعًا هي عندما *q* = 2، وفي هذه الحالة يكون لدينا فضاء هامينغ الثنائي، والذي يتكون من جميع السلاسل الثنائية ذات الطول *n*.
على سبيل المثال، فضاء هامينغ الثنائي ذو الأبعاد 3 (أي *n* = 3) يتكون من المجموعة التالية:
- 000
- 001
- 010
- 011
- 100
- 101
- 110
- 111
لاحظ أن هناك 23 = 8 عناصر في هذا الفضاء.
مسافة هامينغ
مسافة هامينغ بين سلسلتين في فضاء هامينغ هي عدد المواضع التي تختلف فيها الرموز. بعبارة أخرى، هي عدد عمليات الاستبدال المطلوبة لتحويل سلسلة إلى أخرى. على سبيل المثال، مسافة هامينغ بين السلسلتين “10110” و “10011” هي 2، لأنهما تختلفان في الموضعين الثالث والخامس.
رياضيًا، إذا كانت *x* = (x1, x2, …, xn) و *y* = (y1, y2, …, yn) هما سلسلتان في فضاء هامينغ، فإن مسافة هامينغ بينهما، والتي يشار إليها بـ d(x, y)، تُعطى بالصيغة التالية:
d(x, y) = Σi=1n I(xi ≠ yi)
حيث I(xi ≠ yi) هي دالة المؤشر التي تساوي 1 إذا كان xi لا يساوي yi، وصفرًا خلاف ذلك.
مسافة هامينغ هي مقياس حقيقي، مما يعني أنها تحقق الشروط التالية:
- غير سالبة: d(x, y) ≥ 0 لجميع x و y.
- غير متمايزة: d(x, y) = 0 إذا وفقط إذا كان x = y.
- متماثلة: d(x, y) = d(y, x) لجميع x و y.
- تحقق متباينة المثلث: d(x, z) ≤ d(x, y) + d(y, z) لجميع x و y و z.
تطبيقات فضاء هامينغ
يجد فضاء هامينغ ومسافة هامينغ تطبيقات واسعة النطاق في مجالات مختلفة، بما في ذلك:
- نظرية الترميز: تُستخدم مسافة هامينغ لتصميم رموز تصحيح الأخطاء والكشف عنها. الحد الأدنى لمسافة هامينغ لرمز ما يحدد قدرته على اكتشاف وتصحيح الأخطاء. على سبيل المثال، يمكن لرمز ذي مسافة هامينغ دنيا تساوي 3 اكتشاف ما يصل إلى خطأين وتصحيح خطأ واحد.
- الإحصاء: يمكن استخدام فضاء هامينغ لتمثيل البيانات الفئوية. يمكن تمثيل كل فئة بسلسلة ثنائية فريدة، ويمكن استخدام مسافة هامينغ لقياس التشابه بين الفئات.
- علم الأحياء المعلوماتي: يمكن استخدام فضاء هامينغ لمقارنة تسلسلات الحمض النووي أو البروتين. يمكن تمثيل كل تسلسل بسلسلة من الأحرف، ويمكن استخدام مسافة هامينغ لقياس التشابه التطوري بين التسلسلات.
- معالجة الصور: يمكن استخدام فضاء هامينغ لتمثيل الصور الثنائية. يمكن تمثيل كل بكسل بقيمة ثنائية (0 أو 1)، ويمكن استخدام مسافة هامينغ لقياس التشابه بين الصور.
- التعرف على الأنماط: يمكن استخدام فضاء هامينغ لتصنيف الأنماط. يمكن تمثيل كل نمط بسلسلة من الميزات، ويمكن استخدام مسافة هامينغ لقياس التشابه بين الأنماط.
أمثلة على استخدامات فضاء هامينغ
مثال 1: لنفترض أننا نريد تصميم رمز قادر على اكتشاف ما يصل إلى خطأ واحد. يمكننا استخدام رمز ذي مسافة هامينغ دنيا تساوي 2. أحد الأمثلة على ذلك هو رمز التكرار، حيث نكرر كل بت ثلاث مرات. على سبيل المثال، سيتم ترميز البت 0 على النحو 000، وسيتم ترميز البت 1 على النحو 111. إذا حدث خطأ واحد أثناء الإرسال، فسنتمكن من اكتشافه لأن السلسلة المستلمة لن تكون 000 أو 111. على سبيل المثال، إذا استقبلنا السلسلة 001، فسنعرف أن هناك خطأ قد حدث.
مثال 2: لنفترض أننا نريد مقارنة تسلسلين من الحمض النووي. التسلسل الأول هو ATGC، والتسلسل الثاني هو AGGC. يمكننا تمثيل هذه التسلسلات كسلاسل من الأحرف، ويمكننا استخدام مسافة هامينغ لقياس التشابه بينها. مسافة هامينغ بين ATGC و AGGC هي 1، لأنهما يختلفان في الموضع الثاني.
مثال 3: في معالجة الصور، يمكن استخدام فضاء هامينغ لتمثيل الصور الثنائية. على سبيل المثال، لدينا صورتين ثنائيتين صغيرتين، الأولى عبارة عن مربع أبيض على خلفية سوداء، والثانية دائرة بيضاء على خلفية سوداء. يمكننا تمثيل هاتين الصورتين بمصفوفة من البتات (0 للسوداء و 1 للبيضاء). ثم يمكننا استخدام مسافة هامينغ لمقارنة مدى تشابه الصورتين بناءً على عدد البكسلات التي تختلف بينهما.
خصائص فضاء هامينغ
يتمتع فضاء هامينغ بعدة خصائص مهمة تجعله أداة قوية في العديد من المجالات:
- البنية الجبرية: يمكن تعريف عمليات جبرية على فضاء هامينغ، مثل الجمع والضرب. هذا يسمح لنا بتحليل وتصميم الرموز باستخدام التقنيات الجبرية.
- البنية المترية: مسافة هامينغ هي مقياس حقيقي، مما يتيح لنا قياس “المسافة” بين النقاط في الفضاء.
- التباعد: تتميز النقاط في فضاء هامينغ بتباعد جيد، مما يجعلها مناسبة لتصميم الرموز التي يمكنها اكتشاف وتصحيح الأخطاء.
فضاء هامينغ ورموز تصحيح الأخطاء
كما ذكرنا سابقًا، يلعب فضاء هامينغ دورًا حاسمًا في تصميم رموز تصحيح الأخطاء. تهدف هذه الرموز إلى إضافة تكرار إلى البيانات الأصلية بحيث يمكن اكتشاف الأخطاء التي قد تحدث أثناء الإرسال أو التخزين وتصحيحها. تعتمد فعالية رمز تصحيح الأخطاء بشكل كبير على الحد الأدنى لمسافة هامينغ بين أي كلمتين مرمّزتين صحيحتين (codeword). كلما كانت هذه المسافة أكبر، زادت قدرة الرمز على اكتشاف وتصحيح الأخطاء.
على سبيل المثال، إذا كان لدينا رمز بمسافة هامينغ دنيا تساوي 3، فهذا يعني أننا نحتاج إلى تغيير ثلاثة بتات على الأقل لتحويل كلمة مرمّزة صحيحة إلى كلمة مرمّزة صحيحة أخرى. بالتالي، إذا حدث خطأ واحد أو خطأين أثناء الإرسال، يمكننا اكتشاف الخطأ وتصحيحه، لأن الكلمة المستلمة ستكون أقرب إلى الكلمة المرمّزة الأصلية الصحيحة من أي كلمة مرمّزة صحيحة أخرى.
فضاء هامينغ والتشفير
على الرغم من أن فضاء هامينغ يستخدم بشكل أساسي في تصحيح الأخطاء، إلا أنه يمكن أن يكون له تطبيقات محدودة في التشفير. على سبيل المثال، يمكن استخدام مسافة هامينغ كمقياس للمسافة بين قيمتين مشفرتين، مما قد يساعد في تحليل قوة بعض الخوارزميات. ومع ذلك، لا يعتبر فضاء هامينغ بذاته أداة تشفير قوية، وعادةً ما يتم استخدام تقنيات أكثر تعقيدًا لتأمين البيانات.
توسعات فضاء هامينغ
هناك العديد من التوسعات والمفاهيم ذات الصلة بفضاء هامينغ، بما في ذلك:
- فضاء لي (Lee Space): هو تعميم لفضاء هامينغ يستخدم مسافة لي بدلاً من مسافة هامينغ. مسافة لي تأخذ في الاعتبار قيم الرموز، وليس فقط الاختلافات بينها.
- فضاء جراي (Gray Space): هو ترميز حيث تختلف كلمتان متجاورتان ببت واحد فقط. هذه الخاصية مفيدة في التطبيقات التي تتطلب تغييرات تدريجية في القيم.
- رموز هامينغ (Hamming Codes): هي فئة معينة من رموز تصحيح الأخطاء التي تم تصميمها باستخدام فضاء هامينغ.
خاتمة
فضاء هامينغ هو مفهوم أساسي في نظرية المعلومات والترميز، ويوفر إطارًا رياضيًا قويًا لتحليل وتصميم رموز تصحيح الأخطاء. من خلال تحديد مسافة هامينغ كمقياس للاختلاف بين السلاسل، يمكننا إنشاء رموز قادرة على اكتشاف وتصحيح الأخطاء التي تحدث أثناء الإرسال أو التخزين. بالإضافة إلى ذلك، يجد فضاء هامينغ تطبيقات في مجموعة واسعة من المجالات الأخرى، بما في ذلك الإحصاء وعلم الأحياء المعلوماتي ومعالجة الصور والتعرف على الأنماط. فهم فضاء هامينغ ومسافة هامينغ يمكّن المهندسين والعلماء من تطوير حلول مبتكرة لمشاكل متنوعة في معالجة البيانات والاتصالات.