情報・アルゴリズムのテーマ一覧へ

基礎科目・情報・アルゴリズム

誤り検出と検査数字

よく出る大学

6問H26・H28・R1・R4・R5・R6

パリティビットで分かること、ハミング距離とハミング符号による1ビット訂正、ISBNの検査数字の計算が出ます。

よく出る形

  • パリティビットを1ビット付ける方式で，正しい記述を選ぶ
  • 2つのビット列のハミング距離を数え，7ビットのハミング符号で受信した列から，正しい送信列を求める
  • ISBN（本の番号）の読めない1桁を，検査の式から求める
  • パリティ・ハミング符号・ISBN の3つが交代で出る。同じ型どうしは数字や記述の入れ替えが多い

覚えること

  • 偶数パリティ：1の個数が偶数になるように最後に1ビット付ける
  • パリティは，奇数個のビットの反転は見つけられるが，2ビットなど偶数個の反転は見つけられない。どのビットが反転したかも分からない
  • ハミング距離：同じ長さの2つのビット列で，ちがっている桁の数
  • mod 2 は「2で割った余り」。1の個数が偶数なら 0，奇数なら 1
  • ハミング符号（7ビット）は，情報4ビット X1〜X4 に検査3ビット X5〜X7 を付け，1ビットの誤りなら場所まで分かって直せる
  • ISBN-13：左から1倍・3倍・1倍…と交互に重みを掛けて足すと，合計が10の倍数になる。ISBN-10 は重みが10，9，…，2 で，11 で割る方式（モジュラス11）
  • 符号語どうしのハミング距離の最小値が d の符号は，d − 1 ビットまでの誤りを検出でき，(d − 1) ÷ 2 ビット（小数は切り捨て）までの誤りを訂正できる
  • パリティ1ビット（d ＝ 2）は検出だけ。7ビットのハミング符号（d ＝ 3）は1ビット訂正ができる
  • 水平垂直パリティ：各行と各列にパリティを付ける。1ビットの誤りは，合わない行と列の交わる位置で特定して直せる
  • CRC（巡回冗長検査）：データを決まった式で割った余りを付けて送る。連続した誤り（バースト誤り）の検出に強い。ふつうは見つけたら送り直しを求め，すべての誤りを訂正する方式ではない

解き方

  • ハミング符号では，受け取った X1〜X4 から X5〜X7 を計算し直し，受け取った X5〜X7 と比べる
  • ずれた検査ビットが1つだけなら，その検査ビット自身の誤り
  • 2つ以上ずれていたら，そのすべてに入っている情報ビットが誤り（問題の式で，どの X がどの検査ビットに入っているかを見る）
  • 例：X5＝X2＋X3＋X4，X6＝X1＋X3＋X4，X7＝X1＋X2＋X4 のとき，X5 と X6 だけがずれたら，両方に入り X7 に入らない X3 が誤り
  • ISBN-13 の例：X 以外の重み付き合計が 91 なら，91 ＋ X が10の倍数になる X ＝ 9
  • 読めない桁が3倍の位置なら，X 以外の合計 ＋ 3X が10の倍数になる X を，一の位で考えて探す

ひっかけ

  • 「パリティでどのビットが反転したか特定できる」は誤り
  • ハミング符号の問題では，受信した列をそのまま答えた選択肢や，2ビット以上直した選択肢がまぎれている
  • 読めない桁が3倍の位置なのに，1倍として計算しない
  • CRC は誤りを見つける方式で，どんな誤りでも訂正できるわけではない
このテーマの想定問題を解く

想定問題：1・2・3

このテーマの過去問（このサイトに解説がある 4問）

X で共有LINE で送る

平成に出た同じテーマ（2問）

このサイトにはまだ解説がありません。年度と題だけです。