Корректирующие коды (стр. 1 из 3)

Курс: Теория информации и кодирования

Тема: КОРРЕКТИРУЮЩИЕ КОДЫ

Содержание

1. КОРРЕКТИРУЮЩИЕ КОДЫ. ОСНОВНЫЕ ПОНЯТИЯ

2. ЛИНЕЙНЫЕ ГРУППОВЫЕ КОДЫ

3. КОД ХЭММИНГА

Список Литературы

1. КОРРЕКТИРУЮЩИЕ КОДЫ. ОСНОВНЫЕ ПОНЯТИЯ

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

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

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

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

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

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

N₀-N = 2ⁿ -2^k.

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

, (1)

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

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

, (2)

дляS = 0 ;

S = 1 ;

S = 2 ;

S = 3 ;

ит. д.

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

(3)

2^m³

откуда

.

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

.

В зависимости от исходных данных кода (n или k) можно использовать

формулы

. (4)

При этом, m = [log₂(1+n)] или m = [log₂ {(k+1)+ [log₂(k+1)]}], где ква-дратные скобки обозначают округление до большего целого.

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

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

или . (5)

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

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

,

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

Таблица 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

Как видно из таблицы 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)-код.

2. ЛИНЕЙНЫЕ ГРУППОВЫЕ КОДЫ

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

Свойство линейного кода: сумма (разность) кодовых векторов линей-ного кода дает вектор, принадлежащий этому коду. Свойство группового кода: минимальное кодовое расстояние между кодовыми векторами равно минимальному весу ненулевых векторов. Вес кодового вектора равен числу единиц в кодовой комбинации.

Групповые коды удобно задавать при помощи матриц, размерность которых определяется параметрами k и n. Число строк равно k, а число столбцов равно n = k+m.

. (6)

Коды, порождаемые этими матрицами, называются (n, k)-кодами, а соответствующие им матрицы порождающими (образующими, производящими). Порождающая матрица G состоит из информационной I_kk и проверочной R_km матриц. Она является сжатым описанием линейного кода и может быть представлена в канонической (типовой) форме

. (7)

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

. (8)

Строки единичной матрицы представляют собой линейно-незави-симые комбинации (базисные вектора), т. е. их по парное суммирование по модулю два не приводит к нулевой строке.

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

Столбцы добавочной матрицыR_kmопределяют правила формирования проверок. Число единиц в каждой строке добавочной матрицы должно удовлетворять условию r₁ ³ d₀-1, но число единиц определяет число сумматоров по модулю 2 в шифраторе и дешифраторе, и чем их больше, тем сложнее аппаратура.

Производящая матрица кода G(7,4) может иметь вид

и т.д.

Процесс кодирования состоит во взаимно - однозначном соответствии k-разрядных информационных слов - I и n-разрядных кодовых слов - с

c=IG.(9)

Например: информационному слову I=[1 0 1 0] соответствует следующее кодовое слово

. (10)

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

Процесс декодирования состоит в определении соответствия принятого кодового слова, переданному информационному. Это осуществляется с помощью проверочной матрицы H(n, k).

, (11)

где R_mk^T -транспонированная проверочная матрица (поменять строки на столбцы); I_mm- единичная матрица.

Для (7, 4)- кода проверочная матрица имеет вид

. (12)