كد همينگ

[آبجی]

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

http://www.babaktavakoli.com/IMG/IMGT/TIMG0021.GIF
شکل یک گیرنده-فرستنده و کانال
در دهه ۱۹۵۰ میلادی ریچارد همینگ که در آزمایشگاههای شرکت بل کار میکرد به معرفی دسته ای از کد های اصلاح کننده خطا پرداخت که بنام خود او کدهای همینگ خوانده میشوند. شاید ساده ترین روش برای آشکار کردن خطای یک بیت در یک بایت، استفاده از بیت توازن است. در روش همینگ از سه بیت توازن برای آشکارسازی و اصلاح خطا استفاده میشود.
همانطور که در شکل مشخص است چهار بیت d1 الی d4 به عنوان داده ورودی در نظر گرفته میشوند. سپس با ترتیب نشان داده شده بیتهای توازن p1 تا p3 از XOR کردن بیت ها محاسبه میشوند. و در نهایت داده هفت بیتی بدست آمده ارسال میگردد.

http://www.babaktavakoli.com/IMG/IMGT/TIMG0025.GIF
شکل دو نحوه محاسبه بیتهای توازن
در مقصد بیت توازن با بیتهای گروه خود XOR میشود مثلا بیتهای p1 و d1 و d2 و d4 با هم XOR میشوند و نتیجه به عنوان بیت اول نشانه s1 در نظر گرفته میشود به همین ترتیب بیتهای دوم و سوم نشانه هم بدست می آیند. هرگاه هر سه بیت نشانه صفر باشد داده درست منتقل شده است. اما در صورت یک بودن هر یک از بیت های خطا رخ داده است. اگر سه بیت نشانه را از کوچک به بزرگ در کنار هم قرار دهیم یک عدد سه بیتی بدست میآید که مقدار آن نشان دهنده محل وقوع خطاست.

http://www.babaktavakoli.com/IMG/IMGT/TIMG0026.GIF
شکل سه : خطا در بیت ششم رخ داده است
با عوض کردن بیت مورد نظر داده اولیه بدست می آید. باید توجه داشت که این روش همینگ امکان اصلاح یک خطا را دارد و در صورت بروز دو خطا فقط امکان آشکار سازی وجود دارد.
http://www.babaktavakoli.com/IMG/IMG0147.jpg طرح مسئله:
می خواهیم یک برنامه بنویسیم که روی یک تصویر bitmap نویز ایجاد کند. نویز ما با یک احتمال مشخص مقدار بیت را عوض میکند.

http://www.babaktavakoli.com/IMG/IMGT/TIMG0022.jpg

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

http://www.babaktavakoli.com/IMG/IMGT/TIMG0020.jpg

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

http://www.babaktavakoli.com/IMG/IMGT/TIMG0023.jpg

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

http://www.babaktavakoli.com/IMG/IMGT/TIMG0024.jpg

شکل شش: قسمت اول تصویر (هیلاری داف) با نویز دو در هزار، قسمت دوم پس از تصحیح همینگ.
http://www.babaktavakoli.com/IMG/IMG0149.jpgنکته مهم:
کد برنامه برای خوانایی readability بیشتر بصورت غیر کارآمد inefficient نوشته شده قبل از اجرا باید آن را بهینه کرد. متغیرهای اضافی میتوانند حذف شوند.
http://www.babaktavakoli.com/IMG/IMG0099.jpg قسمتی از کد برنامه:

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;
}