كد همينگ

[آبجی]

هرگاه یک کانال ارتباطی برای انتقال اطلاعات داشته باشیم در حین انتقال به دلیل وجود نویز اطلاعات دچار تغییر میشوند. باید روشی برای مشخص کردن این تغییرات داشته باشیم و بهتر است به روشی دست یابیم که میتواند این تغییرات ناخواسته یا خطا ها را اصلاح نماید. شکل یک (برگرفته از کتاب نظریه اطلاعات دیوید مک کی) نمونه هایی از کانالهای نویزی را نشان میدهد.

شکل یک گیرنده-فرستنده و کانال

در دهه ۱۹۵۰ میلادی ریچارد همینگ که در آزمایشگاههای شرکت بل کار میکرد به معرفی دسته ای از کد های اصلاح کننده خطا پرداخت که بنام خود او کدهای همینگ خوانده میشوند. شاید ساده ترین روش برای آشکار کردن خطای یک بیت در یک بایت، استفاده از بیت توازن است. در روش همینگ از سه بیت توازن برای آشکارسازی و اصلاح خطا استفاده میشود.
همانطور که در شکل مشخص است چهار بیت d1 الی d4 به عنوان داده ورودی در نظر گرفته میشوند. سپس با ترتیب نشان داده شده بیتهای توازن p1 تا p3 از XOR کردن بیت ها محاسبه میشوند. و در نهایت داده هفت بیتی بدست آمده ارسال میگردد.

شکل دو نحوه محاسبه بیتهای توازن

در مقصد بیت توازن با بیتهای گروه خود XOR میشود مثلا بیتهای p1 و d1 و d2 و d4 با هم XOR میشوند و نتیجه به عنوان بیت اول نشانه s1 در نظر گرفته میشود به همین ترتیب بیتهای دوم و سوم نشانه هم بدست می آیند. هرگاه هر سه بیت نشانه صفر باشد داده درست منتقل شده است. اما در صورت یک بودن هر یک از بیت های خطا رخ داده است. اگر سه بیت نشانه را از کوچک به بزرگ در کنار هم قرار دهیم یک عدد سه بیتی بدست میآید که مقدار آن نشان دهنده محل وقوع خطاست.

شکل سه : خطا در بیت ششم رخ داده است

با عوض کردن بیت مورد نظر داده اولیه بدست می آید. باید توجه داشت که این روش همینگ امکان اصلاح یک خطا را دارد و در صورت بروز دو خطا فقط امکان آشکار سازی وجود دارد.
طرح مسئله:
می خواهیم یک برنامه بنویسیم که روی یک تصویر bitmap نویز ایجاد کند. نویز ما با یک احتمال مشخص مقدار بیت را عوض میکند.

شکل چهار برنامه و نمایش تصویر (شارلیز ترون) بدون نویز.

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

شکل چهار عبور یک، دو و سه بار تصویر (شارلیز ترون) از کانال نویزدار در نواحی یک تا سه نشان داده شده اند.

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

شکل پنج: قسمت اول تصویر (شارلیز ترون) با نویز دو در هزار، قسمت دوم پس از تصحیح همینگ.

شکل شش: قسمت اول تصویر (هیلاری داف) با نویز دو در هزار، قسمت دوم پس از تصحیح همینگ.

نکته مهم:
کد برنامه برای خوانایی readability بیشتر بصورت غیر کارآمد inefficient نوشته شده قبل از اجرا باید آن را بهینه کرد. متغیرهای اضافی میتوانند حذف شوند.
قسمتی از کد برنامه:

private void Hamming1(int i, out int o1,out int o2)
{ // یک بایت دریافت شده و در دو بایت کد میشود
o1 = o2 = 0;
int[] Arro = new int[] { 0, 0, 0, 0, 0, 0, 0, 0 }; // قابل اصلاح
Arro = Dec2Bin(i);
int d1, d2, d3, d4; // قابل حذف
d1 = Arro[0]; d2 = Arro[1]; d3 = Arro[2]; d4 = Arro[3];
int p1, p2, p3;
int s = 0;
s = d1 + d2 + d4; // XOR محاسبه
p1 = (s % 2);
s = 0;
s = d1 + d3 + d4; // XOR محاسبه
p2 = (s % 2);
s = 0;
s = d2 + d3 + d4;
p3 = (s % 2);

o1 = p1 + 2 * p2 + 4 * d1 + 8 * p3;
o1 += 16 * d2 + 32 * d3 + 64 * d4;

d1 = Arro[4]; d2 = Arro[5]; d3 = Arro[6]; d4 = Arro[7];
s = 0;
s = d1 + d2 + d4;
p1 = (s % 2);
s = 0;
s = d1 + d3 + d4;
p2 = (s % 2);
s = 0;
s = d2 + d3 + d4;
p3 = (s % 2);

o2 = p1 + 2 * p2 + 4 * d1 + 8 * p3;
o2 += 16 * d2 + 32 * d3 + 64 * d4;

}

private int Hamming2(int i) //بازیابی و تصحیح
{
int[] Arr1 = new int[] { 0, 0, 0, 0, 0, 0, 0, 0 };
Arr1 = Dec2Bin(i);
int d1, d2, d3, d4;
int p1, p2, p3;
int s = 0;
p1 = Arr1[0]; p2 = Arr1[1]; d1 = Arr1[2]; p3 = Arr1[3];
d2 = Arr1[4]; d3 = Arr1[5]; d4 = Arr1[6];

int synd0, synd1, synd2 ,synd;

s = 0;
s = p1 + d1 + d2 + d4;
synd0 = (s % 2);

s = 0;
s = p2 + d1 + d3 + d4;
synd1 = (s % 2);

s = 0;
s = p3 + d2 + d3 + d4;
synd2 = (s % 2);

synd = synd0 + 2*synd1 + 4*synd2;

switch (synd)
{
case 0:
return d1 + 2 * d2 + 4 * d3 + 8 * d4;
case 1:
return d1 + 2 * d2 + 4 * d3 + 8 * d4;
case 2:
return d1 + 2 * d2 + 4 * d3 + 8 * d4;
case 3:
return (1-d1) + 2 * d2 + 4 * d3 + 8 * d4;
case 4:
return d1 + 2 * d2 + 4 * d3 + 8 * d4;
case 5:
return d1 + 2 * (1-d2) + 4 * d3 + 8 * d4;
case 6:
return d1 + 2 * d2 + 4 * (1-d3) + 8 * d4;
case 7:
return d1 + 2 * d2 + 4 * d3 + 8 * (1-d4);
default:
return 0;
}