کد افزونگی چرخشی: تفاوت میان نسخه‌ها

یک '''کد افزونگی دوره‌ای''' {{انگلیسی|Cyclic redundancy check}} (سی‌آرسی) تابع درهم‌سازی غیرایمنی است که جهت تشخیص تغییرات تصادفی بر روی داده‌های خام طراحی شده‌است. این تابع عموماً در شبکه‌های مخابراتی دیجیتال و وسایل ذخیره‌سازی داده‌ها از جمله دیسک سخت مورد استفاده قرار می‌گیرد. یک دستگاه دارای قابلیت سی‌آرسی، یک توالی کوتاه و با طول ثابت را، به نام ''کد سی‌آرسی'' (یا فقط ''سی‌آرسی'')، برای هر بلاک از داده‌ها محاسبه نموده و آن را همراه با داده‌ها ذخیره یا ارسال می‌کند. زمانی که یک بلاک دریافت یا خوانده می‌شود دستگاه محاسبه را تکرار می‌کند؛ در صورت مغایرت با کد محاسبه شده قبلی مشخص می‌شود که این بلاک دارای ''خطای داده'' است و در این حالت دستگاه ممکن است عملی را جهت اصلاح خطا از جمله خواندن یا درخواست ارسال مجدد بلاک انجام دهد. اصطلاح سی‌آرسی می‌تواند به کد اعتبارسنج یا تابع تولید کد اطلاق شود. سی‌آرسی‌هاCRCها به جهت پیاده‌سازی ساده در سخت‌افزار دودویی، سادگی تحلیل ریاضی آن‌ها و عملکرد خوب در تشخیص خطاهای معمول حاصل از اختلال در کانال‌های انتقال دارای محبوبیت زیادی هستند. سی‌آرسی توسط W. Wesley Peterson اختراع و در مقاله ۱۹۶۱ وی منتشر شد.<ref name="PetersonBrown1961">{{یادکرد|فصل=|کتاب=|ناشر= |چاپ= |شهر= |کوشش= |ویرایش= |سال=|شابک=|نویسنده= Peterson, W. Wesley. ; Brown, D. T.|نویسندگان سایر بخش‌ها=|ترجمه=|صفحه=228 |زبان=en |مقاله= Cyclic Codes for Error Detection |ژورنال= Proceedings of the IRE |نشریه=|تاریخ= January {{چر}}1961 |دوره=49 |شماره= |شاپا=}}</ref> سی‌آرسی ۳۲ بیتی (CRC32) پیشنهادی مؤسسه مهندسین الکتریک و الکترونیک (IEEE)، که در اترنت و سایر جاها استفاده شده‌است، در کنفرانس مخابراتی سال ۱۹۷۵ ظاهر شد.

اگرچه سی‌آرسی‌هاCRCها می‌توانند با استفاده از هر میدان محدودی ساخته شوند، همه سی‌آرسی‌هایCRCهای پرکاربرد از میدان محدود <span dir="ltr">GF(2)</span> بهره می‌برند. این میدانی از دو عنصر، عموماً به نام ۰ و ۱، است که به راحتی با معماری کامپیوتر سازگار است.

یک دلیل مهم برای محبوبیت سی‌آرسی‌هاCRCها برای تشخیص تغییرات تصادفی داده‌ها اطمینان از کیفیت آن‌ها است. نوعاً، یک سی‌آرسی nبیتی، که برای یک بلاک داده با طول دلخواه محاسبه شده‌است، هر حوزه خطای با طول کمتر از n بیت (به عبارت دیگر، هر تغییری که محدوده آن بیش از n بیت مجاور از داده‌ها نباشد) و <span dir="ltr">۱–۲^-n</span> تعداد از سایر حوزه‌های با طول بیش از n بیت را تشخیص می‌دهد. خطاها در هیچ‌یک از کانال‌های انتقال و رسانه‌های ذخیره‌سازی مغناطیسی دارای توزیع تصادفی نیستند و در نتیجه فایده خواص سی‌آرسی‌هاCRCها را نسبت به سایر روش‌های تشخیص خطا از جمله کدهای چندگانه زوجیت بیشتر می‌کنند.

== سی‌آرسی‌هاCRCها و تمامیت داده‌ها ==

سی‌آرسی‌ها،CRCها، به خودی خود، راهکار مناسبی برای حفاظت در مقابل تغییرات عمدی روی داده نیستند (مثلاً در برنامه‌های اعتبارسنجی)، چون مبانی ساده ریاضیات آن‌ها باعث می‌شود که بتوان هر تغییر دلخواه را روی داده‌ها طوری اعمال کرد که سی‌آرسی داده‌ها تغییر نکند.

