МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ДОСЛІДЖЕННЯ КОДОУТВОРЕННЯ ТА ПРИНЦИПІВ ПОБУДОВИ КОДЕРІВ І ДЕКОДЕРІВ КОДІВ ХЕМІНГА МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи № 4 з курсу "Засоби передавання, приймання та обробки інформації в системах технічного захисту інформації" для студентів спеціальності 125 «Кібербезпека» Львів 2018 Мета роботи – вивчити принципи побудови кодів Хемінга та одержати практичні навики розробки функціональних схем кодерів і декодерів. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ Простота реалізації та ефективне забезпечення завадостійкості зумовили широке застосування коду Хемінга (КХ) не лише у телемеханіці, але і в обчислювальній техніці та зв’язку. Відомі декілька різновидностей КХ, які характеризуються різною коректуючою здатністю [1, 2]. Код Хемінга з d = 3 забезпечує виявлення двократних (r = 2) або виправлення однократної (S = 1) помилки, оскільки d = r + 1 або d = 2S + 1. Вихідним для коду Хемінга є первинний (двійковий або двійково-десятковий)
-розрядний код, до якого в результаті вторинного кодування додають
контрольних розрядів. Отже, загальна довжина кодової комбінації (КК) збільшиться до
. Кількість робочих комбінацій
. Число контрольних розрядів знаходять із виразу [2, 3]:
(1) В табл. 1 наведені значення п і
, для різних
, що задовольняють умову (1). Таблиця 1
3 4 5 6 7 8  п 7 15 31 63 127 255  
4 11 26 57 120 247   Оскільки при збільшенні кількості інформаційних розрядів
, кількість контрольних розрядів
зростає незначно, надлишковість коду,
(2) зменшується, а швидкість передачі інформації
(3) зростає. Побудова коду Хемінга, що виправляє всі одиничні помилки (d = 3) здійснюється так. Спочатку визначають необхідну кількість контрольних розрядів на підставі співвідношення (1). Далі визначають їх розташування в кодовій комбінації. Для спрощення кодування і декодування контрольні символи розташовують на місцях КК, кратних степеню 2, тобто на позиціях 1, 2, 4, 8, 16 і т.д., хоча їх розташування може бути довільним. Інформаційні розряди розташовуються на вільних місцях. На основі зазначеного для 15-розрядної кодової комбінації можна записати:
де І3 перший (молодший), а І15 одинадцятий (старший) розряд робочої (інформаційної) КК. У циклічному коді Хемінга контрольні символи розташовуються після інформаційних розрядів [4]. Потім знаходять значення контрольних символів (0 або 1) підсумовуючи за модулем два (перевірка на парність) значення певних інформаційних розрядів за алгоритмом Хемінга так:
. (4)
; (5)
; (6)
; (7) Щоб виключити необхідність багатократного використання цих рівнянь для визначення контрольних символів, для кожної із
робочих КК застосовують так звану утворюючу матрицю. Утворююча матриця коду Хемінга (n, ni) складається із одиничної матриці
рангу
та приписної (додаткової) матриці
кількість стовпців якої
, а кількість рядків –
. Для 15-бітного КХ утворююча матриця С15, 11 має вигляд:
(8) Неважко помітити – контрольні розряди мають таке значення, що утворене ними двійкове число еквівалентне номерові позиції на якій знаходиться «1» у відповідному рядку одиничної матриці. Оскільки код Хемінга належить до систематичних (лінійних) кодів, то, додавши за модулем два рядки матриці в різних сполученнях, можна одержати решту
дозволених КК, за винятком нульової. Із наведеної матриці С15, 11 можна одержати утворюючі матриці КХ меншої довжини п. Наприклад, для коду Хемінга (7, 4) матриця С7, 4 має вигляд, позначений на матриці (8) п...