Корректирующие коды (стр. 2 из 3)
Между G(n ,k) и H(n, k) существует однозначная связь, т. к. они определяются в соответствии с правилами проверки, при этом для любого кодового слова должно выполняться равенство cHT = 0.
Строки проверочной матрицы определяют правила формирования проверок. Для (7, 4)-кода
p1Å+a1Å+a2Åa4 = S1 ;
p2Å+a1Å+a2Åa3 = S2 ; (13)
p3Å+a1Å+a3Åa4 = S3 .
Полученный синдром сравниваем со столбцами матрицы и определяем разряд, в котором произошла ошибка, номер столбца равен номеру ошибочного разряда. Для исправления ошибки ошибочный бит необходимо проинвертировать.
Пример 1. Построить групповой код способный передавать 16 символов первичного алфавита с исправлением одиночной ошибки. Показать процесс кодирования, декодирования и исправления ошибки для передаваемого информационного слова 1001.
Решение:
1. Построим производящую матрицу 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) - выбираем единичную матрицу (4´4), а в качестве проверочной матрицы Rkm(7 ,4) - выбираем матрицу (4´3), каждая строка которой содержит число единиц больше или равно двум (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) 0000 000 5) 0010 110 9) 0001 101 13) 0011 011
2) 1000 111 6) 1010 001 10) 1001 010 14) 1011 100
3) 0100 011 7) 0110 101 11) 0101 110 15) 0111 000
4) 1100 100 8) 1110 010 12) 1101 101 16) 1111 111
Процесс декодирования состоит в определении соответствия принятого кодового слова, переданному информационному и осуществляется с помощью проверочной матрицы H(7, 4).
Для построенного (7, 4)-кода проверочная матрица имеет вид
.Строки проверочной матрицы определяют правила формирования проверок, позволяющие определить синдром ошибки.
Пусть в процессе передачи произошла ошибка во 2-м информационном разряде 1 1 0 1 1 0 0 1
В соответствии с проверочной матрицей составляем проверочные векторы
p1Åa1Åa2Åa4 =S1 = 0Å1Å1Å0 = 0;
p2Åa1Åa2Åa3 =S2 = 0Å1Å1Å1 = 1 ;
p3Åa1Åa3Åa4 =S3 = 1Å1Å0Å1 = 1.
Синдром 011 показывает, что ошибка произошла во 2-м информационном разряде, который необходимо проинвертировать.
Пример 2. Построить образующую матрицу группового кода, для передачи 100 различных сообщений и способную исправлять возмож-но большее число ошибок.
Решение: Объем кода равен N = 2k. При 100 сообщениях: 100 £ N £ 2k , откуда k = 7. По заданной длине информационного слова, используя соотношения:
n = k+m, 2n³ (n+1)2k и 2m³ n+1
вычислим основные параметры кода n и m.
m=[log2 {(k+1)+ [log2(k+1)]}]=[log2 {(7+1)+ [log2(7+1)]}]=4.
Откуда n = 11, т. е. получили (11, 7)-код.
В качестве информационной матрицы выбираем единичную матрицу I(7x7).Проверочная матрица содержит 4 столбца и 7 строк, которые содержат r1£ d0-1 единиц в четырехразрядном коде (2, 3, 4-единицы).
.3. КОД ХЭММИНГА
Код Хэмминга относится к классу линейных кодов и представляет собой систематический код – код, в котором информационные и контрольные биты расположены на строго определенных местах в кодовой комбинации.
Код Хэмминга, как и любой (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(m´n), столбцы которой представляют запись в двоичной системе всех целых чисел от 1 до 2k –1 перечисленных в возрастающем порядке. Для m = 3 проверочная матрица имеет вид
. (15 )Количество разрядов m - определяет количество проверок.
В первую проверку включают коэффициенты, содержащие 1 в младшем (первом) разряде, т. е. b1, b3, b5 и т. д.
Во вторую проверку включают коэффициенты, содержащие 1 во втором разряде, т. е. b2, b3, b6 и т. д.
В третью проверку - коэффициенты которые содержат 1 в третьем разряде и т. д.
Таблица 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 |
Для обнаружения и исправления ошибки составляются аналогичные проверки на четность контрольных сумм, результатом которых является двоичное (n-k) -разрядное число, называемое синдромом и указывающим на положение ошибки, т. е. номер ошибочной позиции, который определяется по двоичной записи числа, либо по проверочной матрице.
Для исправления ошибки необходимо проинвертировать бит в ошибочной позиции. Для исправления одиночной ошибки и обнаружения двойной используют дополнительную проверку на четность. Если при исправлении ошибки контроль на четность фиксирует ошибку, то значит в кодовой комбинации две ошибки.
Схема кодера и декодера для кода Хэмминга приведена на рис. 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 b2b3b4b5b6b7
к1 к2 0 к3 1 0 1
3. Определяем значения контрольных разрядов (0 или 1), используя проверочную матрицу (5).
Первая проверка:
k1 Åb3Åb5Åb7 = k1Å0Å1Å1 будет четной при k1 = 0.
Вторая проверка:
k2 Åb3Åb6Åb7 = k2Å0Å0Å1 будет четной при k2 = 1.
Третья проверка:
k3 Åb5Åb6Åb7 = k3Å1Å0Å1 будет четной при k3 = 0.
1 2 3 4 5 6 7
Передаваемая кодовая комбинация: 0 1 0 0 1 0 1
Допустим принято: 0 1 1 0 1 0 1