کشف و تصحیح خطا
زمانی که فرستنده اقدام به ارسال پیام به گیرنده می کند، پیام باید بدون خطا به گیرنده برسد. سوالی که مطرح می شود این است که اولا گیرنده چطور می تواند متوجه خطا شود و بفهمد که پیام دارای اشکال است؟ دوما گیرنده چطور باید پیام دریافتی را تصحیح کند؟ برای پاسخ دادن به این پرسش ها ابتدا لازم است با انواع خطا آشنا شویم.
در قسمت اول مطلب کشف و تصحیح خطا گفتیم که برای رسیدن به پاسخ دو پرسش فوق، به ابتدای کدهای ارسالی، بیت هایی را تحت عنوان افزونگی ارسال میکنیم. همچنین مفهوم فاصله همینگ را شرح داده و روش محاسبه آن را توضیح دادیم. اینک به بیان چند مفهوم دیگر و ارتباط آنها با کشف و تصحیح خطا می پردازیم.
مینیمم فاصله همینگ
با وجودی که بحث فاصله همینگ، مفهومی کلیدی برای سر و کار داشتن با کدهای کشف و تصحیح خطا است، ارزیابی اصلی که برای طراحی هر کد صورت می پذیرد، مینیمم فاصله همینگ است. وقتی مجموعه ای از کدها راد اشته باشیم، مینیمم فاصله همینگ عبارت است از کوچکترین عدد همینگ میان همه زوج‌های موجود در مجموعه. این مفهوم با نماد dmin شناخته می شود. مینیمم فاصله همینگ تنها زمانی با فاصله همینگ برابر است که مجموعه کدها تنها دارای دو عضو باشد. به مثال زیر توجه کنید.
مثال: فاصله همینگ و مینیمم فاصله همینگ میان چهار کد 00000، 01011، 10101، 11110 را حساب کنید.
ابتدا فاصله همینگ میان تک تک زوج ها را محسابه میکنیم.
d (00000 , 01011) = 3
d (00000 , 10101) = 3
d (00000 , 11110) = 4
d (01011 , 10101) = 4
d (01011 , 11110) = 3
d (10101 , 11110) = 3
به این ترتیب، مینیمم فاصله همینگ برابر است با 3.
وقتی مجموعه ای از کدها راد اشته باشیم، مینیمم فاصله همینگ عبارت است از کوچکترین عدد همینگ میان همه زوج‌های موجود در مجموعه،
این مفهوم با نماد dmin شناخته می شود
ارتباط میان فاصله همینگ و خطا
این کمیت به ما تعداد بیت های معیوب در حین ارسال را نشان می دهد. به تعداد عدد همینگ، میان کد ارسالی و کد دریافتی بیت معیوب یافت می شود.ارتباط میان مینیمم فاصله همینگ و کشف خطا
برای کشف n خطا در هنگام ارسال، باید مینیمم فاصله همینگ میان دو کد ارسالی برابر با عدد n+1 باشد تا کد دریافتی با کد ارسالی منطبق نگردد.ارتباط میان مینیمم فاصله و تصحیح خطا
اگر بخواهیم n خطا را نه تنها کشف بلکه اصلاح هم کنیم، مینیمم فاصله همینگ میان دو کلمه کد باید برابر با 2n+1 باشد. به عنوان مثال، در مثال حل شده ی بالا، مینیمم فاصله همینگ 3 است پس تنها می توانیم خطاهای تک بیتی را تصحیح کنیم.
دو روش مشهور که برای کشف خطا وجود دارد:
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 فرد بهتر است یا زوج؟
اینكه كدام یك از دو حالت 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 محاسبه سی‌آرسی
برای محاسبه یک سی‌آرسی دودویی nبیتی، بیتهای ورودی را در یک سطر بنویسید، و الگوی (n+1)بیتی را که نشان‌دهنده مقسم سی‌آرسی است (و چندجمله‌ای نامیده میشود) زیر سمت چپ‌ترین بیت قرار دهید. در زیر، اولین محاسبه برای ایجاد یک سی‌آرسی ۳بیتی نشان داده شده‌است:
===
با اضافه کردن یک بیت توازن به کد همینگ می توان بروز دو خطا را تشخیص داد.
======
هرگاه یک کانال ارتباطی برای انتقال اطلاعات داشته
باشیم در حین انتقال به دلیل وجود نویز اطلاعات دچار تغییر می شوند. باید
روشی برای مشخص کردن این تغییرات داشته باشیم و بهتر است به روشی دست یابیم
که میتواند این تغییرات ناخواسته یا خطا ها را اصلاح نماید.
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 فرد بهتر است یا زوج؟
اینكه كدام یك از دو حالت 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 محاسبه سی‌آرسی
برای محاسبه یک سی‌آرسی دودویی nبیتی، بیتهای ورودی را در یک سطر بنویسید، و الگوی (n+1)بیتی را که نشان‌دهنده مقسم سی‌آرسی است (و چندجمله‌ای نامیده میشود) زیر سمت چپ‌ترین بیت قرار دهید. در زیر، اولین محاسبه برای ایجاد یک سی‌آرسی ۳بیتی نشان داده شده‌است:
11010011101100 <--- ورودی
1011 <--- مقسم (4 بیت)
----------------------
01100011101100 <--- نتیجه
اگر بیت ورودی بالای سمت چپ‌ترین بیت مقسم صفر باشد، محاسبه‌ای انجام نمی‌شود و مقسم را یک بیت به راست حرکت می‌دهیم. اگر بیت ورودی بالای سمت چپ‌ترین بیت مقسم یک باشد، مقسم و ورودی XOR میشوند (به بیان دیگر بیت ورودی بالای هر بیت یک مقسم عکس میشود). سپس مقسم را یک بیت به راست حرکت می‌دهیم و این روند تا زمانی تکرار میشود که انتهای مقسم به انتهای سطر ورودی نرسیده‌است. در زیر، آخرین محاسبه نشان داده شده‌است:
00000000001110 <--- نتیجه محاسبه قبلی
1011 <--- مقسم
-----------------------
00000000000101 <--- باقیمانده (3 بیت)
از آنجایی که چپ‌ترین بیت مقسم در مواجه با هر بیت یک ورودی آن را صفر می‌کند، وقتی این روند پایان می‌یابد تنها بیتهای ورودی که می‌توانند غیر صفر باشند آخرین n بیت سمت راست است. این n بیت، باقیمانده مرحله تقسیم است و البته همان مقدار تابع سی‌آرسی است (مگر آنکه تابع سی‌آرسی انتخابی شامل تعدادی پس‌پردازش باشند).
2-1-5-3 مشخصات سی‌آرسی
مفهوم سی‌آرسی به عنوان یک کد تشخیص خطا هنگام پیاده‌سازی آن در یک سامانه واقعی میتواند شامل برخی پیچیدگی‌های دیگر نیز باشد. در زیر، تعدادی از آنها آمده‌است:
یک پیاده‌سازی خاص ممکن است یک الگوی بیتی ثابت را پیشوند قرار دهد. این زمانی مفید است که خطاهای ساعتی ممکن است است بیتهای صفر را در ابتدای پیام قرار دهد و در این صورت با این الگو قابل تشخیص است.
یک پیاده‌سازی خاص ممکن است به پیام n بیت صفر الحاق کند. این میتواند بررسی صحت پیامی را که سی‌آرسی به آن الحاق شده‌است ساده‌تر کند. در این روش پس از الحاق n بیت صفر و محاسبه مجدد سی‌آرسی، نتیجه دقیقا صفر میشود و باقیمانده کافیست با صفر مقایسه شود.
یک پیاده‌سازی خاص ممکن است نتیجه را با یک الگوی ثابت XOR کند.
ترتیب بیت‌ها: برخی روش‌ها کم‌ارزش‌ترین بیت را نخست قرار می‌دهند و برخی بالعکس. ترتیب بیت‌ها در سخت‌افزارهای انتقال سریالی داده بسیار اهمیت دارد زیرا اکثر روشهای انتقال که به صورت وسیع استفاده میشوند از الگوی ابتدا-کم‌ارزش‌ترین-بیت استفاده می‌کنند.
ترتیب بایت‌ها: در سی‌آرسی‌های چند بایتی، ممکن است این تردید پیش آید که آیا بایت منتقل شده اول، کم‌ارزش‌ترین بایت است یا باارزش‌ترین. به عنوان مثال در برخی روش‌ها بایت‌های سی‌آرسی ۱۶بیتی را جابجا می‌کنند.
حذف باارزش‌ترین بیت چندجمله‌ای مقسم: از آنجایی که باارزش‌ترین بیت همیشه یک است، و از آنجایی که یک سی‌آرسی nبیتی باید به صورت یک مقسم (n+1) بیتی تعریف شود و در این صورت میتواند از یک ثبات nبیتی سرریز میشود، برخی نویسندگان بیان بیت بالای مقسم را غیرضروری می‌دانند.
2-1-5-4 سی‌آرسی‌های پرکاربرد و استاندارد
اگرچه سی‌آرسی‌ها از اجزای معیارها متعددی هستند اما خودشان، از منظر وجود الگوریتمی جهانی، مورد قبول نیستند. به عنوان مثال دو چندجمله‌ای سی‌آرسی-۱۲، ده نوع مستند سی‌آرسی-۱۶ و چهار سی‌آرسی-۳۲ وجود دارد. این چندجمله‌ای‌ها عموما بهترین چندجمله‌ای‌های ممکن نیستند. بین ۱۹۹۳ و ۲۰۰۴، کوپمن، کستاگنولی و سایرین فضای چندجمله‌ای‌ها تا ۱۶ بیت، 24 و ۳۲ بیتی را جهت یافتن مثال‌هایی با کارایی بهتر (از نظر فاصله هامنی برای یک طول پیام خاص) از چندجمله‌ای‌های پروتکل‌های پیشین بررسی کردند و بهترین آنها را در جهت بهبود ظرفیت تشخیص خطای استانده‌های آتی منتشر کردند. به طور خاص، iSCSI یکی از یافته‌های این پژوهش را مورد استفاده قرار داده‌است.
2-1-6 کد گری
نمایش کدهای دودویی که بعد از فرانک گری (Frank Gray) به نام کد گری شناخته شد که یک سیستم از اعداد دودویی است که هر دو عدد متوالی فقط در یک بیت با هم اختلاف داشته باشند. امروزه کد‌گری به طور گسترده برای تصحیح اشکالات در سیستم ارتباط دیجیتالی مثل کابل‌های تلویزیونی و تلویزیون‌های دیجیتالی جهانی استفاده میشود.
یکی از محققان آزمایشگاه بل (Bell) به نام فرانک گری اولین بار به طور رسمی کد گری را مورد استفاده قرار داد و این کد بعد از گری توسط افرادی که از آن استفاده می‌کردند کد گری نامگذاری شد.
2-1-6-1 تاریخچه و کاربردهای علمی
کد گری قبل از آن که در مهندسی به کار رود در جدول‌ها پازل‌های ریاضی به کار برده می‌شد، ریاضیدان فرانسویEmile Boudat از کد گری در سال۱۸۷۸در تلگراف استفاده کرد و برای این کارش مدال دریافت کرد و اما کاربردهای آن، از کد گری به عنوان یک رمزگذار استفاده میشود که نسبت به رمزگذار عادی برتری دارد. در نمایش کد گری خاصیت دایره‌ای بودن آن باعث میشود که دو عدد دو سر نیز فقط در یک بیت متفاوت باشند. کد گری یک دور همیلتونی در یک مکعب n بعدی Qn تولید می‌کند که هر کدام از اعداد آن یک راس را نشان میدهد و نیز در الگوریتم‌های ژنتیکی از آن استفاده میشود و نیز البته برچسب گذاری جدول کارنو از موارد دیگر استفاده آن است. زمانی کد گری برای آدرس دهی حافظه در کامپیوتر استفاده میشود کامپیوتر نیروی کمتری صرف یافتن آدرس‌ها می‌کند چون هر آدرس با قبلی فقط در یک بیت متفاوت است. طراحان مدارهای منطقی از کد گری به طور گسترده برای عبور چند بیت اطلاعات بین سیستمهای همزمان استفاده می‌کنند.
1011 <--- مقسم (4 بیت)
----------------------
01100011101100 <--- نتیجه
اگر بیت ورودی بالای سمت چپ‌ترین بیت مقسم صفر باشد، محاسبه‌ای انجام نمی‌شود و مقسم را یک بیت به راست حرکت می‌دهیم. اگر بیت ورودی بالای سمت چپ‌ترین بیت مقسم یک باشد، مقسم و ورودی XOR میشوند (به بیان دیگر بیت ورودی بالای هر بیت یک مقسم عکس میشود). سپس مقسم را یک بیت به راست حرکت می‌دهیم و این روند تا زمانی تکرار میشود که انتهای مقسم به انتهای سطر ورودی نرسیده‌است. در زیر، آخرین محاسبه نشان داده شده‌است:
00000000001110 <--- نتیجه محاسبه قبلی
1011 <--- مقسم
-----------------------
00000000000101 <--- باقیمانده (3 بیت)
از آنجایی که چپ‌ترین بیت مقسم در مواجه با هر بیت یک ورودی آن را صفر می‌کند، وقتی این روند پایان می‌یابد تنها بیتهای ورودی که می‌توانند غیر صفر باشند آخرین n بیت سمت راست است. این n بیت، باقیمانده مرحله تقسیم است و البته همان مقدار تابع سی‌آرسی است (مگر آنکه تابع سی‌آرسی انتخابی شامل تعدادی پس‌پردازش باشند).
2-1-5-3 مشخصات سی‌آرسی
مفهوم سی‌آرسی به عنوان یک کد تشخیص خطا هنگام پیاده‌سازی آن در یک سامانه واقعی میتواند شامل برخی پیچیدگی‌های دیگر نیز باشد. در زیر، تعدادی از آنها آمده‌است:
یک پیاده‌سازی خاص ممکن است یک الگوی بیتی ثابت را پیشوند قرار دهد. این زمانی مفید است که خطاهای ساعتی ممکن است است بیتهای صفر را در ابتدای پیام قرار دهد و در این صورت با این الگو قابل تشخیص است.
یک پیاده‌سازی خاص ممکن است به پیام n بیت صفر الحاق کند. این میتواند بررسی صحت پیامی را که سی‌آرسی به آن الحاق شده‌است ساده‌تر کند. در این روش پس از الحاق n بیت صفر و محاسبه مجدد سی‌آرسی، نتیجه دقیقا صفر میشود و باقیمانده کافیست با صفر مقایسه شود.
یک پیاده‌سازی خاص ممکن است نتیجه را با یک الگوی ثابت XOR کند.
ترتیب بیت‌ها: برخی روش‌ها کم‌ارزش‌ترین بیت را نخست قرار می‌دهند و برخی بالعکس. ترتیب بیت‌ها در سخت‌افزارهای انتقال سریالی داده بسیار اهمیت دارد زیرا اکثر روشهای انتقال که به صورت وسیع استفاده میشوند از الگوی ابتدا-کم‌ارزش‌ترین-بیت استفاده می‌کنند.
ترتیب بایت‌ها: در سی‌آرسی‌های چند بایتی، ممکن است این تردید پیش آید که آیا بایت منتقل شده اول، کم‌ارزش‌ترین بایت است یا باارزش‌ترین. به عنوان مثال در برخی روش‌ها بایت‌های سی‌آرسی ۱۶بیتی را جابجا می‌کنند.
حذف باارزش‌ترین بیت چندجمله‌ای مقسم: از آنجایی که باارزش‌ترین بیت همیشه یک است، و از آنجایی که یک سی‌آرسی nبیتی باید به صورت یک مقسم (n+1) بیتی تعریف شود و در این صورت میتواند از یک ثبات nبیتی سرریز میشود، برخی نویسندگان بیان بیت بالای مقسم را غیرضروری می‌دانند.
2-1-5-4 سی‌آرسی‌های پرکاربرد و استاندارد
اگرچه سی‌آرسی‌ها از اجزای معیارها متعددی هستند اما خودشان، از منظر وجود الگوریتمی جهانی، مورد قبول نیستند. به عنوان مثال دو چندجمله‌ای سی‌آرسی-۱۲، ده نوع مستند سی‌آرسی-۱۶ و چهار سی‌آرسی-۳۲ وجود دارد. این چندجمله‌ای‌ها عموما بهترین چندجمله‌ای‌های ممکن نیستند. بین ۱۹۹۳ و ۲۰۰۴، کوپمن، کستاگنولی و سایرین فضای چندجمله‌ای‌ها تا ۱۶ بیت، 24 و ۳۲ بیتی را جهت یافتن مثال‌هایی با کارایی بهتر (از نظر فاصله هامنی برای یک طول پیام خاص) از چندجمله‌ای‌های پروتکل‌های پیشین بررسی کردند و بهترین آنها را در جهت بهبود ظرفیت تشخیص خطای استانده‌های آتی منتشر کردند. به طور خاص، iSCSI یکی از یافته‌های این پژوهش را مورد استفاده قرار داده‌است.
2-1-6 کد گری
نمایش کدهای دودویی که بعد از فرانک گری (Frank Gray) به نام کد گری شناخته شد که یک سیستم از اعداد دودویی است که هر دو عدد متوالی فقط در یک بیت با هم اختلاف داشته باشند. امروزه کد‌گری به طور گسترده برای تصحیح اشکالات در سیستم ارتباط دیجیتالی مثل کابل‌های تلویزیونی و تلویزیون‌های دیجیتالی جهانی استفاده میشود.
یکی از محققان آزمایشگاه بل (Bell) به نام فرانک گری اولین بار به طور رسمی کد گری را مورد استفاده قرار داد و این کد بعد از گری توسط افرادی که از آن استفاده می‌کردند کد گری نامگذاری شد.
2-1-6-1 تاریخچه و کاربردهای علمی
کد گری قبل از آن که در مهندسی به کار رود در جدول‌ها پازل‌های ریاضی به کار برده می‌شد، ریاضیدان فرانسویEmile Boudat از کد گری در سال۱۸۷۸در تلگراف استفاده کرد و برای این کارش مدال دریافت کرد و اما کاربردهای آن، از کد گری به عنوان یک رمزگذار استفاده میشود که نسبت به رمزگذار عادی برتری دارد. در نمایش کد گری خاصیت دایره‌ای بودن آن باعث میشود که دو عدد دو سر نیز فقط در یک بیت متفاوت باشند. کد گری یک دور همیلتونی در یک مکعب n بعدی Qn تولید می‌کند که هر کدام از اعداد آن یک راس را نشان میدهد و نیز در الگوریتم‌های ژنتیکی از آن استفاده میشود و نیز البته برچسب گذاری جدول کارنو از موارد دیگر استفاده آن است. زمانی کد گری برای آدرس دهی حافظه در کامپیوتر استفاده میشود کامپیوتر نیروی کمتری صرف یافتن آدرس‌ها می‌کند چون هر آدرس با قبلی فقط در یک بیت متفاوت است. طراحان مدارهای منطقی از کد گری به طور گسترده برای عبور چند بیت اطلاعات بین سیستمهای همزمان استفاده می‌کنند.
دایره کد گری
2-1-6-2 انگیزهٔ پیدایش کد گری
بعضی از دستگاه‌ها وضعیت دستگاه را با کدهای باینری نمایش می‌دهند، اگر این دستگاه‌ها از کد باینری عادی استفاده کند این دو وضعیت پشت سر هم خواهند بود 011 -- > 100 و مشکل کد باینری عادی این است که در حالت طبیعی خیلی بعید نست که چند بیت همزمان تغییر کنند همان طور که در بالا نمایش داده شده‌است که در کد باینری عادی هر سه بیت همزمان تغییر کرده‌اند اما می‌توان اعداد را طوری در کنار هم قرار داد که فقط در یک بیت متفاوت باشند و تغییر زیادی نکنند مثلا" 011 − 001 − 101 − 100 پس کد باینری منعکس شده یا همان کد گری این مشکل را حل می‌کند زیرا که فقط یک بیت در آنها تغییر می‌کند.
با توجه به حالت ۷ و ۰ می‌بینیم که فقط در یک بیت تفاوت دارند که همان خاصیت دوره‌ای یا چرخشی بودن کد گری می‌گوییم.
2-1-6-2 انگیزهٔ پیدایش کد گری
بعضی از دستگاه‌ها وضعیت دستگاه را با کدهای باینری نمایش می‌دهند، اگر این دستگاه‌ها از کد باینری عادی استفاده کند این دو وضعیت پشت سر هم خواهند بود 011 -- > 100 و مشکل کد باینری عادی این است که در حالت طبیعی خیلی بعید نست که چند بیت همزمان تغییر کنند همان طور که در بالا نمایش داده شده‌است که در کد باینری عادی هر سه بیت همزمان تغییر کرده‌اند اما می‌توان اعداد را طوری در کنار هم قرار داد که فقط در یک بیت متفاوت باشند و تغییر زیادی نکنند مثلا" 011 − 001 − 101 − 100 پس کد باینری منعکس شده یا همان کد گری این مشکل را حل می‌کند زیرا که فقط یک بیت در آنها تغییر می‌کند.
| Gray | Binary | |
| 000 | 000 | 0 |
| 001 | 001 | 1 |
| 011 | 010 | 2 |
| 010 | 011 | 3 |
| 110 | 100 | 4 |
| 111 | 101 | 5 |
| 101 | 110 | 6 |
| 100 | 111 | 7 |
با توجه به حالت ۷ و ۰ می‌بینیم که فقط در یک بیت تفاوت دارند که همان خاصیت دوره‌ای یا چرخشی بودن کد گری می‌گوییم.
===
با اضافه کردن یک بیت توازن به کد همینگ می توان بروز دو خطا را تشخیص داد.
نظرات شما عزیزان:
تبادل
لینک هوشمند