Рекурентні коди
Рекурентні (безперервні) ланцюгові коди.
Кодування кожного ai здійснюється індивідуально.
Рекурентні кодипризначені в основному для виправлення пакетів помилок.
Операції кодування та декодування здійснюються над безперервною послідовністю символів.
1. При дії у к.с. ( канал зв'язку ) пачок помилок даний метод має суттєві переваги передблоковимикодами, тому що надає великі можливості для найбільш повного використання введеної надмірності .
Пояснення: Для блокових кодів можливості виявлення та виправлення визначаються надмірністю, яка введена в цю кодову комбінацію. Оскільки помилки зустрічаються відносно рідко, надмірність більшості кодових комбінацій не використовується. У той самий час у разі пачки помилок введеної надмірності бракує.
При застосуванні рекурентних кодів досягається усереднення впливу перешкоди на велику послідовність інформаційних символів.
У рекурентних кодах, так само як і в блокових, перевірочні символи виходять в результаті проведення лінійних операцій (найчастіше підсумовування mod2) над певними інформаційними символами.
У процесі кодування перевірочні символи розміщуються між інформаційними так, щоб на кожніkінформаційних символів, що безперервно передаються, доводилосяrперевірочних.
Структуру рекурентного коду, розміщення перевірочних та інформаційних символів у загальній кодовій послідовності розглянемо з прикладу ланцюгових кодів.
Ланцюгові коди– найпростіші рекурентні коди, що мають коефіцієнт надмірності :r/n=0.5. Т. е. коди, що мають однакове числоінформаційних та перевірочних символів
Коригувальні здібності коду визначаються параметром, який називаєтьсякроком додавання:t.
Крок додавання–відстань між двома інформаційними елементами, що підсумовуються по mod 2 для отримання перевірочних елементів bj.
Розглянемо процедури кодування та декодування і через основний параметр tвизначимо структуру та основні параметри ланцюгового коду.
Структурна схема кодуючого пристрою
Кожен інформаційний елемент ai бере участь у формуванні 2хперевірочних елементівbi:
Разом про те, кожен перевірочний елемент формується двома інформаційними ai+2t , ai+t. Т.о.
кількість інформаційних i> і проверочныхi>елементів в кодовій послідовності, що надходить у к. с. – завжди однаково.
Перевірка на наявність помилки (і коригування у разі наявності) здійснюється для кожного ai– індивідуально на приймальній стороні декодуючого пристрою.
Структурна схема декодуючого пристрою
Примітка: ai, bi – до вступу до к.с.
з можливими помилками
Основний принцип перевірки – дуже простий: формування bi-нов та порівняння з виділеними символами: bi'.
Наявність не порівняння є ознакою помилки .
Для ланцюгових кодів ( k=r=1 ) перевірка на наявність помилок здійснюється для кожногоaiіндивідуально.
Ця перевірка проводиться відповідно до формул:
4. Аналізуючи отриманий вираз, визначимоалгоритмкорекції та структуруланцюгового коду.
а.) У коригуванні ai беруть участь ai+t', ai-t', bi-t', bi-2t', які в кодовій послідовності розташовані наступним чином:
При цьому можливі таківаріанти:
а.)ai' –помилковий.Тоді це однозначно може бути виявлено в тому випадку, якщо всі інші елементи, що входять до формулу (**) – прийняти без помилок.
Тоді: 1.) Ознакою того, що ai' – помилковий, є: L1=1, L2=1 => F=L1L2=1
2.) Пакет помилок не повинен «накривати» разом сai – ai+t, ai-t, bi-t, bi-2t, а це накладає обмеження на можливу довжину пакета помилок: l 2t.
При цьому ai прийнятий правильно, і він проходить без жодної корекції.
в.) Можливий випадок, як у кодової послідовності (у виділеному нами вище фрагменті) помилковими виявилися крайні : ai+t иbi-2t (інші правильні) – випадок початку однієї пачки і кінця інший. З формули (**), маємо F=1 і коригуємоai(за алгоритмом п.ai-ого), що єпомилковим. Щоб не відбувалося помилкового виправлення символів – вимога до інтервалу між пачками помилок:
Відстань між останнім символом попередньої пачки помилок та першим символом наступної пачки помилок L повинна задовольняти співвідношення :
L 3*2t+1 ( 3*2t – довжина відтворюваного фрагмента,
всередині якого здійснюється корекція ai)
Структура ланцюгового коду.
Як конкретний приклад побудуємо функціональні схеми кодуючого та декодуючого пристроїв ланцюгового коду, що виправляє 4-х розрядні пакети помилок:
Функціональна схема кодуючого пристрою.