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

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

Для выяснения идеи помехоустойчивого кодирования будем рассматривать двоичный код, нашедший на практике наиболее широкое применение. Двоичный код - это код с основанием m = 2. Количество разрядов n в кодовой комбинации принято называть длиной или значностью кода. Символы каждого разряда могут принимать значения 0 и 1. Количество единиц в кодовой комбинации называют весом кодовой комбинации и обозначают w. Например, кодовая комбинация 100101100 характеризуется значимостью n = 9 и весом w = 4.

Степень отличия любых двух кодовых комбинаций данного ко­да характеризуется так называемым кодовым расстоянием d. Оно выражается числом позиций или символов, в которых комбинации отличаются одна от другой, и определяется как вес суммы по модулю два этих кодовых комбинаций. Например, для определения расстояния между комбинациями 100101100 и 110110101 необходимо просуммировать их по модулю два:

.

Полученная в результате суммирования новая кодовая комбинация характеризуется весом w = 4. Следовательно, расстояние между исходными кодовыми комбинациями d = 4.

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

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

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

Для указания мест в кодовой комбинации, где имеются искажения символов, используется вектор ошибки . Вектор ошибки n -разрядного кода - это n -разрядная комбинация, единицы в которой указывают положение искаженных символов кодовой комбинации. Например, если для пятиразрядного кода вектор ошибки имеет вид =01100, то это значит, что имеют ошибки во втором и третьем разрядах кодовой комбинации.

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

Как уже отмечалось, помехоустойчивость кодирования обеспечивается за счет введения избыточности в кодовые комбинации. Это значит, что из n символов кодовой комбинации для передачи информации используется k < n символов. Следовательно, из общего числа N ₀ = 2 ⁿ возможных кодовых комбинаций для передачи информации используется только N = 2 ^k комбинаций. В соответствии с этим все множество N ₀ = 2 ⁿ возможных кодовых комбинаций делится на две группы. В первую группу входит множество N = 2 ^k разрешенных комбинаций, вторая группа включает в себя множество (N ₀- N) = 2 ⁿ - 2 ^k запрещенных комбинаций.

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

В общем случае каждая из N разрешенных комбинаций может трансформироваться в любую из N ₀ возможных комбинаций (рис. 1.1), т. е. всего имеется N · N ₀ возможных вариантов передачи, из них N вариантов безошибочной передачи. N (N -1) вариантов перехода в другие разрешенные комбинации, что соответствует не обнаруживаемым ошибкам и N (N ₀- N) вариантов перехода в запрещенные комбинации, которые могут быть обнаружены. Таким образом, не все искажения могут быть обнаружены. Доля обнаруживаемых ошибочных комбинаций составляет:

Рис. 17.1. Возможные варианты передачи кодовых комбинаций

Для использования данного кода в качестве исправляющего множество N₀ – N запрещенных кодовых комбинаций разбивается на N непересекающихся подмножеств М_k. Каждое из подмножеств М_k ставится в соответствие одной из разрешенных комбинаций.

Если принятая запрещенная комбинация принадлежит подмножеству M_i, то считается, что передана комбинация А_i. Ошибка будет исправлена в тех случаях, когда полученная комбинация действительно образовалась из комбинации А_i. Таким образом, ошибка исправляется в N ₀ -N случаях, равных количеству запрещенных комбинаций. Доля исправляемых ошибочных комбинаций от общего числа обнаруживаемых ошибочных комбинаций составляет:

.

Способ разбиения на подмножества зависит от того, какие ошибки должны исправляться данным кодом.