Треллис-кодирование

Рассмотрим принципы треллис–кодирования на основе простейшего кодера, состоящего из двух запоминающих ячеек и сумматоров по модулю два (рис.12.8). Пусть на вход такого кодера поступает со скоростью k бит/с последовательность бит 0101110010. Если на выходе кодера установить ключ DA1, работающий с вдвое большей частотой, чем скорость поступления бит на вход кодера, то скорость выходного потока будет в два раза выше скорости входного потока. При этом считывающая ячейка DA1 за первую половину такта работы кодера считывает данные сначала с логического элемента DD5, а вторую половину такта – с логического элемента DD4. В результате каждому входному биту ставится в соответствие два выходных бита, то есть дибит, первый бит которого формируется элементом DD5, а второй – элементом DD4. По временной диаграмме состояния кодера нетрудно проследить, что при входной последовательности бит 0101110010 выходная последовательность будет 00 11 10 00 01 10 01 11 11 10 (рис. 12.11).

Рис. 12.11. Временные диаграммы работы простейшего кодера Треллиса

Отметим одну важную особенность принципа формирования дибитов. Значение каждого формируемого дибита зависит не только от входящего информационного бита, но и от двух предыдущих бит, значения которых хранятся в двух запоминающих ячейках. Действительно, если принято, что A_i – входящий бит, то значение элемента DD5 определится выражением , а значение элемента DD4 – выражением . Таким образом, дибит формируется из пары битов, значение первого из которых равно , а второго – . Следовательно, значение дибита зависит от трех состояний: значения входного бита, значения первой запоминающей ячейки и значения второй запоминающей ячейки. Такие кодеры получили название сверточных кодеров на три состояния (K = 3) с выходной скоростью ½.

Работу кодера удобно рассматривать на основе не временных диаграмм, а так называемой диаграммы состояния. Состояние кодера будем указывать с помощью двух значений – значения первой и второй запоминающих ячеек DD1 и DD3. К примеру, если первая ячейка хранит значение 1 (Q1=1), а вторая – 0 (Q2=0), то состояние кодера описывается значением 10. Всего возможно четыре различных состояния кодера: 00, 01, 10 и 11.

Пусть в некоторый момент времени состояние кодера равно 00. Нас интересует, каким станет состояние кодера в следующий момент времени и какой дибит будет при этом сформирован. Возможны два исхода в зависимости от того, какой бит поступит на вход кодера. Если на вход кодера поступит 0, то следующее состояние кодера также будет 00, если же поступит 1, то следующее состояние (то есть после сдвига) будет 10. Значение формируемых при этом дибитов рассчитывается по формулам и . Если на вход кодера поступает 0, то будет сформирован дибит 00 ( ), если же на вход поступает 1, то формируется дибит 11 ( ). Приведенные рассуждения удобно представить наглядно с помощью диаграммы состояний (рис. 10.12), где в кружках обозначаются состояния кодера, а входящий бит и формируемый дибит пишутся через косую черту. Например, если входящий бит 1, а формируемый дибит 11, то записываем: 1/11.

Рис. 12.12. Диаграмма возможных переходов кодера из начального состояния 00

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

Используя диаграмму состояний кодера, несложно построить временную диаграмму переходов для уже рассмотренной нами входной последовательности бит 0101110010. Для этого строится таблица, в столбцах которой отмечаются возможные состояния кодера, а в строках – моменты времени. Возможные переходы между различными состояниями кодера отображаются стрелками (на основе полной диаграммы состояний кодера – рис. 12.13), над которыми обозначаются входной бит, соответствующий данному переходу, и соответствующий дибит. Например, для первого момента времени диаграмма состояния кодера выглядит так, как показано на рис. 12.14. Жирной стрелкой отображен переход, соответствующий рассматриваемой последовательности бит.

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

