МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ Національний університет “Львівська політехніка” Кафедра “Телекомунікації”
Лабораторна робота № 3 ДОСЛІДЖЕННЯ КОДІВ ХЕМІНГА Львів 2010 Мета роботи Дослідити процес виправлення однократних незалежних помилок систематичними кодами на прикладі досконалого коду Хемінга та ефекти розмноження помилок вищої кратності. Теоретична частина. Одним з найбільш поширених систематичних кодів є код Хемінга. Відомо декілька різновидностей цих кодів, що характеризуються різними коректуючими здатностями. До них кодів звичайно відносяться коди з мінімальною кодовою відстанню dmin=3, які виправляють всі одиночні помилки, і коди з відстанню dmin=4, які виправляють всі одиночні і виявляють всі подвійні помилки, або ж виявляють всі потрійні помилки. Код Хемінга є одним з небагатьох досконалих кодів, для яких виконується ідеальне співвідношення між довжиною коду п та кількістю перевірочних r або інформаційних к розрядів, що випливає з виразу (1) для границі Хемінга: п(2 r-1 (1) Досконалий код Хемінга має кодову відстань dmin=3 і відповідає випадку, коли досягається крайнє значення границі Хемінга: n=2 r-1. Коди Хемінга відносяться до швидких кодів. Характерною особливістю матриці перевірки Н коду з dmin=3 є те, що її стовбці представляють собою будь-які ненульові комбінації довжиною r. Отже ми, наприклад, можемо отримати матрицю Н для коду (15, 11), з r=4 i n=15, записавши у двійковому вигляді всі числа від 1 до (2 r-1)=15 у вигляді стовбчиків матриці: Н15,11=
(2) Розширений код Хемінга має кодову відстань dmin=4 і може бути отриманий з досконалого коду Хеммінга шляхом додавання до нього перевірочного розряду, що є результатом суми по модулю два всіх символів кодової комбінації. Це код виду (2 r-1, 2 r-1-r), n ( 2 r-1. Кодування виконується в два етапи: -визначаєтся КК з використанням матриці H що відповідає досконалому коду Хеммінга; - додається ще один розряд, що дорівнює сумі по модулю два всіх розрядів КК, отриманої на першому етапі. Матриця Н розширеного коду Хемінга буде мати вигляд (тобто (3) доповнена справа нулями, а знизу - одиницями): H=
Декодування: -обчислюється синдром, який відповідає досконалому коду Хеммінга; -перевіряється останнє перевірочне співвідношення. Розрахункове завдання 1. Розрахувати імовірність невиявленої помилки для досконалих кодів Хемінга (7,4) та (15,11), що виправляють однократні помилки, для p0 = 0.1; 0.025; 0.01; 0.002. 2. Розрахувати імовірність невиявленої помилки для досконалого коду Хемінга (7,4), що виявляє помилки, для p0 = 0.1; 0.025; 0.01; 0.002.
Хід роботи Створюю пустий файл розміром 256 байт і закодовую його кодом Хемінга.

Запустив модель телекомунікаційної системи зв’язку і передав закодований файл через канал з незалежними помилками для р0=0,01
Отриманий спотворений файл декодую за допомогою програми-декодера
Повторюю п.п. 2 - 3 для різних значень p0 = 0.002; 0.008.

Після декодування:

Підрахувюю кількість спотворених блоків та обчисляю імовірність невиявленої помилки для декодованого файлу. p0 = 0.01 Р= 2 / 256 = 0.0058 p0 = 0.008 Р= 1 / 256 = 0.0035 p0 = 0.002 Р= 0 / 256 = 0 Висновок: При передачі файлу закодованого кодом Хемінга із різним значенням імовірності помилки, я теоретично вирахував імовірність невиявленої помилки для досконалого коду Хемінга (7,4). Порівнюючи їх із результатами моделювання можна сказати, що обидва способи є досить близькі, а це свідчить про високу точність розрахунків.