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

3.1.    Принципы помехоустойчивого кодирования

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

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

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

Т.к. объем сигнала

, где  динамический диапазон сигнала;

 ширина спектра, длительность, максимальная и минимальная мощность сигнала соответственно, то увеличение объема (т.е. количества переносимой информации) возможно за счет увеличения .

Практические возможности увеличения избыточности сигнала за счет  и  в РСПИ по стандартным каналам резко ограничены. Поэтому преимущественное развитие получили методы, основанные на увеличении длительности сигнала (времени передачи).

На практике чаще всего используются:

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

-  многократная передача и мажоритарный прием;

-  одновременная передача по нескольким параллельно работающим каналам.

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

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

Разрядность двоичных комбинаций .

При этом любой кодовой комбинации соответствует свое сообщение. Если в процессе передачи произойдет хотя бы 1 ошибка, то принятая кодовая комбинация будет интерпретирована как другое сообщение.

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

Идея: в передаваемое сообщение нужно ввести по определенному правилу знаки разрешенной (безошибочной) кодовой комбинации (КК).

Если при приеме эти признаки не обнаруживаются, то считается, что произошла ошибка. В противном случае считается, что ошибок нет.

Внесение избыточности при использовании помехоустойчивого кодирования обязательно связано с увеличением разрядности (длины) КК. При этом всё множество КК можно разбить на 2 подмножества:

-  подмножество разрешенных КК;

-  подмножество запрещенных (ошибочных) КК.

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

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

Однако, если совокупность ошибок превращает одну разрешенную КК в другую, также разрешенную, то такие ошибки не обнаруживаются.

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

Число случаев, когда ошибки обнаруживаются .

Доля обнаруживаемых запрещенных КК .

Например, если = 100,  = 20, то ошибки обнаруживаются в 80% случаев.

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

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

Кодовое расстояние.

Количество разрядов, которыми различаются 2 КК, называется кодовым расстоянием .

Кодовое расстояние можно определить, представив КК в виде векторов в мерном пространстве. В этом случае кодовое расстояние равно норме суммы векторов, соответствующих КК.

Сумма КК определяется поразрядной суммой по .

Норма вектора, соответствующего КК, определяется , т.е. равна числу единиц в КК.

Минимальное кодовое расстояние называется хэмминговским.

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

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

Пример.

Обнаружение и исправление однократной ошибки.

Коэффициент избыточности.

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

Коэффициент избыточности

, где  число сообщений, число разрядов.

Пример. 

Код с повторением (каждое сообщение повторяется дважды).

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

, где  вероятность появления искажения, а .