Обнаружение и исправление ошибок при передаче информации

Размещено на http://www.allbest.ru/

Содержание

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

2. Линейные групповые коды

3. Код Хэмминга



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

Корректирующими называются коды позволяющие обнаруживать и исправлять ошибки.

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

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

N0-N = 2n -2k.

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

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

код корректирующий линейный хэмминг

Рис. 5.3. Представление двоичных кодов с помощью куба

Так, сложив две комбинации

10110101101

11001010101

01111111000

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

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

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

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

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

.

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

Если необходимо исправить две ошибки, то число различных исходов будет составлять . Тогда:

,

в этом случае обнаруживаются однократные и двукратные ошибки. В общем случае, число контрольных символов должно быть не меньше:

.

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

, (1)

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

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

. (2)

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

, (3)

2m откуда .

При этом,

m = [log2(1+n)] или m = [log2 {(k+1)+ [log2(k+1)]}],

где квадратные скобки обозначают округление до большего целого.

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

или . (5)

Линейные групповые коды

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

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

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

. (6)

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

. (7)

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

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

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

. (8)

Столбцы добавочной матрицы 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.

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

Код Хэмминга

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

Код Хэмминга, как и любой (n, k)- код, содержит к информационных и m = n-k избыточных (проверочных) бит.

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

Существуют различные методы реализации кода Хэмминга и кодов которые являются модификацией кода Хэмминга. Рассмотрим алгоритм построения кода для исправления одиночной ошибки.

1. По заданному количеству информационных символов - k, либо информационных комбинаций N = 2k, используя соотношения:

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

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

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

2. Определяем рабочие и контрольные позиции кодовой комбинации. Номера контрольных позиций определяются по закону 2i, где i=1, 2, 3,... т.е. они равны 1, 2, 4, 8, 16,… а остальные позиции являются рабочими.

3. Определяем значения контрольных разрядов (0 или 1) при помощи многократных проверок кодовой комбинации на четность. Количество проверок равно m = n-k.

В каждую проверку включается один контрольный и определенные проверочные биты. Если результат проверки дает четное число, то контрольному биту присваивается значение -0, в противном случае - 1. Номера информационных бит, включаемых в каждую проверку, определяются по двоичному коду натуральных n -чисел разрядностью - m (табл. 1, для m = 4) или при помощи проверочной матрицы H(mn), столбцы которой представляют запись в двоичной системе всех целых чисел от 1 до 2k -1 перечисленных в возрастающем порядке. Для m = 3 проверочная матрица имеет вид:

.(15)

Количество разрядов m - определяет количество проверок.

В первую проверку включают коэффициенты, содержащие 1 в младшем (первом) разряде, т. е. b1, b3, b5 и т. д.

Во вторую проверку включают коэффициенты, содержащие 1 во втором разряде, т. е. b2, b3, b6 и т. д.

В третью проверку - коэффициенты которые содержат 1 в третьем разряде и т. д.

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

Таблица 1.

Десятичные числа (номера разрядов кодовой комбинации)	Двоичные числа и их разряды
	3	2	1
1 2 3 4 5 6 7	0 0 0 1 1 1 1	0 1 1 0 0 1 1	1 0 1 0 1 0 1

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

Пример 1. Построить код Хемминга для передачи сообщений в виде последовательности десятичных цифр, представленных в виде 4-х разрядных двоичных слов. Показать процесс кодирования, декодирования и исправления одиночной ошибки на примере информационного слова 0101.

Решение:

1. По заданной длине информационного слова (k = 4), определим количество контрольных разрядов m, используя соотношение:

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

при этом n = k+m = 7, т. е. получили (7, 4) -код.

2. Определяем номера рабочих и контрольных позиции кодовой комбинации. Номера контрольных позиций выбираем по закону 2i.

Для рассматриваемой задачи (при n = 7) номера контрольных позиций равны 1, 2, 4. При этом кодовая комбинация имеет вид:

b1 b2 b3 b4 b5 b6 b7

к1 к2 0 к3 1 0 1

3. Определяем значения контрольных разрядов (0 или 1), используя проверочную матрицу (5).

Первая проверка:

k1 b3 b5 b7 = k1011 будет четной при k1 = 0.

Вторая проверка:

k2 b3 b6 b7 = k2001 будет четной при k2 = 1.

Третья проверка:

k3 b5 b6 b7 = k3101 будет четной при k3 = 0.

1 2 3 4 5 6 7.

Передаваемая кодовая комбинация: 0 1 0 0 1 0 1.

Допустим, принято: 0 1 1 0 1 0 1.

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

1) k1 b3 b5 b7 = 0111 = 1.

2) k2 b3 b6 b7 = 1101 = 1.

3) k3 b5 b6 b7 = 0101 = 0.

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

Пример 2. Построить код Хэмминга для передачи кодовой комбинации 1 1 0 1 1 0 1 1. Показать процесс обнаружения и исправления ошибки в соответствующем разряде кодовой комбинации.

Решение: Рассмотрим алгоритм построения кода для исправления одиночной ошибки.

1. По заданной длине информационного слова (k = 8), используя соотношения вычислим основные параметры кода n и m.

m = [log2 {(k+1)+ [log2(k+1)]}]= [log2 {(9+1)+ [log2(9+1)]}]=4,

при этом n = k+m = 12, т. е. получили (12, 8) - код.

2. Определяем номера рабочих и контрольных позиции кодовой комбинации. Номера контрольных позиций выбираем по закону 2i.

Для рассматриваемой задачи (при n = 12) номера контрольных позиций равны 1, 4, 8.

При этом кодовая комбинация имеет вид:

b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12

к1 к2 1 к3 1 0 1 к4 1 0 1 1

3. Определяем значения контрольных разрядов (0 или 1) путем многократных проверок кодовой комбинации на четность. Количество проверок равно m = n-k. В каждую проверку включается один контрольный и определенные проверочные биты.

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

0001 b1 Количество разрядов m - определяет количество проверок

0010 b2

0011 b3 1) к1 b3 b5 b7 b9 а11 = к111111 =>

0100 b4 четная при к1=1

0101 b5 2) к2 b3 b6 b7 b10 b11= к210101 =>

0110 b6 четная при к2=1

0111 b7 3) к3 b5 b6 b7 b12 = к31011=>

1000 b8 четная при к3=1

1001 b9 4) к4 b9 b10 b11 b12 = к11011 =>

1010 b10 четная при к4=1

1011 b11

1100 b12

Передаваемая кодовая комбинация: 1 2 3 4 5 6 7 8 9 10 11 12

1 1 1 1 1 0 1 1 1 0 1 1

Допустим, принято: 1 1 1 1 0 0 1 1 1 0 1 1

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

1) к1 b3 b5 b7 b9 b11 = 110111 =1

2) к2 b3 b6 b7 b10 b11 = 110101 =0

3) к3 b5 b6 b7 b12 = 10011 =1

4) к4 b9 b10 b11 b12 = 11011 =0

Обнаружена ошибка в разряде кодовой комбинации с номером 0101, т. е. в 5 -м разряде. Для исправления ошибки необходимо проинвертировать 5 -й разряд в кодовой комбинации.

Размещено на Allbest.ru