При використанні групової коди непоміченими залишаються ті і лише ті помилки, які відповідають рядкам помилок, в точності рівним кодовим словам.

Такі рядки помилок переводять одне кодове слово в інше.

Отже, вірогідність того, що помилка залишиться невиявленою, дорівнює сумі вірогідності всіх рядків помилок, рівних кодовим словам.

Розглянемо завдання оптимізації декодування групової коди з двійковою матрицею кодування Е. Требуєтся мінімізувати вірогідність того, що  .

Схема декодування складається з групи G всіх слів, які можуть бути прийняті (#G=2n). Оскільки кодові слова B утворюють нормальну (нормальність виходить з комутативності G) підгрупу G, то безлічі G можна додати структуру таблиці: записуватимемо в один рядок ті елементи G, які є членами одного суміжного класу G по B. Перший рядок, відповідний нульовому слову з G, буде тоді всіма кодовими словами з B, тобто . У загальному випадку, якщо , то рядок, що містить gi (суміжний клас giB ), має вигляд

.

Лідером кожного з таких побудованих суміжних класів називається слово мінімальної ваги.

Кожен елемент g з G однозначно представляється у вигляді суми gi+bj де  - лідер відповідного суміжного класу і .

Безліч класів суміжності групи утворюють чинник-групу, яка є чинник-множина безлічі G по відношенню еквівалентності-приналежності до одного суміжного класу, а це означає, що множини, складові це чинник-множина, утворюють розбиття G. Звідси витікає, що рядки побудованої таблиці попарно або не перетинаються, або збігаються.

Якщо в даній таблиці в першому стовпці записати лідери, то отримана таблиця називається таблицею декодування. Вона має вигляд:

Те, що рядків буде 2n-m виходить з теореми Лагранжа1), оскільки 2n-m - це порядок фактор-группы G/B #(G/B)=#(G)/#(B), #B=2m.

Декодування слова g=bj+gi полягає у виборі кодового слова bj як переданий і подальшому застосуванні операції, зворотної множенню на E. Така схема декодування зможе виправляти помилки.

Для (3,6) -кода з даного прикладу таблиця декодування буде наступною:

Перший рядок в ній - це рядок кодових слів, а перший стовпець - це лідери.

Щоб декодувати слово bj+e, слід відшукати його в таблиці і вибрати як переданого слово в тому ж стовпці і в першому рядку.

Наприклад, якщо прийнято слово 110011 (2-й рядок, 3-й стовпець таблиці), то вважається, що було передане слово 010011; аналогічно, якщо прийнято слово 100101 (3-й рядок, 4-й стовпець таблиці), за передане вважається слово 110101, і так далі

Групове кодування з схемою декодування за допомогою лідерів виправляє всі помилки, рядки яких збігаються з лідерами. Отже, вірогідність правильного декодування переданої по двійковому симетричному каналу коди дорівнює сумі вірогідності всіх лідерів, включаючи нульовий.

У розглянутій схемі вірогідність правильної передачі слова буде

p6+6p5q+p4q2.

Кодове слово будь-якого стовпця таблиці декодування є найближчим кодовим словом до всіх інших слів даного стовпця.

Хай передане слово bi прийняте як bi+e, d(bi,bi+e)=u(e), тобто ця відстань дорівнює вазі відповідного лідера. Відстань від bi+e до будь-якого іншого кодового слова bj дорівнює вазі їх порозрядної суми, тобто

оскільки e- лідер суміжного класу, до якого належать як bk+e, так і bi+e.

Доведено, при схемі декодування лідерами по отриманому слову береться найближче до нього кодове.

Досконалі і квазідосконалі коди

Груповий  -код, що виправляє всі помилки ваги, не більшої k, і ніяких інших, називається досконалим.

Властивості досконалого коду:

1.                 Для досконалого  -кода, що виправляє всі помилки ваги, не більшої k, виконується співвідношення  . Вірно і зворотне твердження;

2.                 Досконалий код, що виправляє всі помилки ваги, не більшої k, в стовпцях таблиці декодування містить всі слова, віддалені від кодових на відстані, не більшому k. Вірно і зворотне твердження;

3.                 Таблиця декодування досконалого коду, що виправляє всі помилки в не більше ніж k позиціях, має як лідерів всі рядки, що містять не більш k одиниць. Вірно і зворотне твердження.

Досконалий код - це кращий код, що забезпечує максимум мінімальної відстані між кодовими словами при мінімумі довжини кодових слів. Досконалий код легко декодувати: кожному отриманому слову однозначно ставиться у відповідність найближчу кодову. Чисел m, n і , що задовольняють умові досконалості коди, дуже мало. Але і при підібраних m, n і k досконалий код можна побудувати тільки у виняткових випадках.

Якщо m, n і k не задовольняють умові досконалості, то кращий груповий код, який їм відповідає, називається квазідосконалим, якщо він виправляє всі помилки кратності, не більшої k, і деякі помилки кратності k+1. Квазідосконалі код також дуже мало.

Двійковий блоковий  -код називається оптимальним, якщо він мінімізує вірогідність помилкового декодування. Досконалий або квазідосконалий код - оптимальний. Загальний спосіб побудови оптимальних код поки невідомий.

Для будь-якого цілого позитивного числа r існує досконалий  -код, що виправляє одну помилку, званий кодом Хеммінга (Hamming), в якому  і  .

Дійсно

 .

Порядок побудови коди Хеммінга наступний:

1.                 Вибираємо ціле позитивне число r. Повідомлення будуть словами довжини , а кодові слова - довжини  ;

2.                 У кожному кодовому слові  r біт з індексами-ступенями двійки  - є контрольними, останні - в природному порядку - бітами повідомлення. Наприклад, якщо r=4, то биті  - контрольні, а  - з початкового повідомлення;

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.

Шукане кодове слово має вигляд

Далі потрібно обчислити контрольні суми.

Таким чином, шуканий код - 0011000111010. Якщо в процесі передачі цієї коди буде зіпсований його п'ятий біт, то приймач отримає код 0011100111010. Для його декодування знову обчислюються контрольні суми:

Приймач перетворить зміною п'ятого біта отримане повідомлення у відправлене передавачем, з якого потім відкиданням контрольних розрядів відновлює початкове повідомлення.

Досконалий код Хеммінга також можна будувати за розглянутою схемою, оскільки для нього  .

Для виправлення одинарної помилки до 8-розрядного коду досить приписати 4 розряди , до 16-розрядного - 5, до 32-розрядного - 6, до 64-розрядного - 7.

Висновки

1.                 Передача інформації по каналах зв'язку найчастіше пов'язана з рішенням задачі перешкодостійкого кодування. При цьому групове кодування є одним з можливих варіантів рішення даної задачі.

2.                 Коди, що виявляють помилку, і коди, що коректують, обов'язково мають додаткові символи (надмірні).

3.                 Матричне кодування є одним з економних способів опису схеми кодування.

4.                 Груповий код – це блоковий код, у якого кодові слова утворюють групу.

5.                 Одними з найбільш поширених перешкодостійких кодів є коди Хеммінга.

6.                 У реальних системах для кодування інформації застосовується квазідосконале кодування.

Література

1.                 Чисар И., Кернер Я. Теория информации. М.: Мир, 1985

2.                 Блейхер Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986

3.                 Питерсон Р., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976

Страницы: 1, 2