ハミングの限界式

ハミングの限界式

情報語数kと符号長nの関係

kビットの情報語をnビットの符号長に符号化するとき、1ビットの訂正を可能にするにはkとnの間に次の関係が成り立ちます。

$$(1+n)2^k\le 2^n,2^k\le \frac{2^n}{1+n}$$

kビットの情報語をnビットに符号化して伝送路に送信するとき、nの方がkより大きくないと、誤りを訂正するための冗長な情報を符号語に含めることができないことは容易に想像できます。では、「最低限nをどの位の長さにすれば1ビットの訂正が可能になるのか」ということを、この式は示しています。
関係式の左辺のかっこを展開すると次のようになります。
$$(1+n)2^k=(2^k+n{2}^k)\le 2^n$$
これは、$2^k$に$n{2}^k$を加えた数が$2^n$と同じか、または少ない関係になるようなnであれば、1ビットの訂正が可能であることを示しています。
つまり、1ビットの訂正を行うには、正しい(誤りがない)場合の符号語の種類$2^k$に加えて、余分に$n{2}^k$種類の符号語を含むことが可能な大きさにnを設定する必要があるということを意味します。

kとnの例

kが1から8ビットの場合、1ビットの誤り訂正を可能にするために最低限必要な符号nのビット数は、次のようになります。