巡回冗長検査
巡回冗長検査とは、データ転送時のエラーチェック法のひとつである。「周期冗長検査」「CRC」などと呼ばれることもある。
巡回冗長検査では、ビット列を多項式の係数に見立てた上で、あらかじめ定められた生成多項式で割り切れるように、余りを付加してデータを転送し、受信側で割り切れなかったら誤りがあると判断する仕組みとなっている。
誤りパターンに応じたシンドロームを用いるとエラー訂正も可能で、検査効率、エラー検出能力が高くてオーバーヘッドが少ないという特徴がある。ITU-T(国際電気通信連合電気標準化セクター)で生成多項式がいくつも標準化されており、HDLCのフレーム制御、銀行のATM、イーサネットやIP、などでも採用されている。
巡回冗長検査
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/06/28 04:58 UTC 版)
巡回冗長検査(じゅんかいじょうちょうけんさ、英: Cyclic Redundancy Check, CRC)は、誤り検出符号の一種で、主にデータ転送などに伴う偶発的な誤りの検出によく使われている。送信側は定められた生成多項式で除算した余りを検査データとして付加して送信し、受信側で同じ生成多項式を使用してデータを除算し、その余りを比較照合することによって受信データの誤り・破損を検出する。
- ^ Peterson, W. W. and Brown, D. T. (1961-1). “Cyclic Codes for Error Detection”. Proceedings of the IRE 49: 228. doi:10.1109/JRPROC.1961.287814. ISSN 0096-8390.
- ^ a b Brayer, K; Hammond, J L Jr. (1975). "Evaluation of error detection polynomial performance on the AUTOVON channel". Conference Record. National Telecommunications Conference, New Orleans, La. 1. New York: Institute of Electrical and Electronics Engineers. pp. 8-21 to 8-25.
- ^ “(slib) Cyclic Checksum”. 2008年4月6日閲覧。
- ^ Greg Cook (2008年9月9日). “Catalogue of parameterised CRC algorithms”. 2008年9月9日閲覧。
- ^ a b c Koopman, Philip; Chakravarty, Tridib (2004年), Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks
- ^ Castagnoli, G. and Braeuer, S. and Herrman, M. (1993-6). “Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits”. IEEE Transactions on Communications 41 (6): 883. doi:10.1109/26.231911. ISSN 0090-6778. - Castagnoli's et al. CRC多項式のアルゴリズム選択に関する研究
- ^ a b c d e f Koopman, P. (2002-6). “32-Bit Cyclic Redundancy Codes for Internet Applications”. The International Conference on Dependable Systems and Networks: 459. doi:10.1109/DSN.2002.1028931 . - Castagnoli の結果を総当り探索で検証し、新たによい多項式を発見した。
- ^ Perez, A.; Wismer & Becker (1983年). “Byte-Wise CRC Calculations”. IEEE Micro 3 (3): 40–50. doi:10.1109/MM.1983.291120. ISSN 0272-1732.
- ^ Ramabadran, T.V.; Gaitonde, S.S. (1988年). “A tutorial on CRC computations”. IEEE Micro 8 (4): 62-75. doi:10.1109/40.7773. ISSN 0272-1732.
- ^ Thomas Boutell, Glenn Randers-Pehrson, et al. (1998年7月14日). “PNG (Portable Network Graphics) Specification, Version 1.2”. 2008年4月28日閲覧。
- 巡回冗長検査のページへのリンク