محدوده همینگ

در ریاضیات و علوم رایانه، در حوزه نظریه کدگذاری (به انگلیسی: coding theory)، محدوده همینگ (به انگلیسی: Hamming bound) حدی بر پارامترهای یک کد بلوک (به انگلیسی: block code) قراردادی می‌باشد. همچنین به عنوان محدوده جاسازی گوی‌ها (به انگلیسی: sphere-packing bound) یا محدوه حجم (به انگلیسی: volume bound) از تفسیری بر حسب جاسازی گوی‌ها در فاصله همینگ (به انگلیسی: hamming metric) در فضایی از تمام کلمات ممکن، شناخته می‌شود. این یک محدودیت مهم در کارایی ایجاد می‌کند که بوسیله آن هرکد تصحیح خطا (به انگلیسی: error-correcting code) می‌تواند از فضایی که کدواژه‌هایش (به انگلیسی: code words) در آن جاسازی شده بهره گیرد. گفته می‌شود کدی که به محدوده همینگ می‌رسد یک کد کامل است.

تاریخچه کد‌ های تصحیح خطا

یک پیام اصلی و یک نسخه کدگذاری شده هر دو در الفبایی از q حرف ترکیب شده‌اند. هر کلمه کد شامل n حرف می باشد. پیام اصلی (به طولm ) کوتاه‌تر از n حرف می باشد. پیام به وسیله یک الگوریتم کدگذاری به یک کلمه کد n حرفی تبدیل می‌شود، از طریق یک کانال نویزی منتقل شده و در نهایت توسط گیرنده رمزگشایی خواهد شد. فرآیند رمزگشایی، یک کلمه کد آشفته را که فقط به عنوان یک حرف ذکر می شد را به عنوان کلمه کد معتبر که "نزدیک‌ترین" به رشته n حرفی دریافتی است، تفسیر می‌کند.

از نظر ریاضی، دقیقاً q^m پیام ممکن به طول m وجود دارد و هر پیام می‌تواند به عنوان یک بردار به طول m در نظر گرفته شود. طرح کدگذاری یک بردار m (vector) بعدی را به یک بردار n بعدی تبدیل می‌کند. دقیقاً q^m کلمه کد معتبر ممکن است، اما هر یک از qⁿ کلمات ممکن است دریافت شوند؛ زیرا کانال نویزی ممکن است یک یا چند واژه از n حرف را در هنگام ارسال یک کلمه کد تغییر دهد.

بیان حد

تعاریف مقدماتی

یک مجموعه الفبایی ${\mathcal {A}}_{q}$ مجموعه‌ای از نمادها با $q$ عنصر است. مجموعه رشته‌های به طول $n$ روی مجموعه الفبایی ${\mathcal {A}}_{q}$ بصورت ${\mathcal {A}}_{q}^{n}$ نشان داده می‌شوند. . (در این مجموعه رشته‌ها، $q^{n}$ رشته متمایز وجود دارد.) یک کد بلوکی ary- $q$ به طول $n$ زیرمجموعه‌ای از رشته‌های ${\mathcal {A}}_{q}^{n}$ است، که در آن مجموعه الفبایی ${\mathcal {A}}_{q}$ هر مجموعه الفبایی با $q$ عنصر می‌باشد. (انتخاب مجموعه الفبایی ${\mathcal {A}}_{q}$ تأثیری بر نتیجه نمی‌گذارد، به شرطی که الفبا دارای اندازه $q$ باشد).

تعریف حد

فرض کنیم $\ A_{q}(n,d)$نشان دهنده حداکثر اندازه ممکن یک کد بلوکی ary- $q$ با طول $n$ و حداقل فاصله همینگ (به انگلیسی: Hamming distance) $d$ بین عناصر کد بلوکی باشد. (که لزوما برای $q^{n}>1$ مثبت است).

سپس حد همینگ به صورت زیر است:

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

که در آن

$t=\left\lfloor {\frac {d-1}{2}}\right\rfloor .$

جستارهای وابسته

• Gilbert-Varshamov bound
• Griesmer bound
• Johnson bound
• Plotkin bound
• Rate-distortion theory
• Singleton bound

منابع

• P. J. Cameron; J. A. Thas; S. E. Payne (1976). "Polarities of generalized hexagons and perfect codes". Geometriae Dedicata. 5 (4): 525–528. doi:10.1007/BF00150782. S2CID 121071671.
• Hill, R. (1988). A First Course In Coding Theory. Oxford University Press. ISBN 0-19-853803-0.
• MacWilliams, F. J. ; N.J.A. Sloane (1977). The Theory of Error-Correcting Codes. North-Holland. ISBN 0-444-85193-3.
• Pless, V. (1982). Introduction to the Theory of Error-Correcting Codes. John Wiley & Sons. ISBN 0-471-08684-3.
• Roman, S. (1992), Coding and Information Theory, GTM, vol. 134, New York: Springer-Verlag, ISBN 0-387-97812-7
• Tietäväinen, A. (1973). "On the nonexistence of perfect codes over finite fields". SIAM J. Appl. Math. 24: 88–96. doi:10.1137/0124010.
• van Lint, J. H[۱]. (1992). Introduction to Coding Theory. GTM. Vol. 86 (2nd ed.). Springer-Verlag. ISBN 3-540-54894-7.
• van Lint, J. H. (1975). "A survey of perfect codes". Rocky Mountain Journal of Mathematics. 5 (2): 199–224. doi:10.1216/RMJ-1975-5-2-199.