基本情報技術者 2010年秋期午後問03

CRC（巡回冗長検査）に関する次の記述を読んで、設問1〜3に答えよ。

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

設問1：

　次の記述中のに入れる正しい答えを、解答群の中から選べ。　　CRCを採用したパケット転送システムでは、送信側でパケットに符号が付加され、受信側で誤りの有無を検査する。受信側で誤りが検出されると、送信側に対して該当パケットの再送を要求する。100個のパケットに格納されたデータの転送において、受信側が実際に受信したパケットが、再送されたパケットも含めて個であったとすると、受信したパケットの20%から誤りが検出されたことになる。ここで、送信したパケットは必ず相手に届くものとする。また、パケットの再送要求は誤りなく届き、再送要求には必ず応じるものとする。　解答群　ア：100 　イ：102 　ウ：120 　エ：125

模範解答

エ

解説

解答の導き方

CRC（Cyclic Redundancy Check：巡回冗長検査）は、データに付けた符号を使って、受信したデータに誤りがないか調べる方法です。この問題では、誤りが見つかったパケットは再送されます。

受信したパケットの合計を

x

個とします。ここには、最初に送られたパケットだけでなく、再送されたパケットも含まれます。

問題文には、受信したパケットの20%から誤りが検出されたとあります。そのため、誤りが検出されたパケットは

0.2 x

個です。

誤りが検出されたパケットは、再送を要求されます。また、送信したパケットは必ず届き、再送要求にも必ず応じるので、データを正しく受信するまで送信が続きます。したがって、誤りのないパケットを受信した回数は、元のデータに対応する100個です。誤りが検出されたパケットは、その100個に加えて受信した分です。

よって、受信したパケットの合計は次の式で表せます。

x = 100 + 0.2 x

両辺から

0.2 x

を引くと、

0.8 x = 100

したがって、

x = 100 \div 0.8 = 125

実際、125個の20%は25個です。誤りがあった25個に対して再送が行われ、誤りのないパケット100個と合わせて、受信数は125個になります。

誤りやすいポイント

20%の対象を、最初に送信した100個だと考えないようにします。問題文の「受信したパケット」には、再送されたパケットも含まれます。
20%を100個に掛けて20個の誤りとし、合計を120個とするのは誤りです。120個の20%は24個なので、誤りの割合が20%になりません。
再送されたパケットにも誤りが起きる可能性があります。その場合も誤りとして数えられ、さらに再送されます。

FAQ

Q: 再送されたパケットも、誤りの割合を計算するときの対象ですか？
A: はい。受信したパケットの合計には、再送されたパケットも含まれます。再送されたパケットに誤りがあった場合も、誤りの数に含めます。

Q: なぜ受信したパケットのうち、誤りがないものを100個と考えるのですか？
A: 元のデータ100個それぞれについて、誤りのない受信が必要だからです。誤りのある受信は正しい受信の代わりにはならず、再送されます。

Q: CRCはパケットを再送する仕組みですか？
A: CRCは、受信したデータの誤りを検出する方法です。誤りを検出した後に再送を要求する仕組みは、問題文で別に説明されています。

関連キーワード: CRC、誤り検出、パケット、再送制御

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

設問2：

問題文を見る

　次の記述中のに入れる正しい答えを、解答群の中から選べ。　　任意の長さのビット列の符号を求める計算手順を次に示す。ここで、符号の長さはnビットとする。　〔nビットの符号を求める計算手順〕　(1) 左端及び右端のビットが1である(n+1)ビットのビットパターン（以下、マスクという）を定める。　(2) 符号計算対象のビット列の右端にnビットの0を付加したビット列を作る。　(3) (2)で作ったビット列に対して次の操作を行う。　　① ビット列の左端から調べ、最初に値が1であるビットの位置pを見つける。　　② pを左端としp+nを右端とする部分ビット列に対し、マスクで排他的論理和（XOR）を取る。　　③ ビット列の右端nビット以外がすべて0になるまで、①及び②を繰り返す。　(4) (3)の操作で得られたビット列の右端nビットが符号となる。

　図に、マスクが101のときの符号（2ビット）を計算する例を示す。基本情報技術者試験（平成22年午後問3 図）

