Вибір корегуючого коду та розрахунок характеристик завадостійкого декодування
Запишемо кодові комбінації на виході завадостійкого кодера для трьох рівнів квантування – 54, 67, 85. Породжуюча матриця коду:
![]() |
При утворенні кодових комбінацій в кодері і їх перевірці в декодері систематичних кодів будемо користуватися перевірковою матрицею Н. Візьмемо задану породжуючу матрицю для коду (10.6) і доповнимо її перевіркову частину (виділена курсивом) діагональною підматрицею (окреслена пунктиром). Отримана сумарна матриця розміром 4х10 і буде матрицею H¢. Оскільки процедура транспонування має просту геометричну інтерпретацію – обертання матриці відносно її головної діагоналі, знайдемо матрицю Н методом відповідної геометричної побудови. Виконавши її транспонування дістанемо шукану перевіркову матрицю Н для коду (10.6).
Результуюча матриця Н (на рис. 4.1–а вона окреслена штрихпунктиром) буде мати вигляд рис. 4.1–б.
![]() | |||
![]() | |||
а) б)
|
Знайдемо кодові комбінації завадостійкого коду для рівнів з номерами 54, 67, 85. Запишемо номери рівнів у простому двійковому коді, для чого переведемо їх у двійкову систему числення:
5410 = 0×26+1×25+1×24+0×23+1×22+1×21+0×20 =
= 0×64+1×32+1×16+0×8+1×4+1×2+0×1 = 01101102
6710 = 1×26+0×25+0×24+0×23+0×22+1×21+1×20 =
= 1×64+0×32+0×16+0×8+0×4+1×2+1×1 = 10000112
8510 = 1×26+0×25+1×24+0×23+1×22+0×21+1×20 =
= 1×64+0×32+1×16+0×8+1×4+0×2+1×1 = 10101012
Оскільки в отриманих комбінаціях налічується більше ніж 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 d54–67 = 5 010110 d67–85 = 3 100011 d54–85 = 3.
Для кодових комбінацій на виході кодера завадостійкого коду кодові віддалі між усіма парами комбінацій будуть такими:
1101100101 0000111101 1101100101
Å Å Å
00001111010101010101 0101010101
1101011010 d54–67 = 6 0101101000 d67–85 = 4 1000110000 d54–85 = 3.
Коректуючі можливості коду.Для даного випадку маємо на вході завадостійкого кодера мінімальну кодову віддаль між кодовими комбінаціями 67 і 85 d67–85 = 3, взагалі ж для простого двійкового коду d = 1, тобто існують дозволені комбінації, які відрізняються лише в одному розряді. Такий код, згідно теореми кодування, не має коректуючих можливостей і не дозволяє виявляти, а тим більше, виправляти помилки.
На виході кодера завадостійкого коду маємо найменшу кодову віддаль між кодовими комбінаціями 54 і 67 d54–85 = 3, взагалі ж для коду (10.6) d = 3, тобто не існує дозволених кодових комбінацій, які відрізнялися б менш ніж у трьох розрядах. Такий код згідно теореми кодування дозволяє виявляти всі помилки кратністю q < 3, тобто одно- і двократні і деякі помилки з кратністю q ³ 3,а також виправляти помилки з кратністю 1.
Визначимо тривалість символу на виході кодера завадостійкого коду. Зменшення тривалості можна визначити, знаючи відносну швидкість коду R, яка показує відносне число дозволених кодових комбінацій у коді і розраховується за формулою
R = log2 Ма /log2 М = 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 мкс, величина співвідношення сигнал/шум на виході демодулятора становила б h2 = 3,22 і загальна імовірність помилки була б p = 0,1 (див. розділ 3).
Використання завадостійкого коду приводить до зменшення тривалості символу і зміни внаслідок цього співвідношення сигнал/шум:
h2зав = а2×tс.зав /(2×Nо) = 20,8×4,65×10-6/(2×2,5 10-5) = 1,82.
Це дає (згідно рис. 3.1) загальну імовірність помилки p = 0,19.
Імовірності помилок в кодовій комбінації кратністю q на вході декодера для гаусового каналу, при імовірності помилки передачі двійкового символу p розраховуються з використанням біномінального закону: pn(q) = Cnq pq(1–p)n-q, де n – довжина кодової комбінації; Cnq = n!/[q!(n–q)!] – число сполучень із n по q.
Використовучи формулу біномінального закону для однократних та двократних помилок на вході декодера для коду (10.6) (n = 10) будемо мати відповідно:
p10(1) = C101 p (1– p)9 = 10!/[1!(9)!] p (1– p)9 = 10 p (1–p)9 =
= 10×0,19 (1– 0,19)9 = 0,285
p10(2) = C102 p2 (1– p)8 = 10!/[2!(8)!] p2(1– p)8 = (90/2) p2 (1–p)8 =
= (90/2)×0,192 (1– 0,19)8 = 0,301.
Корисний ефект від використання коректуючих кодів полягає в зменшенні імовірності помилки декодування кодових комбінацій Рпд, під якою розуміють імовірність помилки кодової комбінації на виході декодера, яка в разі незалежних помилок символів розраховуютєся за формулою
де n – довжина кодової комбінації; qв– кратність виправлених помилок; Сnі = n!/і!(n-і)!. число сполучень із n по і; р – імовірність помилки символу на вході декодера.
Використання коректуючого коду буде технічно доцільним, якщо в результаті його введення імовірність помилки декодування Рпд кодової комбінації зменшиться, незважаючи на підвищення імовірності помилок її символів. В даному випадку імовірність помилки символів зросла від 0,1 до 0,19 а імовірність однократної помилки декодування Рпд кодової комбінації при цьому зменшується від 0,387 до 0,285 бо
p10(1)0,1 = C101 p (1– p)9 = 10!/[1!(9)!] p (1– p)9 = 10×0,1 (1– 0,1)9 = 0,387.
Отже, використання коректуючого коду буде технічно доцільним.
Виправлення однократних помилок. При виправленні однократних помилок застосовують синдромне декодування. Термін "синдром" у теорії кодування визначає сукупність ознак, характерних для кожної певної конфігурації помилок. Тому під синдромом кодурозуміють контрольне число s(s1, s2,..., sr), що свідчить про наявність помилок і їх розташування (конфігурацію) у кодовій комбінації. Відзначимо, що у двійковому коді синдром записується у двійковій системі числення, тобто його розряди s1, s2,..., sr приймають значення 0 або 1. Нульовий синдром вказує на те, що кодова комбінація є дозволеною, тобто виявлених помилок нема. Ненульовому синдрому відповідає певне (визначене раніше) розміщення помилок, які й виправляються.
Для двійкових кодів виправлення помилок провадиться єдиним способом – інверсією символів (0 замінюється на 1 і, навпаки, 1 – на 0). Тому знання синдрому є необхідною і достатньою умовою для виправлення помилок у двійкових кодах.