Сорока Н.И., Кривинченко Г.А. Теория передачи информации

Подождите немного. Документ загружается.

291

Основным достоинством изложенного выше метода треллис–

кодирования является его помехоустойчивость. Как будет показано в дальней-

шем, благодаря избыточности кодирования (вспомним, что каждому информа-

ционному биту ставится в соответствие дибит, то есть избыточность кода равна

2) даже в случае возникновения ошибок приема (к примеру, вместо дибита 11

ошибочно принят дибит 10) исходная последовательность бит может быть без-

ошибочно восстановлена.

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

ника используется декодер Витерби.

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

1/1

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

292

1/11

1/01

0/10

1/11

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

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

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

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

Декодер Витерби в случае безошибочного приема всей последовательно-

сти дибитов 00 11 10 00 01 10 01 11 11 10 будет обладать информацией об этой

последовательности, а также о строении кодера (то есть о его диаграмме состо-

яний) и о его начальном состоянии (00). Исходя из этой информации он должен

восстановить исходную последовательность бит. Рассмотрим, каким образом

происходит восстановление исходной информации.

293

Зная начальное состояние кодера (00), а также возможные изменения это-

го состояния (00 и 10), построим временную диаграмму для первого момента

времени (рис. 12.17). На этой диаграмме из состояния 00 существует только два

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

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

кодера Треллиса, устанавливаем, что следующим состоянием кодера будет 00,

что соответствует исходному биту 0.

/11

Рис. 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.

294

1/11

1/01

0/10

1/11

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

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

Для следующего момента времени, соответствующего принятому дибиту

10, отметим, что в состояния 00, 01 и 11 ведут по два пути (рис. 12.19). В этом

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

метрика ошибок. Кроме того, поскольку переходы из состояния 11 в состояние

11 и в состояние 01 отбрасываются, переход из состояния 10 в состояние 11, от-

вечающий предыдущему моменту времени, не имеет продолжения, поэтому

тоже может быть отброшен. Аналогично отбрасывается переход, отвечающий

предыдущему моменту времени из состояния 00 в 00.

1/11

1/01

0/10

/01

0/10

1/00

0/11

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

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

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

можных путей и изобразить все возможные пути.

295

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

как может показаться, поскольку большинство из них отбрасываются в процес-

се построения, как не имеющие продолжения (рис. 10.20). К примеру, на ше-

стом такте работы декодера по описанному алгоритму остается всего четыре

возможных пути.

1/01

0/11

1/11

0/01

1/00

0/10

1/01

0/10

1/11

0/11

1/00

0/10

1/11

1/01

0/01

1/01

0/10

0/11

1/00

0/10

1/0

/00

0/10

0/11

0/10

1/01

/00

0/10

/11

1/00

0/11

1/01

/01

0/10

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

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

Аналогично и на последнем такте работы декодера имеется всего четыре

возможных пути (рис. 12.21), причем истинный путь, однозначно восстанавли-

296

вающий исходную последовательность битов 0101110010, соответствует мет-

рике ошибок, равной 0.

t=0 t=1 t=2 t=3

00 11

Состояние

декодера

Входной

дибит

Метрика ошибок: 2+1=3; 3+1=4 : 3

Метрика ошибок: 0+0=0; 3+2=5 : 0

Метрика ошибок: 2+1=3; 3+1=4 : 3

Метрика ошибок: 0+2=2; 3+0=3 : 2

Выходной

бит

t=4 t=5

10 00 01

0/00

0 1 0 1 1

10 01 11

1 0 0 1

t=6 t=7 t=8 t=9 t=10

0/000/00

0/11

0/01

1/10

1/01

1/00

1/11

0/10

1/00

1/01

1/10

0/01

0/11

0/10

t=0 t=1 t=2 t=3

Состояние

декодера

t=4 t=5

0/00

t=6 t=7 t=8 t=9 t=10

0/000/00

0/11

0/01

1/10

1/01

1/00

