Методичні вказівки щодо виконання практичної роботи «Вивчення побудови корегуючого коду Хеммінга»

Новокаховський приладобудівний фаховий коледж

  Дисципліна: «Основи теорії кодування та передавання інформації»

МЕТОДИЧНІ ВКАЗІВКИ ЩОДО ВИКОНАННЯ ПРАКТИЧНОЇ РОБОТИ

«Вивчення побудови корегуючого коду Хеммінга»

Мета роботи: вивчити принципи побудови корегуючого коду Хеммінга.

Теоретичні відомості

Для того, щоб у прийнятому повідомленні можна було знайти помилки, воно повинне мати деяку надмірність, яка дозволяє відрізнити помилковий код від правильного. Коди без надмірності знаходити помилки, а тим більше їх виправляти, не можуть.

Систематичні коди – це коди, в яких інформаційні та корегуючі символи розташовані за строго визначеною системою і завжди займають певні місця у кодових комбінаціях. Систематичні коди є рівномірними, тобто всі комбінації коду із заданими корегуючими властивостями завжди мають однакову довжину.

Типовий приклад систематичного коду – код Хеммінга.

Річард Хеммінг — американський математик. Працював в корпорації Bell Telephone Laboratories, де співпрацював з Клодом Шенноном. Роботи Р.Хеммінга мали великий вплив на розвиток інформатики та телекомунікацій. До його внеску належить розробка коду Хеммінга, числа Хеммінга, пакування куль і відстань Хеммінга. Р.Хеммінг був засновником і президентом Асоціації з обчислювальної техніки. Його філософія наукових обчислень описана в передмові до його книги 1962 р. про чисельні методи: «Мета обчислень - розуміння, а не числа».

Для знаходження коду Хеммінга задається кількість інформаційних розрядів  n_i  або кількість повідомлень   N = 2ⁿⁱ .

За допомогою виразів (1), (2) обчислюється кількість корегуючих розрядів  n_k  та загальна довжина кодової комбінації n:  

n_k  = log₂{(n_i +1) + log₂(n_i +1)} ;                              (1)

n = n_i + n_k ,                                                (2)

де   n_i - кількість інформаційних розрядів; 

       n_k - кількість корегуючих розрядів;

       n - загальна довжина кодової комбінації.

Номери позицій контрольних символів в коді зручно обирати за законом 2ⁱ, де і = 1, 2 , … , тобто номери позицій корегуючих символів в коді будуть такі: 1, 2, 4, 8, 16,…

Потім визначаються перевірочні позиції коду Хеммінга. Для цього складається таблиця двійкових кодів натуральних чисел. Кількість колонок у таблиці: n = n_i + n_k .                                              

Визначимо комбінації двійкового коду інформаційного повідомлення. Наприклад, для числа інформаційних розрядів n_i = 4 число можливих кодових комбінацій дорівнює N = 2ⁿⁱ = 2⁴ = 16.

Усі можливі комбінації 4–значного двійкового коду (старший біт зліва) показані в таблиці 1:

Таблиця 1 - Можливі комбінації 4–значного двійкового коду

Числу N=1 відповідає перевірочний коефіцієнт a1 ,числу N=2 - a2 і т.д. Ці коефіцієнти далі виписують за наступним принципом:

Для першої перевірки виписуються всі перевірочні коефіцієнти, що містять 1 у молодшому розряді двійкового коду (див. таблицю 1):

a1, a3, a5, a7,  ...

Для другої перевірки виписуються всі перевірочні коефіцієнти, що містять 1 у другому розряді двійкового коду (див. таблицю 1):

а2, a3, a6, a7,  ...

Для третьої  перевірки  виписуються всі перевірочні коефіцієнти, що містять 1 у третьому розряді двійкового коду (див. таблицю 1):

а4, a5, a6, a7,  ...

і так далі.

Номери перевірок коефіцієнтів відповідають номерам позицій коду, які входять до загальної таблиці перевірок (див. таблицю 2):

Таблиця 2 – Таблиця перевірок корегуючих розрядів

Потім визначають значення корегуючих символів за правилом: сума одиниць на перевірочних позиціях у всіх перевірках має бути парною. Якщо сума одиниць парна, то значення корегуючого символу дорівнює 0, якщо сума одиниць непарна, то значення корегуючого символу дорівнює 1.

Якщо у прийнятому коді є помилка, то результати перевірок по контрольних позиціях утворюють двійкове число, що вказує номер помилкової позиції. Помилку виправляють, змінюючи символ помилкової позиції на протилежний.

Приклад. Побудувати код Хеммінга для комбінації інформаційних символів 0101.

Розв’язок.  

1. За заданою довжиною інформаційного слова (n_i=4), використовуючи співвідношення (1), (2), обчислимо основні параметри коду n та n_k.

