Систематический код Хемминга

Соотношение между числом информационных символов Систематический код Хемминга - student2.ru , числом исправляемых ошибок Систематический код Хемминга - student2.ru и числом символов кодовой комбинации отображается неравенством (5.6). Хемминг предложил использовать знак равенства

Систематический код Хемминга - student2.ru . (5.15)

Таблица 5.2*  
n
k
r
Систематический код Хемминга - student2.ru 0.4286 0.2667 0.1613 0.0952 0.0551 0.0314
               

Это предложение выполняется только для определённых соотношений Систематический код Хемминга - student2.ru , Систематический код Хемминга - student2.ru и Систематический код Хемминга - student2.ru . В таблице 5.2 приведены решения уравнения (5.15) для целых Систематический код Хемминга - student2.ru , Систематический код Хемминга - student2.ru и Систематический код Хемминга - student2.ru =1.

Коды Систематический код Хемминга - student2.ru имеют минимальное кодовое расстояние Систематический код Хемминга - student2.ru и позволяют исправить одиночную ошибку. Коды Систематический код Хемминга - student2.ru имеют минимальное кодовое расстояние Систематический код Хемминга - student2.ru , обнаруживают двукратную ошибку и позволяют исправить одиночную ошибку.

Второе предложение Хемминга касается построения проверочной матрицы [Березюк Справочник]. Проверочная матрица должна состоять из столбцов, являющихся кодом номера столбца в двоичном представлении. Например, для кода Систематический код Хемминга - student2.ru проверочная матрица будет иметь вид

Систематический код Хемминга - student2.ru

В отличие от проверочной матрицы Систематический код Хемминга - student2.ru , в которой проверочные символы занимают позиции после информационных символов, проверочные символы в матрице Систематический код Хемминга - student2.ru занимают позиции кратные степени два Систематический код Хемминга - student2.ru и обозначены жирными единицами. Уравнения для определения проверочных символов получаются из матрицы Систематический код Хемминга - student2.ru , умножением его на вектор Систематический код Хемминга - student2.ru , Систематический код Хемминга - student2.ru =(h1 ,h2 , …, h15 ):

Систематический код Хемминга - student2.ru (5.16)

Синдром ошибки составляется из проверочных символов и указывает номер позиции символа, в которой произошла ошибка. Если задана информационная часть кода Систематический код Хемминга - student2.ru , необходимо определить значения проверочных символов на 1-ой, 2-ой, 4-ой и 8-ой позициях пятнадцатиразрядного кода Систематический код Хемминга - student2.ru .

Пример 5.3 Используем код Систематический код Хемминга - student2.ru с информационной частью

Систематический код Хемминга - student2.ru . Составим таблицу 5.3, в первой строке – номера символов (разрядов) в кодовой комбинации, во второй – позиции проверочных и значения информационных символов.

Таблица 5.3  
Номер символа
символы h1 h 2 h 4 h 8

Подставим значения символов согласно таблице 5.3 в систему равенств (5.16) и получим значения проверочных символов h1, h 2 , h 4, h 8 .

h1 = h3 Å h5 Å h7 Å h9 Å h11 Å h13 Å h15 = 1 Å 1 Å 1 Å 0 Å 1 Å 1 Å 1 =0,

h 2= h3 Å h6 Å h7 Å h12 Å h13 Å h14 Å h15 = 1Å 0 Å 1 Å 0 Å 1 Å 1 Å 1 =1,

h 4 = h 5 Å h6 Å h7 Å h10 Å h11 Å h13 Å h15 = 1 Å 0 Å 1 Å 0 Å 1 Å 1 Å 1 =1,

h 8 = h 9 Å h 10 Å h11 Å h 12 Å h13 Å h 14 Å h15 = 0 Å 0 Å 1 Å 0 Å 1 Å 1 Å 1 = 0,

Кодер канала выдает последовательность символов

Систематический код Хемминга - student2.ru .

Проверка правильности вычислений – произведение Систематический код Хемминга - student2.ru . Если произошла однократная ошибка, скажем в третьем разряде, декодер выдает двоичный код ошибки Систематический код Хемминга - student2.ru , если ошибка в десятом разряде вектора, код ошибки равен Систематический код Хемминга - student2.ru .

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

Циклические коды являются разновидностью систематических кодов. Они получили широкое распространение из-за простоты кодирования и декодирования. Все разрешённые кодовые комбинации производящей матрицы могут быть получены циклическим сдвигом одной разрешённой комбинации, называемой образующей для данного кода.