　マスク101で計算した、符号計算対象のビット列0010 0110の2ビットの符号はである。　解答群　ア：00 　イ：01 　ウ：10 　エ：11

模範解答

イ

解説

解答の導き方

CRC（Cyclic Redundancy Check：巡回冗長検査）は、データに誤りがないかを調べるための方法です。この問題では、指定されたマスクを使ってビット列にXOR（Exclusive OR：排他的論理和）を繰り返し、最後に残るビットを符号とします。

符号の長さは2ビットなので、計算手順に従って、符号計算対象のビット列の右端に2ビットの0を付けます。

00100110 → 0010011000

マスクは101です。最初に値が1であるビットを左から探し、その位置から3ビット分を取り出してマスク101とXORします。マスクが3ビットなのは、符号の長さ2ビットに1を加えた長さだからです。

XORでは、同じ値どうしなら0、異なる値どうしなら1になります。左端の1から順に計算すると、次のようにビット列が変化します。

操作	計算を始める前のビット列	最初の1から取り出す3ビットと計算	計算後のビット列
1回目	0010011000	100 XOR 101 = 001	0000111000
2回目	0000111000	111 XOR 101 = 010	0000010000
3回目	0000010000	100 XOR 101 = 001	0000000100
4回目	0000000100	100 XOR 101 = 001	0000000001

最後のビット列では、符号として残す右端2ビット以外がすべて0です。したがって、右端の2ビットを取り出すと01です。解答群では、これはイに当たります。

誤りやすいポイント

符号の長さが2ビットの場合、最初に付け加える0も2ビットです。マスクは、符号の長さより1ビット長い3ビットになります。
XORする範囲は、左端から探した最初の1を先頭とする3ビットです。毎回、ビット列全体にマスクを当てるわけではありません。
計算を終えるのは、ビット列全体が0になったときではありません。右端の2ビット以外がすべて0になったときです。その右端の2ビットが符号です。

FAQ

Q: なぜ、計算対象のビット列の右端に0を付けるのですか？
A: 符号を入れる場所をあらかじめ確保するためです。この問題では符号が2ビットなので、右端に2ビットの0を付けてから計算します。

Q: XORは、普通の引き算と同じですか？
A: そのままの引き算とは異なります。XORは、ビットごとに同じ値なら0、異なる値なら1とし、桁上がりや桁借りをしません。

Q: 最後に元のビット列の右端2ビットを使うのですか？
A: いいえ。計算を繰り返した後のビット列の右端2ビットを使います。元のビット列の右端2ビットではありません。

関連キーワード: CRC、巡回冗長検査、排他的論理和（XOR）、誤り検出符号、ビット列

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

設問3：

問題文を見る

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

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

　受信したビット列（符号が付加されたビット列）を、誤りの有無の検査手順に従って検査すると、誤りがなければ最後に残った右端nビットの値はaになる。このことは次の手順で説明できる。　〔手順〕　(1) 符号計算対象のビット列を一つの数値Dと見ると、符号Cは次の式で表せる。　　式①　（

D \times 2^{n}

）⊕

d_{1}

⊕

d_{2}

⊕ ⋯ ⊕

d_{m}

C

　　ここで、⊕はXORを表し、mはXORの繰返し回数とする。

d_{i}

（

1 \leq i \leq m

）はマスクに対応するビット列である。図の例では、

d_{1} = 0101000000

、

d_{2} = 0001010000

、

d_{3} = 0000001010

である。　(2) 〔誤りの有無の検査手順〕で得られた結果の右端nビットの値Tは、次の式で表せる。　　式②　（

D \times 2^{n}

）⊕

C

⊕

d_{1}

⊕

d_{2}

⊕ ⋯ ⊕

d_{m}

T

　(3) 式②を変形すると次の式となる。　　式③　（

D \times 2^{n}

）⊕

d_{1}

⊕

d_{2}

⊕ ⋯ ⊕

d_{m}

⊕

C

T

　(4) 式①と式③によって、　　b =

T

　　となる。

