Представление сверточного кода порождающими многочленами

Краткие теоретические сведения

Исследование устройств кодирования и декодирования сверточных кодов

Цель работы: изучение способов математического описания кодеров сверточных кодов, самих кодов, характеристик сверточных кодов и моделирование их работы

Сверточные коды широко применяются в самых различных областях техники передачи и хранения информации. Наиболее наглядными примерами их эффективного применения являются системы космической связи, системы мобильной связи, модемы для телефонных каналов. В частности, протоколы V.32, V.34, ADSL, HDSL используют для защиты от ошибок сверточные коды в сочетании с декодированием по максимуму правдоподобия по алгоритму Витерби.

Схема кодера двоичного сверточного кода в общем виде представлена на рис. 1. Кодер содержит k двоичных регистров сдвига длин m₁,…m_k. Входами регистров сдвига являются информационные символы. Выходы ячеек регистров соединены с сумматорами по модулю 2. Всего сумматоров n.

Рис.1 Общая структурная схема кодера сверточного кода со скоростью k/n

На каждом такте работы кодера на его вход поступает блок из информационных символов. Эти символы и символы, хранящиеся в данный момент в регистрах кодера, поступают на входы тех сумматоров, которые подключены к соответствующим ячейкам. Результаты сложения по модулю два поступают на выход схемы. После этого в каждом из регистров происходит сдвиг, новые информационные символы записываются в первые ячейки, а содержимое остальных ячеек сдвигается на один разряд.

Содержимое m₁+m₂+…+m_k ячеек регистров сдвига в каждый конкретный момент времени называется текущим состоянием кодера. Предположим, что в начальный момент времени кодер находится в некотором заранее известном состоянии. Примем для определенности это начальное состояние нулевым. Рассмотрим процесс кодирования полубесконечной информационной последовательности. Выходы сумматоров на каждом такте работы называются кодовыми символами сверточного кода. Полубесконечная последовательность кодовых символов называется кодовым словом сверточного кода. Множество всевозможных кодовых слов образует сверточный код.

На каждом такте работы кодера информационных символа используются для формирования кодовых символов. Отношение

R=k/n

называется скоростью сверточного кода. Примеры кодеров сверточных кодов приведены на рис. 2.

Рис. 2. Примеры сверточных кодеров

Суммарная длина регистров сверточного кодера называется длиной кодового ограничения кода, а максимальная длина регистров называется задержкой кодера. Для кодов со скоростью 1/n память и кодовое ограничение совпадают.

Рассматриваемые схемы кодеров сверточных кодов полностью описываются связями ячеек регистров сдвига с выходными сумматорами. Существует несколько общепринятых форм представления этих связей. Начнем с кодов со скоростью 1/n. Связи каждого из n сумматоров с ячейками одного регистра длины m_i записываются в виде двоичного вектора g_i=(g_0i,…,g_mi), i=1,…,n. Ноль означает отсутствие связи, единица - наличие. Векторы g_i называют порождающими. В таблицах кодов порождающие векторы приводят в восьмеричной форме. Например, генератор g=(1010111) будет записан как (125). Другие примеры показаны на рис. 2.

Порождающие векторы записывают также в виде полиномов формальной переменной D. Например, порождающие полиномы кодера, показанного на рис. 1.2а, имеют вид

g₁(D)=1+D²,

g₂(D)=1+D+D².

Эту совокупность полиномов можно также записать в виде матричного порождающего полинома

G(D)=G₀+G₁D+G₂D².

Полиномиальное и матричное полиномиальное представление кодера удобно тем, что оно позволяет записать процесс кодирования в виде умножения полиномов формальной переменной D. Предположим, что на вход кодера подается информационная последовательность u=[101000…]. Эта последовательность может быть записана в виде полинома

u(D)=1+D²+….

Нетрудно убедиться в том, что на выходах сумматоров будут наблюдаться кодовые последовательности

c₁(D)=u(D)g₁(D)=1+D⁴+…;

c₂(D)= u(D)g₂(D)=1+D+D³+ D⁴+….

Матричная запись имеет вид

C(D)=u(D)G(D)=G₀+G₁D+(G₀+G₂)D²+G₁D³+G₂D⁴+…=

=[11]+[01]D+[00]D²+[01]D³+[11]D⁴+…

Следовательно, на выходе кодера будет сформировано кодовое слово [1101000111]. В этом примере был рассмотрен код со скоростью 1/2. В случае кода со скоростью k/n схема кодера содержит регистров сдвига. Обозначим через m максимальную длину регистра. Связи ячеек, имеющих одинаковый номер i с n выходными сумматорами, по-прежнему описываются матрицами G, однако, поскольку таких ячеек теперь k, размерность каждой из матриц будет равна k x n. Кодер будет описан порождающим полиномом

G(D)=G₀+G₁D+…+G_mD^m.

Входная последовательность кодера будет представлена векторным полиномом

u(D)=u₀+u₁D+u₂D²,

в котором подпоследовательности u_i, i=0,1…, имеют размерность 1 x k.

Кодирование представляется как умножение полиномов

C(D)=u(D)G(D) (1)

Пример сверточного кода со скоростью 2/3 приведен на рис. 2б.

Дата добавления: 2014-11-08