基本情報でわかる CRC 「具体例を見て体験すれば仕組みがわかる」

矢沢久雄
2021-01-25 更新

この記事は基本情報技術者試験の旧制度（ 2022 年以前）の記事ですが、試験対策ではなく、技術用語を理解する上では問題ないと考えています。
試験対策としてお読みになる場合は、現在の試験制度では出題されない午後問題を一部題材にしているので、ご注意ください。

この連載では、基本情報技術者試験によく出題されるテクノロジー関連の用語を、午前問題と午後問題のセットを使って解説します。

午前問題で用語の意味や概念を知り、午後問題で技術の活用方法を知ってください。それによって、単なる丸暗記では得られない明確さで、用語を理解できるようになります。

今回のテーマは、 CRC （巡回冗長検査）です。

CRC に関する午前問題～ CRC とは

いきなりですが、以下をご覧ください。これは、データの誤り検査方式に関する問題です。選択肢に並んでいる用語は、どれも誤り検査方式の名称です。

今回のテーマは、「 CRC （ Cyclic Redundancy Check 、巡回冗長検査）」ですから、当然、この問題の正解は、選択肢アの「 CRC 方式」です。

問 4　平成 22 年度秋期午前

送信側では，ビット列をある生成多項式で割った余りをそのビット列に付加して送信し，受信側では，受信したビット列が同じ生成多項式で割り切れるか否かで誤りの発生を判断する誤り検査方式はどれか。

ア　CRC 方式　　
イ　垂直パリティチェック方式
ウ　水平パリティチェック方式　　
エ　ハミング符号方式

それでは、どのようにして CRC を覚えればよいでしょうか。

問題文にあるように、 CRC の仕組みは、

「送信側では、ビット列をある生成多項式で割った余りを、そのビット列に付加する」

「受信側では、受信したビット列が同じ生成多項式で割り切れるか否かで誤りの発生を判断する」

というものです。しかし、まったくイメージがつかめないでしょう。何か、わかりやすい具体例がほしいところです。

解答ア

CRC に関する午後問題

「基本情報技術者試験は、実によくできているなあ！」と思います。先ほどの午前問題と同じ平成 22 年度秋期の午後問題に、 CRC の具体例を示した問題があるからです。

以下に問題の一部（ CRC の具体例に関する部分）を抜粋したもの示します。

設問 2: 午前問題の「送信側では、ビット列をある生成多項式で割った余りを、そのビット列に付加する」の具体例
設問 3: 午前問題の「受信側では、受信したビット列が同じ生成多項式で割り切れるか否かで誤りの発生を判断する」の具体例

後で内容を詳しく説明しますので、ざっと目を通してください。設問 1 は、省略しています。

問 3　平成 22 年度秋期午後（一部抜粋）

CRC (巡回冗長検査) に関する次の記述を読んで，設問 1 ~ 3 に答えよ。

CRC は，誤り検出方式の一つである。送信側でデータに誤り検出符号 (以下，符号という) を付加して送信し，受信側で検査することによって，転送の際の誤りの有無を判断する。

設問 2　次の記述中のに入れる正しい答えを，解答群の中から選べ。

任意の長さのビット列の符号を求める計算手順を次に示す。ここで，符号の長さは n ビットとする。

〔 n ビットの符号を求める計算手順〕

(1)

左端及び右端のビットが 1 である ( n + 1) ビットのビットパターン (以下，マスクという) を定める。

(2)

符号計算対象のビット列の右端に n ビットの 0 を付加したビット列を作る。

(3)

(2) で作ったビット列に対して次の操作を行う。

ビット列の左端から調べ，最初に値が 1 であるビットの位置 p を見つける。
p を左端とし p + n を右端とする部分ビット列に対し，マスクで排他的論理和 (XOR) を取る。
ビット列の右端 n ビット以外がすべて 0 になるまで， 1. 及び 2. を繰り返す。

(4)

(3)の操作で得られたビット列の右端 n ビットが符号となる。

図に，マスクが 101 のときの符号( 2 ビット)を計算する例を示す。

マスクは 101 で計算した，符号計算対象のビット列 0010 0110 の 2 ビットの符号はである。

解答群
ア　00　　イ　01　　ウ　10　　エ　11

設問 2 は、 CRC の検査符号を求める手順と具体例が示され、同じ手順を使って、マスクが 101 のときの 00100110 に対する検査符号を求めよ、という内容です。

「ビット列を生成多項式で割った余り」が検査符号になるのですが、これは「生成多項式で割る」というよりは「生成多項式で得られた値で割る」と考えた方がわかりやすいでしょう。生成多項式とは、値を得るためのルールのことです。

ここでは、手順の (1) に示された「左端及び右端のビットが 1 である ( + 1) ビットのビットパターン」が生成多項式で得られた値です。そして、割り算の余りとは、通常の割り算ではなく、手順の (3) に示された 1 の位置を合わせて XOR 演算を繰り返し、その結果として得られた右端の n ビットのことなのです。

「え～っ、よくわかんな～い？」だと思いますので、設問 2 を解いて

「送信側では、ビット列をある生成多項式で割った余りを、そのビット列に付加する」

を体験してみましょう。

ここでは、マスク 101 （この問題では、生成多項式で得られた値をマスクと呼んでいます。）とビット列 00100110 で検査符号を求めます。 ( n + 1 )ビットのマスクが 101 という 3 ビットなのですから、検査符号は、 n = 2 ビットです。