　マスク101で計算した符号を右端に付加したビット列1001001101を受信した。このビット列にはc。　 aに関する解答群　ア：すべてのビットが0 　イ：すべてのビットが1 　ウ：符号と同じ　エ：符号の各ビットを反転させたものと同じ　 bに関する解答群　ア：

2^{n} - 1

　イ：

C

　ウ：

C

⊕ (

2^{n} - 1

) 　エ：

C

⊕

C

　 cに関する解答群　ア：誤りが含まれる　イ：誤りは含まれない　ウ：誤りが含まれるか否かは判断できない

模範解答

a：ア、b：エ、c：ア

解説

解答の導き方

CRC（Cyclic Redundancy Check：巡回冗長検査）は、データに検査用のビットを付け、受信側で計算し直して誤りを調べる方法です。XOR（exclusive OR：排他的論理和）は、ビットごとに比べて、同じ値なら0、異なる値なら1を出す演算です。マスクは、符号の計算や検査に使うビット列です。

まず、aとbを式から考えます。

式①では、符号計算対象のビット列を表す項と、マスクを使った計算結果をXORした値が、符号

C

になると説明されています。ここで、

(D \times 2^{n}) \oplus d_{1} \oplus d_{2} \oplus \dots \oplus d_{m}

の部分は、式①によって

C

と同じ値です。

式③の左辺は、この部分にさらに

C

をXORしています。したがって、式③は次のように置き換えられます。

C \oplus C = T

XORでは、同じビット同士を計算すると0になります。たとえば、

0 \oplus 0 = 0

、

1 \oplus 1 = 0

です。そのため、

C \oplus C

はすべてのビットが0です。よって、bには「

C \oplus C

」が入り、検査結果の右端

n

ビットである

T

もすべて0になります。aは「すべてのビットが0」です。

次に、cを実際に検査します。問題文には「マスク101で計算した符号を右端に付加したビット列1001001101」とあります。マスクが101の場合、検査する符号は2ビットです。受信したビット列にマスクをずらしながらXORし、左側の1がなくなるまで計算します。0は、マスクの位置をそろえるために補っています。

手順	XORするマスク	計算結果
開始		1001001101
1	1010000000	0011001101
2	0010100000	0001101101
3	0001010000	0000111101
4	0000101000	0000010101
5	0000010100	0000000001

最後に残る右端2ビットは01です。誤りがなければ右端2ビットはすべて0になるので、01が残ったこのビット列には誤りが含まれると判断できます。したがって、cは「誤りが含まれる」です。

誤りやすいポイント

XORを、繰り上がりのある通常の足し算と混同しないようにしましょう。同じビット同士なら、どちらも結果は0です。
検査では、受信したビット列全体が0になるかではなく、最後に残る右端 $n$ ビットを確認します。
検査結果が0以外なら、この問題のように誤りを検出できます。一方、0であれば、必ず誤りがなかったと証明できるわけではありません。

FAQ

Q: なぜ $C \oplus C$ はすべて0になるのですか？
A: XORは同じビット同士を計算すると0になるためです。 $C$ の各ビットは、自分自身とXORするとすべて0になります。
Q: 受信したビット列の検査結果が0なら、誤りは絶対にないのですか？
A: 絶対とはいえません。CRCは誤りを検出する仕組みですが、誤りがあっても検査結果が0になる場合があります。
Q: マスクが101なのに、なぜ検査する符号は2ビットなのですか？
A: マスクは3ビットですが、問題の例では符号の長さは2ビットです。マスクを使って計算した結果として、右端に残る2ビットを符号として扱います。

関連キーワード: CRC、巡回冗長検査、XOR、誤り検出、ビット列

解説を読んでも分からないところは、AIに質問できます。この問題の本文と解説をふまえて答えます。

この設問をAIに質問する

クイズモードで開きます（AIへの質問は無料の会員登録で使えます）

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！

基本情報技術者 2010年 秋期 午後 問03

CRC（巡回冗長検査）に関する次の記述を読んで、設問1〜3に答えよ。

.css-epvm6{white-space:nowrap;}設問1：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

設問2：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

設問3：

模範解答

解説

解答の導き方

誤りやすいポイント

FAQ

基本情報技術者 2010年秋期午後問03

設問1：