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

Корректирующими кодами называют коды, которые позволяют обнаруживать и исправлять ошибки. Основную идею корректирующих кодов геометрически можно проиллюстрировать с помощью N -мерного куба (рис. 7.1), длина ребер в котором равна одной единице. Вершины такого куба отображают двоичные коды. Минимальное расстояние между двумя вершинами определяется минимальным количеством ребер, находящихся между этими вершинами. Расстояние, определяемое таким образом, называют кодовым (или хэмминговым). Другими словами, кодовое расстояние - это минимальное число элементов, в которых одна кодовая комбинация отличается от другой. Для определения кодового расстояния между двумя кодовыми комбинациями можно сложить их по модулю 2 и найти число единиц в получившейся сумме. Например, сложив две комбинации 10110101101 и 11001010101, получим 01111111000 и определим, что расстояние между ними d = 7.

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

d = t + l + 1,

где t – число исправляемых ошибок, l – число обнаруживаемых ошибок, при этом обычно l > t.

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

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

,

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

.

В общем случае, число контрольных символов определяется неравенством Хэмминга

,

где t – максимальное число одновременно исправляемых ошибок.

Поиск по сайту: