Границя Хемінга/Глибина:Використання для двійкового коду

Теорія інформації та кодування/Границя Хемінга

Границя Хемінга дозволяє обчислити кількість додаткових перевірних розрядів для двійкового коду, що виправляє помилки. Введемо позначення:

$k$ — кількість інформаційних символів

$r$ — кількість перевірних

$n=k+r$ — довжина результуючого блокового коду.

$\ t$ — кількість помилок, яку потрібно виправити

Тоді межа Хемінга формулюється як:

$A_{q}(n,\;d_{min})\leqslant {\frac {q^{n}}{\displaystyle \sum _{k=0}^{t}{\textbf {C}}_{n}^{k}(q-1)^{k}}}$

Формулу можна спростити, якщо знати наступне:

$A_{q}(n,\;d_{min})$ — це кількість символів в алфавіті, тобто, потужність коду

$q$ — основа коду. Для двійкового коду $q=2$

Візьмемо $t=1$

$A_{2}(n,\;d_{min})\leqslant {\frac {2^{n}}{C_{n}^{0}+C_{n}^{1}}}={\frac {2^{n}}{1+n}}$

Кількість символів у алфавіті (кодових слів) співпадає з кількістю комбінацій інформаційних повідомлень (адже кожному кодовому слову ставиться у відповідність тільки одне повідомлення). А цю величину розрахувати просто:

$A_{2}(n,\;d_{min})=2^{k}$

Почнемо математичний ланцюжок:

$2^{k}\leqslant {\frac {2^{n}}{1+n}}$

$1+n\leqslant {\frac {2^{n}}{2^{k}}}=2^{n-k}=2^{r}$

$k+r\leqslant 2^{r}-1$

Рішення даної нерівності відносно $r$ дає нам нижню межу для кількості перевірних розрядів блокового коду.

Додаток

При $t=2$ ми отримаємо наступну формулу:

$A_{2}(n,\;d_{min})\leqslant {\frac {2^{n}}{C_{n}^{0}+C_{n}^{1}+C_{n}^{2}}}={\frac {2^{n}}{1+n+{\frac {n(n-1)}{2}}}}={\frac {2^{n+1}}{n^{2}+n+2}}$

$2^{k}\leqslant {\frac {2^{n+1}}{n^{2}+n+2}}$

$n^{2}+n+2\leqslant 2^{r+1}$, де $n=k+r$