Понятие о сверточных кодах

ИТЕРАТИВНЫЕ КОДЫ

Итеративные коды широко применяются в системах передачи данных из-за простоты реализации. Код получают путем представления последовательности информационных символов в виде двумерного массива. Затем каждая строка массива и каждый столбец кодируются некоторым кодом, причем необязательно одним и тем же.

Кодовое расстояние d_min такого кода равно произведению кодовых расстояний используемых итерируемых кодов.

Рассмотрим итеративный код с проверкой на четность по каждой строке и каждому столбцу. Кодовые комбинации информационных символов представлены в коде ASCII.

Код с проверкой на четность имеет кодовое расстояние d_min=2, соответственно для итеративного кода d_min=4. Полученный итеративный код исправляет одиночные ошибки и обнаруживает любые комбинации ошибок нечетного веса. Ошибки четного веса в пределах одной строки обнаруживаются при помощи проверок по столбцам. Четное число ошибок в пределах одного столбца обнаруживается при помощи проверок по строкам. Не обнаруживается любой набор из 4-х ошибок, образующих прямоугольник.

В настоящее время в системах передачи данных очень широко используется сверточное кодирование вместе с декодированием по алгоритму Витерби. Алгоритм Витерби представляет собой декодирование по максимуму правдоподобия и используется для исправления одиночных ошибок.

Сверточные коды являются непрерывными, то есть относятся к классу древовидных кодов. Символы последовательности на выходе кодера такого кода образуются путем суммирования по модулю 2 каждого информационного символа с некоторым набором предыдущих символов.

Кодирующее устройство сверточного кода в общем виде представлено ниже.

При поступлении на вход кодера каждого информационного символа U_i мультиплексор М последовательно считывает за один такт сигналы с выходов всех сумматоров по модулю 2, формируя на выходе m символов V_i. Таким образом, при скорости входной последовательности В_вх бит/с скорость выходной последовательности составляет В_вых=mВ_вх бит/с.

Для задания схемы кодера сверточного кода можно воспользоваться двоичными коэффициентами g_ij:

· Если g_ij =1, значит i -я ячейка регистра сдвига РС имеет связь с j -м сумматором.

· Если g_ij =0, значит i -я ячейка регистра сдвига РС не имеет связи с j -м сумматором.

Совокупность связей i-й ячейки РС с сумматорами представляют в виде двоичного вектора G_i=(g_i1, g_i2, ….,g_im), 0<=i<=N-1.

Второй способ представления связей между ячейками регистра сдвига и сумматорами, который часто используется в научно-технической литературе, заключается в следующем: каждый сумматор описывается порождающим (образующим, формирующим) полиномом g_j(D)=1+D+D²+D³+…

Здесь используется терминология циклических кодов.Степени полинома соответствуют номерам ячеек регистра сдвига (слева направо), с которыми j-й сумматор имеет связь. Например, в радиоканалах подвижной связи стандарта GSM (Глобальная система подвижной связи) используются сверточные кодеры с N=5 и порождающими полиномами g₁=1+D²+D³+D⁴ и g₂=1+D+D⁴.

Сверточный код может быть систематическим (разделимым) или несистематическим ( неразделимым ). Для систематического кода один из полиномов g_j должен быть равен 1

g_j=1.

Тогда на выходе соответствующего сумматора мы имеем входную информационную последовательность, а кодовая последовательность на выходе кодера является разделимой на информационные и (добавленные) проверочные символы. При использовании в декодере алгоритма Витерби предпочтение отдается несистематическим кодам.

Каждый информационный символ находится в регистре сдвига в течение N тактов и влияет на N*m передаваемых символов V_i. Величина N называется памятью сверточного кода. В общем случае число символов на выходе сверточного кодера, соответствующее передаче информационной последовательности длиной L символов составляет (L+N)*m. Обычно L>>N.

Сверточный код характеризуется скоростью R=k/m, где k – число входов сверточного кодера, m – число выходов, то есть число сумматоров. На практике чаще всего используются коды со скоростью R=1/2.