生成多項式で割り切れるかを調べる誤り検査方式の見分け方
基本情報技術者試験 平成29年度秋期 午前 問2 ／ 基礎理論 › 通信に関する理論
過去問にチャレンジ
送信側では，ビット列をある生成多項式で割った余りをそのビット列に付加して送信し，受信側では，受信したビット列が同じ生成多項式で割り切れるか否かで誤りの発生を判断する誤り検査方式はどれか。
- ア
CRC方式
- イ
垂直パリティチェック方式
- ウ
水平パリティチェック方式
- エ
ハミング符号方式
会話形式の解説
講師今回は誤り検査方式の見分けです。問題文にある「生成多項式」と「割り切れるか否か」という二つの言葉に注目してください。
受験者選択肢はどれも誤りを調べる方式なので、私はどれも似て見えてしまいます。何を基準に分ければよいですか。
講師それぞれの方式が誤りを調べるときに何をしているか、つまり多項式の割り算を使うかどうかで分けると一つに絞れます。まずCRC方式から確かめましょう。CRCは巡回冗長検査のことです。
受験者CRCは、送る側がビット列を生成多項式で割って、その余りを付けて送る方式でしたか。
講師そのとおりです。付けた余りが検査用のビットになります。受信側は受け取ったビット列を同じ生成多項式で割り、割り切れなければ途中で誤りが起きたと判断します。問題文の手順とそのまま一致しますね。
受験者パリティチェックも検査用のビットを付けるので、そこで迷いそうです。垂直と水平で何か違いがありますか。
講師パリティチェックは、1の個数が偶数か奇数かで誤りを調べる方式です。垂直パリティは文字ごとに、水平パリティは複数の文字をまとめたブロックで同じビット位置ごとにパリティビットを付けます。向きが違うだけで、どちらも偶奇を数えるだけなので割り算は使いません。
受験者では、ハミング符号はどうでしょうか。検査ビットを複数使うと聞いたので、割り算に近いことをしているのかと思っていました。
講師ハミング符号は、複数の検査ビットを組み合わせて誤りのあるビットの位置を突き止め、1ビットの誤りなら訂正できる方式です。位置を特定する仕組みであって、多項式で割った余りを見る方式ではありません。
受験者整理すると、多項式で割って余りを見るのがCRC、1の個数の偶奇を見るのがパリティ、誤りの位置を特定して訂正するのがハミング符号、ということですね。
講師よく整理できています。補足すると、CRCは単純なパリティでは見逃してしまう偶数個のビット誤りや、連続して起きるバースト誤りも検出できます。付ける検査ビットの長さは生成多項式の次数で決まります。
講師よくある引っかけは、検出と訂正の取り違えです。CRCは主に検出のための方式で、単独では訂正しません。「訂正できる方式はどれか」と問われたらハミング符号になるので、問題文がどちらを聞いているかを必ず読み分けてください。
まとめ
この問題は、送信側が生成多項式で割った余りを付けて送り、受信側が同じ多項式で割り切れるかで誤りを判定する方式を問うもので、答えはCRC方式（巡回冗長検査）です。垂直・水平パリティチェックは1の個数の偶奇を調べるだけで、割り算は使いません。ハミング符号は複数の検査ビットで誤りの位置を特定し、1ビットの誤りを訂正できる方式です。CRCは偶数個のビット誤りやバースト誤りも検出できますが、単独では訂正しないので、検出と訂正のどちらを問われているかを読み分けることが大切です。
解答・解説
正解はアです
この問題のテーマ
誤り検査方式のうち、「生成多項式で割った余りを付加し、受信側で割り切れるかを調べる」という仕組みを持つ方式を見分ける問題です。
解き方の考え方
手がかりになるのは、問題文の「生成多項式」と「割り切れるか否か」という語です。送信側は余りを付けたビット列を送り、受信側は同じ多項式で割り直して余りが0かどうかで誤りを判定します。各選択肢について、誤りを調べるときに多項式の除算を使うかどうかを確かめれば、該当する方式は一つに絞れます。
選択肢ごとの解説
- ○ア CRC方式CRC方式（巡回冗長検査）では、送信側がビット列を生成多項式で割った余りを検査用のビットとして付けて送ります。受信側が同じ生成多項式で割り、割り切れなければ途中で誤りが起きたと判断します。この手順は問題文の説明とそのまま一致するので、CRC方式が該当します。
- ×イ 垂直パリティチェック方式垂直パリティチェック方式は、文字ごとにパリティビットを付け、1の個数が偶数か奇数かで誤りを調べます。検査は1の個数を数えるだけで、生成多項式による割り算は使いません。そのため、問題文の方式には当たりません。
- ×ウ 水平パリティチェック方式水平パリティチェック方式は、複数の文字をまとめたブロックで、同じビット位置どうしの1の個数の偶奇を調べます。パリティを付ける向きが垂直パリティと違うだけで、偶奇の検査であることは同じです。余りを求める除算は行わないので、該当しません。
- ×エ ハミング符号方式ハミング符号方式は、複数の検査ビットを組み合わせて誤りのあるビットの位置を特定し、1ビットの誤りなら訂正できる方式です。2ビットの誤りは検出までできます。誤りの位置を突き止める仕組みであり、多項式で割った余りを見る方式ではないので、該当しません。
補足
CRCは、単純なパリティでは見逃してしまう偶数個のビット誤りや、連続して起きるバースト誤りも検出できます。また、付加する検査ビットの長さは生成多項式の次数で決まります。「訂正できる方式はどれか」と問われた場合の答えはハミング符号なので、検出と訂正のどちらを問われているかを読み分けてください。
POINT
- 問題文に「生成多項式」「余り」「割り切れるか」とあれば、CRC方式を指しています。
- パリティチェックは1の個数の偶奇で誤りを調べる方式で、垂直は文字ごと、水平はブロック内の同じビット位置ごとに検査します。
- ハミング符号は誤りの検出だけでなく1ビットの誤りを訂正でき、2ビットの誤りは検出できます。
- CRCは主に誤りを検出するための方式で、単独では誤りを訂正しません。