Top / CRC方式

CRC方式

目次 †

CRC †

　CRC（Cyclic Redundancy Check：巡回冗長検査）とは、誤り制御の一種である。パリティチェックよりも高度な仕組みとなっている。

　CRCは、ビット列のデータをある生成多項式で割った余りを検査用のCRC符号として、データに付加して送信する方式である。受信側は、受信したデータが同じ生成多項式で割り切れるか否かで誤りの発生を検出する。

　用いられる生成多項式はビット長によって代わるが、代表的なものとしてX16+X12+X5+1がある。この生成生成多項式で割るということは、係数がmod 2としてみたときのビット列10001000000100001で割るということである。

CRCの特徴 †

• 他の冗長符号の方式であるパリティチェック方式よりも冗長度に比較して高い誤り検出能力を持つという利点を持つ。
• データ伝送制御系（例：HDLCを用いたシステム）やフレキシブルディスク装置にはビット誤りの検出を目的としてCRCが広く用いられている。
• これらの制御系にはマイクロコンピュータを使用し、同期制御・入出力制御などの機能と合わせてCRC演算を実行することが多い。
  • この場合、マイクロコンピュータの処理負荷（ステップ数）の中でCRC演算を実現する部分は比較的大きな割合を占めているので、その最適化は重要である。
• 生成多項式で割った余りを検査用のCRC符号として利用する。パリティチェックよりも計算は複雑になるが、バースト誤り（誤りが集中して発生する現象）に強い。

CRCの仕組み †

　CRCのデータブロック（nビット）は、情報ビット（kビット）と検査ビット（n-kビット）から構成される。

　これらは一般に多項式で実現される。

例：1101のようなビット列Dは、多項式D(x)=X3+X2+1のように表すことができる。

　CRCによる誤り検出は、送信側でメッセージをひとつの多項式で表現し、これをCRCの生成多項式G(X)で割り算し、その剰余を情報ビットに続けて伝送路に送り出す。よって、情報ビットと付加された検査ビットを多項式で表現したものはG(X)で割り切れる。

例：1101を101で割ったとき、商が11、余りが10になる。1101の後に10を付加した結果の110111は101で割ると、商が1110、余りが0になる。　◇

　そこで、受信側では受信データをG(x)で割り算し、剰余が0であれば誤りがなしとし、剰余が0でなければ誤りがあったと判定する*1。

CRCの演算 †

　例えば、生成多項式がG(X)=X3+X+1のとき、データビットDに対する剰余は次のように行われる。

　このときの商と剰余は次の通りである。

• 商：
• 剰余：

　よって、旧剰余の係数と新剰余の係数の関係は次のように表される。ただし、Ri（i=0,1,2）は新しい係数である。この3つの漸化式を(*)と置く。

[補講]任意の長さmのデータに対応する多項式f(X)をt次生成多項式G(X)で割る演算は、t段線形帰還シフトレジスタ（G(X)の項に対応したフィードバックを持つ）によって、m回のシフトで実行できる。　◇

　CRCでは標準的に生成多項式としてG(X)=X16+X12+X5+1が使われる。このとき、nビットのデータD(0),D(1),…,D(n-1)に対するCRC演算は、漸化式(*)をn回繰り返すことに相当する。ただし、k=0,1,…,n-1である。この3つの漸化式を(**)と置く。

• 　（i=0）
• 　（i=5,12）
• 　（i≠0,5,12）

　ここで、は旧剰余、は新剰余（いずれも高次の係数より低位の係数へ）を指す。

CRCの演算の高速化 †

　ここでは8ビットのマイクロコンピュータのプログラムで実現することを前提として考える。

XOR命令＋シフト命令の方法 †

　漸化式(**)のからへの変換をXOR（排他的論理和）命令とシフト命令を用いて演算する方法について考える。XOR命令の使用回数が最小となるようにシフト命令の仕様手順を考えればよい。

　単位処理ビット数が8ビットのとき、XOR命令回数は5回になる。

　また、シフト命令の回数はマイクロコンピュータのシフト命令の機能によって異なる。例えば、1ビット右シフト/左シフトによる場合、単位処理ビット数が1〜8ビットにおいて、シフト命令の回数は10回前後をふらつく。

　XOR命令回数とシフト命令の回数を合わせて考慮すると、単位処理ビット数が1〜8ビットの中で8ビットのときに最も効率がよい。結論を述べれば、1ビットのとき（ビットシリアルの演算）と比べると、4倍効率がよくなっている。

8080における実装 †

　Intel 8080系（例えば8080Aなどを含む）での実装例である（Z80,F-8も同様）。

