Глава II. СВЕРТОЧНОЕ КОДИРОВАНИЕ И ВЫЧИСЛЕНИЕ ПРОВЕРОК

Перейдем к рассмотрению сверточного кодирования, включив в круг обсуждения алгебраические свойства кодов, оценки их качества и схемы для кодирования и вычисления проверок. Эта глава задумана главным образом как подготовительная к следующим, но некоторая часть материала является в ней новой. Так, § 2.2, 2.4 и 2.7 содержат оригинальные результаты. Граница, основанная на случайном выборе кода § 2.5, впервые была получена Элайесом [24] (одновременно он ввел сверточное кодирование); мы лишь приводим иной метод доказательства. Возенкрафт [4, стр. 75—77] показал, что оценка Гилберта, приведенная в § 2.3, достигается в двоичных сверточных кодах при скорости Мы даем доказательство, применимое и для недвоичных кодов, и для кодов с произвольной скоростью передачи.

Схема кодирования в п. 2.6 а была впервые описана Возенкрафтом и Рейффеном [4, стр. 77—79], схема же в п. 2.6 б приведена впервые.

§ 2.1. Сверточное кодирование

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

Используя оператор задержки, или D-обозначение, введенный Хаффменом входных последовательностей можно представить совокупностью полиномов

где информационный символ, поступающий на вход кодирующего устройства в момент времени и.

Рис. 3. Общий вид сверточного кодера.

Аналогично, выходных последовательностей обозначают полиномами

где — символ, считываемый на выходе в момент времени .

Без ограничения общности предположим, что код систематический, т. е. первые выходных последовательностей совпадают с входными последовательностями. В D-обозначениях это свойство выражается так:

Определяющее свойство сверточного кода состоит в том, что остальные выходных последовательностей, или проверочных последовательностей,

являются линейными комбинациями входных последовательностей, т. е.

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

Полиномы

называются полиномами, порождающими код (всюду ниже — просто порождающими полиномами); их выбором код определяется полностью. Число таких полиномов равно

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

В течение этого времени кодирующее устройство выдаст всего символов, и потому говорят, что кодовое ограничение кода составляет символов.

В D-обозначениях порождающие полиномы будут представляться в виде

где коэффициенты являются элементами поля

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

символов в начальном кодовом слове будем пользоваться обозначением

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

Согласно этому определению, множество начальных кодовых слов сверточного кода образует систематический линейный код, или -код, как он назван в § 1.1. Длина кода соответствует кодовому ограничению а количество информационных символов величине Другими словами, в начальном кодовом слове имеется символов, из которых являются информационными.

Эти идеи лучше всего пояснить примером. Рассмотрим двоичный сверточный код при порождающим полиномом которого является

Для произвольной информационной последовательности проверочная последовательность, согласно (29), дается выражением

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

то выходная последовательность такова:

Способ, которым образуются проверочные символы, можно понять из рис. 4.

Рис. 4. Пример кодера.

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

Так как в этом примере степень порождающего полинома начальное кодовое слово определяется полиномами

и

Из предыдущего примера должно быть ясно, что начальное кодовое слово, определенное равенством (31), может быть получено из выражений (28) и (29) простым отбрасыванием всех членов, в которые D входит с показателем, большим, чем Отсюда мы можем написать

и

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