Electric Engineering مهندسی برق

نظریه کدگذاری

مقدمه

نظریه کدگذاری که در سال ۱۹۴۸ توسط ریچارد همینگ پایه‌ریزی شد به بررسی

روش‌های کدگذاری اطلاعات می‌پردازد. وی پی برده بود هنگامی که رایانه از یک عمل

رایج نسخه‌برداری می‌کند و با عمل دیگری شروع به کار می‌کند، هرگز نمی‌تواند به

حالت اولیه باز گردد. نظریه کدگذاری مثال قابل توجهی از ریاضی محض در حل مسائل

علمی است. اگر چه برخی از رمزهای ساده دارای ساختاری هستند که نیاز زیادی به

ریاضیات ندارند، با این حال ویژگی رمزها از کشفیات ریاضیات است. مانند هستة

ارسال خطی که اثبات فعالیتهای واقعی را ممکن می‌سازد و بدون این‌گونه برهان‌ها،

رمزها در حقیقت بدون استفاده می‌باشند. علاوه بر این، ریاضیات موجب ایجاد رمزها در

ابعاد دیگر می‌شود و با افزایش قابلیت تصحیح خطا، اثبات‌هایی را برای موجودیت یا

عدم موجودیت رمزها ارایه داده‌است.

دسته بندی

نظریهٔ رمزنگاری یکی از راه‌های حل مساله در بخش‌های مختلف علوم

(مثل نظریه اطلاعات، مهندسی برق، ریاضیات و علوم رایانه، انتقال داده)

است;به این ترتیب که می توان با استفاده از آن روش‌های مطمئن برای انتقال داده‌ها

طراحی کرد به طوری تکرارهای بی مورد کم و خطاها کاهش یابد. سه دسته کد وجود

دارد :

۱: رمز گذاری منبع (فشرده‌سازی داده‌ها )

۲: رمز گذاری مسیر انتقال (تصحیح خطای انتقال )

۳: منبع اشتراکی و رمز گذاری مسیر انتقال

مورد اول، رمز نگاری منبع، تلاش دارد برای موثر تر انتقال دادن داده‌ها، آنها را فشرده

کند .مثال عملی آن هر روز در اینترنت، وقتی از پسوند zip برای انتقال فایل‌های

مختلف استفاده می کنیم قابل مشاهده است .چرا که حجم مورد انتقال را کم کرده و

ترافیک شبکه را کاهش می دهد. مورد دوم، رمز گذاری مسیر انتقال، بیت هایی را به

داده ای مورد انتقال اضافه می‌کند تا آنها را در اختلالات موجود در مسیر انتقال سالم به

مقصد برساند .کار بر عادی ممکن است از کاربردهای معمول این نوع از رمز نگاری

بی خبر باشد . برای نمونه یک CD معمولی از روش کد گذاری Reed-Solomon

برای تصحیح خطای ناشی از خراش و غبار استفاده می‌کند .در این مثال مسیر انتقال داده

خود CD خواهد بود! گوشی‌های همراه نیز از نوعی کد گذاری برای تصحیح خطای

          ناشی از محو شدگی سیگنال و مخابرهٔ رادیویی با فرکانس بالا، بهره می برد .

رمز گذاری منبع

به طور ساده هدف این کار این است که داده‌های منبع را گرفته و آنرا کوچکتر کند.

انتروپی منبع میزان اطلاعات است . اساسا روش‌های کد گذاری منبع تکرار بی مورد را

کم می کنند تا با بیت‌های کمتر اطلاعات بیشتری را منتقل کنند. فشرده سازی داده‌ها همان

 گونه که از نامش پیداست تلاش دارد که متوسط طول پیام‌های ارسالی را بر اساس یک

 مدل احتمالاتی فرضی و ویژه به نام entropy encodingکاهش دهد . تکنیک‌های

متعددی که برنامه‌های فشرده ساز استفاده مکنند در تلاشند که به حد انتروپی منبع