　このとき、レジスタの使い道は次の通りである。

　このときアルゴリズムは次のようになる。ただし、演算直前のAレジスタには8ビットのデータ、BとCレジスタには旧剰余が格納されているものとする。

1. AレジスタとBレジスタ間でXOR演算を行い、その結果をDレジスタに格納する。
2. Dレジスタの内容を4ビット左シフトした結果を、Dレジスタの元の内容でXOR演算する。その結果をDレジスタに格納する。
   • しかし、1ビット左シフトすることは2倍することと同値なので、ここでは1ビット左シフト命令より命令実行時間の短い加算命令でシフト命令を代行する。
3. Dレジスタの内容を3ビット左シフトし、その結果をEレジスタに格納する。
4. Eレジスタの内容とビットパターン"1111 1000"（16進数でF8）をAND演算する。その結果をCレジスタとXOR演算して、その結果をBレジスタに格納する。
5. Eレジスタの内容を1ビット左シフトした後に、ビットパターン"0000 1111"（16進数で0F）とAND演算を行う。その結果とBレジスタのXOR演算を行い、その結果をBレジスタに格納する。
6. Eレジスタの内容とビットパターン"0000 0111"（16進数で07）とAND演算を行う。そして、その結果とDレジスタとでXOR演算を行い、その結果をCレジスタに格納する。
7. 最終的にBとCレジスタの内容が新剰余になる。Bレジスタが高位の8ビット（RU）、Cレジスタが低位の8ビット（RL）に対応する。
   • このBとCレジスタの内容がそのまま次の8ビットデータに対しては旧剰余に対応する。よって、次の8ビットデータに対しては、このデータをAレジスタにセットして、同一のアルゴリズムを実行すればよい。このようにして、入力データに対応する回数分繰り返した結果のBとCレジスタの内容が全入力データに対するCRCデータになる。

　次のコードは上記のアルゴリズムをIntel 8080のアセンブリ言語に実装したものである。コメントアウトの数字はアルゴリズムの箇条書きの番号と対応している。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24

XRA B        ; ��A←A XOR B
MOV D,A        ; D←A
ADD A        ; ��以下4行合わせて、A+A+A+A、即ち4×Aと同等の動き
ADD A
ADD A
ADD A
XRA D        ; A←A XOR D
MOV D,A        ; D←A
RLC            ; �０焚�3行合わせて、Aを3ビット左シフト
RLC
RLC
MOV E,A        ; E←A
ANI 0F8H    ; ��A←A AND "1111 1000"　A=Eの状態でこの演算をするので、レジスタEに対して行っていることと同じ
XRA C        ; A←A XOR C
MOV B,A        ; B←A
MOV A,E        ; ��A←E
RLC            ; 1ビット左シフト
ANI 0FH        ; A←A AND "0000 1111"
XRA B        ; A←A XOR B
MOV B,A        ; B←A
MOV A,E        ; ��A←E
ANI 07H        ; A←A AND "0000 0111"
XRA D        ; A←A XOR D
MOV C,A        ; C←A

M6800における実装 †

　モトローラ社のM6800での実装例である（MC6502も同様）。8080Aの例と比較すると、M6800はレジスタの構成が異なるので、次のように両者のレジスタとエリアの使い方が対応する。

テーブルルックアップの方法 †

　テーブルルックアップとは、テーブルが格納されている右端アドレスを指示し、この場合データレジスタと剰余レジスタのXOR演算の結果がテーブルのインデックスと一致しているかどうかを調べて、もし一致していればそのときの内容を出力する。

　漸化式(**)のの上位nビットと下位(16-n)ビットを分離して取扱い、前者とデータビットとのXOR演算の結果に対する剰余演算をテーブルルックアップにより求めて、その結果と下位(16-n)ビットとのXOR演算の結果が求める剰余となる。

　この方法は、CRC演算の場合、テーブルの内容によってテーブルを引く回数が異なる。テーブルを大きくすれば、引く回数が少なくなる。一方、テーブルを小さくすれば、引く回数が多くなる。よって、テーブルの大きさによって演算時間が大きく左右される。

まとめ †

　XOR命令＋シフト命令の方法とテーブルルックアップの方法を比較する。前者は単位処理ビット数が8ビットのときが最も効率がよい（ただし、1〜8ビットの中に限定したとき）。後者は前者より数倍早くできるが、メモリ容量が大きくなってしまう。よって、総合的なコスト性能では前者の方が優れているといえる。

参考文献 †

• 『1週間で分かる基本情報技術者集中ゼミ【午前編】　2006春秋』
• 『インターフェース　1977年2月号　No.13』