1.10. Непрерывные (сверточные) кодыСверточные коды это коды, исправляющие ошибки, которые используют непрерывную, или последовательную, обработку информации короткими фрагментами (блоками). Сверточный кодер обладает памятью в том смысле, что символы на его выходе зависят не только от (очередного фрагмента) информационных символов на входе, но и предыдущих символов на его входе. Другими словами, кодер представляет собой последовательную машину или автомат с конечным числом состояний. Состояние кодера определяется содержимым его памяти. Кодер использует Рис. 1.12. Кодер сверточного кода Имеется Общая длина регистров сдвига, используемых кодером, называется памятью кода. Сверточный код образуется множеством всех двоичных последовательностей, порождаемых сверточным кодером. Теоретически эти последовательности бесконечны. Практически состояние сверточного кодера периодически устанавливается в некоторое заранее известное состояние и, следовательно, порождаемый код приобретает характер блокового кода. Считается, что конечная кодовая последовательность Сверточный кодер памяти Рис. 1.13. Диаграмма состояний сверточного кодера памяти 3 и скорости 1/2
Так как в кодер вводится по одному биту, то в каждое состояния входят и из каждого состояния исходят по два ребра, помеченные метками По-видимому, метка ребер вида 1/00, 1/11, 1/00 или 0/11 нейтральна, когда символы на выходе одинаковы Пусть двоичная последовательность источника информации имеет вид Табл. 1.8 Представление выходной последовательности кодера (7,5)
В табл. 1.8 жирным шрифтом выделены двоичные символы, которые на предыдущих шагах работы кодера были первыми отправлены в канал связи, курсивом показаны символы, которые формирует кодер на очередном шаге своей работы. Сверточный кодер является линейной постоянной во времени системой, импульсный отклик которой задан набором генераторов кода Тогда общее значение импульсного отклика должно соответствовать композиции элементов для Выходные последовательности
где G – порождающая матрица сверточного кода. В частности, для сверточного кода памяти т и скорости 1/2 имеем
Это, так называемая, ленточная матрица с шириной ленты равной тп, для кода памяти т и скорости 1/п. В представленной матрице сохраняется требование об очередности следования двоичных символов в канал связи. Поэтому первый элемент матрицы находится в первой строке справа. Поступления новых значений Пусть информационная последовательность имеет вид: что соответствует данным на пятом шаге работы кодера, которые приведены в табл. 1.8. Кодирование данных может осуществляться на основе решетчатых диаграмм (треллис-диаграмм). Тогда соответствующая выходная (кодовая) последовательность может быть получена непосредственно как выделенный путь диаграммы, показанный на рис. 1.14.
Рис. 1.14. Путь на треллис-диаграмме сверточного кода при m = 3 Преимуществом такого подхода к описанию работы кодера является идентичность методов анализа работы декодера на приемной стороне. Кроме того, нет необходимости вычислять параметры матрицы Рассмотрим кодер, представленный на рис. 1.10, и входную последовательность Состояние элемента памяти Если предположить, что в канале связи помехи не действуют, то полученный на диаграмме путь (рис. 1.14) должен повторить декодер приемника. Принцип его работы заключается в поиске непрерывного пути наименьшего веса среди множества возможных путей для сверточного кода с определенными для него параметрами. Треллис-диаграмма приемника в общих чертах соответствует диаграмме, которая описывает работу кодера. Особенностями диаграммы являются представители поля Принцип работы декодера иллюстрируется на рис. 1.15. Рис. 1.15. Принцип работы декодера сверточного кода Элементы поля показаны парами на схеме слева во вспомогательных таблицах и соответствуют одному из Для дальнейшего анализа работы декодера необходимо установить соглашение: если обрабатывается нулевой элемент, то на диаграмме переходных состояний ребро графа представляется пунктиром, в противном случае – сплошной линией. В любой точке диаграммы декодер анализирует возможные два исхода по декодированию принятой информации в предположении, что на Работа декодера начинается с левого верхнего узла решетки (также как и работа кодера). В этой точке треллис-диаграммы декодер анализирует ситуацию, когда кодер мог находиться в состоянии 000 и на его входе появился 0. Таким образом, в канал связи кодер мог отправить значения 00. Сравнивая эти показатели с показателями, которые реально принял приемник (данные из канала связи соответствуют значениям 11), декодер устанавливает вес этого пути. Это осуществляется путем поразрядного сложения по Декодер проверяет второй предположительный вариант действия кодера, когда состояние его элементов памяти могло соответствовать значениям 100. В этой ситуации кодер должен был отправить в канал связи пару бит 11. Тогда вес этого ребра равен 0, т.е. зафиксировано полное совпадение информации, принятой из канала связи и информации, которая появляется на выходе декодера в состоянии 100. На первых дух шагах подобному анализу поверглось всего два ребра графа, на втором шаге четыре ребра и после этого анализу повергаются все С учетом пунктирных и сплошных линий устанавливается значение бита, который должен быть выдан приемнику сообщений. В отличие от блочных алгебраических кодов, декодирование сверточных кодов с мягкими решениями не вызывает затруднений. Именно это обстоятельство позволяет успешно использовать сверточные коды в современных системах связи. На практике для декодирования сверточных кодов наибольшее распространение получил алгоритм Витерби, предложенный в 70-х годах прошлого столетия, и несколько модификаций алгоритма последовательного декодирования. Подобные коды используются практически во всех стандартах консорциума DVB (Digital Video Broadcasting) и являются стандартом для многих спутниковых цифровых систем (например, Inmarsat и Intelsat).
|