Коригувальні коди Хеммінга
Побудова кодів Хеммінга базується на принципі перевірки на парність ваги W (числа одиничних символів) в інформаційній групі кодового блоку.
Пояснимо ідею перевірки на парність на прикладі найпростішого коригуючого коду, який так і називається кодом з перевіркою на парність або кодом з перевіркою за паритетом (рівності).
В такому коді до кодовою комбінаціям безізбиточного первинного довічного m – розрядного коду додається один додатковий розряд (символ перевірки на парність, званий перевірочним, або контрольним). Якщо число символів “1” вихідної кодової комбінації парне, то в додатковому розряді формують контрольний символ 0, а якщо число символів “1” непарне, то в додатковому розряді формують символ 1. В результаті загальне число символів “1” в будь-який передається кодової комбінації завжди буде парним.
Таким чином, правило формування перевірочного символу зводиться до наступного:
де i – відповідний інформаційний символ (0 або 1), m – загальне їх число а під операцією “” тут і далі розуміється складання поmod2. Очевидно, що додавання додаткового розряду збільшує загальне число можливих комбінацій удвічі в порівнянні з числом комбінацій вихідного первинного коду, а умова парності розділяє всі комбінації на дозволені і недозволені. Код з перевіркою на парність дозволяє виявляти одиночну помилку при прийомі кодової комбінації, так як така помилка порушує умову парності, переводячи дозволену комбінацію в заборонену.
Критерієм правильності прийнятої комбінації є рівність нулю результату S підсумовування поmod2 всехn символів коду, включаючи перевірки сімволk1. При наявності одиночної ошібкіS приймає значення 1:
Цей код є (m + 1, m) – кодом, або (n, n -1) – кодом. Мінімальна відстань коду дорівнює двом (dmin = 2), і, отже, ніякі помилки не можуть бути виправлені. Простий код з перевіркою на парність може використовуватися тільки для виявлення (але не виправлення) одноразових помилок.
Збільшуючи число додаткових перевірочних розрядів і формуючи за певними правилами перевірочні символи k. рівні 0 або 1, можна підсилити коригувальні властивості коду так, щоб він дозволяв не тільки виявляти, але і виправляти помилки. На цьому і засноване побудова кодів Хеммінга.
Коди Хеммінга. Розглянемо ці коди, що дозволяють виправляти одиночну помилку, за допомогою безпосереднього опису. Для кожного числа перевірочних сімволовk = 3,4,5 . існує класичний код Хеммінга з маркуванням
тобто – (7,4), (15,11), (31,26) .
При інших значеннях числа інформаційних символів m виходять так звані усічені (укорочені) коди Хеммінга. Так, для міжнародного телеграфного коду МТК-2. має 5 інформаційних символів, буде потрібно використання коригуючого коду (9,5), що є усіченим від класичного коду Хеммінга (15,11), так як число символів в цьому коді зменшується (коротшає) на 6. Для прикладу розглянемо код Хеммінга (7,4 ), який можна сформувати і описати за допомогою кодера, представленого на рис.13.1. У найпростішому варіанті при заданих чотирьох (m = 4) інформаційних символах (i1, i2, i3, i4) будемо вважати, що вони згруповані на початку кодового слова, хоча це і не обов’язково. Доповнимо ці інформаційні символи три перевірних символами (k = 3), задаючи їх наступними рівностями перевірки на парність, які визначаються відповідними алгоритмами. Відомо, що кодова відстань дорівнює мінімальному числу перевірок, в які входить інформаційний символ плюс один. В даному кодеdmin. Отже кожен інформаційний символ повинен входити мінімум в два пункти. Визначимо правило формування перевірочних символів наступний чином:
Відповідно до цього алгоритмом визначення значень перевірочних символів ki на ріс.13.3 наведені всі можливі 16 кодових слів (7,4) – коду Хеммінга.
На рис. 13.2пріведена схема декодера для (7,4) – коду Хеммінга, на вхід якого надходить кодове слово
Апостроф означає, що будь-який символ слова може бути спотворений перешкодою в каналі передачі.
У декодере в режимі виправлення помилок будується послідовність:
Трёхсімвольная послідовність (s1. S2. S3) називається синдромом. Термін “синдром” використовується і в медицині, де він позначає поєднання ознак, характерних для певного захворювання. В даному випадку сіндромS = (s1. S2, s3) являє собою поєднання результатів перевірки на парність відповідних символів кодової групи і характеризує певну конфігурацію помилок (вектор помилок).
Рис.13.1. Кодер для простого (7,4) – коду Хеммінга
Рис.13.2. Декодер для простого (7,4) – коду Хеммінга
Таким чином, код (7,4) дозволяє виправити всі поодинокі помилки. Проста перевірка показує, що кожна з помилок має свій єдиний синдром. При цьому можливе створення такого цифрового коректора помилок (дешифратора синдрому), який за відповідним синдрому виправляє відповідний символ в прийнятій кодовій групі. Після внесення виправлення перевірочні символи ki можна на вихід декодера (рис.13.2) не виводити. Дві або більше помилки перевищують можливості коригуючого коду Хеммінга, і декодер буде помилятися. Це означає, що він буде вносити неправильні виправлення і видавати спотворені інформаційні символи.
Ідея побудови подібного коригувального коду, природно, не змінюється при перестановці позицій символів в кодових словах. Всі такі варіанти також називаються (7,4) – кодами Хеммінга.
Розширені коди Хеммінга будуються в результаті доповнення кодів сdmin = 3 спільною перевіркою кожної з кодових комбінацій на парність, тобто ще одним перевірочним символом. Це дозволяє збільшити мінімальну кодову відстань доdmin = 4.
Для продовження скачування необхідно зібрати картинку:
Схожі статті
Коди гемінга – теорія інформації – конспект лекцій
Найбільш поширеним систематичним лінійним блоковим кодом є код Хеммінга. До нього відносяться кодис мінімальним кодовою расстояніемdmin = 3, здатні виправляти одноразові помилки.
При передачі кодового слова по каналу зв’язку можливе виникнення одноразової помилки в будь-якому з його елементів. Кількість таких ситуацій. Таким чином, для того щоб визначити місце виникнення помилки, кількість комбінацій перевірочних елементів 2r має бути не менше кількості можливих помилкових ситуацій в коді плюс ситуація, коли помилка не виникає, т. Е. Має виконуватися нерівність
З цієї нерівності слід мінімальне співвідношення перевірочних та інформаційних розрядів, необхідне для виправлення одноразових помилок
Для розрахунку основних параметрів коду Хеммінга можна задати кількість перевірочних елементовr. тоді довжина кодових слів n≤ 2r-1, а кількість інформаційних елементовk = n -r. Співвідношення між r. n і k наведені в наступній таблиці (табл. 3.3.)
Характерною особливістю перевірочної матриці коду з dmin = 3 є те, що її стовпці – різні ненульові комбінації довжини r.
Хеммінгомпредложено розташовувати стовпці перевірочної матріцитак, чтобиi-й стовпець матриці і номер розряду кодової комбінації відповідали бінарного поданням чіслаi. Тоді синдром виправлення одноразових ошібокбудет двійковим поданням номера розряду, в якому сталася помилка. Для цього перевірочні розряди повинні знаходитися не в правій частині кодового слова, а в позиціях, номери яких є ступенем двійки, т. Е.20. 21. 22. . 2r-1.
Наприклад, для r = 3 перевірочна матриця коду Хеммінга має вигляд
Перевірочна матриця (k, n)-коду Хеммінга складається ізn = 2r-1строк іrстолбцов і являє собою виконавчі комбінації чіслаi. гдеi – номер стовпця перевірочної матриці (розряду кодової комбінації).
Наприклад, для r = 2. 3. 4 перевірочні матриці коду Хеммінга мають вигляд
Синдром, який визначає систему перевірочних рівнянь коду, знаходиться з уравненіяu ‘= 0.
Наприклад, для r = 3 система перевірочних рівнянь буде наступною:
Звідси перевірочні розряди (контрольні суми) знаходяться як
Щоб закодувати сообщеніеm, в качествеui, гдеiне дорівнює ступеню 2. беруться відповідні біти повідомлення, а перевірочні розряди з індексами ступеня 2 знаходяться з системи перевірочних рівнянь коду. У кожне рівняння системи входить лише одна контрольна сума.
Приклад 1 Закодируем повідомлення m = (0 1 1 1) (4, 7)-кодом Хеммінга.
Із системи перевірочних рівнянь знаходимо контрольні суми:
Таким чином, кодовим словом буде послідовність (0001111).
Декодування коду Хеммінга відбувається за такою схемою. Визначається синдром прийнятої последовательностіS = y’, десь транспонована перевірочна матриця коду; y- прийнятий вектор. Якщо синдром дорівнює нульовому вектору, то вважається, що слово передано без помилок, іначезначеніе синдрому відповідає бінарного поданням номера розряду, в якому сталася помилка. В цьому випадку потрібно змінити значення в помилковому розряді, вважаючи розряди зліва направо, починаючи з 1.
Приклад 2 Повідомлення кодується (4, 7)-кодом Хеммінга. Прийнята послідовність y = (0011111). Декодируем прийнятий вектор.
Визначаємо синдром прийнятого вектора:
т. е. помилка сталася в третьому розряді.
Виправляємо помилку, змінюючи значення в третьому бите
(001 1111) ® (0001111).
Передане повідомлення декодируется як
Породжує матрицею (k, n)-коду Хеммінга є матриця (k × n), в якій стовпці з номерами не ступеня 2 утворюють одиничну підматрицю, а інші стовпці відповідають перевірочним рівнянням коду. Така матриця при кодуванні копіюватиме біти повідомлення у позиції, не ступеня 2, і заповнювати інші позиції коду відповідно до системи обчислення контрольних розрядів.
Приклад 3 Система перевірочних рівнянь (4, 7)-коду Хеммінга наступна:
Відповідно породжує матриця даного коду має вигляд
1 Які коди відносяться до перешкодостійким. Якими загальними властивостями вони характеризуються?
2 Для чого в перешкодостійкі коди вводиться надмірність?
3 Які існують класи перешкодостійких кодів?
4 Які коди відносяться до блокових перешкодостійким кодами. В яких випадках їх доцільно використовувати?
5 Як визначаються операції додавання і множення в полі двійкових символів GF (2) (операціісложенія і умноженіяпо модулю 2)?
6 Які коди називаються лінійними блоковими кодами. Які коди мають властивість систематичності.
7 У чому полягає кодування з перевіркою на парність. Яка надмірність такого коду? У чому переваги і недоліки цього коду?
8 Який канал передачі інформації описується моделлю довічного симетричного каналу.
9 У чому полягає процедура виявлення і виправлення помилок ітеративним кодом. Які переваги і недоліки даного коду?
10 Які існують способи завдання лінійних блокових кодів. З яких основних частин будується кодове слово лінійного блокового систематичного коду?
11 Що таке сістемапроверочних рівнянь лінійного блокового коду?
12 Що таке породжує матриця лінійного блокового коду? Які її властивості? Яка структура породжує матриці?
13 Як, використовуючи породжує матрицю, побудувати систему перевірочних рівнянь лінійного блокового коду?
14 Що таке перевірочна матриця лінійного блокового коду? Які її властивості?
15 Яка структура перевірочної матриці лінійного блокового коду? Яка частина перевірочної матриці відповідає інформаційним символам, а яка – перевірочним?
16 Як, використовуючи перевірочну матрицю, побудувати систему перевірочних рівнянь лінійного блокового коду?
17 Як описується вектор помилок в довічним каналі зв’язку? В чому полягає завдання декодування переданого кодового слова?
18 Що таке кодовий синдром лінійного блокового коду? Як він визначається?
19 Яким властивістю характеризується синдром прийнятого вектора? В яких випадках кодовий синдром не дозволяє виявити помилки в переданої послідовності?
20 Як за допомогою кодового синдрому виявляються і виправляються помилки лінійним блоковим кодом?
21 Як визначаються вага і расстояніеХеммінга для довічних послідовностей?
22 Що таке мінімальна кодова відстань Хеммінга лінійного блокового коду? Як воно визначається?
23 Яке необхідна і достатня умова виявлення лінійним блоковим кодом помилок заданої кратності?
24 Яке необхідна і достатня умова виправлення лінійним блоковим кодом помилок заданої кратності?
25 Які необхідне і достаточноеусловія існування перешкодостійкого коду?
26 Як визначається мінімальна кількість перевірочних символів для лінійного блокового коду з заданими характеристиками?
27 Як побудувати породжує матрицю лінійного блокового коду з заданими характеристиками?
28 Які лінійні блокові коди називаються кодами Хеммінга?
29 Як визначається кількість інформаційних і перевірочних символів для коду Хеммінга.
30 Як будуються кодові слова коду Хеммінга.
31 Як складається перевірочна матриця двійкового коду Хеммінга.
32 Чому відповідає значення синдрому при використанні коду Хеммінга?
33 Як відбувається декодування коду Хеммінга?
34 Як будується породжує матриця коду Хеммінга?
[1] Шеннон К. Роботи по теорії інформації і кібернетики. – М. Видавництво іноземної літератури, 1963.
[2] Яглом А. Яглом І. Імовірність і інформація – М. Наука, 1973.