Представление сообщения, закодированного методом Хаффмана, в блочной форме

Необходимо передать сообщение М = (АКСЕНЕНКО_И), закодированное методом Хаффмана:

1000010101100110100010111001101110111110001001

В пункте 7 принято, что сообщение, закодированное методом Хаффмана, в блочном виде выглядит следующим образом:

 

A =

 

Было также определено:

r = 1

S = 1

d = 3

k = 4

 

Построение образующей (генераторной) матрицы

Выбор образующего полинома и определение контрольных разрядов

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

                                         (8.1)

В качестве коэффициента используются бинарные числа 0 и 1.

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

Первый способ базируется на использовании генераторной матрицы.

                                                (8.2)

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

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

Таблица 8.1

№	1	2	3	4
1	1	111	1011 1101	10011 11111 111 11001
2
3
4

 

Так как количество разрядов в контрольной группе k = 4, выберем многочлен из четвертого столбца:

P(x) = 11001

P(x) = a₁x⁴+a₂x³+a₃x⁰

P(x) = x⁴+x³+1

Процедура деления осуществляется до тех пор, пока кодовые группы не начнут повторяться.

 

1 0 0 0 0 0 0 0 0 0 0 | 1 1 0 0 1

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

1 0 0 1 0

1 1 0 0 1

1 0 1 1 0

1 1 0 0 1

    1 1 1 1 0

    1 1 0 0 1

       0 1 1 1 0

       0 0 0 0 0

          1 1 1 0 0

          1 1 0 0 1

             0 1 0 1 0

             0 0 0 0 0

                1 0 1 0    …