مرحلهی بعد از تشخیص خطا در شبکههای کامپیوتری، اصلاح آنها میباشد. به هنگام ارسال داده از فرستنده به گیرنده، کدهای اصلاح خطا جهت شناسایی و تصحیح خطاها مورد استفاده قرار میگیرند. اصلاح خطا در شبکه های کامپیوتری را میتوان به دو روش زیر انجام داد:
- Backward error correction یا اصلاح خطای رو به عقب
گیرنده پس از شناسایی و کشف خطا، از فرستنده درخواست مجدد کل دادهها را دارد.
- Forward error correction یا اصلاح خطا رو به جلو
در این حالت، پس از شناسایی خطا فرستنده از کد اصلاح خطا استفاده نموده که به کمک آن خطاها به صورت اتوماتیک، تصحیح میشوند.
یک بیت اضافه میتواند خطا را تشخیص دهد اما نمیتواند آن را اصلاح کند.
به منظور اصلاح خطا، محل دقیق آن باید مشخص باشد. به عنوان مثال، در صورتی که قصد داشته باشیم خطای تک بیتی را محاسبه نماییم، کد اصلاح خطا مشخص میکند که کدام یک از هفت بیت دارای خطا است. جهت دستیابی به این هدف میبایست چندین بیت اضافه، بیافزاییم.
فرض کنید (r)، تعداد بیتهای اضافه و (d) تعداد کل بیتهای داده میباشد. تعداد بیتهای مازاد r را میتوان با استفاده از این فرمول محاسبه کرد:
2r>=d+r+1
R.W Hamming یک تکنیک جهت تعیین موقعیت بیتی (bit) که خطا دارد، تحت عنوان کد Hamming، تعریف کرده است. در ضمن میتوان آن را در هر طول واحد داده اجرا کرد و از رابطهی بین واحدهای داده و واحدهای اضافه استفاده کرد.
کد Hamming
- Parity bits: بیتی است که به داده اصلی بیتهای باینری، پیوست میشود تا تعداد کل 1ها فرد یا زوج باشد.
- Even parity: به منظور بررسی even parity، در صورتی که تعداد کل 1ها زوج باشد، مقدار عددی parity bit برابر صفر است. چنانچه تعداد کل 1ها فرد باشد، مقدار عددی parity bit برابر یک خواهد بود.
- Odd Parity: به منظور بررسی odd parity، در صورتی که تعداد کل 1ها زوج باشد، مقدار عددی parity bit برابر یک است. چنانچه تعداد کل 1ها فرد باشد، مقدار عددی parity bit برابر صفر خواهد بود.
الگوریتم کد همینگ در اصلاح خطا در شبکه های کامپیوتری
- اطلاعات بیتهای “d” به بیتهای افزونه “r” اضافه میشوند تا d+r را تشکیل دهند.
- مکان تمامی ارقام d+r، عدد اعشاری اختصاص داده میشود.
- بیتهای “r” در موقعیت مکانی 1،2،… 2k-1 قرار میگیرند.
- در پایان فرایند دریافت، parity bitها محاسبه میشوند. مقدار عددی اعشاری parity bitها، خطا را تعیین میکنند.
رابطهی بین موقعیت مکانی خطا (Error Position) و اعداد باینری (Binary Number)
حال مفهوم کد همینگ را در قالب یک مثال، توضیح میدهیم.
فرض کنید دادهی اصلی که قرار است ارسال شود، 1010 است.
تعداد کل بیتهای دادهی d =ا4
تعداد بیتهای مازاد r: ا 2r >= d+r+1ا2r >= d+r+1 2r >= d+r+12r >= d+r+2r >= d+r+11
2r>= 4+r+1
بنابراین، مقدار عددی r که بتوان در فرمول بالا گذاشت، 3 میباشد.
تعداد کل بیتها = d+r = 4+3 = 7
تعیین موقعیت بیتهای مازاد
تعداد بیتهای مازاد، 3 است. این سه بیت به صورت r1, r2, r4 نشان داده میشوند. موقعیت مکانی بیتهای مازاد بعد از رسیدن به توان دو محاسبه میشود. بنابراین، موقعیت متناظر آنها 1, 21, 22 در نظر گرفته میشود.
موقعیت r1 = ا1
موقعیت r2 = ا2
موقعیت r4 = ا4
نمایش دادهها بر روی parity bit های اضافه شده
مشخص کردن Parity bits
– تعیین بیت r1

همان طور که از شکل بالا مشخص است، bit positionهایی که شامل 1 در موقعیت اول هستند، 1 ، 3 ، 5 و 7 میباشند. حال even-parity check را بر روی موقعیت این بیتها انجام میدهیم. تعداد کل 1ها در این موقعیتهای بیت مربوط به r1، زوج است بنابراین، مقدار بیت r1 برابر صفر است.
– تعیین بیت r2
بیت r2 را میتوان با انجام parity check بر روی بیتهایی که موقعیت آنها در نمایش باینری شامل یک در موقعیت دوم میباشد محاسبه نمود.
همان طور که از شکل بالا مشخص است، bit positionهایی که شامل 1 در موقعیت دوم هستند، 2 ، 3 ، 6 و 7 میباشند. حال even-parity check را بر روی موقعیت این بیتها انجام میدهیم. تعداد کل 1ها در این موقعیتهای بیت مربوط به r2، فرد است، بنابراین مقدار بیت r2 برابر یک است.
– تعیین بیت r4
بیت r4 را میتوان با انجام parity check بر روی بیتهایی که موقعیت آنها در نمایش باینری شامل یک در موقعیت سوم میباشد محاسبه نمود.

بیت R1
موقعیت بیتهای r1 در جایگاه 1، 3 ، 5 و 7 میباشد.
همان طور که از شکل بالا مشخص است، نمایش باینری R1 عدد 1100 میباشد. حال ما even-parity check را انجام میدهیم، مجموع کل 1های پیوست شده به بیت r1 یک عدد زوج است. بنابراین مقدار r1 برابر صفر میباشد.
بیت R2
موقعیت بیتهای r2 در جایگاه 2 ، 3 ، 6 و 7 میباشد.
همان طور که از شکل بالا مشخص است، نمایش باینری R2 عدد 1001میباشد. حال ما even-parity check را انجام میدهیم، مجموع کل 1های پیوست شده به بیت r2 یک عدد زوج است. بنابراین مقدار r2 برابر صفر میباشد.
بیت R4
موقعیت بیتهای r4 در جایگاه 4 ، 5 ، 6 و 7 میباشد.
همان طور که از شکل بالا مشخص است، نمایش باینری R4 عدد 1011 میباشد. حال ما even-parity check را انجام میدهیم، مجموع کل 1های پیوست شده به بیت r4 یک عدد فرد است. بنابراین مقدار r4 برابر یک میباشد.