Кодовий синдром

S = y ´ =(u + e)´ = u ´ + e ´ = 0 + e ´ = e ´ ,

оскільки для будь-якого кодового слова u ´ = 0.

Таким чином, кодовийсиндром залежить лише від вектора помилок і не залежить від переданого слова.

Визначивши координати вектора помилок, можна відновити кодове слово так: u * = y + е.

Приклад 4 Знайдемо значення синдрому для всіх можливих однократних помилок в послідовності з семи символів для наведеного прикладу лінійного блокового (4, 7)- коду.

1) e₀ =(0000000),

е₀ ´ =(0000000) ´ =(000) - помилки немає;

2) е₁ =(1000000),

е₁ ´ =(1000000) ´ =(110) - помилка у 1 -му біті;

3) e₂ =(0100000),

е₂ ´ =(0100000)´ =(011) - помилка у 2 -му біті;

4) е₃ =(0010000),

е₃ ´ =(0010000)´ =(111) - помилка у 3 -му біті;

5) е₄ =(0001000),

е₄ ´ =(0001000)´ =(101) - помилка у 4 -му біті;

6) е₅ =(0000100),

е₅ ´ =(0000100)´ =(100) - помилка у 5 -му біті;

7) е₆ =(0000010),

е₆ ´ =(0000010)´ =(010) - помилка у 6 -му біті;

8) е₇ =(0000001),

е₇ ´ =(0000001)´ =(001) - помилка у 7-му біті.

Існує однозначна відповідність між координатами поодиноких помилок і їх синдромами, тобто, знаючи синдром, можна визначити позицію коду, в якій виникла помилка.

Приклад 5 З перевірної матриці лінійного блокового (4, 7)- коду знайдемо систему перевірних рівнянь:

Звідси

де (m₁, m₂, m₃, m₄) – інформаційні символи; r₁, r₂, r₃ - перевірні символи; (u₁, u₂, …, u₇)= (m₁, m₂, m₃, m₄, r₁, r₂, r₃) - кодове слово.

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

Наприклад, якщо помилка у четвертому розряді кодової комбінації u =(u₁, u₂, u₃, u_{4 ,} u₅, u₆, u₇)=(m₁, m₂, m₃, m₄, r₁, r₂, r₃), то не виконаються перше і третє рівняння, в які входить помилковий символ u₄=m₄. Вектором синдрому буде послідовність S =(101), що збігається з четвертим стовпцем перевірної матриці коду H.

У такий спосіб номер помилкового розряду кодової комбінації є номером стовпця перевірної матриці H, що збігається з вектором синдрому, це дозволяє визначити місце виникнення помилки і таким чином її виправити.

Зазначимо, що кодовий синдром виправляє тільки однократні помилки в коді.

Приклад 6 Припустимо, що в прийнятій послідовності виникла не одна, а дві помилки, наприклад, у другому і шостому бітах: е= (0100010).

Тоді вектор синдрому

S= (0100010) ´ =(001).

Цей синдром збігається з сьомим стовпцем перевірної матриці H, що означає наявність однієї помилки у сьомому біті. Отже, декодер не тільки не виправить помилкові біти, але і внесе помилку у позицію, де її не було.

Отже, лінійний блоковий (4, 7) - код не виправляє двократні помилки і помилки більшої кратності.

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

Нехай u =(u₁, u₂, …, u_n) - двійкова послідовність завдовжки 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)=w(u+v).

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

Р_пом = р^{n - d ( u , v )} q^{d ( u , v )},

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

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

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

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

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

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

d_min ≥ l+ 1. (3.4)

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

d_min ≥ 2 l+ 1. (3.5)

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

, (3.6)

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

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

, (3.7)

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

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

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

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

. (3.8)

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

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

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

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

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

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

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

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

Зразки розв'язування задач до розділу 10

Приклад 1 Лінійний блоковий (4, 7)-код заданий твірною матрицею вигляду

.

Побудувати перевірну матрицю і систему перевірних рівнянь коду. Закодувати комбінації 1010, 1110. Визначити синдром виправлення поодиноких помилок у комбінаціях коду. Використовуючи синдром, визначити й виправити помилку в комбінаціях 1010101, 1000100.