موضوع مقاله: کد افزونگی چرخشی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # کد افزونگی چرخشی | مقدمه: کد افزونگی دوره‌ای (سی‌آرسی) یا به عبارت بهتر "بررسی افزونگی چرخه‌ای", تابع درهم‌سازی غیرایمنی است که جهت تشخیص تغییرات تصادفی بر روی داده‌ها خام طراحی شده‌است. | ## بخش 1: کد افزونگی چرخشی | این تابع عموماً در شبکه‌های مخابراتی دیجیتال و وسایل ذخیره‌سازی داده‌ها از جمله دیسک سخت مورد استفاده قرار می‌گیرد. یک دستگاه دارای قابلیت سی‌آرسی، یک توالی کوتاه و با طول ثابت را، به نام کد سی‌آرسی (یا فقط سی‌آرسی)، برای هر بلاک از داده‌ها محاسبه نموده و آن را همراه با داده‌ها ذخیره یا ارسال می‌کند. زمانی که یک بلاک دریافت یا خوانده می‌شود دستگاه محاسبه را تکرار می‌کند؛ در صورت مغایرت با کد محاسبه شده قبلی مشخص می‌شود که این بلاک دارای خطای داده است و در این حالت دستگاه ممکن است عملی را جهت اصلاح خطا از جمله خواندن یا درخواست ارسال مجدد بلاک انجام دهد. CRCها به جهت پیاده‌سازی ساده در سخت‌افزار دودویی، سادگی تحلیل ریاضی آن‌ها و عملکرد خوب در تشخیص خطاهای معمول حاصل از اختلال در کانال‌های انتقال دارای محبوبیت زیادی هستند. سی‌آرسی ۳۲ بیتی (CRC32) پیشنهادی مؤسسه مهندسین الکتریک و الکترونیک (IEEE)، که در اترنت و سایر جاها استفاده شده‌است، در کنفرانس مخابراتی سال ۱۹۷۵ ظاهر شد. محاسبه آن شبیه عمل تقسیم اعشاری است که خارج قسمت حذف می‌شود و باقی‌مانده به عنوان نتیجه در نظر گرفته می‌شود، با این تفاوت مهم که محاسبات آن محاسبات بدون رقم نقلی از یک میدان محدود است. اگرچه CRCها می‌توانند با استفاده از هر میدان محدودی ساخته شوند، همه CRCهای پرکاربرد از میدان محدود GF(2) بهره می‌برند. این میدانی از دو عنصر، عموماً به نام ۰ و ۱، است که به راحتی با معماری کامپیوتر سازگار است. یک دلیل مهم برای محبوبیت CRCها برای تشخیص تغییرات تصادفی داده‌ها اطمینان از کیفیت آن‌ها است. نوعاً، یک سی‌آرسی nبیتی، که برای یک بلاک داده با طول دلخواه محاسبه شده‌است، هر حوزه خطای با طول کمتر از n بیت (به عبارت دیگر، هر تغییری که محدوده آن بیش از n بیت مجاور از داده‌ها نباشد) و کسری معادل با ۱–۲ -n از سایر حوزه‌های خطایی با طول بیش از n بیت را تشخیص می‌دهد. خطاها در هیچ‌یک از کانال‌های انتقال و رسانه‌های ذخیره‌سازی مغناطیسی دارای توزیع تصادفی نیستند و در نتیجه فایده خواص CRCها را نسبت به سایر روش‌های تشخیص خطا از جمله کدهای چندگانه زوجیت بیشتر می‌کنند. ساده‌ترین سامانه تشخیص خطا، بیت زوجیت، در واقع یک سی‌آرسی عادی است که از مقسوم علیه دوبیتی ۱۱ استفاده می‌کند. | ## بخش 2: کد افزونگی چرخشی | CRCها و تمامیت داده‌ها CRCها، به خودی خود، راهکار مناسبی برای حفاظت در مقابل تغییرات عمدی روی داده نیستند (مثلاً در برنامه‌های اعتبارسنجی)، چون مبانی ساده ریاضیات آن‌ها باعث می‌شود که بتوان هر تغییر دلخواه را روی داده‌ها طوری اعمال کرد که سی‌آرسی داده‌ها تغییر نکند. اغلب این فرض غلط وجود دارد که وقتی پیامی به همراه سی‌آرسی آن از یک کانال آزاد دریافت می‌شود و سی‌آرسی دریافتی با سی‌آرسی محاسبه شده مطابقت می‌کند پس پیام ممکن نیست در حین دریافت تغییر کرده باشد. این درست نیست چون هر دوی آن‌ها می‌توانند تغییر کرده باشند، به طوری که سی‌آرسی جدید با پیام جدید مطابقت کند؛ بنابراین CRCها می‌توانند جهت بررسی درستی داده‌ها استفاده شوند ولی نه برای اطمینان از تمامیت آن. ایجاد پیام‌های دیگری که همان سی‌آرسی را ایجاد کنند کار ساده‌ای است، خصوصاً پیام‌هایی که بسیار شبیه پیام اصلی هستند. طبق طراحی پیامی که بسیار شبیه پیام اصلی است (و تفاوت آن تنها در یک الگوی تداخل تصادفی است) سی‌آرسی کاملاً متفاوتی خواهد داشت و بنابراین تشخیص داده خواهد شد. در مقابل، یک راه مؤثر برای محافظت پیام‌ها در برابر تغییرات عمدی استفاده از کدهای اعتبار سنجی پیام همچون HMAC است. محاسبه CRC برای محاسبه یک سی‌آرسی دودویی nبیتی، بیت‌های ورودی را در یک سطر بنویسید، و الگوی (n+1)بیتی را که نشان‌دهنده مقسوم علیه سی‌آرسی است (و چندجمله‌ای نامیده می‌شود) زیر سمت چپ‌ترین بیت قرار دهید. در زیر، اولین محاسبه برای ایجاد یک سی‌آرسی ۳۲ بیتی (CRC32) نشان داده شده‌است: ۱۱۰۱۰۰۱۱۱۰۱۱۰۰ < ورودی ۱۰۱۱ < مقسوم علیه (۴ بیت) ۰۱۱۰۰۰۱۱۱۰۱۱۰۰ < نتیجه اگر سمت چپ‌ترین بیت ورودی بالای مقسوم علیه صفر باشد، محاسبه‌ای انجام نشده و مقسوم علیه را یک بیت به راست حرکت می‌دهیم. اگر سمت چپ‌ترین بیت ورودی بالای مقسوم علیه یک باشد، مقسوم علیه و ورودی XOR می‌شوند (به بیان دیگر بیت ورودی بالای هر بیت یک مقسوم علیه عکس می‌شود). سپس مقسوم علیه را یک بیت به راست حرکت می‌دهیم و این روند تا زمانی تکرار می‌شود که انتهای مقسوم علیه به انتهای سطر ورودی نرسیده‌است. در زیر، آخرین محاسبه نشان داده شده‌است: ۰۰۰۰۰۰۰۰۰۰۱۱۱۰ < نتیجه محاسبه قبلی ۱۰۱۱ < مقسوم علیه ۰۰۰۰۰۰۰۰۰۰۰۱۰۱ < باقی‌مانده (۳ بیت) از آنجایی که چپ‌ترین بیت مقسوم علیه در مواجه با هر بیت یک ورودی آن را صفر می‌کند، وقتی این روند پایان می‌یابد تنها بیت‌های ورودی که می‌توانند غیر صفر باشند آخرین n بیت سمت راست است. این n بیت، باقی‌مانده مرحله تقسیم است و البته همان مقدار تابع سی‌آرسی است (مگر آنکه تابع سی‌آرسی انتخابی شامل تعدادی پس پردازش باشند). | ## بخش 3: کد افزونگی چرخشی | مشخصات سی‌آرسی مفهوم سی‌آرسی به عنوان یک کد تشخیص خطا هنگام پیاده‌سازی آن در یک سامانه واقعی می‌تواند شامل برخی پیچیدگی‌های دیگر نیز باشد. در ذیل، تعدادی از آن‌ها آمده‌است: یک پیاده‌سازی خاص ممکن است یک الگوی بیتی ثابت را پیشوند قرار دهد. این زمانی مفید است که خطاهای ساعتی ممکن است بیت‌های صفر را در ابتدای پیام قرار دهد و در این صورت با این الگو قابل تشخیص است. در این روش پس از الحاق n بیت صفر و محاسبه مجدد سی‌آرسی، نتیجه دقیقاً صفر می‌شود و باقی‌مانده کافیست با صفر مقایسه شود. ترتیب بیت‌ها در سخت‌افزارهای انتقال سریالی داده بسیار اهمیت دارد زیرا اکثر روش‌های انتقال که به صورت وسیع استفاده می‌شوند از الگوی ابتدا-کم‌ارزش‌ترین-بیت استفاده می‌کنند. ترتیب بایت‌ها: در CRCهای چند بایتی، ممکن است این تردید پیش آید که آیا بایت منتقل شده اول، کم‌ارزش‌ترین بایت است یا باارزش‌ترین. حذف باارزش‌ترین بیت چندجمله‌ای مقسم: از آنجایی که باارزش‌ترین بیت همیشه یک است، و از آنجایی که یک سی‌آرسی nبیتی باید به صورت یک مقسوم علیه (n+1)بیتی تعریف شود و در این صورت می‌تواند از یک ثبات nبیتی سرریز می‌شود، برخی نویسندگان بیان بیت بالای مقسوم علیه را غیرضروری می‌دانند. CRCهای پرکاربرد و استاندارد اگرچه CRCها از اجزای استانده‌های متعددی هستند اما خودشان، از منظر وجود الگوریتمی جهانی، استانده نیستند. بین ۱۹۹۳ و ۲۰۰۴، کوپمن، کستاگنولی و سایرین فضای چندجمله‌ای‌ها تا ۱۶ بیت، ۲۴ و ۳۲ بیتی را جهت یافتن مثال‌هایی با کارایی بهتر (از نظر فاصله هامنی برای یک طول پیام خاص) از چندجمله‌ای‌های پروتکل‌های پیشین بررسی کردند و بهترین آن‌ها را در جهت بهبود ظرفیت تشخیص خطای استانده‌های آتی منتشر کردند. همان‌طور که پیش‌تر توضیح داده شد هر پروتکل خاص می‌تواند دارای چینش‌های بیت مختلفی باشد. CRCها در پروتکل‌های تجاری ممکن است از مقدار اولیه خاص و XOR نهایی جهت مبهم‌سازی استفاده کنند ولی این کار استحکام رمزنگاری الگوریتم را افزایش نمی‌دهد. | ## جمع‌بندی | توجه: در این جدول با ازرش‌ترین بیت حذف شده‌است؛ جهت توضیح به قسمت مشخصات سی‌آرسی در بالا مراجعه کنید.