Помехоустойчивое кодирование

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:56, 12 мая 2016.

Постановка задачи

Передача сообщения с ошибками: при передачe сообщения «1010» от отправителя через канал связи, где есть помехи, получатель получает сообщение «1011». (рис. 1)

Рис. 1. Передача сообщения с ошибками.

Передача сообщения без ошибок: при передаче сообщения «1010» от отправителя, сообщение попадает в кодер, где добавляется информационный бит «1». Сообщение проходит через канал связи, где есть помехи «00010». Сообщение с помехой передается декодеру, а после декодирования — получателю. (рис. 2)

Рис. 2. Передача сообщения без ошибок.


Классификация каналов связи

Двоично-симметричные каналы без памяти

Двоичный - т.е. два символа кодирования "0" и "1". Симметричный - вероятность ошибки в 2-х случаях одинакова. Без памяти - ошибка в очередном символе зависит от того, была ли она ранее или нет.

Почти во всех случаях считают, что

Рис. 3.

Не симметричный канал

Рис. 4.

Выпадение символа

Рис. 5.

Мы не знаем был ли вообще символ вместо 3го символа

Канал со стиранием

Рис. 6.

Вероятности ошибок

Пусть вероятность ошибки - . Вероятность того, что ошибки не было для 1 символа - . Если n символов, тогда вероятность безошибочной передачи - . При длине сообщения 1 000 бит вероятность безошибочной передачи будет - . При длине сообщения 10 000 бит вероятность безошибочной передачи будет - .

C увеличением длины сообщения, вероятность ошибки растет экспоненциально.

- исходное сообщение

- сообщение, передаваемый в канал связи

- функция кодирования

- функция декодирования

в

Если и , то может перейти в

Система является хорошей, если вероятность ошибки достаточно маленькая.

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

TemplateExampleIcon.svg Пример Пример: Код с повторением (блочный код)


Раскодирование: выбираем элемент из блока, который наиболее встречается. Удачно раскодируем, если будет не более 1 ошибки в блоке.

Вероятность ошибки Количество ошибок Раскодирование
0 успех
1 успех
2 не успех
3 не успех

Схема Бернулли

- количество испытаний.

- вероятность успехов.

- количество успехов.

- вероятность неудач.

- вероятность того что случится событие m.

Следовательно вероятность не распознавания двух знаков: , но длина сообщения увеличилась в 3 раза. Следовательно увеличили надежность, но скорость передачи сообщения ниже.

См. также

Корректирующие коды

Литература

Мак-Вильямс Ф. Дж, Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М. : Связь, 1979. — С. 744, ил.