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

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

Простейшим способом для обнаружения ошибок в передаваемом пакете данных является проверка четности с помощью расширения передаваемого сообщения за счет добавления бита четности в код. С помощью данного кода мы нельзя восстановить данные, но можно обнаружить одиночную ошибку. Бит четности устанавливается во время отправки данных, и затем рассчитывается и сравнивается во время получения данных. Он равен сумме по модулю 2 всех бит данных в пакете. То есть число единиц в пакете всегда будет четно. Изменение этого бита (например, с 0 на 1) сообщает о возникшей ошибке. Общая идея помехоустойчивого кодирования состоит в том, что из всех возможных кодовых слов считаются допустимыми не все, а лишь некоторые из них. Например, в коде с контролем по четности считаются допустимыми лишь слова с четным числом единиц. Ошибка превращает допустимое слово в недопустимое и поэтому обнаруживается.

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

Рисунок 12- Упрощенная классификация корректирующих кодов Все известные в настоящее время коды могут быть разделены на две большие группы: блочные и непрерывные. Блочные коды характеризуются тем,

что последовательность передаваемых символов разделена на блоки. Операции кодирования и декодирования в каждом блоке производятся отдельно.

В настоящее время в технических приложениях в основном используются двоичные блочные корректирующие коды. Основными характеристиками таких помехоустойчивых кодов являются:

- число разрешённых и запрещённых кодовых комбинаций;

-избыточность кода;

-минимальное кодовое расстояние;

-число обнаруживаемых или исправляемых ошибок;

-корректирующие возможности кодов.

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

Расстояние между различными комбинациями некоторого конкретного кода могут существенно отличаться. Так, в частности, в безизбыточном первичном натуральном коде (n = k) это расстояние для различных комбинаций может изменяться от единицы до величины n, равной значности кода. Особую важность для характеристики корректирующих свойств кода имеет минимальное кодовое расстояние dmin, определяемое при попарном сравнении всех кодовых комбинаций, которое называют расстоянием Хемминга.

В безизбыточном коде все комбинации являются разрешёнными, и, следовательно, его минимальное кодовое расстояние равно единице - dmin = 1. Поэтому достаточно исказиться одному символу, чтобы вместо переданной комбинации была принята другая разрешённая комбинация. Чтобы код обладал корректирующими свойствами, необходимо ввести в него некоторую избыточность, которая обеспечивала бы минимальное расстояние между любыми двумя разрешёнными комбинациями не менее двух /16, 17/. Одним из простейших алгоритмов помехоустойчивого кодирования, позволяющим исправить одиночную ошибку является алгоритм Хэмминга.

2.4.