Визначення і способи задання групових кодів (стр. 3 из 3)
3. Будується матриця M з
рядків і r стовпців. У i-ому рядку стоять цифри двійкового представлення числа i. Матриці для r=2, 3 і 4 такі: 
4. Записується система рівнянь bM=0, де M - матриця з попереднього пункту. Система складається з r рівнянь. Наприклад, для r=3
5. Щоб закодувати повідомлення а, беруться як bj, j не дорівнює ступеню двійки, відповідні біти повідомлення і відшукуються, використовуючи отриману систему рівнянь, ті bj, для яких j- ступінь двійки. У кожне рівняння входить тільки одне bj, j=2j. У виписаній системі b4 входить в 1-е рівняння, b2 - в друге і b1 - в третє. У розглянутому прикладі повідомлення 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, здатний виправляти одну і виявляти дві помилки.
Коди Хеммінга накладають обмеження на довжину слів повідомлення: ця довжина може бути тільки числами вигляду 2r-r-1: 1, 4, 11, 26, 57 . . Але в реальних системах інформація передається байтам або машинними словами, тобто порціями по 8, 16, 32 або 64 бита, що робить використання досконалих кодів не завжди відповідним. Тому в таких випадках часто використовуються квазідосконалі коди.
Квазідосконалі (m, n) -коды, що виправляють одну помилку, будуються таким чином. Вибирається мінімальне n так, щоб
Кожне кодове слово такої коди міститиме k=n-m контрольних розрядів. З попередніх співвідношень виходить, що
Кожному з n розрядів привласнюється зліва-направо номер від 1 до n. Для заданого слова повідомлення складаються k контрольних сум S1,…,Sk по модулю 2 значень спеціально вибраних розрядів кодового слова, які поміщаються в позиції-ступені 2 в ньому: для
вибираються розряди, що містять біти початкового повідомлення, двійкові числа-номери яких мають в i-м розряді одиницю. Для суми S1 це будуть, наприклад, розряди 3, 5, 7 і так далі, для суми S2 - 3, 6, 7 і так далі Таким чином, для слова повідомлення a=a1…am буде побудовано кодове слово b=S1S2a1S3a2a3a4S4a5...am.. Позначимо через 
суму по модулю 2 розрядів отриманого слова, відповідних контрольній сумі Si і самій цієї контрольної суми. Якщо 
, то вважається, що передача пройшла без помилок. У разі одинарної помилки 
дорівнюватиме двійковому числу-номеру збійного біта. У разі помилки, кратності більшої 1, коли 
, її можна виявити. Подібна схема декодування не дозволяє виправляти деякі подвійні помилки, чого можна було б досягти, використовуючи схему декодування з лідерами, але остання значно складніше в реалізації і дає незначне поліпшення якості коди.Приклад побудови кодового слова квазідосконалого (9, n) -кода, що виправляє всі одноразові помилки, для повідомлення 100011010.
Шукане кодове слово має вигляд
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| S1 | S2 | 1 | S3 | 0 | 0 | 0 | S4 | 1 | 1 | 0 | 1 | 0 |
Далі потрібно обчислити контрольні суми.
Таким чином, шуканий код - 0011000111010. Якщо в процесі передачі цієї коди буде зіпсований його п'ятий біт, то приймач отримає код 0011100111010. Для його декодування знову обчислюються контрольні суми:
Приймач перетворить зміною п'ятого біта отримане повідомлення у відправлене передавачем, з якого потім відкиданням контрольних розрядів відновлює початкове повідомлення.
Досконалий код Хеммінга також можна будувати за розглянутою схемою, оскільки для нього
.Для виправлення одинарної помилки до 8-розрядного коду досить приписати 4 розряди
, до 16-розрядного - 5, до 32-розрядного - 6, до 64-розрядного - 7.Висновки
1. Передача інформації по каналах зв'язку найчастіше пов'язана з рішенням задачі перешкодостійкого кодування. При цьому групове кодування є одним з можливих варіантів рішення даної задачі.
2. Коди, що виявляють помилку, і коди, що коректують, обов'язково мають додаткові символи (надмірні).
3. Матричне кодування є одним з економних способів опису схеми кодування.
4. Груповий код – це блоковий код, у якого кодові слова утворюють групу.
5. Одними з найбільш поширених перешкодостійких кодів є коди Хеммінга.
6. У реальних системах для кодування інформації застосовується квазідосконале кодування.
Література
1. Чисар И., Кернер Я. Теория информации. М.: Мир, 1985
2. Блейхер Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986
3. Питерсон Р., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976