کد چکش برای تصحیح خطای تک ، تشخیص خطای مضاعف

کد چکش یک کد بلوک است که قادر به تشخیص حداکثر دو خطای بیت همزمان و اصلاح خطاهای تک بیتی است. این توسط R. W. Hamming برای تصحیح خطا ساخته شده است.

در این روش برنامه نویسی ، منبع با وارد کردن بیت های اضافی در پیام ، پیام را رمزگذاری می کند. این بیت های اضافی بیت های اضافی هستند که در موقعیت های خاص در خود پیام ایجاد و درج می شوند تا تشخیص و تصحیح خطا را فعال کنند. هنگامی که مقصد این پیام را دریافت می کند ، محاسبات را برای تشخیص خطاها انجام می دهد و موقعیت بیتی را که خطا دارد پیدا می کند.

کد چکش برای تصحیح خطای تک

روش تصحیح خطای منفرد توسط کد چکش شامل دو بخش ، رمزگذاری در انتهای فرستنده و رمزگشایی در پایان گیرنده است.

رمزگذاری پیام توسط کدگذاری کد

روشی که توسط فرستنده برای رمزگذاری پیام استفاده شده است ، مراحل زیر را شامل می شود -

• مرحله 1 - محاسبه تعداد بیت های اضافی.
• مرحله 2 - قرار دادن بیت های اضافی.
• مرحله 3 - محاسبه مقادیر هر بیت اضافی.

هنگامی که بیت های اضافی در پیام تعبیه شدند ، این به مقصد ارسال می شود.

مرحله 1 - محاسبه تعداد بیت های اضافی.

اگر پیام حاوی تعداد M بیت های داده باشد ، تعداد بیت های اضافی به آن اضافه می شود تا بتواند حداقل (M + R + 1) حالت های مختلف را نشان دهد. در اینجا ، (M + R) مکان خطا را در هر یک از موقعیت های بیت نشان می دهد و یک حالت اضافی هیچ خطایی را نشان نمی دهد. از آنجا که ، بیت های R می توانند 2 حالت R را نشان دهند ، 2 R باید حداقل برابر با (M + R + 1) باشد. بنابراین معادله زیر باید نگه داشته شود -

مثال 1 - اگر داده ها از 7 بیت ، یعنی M = 7 ، حداقل مقدار R که معادله فوق را برآورده می کند 4 است ، (2 4 4 7 + 4 + 1). تعداد کل بیت ها در پیام رمزگذاری شده ، (M + R) = 11. این به عنوان (11،4) کد گفته می شود.

مرحله 2 - قرار دادن بیت های اضافی.

بیت های اضافی R که در موقعیت های بیت از قدرت 2 ، یعنی 1 ، 2 ، 4 ، 8 ، 16 و غیره قرار می گیرند. آنها در بقیه این متن به عنوان r ذکر می شوند₁(در موقعیت 1) ، r₂(در موقعیت 2) ، r₃(در موقعیت 4) ، r₄(در موقعیت 8) و غیره.

مثال 2 - اگر ، M = 7 به 4 می رسد ، موقعیت بیت های اضافی به شرح زیر است -

مرحله 3 - محاسبه مقادیر هر بیت اضافی.

بیت های اضافی بیت های برابری هستند. یک بیت برابری یک بیت اضافی است که باعث می شود تعداد 1s یکنواخت یا عجیب باشد. دو نوع برابری هستند -

• حتی برابری - در اینجا تعداد کل بیت های موجود در پیام یکنواخت است.
• برابری عجیب و غریب - در اینجا تعداد کل بیت های موجود در پیام عجیب است.

هر بیت اضافی ، r_i، به عنوان برابری ، به طور کلی حتی برابری ، بر اساس موقعیت بیت آن محاسبه می شود. این موقعیت های بیت را پوشش می دهد که نمایندگی باینری شامل 1 در موقعیت اول به جز موقعیت r است_iبشربنابراین -

• r₁بیت برابری برای کلیه بیت های داده در موقعیت هایی است که نمایندگی باینری شامل 1 در حداقل موقعیت قابل توجه است به استثنای 1 (3 ، 5 ، 7 ، 9 ، 11 و غیره)
• r₂بیت برابری برای کلیه بیت های داده در موقعیت هایی است که بازنمایی باینری شامل 1 در موقعیت 2 از سمت راست به جز 2 (3 ، 6 ، 7 ، 10 ، 11 و غیره)
• r₃بیت برابری برای کلیه بیت های داده در موقعیت هایی است که بازنمایی باینری شامل 1 در موقعیت 3 از سمت راست به جز 4 (5-7 ، 12-15 ، 20-23 و غیره)

