3.10 Код Хеммінга
Найбільш поширеним систематичним лінійним блоковим кодом є код Хеммінга. До нього відносяться коди з мінімальним кодовою відстанню dmin = 3. здатні виправляти одноразові помилки.
При передачі кодового слова по каналу зв'язку можливе виникнення одноразової помилки в будь-якому з його елементів. Кількість таких ситуацій. Таким чином, для того щоб визначити місце виникнення помилки, кількість комбінацій перевірочних елементів 2r має бути не менше кількості можливих помилкових ситуацій в коді плюс ситуація, коли помилка не виникає, т. Е. Має виконуватися нерівність
З цієї нерівності слід мінімальне співвідношення перевірочних та інформаційних розрядів, необхідне для виправлення одноразових помилок
Для розрахунку основних параметрів коду Хеммінга можна задати кількість перевірочних елементів r. тоді довжина кодових слів n ≤ 2 r-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 - номер стовпця перевірочної матриці (розряду кодової комбінації).
Синдром. визначає систему перевірочних рівнянь коду, знаходиться з рівняння 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). Декодируем прийнятий вектор.
Визначаємо синдром прийнятого вектора:
т. е. помилка сталася в третьому розряді.
Виправляємо помилку, змінюючи значення в третьому бите
Передане повідомлення декодируется як
Породжує матрицею (k, n)-коду Хеммінга є матриця (k × n), в якій стовпці з номерами не ступеня 2 утворюють одиничну підматрицю, а інші стовпці відповідають перевірочним рівнянням коду. Така матриця при кодуванні копіюватиме біти повідомлення у позиції, не ступеня 2, і заповнювати інші позиції коду відповідно до системи обчислення контрольних розрядів.
Приклад 3 Система перевірочних рівнянь (4, 7)-коду Хеммінга наступна:
Відповідно породжує матриця даного коду має вигляд
Які коди відносяться до перешкодостійким. Якими загальними властивостями вони характеризуються?
Для чого в перешкодостійкі коди вводиться надмірність?
Які існують класи перешкодостійких кодів?
Які коди відносяться до блокових перешкодостійким кодами. В яких випадках їх доцільно використовувати?
Як визначаються операції додавання і множення в полі двійкових символів GF (2) (операції додавання і множення по модулю 2)?
Які коди називаються лінійними блоковими кодами. Які коди мають властивість систематичності.
У чому полягає кодування з перевіркою на парність. Яка надмірність такого коду? У чому переваги і недоліки цього коду?
Який канал передачі інформації описується моделлю довічного симетричного каналу.
В чому полягає процедура виявлення і виправлення помилок ітеративним кодом. Які переваги і недоліки даного коду?
Які існують способи завдання лінійних блокових кодів. З яких основних частин будується кодове слово лінійного блокового систематичного коду?
Що таке система перевірочних рівнянь лінійного блокового коду?
Що таке породжує матриця лінійного блокового коду? Які її властивості? Яка структура породжує матриці?
Як, використовуючи породжує матрицю, побудувати систему перевірочних рівнянь лінійного блокового коду?
Що таке перевірочна матриця лінійного блокового коду? Які її властивості?
Яка структура перевірочної матриці лінійного блокового коду? Яка частина перевірочної матриці відповідає інформаційним символам, а яка - перевірочним?
Як, використовуючи перевірочну матрицю, побудувати систему перевірочних рівнянь лінійного блокового коду?
Як описується вектор помилок в довічним каналі зв'язку? В чому полягає завдання декодування переданого кодового слова?
Що таке кодовий синдром лінійного блокового коду? Як він визначається?
Яким властивістю характеризується синдром прийнятого вектора? В яких випадках кодовий синдром не дозволяє виявити помилки в переданої послідовності?
Як за допомогою кодового синдрому виявляються і виправляються помилки лінійним блоковим кодом?
Як визначаються вага і відстань Хеммінга для двійкових послідовностей?
Що таке мінімальна кодова відстань Хеммінга лінійного блокового коду? Як воно визначається?
Яке необхідна і достатня умова виявлення лінійним блоковим кодом помилок заданої кратності?
Яке необхідна і достатня умова виправлення лінійним блоковим кодом помилок заданої кратності?
Які необхідне і достатнє умови існування перешкодостійкого коду?
Як визначається мінімальна кількість перевірочних символів для лінійного блокового коду з заданими характеристиками?
Як побудувати породжує матрицю лінійного блокового коду з заданими характеристиками?
Які лінійні блокові коди називаються кодами Хеммінга?
Як визначається кількість інформаційних і перевірочних символів для коду Хеммінга.
Як будуються кодові слова коду Хеммінга.
Як складається перевірочна матриця двійкового коду Хеммінга.
Чому відповідає значення синдрому при використанні коду Хеммінга?
Як відбувається декодування коду Хеммінга?
Як будується породжує матриця коду Хеммінга?
1 Шеннон К. Роботи по теорії інформації і кібернетики. - М. Видавництво іноземної літератури, 1963.
2 Яглом А. Яглом І. Імовірність і інформація - М. Наука, 1973.