1.10. Непрерывные (сверточные) коды

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

Кодер использует  элементов памяти , при этом ясно, что скорость кода равна 1/2, так как на каждый введенный информационный символ выдаются два кодовых символа. Кодер, использующий т элементов памяти, называется в дальнейшем кодер памяти т.  В общем случае, сверточный кодер скорости k/п использу­ет к регистров сдвига, один регистр на один вводимый информационный символ. Под скоростью кода в теории кодирования понимается отношение . Более точное наименование параметра  – относительная скорость кода [69, 94], поскольку за единицу времени кодер принимает на вход  информационных разрядов и трансформирует их в  разрядов избыточного кода. Кодер памяти  и скорости  двоичного сверточного ко­да можно рассматривать также как дискретную линейную инвариантную во времени систему. Это означает, что отклик кодера на нулевую последовательность, в которой имеется единственная единица, т.е. выход кодера, полученный для входной последова­тельности  , полностью определяет код. Стрелка вправо символизирует, что единица от источника информации первой поступит на вход кодера. Рассмотрим сверточный кодер, показанный на рис. 1.12.

Рис. 1.12.  Кодер сверточного кода

Имеется  импульсных откликов сверточного кодера скорости , по одному на каждый выход  , где . По мере того, как импульс проходит через память кодера, он отражает связи между элементами памяти и выходом. Обозначим  набор импульсных откликов сверточ­ного кодера скорости , получивших название порождающи­х последовательностей или генераторов кода, которые задают действительные (физические) связи кодера. Кодер на рис. 1 порождает генераторы  и , поскольку на каждом их выходов кодера через  тактов формируются последовательности с нулевыми хвостами, при этом , а .  Обычно, говоря о сверточном коде, генераторы записывают в  восьмеричной системе счисления. Для рассматриваемого кодера эта запись имеет вид (7,5).

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

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

Рис. 1.13. Диаграмма состояний сверточного кодера памяти 3 и скорости 1/2

 

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

По-видимому, метка ребер вида 1/00, 1/11, 1/00 или 0/11 нейтральна, когда символы на выходе одинаковы  , но следует быть точным в представлении последовательности символов в метках  вида 1/01, 1/10 или 0/10, 0/01, когда .

Пусть двоичная последовательность источника информации имеет вид . Тогда последовательность в канале связи может быть представлена табл. 1.8.

Табл. 1.8  Представление выходной последовательности кодера (7,5)

Номер такта работы декодера	Значение информационного символа	Состояние кодера	Вид последовательности на выходе кодера
1	1	100	11
2	0	010	01 11
3	1	101	00 01 11
4	1	110	10 00 01 11
5	0	011	10 10 00 01 11
6	1	101	00 10 10 00 01 11
7	0	010	01 00 10 10 00 01 11
8	0	001	11 01 00 10 10 00 01 11
9	1	100	11 11 01 00 10 10 00 01 11
10	0	010	11 11 11 01 00 10 10 00 01 11

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

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

                                                        

для . С помощью этих генераторов выходную последо­вательность кода можно записать как

                     при                                 (1.18)                        

Выходные последовательности , равны дискретной свертке входной последовательности с генераторами кода . Уравнение (1.2) в ма­тричной форме имеет вид

,                                                  (1.19)

где G – порождающая матрица сверточного кода.

В частности, для сверточного кода памяти т и скорости 1/2 имеем

.

Это, так на­зываемая, ленточная матрица с шириной ленты равной тп, для кода памяти т и скорости 1/п. В представленной матрице сохраняется требование об очередности следования двоичных символов в канал связи. Поэтому первый элемент матрицы находится в первой строке справа. Поступления новых значений  приводит к наращиванию номеров столбцов матрицы слева, а номера строк увеличиваются снизу. Например, для кодера, представленного на рис. 1.10, и  порождающая матрица имеет вид

                                      .                          (1.20)

Пусть информационная последовательность имеет вид: , тогда произведение вектора  на матрицу  представляется последовательность двоичных символов (1.21) 

                           ,          (1.21)

что соответствует данным на пятом шаге работы кодера, которые приведены в табл. 1.8. Кодирование данных может осуществляться на основе решетчатых диаграмм (треллис-диаграмм). Тогда соот­ветствующая выходная (кодовая) последовательность может быть получена непосредственно как выделенный путь диаграммы, показанный на рис. 1.14.

 

Рис. 1.14. Путь на треллис-диаграмме сверточного кода при m = 3

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

Рассмотрим кодер, представленный на рис. 1.10, и входную последовательность . Принцип построения подобной диаграммы заключается в том, что слева показываются состояния последних  ячеек памяти. Это определяет число горизонтальных ярусов треллис-диаграммы, которое равно . В используемом в данном разделе примере, показывается состояние ячеек -значного регистра памяти для  и .

Состояние элемента памяти  изменяется под воздействием бит от источника информации. Данные, поступающие в канал связи на каждом шаге диаграммы сохраняют временную последовательность, как это показано на первом шаге диаграммы. В ходе обработки любых данных кодер начинает свою работу в точке 00. Дальнейшее движение по диаграмме зависит от данных источника информации. Приняв от него на первом шаге 1, регистр памяти переходит в состояние 100. Как было показано выше, в канал связи будут переданы данные сначала с выхода кодера  и только потом с выхода . После отправки данных в канал связи информация в регистре сдвигается на один шаг вправо, следовательно, последние две ячейки памяти будут иметь состояние 10, что отражает ребро графа переходных состояний кодера. Следует заметить, что сигналы на выходе элемента памяти  компенсируются специальной схемой гашения и в дальнейшей работе кодера участия не принимают.

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

Принцип работы декодера иллюстрируется на рис. 1.15.

Рис. 1.15. Принцип работы декодера сверточного кода

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

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

Работа декодера начинается с левого верхнего узла решетки (также как и работа кодера). В этой точке треллис-диаграммы декодер анализирует ситуацию, когда кодер мог находиться в состоянии 000 и на его входе появился 0. Таким образом, в канал связи кодер мог отправить значения 00. Сравнивая эти показатели с показателями, которые реально принял приемник (данные из канала связи соответствуют значениям 11), декодер устанавливает вес этого пути. Это осуществляется путем поразрядного сложения по  2 данных из канала связи и данных выработанных декодером для данного ребра, т.е. 1100=11 и вес этого пути равен 2 (в результате сложения оказалось, что оба разряда равны единице).

Декодер проверяет второй предположительный вариант действия кодера, когда состояние его элементов памяти могло соответствовать значениям 100. В этой ситуации кодер должен был отправить в канал связи пару бит 11. Тогда вес этого ребра равен 0, т.е. зафиксировано полное совпадение информации, принятой из канала связи и информации, которая появляется на выходе декодера в состоянии 100.

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

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

На практике для декодирования сверточных кодов наи­большее распространение получил алго­ритм Витерби, предложенный в 70-х го­дах прошлого столетия, и несколько модификаций алгорит­ма последовательного декодирования. Подобные коды используются практически во всех стандартах консорциума DVB (Digital Video Broadcasting) и являются  стандартом для многих спутниковых цифровых систем (например, Inmarsat и Intelsat).