Основным достоинством изложенного выше метода треллис–кодирования является его помехоустойчивость. Как будет показано в дальнейшем, благодаря избыточности кодирования (вспомним, что каждому информационному биту ставится в соответствие дибит, то есть избыточность кода равна 2) даже в случае возникновения ошибок приема (к примеру, вместо дибита 11 ошибочно принят дибит 10) исходная последовательность бит может быть безошибочно восстановлена.

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

Рис. 12.13. Полная диаграмма состояния кодера

Рис. 12.14. Временная диаграмма состояния кодера для первого момента времени

Рис. 12.15. Временная диаграмма состояния кодера для двух первых моментов времени

Рис. 12.16. Временная диаграмма состояния кодера

для рассматриваемой входной последовательности бит

Декодер Витерби

Декодер Витерби в случае безошибочного приема всей последовательности дибитов 00 11 10 00 01 10 01 11 11 10 будет обладать информацией об этой последовательности, а также о строении кодера (то есть о его диаграмме состояний) и о его начальном состоянии (00). Исходя из этой информации он должен восстановить исходную последовательность бит. Рассмотрим, каким образом происходит восстановление исходной информации.

Зная начальное состояние кодера (00), а также возможные изменения этого состояния (00 и 10), построим временную диаграмму для первого момента времени (рис. 12.17). На этой диаграмме из состояния 00 существует только два возможных пути, соответствующих различным входным дибитам. Поскольку входным дибитом декодера является 00, то, пользуясь диаграммой состояний кодера Треллиса, устанавливаем, что следующим состоянием кодера будет 00, что соответствует исходному биту 0.

Рис. 12.17. Временная диаграмма возможных состояний декодера

для первого момента времени

Однако у нас нет 100% гарантии того, что принятый дибит 00 является правильным, поэтому не стоит пока отметать и второй возможный путь из состояния 00 в состояние 10, соответствующий дибиту 11 и исходному биту 1. Два пути, показанные на диаграмме, отличаются друг от друга так называемой метрикой ошибок, которая для каждого пути рассчитывается следующим образом. Для перехода, соответствующего принятому дибиту (то есть для перехода, который считается верным), метрика ошибок принимается равной нулю, а для остальных переходов она рассчитывается по количеству отличающихся битов в принятом дибите и дибите, отвечающем рассматриваемому переходу. Например, если принятый дибит 00, а дибит, отвечающий рассматриваемому переходу, равен 11, то метрика ошибок для этого перехода равна 2.

Для следующего момента времени, соответствующего принятому дибиту 11, возможными будут два начальных состояния кодера: 00 и 10, а конечных состояния будет четыре: 00, 01, 10 и 11 (рис. 10.18). Соответственно для этих конечных состояний существует несколько возможных путей, отличающихся друг от друга метрикой ошибок. При расчете метрики ошибок необходимо учитывать метрику предыдущего состояния, то есть если для предыдущего момента времени метрика для состояния 10 была равной 2, то при переходе из этого состояния в состояние 01 метрика ошибок нового состояния (метрика всего пути) станет равной 2 + 1 = 3.

Рис. 12.18. Временная диаграмма возможных состояний декодера

для первых двух моментов времени

Для следующего момента времени, соответствующего принятому дибиту 10, отметим, что в состояния 00, 01 и 11 ведут по два пути (рис. 12.19). В этом случае необходимо оставить только те переходы, которым отвечает меньшая метрика ошибок. Кроме того, поскольку переходы из состояния 11 в состояние 11 и в состояние 01 отбрасываются, переход из состояния 10 в состояние 11, отвечающий предыдущему моменту времени, не имеет продолжения, поэтому тоже может быть отброшен. Аналогично отбрасывается переход, отвечающий предыдущему моменту времени из состояния 00 в 00.

Рис. 12.19. Временная диаграмма возможных состояний декодера

для первых трех моментов времени

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

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

Рис. 12.20. Временная диаграмма возможных состояний декодера

для четвертого, пятого и шестого тактов

Аналогично и на последнем такте работы декодера имеется всего четыре возможных пути (рис. 12.21), причем истинный путь, однозначно восстанавливающий исходную последовательность битов 0101110010, соответствует метрике ошибок, равной 0.