まず、ビット列 00100110 の右端に n = 2 ビットの 0 を付加して、ビット列を 0010011000 にします。
次に、ビット列 0010011000 の左端の 1 の位置にマスクの 101 の左端の 1 を合わせて XOR 演算を行います。
```
    0010011000
XOR   101
---------------
    0000111000
```

これ以降は、同じ手順を、ビット列の右端の n = 2 ビット以外がすべて0になるまで繰り返します。

    0000111000
XOR     101
---------------
    0000010000

    0000010000
XOR      101
---------------
    0000000100

    0000000100
XOR        101
---------------
    0000000001 ・・・ビット列の右端の n = 2 ビット以外がすべて 0 になりました。

0000000001というビット列の右端の n = 2 ビットの 01 が検査符号です。

以上のことから、選択肢イが正解です。

ビット列の左端の 1 の位置にマスクの左端の 1 を合わせて XOR 演算を行うと、 1 XOR 1 は 0 なので、その位置を 0 にできます。これをビット列の右端の n = 2 ビット以外がすべて 0 になるまで繰り返して、右端の n = 2 ビットに得られた値が「ビット列を生成多項式で割った余り」なのです。

今度は、設問 3 を解いて、

「受信側では、受信したビット列が同じ生成多項式で割り切れるか否かで誤りの発生を判断する」

の意味を確認してみましょう。

設問 3　次の記述中のに入れる正しい答えを，解答群の中から選べ。

誤りの有無の検査は，次の手順で行う。

〔誤りの有無の検査手順〕

(1): 受信したビット列に対して，送信側で符号の計算に利用したものと同じマスクを使い，〔 n ビットの符号を求める計算手順〕の (3) と同じ処理を行う。
(2)
: 右端 n ビットの値によって，誤りの有無を判断する。

　受信したビット列(符号が付加されたビット列)を誤りの有無の検査手順に従って検査すると，誤りがなければ最後に残った右端 n ビットの値はaになる。このことは次の手順で説明できる。

〔手順〕

(1): 符号計算対象のビット列を一つの数値 D と見ると，符号 C は次の式で表せる。; 式 (D × 2ⁿ)d₁d₂…d_m = C; 　ここで，は XOR を表し，m は XOR の繰返し回数とする。d_i(1 ≦ i ≦ m) はマスクに対応するビット列である。図の例では， d₁ = 0101000000， d₂ = 0001010000， d₃ = 0000001010 である。
(2)
: 〔誤りの有無の検査手順〕で得られた結果の右端 n ビットの値 T は，次の式で表せる。; 式 (D × 2ⁿ)Cd₁d₂…d_m = T
(3): 式を変形すると次の式となる。; 式 (D × 2ⁿ)d₁d₂…d_mC = T
(4): 式と式によって，; b= T; となる。

　マスク 101 で計算した符号を右端に付加したビット列 1001001101 を受信した。このビット列にはc。

a に関する解答群

ア　すべてのビットが 0　　
イ　すべてのビットが 1
ウ　符号と同じ　　
エ　符号の各ビットを反転させたものと同じ

b に関する解答群

ア　2ⁿ – 1　　
イ　C　　
ウ　C (2ⁿ – 1)　　
エ　CC

c　に関する解答

ア　誤りが含まれる　　
イ　誤りは含まれない
ウ　誤りが含まれるか否かは判断できない

ここでも、設問 2 と同様に、「左端及び右端のビットが 1 である ( + 1) ビットのビットパターン」が生成多項式で得られた値であり、割り算の余りとは、 1 の位置を合わせて XOR 演算を繰り返し、その結果として得られた右端の n ビットのことです。

「割り切れる」とは、「割り算の余りがゼロになる」ことなので、検査符号を生成したときと同じ XOR 演算を繰り返して、右端の n ビットがゼロになったら誤りがないと判断できます。

したがって、空欄 a の正解は、選択肢アです。

空欄 b は、右端の n ビットがゼロになったら誤りがないと判断できる理由を示しています。

式は、 XOR 演算を繰り返して、 n ビットの検査符号 C が得られるという意味です。ここでは、検査符号を作成しています。

式 (D × 2ⁿ)d₁d₂…d_m = C

式は、検査符号付きのビット列に同じ XOR 演算を繰り返して得られた右端の n ビットを T としています。ここでは、検査符号を使った誤りの検出を行っています。

式 (D × 2ⁿ)Cd₁d₂…d_m = T

式は、式を変形したものです。

式 (D × 2ⁿ)d₁d₂…d_mC = T

式において赤枠で囲んだ部分は、式の左辺と同じなので、この部分を C と置き換えることができます。

したがて、空欄 b の正解は、選択肢エです。

CC

問題では、この後の説明が省略されていますが、同じ C と C という値で XOR 演算を行うと結果はゼロになります。

したがって、 0 = T になったら、つまり、検査符号を生成したときと同じ XOR 演算を繰り返して、右端の n ビット（ここでは T ）がゼロになったら、誤りがないと判断できるのです。

空欄 c は、マスク 101 で検査符号を付加したビット列 1001001101 に誤りがあるかどうかチェックしてみよう、という内容です。

以下のように、検査符号を生成したときと同じ XOR 演算を繰り返して右端の n = 2 ビットを求めると 01 になるので（ゼロではないので）、誤りが含まれていると判断できます。したがって、空欄 c の正解は、選択肢アです。

    1001001101
XOR 101
---------------
    0011001101

    0011001101
XOR   101
---------------
    0001101101

    0001101101
XOR    101
---------------
    0000111101

    0000111101
XOR     101
---------------
    0000010101

    0000010101
XOR      101
---------------
    0000000001 ・・・ビット列の右端の n = 2 ビット以外がすべて 0 になりました。