基本情報技術者試験「誤り訂正符号」の問題
ある符号の最小ハミング距離が3であるとき、この符号の誤り検出・訂正能力として正しいものはどれか。
ア2ビットの誤りまで自動的に訂正できる
イ誤り検出も訂正も一切できない
ウ1ビットの誤りを訂正でき、2ビットの誤りを検出できる
エ3ビットの誤りを確実に訂正できる
正解
ウ．1ビットの誤りを訂正でき、2ビットの誤りを検出できる
最小ハミング距離d=3の符号は、検出能力 d-1=2ビット、訂正能力 floor((d-1)/2)=1ビットを持つ。よって1ビット訂正・2ビット検出が正しい。
?選択肢ごとの解説
ア ×2ビットまで訂正できるには最小ハミング距離が5以上必要で、d=3では1ビットしか訂正できない。
イ ×検出も訂正もできないのは最小ハミング距離が1の場合であり、d=3では検出も訂正も可能である。
ウ ○最小ハミング距離d=3の符号は、検出能力 d-1=2ビット、訂正能力 floor((d-1)/2)=1ビットを持つ。よって1ビット訂正・2ビット検出が正しい。
エ ×3ビットを確実に訂正するには最小ハミング距離が7以上必要で、d=3では到底足りない。
✎くわしく
最小ハミング距離dと能力の関係は『検出=d-1』『訂正=floor((d-1)/2)』である。距離が大きいほど符号語どうしが離れ、多くの誤りを区別・復元できる。ハミング符号は通常d=3で1ビット訂正を実現する代表例である。
✓本番での押さえどころ
試験のコツ
公式『検出=d-1、訂正=(d-1)/2の切り捨て』を暗記する。d=3なら検出2・訂正1と即答できる。
覚え方
距離3=『誤っても最も近い正しい符号語が1つに定まる範囲が1ビット』。訂正1・検出2、と数直線で覚える。
よくある誤り
検出能力と訂正能力を混同する、(d-1)/2の切り捨てを忘れる誤りが多い。訂正には検出の倍近い距離が要る点を押さえる。
基礎理論の他の問題
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0117