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

4

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

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

N0-N = 2n -2k.

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

, (1)

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

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

, (2)

для S = 0 ;

S = 1 ;

S = 2 ;

S = 3 ; и т. д.

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

(3)

2m откуда .

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

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

формулы

. (4)

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

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

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

или . (5)

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

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

,

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

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

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

. (6)

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

. (7)

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

. (8)

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

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

Столбцы добавочной матрицы Rkm определяют правила формирования проверок. Число единиц в каждой строке добавочной матрицы должно удовлетворять условию r1 d0-1, но число единиц определяет число сумматоров по модулю 2 в шифраторе и дешифраторе, и чем их больше, тем сложнее аппаратура.

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

и т.д.

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

c=IG. (9)

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

. (10)

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

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

, (11)

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

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

. (12)

Между G(n ,k) и H(n, k) существует однозначная связь, т. к. они определяются в соответствии с правилами проверки, при этом для любого кодового слова должно выполняться равенство cHT = 0.

Строки проверочной матрицы определяют правила формирования проверок. Для (7, 4)-кода

p1+a1+a2a4 = S1 ;

p2+a1+a2a3 = S2 ; (13)

p3+a1+a3a4 = S3 .

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

Пример 1. Построить групповой код способный передавать 16 символов первичного алфавита с исправлением одиночной ошибки. Показать процесс кодирования, декодирования и исправления ошибки для передаваемого информационного слова 1001.

Решение:

Построим производящую матрицу G(n, k).

Если объем кода N = 2k = 16, то количество информационных разрядов к = 4. Минимальное кодовое расстояние для исправления одиночной ошибки d0=2s+1=3. По заданной длине информационного слова, используя соотношения:

n = k+m, 2n (n+1)2k и 2m n+1

вычислим основные параметры кода n и m.

m=[log2 {(k+1)+ [log2(k+1)]}]=[log2 {(4+1)+ [log2(4+1)]}]=3.

Откуда n = 7, т. е. необходимо построить (7, 4)-код.

В качестве информационной матрицы Ik(7, 4) - выбираем единичную матрицу (44), а в качестве проверочной матрицы Rkm(7 ,4) - выбираем матрицу (43), каждая строка которой содержит число единиц больше или равно двум (r1 d0-1).

Таким образом, в качестве производящей можно принять матрицу

.

2. Определим комбинации корректирующего кода.

Для заданного числа информационных разрядов k = 4,число кодовых комбинаций равно N = 2k = 24 = 16.

1) 0000 5) 0010 9) 0001 13) 0011

2) 1000 6) 1010 10) 1001 14) 1011

3) 0100 7) 0110 11) 0101 15) 0111

4) 1100 8) 1110 12) 1101 16) 1111

Старшинство разрядов принимаем слева на право, в соответствии с их поступлением на вход декодера.

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

Например, для информационного слова I= [1001] кодовое слово имеет вид

Страницы: 1, 2