هامينغ باوند

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

تتكون الرسالة الأصلية والنسخة المشفرة منها من أبجدية مكونة من q حرفًا. تحتوي كل كلمة مشفرة على n حرفًا. الرسالة الأصلية (بطول m ) أقصر من n حرفًا. تُحوّل الرسالة إلى كلمة مشفرة مكونة من n حرفًا بواسطة خوارزمية تشفير، ثم تُرسل عبر قناة مشوشة ، وأخيرًا تُفك شفرتها بواسطة جهاز الاستقبال. تفسر عملية فك التشفير الكلمة المشفرة المشوشة، والتي يُشار إليها ببساطة بالكلمة ، على أنها الكلمة المشفرة الصحيحة "الأقرب" إلى سلسلة الأحرف n المستلمة.

رياضيًا، يوجد بالضبط q ^m رسالة ممكنة بطول m ، ويمكن اعتبار كل رسالة متجهًا بطول m . يحوّل نظام التشفير متجهًا ذا m بُعد إلى متجه ذي n بُعد. يوجد بالضبط q ^m كلمة رمزية صالحة، ولكن يمكن استقبال أي كلمة من بين q ⁿ كلمة، لأن القناة المشوشة قد تشوه حرفًا واحدًا أو أكثر من حروف n عند إرسال الكلمة الرمزية.

ويترتب على ذلك تعريف${\displaystyle d}$هذا إن كان على الأكثر

${\displaystyle t=\left\lfloor {\frac {1}{2}}(d-1)\right\rfloor }$

إذا حدثت أخطاء أثناء إرسال كلمة مشفرة، فإن فك التشفير بأقل مسافة سيفك تشفيرها بشكل صحيح (أي أنه يفك تشفير الكلمة المستلمة على أنها الكلمة المشفرة التي تم إرسالها). وبالتالي، يُقال إن الشفرة قادرة على التصحيح.${\displaystyle t}$أخطاء.

لكل كلمة سرية${\displaystyle c\in C}$لنفترض كرة ذات نصف قطر ثابت${\displaystyle t}$حول${\displaystyle c}$كل زوج من هذه الكرات ( كرات هامينغ ) لا يتقاطع بواسطة${\displaystyle t}$خاصية تصحيح الأخطاء. دع${\displaystyle m}$ليكن عدد الكلمات في كل كرة (بمعنى آخر، حجم الكرة). يمكن للكلمة الموجودة في مثل هذه الكرة أن تنحرف في أكثر من${\displaystyle t}$مكونات من مكونات مركز الكرة ، وهو كلمة سرية. ثم يتم الحصول على عدد هذه الكلمات عن طريق اختيار ما يصل إلى${\displaystyle t}$التابع${\displaystyle n}$مكونات كلمة السر للانحراف إلى أحد${\displaystyle (q-1)}$القيم الأخرى المحتملة (تذكر، الرمز هو${\displaystyle q}$-ary: يأخذ القيم في${\displaystyle {\mathcal {A}}_{q}^{n}}$). هكذا،

${\displaystyle m={\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}.}$

${\displaystyle A_{q}(n,d)}$يمثل (الحد الأقصى) إجمالي عدد الكلمات المشفرة في${\displaystyle C}$وبالتالي، بحسب تعريف${\displaystyle t}$، وهو أكبر عدد من الكرات التي لا تشترك فيها أي كرتين في كلمة واحدة. بأخذ اتحاد الكلمات في هذه الكرات المتمركزة حول الكلمات المشفرة، ينتج مجموعة من الكلمات، تُحسب كل منها مرة واحدة فقط، وهي مجموعة جزئية من${\displaystyle {\mathcal {A}}_{q}^{n}}$(أين${\displaystyle |{\mathcal {A}}_{q}^{n}|=q^{n}}$(كلمات) وهكذا:

${\displaystyle A_{q}(n,d)\times m=A_{q}(n,d)\times {\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}\leq q^{n}.}$

من أين:

${\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}}.}$