مثال 3 - فرض کنید که پیام 1100101 باید با استفاده از کد حتی برابری چکش رمزگذاری شود. در اینجا ، M = 7 و R به 4 می رسد. مقادیر بیت های اضافی به شرح زیر خواهد بود -

از این رو ، پیام ارسال شده 11000101100 خواهد بود.

رمزگشایی یک پیام در کد چکش

هنگامی که گیرنده یک پیام دریافتی دریافت می کند ، محاسبات مجدد را برای تشخیص خطاها و اصلاح آنها انجام می دهد. مراحل محاسبه مجدد عبارتند از -

• مرحله 1 - محاسبه تعداد بیت های اضافی.
• مرحله 2 - قرار دادن بیت های اضافی.
• مرحله 3 - بررسی برابری.
• مرحله 4 - تشخیص و تصحیح خطا

مرحله 1) محاسبه تعداد بیت های اضافی

با استفاده از همان فرمول در رمزگذاری ، تعداد بیت های اضافی مشخص می شود.

جایی که M تعداد بیت های داده و R تعداد بیت های اضافی است.

مرحله 2) قرار دادن بیت های اضافی

بیت های اضافی R در موقعیت های بیت از قدرت 2 ، یعنی 1 ، 2 ، 4 ، 8 ، 16 و غیره قرار می گیرند.

مرحله 3) بررسی برابری

بیت های برابری بر اساس بیت های داده و بیت های اضافی با استفاده از همان قاعده ای که در طول تولید C محاسبه می شود محاسبه می شود₁, c₂, c₃, c₄و غیره

c₁= برابری (1 ، 3 ، 5 ، 7 ، 9 ، 11 و غیره)

c₂= برابری (2 ، 3 ، 6 ، 7 ، 10 ، 11 و غیره)

c₃= برابری (4-7 ، 12-15 ، 20-23 و غیره)

مرحله 4) تشخیص و تصحیح خطا

معادل اعشاری مقادیر باینری بیت های برابری محاسبه می شود. اگر 0 باشد ، هیچ خطایی وجود ندارد. در غیر این صورت ، مقدار اعشاری موقعیت بیتی را که خطا دارد ، می دهد. به عنوان مثال ، اگر C₁c₂c₃c₄= 1001 ، این بدان معنی است که بیت داده در موقعیت 9 ، معادل اعشاری 1001 ، خطا دارد. بیت برای دریافت پیام صحیح (از 0 به 1 یا برعکس) تبدیل می شود.

مثال 4 - فرض کنید که یک پیام ورودی 11110101101 دریافت می شود.

مرحله 1 - در ابتدا تعداد بیت های اضافی با استفاده از فرمول 2 r ≥ m + r + 1. محاسبه می شود. در اینجا ، m + r + 1 = 11 + 1 = 12. حداقل مقدار r به گونه ای که 2 r ≥ 12 است4

مرحله 2 - بیت های اضافی به صورت زیر قرار می گیرند -

مرحله 3 - حتی بررسی برابری انجام می شود -

c₁= EVEN_PARITY (1 ، 3 ، 5 ، 7 ، 9 ، 11) = 0

c₂= EVEN_PARITY (2 ، 3 ، 6 ، 7 ، 10 ، 11) = 0

c₃= EVEN_PARITY (4 ، 5 ، 6 ، 7) = 0

c₄= EVEN_PARITY (8 ، 9 ، 10 ، 11) = 0

مرحله 4 - از آنجا که مقدار بیت های چک c₁c₂c₃c₄= 0000 = 0 ، هیچ خطایی در این پیام وجود ندارد.

کد چکش برای تشخیص خطای مضاعف

کد چکش زدن را می توان برای اصلاح یک خطای واحد اصلاح کرد و با افزودن یک بیت برابری به عنوان MSB ، که XOR همه بیت های دیگر است ، خطاهای مضاعف را تشخیص دهد.

مثال 5 - اگر Codeword ، 11000101100 را در نظر بگیریم ، پس از اضافه کردن P = XOR (1،1،0،0،0،1،0،1،1،0،0) = 0 ، جدید ، جدید ارسال شده است. CodeWord ارسال می شود 011000101100 خواهد بود.

در انتهای گیرنده ، تشخیص خطا همانطور که در جدول زیر نشان داده شده است انجام می شود - < Pan> مرحله 1 - در ابتدا تعداد بیت های اضافی با استفاده از فرمول 2 r ≥ m + r + 1. محاسبه می شود.= 11 + 1 = 12. حداقل مقدار R به گونه ای که 2 R ≥ 12 4 باشد.