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

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

Пример. Если в -коде в примере из разд. 8.2 опустить первый информационный символ, то получится -код с порождающей матрицей и проверочной матрицей Н:

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

Укороченный код обладает по крайней мере столь же большим минимальным кодовым расстоянием, как и код, из которого он

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

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

Теорема 8.5. Всякий псевдоциклический код с минимальным весом. большим 2, является циклическим кодом или укороченным циклическим кодом.

Доказательство. Пусть - многочлен степени и пусть некоторый идеал в алгебре многочленов по модулю т. е. псевдоциклический код. Тогда в соответствии с утверждениями теорем 6.9 и 6.10 существует приведенный многочлен порождающий идеал, и вектор принадлежит идеалу тогда и только тогда, когда многочлен делится на Пусть наименьшее целое число, при котором многочлен делится на Тогда так как иначе вектор был бы кодовым вектором веса 2. Поэтому многочлен порождает циклический код длины причем вектор принадлежит этому коду тогда и только тогда, когда многочлен делится на Если этот циклический код совпадает с псевдоциклическим кодом, порожденным многочленом Если и если укоротить этот циклический код, оставляя только те кодовые векторы, у которых компоненты все равны 0, и вычеркивая эти компоненты, то получится в точности тот же самый псевдоциклический код. Ч. т. д.

Теорема 8.6. Всякий укороченный циклический код является псевдоциклическим кодом.

Доказательство. Предположим, что многочлен порождает циклический код длины и рассмотрим укороченный циклический код длины полученный из этого кода. Равенство (6.4) можно переписать в виде

где многочлен степени меньшей, чем степень Положим и рассмотрим алгебру многочленов по модулю Из равенства (8.12) видно, что многочлен делится на многочлен По теореме 6.10 многочлен порождает идеал,

и, следовательно, псевдоциклический код, который, как нетрудно проверить, совпадает с рассматриваемым укороченным циклическим кодом. Ч. т. д.