ビット列のハミング限界とは、符号間の最小ハミング距離が\(d\)である\(n\)桁のビット列の符号において、\(t\)個以下の符号誤りを最小距離復号で誤り訂正するために符号の総数\(M\)が満たすべき以下の条件のことです。
\[M\leq \frac{2^n}{\displaystyle \sum_{k=0}^{t}\binom{n}{k}}\]
ただし、\(t=\left \lfloor \displaystyle \frac{d-1}{2}\right \rfloor\)です。
符号誤りの個数を\(k\)とした場合、\(n\)桁のビット列の符号誤りの組み合わせの数は、\(\displaystyle\binom{n}{k}\)と表せます。
よって、\(t\)個以下の符号誤りの組み合わせの数は、総和を用いて、\(\displaystyle\sum_{k=0}^{t}\binom{n}{k}\)と表せます。\(k=0\)のとき、符号誤りなしです。
1個の符号に対して、\(\displaystyle\sum_{k=0}^{t}\binom{n}{k}\)のパターンのビット列が必要なので、符号の総数を\(M\)とすると、必要なビット列のパターンは、\(M\displaystyle\sum_{k=0}^{t}\binom{n}{k}\)となります。
\(n\)桁のビット列は、\(2^n\)パターンを表現できるため、以下が成り立ちます。
\[M\displaystyle\sum_{k=0}^{t}\binom{n}{k}\leq 2^n\]
両辺を\(\displaystyle\sum_{k=0}^{t}\binom{n}{k}\)で割ります。
\[M\leq \frac{2^n}{\displaystyle \sum_{k=0}^{t}\binom{n}{k}}\]
導出できました。
また、n個の符号誤りを最小距離復号で誤り訂正するために必要な符号間の最小ハミング距離より、\(d=2t+1\)です。
\(t=\displaystyle\frac{d-1}{2}\)と変形します。\(t\)は、\(\displaystyle\frac{d-1}{2}\)以下の整数である必要があるため、フロア関数を用いて、\(t=\left \lfloor \displaystyle \frac{d-1}{2}\right \rfloor\)となります。