Любой Систематический код Хемминга - student2.ru -разрядный код можно представить в виде полинома степени Систематический код Хемминга - student2.ru

Систематический код Хемминга - student2.ru ,

где Систематический код Хемминга - student2.ru - основание счисления,

Систематический код Хемминга - student2.ru - коэффициенты, принимающие значения «0» или «1», если Систематический код Хемминга - student2.ru .

Например, комбинацию 110101 можно записать как

Систематический код Хемминга - student2.ru .

Циклический сдвиг эквивалентен умножению многочлена Систематический код Хемминга - student2.ru на Систематический код Хемминга - student2.ru .

Действительно,

Систематический код Хемминга - student2.ru .

Но в кодовой комбинации должно быть всего Систематический код Хемминга - student2.ru членов, причём степень полинома не должна превышать Систематический код Хемминга - student2.ru . Чтобы удовлетворить этому условию, положим Систематический код Хемминга - student2.ru . Тогда получим

Систематический код Хемминга - student2.ru ,

т.е. получили циклический сдвиг. Если код, выраженный в виде полинома, принадлежит разрешённой кодовой комбинации, то кодовая комбинация, полученная циклическим сдвигом, также принадлежит разрешённой кодовой комбинации. Из условия того, что Систематический код Хемминга - student2.ru имеем

Систематический код Хемминга - student2.ru . (5.16)

Пусть имеется полином Систематический код Хемминга - student2.ru степени Систематический код Хемминга - student2.ru . Среди полиномов Систематический код Хемминга - student2.ru выделим полиномы, которые делятся только лишь на самого себя и на 1. Такие полиномы называются простыми или неприводимыми.

Рассмотрим неприводимый полином Систематический код Хемминга - student2.ru и различные кодовые комбинации, выраженные в виде полиномов Систематический код Хемминга - student2.ru степени Систематический код Хемминга - student2.ru . Из всей совокупности полиномов Систематический код Хемминга - student2.ru к числу разрешённых кодовых комбинаций отнесём только те, которые делятся без остатка на полином Систематический код Хемминга - student2.ru . Определённый таким образом полином Систематический код Хемминга - student2.ru степени Систематический код Хемминга - student2.ru называется образующим.

Циклическими Систематический код Хемминга - student2.ru кодами называются коды, каждая кодовая комбинация которых, выраженная в виде полинома, имеет степень, не превышающую Систематический код Хемминга - student2.ru , и нацело делится на образующий полином Систематический код Хемминга - student2.ru степени Систематический код Хемминга - student2.ru .

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

Каноническая форма производящей матрицы Систематический код Хемминга - student2.ru размерности Систематический код Хемминга - student2.ru (5.10) состоит из зеркального отражения единичной подматрицы размерности Систематический код Хемминга - student2.ru , ( матрица отражения [Марпл]), и проверочной подматрицы размерности Систематический код Хемминга - student2.ru .

Систематический код Хемминга - student2.ru . (5.23)

Каждую строку матрицы Систематический код Хемминга - student2.ru разделим на неприводимый полином Систематический код Хемминга - student2.ru , дающий n остатков, и заменим нули в соответствующей строке проверочной части матрицы на остаток Систематический код Хемминга - student2.ru . Результирующая матрица Систематический код Хемминга - student2.ru будет производящей матрицей циклического кода Систематический код Хемминга - student2.ru .

Пример 5.5. Пусть n = 7, k = 4, r = 3. Первоначальное значение производящей матрицы имеет вид

Систематический код Хемминга - student2.ru Выберем образующий полином

Таблица 5.6
Номер строки
Код остатка

Систематический код Хемминга - student2.ru , который дает 7 остатков при делении кода ошибки на образующий полином. Разделим коды строк производящей матрицы Систематический код Хемминга - student2.ru на код образующего полинома Систематический код Хемминга - student2.ru . В результате имеем четыре остатка, значения которых приведены в таблице 5.6. После замены нулей в проверочной части матрицы соответствующими кодами остатков получим каноническую форму производящей матрицы

Систематический код Хемминга - student2.ru .

Полученная производящая матрица состоит из четырёх строк (кодов). Все остальные Систематический код Хемминга - student2.ru =11 кодов, кроме кода 0000000, могут быть получены линейной комбинацией строк производящей матрицы Систематический код Хемминга - student2.ru .

Наши рекомендации