10.5  Вага і відстань Хеммінга. Можливості лінійних кодів виявляти і виправляти помилки

 

Нехай u=(u1, u2, …, un) - двійкова послідовність завдовжки n.

Число одиниць в цій послідовності називається вагою Хеммінга двійкового вектора u і позначається w(u).

Наприклад: u=(1001011), тоді w(u)=4.

Нехай u і v - двійкові слова завдовжки n.

Число розрядів, в яких ці слова відрізняються, називається відстанню Хеммінга між u і v і позначається d(u, v).

Наприклад: u=(1001011), v=(0100011), тоді d(u, v)=3.

Легко бачити, що відстань між двійковими послідовностями u і v однакової довжини дорівнює вазі їх порозрядної суми, тобто

d(u, v)=(u+v).

Тоді ймовірність того, що слово v буде взяте за u

Рпом=рn-d(u, v) qd(u, v),

де p - ймовірність правильної передачі біта повідомлення; q=1-p - ймовірність помилки.

Визначив лінійний блоковий код, тобто задав всі його 2k кодових слів, можна знайти відстані між всіма можливими парами кодових слів, мінімальна з них називається мінімальною кодовою відстанню Хеммінга dmin.

Не складно довести, що відстань між нульовим кодовим словом і одним із кодових слів, що входять до твірної матриці коду, дорівнює dmin (за визначенням рядки твірної матриці лінійного блокового коду самі є кодовими словами).

Тоді мінімальна кодова відстань dmin коду дорівнює мінімальній вазі Хеммінга для всіх рядків твірної матриці.

Для забезпечення можливості виявлення помилки в одній позиції мінімальна кодова відстань між кодовими словами повинна бути більше 1, інакше помилка в одній позиції може перевести одне кодове слово в інше, що не дасть її виявити.

Для виявлення кодом помилок кратності не більше l необхідно і достатньо, щоб мінімальна відстань між його словами була l+1:

dmin ≥ l+1.                                                            (3.4)

Для виправлення кодом помилок кратності не більше l необхідно і достатньо, щоб мінімальна відстань між його словами була 2l+1:

dmin ≥ 2l+1.                                                          (3.5)

Для лінійного блокового (k, n)-коду, мінімальна відстань між кодовими словами якого dmin=2l+1, де l - кратність помилок, що виявляються кодом, кількість перевірних розрядів r=n-k визначається нерівністю

 

,                               (3.6)

 

що називається нижньою границею Хеммінга.

Крім того, якщо параметри n, r і l відповідають нерівності

 

,                 (3.7)

 

що називається верхньою границею Варшамова-Гільберта, то існує (n-r, n)-код, що виправляє всі помилки кратності l і менше.

Нижня границя задає необхідні умови існування завадостійкого коду із заданими характеристиками.

Верхня границя задає достатні умови існування завадостійкого коду.

Для лінійних блокових (k, n)- кодів з мінімальною відстанню dmin також існує нижня границя Плоткіна, що встановлює мінімальну кількість перевірних символів r для n ≥ 2dmin-1:

 

.                                              (3.8)

 

Розглядаючи вищевикладене, сформулюємо правила побудови твірної матриці лінійного блокового (k, n)- коду:

1)            кількість початкових кодових комбінацій (число рядків) твірної матриці дорівнює k, тобто кількості інформаційних елементів;

2)            усі кодові комбінації твірної матриці повинні відрізнятися, причому нульова комбінація до їх складу не входить;

3)            усі кодові комбінації твірної матриці лінійно незалежні;

4)            кількість одиниць в кожній кодовій комбінації твірної матриці повинна бути   dmin;

5)            кодова відстань між будь-якою парою кодових слів повинна бути   dmin.

Таким чином, твірна матриця лінійного систематичного блокового коду складається з двох підматриць: інформаційної підматриці Ik×k (яку зручно подавати у вигляді одиничної матриці) і перевірної підматриці Рkr.

Перевірна підматриця Pk(n-k) визначається підбором r-розрядних комбінацій з кількістю одиниць у рядку ≥ dmin-1 і кодовою відстанню між рядками ≥ dmin-2.