Розділ 11  КОД ХЕММІНГА

 

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

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

 

.                                                    (3.9)

 

З цієї нерівності випливає мінімальне співвідношення перевірних і інформаційних розрядів, необхідне для виправлення кодом поодиноких помилок

 

.                                               (3.10)

 

Для розрахунку основних параметрів коду Хеммінга можна задатися кількістю перевірних елементів r, тоді довжина кодових слів , а кількість інформаційних елементів k=n-r. Співвідношення між r, n і k зручно подати у вигляді такої таблиці (табл. 3.3).

Таблиця 3.3

k              1              1              2              3              4              4              5              6              7              8              9              10            11            11            12

r              2              3              3              3              3              4              4              4              4              4              4              4              4              5              5

n              3              4              5              6              7              8              9              10            11            12            13            14            15            16            17

 

Характерною властивістю перевірної матриці лінійного блокового коду з dmin=3 є те, що її стовпці являють собою різні ненульові комбінації завдовжки r.

Хеммінгом запропоновано розміщувати стовпці перевірної матриці так, щоб i-й стовпець матриці, що відповідає номеру i помилкового розряду кодової комбінації, був двійковим поданням цього номера. Тоді синдром виправлення однократних помилок кодом Хеммінга є двійковим поданням номера розряду, в якому виникла помилка. Для цього перевірні розряди, що відповідають стовпцям одиничної підматриці перевірної матриці коду, повинні знаходитися не в правій частині кодового слова, а у позиціях з номерами степеня двійки, тобто 20, 21, 22,…,.

Наприклад, для r=3 перевірна матриця Хеммінга має вигляд

.

Для даного лінійного блокового (4, 7)- коду перший, другий, четвертий розряди (u1, u2, u4) будуть перевірними, а третій, п'ятий, шостий і сьомий розряди (u3, u5, u6, u7) - символами інформаційного повідомлення у звичайному порядку, тобто (m1, m2 m3, m4) відповідно.

Отже, для (k, n)- коду Хеммінга в кожному кодовому слові u=(u1, u2, u3, u4, …, u8, … un), r = n-k бітів з номерами степеня двійки є перевірними, а інші – бітами повідомлення, тобто кодування здійснюється так:

E(m1, m2, …, mk) =(u1, u2, …, un) =(r1, r2, m1, r3, m2, m3, m4, r4,

m5, m6, …, mk).

Перевірна матриця (k, n)- коду Хеммінга складається із r рядків і  стовпців, що є двійковими комбінаціями числа i, де i - номер стовпця. Наприклад, для r = 2, 3, 4 перевірні матриці коду Хеммінга мають вигляд

;                              ;

                               .

Синдром, що визначає систему перевірних рівнянь коду, знаходиться із рівняння

u=0.

Наприклад, для r = 3 система перевірних рівнянь буде така:

 

Звідси визначають перевірні розряди (контрольні суми)

 

Щоб закодувати повідомлення m u, значеннями розрядів ui, де i не дорівнює степеню двійки, будуть відповідні біти повідомлення у тому самому порядку, а перевірні розряди з індексами степеня двійки знаходяться з системи перевірних рівнянь. У кожне рівняння системи входить тільки одна контрольна сума.

Приклад 1  Закодуємо повідомлення m=(0111) (4, 7)-кодом Хеммінга.

Кодовим словом для заданого повідомлення m буде послідовність u=(u1 u2 0 u4 1 1 1), де u1, u2, u4 - контрольні суми r1, r2, r3 відповідно.

Знаходимо контрольні суми з системи перевірних рівнянь:

r1=u1=u3+u5+u7=m1+m2+m4=0+1+1=0, r2=u2=u3+u6+u7=m1+m3+m4=0+1+1=0, r3=u4=u5+u6+u7=m2+m3+m4=1+1+1=1.

Отже, кодовим словом буде послідовність u=(0001111).

Декодування коду Хеммінга здійснюється у такий спосіб. Обчислюється синдром прийнятої послідовності y:

S=y,

де  - перевірна матриця коду. Якщо синдром нульовий вектор, то вважається, що слово передане без помилок, інакше значення синдрому відповідає двійковому поданню номера помилкового розряду. У цьому випадку потрібно змінити значення помилкового біту, нумеруючи біти зліва направо, починаючи з 1.

Приклад 2  Повідомлення кодується (4, 7)- кодом Хеммінга. Декодуємо прийняту послідовність y=(0011111).

Обчислюємо синдром прийнятого вектора:

y = (0011111)= (011)2 =310 - помилка виникла у 3-му біті.

Виправляємо помилку, змінюючи значення у помилковому біті: (0011111) (0001111).

Передане повідомлення декодується так:

D(u1, u2, u3, u4, u5, u6, u7)=D(0001111)=(0111).

Твірна матриця (k, n)-коду Хеммінга - це матриця (k×n), в якій стовпці з номерами нестепеня 2 утворюють одиничну підматрицю, а решта стовпців визначається з перевірних рівнянь коду. Така матриця при кодуванні копіюватиме біти повідомлення у позиції з номерами нестепеня 2 і заповнюватиме інші позиції коду згідно з перевірним рівнянням знаходження відповідного контрольного розряду.

Приклад 3  Система перевірних рівнянь (4, 7)- коду Хеммінга має вигляд:

r1= u1 = u3+u5+u7 = m1+m2+m4,

r2= u2 = u3+u6+u7 = m1+m3+m4,

r3= u4 = u5+u6+u7 = m2+m3+m4.

Відповідно твірна матриця даного коду така:

.