Укороченные циклические коды

Матричная запись циклического кода

Полная образующая матрица циклического кода M_n,_k составляется из двух матриц: единичной I_k (соответствующей k информационным разрядам) и дополнительной С_k,n-k (соответствующей проверочным разрядам):

M_n,k = || I_kC_k,n-k ||

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

Дополнительную матрицу можно определить и не строя I_k. Для этого достаточно делить на g(x) комбинацию в виде единицы с рядом нулей и получающиеся остатки записывать в качестве строк дополнительной матрицы. При этом если степень какого-либо r(х) оказывается меньше n – k – 1, то следующие за этим остатком строки матрицы получают путем циклического сдвига предыдущей строки влево до тех пор, пока степень r(х) не станет равной п-k— 1. Деление производится до получения k строк дополнительной матрицы.

Пример 36. Запишем образующую матрицу для циклического кода (15,11) с порождающим многочленом g(x) = х⁴ + х³ + 1.

Воспользовавшись результатами ранее проведенного деления, получим

Существует другой способ построения образующей матрицы, базирующийся на основной особенности циклического (n, k)-кода. Он проще описанного, но получающаяся матрица менее удобна.

Матричная запись кодов достаточно широко распространена.

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

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

Следовательно, необходимо брать многочлен четвертой степени и тогда n= 15. Такой код рассчитан на 11 информационных разрядов.

Однако можно построить код минимальной разрядности, заменив в (n, k)-коде j первых информационных символов нулями и исключив их из кодовых комбинаций. Код уже не будет циклическим, поскольку циклический сдвиг одной разрешенной кодовой комбинации не всегда приводит к другой разрешенной комбинации того же кода. Получаемый таким путем линейный (n-j, k-j)-код называют укороченным циклическим кодом. Минимальное расстояние этого кода не менее, чем минимальное кодовое расстояние (n, k)-кода, из которого он получен. Матрица укороченного кода получается из образующей матрицы (n, k)-кода исключением j строк и столбцов, соответствующих старшим разрядам. Например, образующая матрица кода (9,5), полученная из матрицы кода (15,11), имеет вид