カテゴリ:3.コンピュータの基礎理論 > 3.5 誤り制御

 

1.CRC

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

2.CRCの過去問 

CRCに関して、ここ最近の応用情報技術者試験では、あまり問われていません。
(1)H21春AP午前問4

問4 誤り検出方式であるCRCに関する記述として,適切なものはどれか。
ア 検査用のデータは,検査対象のデータを生成多項式で処理して得られる1ピットの値である。
イ 受信側では,付加されてきた検査用のデータで検査対象のデータを割り,余りがなければ送信が正しかったと判断する。
ウ 送信側では,生成多項式を用いて検査対象のデータから検査用のデータを作り,これを検査対象のデータに付けて送信する。
エ 送信側と受信側では,異なる生成多項式が用いられる。




正解:ウ

(2)H22秋FE午後問3

問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ビットの誤りを訂正できるようにしたものである」とあります。ポイントは、どのビットが間違っているかまで検出できるので、データ誤りを訂正できることです。

以下の過去問で言うと、データが「0110」で、それに対するハミング符号が「011」です。これを付与することで、1ビット誤りを検出し、どこが間違っているかもわかります。

CRCとの違い
CRCとハミング符号の違いについて
CRCは、「生成多項式」を使うのが特徴。x3乗+○x2乗+・・・みたいな、xの何次式かの計算式である。
これにより、パリティと違い、複数のビット誤りを検出できる。
ただし、誤りの訂正まではできないので、受信側が送信側にデータの再送を依頼する。
これは、HDLC手順で利用されています。

一方、ハミング符号は、こちらも計算式を用いることはCRCと同じ。
特徴は、受信側で誤りの訂正までできる優れもの。再送しなくていいのは便利。
だが、CRCと違って、1ビット誤りしか分からない。一部のRAIDで使われている。

ハミング符号の過去問
(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つの式も全て満たします。

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


正解は、エのハミング符号です。

(3)H17NW午前問32

haming2

1.誤り制御とは

データを通信相手の送信する際に、通信中のノイズなどにより、データが誤って送られる場合があります。受信側では、その誤りを検知したり、場合によっては訂正するなどの誤り制御をすることで、データの正確性を保ちます。
誤り制御方式には、①パリティビット、②CRC、③ハミング符号、などがあります。 
CRCに関しては、以下
http://sm.seeeko.com/archives/15876760.html

ハミング符号に関しては以下に記載
http://sm.seeeko.com/archives/15877011.html

2.パリティビット

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

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

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

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

3.パリティビットに関する過去問

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



正解:ア

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



正解:ア

↑このページのトップヘ