基本情報技術者過去問題平成22年秋期午後問3(ネットワーク)

基本情報技術者過去問題平成22年秋期午後問3

問3　ネットワーク

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

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

設問1

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

　CRCを採用したパケット転送システムでは，送信側でパケットに符号が付加され，受信側で誤りの有無を検査する。受信側で誤りが検出されると，送信側に対して該当パケットの再送を要求する。100個のパケットに格納されたデータの転送において，受信側が実際に受信したパケットが，再送されたパケットも含めて　個であったとすると，受信したパケットの20%から誤りが検出されたことになる。ここで，送信したパケットは必ず相手に届くものとする。また，パケットの再送要求は誤りなく届き，再送要求には必ず応じるものとする。

解答群

解答選択欄

解答

解説

再送された分も含めて受信したパケット全体の20％が誤りだとすると、正しく届くパケットは送信したパケットの80%ということになります。

受信したパケット数をXとして、これを式にすると、

　X×0.8＝100
　X＝125

したがって受信側が実際に受信したパケットが、再送されたパケットも含めて 125個の場合に、受信したパケットの20% から誤りが検出されたことになります。

∴エ：125

設問2

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

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

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

左端及び右端のビットが1である(n＋1)ビットのビットパターン(以下，マスクという)を定める。
符号計算対象のビット列の右端にnビットの0を付加したビット列を作る。
(2)で作ったビット列に対して次の操作を行う。
1. ビット列の左端から調べ，最初に値が1であるビットの位置pを見つける。
2. pを左端とし，p＋nを右端とする部分ビット列に対し，マスクで排他的論理和(XOR)を取る。
3. ビット列の右端nビット以外がすべて0になるまで，①及び②を繰り返す。
(3)の操作で得られたビット列の右端nビットが符号となる。

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

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

解答群

解答選択欄

解答

解説

排他的論理和(XOR)演算は、入力される2つの値が同じ時は0、異なるときは1を出力する論理演算です。

図「マスクが101の時の符号(2ビット)を計算する例」を参考にして、符号計算対象のビット列00100110からマスク101を使って符号を計算する手順を図にすると以下のようになります。

最後に右に残る2ビットが符号になりますので、計算によって求められた符号は01が適切です。

∴イ：01

設問3

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

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

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

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

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

〔手順〕

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

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

a に関する解答群

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

b に関する解答群

2ⁿ－1
C
C⊕(2ⁿ－1)
C⊕C

c に関する解答群

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

解答選択欄

解答

a=ア
b=エ
c=ア

解説

〔aについて〕
誤りがなければ右端nビットはaになる。という部分を確かめたいので、先ほどの設問2での結果を使って確認を試みます。
計算対象のデータ00100110に、計算された符号"01"を付加したビット列"0010011001"に対して設問2の(3)の手順と同様の手順で誤りの有無を検査していきます。

実際に計算を行うと以下のようになります。

誤りのないデータの計算結果では符号が"00"となったので、選択肢から考えると「すべてのビットが0」の場合には、受信したデータに誤りがないと判断できることになります。

∴a＝ア：すべてのビットが0

〔bについて〕
式①と式③は以下の通りです。

2つの式を注意して見ると、式③の中の

は、式①の左辺と全く同じであることがわかります。つまり式③の

は、"C"で置き換えることが可能です。つまり式③を変形し、

　C⊕C＝T

とすることができます。

∴b ＝ エ：C⊕C＝T

〔cについて〕
受信したデータ"1001001101"に対して、マスク101を使い符号を計算します。

計算結果の符号は"01"になり、誤りがない場合の計算結果「すべてのビットが0」ではないので、この受信したデータには誤りが含まれると判断することができます。

∴c＝ア：誤りが含まれる

平成22年秋期午後問題一覧

問1　問2　問3　問4　問5　問6　問7　問8　問9　問10　問11　問12　問13　採点講評