тамі ПОВІДОМЛЕННЯ. Наприклад, ЯКЩО r = 4, то Биті - контрольні, а - із Початкова ПОВІДОМЛЕННЯ;
3. Будується матриця M з рядків и r стовпців. У i-ому рядку стояти цифри двійкового представлення числа i. Матріці для r = 2, 3 і 4 Такі:
В
4. Запісується система рівнянь bM = 0, де M - матриця з попередня пункту. Система Складається з r рівнянь. Наприклад, для r = 3
В
5. Щоб закодуваті ПОВІДОМЛЕННЯ а, беруться як b j , j НЕ дорівнює ступенів двійкі, відповідні біті ПОВІДОМЛЕННЯ и відшукуються, вікорістовуючі отриманий систему рівнянь, ті b j , для якіх j-ступінь двійкі. У кожному рівняння входити Тільки Одне b j, j = 2 j . У віпісаній Системі b 4 входити в 1-е рівняння, b 2 - в одному и b 1 - в Третє. У Розглянуто прікладі ПОВІДОМЛЕННЯ a = 0111 буде закодовано кодовим словом b = 0001111.
Декодування коду Хеммінга проходити за Наступний схему. Хай Прийнято слово b + e, де b - надіс кодове слово, а e - рядок помилок. Оскількі bM = 0, то (b + e) ​​M = bM + eM = eM. Если результат нульовий, як відбувається при правільній передачі, вважається, что помилок Не було. Если рядок помилок має одиницю в і-ій позіції, то результатом множення eM буде i-й рядок матріці M або двійкове представлення числа i. У цьом випадка слід Изменить символ в i-й позіції слова
Код Хеммінга - це груповий код. Це вітікає з того, что (m, n)-код Хеммінга можна отріматі матричний кодування, за помощью-матриці, в якій стовпці з Номер не ступенями 2 утворюють одінічну підматріцю. Решта стовпців відповідає рівнянням Кроку 4 побудова коди Хеммінга, тоб 1-у стовпцю відповідає рівняння для обчислення 1-го контрольного розряду, 2-у - для 2-го, 4-у - для 4-го и так далі Така матриця при кодуванні копіюватіме біті ПОВІДОМЛЕННЯ у позіції НЕ ступінь 2 коди и заповнюваті Другие позіції коди згідно схемі кодування Хеммінга.
До (m, n)-коду Хеммінга можна Додати перевірку парності. Вийди (m, n +1)-код з найменшого вагою ненульового кодового слова 4, здатн віправляті одну и віявляті Дві помилки.
Коді Хеммінга накладають обмеження на Довжину слів Повідомлення: ця довжина может буті Тільки числами вигляд 2 r -r-1: 1, 4, 11, 26, 57. . Альо в реальних системах інформація передається байтам або машинними словами, тоб порціямі по 8, 16, 32 або 64 біта, что Робить Використання Досконалий кодів НЕ всегда відповіднім. Тому в таких випадка часто Використовують квазідосконалі коди. p> Квазідосконалі (M, n)-коди, что віправляють одну Помилка, будуються таким чином. Вібірається мінімальне n так, щоб
Кожне кодовий слово Такої коди містітіме k = nm контрольних розрядів. З попередніх СПІВВІДНОШЕНЬ виходе, что
В
Кожному з n розрядів прівласнюється Зліва-направо номер від 1 до n. Для заданого слова ПОВІДОМЛЕННЯ складаються k контрольних сум S 1 , ..., S k по модулем 2 значень спеціально вибраних розрядів кодового слова, Які поміщаються в позіції-Ступені 2 в ньом: для вібіраються розряди, что містять біті початкова ПОВІДОМЛЕННЯ, двійкові числа-номери якіх мают в i-му розряді одиницю. Для суми S 1 це будут, Наприклад, розряди 3, 5, 7 и так далі, для суми S 2 - 3, 6, 7 и так далі Таким чином, для слова ПОВІДОМЛЕННЯ a = a 1 ... a m буде побудовали кодове слово Позначімо через торбу за модулем 2 розрядів Отримання слова, відповідніх контрольній сумі S i и самій цієї контрольної суми. Если, то вважається, что передача пройшла без помилок. У разі одінарної помилки дорівнюватіме двійковому числу-номеру збійного біта. У разі помилки, кратності більшої 1, коли, ее можна віявіті. Подібна схема декодування НЕ дозволяє віправляті деякі подвійні помилки, чого можна Було б досягті, вікорістовуючі схему декодування з лідерамі, альо остання однозначно складніше в реалізації и Дає незначна Поліпшення якості коди.
Приклад побудова кодового слова квазідосконалого (9, n)-коду, что віправляє ВСІ одноразові помилки, для ПОВІДОМЛЕННЯ 100011010.
В
Шуканов кодовий слово має вигляд
1
2
3
4
5
6
7
8
9
10
11
12
13
S 1
S 2
1
S 3
0
0
0
S 4 ...