اغلب این فرض غلط وجود دارد که وقتی پیامی به همراه سی‌آرسی آن از یک کانال آزاد دریافت می‌شود و سی‌آرسی دریافتی با سی‌آرسی محاسبه شده مطابقت می‌کند پس پیام ممکن نیست در حین دریافت تغییر کرده باشد. این درست نیست چون هر دوی آن‌ها می‌توانند تغییر کرده باشند، به طوری که سی‌آرسی جدید با پیام جدید مطابقت کند؛ بنابراین سی‌آرسی‌هاCRCها می‌توانند جهت بررسی درستی داده‌ها استفاده شوند ولی نه برای اطمینان از تمامیت آن.

از آنجایی که چپ‌ترین بیت مقسوم علیه در مواجه با هر بیت یک ورودی آن را صفر می‌کند، وقتی این روند پایان می‌یابد تنها بیت‌های ورودی که می‌توانند غیر صفر باشند آخرین n بیت سمت راست است. این n بیت، باقی‌مانده مرحله تقسیم است و البته همان مقدار تابع سی‌آرسی است (مگر آنکه تابع سی‌آرسی انتخابی شامل تعدادی پس‌پردازشپس پردازش باشند).

* '''ترتیب بایت‌ها''': در سی‌آرسی‌هایCRCهای چند بایتی، ممکن است این تردید پیش آید که آیا بایت منتقل شده اول، کم‌ارزش‌ترین بایت است یا باارزش‌ترین. به عنوان مثال در برخی روش‌ها بایت‌های سی‌آرسی ۱۶بیتی را جابجا می‌کنند.

== سی‌آرسی‌هایCRCهای پرکاربرد و استانده ==

اگرچه سی‌آرسی‌هاCRCها از اجزای استانده‌های متعددی هستند اما خودشان، از منظر وجود الگوریتمی جهانی، استانده نیستند. به عنوان مثال دو چندجمله‌ای سی‌آرسی-۱۲،<ref name=slib>{{یادکرد|فصل=|کتاب=|ناشر= |چاپ= |شهر= |کوشش= |ویرایش= |سال=|شابک=|نویسنده= |نویسندگان سایر بخش‌ها=|ترجمه=|صفحه= |زبان=en |مقاله= [http://os.cqu.edu.au/cgi-bin/info/info2html.cgi?(slib)Cyclic%20Checksum (slib) Cyclic Checksum] |ژورنال= |نشریه= |تاریخ= |دوره= |شماره= |شاپا=}} Retrieved on 6 April 2008.</ref> ده نوع مستند سی‌آرسی-۱۶ و چهار سی‌آرسی-۳۲ وجود دارد. این چندجمله‌ای‌ها عموماً بهترین چندجمله‌ای‌های ممکن نیستند. بین ۱۹۹۳ و ۲۰۰۴، کوپمن، کستاگنولی و سایرین فضای چندجمله‌ای‌ها تا ۱۶ بیت، ۲۴ و ۳۲ بیتی را جهت یافتن مثال‌هایی با کارایی بهتر (از نظر فاصله هامنی برای یک طول پیام خاص) از چندجمله‌ای‌های پروتکل‌های پیشین بررسی کردند و بهترین آن‌ها را در جهت بهبود ظرفیت تشخیص خطای استانده‌های آتی منتشر کردند. به طور خاص، iSCSI یکی از یافته‌های این پژوهش را مورد استفاده قرار داده‌است.

جدول زیر تنها شامل چندجمله‌ای‌های مورد استفاده در الگوریتم‌های متداول است. همان‌طور که پیش‌تر توضیح داده شد هر پروتکل خاص می‌تواند دارای چینش‌های بیت مختلفی باشد. سی‌آرسی‌هاCRCها در پروتکل‌های تجاری ممکن است از مقدار اولیه خاص و XOR نهایی جهت مبهم‌سازی استفاده کنند ولی این کار استحکام رمزنگاری الگوریتم را افزایش نمی‌دهد.

''توجه: در این جدول باازرش‌ترینبا ازرش‌ترین بیت حذف شده است؛ جهت توضیح به قسمت مشخصات سی‌آرسی در بالا مراجعه کنید. ''

سی‌آرسی‌هایCRCهای زیر نیز وجود دارند ولی از نظر فنی کارایی ندارند و عمدتاً با توابع درهم‌سازی رمزی جایگزین شده‌اند:

* [http://serversniff.net/crypt-checksum.php ابزاری برای محاسبه سی‌آرسی‌هایCRCهای معمول (۸/۱۶/۳۲/۶۴) از روی رشته‌ها]

* [http://www.paulschou.com/tools/xlate/ کدگشا و کدنگارکد نگار کاراکتر (ASCII)، مبنای ۱۶، دودویی، مبنای ۶۴، غیره... به همراه الگوریتم‌های درهم‌سازی MD2، MD4، MD5، SHA1+2، CRC، غیره]