10.4  Синдромне декодування лінійних блокових кодів

К оглавлению
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

 

                Нехай u=(u1, u2, …, un) - передане кодове слово; е=(е1, е2, …, еn) - вектор помилок; y=(y1, y2, … yn) - прийнята послідовність. Тоді  y=u+е.

                Кодовий синдром

S=y=(u+e)=u+e=0+e=e,

оскільки для будь-якого кодового слова u=0.

Таким чином, кодовий синдром залежить лише від вектора помилок і не залежить від переданого слова.

Визначивши координати вектора помилок, можна відновити кодове слово так:  u*=y+е.

Приклад 4  Знайдемо значення синдрому для всіх можливих однократних помилок в послідовності з семи символів для наведеного прикладу лінійного блокового (4, 7)- коду.

 

1) e0=(0000000),

е0=(0000000)=(000) -  помилки немає;

2) е1=(1000000),

е1=(1000000)=(110) - помилка у 1-му  біті;

3) e2=(0100000),

е2=(0100000) =(011) - помилка у 2-му біті;

4) е3=(0010000),

е3=(0010000)=(111) - помилка у 3-му біті;

5) е4=(0001000),

е4=(0001000)=(101) - помилка у 4-му  біті;

6) е5=(0000100),

е5=(0000100)=(100) - помилка у 5-му біті;

7) е6=(0000010),

е6=(0000010)=(010) - помилка у 6-му  біті;

8) е7=(0000001),

е7=(0000001) =(001) - помилка у 7-му біті.

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

Приклад 5  З перевірної матриці лінійного блокового (4, 7)- коду знайдемо систему перевірних рівнянь:

               

Звідси

 

де (m1, m2, m3, m4) – інформаційні символи; r1, r2, r3 - перевірні символи; (u1, u2, …, u7)=(m1, m2, m3, m4, r1, r2, r3) - кодове слово.

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

Наприклад, якщо помилка у четвертому розряді кодової комбінації u=(u1, u2, u3, u4, u5, u6, u7)=(m1, m2, m3, m4, r1, r2, r3), то не виконаються перше і третє рівняння, в які входить помилковий символ u4=m4. Вектором синдрому буде послідовність S=(101), що збігається з четвертим стовпцем перевірної матриці коду H.

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

Зазначимо, що кодовий синдром виправляє тільки однократні помилки в коді.

Приклад 6  Припустимо, що в прийнятій послідовності виникла не одна, а дві помилки, наприклад, у другому і шостому бітах: е=(0100010).

Тоді вектор синдрому

S=(0100010)=(001).

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

Отже, лінійний блоковий (4, 7) - код не виправляє двократні помилки і помилки більшої кратності.