Циклического кода

Циклические коды являются линейными. Их можно строить точно так же, как и рассмотренные выше систематические линейные коды Хэмминга, определяя порождающую (базис циклического кода) или проверочную матрицу. Как и в СЛБК, порождающая матрица циклического кода содержит k строк и n столбцов, ее ранг (). В проверочной матрице r строк и n столбцов, ее ранг .

Порождающая матрица неразделимого циклического кода

Порождающая матрица неразделимого ЦК строится на базе порождающего полинома g(х) и содержит k линейно независимых строк g(х), х¹ g(х), …, х^{к-1 g(х)}:

(28)

где g₀, g₁…g_r - коэффициенты порождающего полинома (12);

0 - нулевые символы, дополняющие каждую строку до n -разрядной.

Матрица (28) не является канонической

С использованием матрицы (28) формируются кодовые комбинации неразделимого циклического кода путем поразрядного умножения информационной комбинации А_k на каждый из столбцов матрицы (28) и суммирования по модулю два результатов умножения.

Пример 15. Сформировать порождающую матрицу неразделимого циклического кода (7;4) с порождающим полиномом g(х)=х³+х+1; r=3; k=4; d₀=3. Для формирования первой строки матрицы следует взять кодовую комбинацию с n=7, соответствующую порождающему полиному g(х) (очевидно, что она будет делиться без остатка на порождающий полином g (x)).

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

а₁(х)= х³+х+1 0001011.

Остальные три разрешенные комбинации находятся циклическим сдвигом полученной кодовой комбинации, т.е. умножением а₁(х) на х, х², х³. В результате имеем

а₂(х)= а₁(х)^.х 0010110

а₃(х)= а₁(х)^.х² 0101100

а₄(х)= а₁(х)^.х³ 1011000.

В итоге порождающая матрица неразделимого циклического кода имеет вид:

Порождающая матрица разделимого циклического кода

Для формирования разделимого циклического кода с помощью матрицы используют каноническую приведенно-ступенчатую порождающую матрицу . Она содержит единичную подматрицу I_k рангом и проверочную подматрицу G^* рангом . Проверочные символы для каждой из k строк матрицы определяются тем же способом, что и при формировании разрешенных кодовых комбинаций разделимого циклического кода: информационная кодовая комбинация, преобразованная в полином а_k-1(x), умножается на х^r и затем произведение а_k-1(x)^.х^r делится на порождающий полином g(х) для нахождения остатка R(х) и т.д. Кодовые комбинации разделимого циклического кода формируются с использованием порождающей матрицы таким же образом, как в систематических линейных блочных кодах.

Пример 16 Сформировать каноническую порождающую матрицу разделимого циклического кода (7;4) с порождающим полиномом g(х)=х³+х+1. Кодовая комбинация кода (7;4) содержит k=4 информационных символов, r=3 проверочных и общее число символов n=7. Единичная матрица кода имеет вид:

.

Для определения проверочных символов первой строки преобразуем информационную комбинацию 1000 в полином (1000 х³) и умножим его на х^r. Полученное произведение х^3.х³=х⁶ разделим на порождающий полином g(х):

Полученный остаток от деления переведем в двоичный вид с учетом разрядности строк проверочной подматрицы: В итоге первая строка канонической порождающей матрицы примет вид: 1000 101. Для нахождения второй, третьей и четвертой строк матрицы произведем деление на полином g(х) соответствующих одночленов х⁵, х⁴, х³. Получим:

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

.

Проверочные матрицы циклических кодов

Проверочная матрица неразделимого циклического кода строится на базе проверочного полинома h(x) (14) и содержит r линейно независимых строк: h(x), х¹ h(x),…,х^r-1 h(x):

где h₀, h₁ …h_k - коэффициенты полинома h(x),

0 - нулевые символы, дополняющие каждую строку до n -разрядной.

Проверочную матрицу разделимого циклического кода можно сформировать, используя каноническую ступенчато-приведенную матрицу кода, аналогично тому, как это делается в систематических линейных блочных кодах. Как и в СЛБК, для матриц циклических кодов должно выполняться условие: .

Дата добавления: 2015-08-13