Рис. 12.21. Временная диаграмма возможных состояний декодера

для последнего момента времени

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

Таблица 12.1.

Метрика ошибок для различных состояний декодера

В описанном выше случае мы предполагали, что все принятые декодером дибиты не содержат ошибок. Рассмотрим далее ситуацию, когда в принятой последовательности дибитов содержатся две ошибки. Пусть вместо правильной последовательности 00 11 10 00 01 10 01 11 11 10 декодер принимает последовательность 00 11 11 00 11 10 01 11 11 10, в которой третий и пятый дебит являются сбойными. Попробуем применить рассмотренный выше алгоритм Витерби, основанный на выборе пути с наименьшей метрикой ошибок, к данной последовательности и выясним, сможем ли мы восстановить в правильном виде исходную последовательность битов, то есть исправить сбойные ошибки.

Вплоть до получения третьего (сбойного) дибита алгоритм вычисления метрики ошибок для всех возможных переходов не отличается от рассмотренного ранее случая. До этого момента наименьшей метрикой накопленных ошибок обладал путь, отмеченный на рис. 10.22 полужирной линией. После получения такого дибита уже не существует пути с метрикой накопленных ошибок, равной 0. Однако при этом возникнут два альтернативных пути с метрикой, равной 1. Поэтому выяснить на данном этапе, какой бит исходной последовательности соответствует полученному дибиту, невозможно.

Рис. 12.22. Вычисление метрики накопленных ошибок при получении первого

ошибочного дибита

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

После получения десятого дибита количество возможных путей с различной метрикой накопленных ошибок станет достаточно большим (рис. 12.24), однако на приведенной диаграмме (с использованием табл. 12.2, где представлена метрика накопленных ошибок для различных путей) нетрудно выбрать единственный путь с наименьшей метрикой (на рис. 12.24 этот путь отмечен жирной линией). По данному пути, пользуясь диаграммой состояния треллис–кодера (см. рис. 12.13), можно однозначно восстановить исходную последовательность бит 0101110010, невзирая на допущенные ошибки при получении дибитов.

Рис. 12.23. Вычисление метрики ошибок при получении

второго ошибочного дибита

Рис. 12.24. Вычисление метрики ошибок при получении последнего дибита

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

Таблица 12.2.

Метрика накопленных ошибок для различных путей

Контрольные вопросы

1. Сформулируйте теорему Шеннона о кодировании в каналах связи с помехами.

2. Перечислите основные задачи, решаемые кодированием.

3. При каких предположениях решают задачи корректирующего кодирования?

4. Приведите классификацию корректирующих кодов.

5. Дайте определение блочным кодам.

6. Назовите основные характеристики корректирующих кодов.

7. Покажите принцип обнаружения ошибок на геометрической модели кодов.

8. Приведите выражение для определения числа контрольных символов.

9. Какие коды называются систематическими?

10. Как строится образующая и проверочная матрицы систематического кода?

11. Как получается алгоритм кодирования и декодирования в систематическом коде?

12. Какой принцип кодирования кодовых комбинаций в рекуррентном коде?

13. Какое минимальное расстояние должно быть между пакетами искажений, чтобы принятая кодовая комбинация была однозначно декодируемой?

14. Поясните принцип работы кодера сверхточного кода (8,4).

15. Приведите и поясните диаграмму переходов кодера (6,3).

16. В чём сущность декодирования кодовых сообщений по методу Витерби.

ЗАКЛЮЧЕНИЕ

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

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

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

Основные тенденции и перспективы теории информации следующие:

широкое внедрение цифровых методов передачи сообщений;

рост удельного веса алгоритмических и программных методов управления процессами передачи информации;

широкое использование корректирующего кодирования;

разработка методов оценки эффективности передачи информации с позиции системного подхода;

применение цифрового и статистического моделирования процессов передачи сообщения для анализа и синтеза информационных систем;

Глубокое и всестороннее развитие теории информации тесно связано с практическими потребностями информационной техники.

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