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

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

سیستم تلفن دارای سه قسمت است: راه گزین ها، شاه سیم ها، و حلقه های محلی.

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

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

 

کدهای تصحیح خطا

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

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

 

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

برای درک چگونگی اداره کردن خطا، باید ماهیت خطا مشخص شود. معمولا هر قاب از m بیت داده و r بیت اضافی یا کنترلی تشکیل شده است. اگر طول قاب (n = m  + r)n باشد، واحد nبیتی حاوی بیت های داده و کنترلی، غالبا بعنوان کدواژه شناخته می شود. برای تعیین بیت های متفاوت دو کدواژه، کافی است XOR را بر روی دو کدواژه اجرا کرد و تعداد 1 های نتیجه را شمارش نمود.

تعداد موقعیت هایی از بیت ها که در دو کدواژه با هم متفاوت اند، فاصله همینگ نامیده می شود. اهمیت این فاصله این است که اگر فاصله همینگ دو کد واژه d باشد، d خطای تک بیتی لازم است تا یکی به دیگری تبدیل شود.

در اغلب کاربردهای انتقال داده ها تمام 2^m پیام ممکن دادهها، معتبر است، اما به خاطر روش محاسبه بیت های کنترلی، تمام 2ⁿ کد واژه ممکن مورد استفاده قرار نمی گیرد. با در نظر گرفتن الگوریتم محاسبه بیت های کنترلی، می توان فهرست کاملی از کدواژه های معتبر را ایجاد کرد و از بین آنها دو کدواژه را پیدا کرد که فاصله همینگ آنها کمینه باشد. این فاصله، فاصله همینگ کد کامل خواهد بود.

 

خواص تشخیص خطا و تصحیح خطای کد، بستگی به فاصله همینگ آن دارد. برای یافتن d خطا، به کدی با فاصله d + 1 نیاز است، زیرا با چنین کدی، راهی وجود ندارد که d خطای تک بیتی بتواند یک کدواژه معتبر را به کد واژه معتبر دیگر تغییر دهد. وقتی گیرنده کدواژه نامعتبری را ببیند، می تواند بگوید که خطایی رخ داده است.

بطور مشابه برای تصحیح d خطا به کدی با فاصله  2d + 1 نیاز است زیرا در آن صورت است که کد واژه های معتبر آنقدر از هم جدایند که حتی با d تغییر، کد واژه اولیه هنوز از هر کد دیگر نزدیک تر است بنابراین می توان آن را بطور انحصاری تعیین کرد.

 

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

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

وقتی قاب به گیرنده می رسد، در هر بار یک ستون از ماتریس بازسازی می شود . اگر خطای انفجاری به طول k اتفاق بیفتد حداکثر 1 بیت در هر یک از k کد واژه، از آن تاثیر می پذیرد ولی کد همینگ را میتوان بصورت یک خطا به ازای هر کدواژه تصحیح کرد. بنابراین یک بلوک را می توان بازیابی کرد.

 

کدهای تشخیص خطا

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

برای تشخیص بلوکی با خطای 1 بیتی، یک بیت توازن در هر بلوک کافی است. برای هر 1000 بلوک باید یک بلوک اضافی (بیت های 1001) منتقل شود. سربار کلی مربوط به تشخیص خطا + روش انتقال مجدد، برابر با 2001 بیت در هر مگابیت از داده هاست، در حالی که برای کد همینگ برابر با 10000 بیت است.

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

در این روش خطای انفجاری به طول n قابل تشخیص است، زیرا در هر ستون فقط 1 بیت تغییر خواهد کرد. اگر اولین بیت معکوس شده باشد، آخرین بیت معکوس شده باشد و تمام بیت های دیگر صحیح باشند خطاهای انفجاری به طول n +1 بدون انکه تشخیص داده شود عبور خواهد کرد. اگر بلوک توسط خطای انفجاری طولانی یا چند خطای پیوسته کوتاه تر آسیب ببیند احتمال آنکه هر یک از n ستون دارای توازن صحیحی باشد تصادفا 0.5 است، لذا احتمال پذیرش بلوک بد، 2^-n است.