Побудова перевіркової матриці.
Тема: Побудова кодових комбінацій систематичних кодів.
Зміст
2 Знаходження кодових комбінації коду (7.4)
При утворенні кодових комбінаційв кодері і їх перевірці в декодері систематичних кодів користуються перевірковою матрицею Н. Перевіркова матриця - це матриця розміром [n·(n-k)]. Вона будується на основі породжуючої за наступним правилом: GH' = 0. Тут G - породжуюча, Н' - транспонована перевіркова матриці.
Побудуємо матрицю Н, приймаючи до уваги, що транспонованою до матриці Н' ≡ [bik] розміром m стовпчиків на n рядків [m x n] є матриця Н' розміром [n х m] така, що Н' ≡ [bki].
Для отримання Н з породжуючої матриці спочатку знайдемо Н'. Для цього потрібно (див. рис. 8.1) доповнити надлишкову (перевіркову) частину породжуючої матриці (стовпчики від k до п) діагональною підматрицею розміром (n-k). Виділена (курсивом) доповнена надлишкова частина і буде шуканою матрицею Н'. Для отримання перевіркової матриці Н потрібно транспонувати Н'.
а)
б)
Рисунок 8.1. Побудова перевіркової матриці: а) і її результат б) для коду (7.4)
Візьмемо задан
у породжуючу матрицю для коду (7.4) і доповнимо її перевіркову частину (виділена курсивом) діагональною підматрицею (окреслена пунктиром). Отримана сумарна матриця розміром 3x7 і буде матрицею Н'. Оскільки процедура транспонування має просту геометричну інтерпретацію - обертання матриці відносно її головної діагоналі, знайдемо матрицю Н методом відповідної геометричної побудови. Виконавши транспонування дістанемо шукану перевіркову матрицю Н для коду (7.4). Результуюча матриця Н (на рис. 8.1-а вона окреслена штрихпунктиром) буде мати вигляд рис. 8.1-б.
Одиничні розряди кодів у цій матриці вказують, що власне ці розряди аналізованого слова потрібно додати за модулем 2 і в результаті отримати 0. Всі решта розряди комбінації до уваги не беруться. Якщо в результаті додавання отримано 0 (будемо помічати це символом !), вважається, що кодова комбінація пройшла перевірку на даному рядку перевіркової матриці. При одиничному результаті комбінація бракується (будемо помічати це символом X) і не приймає участі в наступних перевірках як за допомогою даної, так і всіх інших рядків перевіркової матриці. Щоб бути допустимою, кодова комбінація повинна пройти перевірку у всіх рядках перевіркової матриці.
Операція додавання за модулем 2 виконується згідно наступних правил:
Знайдемо кодові комбінації примітивного коду для рівнів з номерами 5,9, 12. Запишемо номери рівнів у простому двійковому коді, для чого переведемо їх у двійкову систему числення:
Для рівня5 перевірка за першим рядком перевіркової матриці дає:
Перевірказа другим рядком перевіркової матриці:
Перевірказа третім рядком перевіркової матриці:
Отже, при кодуванні систематичним кодом (7.4) для інформаційної комбінації 0101 (номер рівня 5) допустимою кодовою комбінацією буде 0101110.
Для інформаційної комбінації 1001 (номер рівня 9) перевірки у всіх рядках перевіркової матриці проходить кодова комбінація 1001011, вона і буде допустимою:
Для інформаційної комбінації 1100 (номер рівня 12) перевірки у всіх рядках перевіркової матриці проходить кодова комбінація 1100101, вона і буде допустимою:
Контрольні питання:
1 Що означає позначення - (n.k)-код, яке використовується для систематичних кодів?
2 Як утворюємо кодові комбінації систематичних кодів в кодері і перевіряємо їх в декодері?
3 Чому дорівнює пропускна здатність ідеального каналу?
4 Скільки рядків у перевіркової матриці і що вказують розряди її кодів?
5 Як виконується перевірка кодової комбінації?