Пространство сообщений. Коды обнаружения и исправления ошибок

Введем пространство сообщений в виде E(n, U_m), где U_m - алфавит, m - размерность алфавита, n - число символов из алфавита, образующих сообщение (слово) [9]. Такое пространство сообщений можно рассматривать как метрическое пространство, в котором расстояние между двумя сообщениями x и y, обозначаемое d(x, y) есть число различающихся символов в сообщениях x и y.

Пример. Пусть имеем алфавит U₂ = {0,1} и пространство сообщений E(6, U2), в котором формируются сообщения:

x = (0 1 0 1 0 0), y = (1 1 1 0 0 0). Расстояние по Хеммингу между этими сообщениями будет равно 3, то есть d (x, y) = 3.

Приведенное определение расстояния d (x, y) в пространстве сообщений удовлетворяет всем свойствам расстояния.

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

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

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

Рассмотрим случай, когда в процессе передачи сообщения оно может исказиться не более, чем в k разрядах. В пространстве сообщений E(n, U₂) выделим подмножество H_k Í E(n, U₂), обладающее тем свойством, что для " x, y Î Hk выполняется неравенство:

d (x, y) > k. (4.2)

Множество H_k назовем множеством осмысленных слов. Тогда

любое x1 Ï Hk будет бессмысленным словом. Предположим, что при передаче слова x Î Hk оно исказилось и перешло в x1, но поскольку по условию искажение может произойти не более чем в k разрядах, то расстояние d (x, x1) £ k, следовательно, x1 Ï Hk и x1 есть бессмысленное слово. Таким образом, коды, удовлетворяющие условию (4.2) есть коды с обнаружением ошибки.

Пример. В пространстве сообщений E(3, U₂ ) сформировать множество осмысленных слов.

Решение. Предлагается в качестве множества осмысленных слов H1

рассматривать множество { 000, 011, 110 } c расстоянием между кодами 2.

Тогда при k = 1 при передаче сообщения искажение в любом одном разряде превратит слово в бессмысленное.

Пример. В пространстве сообщений E(n-1, U₂ ) сформировать множество осмысленных слов.

Решение. Предлагается в качестве множества H1 осмысленных слов рассматривать множество кодов, к которым добавляется один разряд, значение которого выбирается таким образом, чтобы общее число единиц в словах x Î H1 было четным. Если в качестве пространства сообщений рассматривать Е(3, U2) = (000, 001, 010, 011, 100, 101, 110, 111), то в качестве H1 можно предложить множество

H1 = { 0000,1001,1010, 0011,1100, 0101, 0110,1111 }.

Искажение любого одного разряда в этих словах превращает их в бессмысленные, так как исказится четность числа. В рассмотренном примере 4-х разрядный код с обнаружением ошибки дает возможность составить 2ⁿ, то есть 16 различных слов. Однако, в качестве осмысленных слов, то есть подлежащих передаче по каналу связи используется только 8.

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

Наличие избыточности является необходимым условием построения помехоустойчивых кодов. Рассмотрим построение кодов с обнаружением и исправлением ошибок, возникших при передаче сообщений. Предположим, что в процессе передачи информации может исказиться не более k разрядов кода. Множество осмысленных слов Hk Í E(n, U2) назначим таким образом, чтобы расстояние между его кодами подчинялось условию:

d (x, y) > 2k (4.3)

для " x, y Î Hk. Пусть в результате искажения код x перешел в код x1, тогда d (x, x1) £ k. Запишем неравенство треугольника:

d (x, y) £ d (x, x1) + d(x1, y).

Усилим неравенство:

2k < k + d(x1, y),

что равносильно неравенству d (x1, y) > k. Последнее неравенство показывает, что расстояние от ошибочного слова x1 до слова x, подвергшегося искажению, меньше чем до любого другого осмысленного слова, тем самым позволяет восстановить правильное сообщение x.

Коды, удовлетворяющие условию (4.3) называются кодами с исправлением ошибок.

Пример. В пространстве сообщений Е(4, U2) выделить множество осмысленных слов с расстоянием 3.

Решение. Поскольку заданное расстояние d (x, y) = 3, то выбрав k = 1, для множества осмысленных слов зададим условие d (x, y) > 2 k. Что позволяет в качестве осмысленных слов выбрать коды: 0000, 0111. Тогда, если при передаче сообщения x = 0000 оно исказится и примет вид

x1 = 0001, то d (x, x1) = 1, d (x1, y) = 2. Следовательно, передано было сообщение 0000, то есть введенное множество H1 позволяет определять ошибку в переданном сообщении и позволяет восстанавливать сообщение, подвергшееся искажению.