12.3. Теоремы о числе последовательностей

Пусть V — некоторая -ичная последовательность, превосходящая все свои собственные суффиксы. Тогда

12.31. Никакая субпоследовательность для V не является собственным префиксом никакой другой субпоследовательности для

12.32. Каждый суффикс любой субпоследовательности для V является сцеплением других субпоследовательностей для

12.33. Если последовательность и все ее циклические сдвиги меньше V, то однозначно представима в виде сцепления субпоследовательностей для V, включая (возможно, пустую) окаймляющую субпоследовательность. А именно

субпоследовательности для окаймляющая субпоследовательность. Окаймляющая субпоследовательность имеет префикс который является суффиксом для и суффикс который является префиксом для как сцепление более коротких субпоследовательностей

12.34. Каждое сцепление субпоследовательностей для V, включающее (возможно, пустую) окаймляющую субпоследовательность, дает последовательность, обладающую тем свойством, что все ее циклические сдвиги меньше Никакая из таких последовательностей длины не может превышать максимального сцепления субпоследовательностей для V длины Если максимальное сцепление длины субпоследовательностей для то

12.35. , где если превосходит длину последовательности

12.36. Пусть

Если

то

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

12.32. Докажем сначала более слабое утверждение:

12.321. Каждый собственный суффикс любой субпоследователъности для V имеет префикс — более короткую субпоследовательностъ для

Пусть некоторая субпоследовательность для V, и пусть суффикс для Можно записать Так как отличается от V только своей последней цифрой, то является префиксом для Так как Так как V превосходит свои собственные суффиксы, то Отсюда следует, что Следовательно, некоторый префикс для является субпоследовательностью для

12.322. Если каждый суффикс субпоследователъности имеет префикс, являющийся субпоследователъностъю, то каждый суффикс каждой субпоследователъности является сцеплением субпоследовательностей.

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

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

собственный префикс любой другой субпоследовательности для V, то должна быть пустой,

12.34. Это утверждение является обратным по отношению к утверждению 12.33. Предположим, что дана последовательность где и субпоследовательности для Нужно показать, что все циклические сдвиги меньше Произвольный циклический сдвиг имеет вид где Если пустая последовательность, то С имеет префикс субпоследовательность для Если последовательность не пустая, то, согласно утверждению 12.32, она имеет префикс, который является субпоследовательностью для V и префиксом для С. В любом случае С имеет префикс — субпоследовательность для Следовательно,

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

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

12.36. Наименьшая последовательность. Предположим, что наименьшая последовательность длины большая чем Введя обозначения получаем, что или Согласно лемме 12.23,

12.36. Наибольшая последовательность. Пусть наименьшее сцепление суперпоследовательностей для V длины Тогда наибольшее сцепление суперпоследовательностей для V длины . В обозначениях леммы 12.23 . Полагая имеем Полагая получаем, что так как Теорема вытекает из утверждения 12.34 и леммы 12.23.

12.36. Справедливость утверждения в общем случае следует из монотонности как функции от

12.37. Пример. Положим Тогда имеет место

Таблица 12.1 (см. скан)

Здесь подсчитано, согласно теореме 12.35, а конструктивные расстояния — в соответствии с теоремой 12.36 при с субпоследовательностями и .

Очевидно, что двоичный БЧХ-код с и конструктивным расстоянием 768 совпадает с двоичным БЧХ-кодом с и конструктивным расстоянием 769 или 770, или или 819, но отличается от двоичного БЧХ-кода с и конструктивным расстоянием 820. Это справедливо в общем случае, так как наименьшее сцепление длины суперпоследовательностей для V необходимо является минимальным среди всех его собственных циклических сдвигов. Это наибольшее конструктивное расстояние называется расстоянием Боуза.

Двоичный БЧХ-код с блоковой длиной 212 — 1 и конструктивным расстоянием 768 отличается также от двоичного БЧХ-кода с блоковой длиной с конструктивным расстоянием 767, поскольку двоичное представление числа 767 длины 12 является минимальным среди всех его циклических сдвигов. Это, однако, не выполняется в общем случае. Например, двоичный БЧХ-код с блоковой длиной 24—1 и конструктивным расстоянием 3 не отличается от двоичного БЧХ-кода с блоковой длиной 24—1 и конструктивным

расстоянием 2, так как двоичное представление числа 2 не является минимальным среди своих циклических сдвигов (минимальный среди сдвигов равен 0001).

В общем случае нам необходимо определить число информационных позиций -ичного БЧХ-кода с блоковой длиной и конструктивным расстоянием Теоремы 12.23 и 12.35 дают решение этой задачи, если удастся найти последовательность V, которая больше всех своих собственных суффиксов и обладает тем свойством, что

Переход к дополнениям в этом условии дает

или

где X — наибольшая субпоследовательность для Можно предположить, что V не имеет нулей на конце и что длина V не превосходит длины Так как имеют одну и ту же длину, то X - префикс

Так как V — наименьшая суперпоследовательность X, то задача отыскания V сводится к нахождению последовательности X, являющейся префиксом Решение этой задачи дается теоремой 12.38.

12.38. Теорема. Пусть X — кратчайший префикс такой, что и пусть V — наименьшая суперпоследователъность для Тогда наименьшего сцепления длины суперпоследователъностей для

12.382. V превосходит все свои собственные суффиксы.

Доказательство 12.381. Так как X — префикс суперпоследовательность для X, то V — суперпоследовательность для Таким образом,

Дополнение дает неравенство так что

Пусть Тогда неравенство эквивалентно неравенству Следовательно, или Используя индукцию, получаем, что для всех к. Так как это справедливо для произвольно большого к, то

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

Доказательство 12.382. Пусть где произвольные (возможно, пустые) последовательности и последняя цифра последовательности Тогда

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

Никакой собственный суффикс V не совпадает с V, так как суффикс должен быть короче.

Если некоторый собственный префикс скажем возможно, — пустая последовательность), превосходит V, то

Если то что дает противоречие. Если префикс для X, то и из неравенства

выводим, что

Теперь префикс, более короткий, чем X, что приводит к противоречию. Таким образом, следовательно, V превосходит все свои собственные суффиксы.