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

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

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

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

а) б)

	Рис. 4.1. Побудова перевіркової мат-риці – а) і її результат б) для коду (10.6)

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

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

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

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

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

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

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

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

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

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

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

1001011000 – перша строчка перевіркової матриці.

1101100000 Þ 1 Å 1 Å 0 Å 0 = 0 !

1101100001Þ !

1101100010Þ !

1101100011Þ !

1101100100Þ !

1101100101Þ !

1101100110Þ !

1101100111Þ !

1101101000Þ 1 Å 1 Å 0 Å 1 = 1 Х

1101101001Þ Х

1101101010Þ Х

1101101011Þ Х

1101101100Þ Х

1101101101Þ Х

1101101110Þ Х

1101101111Þ Х

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

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

1101100000 Þ 1 Å 1 Å 1 Å 0 = 1 Х !

1101100001Þ Х !

1101100010Þ Х !

1101100011Þ Х !

1101100100Þ 1 Å 1 Å 1 Å 1 = 0 ! !

1101100101Þ ! !

1101100110Þ ! !

1101100111Þ ! !

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

0111000010 – третя строчка перевіркової матриці.

1101100100 Þ 1 Å 0 Å 1 Å 0 = 0 ! ! !

1101100101Þ ! ! !

1101100110Þ 1 Å 0 Å 1 Å 1 = 1 Х ! !

1101100111Þ Х ! !

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

0010110001 – четверта строчка перевіркової матриці.

1101100100Þ 0 Å 1 Å 0 Å 0 = 1 Х ! ! !

1101100101Þ 0 Å 1 Å 0 Å 1 = 0 ! ! ! !

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

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

0000111101 Þ 0 Å 0 Å 1 Å 1 = 0 !

0000111101Þ 0 Å 0 Å 1 Å 1 = 0 !

0000111101Þ 0 Å 0 Å 0 Å 0 = 0 !

0000011101Þ 0 Å 0 Å 1 Å 1 = 0 !

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

0101010101Þ 0 Å 1 Å 1 Å 0 = 0 !

0101010101 Þ 0 Å 1 Å 0 Å 1 = 0 !

0101010101Þ 1 Å 0 Å 1 Å 0 = 0 !

0101010101Þ 0 Å 0 Å 1 Å 1 = 0 !

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

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

110110 000011 110110

Å Å Å

000011010101010101

110101 d_54–67 = 5 010110 d_67–85 = 3 100011 d_54–85 = 3.

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

1101100101 0000111101 1101100101

Å Å Å

00001111010101010101 0101010101

1101011010 d_54–67 = 6 0101101000 d_67–85 = 4 1000110000 d_54–85 = 3.

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

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

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

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

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

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

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

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

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

h²_зав = а²×t_с.зав /(2×N_о) = 20,8×4,65×10^-6/(2×2,5 10^-5) = 1,82.

Це дає (згідно рис. 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). Тому знання синдрому є необхідною і достатньою умовою для виправлення помилок у двійкових кодах.