3.7. Укороченные коды

Предположим, что линейный -код С имеет порождающую матрицу, первые столбцов которой являются линейно независимыми Множество кодовых векторов, первые компонент которых равны 0, образует подпространство размерности пространства (кода) С. Множество С векторов длины полученных удалением первых компонент из таких кодовых векторов, образует линейный -код. Эта процедура называется укорачиванием, а код С — укорочением кода С. Минимальное расстояние С не меньше, чем минимальное расстояние С. В частности, если С — циклический код, то С называется укороченным циклическим кодом. Порождающая матрица кода С получается из порождающей матрицы вида (3.20) кода С путем удаления первых строк и столбцов. Проверочная матрица кода С получается удалением первых столбцов из проверочной матрицы кода С. Если вектору (здесь поставить в соответствие многочлен (а не класс вычетов по модулю как в случае циклических кодов), то, как следует из (3.20) и указанного выше способа построения будет кодовым вектором тогда и только тогда, когда делится на порождающий многочлен кода С. Так как

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

Утверждение 3.19 [38]. Пусть целые числа, удовлетворяющие следующему неравенству.

где -число неприводимых многочленов степени над полем Тогда существует двоичный укороченный циклический код длины с минимальным расстоянием или более, порождаемый неприводимым многочленом степени

Краткое доказательство. Число многочленов над степени не выше со свободным членом, равным 1, и не более чем с ненулевыми коэффициентами равно

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

Утверждение 3.20 [38]. Неравенство в формулировке предыдущего утверждения можно заменить на неравенство

где при и фиксированных отношениях Другими словами, при больших укороченные циклические коды достигают нижней границы Варшамова — Гилберта.

Идея доказательства. Следует воспользоваться верхней границей Чернова и неравенством (2.13).