Згортальні коди

Згортальні завадостійкі коди

Лекція № 5.1

Теорія інформації та кодування

Вступ

Лекція № 5.1 − “Згортальні завадостійкі коди”. Цією лекцією розпочинаємо вивчення останнього, п’ятого, модуля дисципліни ТІК “Інформаційні системи. Системи і мережі передачі даних”. Модуль включає 3 теми: “Інформаційні та телекомунікаційні системи. Технології передачі інформації із зворотним зв’язком” обсягом 42 години, “Інформаційні та телекомунікаційні системи. Системи і мережі передачі даних” обсягом 10 годин, “Керування потоком інформаційних об’єктів. Комутація та маршрутизація в мережах” обсягом 6 годин, модульну контрольну роботу (2 год.) та розрахунково – графічну робота. Розрахунково – графічну робота слід здати на перевірку не пізніше ніж через 10 днів від цієї лекції. Невчасна здача РГР має своїм наслідком зниження максимальної оцінки до 10 балів.

По видам занять модуль має наступний розподіл: 9 лекційних (18 год., із яких 2 год. – МКР), 5 лабораторних (20 год.) заняття, і надає змогу набрати 53 бали (9 – за успішну працю на лекційних заняттях, 5•5 = 25 – за лабораторні заняття, 13 балів – за розрахунково – графічну роботу та 6 – за модульний контроль). Мінімальна кількість балів на оцінку “задовільно” – 31. При відсутності заохочувальних балів можна набрати: за лабораторні заняття – 5•3 = 15, за модульний контроль – 4 бали, за РГР – 8, що складає у сумі 27 балів. Отже при пропуску більше ніж 3 лекції вийти на оцінку “задовільно” складно.

В лекції будуть розглянуті наступні учбові питання:

1 Згортальні коди. 3

2 Згортальні ланцюгові коди. 5

3 Згортальні ґратчасті коди та алгоритм Вітербі 12

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

Рекурентними ці коди називаються тому, що співвідношення, що зв’язують перевірочні символи з інформаційними, справедливі для будь-якої ділянки інформаційної послідовності. В згортальні кодах так само, як і в блокових, виділяють класи систематичних і несистематичних кодів. Нагадаємо, що в словах систематичного коду відомі позиції з інформаційними і перевірочними символами.

Термін “згортальні коди” пояснюється тим, що кодове слово можна розглядати як згортку відгуку лінійної системи (кодера) і вхідний інформаційної послідовності. Тому згортальні коди є лінійними, для яких сума будь-яких кодових послідовностей також є кодовою послідовністю.

Структура слова систематичного згортального коду схематично зображено на рис. 1.

Рис. 1. Структура слова згортального коду

Не заштриховані ділянки відзначають позиції, на яких розташовані інформаційні символи (кадри), а заштриховані – позиції з перевірочними символами. Таким чином, кодове слово складається з елементарних блоків довжиною п з т інформаційними символами, що забезпечує швидкість m/n. При аналізі згортальних кодів зручно вважати, що інформаційні символи, які стоять на однакових позиціях в елементарних блоках, належать одній інформаційній послідовності. Таким чином, при використанні коду зі швидкістю m/n проводиться кодування λ інформаційних послідовностей. Кодування полягає у формуванні за певними правилами λ k – символьних перевірочних кадрів із λ m – символьних інформаційних послідовностей. Цей процес умовно показано на рис. 1 стрілками як зв’язки між перевірочними та інформаційними символами.

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

Для отримання слова систематичного коду треба по відомим інформаційним символам знайти перевірочні та розташувати їх на заданих позиціях елементарного блоку. Відомо багато алгоритмів згортального кодування. Для простоти їх розгляду покладемо λ = 1, тобто будемо кодувати одну послідовність інформаційних символів. Часто інформаційні послідовності, як і в циклічних кодах, представляються багаточленами:.

1. Перевірочні символи визначаються за відомими інформаційним з допомогою рекурентних співвідношень.

2. Згортальний код задається за допомогою графа і кодової решітки. Кодове слово зображується послідовним з'єднанням ребер графа, структура якого схожа на гіллясте дерево. Тому згортальні коди відносяться до класу деревовидних.

Ці варіанти такого кодування розглянемо в наступних запитаннях.

3. Послідовність перевірочних символів визначається за допомогою породжуючого багаточлена.

4. Для згортального коду можуть бути побудовані породжує і перевірочна матриці. У порівнянні з тими ж матрицями блочного коду ці матриці (як кодована і прийнята послідовності) напівнескінченних.