Визначення і способи задання групових кодів (стр. 2 из 3)

Припустимо, що

.

Тоді для b=b₁…b_n=aE,

, отримуємо

тобто

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

Блоковий код називається груповим, якщо його кодові слова утворюють групу.

Більшість код, що коректують, є лінійними кодами. Лінійні коди - це такі коди, у яких контрольні символи утворюються шляхом лінійної комбінації інформаційних символів. Крім того, що коректують коди є груповими кодами. Групові коди (G_n) - це такі коди, які мають одну основну операцію. При цьому, повинна дотримуватися умова замкнутості (тобто, при складанні двох елементів групи виходить елемент що належить цій же групі). Число розрядів в групі не повинне збільшуватися. Цій умові задовольняє операція порозрядного складання по модулю 2. У групі, крім того, має бути нульовий елемент.

Наприклад, нижче приведені кодові комбінації, що є групою чи ні.

1) 1101 1110 0111 1011 – не група, оскільки немає нульового елементу

2) 0000 1101 1110 0111 – не група, оскільки не дотримується умова замкнутості (1101+1110=0011)

3) 000 001 010 011 100 101 110 111 - група

4) 000 001 010 111 - підгрупа

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

Це витікає із співвідношення

.

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

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

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

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

.

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

. У загальному випадку, якщо , то рядок, що містить g_i (суміжний клас g_iB ), має вигляд

.

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

Кожен елемент g з G однозначно представляється у вигляді суми g_i+b_j де

- лідер відповідного суміжного класу і .

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

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

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

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

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

000000	100110	010011	110101	001111	101001	011100	111010
100000	000110	110011	010101	101111	001001	111100	011010
010000	110110	000011	100101	011111	001101	001100	101010
001000	101110	011011	111101	000111	100001	010100	110010
000100	100010	010111	110001	001011	101101	011000	111110
000010	100100	010001	110111	001101	101011	011110	111000
000001	100111	010010	110100	001110	101000	011101	111011
000101	100011	010110	11000	001010	101100	011001	111111

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

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

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

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

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

p⁶+6p⁵q+p⁴q².

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

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

оскільки e- лідер суміжного класу, до якого належать як b_k+e, так і b_i+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, то биті - контрольні, а - з початкового повідомлення;