МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ДОСЛІДЖЕННЯ КОДОУТВОРЕННЯ ТА ПРИНЦИПІВ ПОБУДОВИ
КОДЕРІВ І ДЕКОДЕРІВ КОДІВ ХЕМІНГА
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 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) пунктиром. Для КХ більшої значності п кількість рядків і стовпців має бути відповідно збільшена.
Отже, первинний код перетворюють в код Хемінга формуванням мінімальної групи контрольних розрядів, кожен із яких у своїй групі набуває значення, що забезпечує парну кількість одиниць. Ця особливість використовується при декодуванні КХ. Для цього із прийнятих кодових комбінацій формуються контрольні суми S1, S2, S4, S8 відповідно до алгоритмів (4) – (7)
,
,
,
.
Двійкове число S8, S4, S2, S1 називається синдромом помилок і використовується для їх розпізнавання. Очевидно, що прийнята КК може вважатися правильною лише при S1 = S2 = S4 = S8 = 0. Якщо ж вага синдрому відрізняється від нуля, то КК вважається неправильною і підлягає корекції. Виправлення помилково прийнятого розряду здійснюється за виглядом синдрому, який не залежить від вигляду кодової комбінації, а визначається лише місцезнаходженням спотвореного розряду. Отже, кожному помилковому розряду або відповідає тільки один синдром. Вигляд синдрому може бути визначений за допомогою перевірочної матриці , яка будується на підставі утворюючої і є транспонованою прописаною матрицею , що доповнена одиничною матрицею контрольних розрядів . Перевірочна матриця H15, 11 коду Хемінга (15, 11) має вигляд
(10)
Із перевірочної матриці можна визначити, які розряди беруть участь у формуванні контрольних сум Si, а також вигляд синдромів для кожної позиції. Стовпці перевірочної матриці визначають синдроми помилки для розряду, номер якого відповідає номерові стовпця. Якщо, наприклад, замість переданої кодової комбінації 110000000000001, в якій чотири останні розряди є контрольними, була прийнята КК 100000000000001, то після обчислення S1, S2, S4, і S8 буде визначений синдром S = 1110. Із матриці H15, 11 випливає, що спотвореним є 14-й розряд і для виправлення він має бути проінвертований.
Рис. 1. Схема кодера і декодера (а), та часткові діаграми роботи (б)
На рис. 1 наведені найпростіші схеми кодера і декодера для коду Хемінга (7, 4). Для формування контрольних розрядів в кодері використовуються паралельні суматори за модулем два. У декодері для визначення контрольних сум також використовуються паралельні суматори. За допомогою дешифратора двійковий код синдрому помилки перетворюється в позиційний. Виправляють помилки двовходовими суматорами за модулем два. У випадку передачі інформації не паралельним, а послідовним кодом, як суматори за модулем два можуть бути використані лічильні Т-тригери.
Для кодування і декодування кодів Хемінга розроблена спеціалізована ВІС К555 ВЖІ, за допомогою якої можна сформувати код Хемінга (22,16). Інформація про мікросхему К555 ВЖІ наведена далі.
Розширений код Хемінга (d = 4) будується на основі КХ з d = 3, але передбачає використання додаткового контрольного розряду К0, який визначається сумуванням за модулем два всіх інформаційних , та контрольних розрядів. Отже, утворююча матриця коду Хемінга (8, 4) має вигляд:
Операція декодування коду Хемінга d=4 складається із двох етапів. На першому визначається синдром для КХ з d = 3, а на другому контрольна сума S0 у результаті додавання за модулем два всіх без винятку розрядів кодової комбінації. При цьому можливі такі випадки:
1) Si = 0, S0 = 0 – помилки в КК нема,
2) Si 0, S0 = 1 – одинична помилка,
3) Si 0, S0 = 0 – подвійна помилка,
4) Si = 0, S0 = 1 – потрійна помилка або помилка вищої непарної кратності.
На основі цієї закономірності можна синтезувати логічну схему, яка дасть змогу зчитувати прийняту інформацію із регістра оперативної пам’яті в регістр тривалої пам’яті без корекції або з попередньою корекцією одиничної помилки у двох перших випадках або ж забороняє зчитування і вмикає індикатор наявності помилок у двох останніх випадках.
При використанні лише одного контрольного розряду К0 і однієї контрольної суми S0 забезпечується кодова віддаль d=2, тобто код Хемінга вироджується у код із захистом за парністю.
Для кодів Хемінга з d > 4, які виправляють подвійні помилки і помилки більшої кратності (S 2), одержання синдромів складніше, оскільки вигляд синдрому має однозначно показати на одночасні помилки в S розрядах у різних сполученнях . Тому синдроми беруть із спеціальних таблиць, одержаних за допомогою ЕОМ [3]. Кодер в цьому випадку доцільно побудувати на основі ПЗП, на вхід якого подається -розрядний безнадлишковий код, а з виходу знімається - розрядний код із заданою d.
Значно простіший спосіб збільшення кодової віддалі майже вдвічі полягає у заміні двійкового коду квазітрійковим без зміни алгоритмів кодування і декодування КХ [4]. Для квазітрійкового кодування достатньо послідовний код Хемінга з d=3 або d=4 пропустити через дискретний модулятор, який забезпечує формування двох імпульсних ознак для передачі «1» і «0», наприклад, відеоімпульсів додатної та від’ємної полярності, в результаті чого на лінію зв’язку подається біполярна-послідовність імпульсів. Один із варіантів реалізації такого дискретного модулятора і часові діаграми його вхідних та вихідних сигналів наведені на рис. 2.
Декодування квазітрійкових кодів передбачає формування із прийнятої біполярної імпульсної послідовності двох КК двійкового коду, кожна із яких містить елементи кодової посилки лише з однією імпульсною ознакою. Далі необхідно декодувати кожну із одержаних кодових комбінацій одночасно і незалежно одну від одної за розглянутими вище алгоритмами декодування КХ, а одержані синдроми використати для остаточного формування прийнятої інформації. Завдяки цьому при передачі інформації з d = 3 у приймачі в кожній виділеній КК можна виявити не більше від двох помилок, тобто загальна кількість помилок подвоюється і буде дорівнювати r = 4, а кодова віддаль d = r + 1 = 5. Аналогічно збільшується до d = 7 кодова віддаль при квазітрійковому кодуванні КХ з d = 4.
Рис. 2. Схема квазітрійкового модулятора (а) та епюри в найважливіших точках (б)
2. МЕТОДИЧНІ ВКАЗІВКИ
Лабораторна робота полягає у дослідженні схеми кодера та декодера ІК шляхом моделювання їх роботи у середовищі LogicWorks 5. Для чого необхідно:
1. Запустити програму LogicWorks (файл LogicWorks.exe).
2. Відкрити файл LR1_Hamming.cct. Це можна зробити через пункт меню File/Open. При цьому в редакторі появиться схема представлена на рис. 3, що здійснює кодування інформаційних розрядів кодом Хемінга Н16, 11 при d = 4 з індикацією інформаційних та контрольних розрядів, подальшу передачу закодованої ІК з можливістю внесення спотворень під час передачі, декодування одержаної матриці та індикацію прийнятих розрядів і синдромів помилок. Структурна схема представлена на рис. 4.
Структурна схема (рис. 4) складається із генератора тактових імпульсів (ГТІ), кодера в складі формувача контрольних розрядів (ФКР), регістра пам’яті (РП) для зберігання коду Хемінга, перетворювача Пр-Пс паралельного коду в послідовний, декодера у складі перетворювача Пс-Пр послідовного коду в паралельний та формувача синдрому (ФС), лічильника імпульсів (ЛІ), під дією якого паралельний код перетворюється в послідовний та навпаки, пристрою внесення спотворень (ПВС), схеми управління (СУ), що забезпечує роботу макета в одному з двох режимів. На панелі передбачені 11 тумблерів для задання інформаційних розрядів, тумблери управління, кнопка обнулення, індикатори переданої та прийнятої кодової комбінації, індикатор рахунку, індикатор синдрому, а також гнізда імітації спотворень.
Рис. 4. Структурна схема кодера-декодера коду Хемінга
До складу схеми входять:
а. 11 перемикачів (І15, І14, І13, І12, І11, І10, І9, І7, І6, І5, І3) та індикаторів для задання значень і відображення інформаційних розрядів;
б. Кодер КХ у складі: формувачів контрольних розрядів (К8, К4, К2, К1, К0) виконаних на суматорах за модулем 2 (XOR), перетворювача паралельного коду в послідовний (Пр-Пс) побудованого на регістрах зсуву REG 1-REG 2;
в. 16 перемикачів (ЕІ15, ЕІ14, ЕІ13, ЕІ12, ЕІ11, ЕІ10, ЕІ9, ЕК8, ЕІ7, ЕІ6, ЕІ5, ЕК4, ЕІ3, ЕК2, ЕК1, ЕК0) для внесення спотворень при передачі. Для того щоб спотворити певний розряд необхідно відповідний перемикач перевести в 1 стан;
г. Пристрій внесення спотворень (ПВС) в розряди передаваної кодової комбінації реалізований на регістрах зсуву REG 3-REG 4 та суматорі за модулем два SUM. ПВС формує сигнали помилок, які, надходячи на суматор за модулем два, інвертують розряди КК, що передається;
д. Декодер КХ у складі: перетворювача послідовного коду в паралельний (Пс-Пр) на регістрах зсуву REG 5-REG 6, індикаторів прийнятої КК (І_15, І_14, І_13, І_12, І_11, І_10, І_9, К_8, І_7, І_6, І_5, К_4, І_3, К_2, К_1, К_0), формувачів та індикаторів синдрому помилки (S8, S4, S2, S1, S0);
е. Генератор тактових імпульсів (ГТІ) та лічильник імпульсів (ЛІ) (на схемі 3 не показаний);
є. Схема управління (СУ) у складі перемикачів SAVE і RES.
3. В початковому стані перемикачі SAVE (ЗАПИС), здійснює запис кодової комбінації в регістри для передачі в послідовному коді), RES (СКИД) знаходяться в положенні 1, всі перемикачі внесення спотворень знаходяться в нульовому стані (спотворення відсутні).
4. Запустити моделювання схеми для чого необхідно вибрати пункт меню Simulation/Run або натиснути лівою клавішею мишки по піктограмі на панелі інструментів.
5. З допомогою перемикачів І15, І14, І13, І12, І11, І10, І9, І7, І6, І5, І3 задати передбачені завданням кодові комбінації в (щоб змінити положення перемикача потрібно навести на нього мишку і натиснути ліву клавішу). Одночасно формуються контрольні розряди К8, К4, К2, К1, К0.
6. Порівняти одержані контрольні розряди з розрахованими при домашній підготовці.
7. Перевести перемикач SAVE в положення 0.
8. Перевести перемикач RES в положення 0.
9. Натиснути лівою клавішею мишки по піктограмі на панелі інструментів. З’явиться меню представлене на рис. 5.
Рис. 5. Меню Simulation Trigger Setup (задання умови закінчення моделювання)
У ньому потрібно вести дані представлені на рис. 5 та натиснути кнопку OK.
10. Перевести спочатку перемикач SAVE, а потім RES в положення 1. Після цього починається моделювання роботи схеми, яке триває 16 тактів сигналу NCLK1. Після 16 такту моделювання автоматично зупиняється, а в регістрах REG 5–REG 6 (рис. 4) буде записана одержана кодова комбінація у двійковому коді. З допомогою індикаторів прийнятих розрядів І_15, І_14, І_13, І_12, І_11, І_10, І_9, К_8, І_7, І_6, І_5, К_4, І_3, К_2, К_1, К_0 порівняти передані та прийняті КК.
11. Порівняти одержаний синдром помилки S8, S4, S2, S1, S0 з розрахованими при домашній підготовці.
12. Одночасно можна спостерігати часові діаграми роботи схеми (рис. 6), які виводяться у вікні Timing Window, що розташоване у нижній частині редактора схем. У разі якщо вікно Timing Window відсутнє, його можна вивести вибравши пункт меню Window/Timing Window.
Рис. 6. Часова діаграма роботи схеми
13. Повторити пункти 1-12 з внесенням відповідних спотворень у КК (див. пункт 6 ЗАВДАННЯ). Для того, щоб спотворити певний розряд необхідно на кроці 5 перевести відповідні перемикачі внесення спотворення (ЕІ15, ЕІ14, ЕІ13, ЕІ12, ЕІ11, ЕІ10, ЕІ9, ЕК8, ЕІ7, ЕІ6, ЕІ5, ЕК4, ЕІ3, ЕК2, ЕК1, ЕК0) у одиничний стан.
3. ЗАВДАННЯ
1. Вивчити основи побудови, відмінності та можливості кодів Хемінга з різною кодовою віддаллю.
2.* Визначити основні параметри коду Хемінга d = 3 (), якщо кількість інформаційних розрядів дорівнює двом останнім цифрам номера залікової книжки (НЗК).
3.* Побудувати утворюючу матрицю КХ (16, 11) і на її основі закодувати число у двійковому та двійково-десятковому кодах, що відповідає трьом останнім цифрам НЗК.
4.* Побудувати перевірочну матрицю КХ (16, 11). Декодувати одну з КК одержаних в п. 3, для випадку, коли спотворень нема, коли вони є в одному, двох і трьох розрядах. Номери спотворюваних розрядів вибирати довільно.
5. Ознайомитися з схемою, передати і прийняти кодові комбінації, одержані в п. 3 без спотворень та із спотвореннями. Порівняти синдроми, які відтворюються індикаторами S0, S1, S2, S4, S8 з результатами, одержаними в п. 4.
6. За допомогою часового вікна замалювати кодові комбінації кожної кодової комбінації, одержаної в п. 4. Дати необхідні пояснення.
7.* Скласти схеми кодера і декодера кодів Хемінга при d = 2, d = 4, d = 5.
8.* Побудувати графіки залежності та для коду Хемінга з d = 3, якщо кількість інформаційних розрядів змінюється від 1 до 250.
4. КОРОТКИЙ ТЕХНІЧНИЙ ОПИС ВІС К555 ВЖІ
К555 ВЖІ – це 16-розрядна схема, яка забезпечує виправлення одиничних та виявлення подвійних помилок за кодом Хемінга. Крім того, вона дає змогу виявляти помилки виду всі «1» або всі «0», а також ряду потрійних і п’ятикратних помилок.
На рис. 7 наведено структурну схему, а на рис. 8 графічне зображення ВІС К555 ВЖІ.
Простота управління мікросхеми К555 ВЖІ обумовлена тим, що є лише два входи управління (S0, S1), при цьому не потрібно застосовувати зовнішні складні пристрої синхронізації. В табл. 2 наведений опис режимів роботи ВІС.
Таблиця 2
РЕЖИМИ РОБОТИ ВІС К555 ВЖІ
Входи
управ-ління
Режим
роботи
Цикл
пам’яті
Характер
інформації на шині ДІ
Характер
інформації
контрольного
слова – Кі/Сі
Ознаки
помилок
0
0
Формування контрольних розрядів
Запис
Вхідні інформаційні розряди (із ЗП)
Вихідні контрольні розряди
Заборонено
1
0
Запис інформаційних і контрольних розрядів із запам’ятовуючого пристрою /ЗП/ в ВІС
Вхідні інформаційні розряди (із ЗП)
Вхідні контрольні
розряди (із ЗП)
Заборонено
1
1
Блокування інформації та дозвіл ознак помилок
Вимкнений стан
Вимкнений стан
Дозволено
0
1
Видача скоректованого інформаційного слова та синдрому помилки
Вихідні скоректовані розряди
Вихідні розряди
синдрому помилки
Дозволено
Рис. 7. Структурна схема ВК К555 ВЖ1
Рис. 8. Позначення ВІС К555 ВЖ1
В режимі формування контрольних розрядів (S0=0, S1=0) інформаційна кодова комбінація із входів ВІС через блок задання напрямку обміну інформаційних розрядів надходить на вхід генератора контрольних розрядів (ГКР). У ВІС К555 ВЖІ використовується модифікований код Хемінга С22, 16, контрольні розряди якого утворюються за таким алгоритмом:
,
,
,
,
,
.
Сформовані контрольні розряди через генератор синдрому (ГС) і блок задання напряму обміну контрольних і синдромних розрядів БЗНОКІСР подаються на відповідні виходи () ВІС.
Виправлення помилок здійснюється в три етапи :
1. Зчитуються значення інформаційних і контрольних розрядів
S0=1, S1=0, відповідно із входів і через блоки задання напрямку обміну інформаційних і контрольних та синдромних розрядів. Генератор синдрому формує синдром помилки.
2. Інформація блокується у тригерах блоків завдання напрямку обміну і визначаються ознаки помилок (S0=1, S1=1). Табл. 3 ілюструє залежність вигляду синдрому і наслідків спотворення кодових комбінацій.
Таблиця 3
000
001
010
011
100
101
110
111
000
ВБ
НБ
НБ
ВБ
НБ
ВБ
ВБ
НБ
001
НБ
ВБ
ВБ
I8
ВБ
I3
I0
ВБ
010
НБ
ВБ
ВБ
I9
ВБ
I4
I1
ВБ
011
ВБ
I13
/10
ВБ
НБ
ВБ
ВБ
К0
100
НБ
ВБ
ВБ
НБ
ВБ
I5
I2
ВБ
101
ВБ
I14
I11
ВБ
I6
ВБ
ВБ
К1
110
ВБ
I15
I12
ВБ
I7
ВБ
ВБ
К2
111
НБ
ВБ
ВБ
K5
ВБ
K4
К3
НП
НП - немає помилок в кодовій комбінації (ЕF=0, NЕF=0);
Кi - номер спотвореного контрольного розряду (ЕF=1, NЕF=0);
Ii - номер спотвореного інформаційного розряду (ЕF=1, NЕF=0);
ВБ - багатократна помилка, яка виявляється (ЕF=0, NЕF=І);
НБ - багатократна помилка, яка не виявляється (ЕF=1, NЕF=1);
У випадку одиничної помилки (ЕF=1, NЕF=0) дешифратор визначає її адрес і помилка виправляється у коректуючому пристрої.
3. Дозволяється видача скоректованого результату (S0=0, S1=1) через блок задання напрямку обміну інформаційних розрядів на виходи ВІС.
Модифікований код Хемінга, який використаний у ВІС К555 ВЖІ, дав змогу :
1. Уніфікувати принципову схему кодуючих та декодуючих пристроїв за типом входів і навантаження логічних схем.
2. Зменшити час затримки при формуванні контрольних розрядів (50 нс), синдрому і ознак помилок (для однократних 30 нс, багатократних 40 нс).
3. Збільшити кількість виявлених помилок (як у коді системи МКТ-2).
4. Зменшити складність і збільшити швидкодію блоків визначення багатократних помилок.
5. Забезпечити збільшення формату інформаційних даних, використовуючи кілька ВІС, зберегти при цьому мінімальний коефіцієнт надлишковості.
6. Забезпечити можливість апаратно-програмної обробки синдромів помилок.
7. Забезпечити режим самодіагностики ВІС.
Експериментальне показано, що використання коду Хемінга в запам’ятовуючих пристроях (ЗП) з інформаційною ємністю 64 к байт дає змогу збільшити надійність функціонування ЗП в 60 100 і більше раз.
6. ЗМІСТ ЗВІТУ
1. Мета роботи.
2. Результати виконання пунктів 2-4, 7-8 при домашній підготовці.
3. Результати досліджень на програмному макеті.
4. Схеми кодерів і декодерів.
5. Висновки по роботі.
7. КОНТРОЛЬНІ ЗАПИТАННЯ
1. Методика визначення кількості контрольних розрядів коду Хемінга.
2. Місцезнаходження контрольних розрядів у класичному і циклічному кодах Хемінга.
3. Алгоритми утворення контрольних розрядів і синдромів помилок.
4. Використання утворюючої і контрольної матриць.
5. Методика кодування і декодування кодів Хемінга при різних кодових віддалях при виявленні і при виправленні помилок.
6. Схемотехнічне забезпечення кодування і декодування кодів Хемінга.
7. Методи збільшення кодової віддалі (d > 4).
8. Суть квазітрійкового кодування та декодування кодів Хемінга.
8. СПИСОК ЛІТЕРАТУРИ
1. Кодирование информации. Двоичные коды. Справочник / Под ред. Н. Т. Березюка. – Харьков: Вища шк., 1978.
2. Кузьмин И. В., Кедрус В. А. Основы теории информации и кодирование. – К.: Вища шк.; 1986.
3. Митюшкин К. Г. Телеконтроль и телеуправление в энергосистемах. – М.: Энергоатомиздат, 1990.
4. Питання теорії та проектування передавальних напівкомплектів систем телемеханіки: Навч. пос. / Під ред. М.В. Кіріанакі. – К.: НМК ВО, 1991.
5. Тутевич В. И. Телемеханика. – М.: Высшая шк., 1985.