Теория информации


Математическая модель системы связи


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

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

Таким образом, должна быть четной.

Соответствующая схема декодирования тривиальна:

Разумеется, что четность не гарантирует безошибочной передачи.

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

Рассмотрим -код с тройным повторением. Коды с повторениями очень неэффективны, но полезны в качестве теоретического примера кодов, исправляющих ошибки. Любое сообщение разбивается на блоки длиной каждое и каждый блок передается трижды - это определяет функцию . Функция определяется следующим образом. Принятая строка разбивается на блоки длиной . Бит с номером в декодированном блоке получается из анализа битов с номерами , , в полученном блоке: берется тот бит из трех, который встречается не менее двух раз. Вероятность того, что бит в данной позиции будет принят трижды правильно равна . Вероятность одной ошибки в тройке равна . Поэтому вероятность правильного приема одного бита равна . Аналогичным образом получается, что вероятность приема ошибочного бита равна .

Пример. Предположим . Тогда вероятность ошибки при передачи одного бита - 0.028, те. этот код снижает вероятность ошибки с 10% до 2.8%. Подобным образом организованная передача с пятикратным повторением даст вероятность ошибки на бит т.е.


- Начало -    - Вперед -