Main Content

巡回冗長検査の実行

ライブ スクリプトを開く

この例では、数値のビットに対して "巡回冗長検査" (CRC) を実行する方法を説明します。CRC は、デジタル システムでのデータ送信のエラーを検出するのに使用されます。データが送信される際に、短い "チェック値" がそれに付加されます。このチェック値は、データ内のビットを使った多項式除算で取得されます。データを受信すると多項式除算が繰り返され、結果がチェック値と比較されます。結果が異なっている場合、データは送信時に破損しています。

チェック値の手動計算

まず、送信するメッセージである 16 ビットの 2 進数から開始します。

1101100111011010

チェック値を取得するには、この数値を多項式 x3+x2+x+1 で除算します。この多項式はその係数 1111 で表すことができます。

除算は段階的に実行され、各ステップの後で多項式の除数が数値内で最も左にある 1 と揃えられます。4 項の多項式による除算の結果は 3 ビットになるため (一般に、長さ n+1 の多項式で除算すると、長さ n のチェック値が得られる)、剰余の計算用に数値に 000 を追加します。各ステップでは、演算対象である 4 ビットのビット単位の XOR が結果で使用され、その他すべてのビットは変更されません。

最初の除算は次のとおりです。

1101100111011010 000
1111
----------------
0010100111011010 000

後続の除算はそれぞれ、前のステップの結果に対して行われるため、2 番目の除算は次のようになります。

0010100111011010 000
  1111
----------------
0001010111011010 000

被除数がすべて 0 になると除算は完了します。上記の 2 ステップを含め、完全な除算は次のようになります。

1101100111011010 000
1111
0010100111011010 000
  1111
0001010111011010 000
   1111
0000101111011010 000
    1111
0000010011011010 000
     1111
0000001101011010 000
      1111
0000000010011010 000
        1111
0000000001101010 000
         1111
0000000000010010 000
           1111
0000000000001100 000
            1111
0000000000000011 000
              11 11
0000000000000000 110

剰余のビット 110 がこのメッセージのチェック値になります。

チェック値のプログラムによる計算

MATLAB® では、上記と同じ演算を実行して、ビット単位の演算を使用するチェック値を取得できます。まず、メッセージの変数と多項式除数の変数を定義します。符号なしの 32 ビット整数を使用して、余分なビットを剰余に使用できるようにします。

message = 0b1101100111011010u32;
messageLength = 16;
divisor = 0b1111u32;
divisorDegree = 3;

次に、多項式除数を初期化します。dec2bin を使用して結果のビットを表示します。

divisor = bitshift(divisor,messageLength-divisorDegree-1);
dec2bin(divisor)
ans = 
'1111000000000000'

次に、除数とメッセージをシフトして、ビットの数が正しくなるようにします (メッセージは 16 ビット、剰余は 3 ビット)。

divisor = bitshift(divisor,divisorDegree);
remainder = bitshift(message,divisorDegree);
dec2bin(divisor)
ans = 
'1111000000000000000'

dec2bin(remainder)
ans = 
'1101100111011010000'

for ループを使用して CRC の除算のステップを実行します。for ループは常にステップごとに 1 ビット進むため、現在の桁が 1 かどうかを確認するチェックを含めます。現在の桁が 1 の場合、除算ステップを実行します。そうでない場合は、ループを 1 ビット進めて続行します。

for k = 1:messageLength
    if bitget(remainder,messageLength+divisorDegree)
        remainder = bitxor(remainder,divisor);
    end
    remainder = bitshift(remainder,1);
end

剰余のビットを右にシフトし、演算のチェック値を取得します。

CRC_check_value = bitshift(remainder,-messageLength);
dec2bin(CRC_check_value)
ans = 
'110'

メッセージの整合性のチェック

同じ除算演算を繰り返すことで、チェック値を使用してメッセージの整合性を検証できます。ただし、最初に剰余として 000 を使用するのではなく、チェック値 110 を使用します。メッセージに誤りがなければ、除算の結果は 0 になります。

剰余変数をリセットし、ビット単位の OR を使用して、CRC チェック値を剰余ビットに加算します。bitset を使ってビット値の 1 つを反転させることで、メッセージに誤りを導入します。

remainder = bitshift(message,divisorDegree);
remainder = bitor(remainder,CRC_check_value);
remainder = bitset(remainder,6);
dec2bin(remainder)
ans = 
'1101100111011110110'

CRC 除算の演算を実行した後、結果が 0 かどうかを確認します。

for k = 1:messageLength
    if bitget(remainder,messageLength+divisorDegree)
        remainder = bitxor(remainder,divisor);
    end
    remainder = bitshift(remainder,1);
end
if remainder == 0
    disp('Message is error free.')
else
    disp('Message contains errors.')
end
Message contains errors.

参照

[1] Sklar, Bernard. Digital Communications: Fundamentals and Applications. Englewood Cliffs, NJ: Prentice Hall, 1988.

[2] Wicker, Stephen B. Error Control Systems for Digital Communication and Storage. Upper Saddle River, NJ: Prentice Hall, 1995.

参考

|

関連するトピック