完全符号

以下は式は複雑になるが、落ち着いて考えればごく当たり前のことなので 落ち着いて考えるように。

• 長さ n ビットのある符号 x において、ハミング距離が e ビット以内の ものは　　　　　個ある。
• 長さ n ビットで、符号語(意味のあるビットパタン)がM種類ある 符号において、e ビットの誤りが訂正可能であるためには、 少なくとも　　　　　個の 符号(ビットパタン)が必要である。
• したがって、長さ n、符号語数 M の符号が e ビットの誤りを訂正 可能なとき
  
  $$2^n\geq$$
  
  
  という不等式が成立する。
• この不等式において、等式が成立する場合を完全符号 (perfect code)という。
• 完全符号には(理論上あきらかに)全く無駄がない。
• 完全符号は多くはない。

完全符号の概念は図1のように示される。 完全符号であればeビット以内の誤りがあったら必ず訂正でき、かつ 無駄がまったくない。図1の右は完全符号では ない例。誤りが発生した結果、斜線部の領域に行ってしまった符号は (誤り検出はできても)訂正ができない。

図 1: 完全符号の概念

問:

• (3, 1)繰り返し符号は完全符号で　　　　。
• (9, 4)2重パリティ符号は完全符号で　　　　。
• (16, 9)2重パリティ符号は完全符号で　　　　。