Корректирующие коды

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

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

Так, сложив две комбинации определим, что расстояние между ними d = 7.

11001010101

Код с n = 3 и d = 1 для передачи используются все восемь кодовых комбинаций 000, 001,.., 111. Такой код является не помехоустойчивым, он не в состоянии обнаружить ошибку.

Если выберем комбинации с кодовым расстоянием d = 2, например, 000,110,101,011, то такой код позволит обнаруживать однократные ошибки. Назовем эти комбинации разрешенными, предназначенными для передачи информации. Все остальные 001, 010, 100, 111 – запрещенные. Любая одиночная ошибка приводит к тому, что разрешенная комбинация переходит в ближайшую, запрещенную комбинацию. Получив запрещенную комбинацию, мы обнаружим ошибку.

Комбинации для кода с d = 3:

Такой код может исправить одну одиночную ошибку или обнаружить две ошибки. Таким образом, увеличивая кодовое расстояние можно увеличить помехоустойчивость кода. В общем случае кодовое расстояние определяется по формуле d = (S + r)+ 1, где S - число исправляемых ошибок, r - число обнаруживаемых ошибок. Обычно r > S.

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

Кроме того, корректирующие коды являются групповыми кодами. Групповые коды (G_n) – это такие коды, которые имеют одну основную операцию. При этом должно соблюдаться условие замкнутости (то есть, при сложении двух элементов группы получается элемент, принадлежащий этой же группе). Число разрядов в группе не должно увеличиваться. Этому условию удовлетворяет операция поразрядного сложения по модулю 2. В группе, кроме того, должен быть нулевой элемент.

Примеры кодовых комбинаций:

1) 1101 1110 0111 1011 – не группа, так как нет нулевого элемента;

2) 0000 1101 1110 0111 – не группа, так как не соблюдается условие замкнутости (1101 + 1110 = 0011);

3) 000 001 010 011 100 101 110 111 – группа;

4) 000 001 010 111 – подгруппа.

Большинство корректирующих кодов образуются путем добавления к исходной m – комбинации k – контрольных символов. В итоге в линию передаются n = m + k символов. При этом корректирующие коды называются (n, m) кодами.

Для построения кода способного обнаруживать и исправлять одиночную ошибку необходимое число контрольных разрядов будет составлять n - m ≥ log (n + 1).

Если необходимо исправить две ошибки, то число различных исходов будет составлять C_n ². Тогда n - m ≥ log (1 + C_n ¹ + C_n ²), в этом случае обнаруживаются однократные и двукратные ошибки. В общем случае, число контрольных символов должно быть не меньше:

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

Код Хэмминга

Код Хэмминга, являющийся групповым (n, m) кодом, с минимальным расстоянием d =3 позволяет обнаруживать и исправлять однократные ошибки. Построение кодов Хемминга базируется на принципе проверки на чётность веса W (числа единичных символов) в информационной группе кодового блока.

Для каждого числа проверочных символов k = 3,4,5… существует классический код Хемминга с маркировкой (n, m) = (2 ^k -1, 2 ^k -1 - k), т.е. – (7,4), (15,11), (31,26) …

Для примера рассмотрим классический код Хемминга (7,4). В простейшем варианте при заданных четырёх (m = 4) информационных символах (i ₁, i ₂, i ₃, i ₄) будем полагать, что они сгруппированы в начале кодового слова, хотя это и не обязательно. Дополним эти информационные символы тремя проверочными символами (k = 3), задавая их следующими равенствами проверки на чётность, которые определяются соответствующими алгоритмами:

k ₁ = i ₁ i ₂ i ₃;

k ₂ = i ₂ i ₃ i ₄;

k ₃ = i ₁ i ₂ i ₄, где знак означает сложение по модулю 2.

В соответствии с этим алгоритмом определения значений проверочных символов k_i возможны 16 кодовых слов (7,4) – кода Хемминга.

m = 4	k = 3
i 1	i 2	i 3	i 4	k 1	k 2	k 3

На вход декодера поступает кодовое слово V = (i ₁', i ₂', i ₃', i ₄', k ₁', k ₂', k ₃'), апостроф означает, что любой символ слова может быть искажён помехой в канале передачи.

В декодере в режиме исправления ошибок строится последовательность:

s ₁ = k ₁' i ₁' i ₂' i ₃';

s ₂ = k ₂' i ₂' i ₃' i ₄';

s ₃ = k ₃' i ₁' i ₂' i ₄'.

Трёхсимвольная последовательность (s ₁, s ₂, s ₃) называется синдромом S.

Синдром S = (s ₁, s ₂, s ₃) представляет собой сочетание результатов проверки на чётность соответствующих символов кодовой группы и характеризует определённую конфигурацию ошибок (шумовой вектор).

Число возможных синдромов определяется выражением: S = 2 ^k.

Рис. 16.1. Кодер простого (7, 4) – кода Хемминга

Рис. 16.2. Декодер простого (7, 4) – кода Хемминга

При числе проверочных символов k = 3 имеется восемь возможных синдромов (2³ = 8). Нулевой синдром (000) указывает на то, что ошибки при приёме отсутствуют или не обнаружены. Всякому ненулевому синдрому соответствует определённая конфигурация ошибок, которая и исправляется. Классические коды Хемминга имеют число синдромов, точно равное их необходимому числу, позволяют исправить все однократные ошибки в любом информативном и проверочном символах и включают один нулевой синдром. Такие коды называются плотноупакованными.

Усечённые коды являются неплотноупакованными, так как число синдромов у них превышает необходимое. Так, в коде (9,5) при четырёх проверочных символах число синдромов будет равно 2⁴ =16, в то время как необходимо всего 10. Лишние 6 синдромов свидетельствуют о неполной упаковке кода (9,5). Для рассматриваемого кода (7,4) в таблице 16.1 представлены ненулевые синдромы и соответствующие конфигурации ошибок.

Таблица 16.1

Синдром
Конфигурация ошибок
Ошибка в символе	k 3	k 2	i 4	k 1	i 1	i 3	i 2

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

Дата добавления: 2015-10-28