7.1. Основные понятия

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

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

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

В ЭВМ эти коды используются для повышения надежности оперативной памяти (ОП) и магнитных дисков. Число ошибок в ЭВМ зависит от типа неисправностей элементов схем (например, неисправность одного элемента интегральной схемы (ИС) вызывает одиночную ошибку, а всей ИС ОП - кратную). Для обнаружения кратных ошибок используется код КО-ОД-ООГ (коррекция одиночной, обнаружение двойной и обнаружение кратной ошибки в одноименной группе битов).

Среди корректирующих кодов широко используются циклические коды, в ЭВМ эти коды применяются при последовательной передаче данных между ЭВМ и внешними устройствами, а также при передаче данных по каналам связи. Для исправления двух и более ошибок (d₀  5) используются циклические коды БЧХ (Боуза - Чоудхури - Хоквингема), а также Рида-Соломона, которые широко используются в устройствах цифровой записи звука на оптические компакт-диски и позволяющие осуществлять коррекцию групповых ошибок. Способность кода обнаруживать и исправлять ошибки достигается за счет введений избыточности в кодовые комбинации, т. е. кодовым комбинациям из к - двоичных информационных символов, поступающих на вход кодирующего устройства, соответствует на выходе последовательность из n - двоичных символов (такой код называется (n, k) - кодом).

Если N₀ = 2ⁿ - общее число кодовых комбинаций, а N = 2^k - число разрешенных, то число запрещенных кодовых комбинаций равно 2ⁿ -2^k.

При этом число ошибок, которое приводит к запрещенной кодовой комбинации равно:

,

где S - кратность ошибки, т. е. количество искаженных символов в кодовой комбинации S = 0, 1, 2, ...

C_nⁱ - сочетания из n элементов по i, вычисляемое по формуле:

,

для S = 0 ;

S = 1 ;

S = 2 ; S = 3 ; и т. д.

Для исправления S ошибок количество комбинаций кодового слова, составленного из m проверочных разрядов N = 2^m, должно быть больше возможного числа ошибок (13.2), при этом количество обнаруживаемых ошибок в два раза больше, чем исправляемых

2^m  откуда .

Для одиночной ошибки, как наиболее вероятной .

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

, где - полное число комбинаций кода.

Для практических расчетов при определении числа контрольных разрядов для корректирующих кодов с минимальным кодовым расстоянием удобно пользоваться выражением : m = [log₂(1+n)] или, если удобно в расчетах использовать число информационных символов, то m = [log₂ {(k+1)+ [log₂(k+1)]}], где квадратные скобки обозначают округление до большего целого.

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

Для исправления двукратной ошибки

или .

Таблица 7.1

N	7	10	15	31	63	127	255
K	4	6	11	26	57	120	247
M	3	4	4	5	6	7	8
	0,57	0,6	0,75	0,84	0,9	0,95	0,97

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

Например, для кода (31, 26) скорость передачи информации равна

,

т. е. скорость передачи уменьшается на 16%.

Как видно из таблицы 1, чем больше n, тем эффективнее используется канал.

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

Решение: Общая длина кодовой комбинации равна n = k+m, где k- количество информационных разрядов, а m- проверочных разрядов.

Для обнаружения двойной и исправления одиночной ошибки зависимости для разрядов имеют вид , при этом

m = [log₂ {(k+1)+ [log₂(k+1)]}]=[log₂ {(20+1)+ [log₂(20+1)]}]=5,

т. е. получим (25, 20)-код.