Зразки розв'язування задач до розділу 9

 

Приклад 1  Завадостійкий код заданий твірною матрицею вигляду

.

Побудувати таблицю кодів;

Описати основні характеристики коду: мінімальну відстань між словами, ймовірність невиявлення помилки, максимальну кратність помилок, які можуть бути виявлені й виправлені кодом;

Побудувати таблицю декодування;

Уточнити можливості коду з виявлення і виправлення помилок: знайти ймовірність правильної передачі закодованого повідомлення і описати помилки, що виправляються кодом;

Як будуть декодовані слова: 10001, 01110, 10111?

Розв'язання

                Кодові слова завадостійкого коду, заданого твірною матрицею Gkn, мають довжину n символів і визначаються так: ,

де через m позначено інформаційну послідовність довжиною k .

                За умовою задачі завадостійкий код заданий твірною матрицею вигляду

,

    I22     P23

що складається з одиничної частини Ikk і перевірочної частини Pk(n-k). Одинична матриця відповідає  інформаційним символам кодового слова, перевірочна – визначає перевірні символи.

                Отже, кодові слова даного коду будуються так:

                ,

де перші два символи інформаційні, а наступні три є контрольними сумами r1, r2, r3.

                Побудуємо таблицю кодових слів заданого коду й оцінимо їхню ймовірність (mабл. 1).

                                 Таблиця 1 

Інформаційна

послідовність        Кодове слово        Імовірність

000          00 000    

01            01 110     p2q3

10            10 101     p2q3

11            11 011     pq4

               

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

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

                Опишемо основні характеристики заданого коду.

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

                У даному випадку мінімальна вага кодових слів у твірній матриці дорівнює 3, отже, мінімальна відстань Хеммінга dmin=3.

                Помилки лінійним блоковим кодом не будуть виявлені у тих випадках, якщо під впливом завад одне кодове слово перетвориться в інше кодове слово даного коду. Виходячи з того, що кодове слово лінійного коду є лінійною комбінацією двох інших кодових слів, ймовірність того, що одне кодове слово перетвориться в інше, визначається ймовірністю того, що вектор помилок збігається з одним із кодових слів коду (прийнята послідовність y=u+e, де u – передане кодове слово; e – вектор помилок у двійковому каналі). Таким чином, імовірність невиявлення помилок заданим кодом буде такою (див. табл. 1):

Pпом=2p2q3+pq4.

                Кратність помилок, що виявляються лінійним блоковим кодом, визначається за нерівністю

dmin  l+1,

де l – кратність помилок; dmin – мінімальна відстань коду.

                Звідси максимальна кратність помилок, що виявляються заданим кодом,  l  dmin–1=3-1=2.

                Кратність помилок, що виправляються лінійним блоковим кодом, визначається за нерівністю

dmin  2l+1.

                Звідси максимальна кратність помилок, що виправляються заданим кодом,  l  (dmin –1)/2=1.

                Побудуємо таблицю декодування (табл. 2). Для цього в першому рядку таблиці випишемо всі кодові слова, а в лівому стовпці – значення вектора помилок. Можливі прийняті комбінації – це слова, записані у відповідних рядках і стовпцях таблиці.

      Таблиця 2

Вектор помилок    Кодові слова

00000      01110      10101      11011

00001      01111      10100      11010

00010      01100      10111      11001

00100      01010      10001      11111

01000      00110      11101      10011

10000      11110      00101      01011

               

                Якщо продовжити цю таблицю далі для всіх можливих комбінацій з двома помилками, можна побачити, що однозначної відповідності між переданими послідовностями і відповідними кодовими словами вже не буде, тобто виправити помилки кратності 2 заданим кодом неможливо. Таким чином, імовірність правильної передачі кодового слова довжиною 5 символів

.

                Для того щоб декодувати прийняту послідовність y=uj+ei, де uj – передане кодове слово; ei – вектор помилок у каналі, потрібно відшукати її в таблиці декодування й вибрати як передане кодове слово в тому самому стовпці і у першому рядку. У такий спосіб декодуємо задані комбінації:

                               10001 10101 10;

                               01110 01110 01;

                               10111 10101 10.

Приклад 2  Для кодування послідовності з k=12 інформаційних елементів застосовується ітеративний метод. Записати твірну матрицю еквівалентного лінійного блокового коду. Закодувати повідомлення (110111000110). Виправити помилку в прийнятій послідовності (11011110001110001111). Визначити надлишковість коду.

Розв'язання

                Інформаційну послідовність розмістимо у вигляді матриці розмірністю 34. Дописуємо до кожного рядка і стовпця матриці перевірний елемент контролю на парність.

                У загальному вигляді такий спосіб кодування інформаційної послідовності (m1, m2, … , m12) подамо так:

,                ()

де r1, r2, …, r8 – перевірні елементи.

                Записавши матрицю () по рядках, отримуємо послідовність, що зберігається або передається по каналу зв’язку, u= (m1, m2, m3, m4, r1, m5, m6, m7, m8, r2, m9, m10, m11, m12, r3, r4, r5, r6, r8).

                З матриці () отримуємо систему перевірних рівнянь, що визначає правила знаходження перевірних елементів:

                                                  ()

                Скориставшись системою перевірних рівнянь (), знаходимо твірну матрицю G1220 еквівалентного лінійного блокового коду, яку можна легко привести до канонічного вигляду, розмістивши стовпці, що відповідають перевірним елементам у правій частини твірної матриці, а одиничну підматрицю, що визначає інформаційну частину кодового слова – у лівій:

 

1              1              0              1

1              1              0              0

0              1              1              0

1              1              0              1              1             

1              1              0              0              0             

0              1              1              0              0              .

0              1              1              1              1             

                Закодуємо задану інформаційну послідовність m=(110111000110).

                Розмістимо її у вигляді матриці 34 і допишемо перевірні елементи до кожного рядка і стовпця:

 

 

 

Отже, кодовим слово буде (11011110000110001111).

                Згідно з умовою задачі на прийомній стороні прийнята послідовність (11011110001110001111). Декодуємо її за ітеративним методом.

                Запишемо прийняте слово у вигляді матриці (у даному випадку розмірністю 45) і виконаємо перевірку на парність за її кожним рядком і стовпчиком. У разі відсутності помилки контрольні елементи парності за рядками і стовпчиками матриці мають значення 0. Невиконання контролю парності у стовпчику і рядку однозначно визначить координати помилкового елемента – це дозволить його виправити.

1              1              0              1              1              0             

1              1              0              0              0              0             

1              1              1              0              0              1              .

0              1              1              1              1              0             

1              0              0              0              0              1             

 

1              1              0              1              1

1              1              0              0              0

1              1              1              0              0

0              1              1              1              1

 

         

 

 

 

 

                У даному випадку не виконується контроль парності в третьому рядку й першому стовпці, тобто помилковий елемент m [3, 1]. Виправляємо помилку, змінивши значення помилкового елемента на протилежне:

1              1              0              1              1

1              1              0              0              0

1              1              1              0              0

0              1              1              1              1

1              1              0              1              1             

1              1              0              0              0             

0              1              1              0              0              .

0              1              1              1              1             

 

                  

 

 

                Отже, виправлена комбінація така:

y=(11011110000110001111).

                Декодуємо її, прибравши перевірні елементи:

(11011110000110001111)  (110111000110).

                Надлишковість коду .