12.2. Сведение задачи для случая примитивных БЧХ-кодов к перечислению некоторых q-ичных последовательностей

Мы покажем, как найти число информационных символов примитивных БЧХ-кодов путем перечисления последовательностей некоторого определенного вида над алфавитом из чисел Этот метод был предложен Манном [1962]. Начнем с определения необходимых операций над такими последовательностями.

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

Пусть некоторая -ичная последовательность, Обозначим через дополнение к V, где для всех Если конечная -ичная последовательность, то под ее циклическими сдвигами понимаются конечная -ичная последовательность, то можно построить сцепление Сцепление моашо строить независимо от того, является ли конечной или бесконечной -ичной последовательностью. Если при этом конечна, то является циклическим сдвигом

Пусть есть -ичная последовательность. Она называется префиксом X, если для некоторой последовательности называется суффиксом X, если Префикс всегда конечен (или пуст), а суффикс может быть пустым, конечным или бесконечным. называется собственным префиксом X тогда и только тогда, когда ни У, ни не являются пустыми. Аналогично, собственный суффикс X тогда и только тогда, когда и не пусты. Если X — конечная -ичная последовательность, то можно образовать бесконечную последовательность, являющуюся ее многократным сцеплением . В частности, означает бесконечную последовательность, всеми буквами которой является число

Введем упорядочение: тогда и только тогда, когда существует такое что для но Если то одна последовательность — префикс другой.

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

12.21. Теорема. Пусть

и пусть не является суффиксом последовательностей Тогда

Назовем X субпоследователъностъю для если конечна и но Последовательность имеет субпоследовательностей длины субпоследовательностей длины субпоследовательностей длины к. Если последовательность имеет только конечное число ненулевых букв, то можно определить наибольшую последовательность для Если последняя ненулевая буква последовательности то наибольшая субпоследовательность для Если последовательность содержит бесконечно много ненулевых букв, то имеет бесконечно много субпоследовательностей. Каждая из них меньше но ни одна не является наибольшей.

Аналогично, называется суперпоследователъностъю для X, если где но Если то наименьшей суперпоследователъностъю для X является где для Ясно, что наименьшая суперпоследовательность лежит среди наиболее длинных суперпоследовательностей, а наибольшая субпоследовательность — среди наиболее длинных субпоследовательностей.

12.22. Определение. Если некоторое натуральное число и некоторая бесконечная -ичная последовательность, то определим как число -ичных последовательностей длины все циклические сдвиги которых меньше

12.23 (Манн). Лемма. Если

— некоторая -ичная последовательность, то

Доказательство. Лемма 12.23 сводится к лемме 12.12 с помощью следующего соответствия. Согласно условию, последовательности соответствует число Другой -ичной последовательности длины можно сопоставить число Тогда последовательности являющейся первым циклическим сдвигом будет соответствовать число

сравнимое по модулю с числом Следовательно, соответствующим циклическим сдвигам отвечают числа Эти числа исчерпывают все числа тогда и только тогда, когда для любого

Выбор в качестве последовательности имеет интересную интерпретацию:

последовательность является -ичным представлением числа Это позволяет при больших и фиксированном отношении свести исследование числа к изучению как функции от при фиксированных

Временно будем пренебрегать периодичностью и рассматривать для произвольной -ичной последовательности Мы будем предполагать только, что последовательность V не имеет на конце нулей.

Из определения субпоследовательности для V ясно, что если -ичная последовательность длины меньше V, то некоторая субпоследователъностъ для V является префиксом Действительно, если то существует номер к, такой, что для , но и последовательность является одновременно префиксом и субпоследоватедьностью для

Предположим теперь, что некоторая последовательность длины и все ее циклические сдвиги меньше Так как сама последовательность меньше V, то некоторый ее префикс является субпоследовательностью для Являются ли все возможные субпоследовательности возможными префиксами Вообще говоря, нет, так как некоторые субпоследовательности могут иметь суффиксы, которые больше, чем Если является субпоследовательностью для больше V, то не может быть префиксом Действительно, если то одним из циклических сдвигов является последовательность

Например, рассмотрим троичную последовательность Ее субпоследовательностями являются 0; 1; 200; 201; 2020; 20210 и 20211. Субпоследовательность 20210 имеет суффикс 210, который больше V, следовательно, если 20210 является префиксом то второй левый циклический сдвиг больше, чем Аналогично субпоследовательность 20211 имеет суффикс 211, который также больше

Для некоторых последовательностей V такая трудность не возникает. Если V превосходит все свои собственные суффиксы, то справедливы следующие теоремы 12.3.