|
یک '''کد افزونگی دوره ای''' {{انگلیسی|Cyclic redundancy code}} (سی‌آرسی) تابع درهم‌سازی غیرایمنی است که جهت تشخیص تغییرات تصادفی بر روی داده‌های خام طراحی شده‌است. این تابع عموماً در شبکه‌های مخابراتی دیجیتال و وسایل ذخیره‌سازی داده‌ها از جمله دیسک سخت مورد استفاده قرار می‌گیرد. یک دستگاه دارای قابلیت سی‌آرسی، یک توالی کوتاه و با طول ثابت را، به نام ''کد سی‌آرسی'' (یا فقط ''سی‌آرسی'')، برای هر بلاک از داده‌ها محاسبه نموده و آن را همراه با داده‌ها ذخیره یا ارسال می‌کند. زمانی که یک بلاک دریافت یا خوانده می‌شود دستگاه محاسبه را تکرار می‌کند؛ در صورت مغایرت با کد محاسبه شده قبلی مشخص می‌شود که این بلاک دارای ''خطای داده'' است و در این حالت دستگاه ممکن است عملی را جهت اصلاح خطا از جمله خواندن یا درخواست ارسال مجدد بلاک انجام دهد. اصطلاح سی‌آرسی می‌تواند به کد اعتبارسنج یا تابع تولید کد اطلاق شود. سی‌آرسی‌ها به جهت پیاده‌سازی ساده در سخت‌افزار دودویی، سادگی تحلیل ریاضی آن‌ها و عملکرد خوب در تشخیص خطاهای معمول حاصل از اختلال در کانال‌های انتقال دارای محبوبیت زیادی هستند. سی‌آرسی توسط W. Wesley Peterson اختراع و در مقاله ۱۹۶۱ وی منتشر شد.AAAA<ref name="PetersonBrown1961"BBBB>
{{یادکرد|فصل=|کتاب=|ناشر= |چاپ= |شهر= |کوشش= |ویرایش= |سال=|شابک=|نویسنده= Peterson, W. Wesley. ; Brown, D. T.|نویسندگان سایر بخش‌ها=|ترجمه=|صفحه=228 |زبان=en |مقاله= Cyclic Codes for Error Detection |ژورنال= Proceedings of the IRE |نشریه=|تاریخ= {{{day}}} January {{چر}}1961 |دوره=49 |شماره= |شاپا=}}</refBBBBref> سی‌آرسی ۳۲ بیتی (CRC32) پیشنهادی موسسه مهندسین الکتریک و الکترونیک (IEEE)، که در اترنت و سایر جاها استفاده شده‌است، در کنفرانس مخابراتی سال ۱۹۷۵ ظاهر شد.
== مقدمه ==
سی‌آرسی یک کد تشخیص خطا است. محاسبه آن شبیه عمل تقسیم اعشاری است که خارج قسمت حذف می‌شود و باقی‌مانده به عنوان نتیجه در نظر گرفته می‌شود، با این تفاوت مهم که محاسبات آن محاسبات بدون رقم نقلی از یک میدان محدود است. اعلام یک سی‌آرسی خاص با مشخص کردن مقسوم علیه و سایر مشخصات آن انجام می‌شود.
اگرچه سی‌آرسی‌ها می‌توانند با استفاده از هر میدان محدودی ساخته شوند، همه سی‌آرسی‌های پرکاربرد از میدان محدود <span dir="ltr"BBBBGF>GF(2)</spanBBBBspan> بهره می‌برند. این میدانی از دو عنصر، عموماً به نام ۰ و ۱، است که به راحتی با معماری کامپیوتر سازگار است.
یک دلیل مهم برای محبوبیت سی‌آرسی‌ها برای تشخیص تغییرات تصادفی داده‌ها اطمینان از کیفیت آن‌ها است. نوعاً، یک سی‌آرسی nبیتی، که برای یک بلاک داده با طول دلخواه محاسبه شده‌است، هر حوزه خطای با طول کمتر از n بیت (به عبارت دیگر، هر تغییری که محدوده آن بیش از n بیت مجاور از داده‌ها نباشد) و <span dir="ltr"BBBB۱>۱-۲<supBBBBsup> -n</supBBBBsup></spanBBBBspan> تعداد از سایر حوزه‌های با طول بیش از n بیت را تشخیص می‌دهد. خطاها در هیچ‌یک از کانال‌های انتقال و رسانه‌های ذخیره‌سازی مغناطیسی دارای توزیع تصادفی نیستند و در نتیجه فایده خواص سی‌آرسی‌ها را نسبت به سایر روش‌های تشخیص خطا از جمله کدهای چندگانه زوجیت بیشتر می‌کنند.
ساده‌ترین سامانه تشخیص خطا، بیت زوجیت، در واقع یک سی‌آرسی عادی است که از مقسوم علیه دوبیتی ۱۱ استفاده می‌کند.
برای محاسبه یک سی‌آرسی دودویی nبیتی، بیت‌های ورودی را در یک سطر بنویسید، و الگوی (n+1)بیتی را که نشان‌دهنده مقسوم علیه سی‌آرسی است (و چندجمله‌ای نامیده می‌شود) زیر سمت چپ‌ترین بیت قرار دهید. در زیر، اولین محاسبه برای ایجاد یک سی‌آرسی ۳۲ بیتی (CRC32) نشان داده شده‌است:
<pre>
<preBBBB
11010011101100 <--- ورودی
1011 <--- مقسوم علیه (۴ بیت)
----
01100011101100 <--- نتیجه
</preBBBBpre>
اگر سمت چپ ترین بیت ورودی بالای مقسوم علیه صفر باشد، محاسبه‌ای انجام نشده و مقسوم علیه را یک بیت به راست حرکت می‌دهیم. اگر سمت چپ ترین بیت ورودی بالای مقسوم علیه یک باشد، مقسوم علیه و ورودی XOR می‌شوند (به بیان دیگر بیت ورودی بالای هر بیت یک مقسوم علیه عکس می‌شود). سپس مقسوم علیه را یک بیت به راست حرکت می‌دهیم و این روند تا زمانی تکرار می‌شود که انتهای مقسوم علیه به انتهای سطر ورودی نرسیده‌است. در زیر، آخرین محاسبه نشان داده شده‌است:
<pre>
<preBBBB
00000000001110 <--- نتیجه محاسبه قبلی
1011 <--- مقسوم علیه
----
00000000000101 <--- باقی‌مانده (۳ بیت)
</preBBBBpre>
از آنجایی که چپ‌ترین بیت مقسوم علیه در مواجه با هر بیت یک ورودی آن را صفر می‌کند، وقتی این روند پایان می‌یابد تنها بیت‌های ورودی که می‌توانند غیر صفر باشند آخرین n بیت سمت راست است. این n بیت، باقی‌مانده مرحله تقسیم است و البته همان مقدار تابع سی‌آرسی است (مگر آنکه تابع سی‌آرسی انتخابی شامل تعدادی پس‌پردازش باشند).
== سی‌آرسی‌های پرکاربرد و استانده ==
اگرچه سی‌آرسی‌ها از اجزای استانده‌های متعددی هستند اما خودشان، از منظر وجود الگوریتمی جهانی، استانده نیستند. به عنوان مثال دو چندجمله‌ای سی‌آرسی-۱۲AAAA۱۲<ref name=slibBBBBslib>{{یادکرد|فصل=|کتاب=|ناشر= |چاپ= |شهر= |کوشش= |ویرایش= |سال=|شابک=|نویسنده= |نویسندگان سایر بخش‌ها=|ترجمه=|صفحه= |زبان=en |مقاله= [http://os.cqu.edu.au/cgi-bin/info/info2html.cgi?(slib)Cyclic%20Checksum (slib) Cyclic Checksum] |ژورنال= |نشریه= |تاریخ= |دوره= |شماره= |شاپا=}} Retrieved on 6 April 2008.</refBBBB،ref>، ده نوع مستند سی‌آرسی-۱۶ و چهار سی‌آرسی-۳۲ وجود دارد. این چندجمله‌ای‌ها عموماً بهترین چندجمله‌ای‌های ممکن نیستند. بین ۱۹۹۳ و ۲۰۰۴، کوپمن، کستاگنولی و سایرین فضای چندجمله‌ای‌ها تا ۱۶ بیت، ۲۴ و ۳۲ بیتی را جهت یافتن مثال‌هایی با کارایی بهتر (از نظر فاصله هامنی برای یک طول پیام خاص) از چندجمله‌ای‌های پروتکل‌های پیشین بررسی کردند و بهترین آن‌ها را در جهت بهبود ظرفیت تشخیص خطای استانده‌های آتی منتشر کردند. به طور خاص، iSCSI یکی از یافته‌های این پژوهش را مورد استفاده قرار داده‌است.
جدول زیر تنها شامل چندجمله‌ای‌های مورد استفاده در الگوریتم‌های متداول است. همانطور که پیش‌تر توضیح داده شد هر پروتکل خاص می‌تواند دارای چینش‌های بیت مختلفی باشد. سی‌آرسی‌ها در پروتکل‌های تجاری ممکن است از مقدار اولیه خاص و XOR نهایی جهت مبهم‌سازی استفاده کنند ولی این کار استحکام رمزنگاری الگوریتم را افزایش نمی‌دهد.
|-
|CRC-1 || <mathBBBBxmath>x + 1</mathBBBBmath> (اغلب در سخت‌افزار؛ و همچنین معروف به ''بیت زوجیت'') || 0<span dir="ltr"BBBBx1>x1 or 0x1 (0x1)</spanBBBBspan>
|-
|CRC-4-ITU || <mathBBBBxmath>x^4 + x + 1</mathBBBBmath> (ITU [http://www.itu.int/rec/T-REC-G.704-199810-I/en G.704]، صفحه ۱۲) || <span dir="ltr"BBBB0x3>0x3 or 0xC (0x9)</spanBBBBspan>
|-
|CRC-5-EPC || <mathBBBBxmath>x^5 + x^3 + 1</mathBBBBmath> (RFID نسل دومAAAAدوم<ref name="gen-2-spec"BBBB>{{یادکرد|فصل=|کتاب=|ناشر= EPCglobal |چاپ= |شهر= |کوشش= |ویرایش= |سال=|شابک=|نویسنده= |نویسندگان سایر بخش‌ها=|ترجمه=|صفحه=۱۰۸ ۳۵ |زبان=en |مقاله= [http://www.epcglobalinc.org/standards/uhfc1g2/uhfc1g2_1_0_9-standard-20050126.pdf Class-1 Generation-2 UHF RFID Protocol] |ژورنال= |نشریه=|تاریخ=23 October 2008 |دوره= |شماره= |شاپا= }}</refBBBBref>) || <span dir="ltr"BBBB0x09>0x09 or 0x12 (0x14)</spanBBBBspan>
|-
|CRC-5-ITU || <mathBBBBxmath>x^5 + x^4 + x^2 + 1</mathBBBBmath> (ITU [http://www.itu.int/rec/T-REC-G.704-199810-I/en G.704]، صفحه ۹) || <span dir="ltr"BBBB0x15>0x15 or 0x15 (0x1A)</spanBBBBspan>
|-
|CRC-5-USB || <mathBBBBxmath>x^5 + x^2 + 1</mathBBBBmath> (بسته‌های [[USB]]) || <span dir="ltr"BBBB0x05>0x05 or 0x14 (0x12)</spanBBBBspan>
|-
|CRC-6-ITU || <mathBBBBxmath>x^6 + x + 1</mathBBBBmath> (ITU [http://www.itu.int/rec/T-REC-G.704-199810-I/en G.704]، صفحه ۳) || <span dir="ltr"BBBB0x03>0x03 or 0x30 (0x21)</spanBBBBspan>
|-
|CRC-7 || <mathBBBBxmath>x^7 + x^3 + 1</mathBBBBmath> (سامانه‌های مخابراتی, MMC, SD) || <span dir="ltr"BBBB0x09>0x09 or 0x48 (0x44)</spanBBBBspan>
|-
|CRC-8-ATM || <mathBBBBxmath>x^8 + x^2 + x + 1</mathBBBBmath> (ATM HEC) || <span dir="ltr"BBBB0x07>0x07 or 0xE0 (0x83)</spanBBBBspan>
|-
|CRC-8-CCITT || <mathBBBBxmath>x^8 + x^7 + x^3 + x^2 + 1</mathBBBBmath> (گذرگاه تک-سیم) || <span dir="ltr"BBBB0x8D>0x8D or 0xB1 (0xC6)</spanBBBBspan>
|-
|CRC-8-Dallas/Maxim || <mathBBBBxmath>x^8 + x^5 + x^4 + 1</mathBBBBmath> (گذرگاه تک-سیم) || <span dir="ltr"BBBB0x31>0x31 or 0x8C (0x98)</spanBBBBspan>
|-
|CRC-8 || <mathBBBBxmath>x^8 + x^7 + x^6 + x^4 + x^2 + 1</mathBBBBmath> || <span dir="ltr"BBBB0xD5>0xD5 or 0xAB (0xEA)</spanBBBBspan>
|-
|CRC-8-SAE J1850 || <mathBBBBxmath>x^8 + x^4 + x^3 + x^2 + 1</mathBBBBmath> || <span dir="ltr"BBBB0x1D>0x1D or 0xB8 (0x8E)</spanBBBBspan>
|-
|CRC-10 || <mathBBBBxmath>x^{10} + x^9 + x^5 + x^4 + x + 1</mathBBBBmath> || <span dir="ltr"BBBB0x233>0x233 or 0x331 (0x319)</spanBBBBspan>
|-
|CRC-11 || <mathBBBBxmath>x^{11} + x^9 + x^8 + x^7 + x^2 + 1</mathBBBBmath> (FlexRay) || <span dir="ltr"BBBB0x385>0x385 or 0x50E (0x5C2)</spanBBBBspan>
|-
|CRC-12 || <mathBBBBxmath>x^{12} + x^{11} + x^3 + x^2 + x + 1</mathBBBBmath> (سامانه‌های مخابراتی,
|| 0x80F or 0xF01 (0xC07)
|-
|CRC-15-CAN|| <mathBBBBxmath>x^{15} + x^{14} + x^{10} + x^8 + x^7 + x^4 + x^3 + 1 </mathBBBBmath> || <span dir="ltr"BBBB0x4599>0x4599 or 0x4CD1 (0x62CC)</spanBBBBspan>
|-
|CRC-16-CCITT || <mathBBBBxmath>x^{16} + x^{12} + x^5 + 1</mathBBBBmath> (سرآیندهای G.hn PHY, 802.15.4, X.25, V.41, CDMA, [[بلوتوث]], XMODEM, HDLC,PPP, IrDA, BACnet؛ معروف به ''CRC-CCITT'', MMC, SD) || <span dir="ltr"BBBB0x1021>0x1021 or 0x8408 (0x8810)</spanBBBBspan>
|-
|CRC-16-DNP || <mathBBBBxmath>x^{16} + x^{13} + x^{12} + x^{11} + x^{10} + x^8 + x^6 + x^5 + x^2 + 1</mathBBBBmath> (DNP, IEC 870, M-Bus) || <span dir="ltr"BBBB0x3D65>0x3D65 or 0xA6BC (0x9EB2)</spanBBBBspan>
|-
|CRC-16-[[IBM]] || <mathBBBBxmath>x^{16} + x^{15} + x^2 + 1</mathBBBBmath> (SDLC, [[USB]]، غیره؛ و همچنین معروف به ''CRC-16'') || <span dir="ltr"BBBB0x8005>0x8005 or 0xA001 (0xC002)</spanBBBBspan>
|-
|CRC-24 || <mathBBBBxmath>x^{24} + x^{22} + x^{20} + x^{19} + x^{18} + x^{16} + x^{14} + x^{13} + x^{11} + x^{10} + x^8 + x^7 + x^6 + x^3 + x + 1</mathBBBBmath> (FlexRay) || <span dir="ltr"BBBB0x5D6DCB>0x5D6DCB or 0xD3B6BA (0xAEB6E5)</spanBBBBspan>
|-
|CRC-24-Radix-64 || <mathBBBBmath> x^{24} + x^{23} + x^{18} + x^{17} + x^{14} + x^{11} + x^{10} + x^7 + x^6 + x^5 + x^4 + x^3 + x + 1 </mathBBBBmath> (OpenPGP) || <span dir="ltr"BBBB0x864CFB>0x864CFB or 0xDF3261 (0xC3267D)</spanBBBBspan>
|-
|CRC-30 || <mathBBBBxmath>x^{30} + x^{29} + x^{21} + x^{20} + x^{15} + x^{13} + x^{12} + x^{11} + x^{8} + x^{7} + x^{6} + x^{2} + x + 1 </mathBBBBmath> (CDMA) || <span dir="ltr"BBBB0x2030B9C7>0x2030B9C7 or 0x38E74301 (0x30185CE3)</spanBBBBspan>
|-
|CRC-32-IEEE 802.3 || <mathBBBBxmath>x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1</mathBBBBmath> (V.42, MPEG-2, PNG، کد مجموع POSIX)
|| <span dir="ltr"BBBB0x04C11DB7>0x04C11DB7 or 0xEDB88320 (0x82608EDB)</spanBBBBspan>
|-
|CRC-32C (Castagnoli) || <mathBBBBxmath>x^{32} + x^{28} + x^{27} + x^{26} + x^{25} + x^{23} + x^{22} + x^{20} + x^{19} + x^{18} + x^{14} + x^{13} + x^{11} + x^{10} + x^9 + x^8 + x^6 + 1</mathBBBBmath> (G.hn payload) || <span dir="ltr"BBBB0x1EDC6F41>0x1EDC6F41 or 0x82F63B78 (0x8F6E37A0)</spanBBBBspan>
|-
|CRC-32K (Koopman) || <mathBBBBxmath>x^{32} + x^{30} + x^{29} + x^{28} + x^{26} + x^{20} + x^{19} + x^{17} + x^{16} + x^{15} + x^{11} + x^{10} + x^{7} + x^{6} + x^{4} + x^{2} + x + 1</mathBBBBmath> || <span dir="ltr"BBBB0x741B8CD7>0x741B8CD7 or 0xEB31D82E (0xBA0DC66B)</spanBBBBspan>
|-
|CRC-32Q || <mathBBBBxmath>x^{32} + x^{31} + x^{24} + x^{22} + x^{16} + x^{14} + x^{8} + x^{7} + x^{5} + x^{3} + x + 1</mathBBBBmath> (aviation; AIXM AAAA<ref name="aixm-primer"BBBB>{{یادکرد|فصل=|کتاب=|ناشر= European Organisation for the Safety of Air Navigation |چاپ= |شهر= |کوشش= |ویرایش= |سال=|شابک=|نویسنده= |نویسندگان سایر بخش‌ها=|ترجمه=|صفحه= |زبان=en |مقاله= [http://www.eurocontrol.int/aim/gallery/content/public/aicm_aixm_4_5/aixm_primer/AIXM_Primer_4.5.pdf AIXM Primer] |ژورنال= |نشریه=|تاریخ=20 March 2006 |دوره= |شماره= |شاپا= }}</refBBBBref>) || <span dir="ltr"BBBB0x814141AB>0x814141AB or 0xD5828281 (0xC0A0A0D5)</spanBBBBspan>
|-
|CRC-64-ISO || <mathBBBBxmath>x^{64} + x^4 + x^3 + x + 1</mathBBBBmath> (HDLC — ISO 3309) || <span dir="ltr"BBBB0x000000000000001B>0x000000000000001B or 0xD800000000000000 (0x800000000000000D)</spanBBBBspan>
|-
|CRC-64-ECMA-182 || <mathBBBBxmath>x^{64} + x^{62} + x^{57} + x^{55} + x^{54} + x^{53} + x^{52} + x^{47} + x^{46} + x^{45} + x^{40} + x^{39} + x^{38} + x^{37} + x^{35} + x^{33} +</mathBBBBmath> <mathBBBBxmath>x^{32} + x^{31} + x^{29} + x^{27} + x^{24} + x^{23} + x^{22} + x^{21} + x^{19} + x^{17} + x^{13} + x^{12} + x^{10} + x^9 + x^7 + x^4 + x + 1</mathBBBBmath> ([http://www.ecma-international.org/publications/standards/Ecma-182.htm ECMA-182] صفحه 51) || <span dir="ltr"BBBB0x42F0E1EBA9EA3693>0x42F0E1EBA9EA3693 or 0xC96C5795D7870F42 (0xA17870F5D4F51B49)</spanBBBBspan>
|-
| 