令和元年度(再試験) III-5

解説

この問題で問われていること

最小ハミング距離と誤り訂正・検出能力の関係、符号のレート、ハミング符号の関係式を確認する問題。

解き方

① 最小ハミング距離 d の符号: 検出できるのは d−1 ビット、訂正できるのは ⌊(d−1)/2⌋ ビット(t ビット訂正には d≧2t+1)。符号化率は k/n
② ①k/dではなくk/n、②n=2^(n−k)−1、③d≧t+1は検出の条件、④0000と0011の距離は2なので最小距離は2
③ ⑤

正解が正しい理由

最小ハミング距離がdの符号では、⌊(d−1)/2⌋ビット以内の誤りを訂正でき、d−1ビット以内の誤りを検出できる。したがって⑤が最も適切である。

各選択肢について

• ① (n,k)線形符号のレート(符号化率)は、k/nで求められる(k/dではない)。
• ② (n,k)ハミング符号では、n=2^(n−k)−1という関係がある。「−1」が抜けており、記述は誤り。
• ③ tビットの誤りを訂正できるためには、d≥2t+1を満たす必要がある。d≥t+1は、tビットの誤り検出(d≥t+1)の条件。
• ④ 符号語0000、0011、1100、1111のうち、0000と0011の距離は2、0011と1100の距離は4、0000と1100の距離は2。最小ハミング距離は2で、4ではない。
• ⑤ 最小ハミング距離がdなら、⌊(d−1)/2⌋ビット以内の誤りを訂正できる。これが正答。

覚えるべきポイント

最小ハミング距離d: 検出できる誤り=d−1ビット、訂正できる誤り=⌊(d−1)/2⌋ビット。訂正にはd≥2t+1が必要。符号化率はk/n。