کشف و تصحیح خطا مقاله شماره 2

دو روش مشهور که برای کشف خطا وجود دارد:

 PCC  Parity Check Code  و CRC  Cyclic Redundancy Check  است. روش سوم که مجموعه مقابله‌ای یا Checksum نام دارد، مکانیزمی است که در اینترنت جهانی کاربرد دارد و توسط چندین پروتکل مورد استفاده قرار می‌ گیرید که در اینجا به شرح آن می پردازیم.

این مکانیز نیز مانند دو روش PCC و CRC بر اساس مفهوم افزونگی طراحی شده اند. این روش را با حل یک مثال ساده، به آسانی درک خواهید کرد.

مثال: مجموعه مقابله‌ای 8 بیتی را برای بلوک 16 بیتی 1010100100111001  محاسبه کنید و نشان دهید خطایی وجود ندارد.

قدم اول : کد 16 بیتی را به دو کد 8 بیتی تقسیم میکنیم.

قدم دوم : اعداد را در دسته های 8 بیتی جمع می کنیم.

10101001 + 00111001 = 11100010

قدم سوم : از عدد بدست آمده مکمل 1 میگیریم.

00011101

نتیجه بدست آمده را به انتهای کد اضافه می کنیم.

101010010011100100011101

برای نشان دادن عدم وجود خطا، کافیست گیرنده 24 بیت بدست آمده را به سه قسمت 8 تایی تقسیم کنیم و اعداد را با هم جمع کنیم و از آن مکمل 1 بگیریم. اگر نتیجه نهایی برابر با 0 شود، می توان نتیجه گرفت که خطایی رخ نداده است.

10101001 + 00111001 + 00011101 = 11111111

مکمل 1 = 00000000

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

معنای عدم کشف خطاهای پدید آمده است.
======

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

1-1 مفاهیم کدینگ (Coding Concepts) 
برای آنكه بتوانیم یك كلمه (Word) از داده ها را بگونه ای کد گذاری كنیم كه قابلیت تشخیص و تصحیح خطا را داشته باشد، باید تعداد بیت هاى آن را افزایش دهیم. اگر طول یك Data Word به اندازه D بیت باشد، پس از کد گذاری یك كلمه کد شده (Codeword) به اندازه C بیت خواهد بود. بگونه ای كه C>D می‌باشد. پس حالا ما بجای 2D حالت ممكن، 2C حالت ممكن داریم. ولی تمام این حالت ها درست نیستند، و این همان چیزی است كه باعث می شود سیستم بتواند وجود خطا را تشخیص دهد. یعنی اگر یك عدد در یكی از این حالات غیرمجاز باشد، سیستم می فهمد كه خطایی روى داده است. در بعضی از روش ها، سیستم در یك سری از حالات می تواند خطای بوجود آمده را نیز اصلاح كند. روش ارائه شده باید این قابلیت را داشته باشد كه از بین C بیت موجود D بیت اصلی را خارج كند. به این عمل اصطلاحا Decoding می گویند. یكی از مشكلات استفاده از کدینگ این است كه سیستم مجبور است تا یك مدت زمانى را صرف عملیات Encoding و Decoding كند كه باعث ایجاد سربار (Overhead) در سیستم می شود. 

1-2 کد همینگ
در دهه ۱۹۵۰ میلادی ریچارد همینگ که در آزمایشگاههای شرکت بل کار می کرد به معرفی دسته ای از کد های اصلاح کننده خطا پرداخت که بنام خود او کدهای همینگ خوانده می شوند. شاید ساده ترین روش برای آشکار کردن خطای یک بیت در یک بایت، استفاده از بیت توازن است. 

1-3 فاصله همینگ (Hamming Distance) 
فاصله همینگ بین دو Codeword برابر است با تعداد بیت هایی كه آنها با هم متفاوتند. یعنی نشان میدهد كه اگر در اثر خطا یك کد بخواهد به یك کد دیگر تبدیل شود، چند بیت از آن باید تغییر كند تا این تبدیل انجام شود بدون آنکه سیستم آن را خطا به حساب آورد .
در تئوری اطلاعات فاصله همینگ بین دو رشته برابر طول تعداد مکانهایی است که سمبولهای متناظر متفاوت هستند. به معنای دیگر، کمترین تعداد جایگزینی هایی است که یک رشته به یک رشته دیگر تغییرپیدا کند، یا تعداد خطاهایی که یک رشته به رشته دیگر تبدیل گردد.  
چند مثال برای فاصله همینگ بین چند رشته:
«toned»و«roses» فاصله همینگ سه هست.
۱۰۱۱۱۰۱ و ۱۰۰۱۰۰۱ فاصله همینگ دو هست.
۲۱۷۳۸۹۶ و ۲۲۳۳۷۹۶ فاصله همینگ سه هست.
کدهای 101 و 011 در 2 بیت با یك دیگر متفاوت هستند. در نتیجه فاصله همینگ بین آنها برابر 2 است. اما کدهای 101 و 100 فقط در یك بیت با هم تفاوت دارند. در نتیجه اگر یك خطا در بیت كم ارزش آنها روى دهد، یكی از آنها را به دیگری تبدیل می كند و سیستم متوجه وجود خطا نخواهد شد. فاصله همینگ به اندازه 2 تضمین می كند كه اگر یك خطای تك بیتی اتفاق بیفتد سیستم حتما متوجه بروز خطا خواهد شد. 
در شکل روبه رو مکعب باینری را میبیند که در هر گوشه آن یک عدد باینری قرار دارد . در این مکعب هر ضلع یک فاصله همینگ به حساب می آید . برای مثال فاصله بین دو عدد 001 تا 010 دو ضلع است به عبارتی فاصله همینگ آن 2 است .    

 

                                                       



1-4 فاصله کد (Code Distance) 
فاصله کد برابر است با كمترین فاصله همینگ كه بین هر دو کد موجود در یك مجموعه کد وجود دارد. یعنی اگر مثلا در یك روش کدینگ فاصله کد برابر 2 باشد به این معنی است كه هیچ كدام از کدها با کدهای دیگر فاصله همینگ كمتر از 2 ندارند. برای مثال مجموعه کدهای {001، 010، 100، 111} همگی باهم فاصله 2 دارند. در نتیجه این کد می تواند هر خطای تك بیتی را تشخیص دهد. 
به عنوان مثالی دیگر کدهای {000، 111} داراى فاصله 3 هستند پس می توانند هر خطای تك بیتی یا دو بیتی را تشخیص دهند. اما اگر فرض شود احتمال خطای دو بیتی كم است، این کد را می توان به عنوان روشى كه می تواند خطاهای تك بیتی را اصلاح (Correct) كند، نیز استفاده شود. 

1-5 محدودیت تشخیص و تصحیح (Detection and Correction) 
به عنوان یك تعریف ریاضی می توان گفت : برای آنكه بتوانیم تا حداكثر t بیت خطا را تشخیص دهیم، نیاز به حداقل فاصله کد به اندازه t+1 داریم. ولی برای آنكه بتوانیم تا حداكثر t بیت خطا را تصحیح كنیم، نیاز به حداقل فاصله کد 2t+1 داریم. 

1-6 کدینگ و افزونگی (Coding and Redundancy)
فرض كنید كه یك مجموعه کد شامل دو حالت به صورت {000، 111} باشد كه برای نشان دادن تنها یك بیت به كار می رود. در واقع عدد 0 به شكل 000 کد شده است و عدد 1 به شكل 111. این سیستم کد دهی معادل سیستم های TMR می باشد. در واقع کدینگ همیشه همراه با افزونگی (Redundancy) می‌باشد كه در نتیجه می توان از تكنیكهاى بكار رفته شده برای افزونگی در کدینگ نیز استفاده كرد. مثلا Duplex یكی از راه هاى افزونگی است كه در این روش Codeword دو بار عینا تكرار می شود. برای مثال برای یك تك بیت دو حالت وجود دارد كه 00 و 11 است كه از دو بار تكرار 0 و 1 به دست آمده اند. 

1-7 جداپذیری کد (Code Separability) 
داده های کد شده می توانند دو حالت داشته باشند :
    جدا پذیر (Separable)

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

    جدا ناپذیر (Non-Separable) 
در کدهای جداناپذیر داده های اصلی با کدهای اضافی با هم تركیب شده اند و جدا سازی آنها از یك دیگر نیاز به انجام پردازش های اضافی دارد. 

2-1 روشهای کدینگ (Coding methods) 

2-1-1 کد Parity (Parity Coding) 
پریتی (Parity) ساده ترین روش كد گذاری جدا پذیر است. در این روش اطلاعات کد شده شامل N بیت داده اصلی به همراه یك بیت اضافه كه Parity را نگه می دارد، می‌باشد. دو نوع Parity وجود دارد:
     Even (زوج)
در روش زوج بیت Parity به گونه ای تنظیم می شود كه تعداد یك ها در كل بیت ها (داده اصلی و Parity) زوج باشد. 

     Odd (فرد)
روش فرد بر عكس عمل می كند. یعنی در روش فرد بیت Parity به گونه ای تنظیم می شود كه تعداد یك ها در كل بیت ها (داده اصلی و Parity) فرد باشد. 
تعداد كل بیت ها در نهایت برابر (N+1) است. در این حالت عملا به میزان 1/N بیت جدید به داده اضافه شده است. کد Parity داراى فاصله همینگ 2 می‌باشد كه در نتیجه می تواند هر خطای تك بیتی را تشخیص دهد ولی نمی تواند هیچ نوع تصحیحی انجام دهد. کد Parity نمی تواند یك خطای دو بیتی را تشخیص دهد، ولی خطاهای سه بیتی را می تواند تشخیص دهد. در کل کد پریتی قابلیت تشخیص خطا در تعداد فرد را دارد .

    Parity فرد بهتر است یا زوج؟ ادامه در مقاله بعدی