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

 

Запишемо кодові комбінації на виході завадостійкого кодера для трьох рівнів квантування – 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) перевірка за першою строчкою перевіркової матриці дає старший розряд перевіркової частини:

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

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

1 10 1 1 00 001Þ!

1 10 1 1 00 010Þ!

1 10 1 1 00 011Þ!

1 10 1 1 00 100Þ!

1 10 1 1 00 101Þ!

1 10 1 1 00 110Þ!

1 10 1 1 00 111Þ!

1 10 1 1 01 000Þ 1 Å 1 Å 0 Å 1 = 1 Х

1 10 1 1 01 001Þ Х

1 10 1 1 01 010Þ Х

1 10 1 1 01 011Þ Х

1 10 1 1 01 100Þ Х

1 10 1 1 01 101Þ Х

1 10 1 1 01 110Þ Х

1 10 1 1 01 111Þ Х

 

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

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

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

11 01 1 00 0 01Þ Х!

11 01 1 00 0 10Þ Х!

11 01 1 00 0 11Þ Х!

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

11 01 1 00 1 01Þ !!

11 01 1 00 1 10Þ !!

11 01 1 00 1 11Þ !!

 

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

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

1 101 1001 0 0 Þ 1 Å 0 Å 1 Å 0 = 0 !!!

1 101 1001 0 1Þ !!!

1 101 1001 1 0Þ 1 Å 0 Å 1 Å 1 = 1 Х!!

1 101 1001 1 1Þ Х!!

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

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

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

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

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

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

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

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

0 000 1111 0 1Þ 0 Å 0 Å 0 Å 0 = 0!

00 0 0 01 110 1 Þ 0 Å 0 Å 1 Å 1 = 0!

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

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

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

0 101 0101 0 1Þ 1 Å 0 Å 1 Å 0 = 0!

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