10.5. ОТОБРАЖЕНИЕ КОДОВ НАД GF(2^m) В ДВОИЧНЫЕ КОДЫ

Как мы знаем из гл. 4, элементы поля где могут быть представлены -векторами с элементами из Следовательно, -код РС над GF(q) становится -кодом над Если то, как мы сейчас увидим, двоичные коды, получаемые таким путем (и другие коды, полученные из них), часто имеют большое минимальное расстояние.

Пусть базис элементов поля над Тогда, если любой элемент где то отобразим в -вектор Это отображение переводит линейные коды в линейные (но циклические коды не обязательно переходят в циклические).

Примеры. (1). Используя базис 1, а для элементов над GF(2), получаем отображение: Тогда -код РС над изображенный на рис. 10.1, становится двоичным -кодом, который приведен на рис. 10 4.

Рис. 10.4 Двоичный [6, 4, 2] код, полученный из -кода изображенного на рис. 10.1

(2). Пусть вектор принадлежит -коду РС над Заменим каждый элемент соответствующим двоичным -вектором и к каждому такому -вектору добавим общую проверку на четность. Получившийся двоичный код будет иметь параметры

где К — любое, То же самое построение, примененное к расширенному коду приводит к

двоичным кодам, где

Например, из и -кодов над мы получаем [75, 40, 12] и [80, 40, 14] двоичные коды. Хотя существуют несколько лучшие коды — в гл. 12 мы построим [80, 40, 16] квадратично-вычетный код, простота этого построения производит глубокое впечатление (см. также § 18.8.1).

(3). Если в качестве базиса для элементов над выбрать то получим отображение:

Рассмотрим -код РС над с порождающим многочленом

Удивительно, что при данном отображении этот код переходит в [21, 15, 3] двоичный код БЧХ с порождающим многочленом Действительно, сам многочлен отображается в вектор представляющий многочлен Кроме того, отображается в Это единственный известный нетривиальный пример циклического кода, переходящего при таком отображении в циклический код!

Упражнение. (3). Пусть линейное отображение из на и пусть отображение векторов длины над на двоичные векторы длины индуцированное отображением Предположим, что — циклическии код над с порождающим многочленом двоичный циклический код с порождающим многочленом Показать, что отображает код на код тогда и только тогда, когда для всех кодовое слово является образом при отображении некоторого кодового слова, пропорционального

Задача (нерешенная). (10.1). Найти другие примеры циклических кодов, отображаемых на циклические коды.

Выбор базиса. Замена базиса может изменить весовой «спектр и даже минимальный вес кода. Например, рассмотрим -код МДР с идемпотентом и проверочным многочленом (Этот код не является кодом Кодовые слова (над представляют собой циклические перестановки девяти векторов, изображенных на рис. 10.5.

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

которое дает двоичные веса, приведенные в девятом столбце. Заметим, что минимальный вес, полученный при первом отображении, равен 8, в то время как при втором — только 6.

Рис. 10.5 Циклический код и веса двух двоичных кодов, полученных из него

Упражнение. (4). Показать, что первый двоичный код имеет следующий весовой спектр: Спектр второго кода таков:

Задача (нерешенная). (10.2). Для заданного кода над указать базис элементов поля над GF(2), который отображает код в двоичный код с наибольшим минимальным расстоянием. Как сильно сказывается выбор базиса на минимальном расстоянии кода Помогает ли использование нелинейных отображений?

Коды РС содержат коды БЧХ. Коды в примере 2 столь хороши, что заслуживают исследования их параметров при больших значениях Они ухудшаются, так как верна следующая теорема.

Теорема -код РС с корнями порождающего многочлена содержит примитивный двоичный код БЧХ длины и с конструктивным расстоянием Аналогично расширенный код РС содержит расширенный код БЧХ.

Доказательство. Если вектор с принадлежит коду БЧХ, то с — двоичный вектор такой, что с и поэтому он также принадлежит коду РС.

Следовательно, минимальное расстояние кода РС равно самое большее минимальному расстоянию кода БЧХ. Отсюда можно

вывести, что раз длинные коды БЧХ являются плохими (§ 9 5), то таковы же и длинные двоичные коды, полученные из кодов РС.

Теорема 3 Двоичные коды, полученные из кодов РС и имеющие параметры, заданные выражениями (10 4) и (10 5), являются асимптотически плохими, т. е. они не содержат бесконечного семейства кодов, у которых и скорость, и отношение расстояние/длина были бы отделены одновременно от нуля

Доказательство. Пусть -код РС В силу теоремы 2 код содержит двоичный БЧХ код длины с конструктивным расстоянием Определим следующим образом

так что код содержит код БЧХ с конструктивным расстоянием По теореме 5 гл. 9 расстояние представляет собой истинное минимальное расстояние кода 92

Пусть теперь двоичный -код с параметрами (10 4), полученный из кода (Доказательство для кодов с параметрами (10.5) аналогично) Тогда

Следовательно, еслискорость кода равную зафиксировать, то отношение

стремится к нулю, когда .

Однако если использовать лишь немного более сложное построение, то из кодов РС можно получить асимптотически хорошие двоичные коды (см § 10 11)