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

⇄問題文と設問を画面2分割で開く⇱問題PDF

問3 ネットワーク

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

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

設問1

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

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

解答選択欄

  •  

解答

  •  

解説

再送された分も含めて受信したパケット全体の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ビット)を計算する例を示す。
pm03_1.png/image-size:358×304
 マスク101で計算した,符号計算対象のビット列00100110の2ビットの符号は である。
解答群
  • 00
  • 01
  • 10
  • 11

解答選択欄

  •  

解答

  •  

解説

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

図「マスクが101の時の符号(2ビット)を計算する例」を参考にして、符号計算対象のビット列00100110からマスク101を使って符号を計算する手順を図にすると以下のようになります。
pm03_5.png/image-size:358×309
最後に右に残る2ビットが符号になりますので、計算によって求められた符号は01が適切です。

イ:01

設問3

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

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

〔誤りの有無の検査手順〕
  • 受信したビット列に対して,送信側で符号の計算に利用したものと同じマスクを使い,〔 nビットの符号を求める計算手順〕の(3)と同じ処理を行う。
  • 右端nビットの値によって,誤りの有無を判断する。
 受信したビット列(符号が付加されたビット列)を,誤りの有無の検査手順に従って検査すると,誤りがなければ最後に残った右端nビットの値はaになる。このことは次の手順で説明できる。

〔手順〕
  • 符号計算対象のビット列を一つの数値Dと見ると,符号Cは次の式で表せる。
    pm03_2.png/image-size:267×16
    ここで,⊕はXOR を表し,mはXORの繰返し回数とする。d1(1≦i≦m)はマスクに対応するビット列である。図の例では,d1=0101000000,d2=0001010000,d3=0000001010である。
  • 〔誤りの有無の検査手順〕で得られた結果の右端nビットの値Tは,次の式で表せる。
    pm03_3.png/image-size:303×15
  • 式②を変形すると次の式となる。
    pm03_4.png/image-size:303×16
  • 式①と式③によって,b=Tとなる。
 マスク101で計算した符号を右端に付加したビット列1001001101を受信した。このビット列にはc
a に関する解答群
  • すべてのビットが0
  • すべてのビットが1
  • 符号と同じ
  • 符号の各ビットを反転させたものと同じ
b に関する解答群
  • 2n-1
  • C
  • C⊕(2n-1)
  • C⊕C
c に関する解答群
  • 誤りが含まれる
  • 誤りは含まれない
  • 誤りが含まれるか否かは判断できない

解答選択欄

  • a:
  • b:
  • c:

解答

  • a=
  • b=
  • c=

解説

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

実際に計算を行うと以下のようになります。
pm03_6.png/image-size:358×309
誤りのないデータの計算結果では符号が"00"となったので、選択肢から考えると「すべてのビットが0」の場合には、受信したデータに誤りがないと判断できることになります。

aア:すべてのビットが0

bについて〕
式①と式③は以下の通りです。
pm03_2.png/image-size:267×16
pm03_4.png/image-size:303×16
2つの式を注意して見ると、式③の中のpm03_7.png/image-size:180×15は、式①の左辺と全く同じであることがわかります。つまり式③のpm03_7.png/image-size:180×15は、"C"で置き換えることが可能です。つまり式③を変形し、

 C⊕C=T

とすることができます。

bエ:C⊕C=T

cについて〕
受信したデータ"1001001101"に対して、マスク101を使い符号を計算します。
pm03_8.png/image-size:350×364
計算結果の符号は"01"になり、誤りがない場合の計算結果「すべてのビットが0」ではないので、この受信したデータには誤りが含まれると判断することができます。

cア:誤りが含まれる

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

問1 問2 問3 問4 問5 問6 問7 問8 問9 問10 問11 問12 問13 採点講評
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop