Вибір корегуючого коду та розрахунок характеристик завадостійкого декодування

Запишемо кодові комбінації на виході завадостійкого кодера для трьох рівнів квантування – 35, 59, 76. Породжуюча матриця коду:

При утворенні кодових комбінацій в кодері і їх перевірці в декодері систематичних кодів будемо користуватися перевірковою матрицею Н. Візьмемо задану породжуючу матрицю для коду (10.6) і доповнимо її перевіркову частину (виділена курсивом) діагональною підматрицею (окреслена пунктиром). Отримана сумарна матриця розміром 4х10 і буде матрицею H¢. Оскільки процедура транспонування має просту геометричну інтерпретацію – обертання матриці відносно її головної діагоналі, знайдемо матрицю Н методом відповідної геометричної побудови. Виконавши її транспонування дістанемо шукану перевіркову матрицю Н для коду (10.6).

Результуюча матриця Н (на рис. 4.1–а вона окреслена штрихпунктиром) буде мати вигляд рис. 4.1–б.

а) б)

Знайдемо кодові комбінації завадостійкого коду для рівнів з номерами 35, 59, 76. Запишемо номери рівнів у простому двійковому коді, для чого переведемо їх у двійкову систему числення:

35₁₀ = 0× 2⁶+1× 2⁵+0× 2⁴+0× 2³+0× 2²+1× 2¹+1× 2⁰ =

= 0× 64+1× 32+0× 16+0× 8+0× 4+1× 2+1× 1 = 0100011₂

59₁₀ = 0× 2⁶+1× 2⁵+1× 2⁴+1× 2³+0× 2²+1× 2¹+1× 2⁰ =

= 0× 64+1× 32+1× 16+1× 8+0× 4+1× 2+1× 1 = 0111011₂

76₁₀ = 1× 2⁶+0× 2⁵+0× 2⁴+1× 2³+1× 2²+0× 2¹+0× 2⁰ =

= 1× 64+0× 32+0× 16+1× 8+1× 4+0× 2+0× 1 = 1001100₂

Оскільки в отриманих комбінаціях налічується більше ніж 6 знаків, опустимо їх старші розряди. Знайдемо для отриманих кодів комбінації систематичного коду (10.6), записавши всі можливі випадки і виконавши їх перевірку за допомогою перевіркової матриці. Одиничні розряди кодів у цій матриці вказують, що власне ці розряди вхідного коду потрібно додати по модулю 2 і в результаті отримати 0. Всі решта розряди комбінації до уваги не беруться. Якщо в результаті додавання отримано 0 (будемо помічати це символом!), вважається, що кодова комбінація пройшла перевірку на даній строчці перевіркової матриці. При одиничному результаті комбінація бракується (будемо помічати це символом Х) і не приймає участі в наступних перевірках як за допомогою даної, так і всіх інших строчок перевіркової матриці. Щоб бути допустимою, кодова комбінація повинна пройти перевірку у всіх строчках перевіркової матриці.

Операція додавання за модулем 2 виконується згідно наступних правил:

0 Å 0 = 0; 0 Å 1 = 1; 1 Å 0 = 1; 1 Å 1 = 0.

Для рівня 35 (кодова комбінація 100011) перевірка за першою строчкою перевіркової матриці дає старший розряд перевіркової частини:

1 00 1 0 11 000 – перша строчка перевіркової матриці.

1 00 0 1 10 000 Þ 1 Å 0 Å 1 Å 0 = 0!

1 00 0 1 10 001Þ!

1 00 0 1 10 010Þ!

1 00 0 1 10 011Þ!

1 00 0 1 10 100Þ!

1 00 0 1 10 101Þ!

1 00 0 1 10 110Þ!

1 00 0 1 10 111Þ!

1 00 0 1 11 000Þ 1 Å 0 Å 1 Å 1 = 1 Х

1 00 0 1 11 001Þ Х

1 00 0 1 11 010Þ Х

1 00 0 1 11 011Þ Х

1 00 0 1 11 100Þ Х

1 00 0 1 11 101Þ Х

1 00 0 1 11 110Þ Х

1 00 0 1 11 111Þ Х

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

11 00 1 00 1 00 – друга строчка перевіркової матриці.

10 00 1 10 0 00 Þ 1 Å 0 Å 1 Å 0 = 0 !!

10 00 1 10 0 01Þ !!

10 00 1 10 0 10Þ !!

10 00 1 10 0 11Þ !!

10 00 1 10 1 00Þ 1 Å 0 Å 1 Å 1 = 1 Х!

10 00 1 10 1 01Þ Х!

10 00 1 10 1 10Þ Х!

10 00 1 10 1 11Þ Х!

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

0 111 0000 1 0 – третя строчка перевіркової матриці.

1 000 1100 0 0 Þ 0 Å 0 Å 0 Å 0 = 0 !!!

1 000 1100 0 1Þ !!!

1 000 1100 1 0Þ 0 Å 0 Å 0 Å 1 = 1 Х!!

1 000 1100 1 1Þ Х!!

перевірка за четвертою строчкою перевіркової матриці, нарешті дає молодший (останній) розряд перевіркової частини, тобто повністю визначає кодову комбінацію:

00 1 0 11 000 1 – четверта строчка перевіркової матриці.

10 0 0 11 000 0 Þ 0 Å 1 Å 1 Å 0 = 0 !!!!

11 0 1 00 000 1 Þ 0 Å 1 Å 1 Å 1 = 1 Х!!!

Отже при кодуванні систематичним кодом (10.6) для інформаційної комбінації 100011 (номер рівня 35) допустимою кодовою комбінацією буде 1000110000.

Для інформаційної комбінації 111011 (номер рівня 59) перевірки у всіх строчках перевіркової матриці проходить кодова комбінація 1110110101, вона і буде допустимою:

1 11 0 1 10 101 Þ 1 Å 0 Å 1 Å 0 = 0!

11 10 1 10 1 01 Þ 1 Å 1 Å 1 Å 1 = 0 !!

1 110 1101 0 1Þ 1 Å 1 Å 0 Å 0 = 0!

11 1 0 11 010 1 Þ 1 Å 1 Å 1 Å 1 = 0!

Для інформаційної комбінації 001100 (з номеру рівня 76) перевірки у всіх строчках перевіркової матриці проходить кодова комбінація 0011001001, вона і буде допустимою:

0 01 1 0 01 001 Þ 0 Å 1 Å 0 Å 1 = 0!

00 11 0 01 0 01Þ 0 Å 0 Å 0 Å 0 = 0!

0 011 0010 0 1Þ 0 Å 1 Å 1 Å 0 = 0!

00 1 1 00 100 1 Þ 1 Å 0 Å 0 Å 1 = 0!

Визначимо кодові відстані між комбінаціями на вході кодера та між комбінаціями на його виході.

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

100011 111011 100011

Å Å Å

111011001100001100

011000 d_35–59 = 2 110111 d_59–76 = 5 101111 d_35–76 = 5.

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

1000110000 1110110101 1000110000

Å Å Å

111011010100110010010011001001

0110000101 d_35–59 = 4 1101111100 d_59–79 = 6 1011111001 d_35–79 = 7.

Коректуючі можливості коду. Для даного випадку маємо на вході завадостійкого кодера мінімальну кодову віддаль між кодовими комбінаціями 35 і 59 d_35–59 = 2, взагалі ж для простого двійкового коду d = 1, тобто існують дозволені комбінації, які відрізняються лише в одному розряді. Такий код, згідно теореми кодування, не має коректуючих можливостей і не дозволяє виявляти, а тим більше, виправляти помилки.

На виході кодера завадостійкого коду маємо найменшу кодову віддаль між кодовими комбінаціями 35 і 59 d_59–35 = 4, взагалі ж для коду (10.6) d = 3, тобто не існує дозволених кодових комбінацій, які відрізнялися б менш ніж у трьох розрядах. Такий код згідно теореми кодування дозволяє виявляти всі помилки кратністю q < 3, тобто одно- і двократні і деякі помилки з кратністю q ³ 3, а також виправляти помилки з кратністю 1.

Визначимо тривалість символу на виході кодера завадостійкого коду. Зменшення тривалості можна визначити, знаючи відносну швидкість коду R, яка показує відносне число дозволених кодових комбінацій у коді і розраховується за формулою

R = log₂ М_а /log₂ М = k/n.

Тривалість символу на виході кодера завадостійкого коду буде становити:

t_с.зав = t_с R = t_с (k/n) = 7, 94 (6/10) = 4, 76 мкс.

Вважаючи, що в каналі застосовується передача кодом (10.6), з тривалістю двійкових символів t_с.зав, знайдемо загальну імовірність помилки передачі двійкового символу p.

Без використання завадостійкого кодування в каналі передавалися б тільки інформаційні частини кодових комбінацій коду (10.6). Довжина кодової комбінації була б k = 6, тривалість двійкового символу t_с=7, 94 мкс, величина співвідношення сигнал/шум на виході демодулятора становила б h² = 6, 44 і загальна імовірність помилки була б p = 0, 1 (див. розділ 3).

Використання завадостійкого коду приводить до зменшення тривалості символу і зміни внаслідок цього співвідношення сигнал/шум:

h²_зав = а²× t_с.зав /(2× N_о) = 37, 3× 4, 76× 10^-6/(2× 2, 3 10^-5) = 3, 86.

Це дає (згідно рис. 3.1) загальну імовірність помилки p = 0, 19.

Імовірності помилок в кодовій комбінації кратністю q на вході декодера для гаусового каналу, при імовірності помилки передачі двійкового символу p розраховуються з використанням біномінального закону: p_n(q) = C_n^q p^q(1–p)^n-q, де n – довжина кодової комбінації; C_n^q = n! /[q! (n–q)! ] – число сполучень із n по q.

Використовучи формулу біномінального закону для однократних та двократних помилок на вході декодера для коду (10.6) (n = 10) будемо мати відповідно:

p₁₀(1) = C₁₀¹ p (1– p)⁹ = 10! /[1! (9)! ] p (1– p)⁹ = 10 p (1–p)⁹ =

= 10× 0, 19 (1– 0, 19)⁹ = 0, 285;

p₁₀(2) = C₁₀² p² (1– p)⁸ = 10! /[2! (8)! ] p²(1– p)⁸ = (90/2) p² (1–p)⁸ =

= (90/2)× 0, 19² (1– 0, 19)⁸ = 0, 301.

Корисний ефект від використання коректуючих кодів полягає в зменшенні імовірності помилки декодування кодових комбінацій Р_пд, під якою розуміють імовірність помилки кодової комбінації на виході декодера, яка в разі незалежних помилок символів розраховуютєся за формулою

де n – довжина кодової комбінації; q_в– кратність виправлених помилок; С_n^і = n! /і! (n-і)!. число сполучень із n по і; р – імовірність помилки символу на вході декодера.

Використання коректуючого коду буде технічно доцільним, якщо в результаті його введення імовірність помилки декодування Р_пд кодової комбінації зменшиться, незважаючи на підвищення імовірності помилок її символів. В даному випадку імовірність помилки символів зросла від 0, 1 до 0, 19 а імовірність однократної помилки декодування Р_пд кодової комбінації при цьому зменшується від 0, 387 до 0, 285 бо

p₁₀(1)_{0, 1} = C₁₀¹ p (1– p)⁹ = 10! /[1! (9)! ] p (1– p)⁹ = 10× 0, 1 (1– 0, 1)⁹ = 0, 387.

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

Виправлення однократних помилок. При виправленні однократних помилок застосовують синдромне декодування. Термін " синдром" у теорії кодування визначає сукупність ознак, характерних для кожної певної конфігурації помилок. Тому під синдромом кодурозуміють контрольне число s(s₁, s₂,..., s_r), що свідчить про наявність помилок і їх розташування (конфігурацію) у кодовій комбінації. Відзначимо, що у двійковому коді синдром записується у двійковій системі числення, тобто його розряди s₁, s₂,..., s_r приймають значення 0 або 1. Нульовий синдром вказує на те, що кодова комбінація є дозволеною, тобто виявлених помилок нема. Ненульовому синдрому відповідає певне (визначене раніше) розміщення помилок, які й виправляються.

Для двійкових кодів виправлення помилок провадиться єдиним способом – інверсією символів (0 замінюється на 1 і, навпаки, 1 – на 0). Тому знання синдрому є необхідною і достатньою умовою для виправлення помилок у двійкових кодах.