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


2021-01-25 更新

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

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

今回のテーマは、 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. ビット列の左端から調べ,最初に値が 1 であるビットの位置 p を見つける。
  2. p を左端とし p + n を右端とする部分ビット列に対し,マスクで排他的論理和 (XOR) を取る。
  3. ビット列の右端 n ビット以外がすべて 0 になるまで, 1. 及び 2. を繰り返す。
(4)
(3)の操作で得られたビット列の右端 n ビットが符号となる。
図に, マスクが 101 のときの符号( 2 ビット)を計算する例を示す。

図 マスクが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 ビットです。

  1. まず、ビット列 00100110 の右端に n = 2 ビットの 0 を付加して、ビット列を 0010011000 にします。
  2. 次に、ビット列 0010011000 の左端の 1 の位置にマスクの 101 の左端の 1 を合わせて XOR 演算を行います。
        0010011000
    XOR   101
    ---------------
        0000111000
    
  3. これ以降は、同じ手順を、ビット列の右端の n = 2 ビット以外がすべて0になるまで繰り返します。
        0000111000
    XOR     101
    ---------------
        0000010000
    
        0000010000
    XOR      101
    ---------------
        0000000100
    
        0000000100
    XOR        101
    ---------------
        0000000001 ・・・ビット列の右端の n = 2 ビット以外がすべて 0 になりました。
    
  4. 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 は次の式で表せる。
looks_one (D × 2n)control_pointd1control_pointd2control_pointcontrol_pointdm = C
 ここで,control_pointは XOR を表し,m は XOR の繰返し回数とする。di(1 ≦ i ≦ m) はマスクに対応するビット列である。図の例では, d1 = 0101000000, d2 = 0001010000, d3 = 0000001010 である。
(2)

〔誤りの有無の検査手順〕で得られた結果の右端 n ビットの値 T は,次の式で表せる。
looks_two (D × 2n)control_pointCcontrol_pointd1control_pointd2control_pointcontrol_pointdm = T
(3)
looks_twoを変形すると次の式となる。

looks_3 (D × 2n)control_pointd1control_pointd2control_pointcontrol_pointdmcontrol_pointC = T
(4)
looks_oneと式looks_3によって,

b= T
となる。

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

a に関する解答群

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

b に関する解答群

ア 2n – 1  
イ C  
ウ Ccontrol_point (2n – 1)  
エ Ccontrol_pointC

c に関する解答

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

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

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

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

 

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

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

looks_one (D × 2n)control_pointd1control_pointd2control_pointcontrol_pointdm = C

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

looks_two (D × 2n)control_pointCcontrol_pointd1control_pointd2control_pointcontrol_pointdm = T

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

looks_3 (D × 2n)control_pointd1control_pointd2control_pointcontrol_pointdmcontrol_pointC = T

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

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

Ccontrol_pointC

問題では、この後の説明が省略されていますが、同じ CC という値で 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 になりました。

 

解答設問 2 イ 設問 3 a – ア, b – エ, c – ア

いかがでしたか?

具体例を見て実際に体験したことで、 CRC の仕組みをしっかりと理解できたでしょう。

この連載では、今後も、多くの受験者が苦手としている用語を取り上げて行きます。それでは、またお会いしましょう!

label 関連タグ
実は、午前試験を『免除』できます 独習ゼミで午前免除試験を受けた 86% の方が、
午前試験を免除しています。
2021 年 下期 試験向け
午前免除のチャンスは
6月10日 12時(正午)まで!
info_outline
2021 年 下期 試験向け
午前免除のチャンスは
6月10日 12時(正午)まで!
詳しく見てみるplay_circle_filled
label これまでの『基本情報でわかるテクノロジー』の連載一覧 label 著者

『プログラムはなぜ動くのか』(日経BP)が大ベストセラー
IT技術を楽しく・分かりやすく教える“自称ソフトウェア芸人”

大手電気メーカーでPCの製造、ソフトハウスでプログラマを経験。独立後、現在はアプリケーションの開発と販売に従事。その傍ら、書籍・雑誌の執筆、またセミナー講師として活躍。軽快な口調で、知識0ベースのITエンジニアや一般書店フェアなどの一般的なPCユーザの講習ではダントツの評価。
お客様の満足を何よりも大切にし、わかりやすい、のせるのが上手い自称ソフトウェア芸人。

主な著作物

  • 「プログラムはなぜ動くのか」(日経BP)
  • 「コンピュータはなぜ動くのか」(日経BP)
  • 「出るとこだけ! 基本情報技術者」 (翔泳社)
  • 「ベテランが丁寧に教えてくれる ハードウェアの知識と実務」(翔泳社)
  • 「ifとelseの思考術」(ソフトバンククリエイティブ) など多数