1/11

0/10

1/01

0/10

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

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

При построении рассмотренных временных диаграмм удобно отображать

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

Именно эта таблица и является источником той информации, на основе которой

возможно восстановить исходную последовательность бит (табл. 12.1).

Таблица 12.1.

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

Состояния декодера T=0

t=1

t=2

t=3

t=4

t=5

t=6

t=7

t=8

t=9

t=10

00 – 0 2 3 2 3 3 3 0 2 3

01 – – 3 0 3 2 2 0 3 3 0

10 – 2 0 3 0 3 3 3 2 0 3

11 – – 3 2 3 0 0 2 3 3 2

Входной дибит 00

Выходной бит 0 1 0 1 1 1 0 0 1 0

297

В описанном выше случае мы предполагали, что все принятые декодером

дибиты не содержат ошибок. Рассмотрим далее ситуацию, когда в принятой по-

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

последовательности 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), можно однозначно восстановить исходную последова-

298

тельность бит 0101110010, невзирая на допущенные ошибки при получении

дибитов.

1/01

0/10

1/00

1/1

1/00

1/11

1/01

0/10

0/11

1/00

0/10

0/01

1/1

0/11

1/01

0/01

0/10

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

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

0/10

0/11

1/01

1/00

/00

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

Рассмотренный сверточный кодер Треллиса на четыре состояния и алго-

ритм Витерби являются простейшими примерами, иллюстрирующими основ-

ной принцип работы. В реальности используемые кодеры Треллиса (и в гига-

битных адаптерах, и в модемах) гораздо более сложные, но именно благодаря

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

передачи данных.

299

Таблица 12.2.

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

Состояния декодера t=0

t=1

t=2

t=3

t=4

t=5

t=6

t=7

t=8

t=9

t=10

00 – 0 2 3 3 2 3 4 2 4 5

01 – – 3 1 2 2 3 2 4 5 2

10 – 2 0 2 1 3 3 4 4 2 5

11 – – 3 1 2 2 2 3 4 5 4

Полученный дибит 00

Выходной бит 0 1

1 0 0 1 0

КОНТРОЛЬНЫЕ ВОПРОСЫ

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

помехами.

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

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

вания?

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

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

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

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

кодов.

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

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

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

кода?

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

ческом коде?

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

коде?

13. Какое минимальное расстояние должно быть между пакетами иска-

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

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

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

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

300

ЗАКЛЮЧЕНИЕ

Изложенные в конспекте лекций идеи и методы теории информации

представляют интерес не только в плане решения задач, связанных с передачей

и хранением информации. Теоретико–информационный подход приобрел зна-

чение метода исследования, позволяющего качественно и количественно сопо-

ставлять специфические характеристики конкретных устройств и систем неза-

висимо от их физической сущности.

Трудами ученых и инженеров созданы и продолжают создаваться фунда-

ментальные методы анализа, синтеза и оптимизации информационных систем.

Развивается математическое моделирование процессов передачи сообщений,

разрабатываются и внедряются новые методы анализа нестационарных непре-

рывных каналов, неоднородных асимметричных дискретных каналов, помехо-

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

ненадежность аппаратуры и отклонение характеристик устройств от идеаль-

ных, строятся математические модели сложных шумовых ситуаций, интенсив-

но развивается корректирующее кодирование.

Методы теории информации все шире применяются для решения практи-

ческих задач повышения качества передачи информации и эффективности си-

стем и сетей связи, радионавигационных и радиолокационных систем, автома-

тизированных систем управления воздушным движением, вычислительных си-

стем, измерительных комплексов и многих других.

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

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

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

ния процессами передачи информации;

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

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

ции системного подхода;

применение цифрового и статистического моделирования процессов пе-

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

Глубокое и всестороннее развитие теории информации тесно связано с

практическими потребностями информационной техники.

Следует ожидать, что идеи и методы теории информации будут успешно

использоваться при создании сложных систем, объединяющих различные по

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