応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。
カテゴリ:

1.基礎理論 > 1.8 通信に関する理論

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

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


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

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

解答群
ア 100    イ 102    ウ 120    エ 125
正解は、エです。

設問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-FE問3-1

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

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

解答群
ア 00    イ 01    ウ 10    エ 11
正解は、イです。

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

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

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

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

〔手順〕
(1)符号計算対象のビット列を一つの数値Dと見ると,符号Cは次の式で表せる。
22-FE問3-2
(2)〔誤りの有無の検査手順〕で得られた結果の右端nビットの値Tは,次の式で表せる。
22-FE問3-3

(3)式△鯤儼舛垢襪伴,亮阿箸覆襦
22-FE問3-4

(4)式,伴悪によって,
    [  b  ]=T
となる。

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

aに関する解答群
ア すべてのビットが0  
イ すべてのビットが1
ウ 符号と同じ
エ 符号の各ビットを反転させたものと同じ

bに関する解答群
22-FE問3-5

cに関する解答群
ア 誤りが含まれる
イ 誤りは含まれない
ウ 誤りが含まれるか否かは判断できない
正解は、
a ア
b エ
c ア です。

過去問(H25春AP午前問4)ではハミング符号に関して、「ハミング符号とは,データに冗長ビットを付加して,1ビットの誤りを訂正できるようにしたものである。」とあります。ポイントは、どのビットが間違っているかまで検出できるので、データ誤りを訂正できることです。

過去問(H25春AP午前問4)を見てみましょう。
問4 ハミング符号とは,データに冗長ビットを付加して,1ビットの誤りを訂正できる
haming
ハミング符号1110011には1ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。

ア 0110011  イ 1010011  ウ 1100011  エ 1110111
今回は1ビット誤りなので、X1〜X4のどれかに誤りがあります。
問題文と照らし合わせ、X1X2X3P3X4P2P1=1110011 として、3つの式に入れてみましょう。

1※1※0※1=1
1※1※0※1=1
1※1※1※0=1  ※は排他的論理和(表記の関係で)

ということで、本来は0になるべき値が、全て1に変わっています。
全ての式にX1が入っているので、X1が誤りということが分かります。
よって、X1を0に置き換えた0110011(選択肢ア)が正解です。
ネットワークスペシャリストを目指す女性SEあれ?

それ以外のビットは変更無しですか?




はい。1ビットの誤りですし、実際、X1を0にすることで、付加ビットの3つの式も全て満たします。


以下の過去問(H17NW午前問32)にもハミング符号を理解する問題があります。

haming2

過去問では、CRCに関して「送信側では、生成多項式を用いて検査対象のデータから検査用のデータを作り、これを検査対象のデータに付けて送信する(H16NW午前問31)」と述べている。

CRCに関して、ここ最近の応用情報技術者試験では、あまり問われていません。
少し前の過去問(H21春AP午前問4)を見てみましょう。
問4 誤り検出方式であるCRCに関する記述として,適切なものはどれか。
ア 検査用のデータは,検査対象のデータを生成多項式で処理して得られる1ピットの値である。
イ 受信側では,付加されてきた検査用のデータで検査対象のデータを割り,余りがなければ送信が正しかったと判断する。
ウ 送信側では,生成多項式を用いて検査対象のデータから検査用のデータを作り,これを検査対象のデータに付けて送信する。
エ 送信側と受信側では,異なる生成多項式が用いられる。

パリティとは
データの誤りを検知するために付与する冗長ビットのことです。
具体例は、次で説明します。

奇数パリティと偶数パリティ
偶数パリティは、1の数が偶数、奇数パリティは奇数になるようにします。
たとえば、
1000という4ビットデータがあった場合、
➀偶数パリティ
1000 ⇒ 10001 最後に1のパリティを付与
奇数パリティ
1000 ⇒ 10000 最後に0のパリティを付与します。

もし、途中で1ビットのデータ誤りが発生した場合、上記の偶数パリティが10101になっていれば、1の数が奇数個ですから、データ誤りが発生したことが分かります。しかし、10111というように、2ビットのデータ誤りの場合、1の数が偶数個(つまり正しい)なので、データ誤りを検知できません。
パリティ

垂直パリティと水平パリティ
この下の過去問にありますように、垂直方向か水平方向にチェックするかによって、垂直パリティと水平パリティがあります。
垂直パリティだけですと、1ビットの誤りは検知できますが、どのビットで誤りが発生したかは分かりません。水平パリティと組み合わせることで、どこに誤りが発生したかが分かります。そのビットを反転(0⇒1、1⇒0)させることでデータ誤りの検知だけでなく、訂正まで行うことができます。

過去問(H27秋AP午前問4)を見ましょう。
問4 図のように16ビットのデータを4×4の正方形状に並べ,行と列にパリティビットを付加することによって何ビットまでの誤りを訂正できるか。ここで,図の網掛け部分はパリティビットを表す。
パリティ
ア 1  イ 2  ウ 3  エ 4

過去問(H25春FE午前問4)を見ましょう。
問4 通信回線の伝送誤りに対処するパリティチェック方式(垂直パリティ)の記述として,適切なものはどれか。
ア 1ビットの誤りを検出できる。
イ 1ビットの誤りを訂正でき,2ビットの誤りを検出できる。
ウ 奇数パリティならば1ビットの誤りを検出できるが,偶数パリティでは1ビットの誤りも検出できない。
エ 奇数パリティならば奇数個のビット誤りを,偶数パリティならば偶数個のビット誤りを検出できる。
正解はアです。
1ビットの誤りまでは検知できますが、それ以上の検知や、誤りの訂正はできません。

過去問(H19秋SW午前問7)を見ましょう。
問7 コンピュータの主記憶の誤り制御などに採用されている方式のうち、1 ビット誤りを訂正し,2ビットの誤りを検出することができる方式はどれか。
ア 奇数パリティ方式 
イ 水平パリティ方式 
ウ チェックディジット方式
エ ハミング符号方式
正解は、エのハミング符号です。

データの伝送中に外部からのノイズなどにより、データに誤りが出る可能性があります。
それを検知・訂正するために誤り制御を行います。
誤り制御方式には、.僖螢謄チェック、CRC、ハミング符号、などがあります。

このページのトップヘ