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

    Parity فرد بهتر است یا زوج؟ 
اینكه كدام یك از دو حالت Parity موثرتر هستند كاملا بستگی به شرایط دارد. یكی از خطاهای رایج به نام Burst Error یا All-Bits Error وجود دارد . در این نوع خطا همه بیت ها یا 1 می شوند و یا 0 می شوند . در صورتی كه از Parity زوج استفاده شود آنگاه خطای همه 0 (All-0'S) قابل تشخیص نیست. ولی با انتخاب Parity فرد این خطا تشخیص داده می شود . پس اگر احتمال خطای همه 0 بیشتر است بهتر است كه از Parity فرد استفاده شود. اگر احتمال خطای همه 1 بیشتر است، آنگاه دو حالت وجود دارد اگر تعداد كل بیت ها ( همراه با Parity ، N+1) زوج باشد باید از Parity فرد و اگر تعداد كل بیت ها فرد باشد از Parity زوج استفاده كرد .

می توانیم بجای آنكه به كل بیت ها یك Parity اختصاص دهیم به هر گروه از آنها، مثلا هر یک بایت، یك Parity اختصاص دهیم. در این حالت بدیهی است كه میزان Overhead از 1/N به M/N افزایش خواهد یافت. (M تعداد گروه یا بایت ها است) در این حالت حد اكثر M خطا قابل تشخیص است، البته به شرطی كه خطا ها در بایت های مختلف باشند. اگر هر دو نوع خطای همه 0 و همه 1 ممكن است اتفاق بیفتد می توانید از پریتى Parity برای یك بایت و از Parity فرد برای بایت بعدی استفاده كنید. 

2-1-2 کد همینگ
در اصل کد همینگ یک نوع کدگذاری از خانواده ی کدگذاری پریتی است . در روش همینگ از سه بیت توازن برای آشکارسازی و اصلاح خطا استفاده میشود. همانطور که در شکل مشخص است چهار بیت d1 الی d4 به عنوان داده ورودی در نظر گرفته میشوند. سپس با ترتیب نشان داده شده بیتهای توازن p1 تا p3 از XOR کردن بیت ها محاسبه می شوند و در نهایت داده هفت بیتی بدست آمده ارسال می گردد.



                                                              
                                           نحوه محاسبه بیتهای توازن در کد همینگ


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

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

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

برای آنكه بدانیم به چند بیت برای Parity نیاز داریم ، باید طبق رابطه زیر عمل كنیم : اگر تعداد بیت های داده برابر D باشد و تعداد بیت های Parity برابر R باشد. در آن صورت جمعا" D+R بیت داریم كه هر كدام از آنها می تواند دچار خطا شود یعنی با فرض اینكه خطا های ما تك بیتی هستند، D+R حالت مختلف خطا داریم. علاوه بر حالت های خطا یك حالت درست هم داریم كه در آن هیچ بیتی دچار اشكال نشده است. پس جمعا D+R+1 حالت ممكن وجود دارد كه باید توسط Parity نمایش داده شود.
پس با توجه به اینكه R بیت Parity وجود دارد می توانیم 2R حالت مختلف داشته باشیم كه شامل حالت های خطا و درست می شود. پس اگر داشته باشیم :

                                                                        2R >= R+D+1       

آنگاه می توانیم مطمئن باشیم كه تعداد بیت های Parity كافى است.


2-1-3 جمع کنترلی ( Checksum )
این روش در اصل برای سیستمهای انتقال اطلاعات استفاده می شود. ایده اصلی آن این است كه بایت های یك بلوك از داده ها با یك دیگر جمع شوند و حاصل جمع نیز ارسال شود. گیرنده نیز داده ها را جمع می كند و اگر با حاصل جمع دریافتی یكی نباشد، می فهمد كه خطا روى داده است. گونه های مختلفی برای Checkcum وجود دارد كه در اینجا آنها را بررسی می كنیم: (فرض كنیم كه هر كلمه از داده ها داراى طول D باشد).
2-1-3-1 Single-Percision (تک دقتی):
در این روش جمع به پیمانه (Modulo) 2D انجام می شود. یعنی حاصل جمع به 2D تقسیم می شود و باقیمانده آن فقط در نظر گرفته می شود. یا به عبارتی تنها D رقم سمت راست حاصل جمع در نظر گرفته می شود.

2-1-3-2 Double-Percision (دقت مضاعف):
كاملا شبیه Single است ولی بجای 2D از 22D استفاده می شود كه در نتیجه این روش خطاهای بیشتری را می تواند كشف كند.


2-1-3-3 Residue Checksum (باقیمانده):
 در این روش بیت هاى اضافی بعد از D اُمین بیت كه در روش Single دور ریخته می شد، مجددا با خود داده اصلی جمع می شود كه در نتیجه قابلیت اطمینان سیستم بالاتر می رود. زیرا وجود خطا در آن بیت هاى اضافی نیز تاثیر گذار هستند. 

2-1-3-4 Honeywell Checksum :
در این روش هر دو كلمه را به هم می چسبانند و سپس كل این مجموعه های دوتایی را با هم جمع میكنند و نتیجه را به پیمانه 22D در نظر می گیرند. حسن این روش این است كه اگر یك خطا همواره روی یكی از بیت هاى هر كلمه (مثلا بیت سوم) اتفاق بیفتد، در گونه های قبلى ممكن بود تشخیص داده نشود، ولی در این روش جلوى این نوع خطا ها نیز گرفته می شود. 

    نکته : روشهای Checksum فقط می توانند وجود خطا را تشخیص دهند ولی نمی توانند آن را تصحیح كنند. به همین خاطر اگر خطایی روى دهد، كل بلوك باید مجددا ارسال شود. 



2-1-4 کد برگر (Berger Code )
کد بِرگر یك روش جداپذیر (Separable) است. این روش به این شكل عمل می كند كه ابتدا تعداد یك های درون داده را می شمارد، سپس از عدد به دست آمده مكمل می گیرد و سپس این عدد به دست آمده را در كنار عدد اصلی قرار میدهد. 
برای مثال فرض كنید عدد 11101 را داریم. درون این عدد چهار 1 وجود دارد كه فرم باینرى آن 100 می شود و مكمل آن 011 است. حالا اگر این عدد را در كنار عدد اصلی قرار دهیم، داریم 11101011 . این روش می تواند هر نوع خطای Unidirectional را تشخیص دهد، چه خطا از 0 به 1 باشد یا برعكس آن. اما اگر هم زمان بعضی 0 ها به 1 تبدیل شوند، و همان تعداد 1 نیز به 0 تبدیل شوند، نمی تواند خطا را تشخیص دهد. 




2-1-5 کد افزونگی چرخشی CRC
یک کد افزونگی چرخشی (به انگلیسی: Cyclic redundancy code) (سی‌آرسی) تابع درهم‌سازی غیرایمنی است که جهت تشخیص تغییرات تصادفی رو داده‌های خام طراحی شده‌است. این تابع عموما در شبکه‌های مخابراتی دیجیتال و وسایل ذخیره‌سازی داده‌ها از جمله دیسک سخت مورد استفاده قرار می‌گیرد. یک دستگاه دارای قابلیت سی‌آرسی، یک توالی کوتاه و با طول ثابت را، به نام کد سی‌آرسی (یا فقط سی‌آرسی)، برای هر بلاک از داده‌ها محاسبه نموده و آن را همراه با داده‌ها ذخیره یا ارسال می‌کند. زمانی که یک بلاک دریافت یا خوانده می‌شود دستگاه محاسبه را تکرار می‌کند؛ در صورت مغایرت با کد محاسبه شده قبلی مشخص می‌شود که این بلاک دارای خطای داده است و در این حالت دستگاه ممکن است عملی را جهت اصلاح خطا از جمله خواندن یا درخواست ارسال مجدد بلاک انجام دهد. اصطلاح سی‌آرسی می‌تواند به کد اعتبارسنج یا تابع تولید کد اطلاق شود. سی‌آرسی‌ها به جهت پیاده‌سازی ساده در سخت‌افزار دودویی، سادگی تحلیل ریاضی آن‌ها و عملکرد خوب در تشخیص خطاهای معمول حاصل از اختلال در کانال‌های انتقال دارای محبوبیت زیادی هستند. سی‌آرسی توسط W. Wesley Peterson اختراع و در مقاله ۱۹۶۱ وی منتشر شد . سی‌آرسی 32 بیتی پیشنهادی موسسه مهندسین الکتریک و الکترونیک (IEEE)، که در اترنت و سایر جاها استفاده شده‌است، در کنفرانس مخابراتی سال 1975 ظاهر شد.
سی‌آرسی یک کد تشخیص خطا است. محاسبه آن شبیه عمل تقسیم اعشاری است که خارج قسمت حذف می‌شود و باقیمانده به عنوان نتیجه در نظر گرفته می‌شود، با این تفاوت مهم که محاسبات آن محاسبات بدون رقم نقلی از یک میدان محدود است. اعلام یک سی‌آرسی خاص با مشخص کردن مقسم و سایر مشخصات آن انجام می‌شود.
اگرچه سی‌آرسی‌ها می‌توانند با استفاده از هر میدان محدودی ساخته شوند، همه سی‌آرسی‌های پرکاربرد از میدان محدود GF(2) بهره می‌برند. این میدانی از دو عنصر، عموما به نام ۰ و ۱، است که به راحتی با معماری کامپیوتر سازگار است. یک دلیل مهم برای محبوبیت سی‌آرسی‌ها برای تشخیص تغییرات تصادفی داده‌ها اطمینان از کیفیت آن‌ها است. نوعا"، یک سی‌آرسی nبیتی، که برای یک بلاک داده با طول دلخواه محاسبه شده‌است، هر حوزه خطای با طول کمتر از n بیت (به عبارت دیگر، هر تغییری که محدوده آن بیش از n بیت مجاور از داده‌ها نباشد) و 1-2^(-n) تعداد از سایر حوزه‌های با طول بیش از n بیت را تشخیص می‌دهد. خطاها در هیچ‌یک از کانال‌های انتقال و رسانه‌های ذخیره‌سازی مغناطیسی دارای توزیع تصادفی نیستند و در نتیجه فایده خواص سی‌آرسی‌ها را نسبت به سایر روش‌های تشخیص خطا از جمله کدهای چندگانه زوجیت بیشتر می‌کنند. ساده‌ترین سامانه تشخیص خطا، بیت زوجیت، در واقع یک سی‌آرسی عادی است که از مقسم دوبیتی ۱۱ استفاده می‌کند.


2-1-5-1 سی‌آرسی‌ها و تمامیت داده‌ها
سی‌آرسی‌ها، به خودی خود، راهکار مناسبی برای حفاظت در مقابل تغییرات عمدی روی داده نیستند (مثلا در برنامه‌های اعتبارسنجی)، چون مبانی ساده ریاضیات آن‌ها باعث می‌شود که بتوان هر تغییر دلخواه را روی داده‌ها طوری اعمال کرد که سی‌آرسی داده‌ها تغییر نکند. اغلب این فرض غلط وجود دارد که وقتی پیامی به همراه سی‌آرسی آن از یک کانال آزاد دریافت می‌شود و سی‌آرسی دریافتی با سی‌آرسی محاسبه شده مطابقت می‌کند پس پیام ممکن نیست در حین دریافت تغییر کرده باشد. این درست نیست چون هر دوی آن‌ها می‌توانند تغییر کرده باشند، به طوری که سی‌آرسی جدید با پیام جدید مطابقت کند. بنابراین سی‌آرسی‌ها می‌توانند جهت بررسی درستی داده‌ها استفاده شوند ولی نه برای اطمینان از تمامیت آن. ایجاد پیام‌های دیگری که همان سی‌آرسی را ایجاد کنند کار ساده‌ای است، خصوصا پیام‌هایی که بسیار شبیه پیام اصلی هستند. طبق طراحی پیامی که بسیار شبیه پیام اصلی است (و تفاوت آن تنها در یک الگوی تداخل تصادفی است) سی‌آرسی کاملا متفاوتی خواهد داشت و بنابراین تشخیص داده خواهد شد. در مقابل، یک راه موثر برای محافظت پیام‌ها در برابر تغییرات عمدی استفاده از کدهای اعتبار سنجی پیام همچون HMAC است.

2-1-5-2 محاسبه سی‌آرسی

ادامه در مقاله بعدی