3.10. код Хеммінга
Одним з найбільш поширених систематичних кодів є код Хеммінга [132].
До них зазвичай відносяться коди з мінімальним кодовою відстанню виправляють всі поодинокі помилки, і коди з відстанню виправляють всі поодинокі і виявляють все подвійні помилки. Довжина коду Хеммінга
(R - кількість перевірочних розрядів). З цієї нерівності отримуємо
Формулу (3.29) можна привести до наступного вигляду:
де кількість інформаційних розрядів. Це нерівність дозволяє визначити довжину коду при заданому числі інформаційних розрядів. У табл. 21 наведені параметри деяких кодів Хеммінга.
Таблиця 21 (див. Скан)
Характерною особливістю перевірочної матриці коду з є те, що її стовпці представляють собою будь-які різні ненульові комбінації довжиною Наприклад, при т. Е. Для коду (15,11), перевірочна матриця може мати наступний вигляд:
Перестановкою стовпців, що містять одну одиницю, дану матрицю можна привести до виду
Використання такого коду дозволяє виправити будь-яку одиночну помилку або виявити довільну помилку кратності два.
Якщо інформаційні та перевірочні розряди коду нумерувати зліва направо, то відповідно до матриці отримуємо систему перевірочних рівнянь, за допомогою яких обчислюємо перевірочні розряди:
де «перевірочні розряди; інформаційні розряди.
У тому випадку, коли при передачі кодового слова виникає одиночна помилка, виявляться невиконаними ті перевірочні співвідношення, в які входить значення помилкового розряду. Наприклад, якщо помилка виникла в п'ятому інформаційному розряді, виявляться нездійсненними перше і четверте рівняння, т. Е. Синдром дорівнює 1001 (збігається з п'ятим стовпцем матриці Я). Звідси отримуємо алгоритми визначення місця одиночної помилки: місце розташування стовпця матриці, що збігається з обчисленим синдромом, вказує місце помилки. Ясно, що обчислене значення синдрому обов'язково збігається з одним з стовпців матриці, так як в якості стовпців обрані всі можливі виконавчі розрядні числа.
Хеммінга запропонував використовувати таке розташування стовпців перевірочної матриці, щоб номер стовпця матриці і номер розряду кодової комбінації відповідав бінарного поданням числа В цьому випадку синдром, отриманий з перевірочних рівнянь, є двійковим поданням номера розряду комбінації, в якому сталася помилка. Для цього перевірочні розряди повинні знаходитися не в кінці кодової комбінації, а на номерах позицій, які виражаються ступенем двійки так як кожен з них входить тільки в одне з перевірочних рівнянь.
Приклад. Для як перевірочної може бути обрана наступна матриця:
Як перевірочних розрядів вибираємо перший, другий і четвертий. Щоб закодувати повідомлення 1101, потрібно визначити перевірочні розряди в комбінації З матриці маємо
Отже, і закодоване повідомлення має вигляд 1010101. Припустимо, що шостий символ прийнятий помилково, тоді буде отримано повідомлення 1010111. Синдром в цьому випадку має вигляд т. Е. Двійкове подання числа 6.
Двійковий код Хеммінга з кодовою відстанню виходить шляхом додавання до коду Хеммінга з одного перевірочного розряду, що представляє собою результат підсумовування по модулю два всіх розрядів кодового шару. Довжина коду при цьому розрядів, з яких є перевірочними.
Операція кодування може виконуватися в два етапи. На першому етапі визначається кодова комбінація з використанням матриці Я, відповідної коду з на другому - додається один перевірки розряд, в якому записується результат підсумовування по модулю два всіх розрядів кодового слова, отриманого на першому етапі.
Операція декодування також складається з -двух етапів. На першому обчислюється синдром, відповідний коду з на другому - перевіряється останнім перевірочне співвідношення. Результати виконання цих операцій і відповідні їм висновки наведені в табл. 22,
Таблиця 22 (див. Скан)
Перевірочна матриця для -кода з може мати вигляд
Додаткове перевірочне співвідношення, що вводиться для збільшення мінімальної відстані коду Хеммінга, уявімо так: З огляду на (3.31), отримуємо
Система рівнянь (3.31) і останнє співвідношення для дозволяє записати перевірочну матрицю для коду (16, 11):
Іноді при практичному використанні коду зустрічається завдання отримання укороченого коду із заданим мінімальним відстанню або 4). У цьому випадку будується перевірочна матриця для неукороченного коду з найменшим значенням задовільняють наступні вимоги:
У другому випадку число перевірочних розрядів коду одно Потім в отриманій матриці відкидаються всі зайві стовпці подматріци
Приклад. Побудувати перевірочну матрицю для коду Хеммінга з містить інформаційних розрядів. Найменше значення яке задовольняє нерівності (3.34), дорівнює 4.
Довжина коду дорівнює 16. Матриця для цього коду приведена в (3.32) У подматріца містить І розрядів, викреслюємо останній стовпець для економії апаратури (зазвичай викреслюються стовпці з найбільшою кількістю едіінц).
Перевірочна матриця укороченого коду (15, 10) в цьому випадку має вигляд
При використанні табл. 21 дуже просто визначаємо, для якого з неукороченних кодів Хеммііга необхідно побудувати перевірочну матрицю, по якій будується перевірочна матриця укороченого коду. Наприклад, якщо необхідно будувати перевірочну матрицю для коду, з т. Е. Коду (63, 57), і потім викреслити з подматріци двадцять сім стовпців.
Вагову характеристику коду Хеммінга зручно знаходити за допомогою функції дозволяє визначити число кодових векторів з різними вагами 193].
У формулах (3.35), (3.36) число кодових векторів ваги зі дорівнює значенню коефіцієнтів многочлена, що стоять перед
Приклад. Нехай постав код Хеммінга про Визначити коефіцієнти помилкових переходів. Для цього коду згідно з формулою (3.35) маємо
Отже, даний код містить одне кодове слово ваги О, сім слів ваги 3, сім слів ваги 4 і одне слово ваги 7. Це означає, що розподіл робочих векторів по кодовою відстаням даного коду наступне! Коефіцієнти помилкових переходів
Тому втот код виявляє все одно-, дво, п'яти-, шестикратні помилки, 80% триразових і чотирикратних.