Корректирующие свойства кодов с избыточностью

Лекция 6.

Связь корректирующей способности кода с кодовым расстоянием

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

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

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

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

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

Более полное представление о свойствах кода дает матрица расстояний D, элементы которой d_ij (i,j = 1,2,...,n) равны расстояниям между каждой парой из всех m разрешенных комбинаций.

Пример: Представить симметричной матрицей расстояний код X1 = 000; Х2 = 001; Х3 = 010;X4=111

Решение.. Минимальное кодовое расстояние для кода d=1.

Это вытекает из рассмотрения симметричная матрицы всех возможных кодовых расстояний между словами кода.

Таблица 5.1

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

Такое декодирование называется декодированием по методу максимального правдоподобия.

Рассмотрим сущность помехоустойчивого кодирования на уже рассмотренном на предыдущей лекции рисунке

На этом рисунке через Ai (N шт.) обозначенные разрешеные кодовые слова, Bj (L-N)шт. запрещенные слова, а Mi (N шт.) некоторые подмножества, элементами которых являются те или другие запрещенные кодовые слова.

Из рисунка видно, что при передаче кодовой комбинации Ai она может под воздействием помех перейти в одну из комбинаций Bj, то есть ошибка может быть выявлена (L - N) случаях из общего количества L кодовых слов. Так происходит каждый раз, когда передается любая из N разрешенных кодовых комбинаций. Общее количество ошибочных комбинаций, которые обнаруживаются, равняется N (L - 1)а общее количество возможных комбинаций L * N поэтому часть ошибочных комбинаций, которые обнаруживаются, равняется

µ=1-(N/L);

Аналогичный прием используется и для исправления ошибок. Для использования кода как корректирующего надо разбить множества Bj всего (L-N)шт. запрещенных кодовых комбинаций - на N непересекающихся подмножеств Mi. Каждое из подмножеств Mi приписывается одному из кодовых слов Ai. Способ корректировки или исправления ошибок заключается в том, что когда принятая комбинация Bj принадлежит М i, тогда считается, что передана комбинация А i. При таком способе декодирования существует возможность исправления ошибок.

Из рисунка видно, что при любом способе разбития ошибка может быть исправлена в L-N (для Bj) случаях и обнаружена в N (L - N)случаях. Отношение количества ошибочных комбинаций, которые исправляются, к количеству ошибочных комбинаций равно 1 / N.

Наконец, определим, что количество -ошибок, которые не исправляются равняется N*(N-1),при этом часть некорректируемых ошибок по отношению к общему количеству последствий равняется (N -1)/ L. Отмеченные результаты имеют общий характер и верны для всех корректирующих кодов.

Дата добавления: 2013-12-11