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

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

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

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

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

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

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

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

$A_q(n,d_{min})⩽\frac{q^n}{\sum _{k=0}^t{\mathbf{\text{C}}}_n^k(q-1{)}^k}$

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

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

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

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

$A_2(n,d_{min})⩽\frac{2^n}{C_n^0+C_n^1}=\frac{2^n}{1+n}$

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

$A_2(n,d_{min})=2^k$

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

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

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

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

Додаток

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

$A_2(n,d_{min})⩽\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⩽\frac{2^{n+1}}{n^2+n+2}$