لـ${\displaystyle A_{q}(n,d)}$الرمز ج (مجموعة فرعية من${\displaystyle {\mathcal {A}}_{q}^{n}}$نصف قطر التغطية للمجموعة C هو أصغر قيمة لـ r بحيث يكون كل عنصر من${\displaystyle {\mathcal {A}}_{q}^{n}}$يتم احتواء كل كرة من الكرات ذات نصف القطر r والمتمركزة عند كل كلمة من كلمات C على الأقل . نصف قطر التعبئة لـ C هو أكبر قيمة لـ s بحيث تكون مجموعة الكرات ذات نصف القطر s والمتمركزة عند كل كلمة من كلمات C منفصلة عن بعضها البعض .

من برهان حد هامينغ، يمكن ملاحظة أنه بالنسبة لـ${\displaystyle t\,=\,\left\lfloor {\frac {1}{2}}(d-1)\right\rfloor }$لدينا:

s ≤ t و t ≤ r .

لذلك، s ≤ r ، وإذا تحققت المساواة فإن s = r = t . حالة المساواة تعني أن حد هامينغ قد تحقق.

تُسمى الشفرات التي تحقق حد هامينغ بالشفرات المثالية . ومن الأمثلة على ذلك الشفرات التي تحتوي على كلمة رمزية واحدة فقط، والشفرات التي تمثل كامل...${\displaystyle {\mathcal {A}}_{q}^{n}}$مثال آخر هو رموز التكرار ، حيث يُكرر كل رمز من رموز الرسالة عددًا فرديًا ثابتًا من المرات للحصول على كلمة رمزية يكون فيها q = 2. تُسمى جميع هذه الأمثلة عادةً بالرموز الكاملة البسيطة . في عام 1973، أثبت تيتافاينن ^{[ 1 ]} أن أي رمز كامل غير بسيط على أبجدية ذات قوى أولية له معلمات رمز هامينغ أو رمز غولاي .

يمكن تفسير الشفرة المثالية بأنها تلك التي تملأ فيها الكرات ذات نصف قطر هامينغ t، والمتمركزة حول الكلمات المشفرة، الفراغ تمامًا (حيث t هو نصف قطر التغطية = نصف قطر التعبئة). أما الشفرة شبه المثالية فهي تلك التي تكون فيها الكرات ذات نصف قطر هامينغ t، والمتمركزة حول الكلمات المشفرة، منفصلة، ​​وتغطي الكرات ذات نصف القطر t + 1 الفراغ، مع احتمال وجود بعض التداخلات. ^{[ 2 ]} وبعبارة أخرى، تكون الشفرة شبه مثالية إذا كان نصف قطر تغطيتها أكبر بواحد من نصف قطر تعبئتها. ^{[ 3 ]}

• متجه إلى جيلبرت-فارشاموف
• مقيد بجريسمر
• متجه إلى جونسون
• بلوتكين المقيد
• نظرية التشوه المعدل
• متجهة إلى سينغلتون

• بي جيه كاميرون؛ جيه إيه ثاس؛ إس إي باين (1976). "قطبية الأشكال السداسية المعممة والرموز الكاملة". Geometriae Dedicata . 5 (4): 525–528 . doi : 10.1007/BF00150782 . S2CID 121071671 . 
• هيل، ر. (1988). مدخل إلى نظرية الترميز . مطبعة جامعة أكسفورد . ISBN 0-19-853803-0.
• ماكويليامز، إف جيه ؛ إن جيه إيه سلون (1977). نظرية رموز تصحيح الأخطاء . نورث هولاند. ISBN 0-444-85193-3.
• بليس، ف. (1982). مقدمة في نظرية رموز تصحيح الأخطاء . جون وايلي وأولاده. ISBN 0-471-08684-3.
• رومان، س. (1992)، الترميز ونظرية المعلومات ، GTM ، المجلد  134، نيويورك: سبرينغر-فيرلاغ، ISBN 0-387-97812-7
• تيتافاينن، أ. (1973). "حول عدم وجود رموز مثالية على الحقول المنتهية" . مجلة SIAM للرياضيات التطبيقية 24 : 88-96 . doi : 10.1137/0124010 .
• فان لينت، جيه إتش (1992). مقدمة في نظرية الترميز . جي تي إم . المجلد  86 (  الطبعة الثانية). سبرينغر-فيرلاغ. ISBN 3-540-54894-7.
• فان لينت، جيه إتش (1975). "دراسة استقصائية للرموز المثالية" . مجلة روكي ماونتن للرياضيات . 5 (2): 199-224 . doi : 10.1216/RMJ-1975-5-2-199 .