Теория кодирования

 

, контрольный  бит 1=1.

, контрольный бит 2=0.

, контрольный  бит 4=0.

 контрольный  бит 8=0.

, контрольный  бит 16=0.

 

Контрольная сумма: 10000, передаваемое сообщение 101010000101110010100

 

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

Решение:

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

 

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

 

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

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

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

b₁ b₂ b₃ b₄ b₅ b₆ b₇

к₁ к₂ 0 к₃ 1 0 1

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

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

 k₁ Å b₃Å b₅Å b₇ = k₁Å0Å1Å1 будет четной при k₁ = 0.

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

 k₂ Å b₃Å b₆Å b₇ = k₂Å0Å0Å1 будет четной при k₂ = 1.

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

 k₃ Å b₅Å b₆Å b₇ = k₃Å1Å0Å1 будет четной при k₃ = 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) k₁ Å b₃Å b₅Å b₇ = 0Å1Å1Å1 = 1.

2) k₂ Å b₃Å b₆Å b₇ = 1Å1Å0Å1 = 1.

3. k₃ Å b₅Å b₆Å b₇ = 0Å1Å0Å1 = 0.

 

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

3.10. Циклические коды

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

A(X) = 1×x⁵ + 0×x⁴ + 1×x³ + 1×x² + 0×x¹ + 1 = x⁵ + x³ + x² + 1. 

Циклические коды относятся к систематическим (n, k) кодам, в которых контрольные r и информационные k разряды расположены на строго определенных местах: n = k + r.  

 

    Рассмотрим алгебру циклических  кодов. Допустим, необходимо перемножить  три многочлена      (x³+x²+1)·(x³+x+1)·(x+1). Действия производятся также как в обычной алгебре, только сложение проводится по модулю 2.

При делении  операция вычитания заменяется операцией  сложения по модулю 2. Например, необходимо разделить многочлен седьмой  степени на многочлен третей степени       (x⁷+x⁵+x⁴+x+1) / ( x³+x²+1)

Операция  деления может быть произведена  или в виде многочленов или  в виде двоичных кодов.

 

 

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

Пример 5.5.  Построить схему деления на многочлен     g(x)=x³+x+1 (1011)

Рис.5.6. Схема деления на многочлен  g(x)=x³+x+1  

Пусть на вход подается комбинация   10110001

В процессе алгебраического деления  получается остаток 001

            

Процесс деления  с помощью устройства показан в таблице 5.1.

  Таблица 5.1

Вх	1	2	3
1	1	0	0
0	0	1	0
1	1	0	1
1	0	0	0
0	0	0	0
0	0	0	0
0	0	0	0
1	1	0	0

Циклический код получают следующим  образом: заданный многочлен h(х) сначала умножается на одночлен х^n-k, затем делится на образующий многочлен g(х). В результате получим                     

       (5.3)

или

              F(x) = Q(x) · g(x) = x^n-kh(x) + R(X)             (5.4) 

Таким образом, циклический код  можно построить умножением кодовой  комбинации h(х), являющейся заданной, на одночлен х^n-k добавлением к этому произведению остатка R(х). При декодировании, принятую кодовую комбинацию необходимо разделить на g(x). Наличие остатка указывает на ошибку.

Образующий полином g(х) является сомножителем при разложении двучлена хⁿ+1. Сомножителями разложения двучлена являются неприводимые полиномы (таблица 5.3).

Образующий полином выбирают следующим  образом. По заданной кодовой комбинации k определяют число контрольных символов из соотношения r = log (n + 1)  или по эмпирической формуле

                             r = [log{(k + 1) + [log(k + 1)]}]    (5.5)

Соотношение значений n, k, r можно определить по таблице 5.2.

Таблица 5.2 зависимостей между n, k и r

n	3	5	6	7	9...15	17...31	33...63	65...127
k	1	2	3	4	5...11	12...26	27...57	28...120
r	2	3	3	3	4	5	6	7

Из таблицы неприводимых полиномов (табл.5.3) выбирают самый короткий многочлен  со степенью, равной числу контрольных  символов; его и принимают за образующий полином.

Пример 5.6. Пусть требуется закодировать комбинацию вида 1101, что соответствует h(х) = х³ + х² + 1.       По формуле (5.5) определяем число контрольных символов r = 3. Из таблицы 5.3 возьмем многочлен g(х) = х³ + х + 1, т.е. 1011.

Решение:

Умножим h(х) на х^r.

h(x)x^r = (x³ + x² + 1)x³ = x⁶ + x⁵ + x³ ® 11010000

Разделим полученное произведение на образующий полином g(х) 

  

При делении необходимо учитывать, что вычитание производится по модулю 2. Остаток суммируем с h(х)х^r. В результате получим закодированное сообщение: 