n_k - кількість корегуючих розрядів:

n_k = log₂{(n_i+1)+ log₂(n_i+1)} = log₂{(4+1)+ log₂(4+1)} = 2,872 ≈ 3.

n - загальна довжина кодової комбінації:

n = n_i + n_k = 4 + 3 = 7.

Визначаємо робочі та контрольні позиції кодової комбінації.

Номери контрольних позицій визначаються за законом 2ⁱ, де i = 1, 2, 3, ... , тобто вони дорівнюють 1, 2, 4, 8, 16, … , рахуючи зліва. Інші позиції кодової комбінації є робочими.

Для даного прикладу корегуючі символи будуть на позиціях 1, 2, 4. Тоді проєкт коду Хеммінга для комбінації інформаційних символів 0101 має вигляд, показаний в таблиці 3. 

Таблиця 3 - Робочі та контрольні позиції кодової комбінації 0101

Користуючись таблицею 2 перевірочних позицій, визначаємо  значення корегуючих символів  k₁, k₂, k₃ коду на позиціях 1, 2, 4.

Перша  перевірка: 

сума одиниць на перевірочних позиціях П₁П₃П₅П₇  має бути парною:

k₁011 = 0,  якщо k₁ = 0.

Друга  перевірка:

сума одиниць на перевірочних позиціях П₂П₃П₆П₇  має бути парною:

k₂001 = 0,  якщо k₂ = 1.

Третя  перевірка:

сума одиниць на перевірочних позиціях П₄П₅П₆П₇  має бути парною:

k₃101 = 0,  якщо k₃ = 0.

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

Таблиця 4 - Корегуючий  код Хеммінга

Припустимо, в результаті спотворень в каналі замість послідовності 0100101 була прийнята послідовність 0100111 (помилка у шостому розряді; порядок рахування розрядів  - зліва направо).

Таблиця 5 - Проєкт коду Хеммінга з помилкою у шостому розряді

Для виявлення і виправлення помилки складаються аналогічні перевірки на парність контрольних сум, результатом яких є двійкове (n - n_i) - розрядне число (синдром), яке вказує на номер помилкової позиції, який визначається за двійковим записом числа.

Для знаходження помилки виконується контроль перевірочних коефіцієнтів на парність, що аналогічні перевіркам при виборі корегуючих символів.

Перша  перевірка:

сума одиниць на позиціях П₁П₃П₅П₇ = 0011= 0 парна, тоді перший (молодший) розряд номеру помилкової позиції дорівнює  0.

Друга  перевірка:

сума одиниць на позиціях П₂П₃П₆П₇ =1011=1 – непарна, тоді другий розряд номеру помилкової позиції дорівнює  1.

Третя перевірка:

сума одиниць на позиціях  П₄П₅П₆П₇ = 0111=1 – непарна, тоді третій розряд номеру помилкової позиції  дорівнює  1.

Порядок розташування розрядів з молодшого розряду до старшого

(зліва направо).

Номер помилкової позиції : 110₂ = 6₁₀. Отже, символ 6-ї позиції коду Хеммінга треба замінити на зворотній.

Для виправлення одиничної та знаходження подвійної помилки, крім перевірок по перевірочним позиціям, треба зробити ще одну перевірку на парність для кожного коду. Щоб це зробити, треба до кожного коду в кінці додати контрольний символ таким чином, щоб сума одиниць в отриманій комбінації була парною. Тоді у випадку однієї помилки перевірки по позиціях вкажуть номер помилкової позиції, а перевірка на парність вкаже наявність помилки.

Якщо перевірки позиції вкажуть на наявність помилки, а перевірка на парність не фіксує помилки, значить, тоді у коді є дві помилки.

Порядок виконання практичної роботи

Побудуйте коригувальний коригуючий код Хеммінга для передавання повідомлення: 0011.

Виконайте процедуру  виявлення і виправлення помилки в 3-му розряді  побудованого коду Хеммінга.

Зміст звіту практичної роботи

1.               Назва та ціль роботи.
2.               Формули розрахунків.
3.               Таблиці результатів розрахунків.
4.               Короткі висновки з роботи і  відповіді на контрольні питання.

Контрольне питання

1.               Що називається систематичним кодом?

Література

1.               Беркман Л.Н., Бондарчук А.П., Гайдур Г.І., Чумак Н.С. Кодування джерел інформації та каналів зв’язку :  навчальний посібник. – Київ: ННІТІ ДУТ, 2018.
2.               Фетюхіна Л. В. Теорія інформації та кодування : навч.-метод. посібник/ Л. В.Фетюхіна, О. А. Бутова – Харків: НТУ «ХПІ», 2012.