МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка” Кафедра “Телекомунікації”
/
ДОСЛІДЖЕННЯ КОДІВ ХЕМІНГА
Львів 2017
Мета роботи
Дослідити процес виправлення однократних незалежних помилок систематичними кодами на прикладі досконалого коду Хемінга та ефекти розмноження помилок вищої кратності.
Теоретична частина.
Одним з найбільш поширених систематичних кодів є код Хемінга. Відомо декілька різновидностей цих кодів, що характеризуються різними коректуючими здатностями. До них кодів звичайно відносяться коди з мінімальною кодовою відстанню dmin=3, які виправляють всі одиночні помилки, і коди з відстанню dmin=4, які виправляють всі одиночні і виявляють всі подвійні помилки, або ж виявляють всі потрійні помилки.
Код Хемінга є одним з небагатьох досконалих кодів, для яких виконується ідеальне співвідношення між довжиною коду п та кількістю перевірочних r або інформаційних к розрядів, що випливає з виразу (1) для границі Хемінга:
п≤2 r-1 (1)
Досконалий код Хемінга має кодову відстань dmin=3 і відповідає випадку, коли досягається крайнє значення границі Хемінга: n=2 r-1.
Отже, його параметри
(n, k) = (2 r-1, 2 r-1-r),’
де r=2, 3,... - кількість перевірочних розрядів.
В табл.1 наведені параметри деяких кодів Хеммінга.
Коди Хемінга відносяться до швидких кодів.
Характерною особливістю матриці перевірки Н коду з dmin=3 є те, що її стовбці представляють собою будь-які ненульові комбінації довжиною r. Отже ми, наприклад, можемо отримати матрицю Н для коду (15, 11), з r=4 i n=15, записавши у двійковому вигляді всі числа від 1 до (2 r-1)=15 у вигляді стовбчиків матриці:
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
Н15,11= (2)
1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1
Перестановкою стовбців, що містять одну одиницю, дану матрицю можна звести до канонічної форми:
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0
1 1 1 0 0 0 1 1 1 1 0 1 0 0
Н15,11= (3)
0 1 1 0 1 1 0 0 1 1 0 0 1 0
1 1 0 1 1 0 1 0 1 0 1 0 0 0 1
Кодування
Знаючи матрицю Н, легко побудувати матрицю G і всі її робочі кодові комбінації.
Декодування
Отримавши кодову комбінацію (КК), ми обчислюємо синдром і дивимось, з яким стовбцем матриці він співпадає:
якщо синдром рівний нулеві, прийнята КК вважається правильною і з неї видаляємо перевірочні розряди;
якщо синдром не нульовий, тоді знаходимо номер стовбчика матриці Н, що рівний синдромові, і виправляємо помилку у розряді прийнятої КК, що має цей же номер, або робимо висновок, що прийнята КК - помилкова.
Хемінг запропонував використовувати матрицю Н не в канонічному вигляді (3), а у вигляді (2) -номер стовбчика у двійковому вигляді співпадає з елементами у цьому ж стовбчику.
Тоді перевірочні розряди КК повинні знаходитись не в кінці КК, а на номерах позицій, що відповідають степені 2: 20, 21, 22,..., 2 r-1.
У цьому випадку синдром, отриманий з прийнятої КК, буде двійковим номером розряда КК, у якому виникла помилка, що значно полегшує процес декодування.
Наприклад, для матриці (2) перевірочними будуть 1, 2, 4 та 8 розряди, а інформаційними - 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15. Повідомлення 11010101011 після кодування матиме вигляд 011110100101011. Якщо помилка виникла в 7-ому розряді, тоді прийнята КК буде 01110000101011 синдром, після підрахунку, буде мати вигляд 0111, тобто 710. Отже, помилка виникла в 7-у розряді.
Таблиця 1. Параметри кодів Хеммінга
k
r
n
R=r/n
d
k
r
n
R=r/n
d
4
3
7
0.429
3
4
4
8
0.5
4
11
4
15
0.267
3
11
5
16
0.312
4
26
5
31
0.161
3
26
6
32
0.188
4
57
6
63
0.095
3
57
7
64
0.109
4
120
7
127
0.055
3
120
8
128
0.063
4
247
8
255
0.031
3
247
9
256
0.035
4
502
9
511
0.0177
3
502
10
512
0.0195
4
1013
10
1023
0.0098
3
1013
11
1024
0.0107
4
Розширений код Хемінга має кодову відстань dmin=4 і може бути отриманий з досконалого коду Хеммінга шляхом додавання до нього перевірочного розряду, що є результатом су...
