کشف و تصحیح خطا مقاله شماره 4
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 تولید می‌کند که هر کدام از اعداد آن یک راس را نشان می‌دهد و نیز در الگوریتم‌های ژنتیکی از آن استفاده می‌شود و نیز البته برچسب گذاری جدول کارنو از موارد دیگر استفاده آن است. زمانی کد گری برای آدرس دهی حافظه در کامپیوتر استفاده می‌شود کامپیوتر نیروی کمتری صرف یافتن آدرس‌ها می‌کند چون هر آدرس با قبلی فقط در یک بیت متفاوت است. طراحان مدارهای منطقی از کد گری به طور گسترده برای عبور چند بیت اطلاعات بین سیستم‌های همزمان استفاده می‌کنند.
دایره کد گری
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 |
با توجه به حالت ۷ و ۰ می‌بینیم که فقط در یک بیت تفاوت دارند که همان خاصیت دوره‌ای یا چرخشی بودن کد گری می‌گوییم.
===
با اضافه کردن یک بیت توازن به کد همینگ می توان بروز دو خطا را تشخیص داد.