Построение корректирующих кодов.

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

Если n₀=n_a, то все возможные последовательности n-элементного кода используются для передачи или, как говорят, являются разрешенными. Полученный таким образом код называется простым.

 

1. Для передачи сообщений, число которых равно восьми (na=8), используется трехэлементный код. Число кодовых комбинаций, которое можно при этом получить, n0=23=8. Из таблицы 7.1 видно, что комбинация под номером 0 отличается от комбинации 1 только в одной позиции. Следовательно, если при передаче комбинации 000 произойдет ошибка в третьем элементе, то получим комбинацию 001.

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

 

Поэтому расстояние хемминга d =2. Иначе его определяют как вес суммы по модулю два ( – условное обозначение суммы) этих кодовых комбинаций. Весом w кодовой комбинации называется число входящих в нее ненулевых элементов.

 

Табл. 6.1 – Кодовые комбинации трехэлементного кода
Номер комбинации
Вид комбинации

 

Перебрав все возможные пары кодовых комбинаций, можно найти минимальное хеммингово расстояние, которое принято называть кодовым и обозначать d₀. Для примера 6.1 кодовое расстояние d₀=1. Рассмотренный в примере код простой. Любая ошибка (даже одиночная!) При использовании такого кода приведет к тому, что переданная разрешённая кодовая комбинация перейдет в другую разрешенную. Таким образом, простой код не способен обнаруживать и тем более исправлять ошибки и имеет d₀=1.

Для того чтобы код мог обнаруживать ошибки, необходимо, чтобы соблюдалось неравенство n_a<n₀. При этом неиспользуемые n-элементные кодовые комбинации, число которых (n₀-n_a), будем называть запрещенными. Они определяют избыточность кода. Очевидно, что появление ошибки в кодовой комбинации будет обнаружено, если переданная разрешенная комбинация перейдет в одну из запрещенных. В качестве n_p=n_a разрешенных кодовых комбинаций надо выбирать такие, которые максимально отличаются друг от друга.

2. Алфавит передаваемых сообщений na=2. Выберем из числа комбинаций, представленных в таблице 6.1, две. Очевидно, что ими должны быть комбинации 000, 111 или 001 и 110 и т.д. Кодовое расстояние d0=3. Ошибки кратности один или два превращают любую разрешенную кодовую комбинацию в запрещенную. Следовательно, максимальная кратность обнаруживаемых таким образом ошибок равна двум (tо.ош=2).

Нетрудно догадаться, что минимальное кодовое расстояние d₀ и гарантированно обнаруживаемая кратность ошибок связаны соотношением t_о.ош=d₀-1.

Исправление ошибок возможно также только в том случае, если переданная разрешенная кодовая комбинация переходит в запрещенную. Вывод о том, какая кодовая комбинация передавалась, делается на основании сравнения принятой запрещенной комбинации со всеми разрешенными. Принятая комбинация отождествляется с той из разрешенных, на которую она больше всего похожа, т.е. С той, от которой она отличается меньшим числом элементов. Так, если в примере 6.2 при передаче кодовой комбинации 000 получим 001, то вынесем решение, что передавалась кодовая комбинация 000.

Связь между d₀ и кратностью исправляемых ошибок определяется выражением t_и.ош=(d₀/2) – 1 для четного d₀ и t_и.ош =(d₀ – 1) / 2 для нечетного d₀.

Итак, задача получения кода с заданной корректирующей способностью сводится к задаче выбора (путем перебора) из n₀=2ⁿ кодовых комбинаций n_a комбинаций с требуемым кодовым расстоянием d₀. Если n достаточно мало, то такой перебор не представляет особого труда. При больших n перебор может оказаться непосильным даже для современной эвм, поэтому на практике используют методы построения кодов, не требующие перебора с целью получения кода с заданным d₀ и отличающиеся невысокой сложностью реализации.