F(x) = (x³ + x² + 1) (x³ + x + 1) = (x³ + x² + 1)x³ + 1 ® 1101001 

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

Сообщение, которое закодировано,   является   одной из   комбинаций 4-разрядного кода, так как весь ансамбль сообщений (вся группа) содержит N=16 сообщений. Это значит, что если все  сообщения передаются в закодированном виде, то каждое из них необходимо кодировать так же, как и комбинацию h(x) = 1101. Однако выполнять дополнительные 15 расчетов (а в общем случае 2^n-k-1 расчет) нет необходимости. Это можно сделать проще, путем составления образующей (порождающей) матрицы.

Образующая матрица составляется на основе единичной транспонированной, к которой справа дописывается матрица  дополнений:                          

 H_n,k = || I_k, C_n,r ||     (5.6) 

Матрица дополнений получается из остатков от деления единицы с нулями на образующий многочлен g(x). Комбинации единиц с нулями представляют собой векторы ошибок: 00...01, 00... 10, 00... 1...0 и т.д. Каждому вектору ошибок будет соответствовать свой остаток (опознаватель):

Получено 4 комбинации циклического кода, т.е. столько, сколько информационных разрядов, а так как в 4-разрядном  двоичном коде всего N = 2⁴ = 16 комбинаций, то остальные 11 ненулевых комбинаций находятся суммированием по модулю 2 всевозможных сочетаний строк образующей матрицы. Например, необходимо из исходных кодов 1101 и 1010 получить циклические помехозащищенные коды. Они получаются суммированием соответствующих строк образующей матрицы: 

1. 1+3+4 = 1101001;

2.       2+4 = 1010011.

Декодирование циклических кодов    

Для обнаружения  и исправления ошибок принятая комбинация делится на образующий многочлен  g(х). Если остаток R(х) = 0, значит, комбинация принята без ошибок. Наличие остатка свидетельствует о том, что комбинация принята искаженной. Значение остатка совпадет с одним из опознавателей матрицы Н, который и укажет на местоположение ошибки по вектору ошибок.

1100001

1011

  1110

  1011

    1010

    1011

      011 - ошибка в четвертом разряде

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

1101011

1011

  1100

  1011

    1111

    1011

      1001

      1011

        010   - ошибка во 2-м контрольном разряде

Существует более общий  алгоритм обнаружения и исправления  ошибок:

1.      Принятая комбинация делится на образующий многочлен g(x). Если остаток R(x)<>0 то определяется вес остатка w. Если вес остатка равен или меньше числа исправляемых ошибок t (w<=t), то принятую комбинацию складывают по модулю 2 с остатком и получают исправленную комбинацию.

2.      Если w>t, то производится циклический сдвиг на один символ влево и полученная после такого сдвига комбинация снова делится на образующий многочлен. Если вес полученного остатка w<=t, то циклически сдвинутую комбинацию складывают с остатком и затем после сложения  циклически сдвигают в обратную сторону вправо на один символ (возвращают на прежнее место). В результате получаем исправленную комбинацию.

3.      Если после циклического сдвига на один символ по прежнему w>t, то производят дополнительные циклические сдвиги влево. При этом после каждого сдвига осуществляется деление сдвинутой комбинации на g(x)  и проверяется вес остатка. При w<=t сдвинутую комбинацию складывают с остатком и производят обратных циклических сдвигов вправо столько, сколько было сделано влево.

3.11. Итеративные коды

Итеративные коды. 

Итеративные коды являются подклассом матричных  кодов, для которых на ряду с защитой  каждой комбинации простого кода характерно кодирование групп пере даваемых комбинаций. Матричный код это  множество матриц, строки и столбцы  которых являются комбинациями блочных  корректирующих кодов, т.е. nэлементная комбинация матричного кода А имеет  вид: 

а 00 a 01 ... а 0 (n21) 

а 10 а 11 ... a1( n21)

A = ... ... ... ...  

A (n11) 0 а (n11) 1 ... а (n11) (n21)

Размерность матрицы n1 х n2, причем n = n1 * n2.

Элементы  комбинации передаются в дискретный канал связи в следующем порядке:

a00, a10, ..., a(n1), a01, a11, ..., a(n11)1, ..., a0(n21), ..., a(n11)(n21).

Таким образом, элементы строк передаются c разносом в n элементов, что обеспечивает декорреляцию ошибок и повышение эффективности  корректирующих кодов, соответствующих  строкам матрицы.

Итеративный код матричный код, строки и столбцы  которого представляют собой комбинации группового кода. Итеративный код  является групповым (n, k)кодом, причем n=n1*n2, k=k1*k2, (n1, k1) групповой код, соответствующий  столбцам, а (n2, k2) строкам.

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