یعنی(C(x) ≥ H(x برسند .که در ان(H(x انتروپی منبع و(C(x انتروپی فایل پس از

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

نیست !

رمز گذاری مسیر انتقال

رمز گذاری مسیر انتقال: هدف این رمز گذاری یافتن کد هایی است که سریع تر منتقل

می شوند، شامل تعداد زیادی کد واژهٔ صحیح هستند و می توانند خطاها را تصحیح کنند

یا اینکه حد اقل تعداد زیادی از خطاها را تشخیص دهند .کارایی برنامه‌ها در این زمینه

نوعی سبک و سنگین کردن نیاز دارد .به همین دلیل برنامه‌ها هر کدام کدهای متناسب

خود را دارند .ویژگی‌های مورد نیاز برای هر کد بستگی به این دارد که در انتقال مربوط

 به آن کد احتمال وقوع چه خطاهایی وجود دارد، برای نمونه درمورد CD‌های معمولی

خطاهای رایج خراش‌ها و گرد و غبار هستند . پس داده‌ها روی سطح دیسک توضیع می

شوند . به عنوان یک مثال نه چندان خوب از کد گذاری، کد گذاری تکراری ساده، مورد

قابل فهمی از این روش است . در این روش یک بخش از بیت‌های منبع را گرفته و آن را

سه بار می فرستیم .درمقصد، دریافت کننده این سه قسمت را گرفته و آنها را بیت به بیت

 چک می‌کند، و آن مقداری را که برای هر بیت فراوانی بیشتری دارد به عنوان مقدار

صحیح بر می گزیند .راه پیچیده تر آن است که بیت‌ها را کاملا پشت سر هم نفرستییم

.بلکه آن هارا برگ برگ کنیم .داده‌ها ابتدا به چهار دسته تقسیم می شوند، سپس در یک

حلقه یک بیت از اولی، یک بیت از دومی و ...را می فرستیم . این کار سه بار تکرار

می‌شود تا جایی که داده‌ها روی سطح دیسک توضیع شوند .در مورد روش کد گذاری

تکراری ساده شاید این روش موثر نباشد .اما کدهای شناخته شدی قدرتمندی وجود دارند

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

 از خراش و غبار بسیار موثرند . کدهای دیگر برای کاربردهای دیگر مفیدند .

کد گذاری دیجیتال

عبارت نظریهٔ کد گذاری جبری زیر مجموعه ای از نظریهٔ کد گذاری را بیان می‌کند که

در آن ویژگی‌های کدها با عبارات جبری بیان می‌شود .نظریهٔ کد گذاری جبری اساسا به

دو دسته تقسیم می‌شود :

۱. کد هایی با بلوک‌های خطی.

۲.کدهای پیچشی (کانولوشن).

این نظریه سه ویژگی زیر از کدها را بررسی می‌کند :

۱. طول کد واژه ها

۲.تعداد کل کد واژه‌های قابل قبول

۳.حد اقل فاصلهٔ میان دو کد واژهٔ قابل قبول، بیشتر با استفاده از روش فاصلهٔ همینگ و در بعضی از موارد با استفاده از روش فاصلهٔ لی.

کد گذاری آنالوگ

اطلاعات به طور آنالوگ در شبکهٔ عصبی مغز، در پردازش سیگنال‌های آنالوگ و

الکترونیک آنالوگ، کد گذاری می شوند .نمودهای کد گذاری آنالوگ در تصحیح خطای

 آنالوگ، فشرده سازی داده‌های آنالوگ و پنهان سازی آنالوگ قابل مشاهده است .

کار بردهای دیگری از نظریهٔ رمز نگاری

غیر از آنچه که در بالا به آن اشاره شد، طراحی کد برای همگام سازی، از دیگر موارد

مد نظر نظریهٔ کد گذاری است .یک کد می تواند طوری طراحی شود که به راحتی

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

بفرستد .

دیگر کاربرد کدها که در برخی از گوشی‌های همراه استفاده می‌شود، دسترسی چندگانه تقسیم کدی می‌باشد .

                                        كد همينگ    RSS 

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

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

در دهه ۱۹۵۰ میلادی ریچارد همینگ که در آزمایشگاههای شرکت بل کار میکرد به معرفی دسته ای از کد های اصلاح کننده خطا پرداخت که بنام خود او کدهای همینگ خوانده میشوند. شاید ساده ترین روش برای آشکار کردن خطای یک بیت در یک بایت، استفاده از بیت توازن است. در روش همینگ از سه بیت توازن برای آشکارسازی و اصلاح خطا استفاده میشود.
همانطور که در شکل مشخص است چهار بیت 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;
}

يك مثال ديگر:

کد بدون وزن همینگ :

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

ما در اینجا کد همینگ با حداقل فاصله 3 را توضیح می دهیم. یعنی بیتهایی را که به آنها اضافه می کنیم 3 بیت می باشد. چون در کد همینگ به منظور تشخیص و تصحیح خطا باید بیتهایی را به کدمان اضافه کنیم.

اگر بخواهیم کد NBCD را با حداقل فاصله 3 ارسال کنیم. باید به کد NBCD 3 بیت اضافه کنیم. که اطلاعات ارسالی به صورت زیر می شود.
c1 c2  b3 c4 b5 b6 b7
که در اینجا بیت c1 و c2 و c4 سه بیتی هستند که به کدمان اضافه می شوند و به آنها بیتهای الحاقی می گویند و به بیتهای b3 و b5 و b6 و b7 بیتهای اطلاعاتی می گویند.

مقادیر سه بیت الحاقی به صورت زیر محاسبه می شود.

C1={ b3, b5 , b7} c2={ b3 , b6 , b7 } c3={ b5 , b6 , b7 }

که در آنها اگر تعداد یک ها زوج بود حاصل c برابر صفر و اگر فرد بود برابر یک شو.د.

به عنوان مثال رقم 5 در کد NBCD را به روش زیر ارسال می کنیم.


c1=? c2=? b3=0 c4=? b5=1 b6=0 b7=1


c1={ b3 , b5 , b7 }= { 0,1,1} ====> c1=0



1= c2={ b3 , b6 , b7 }= { 0,0,1 }====> c2



0= c3={ b5 , b6 , b7 }= { 1,0,1 }====> c3



پس بر اساس اعداد به دست آمده عدد 5 هنگام ارسال به صورت 0100101 ارسال می شود

كد همينگ كدي است خطي دودويي كه قابليت تصحيح و تشخيص هر خطاي منفرد در درون هر بلاك را دارد. اين كد كه در سال 1950 توسط ريچارد همينگ كشف گرديد، از آن در انتقال اطلاعات و در سيستمهاي Teletext و Telecommunication استفاده مي‌شود. كد همينگ باعث مي‌شود كه درجه اطمينان داده در ارسال داده از راه دور زياد شود.

در كد همينگ رابطه 2 ^ m >= n+1برقرار است كه:

n= تعداد بيتهاي موجود در يك بلاك
m= تعداد بيتهاي كنترلي در بلاك (m=n-k)
k=تعداد بيتهاي اطلاعاتي در بلاك

Coding
براي به كد درآوردن اطلاعات توسط كد همينگ بايد مراحل زير را انجام داد:

ابتدا توسط رابطه گفته شده تعداد بيتهاي كنترلي را با توجه به طول بلاك و تعداد بيتهاي اطلاعاتي به دست مي‌آوريم. بيتهاي موجود در بلاك از سمت راست از يك شماره‌گذاري مي‌شوند.

اگر تعداد بيتها (مجموع كنترلي و اطلاعاتي) فرد شد. يك صفر به سمت راست اضافه ميكنيم. بايد توجه داشت كه اين بيت در شماره‌گذاري شركت نمي‌كند.

بيتهايي كه توانهايي از دو هستند (...و1،2،4,8) را با بيتهاي كنترلي پر مي‌كنيم و بقيه بيتها را (...و3،5،6،7،9) با بيتهاي اطلاعاتي. هر بيت كنترلي به گونه‌اي پر مي‌شود كه توازن (parity) بيت كنترلي و مجموعه‌اي از بيتها زوج باشد. براي چك كردن توازن بايد به صورت زير عمل كنيم:

توازن بيتهايي را چك مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر 2، يك باشد.

توازن بيتهايي را چك مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر 4، دو يا سه باشد.

توازن بيتهايي را چك مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر 8، چهار، پنج، شش يا هفت باشد.

توازن بيتهايي را چك مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر 16، هشت، نه، ده، يازده، دوازده، سيزده، چهارده يا پانزده باشد. والي آخر.

Decoding
بايد مراحل زير را انجام داد:

محاسبه توازن بيتها

توازن بيتهايي را محاسبه مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر 2، يك باشد.

توازن بيتهايي را محاسبه مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر 4، دو يا سه باشد.

توازن بيتهايي را محاسبه مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر 8، چهار، پنج، شش يا هفت باشد.

توازن بيتهايي را محاسبه مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر 16، هشت، نه، ده، يازده، دوازده، سيزده، چهارده يا پانزده باشد. والي آخر.

سپس توازنهاي به دست آمده را به ترتيب به صورت يك عدد دودويي مي‌نويسيم. ارزش توازن به دست آمده در مرحله اول 20، مرحله دوم 21، مرحله سوم 22 و الي آخر مي‌باشد.

اگر عدد به دست آمده در مرحله قبل صفر باشد يعني خطايي وجود ندارد ولي اگر غير صفر باشد، عدد حاصل شماره بيتي كه خطا دارد را به صورت دودويي نشان مي‌دهد. بايد بيت مورد نظر معكوس شود.

در مرحله آخر بيتهاي كنترلي را حذف مي‌كنيم و اگر در مرحله دو از Coding بيتي اضافه شده آن را نيز حذف ميكنيم. در نهايت داده اصلي به دست مي‌آيد.

مثال:

Coding:
01111101000 داده اصلي
k= 11
m= 4
n=15

توازن بيتهايي را چك مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر 2، يك باشد

توازن بيتهايي را چك مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر 4، دو يا سه باشد

توازن بيتهايي را چك مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر 8، چهار، پنج، شش يا هفت باشد

توازن بيتهايي را چك مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر 16، هشت، نه، ده، يازده، دوازده، سيزده، چهارده يا پانزده باشد

حال داده را با يك خطا در بيت يازدهم ارسال مي‌كنيم. داده ارسال شده به صورت زير خواهد بود :

0111010110000010

Decoding:

توازن بيتهايي را محاسبه مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر 2، يك باشد:P1=1

توازن بيتهايي را محاسبه مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر 4، دو يا سه باشد:P2=1

توازن بيتهايي را محاسبه مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر 8، چهار، پنج، شش يا هفت باشد: P3=0

توازن بيتهايي را محاسبه مي‌كنيم كه باقيمانده تقسيم شماره بيت آنها بر شانزده، هشت، نه، ده، يازده، دوازده، سيزده، چهارده يا پانزده باشد:P4=1

توازنهاي به دست آمده نشان مي‌دهد كه بيت يازدهم داراي خطا است:

پس طبق الگوريتم بيت يازدهم را معكوس مي‌كنيم در نتيجه خواهيم داشت:

0111110110000010

پس از حذف بيتهاي كنترلي و بيت اضافه شده داده اصلي به دست خواهد آمد.

01111101000