Доказательство. 12.31. Это свойство субпоследователь-* ностей даже не зависит от условий, налагаемых на суффиксы F. Согласно определению субпоследовательностей, каждая субпосле4 довательность должна отличаться от F только своей последней h;h(J рой, и, следовательно, ни одна субпоследовательность не может быт* префиксом некоторой другой.

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

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

Пусть iS - некоторая субпоследовательность для F, и пуст S() - суффикс для 5. Можно записать S = 5() * 8<У. Так ка S отличается от V только своей последней цифрой, то 5) являете! префиксом для F и F = S() * V(h Так как 5 < F, то S() < F(2 )J Так как V превосходит свои собственные суффиксы, то F() <; Отсюда следует, что 5() < F. Следовательно, некоторый преф! для является субпоследовательностью для V.

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

Действительно, предположим, что F - суффикс некоторой су последовательности. Тогда F = 5(> * F(), где В-) - субпосле;] вательность. Так как F<) является суффиксом для F, то F<) являе ся также суффиксом для субпоследовательности, и Ff) = * F где Б() - субпоследовательность F = * Б() * * .

12.33. Так как TF <; F, то существует префикс TF(), котор! является субпоследовательностью для F. После сдвига этого преф! са в конец слова можно аналогично поступить с PF(*), PFO, .

. . ., TF(~•), каждая из которых является субпоследовательност! для F. Последовательность WO) . TF(i) . W<) ..... W<-1

циклический сдвиг W ш, следовательно, имеет префикс Р, являюг ся субпоследовательностью для V. Р не является префиксом для WU так что TF<) должна быть префиксом для Р. Предположим, Wb * PF() ..... TF<) - префикс для Р, а W() . W<-) *

.... TF(*+) не является префиксом Р (это определяет i). Tor

Р = TF( . ..... TF(*) . S, где (возможно, пустая) после?

вательность S является собственным префиксом для TF(+. Так S - суффикс для Р, а Р в свою очередь является субпоследовател ностью для V, то S - сцепление субпоследовательностей для Но так как никакая субпоследовательность для F не есть собств

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

12.34. Это утверждение является обратным по отношению к утверждению 12.33. Предположим, что дана последовательность W = S) * TF(i) . TF(2) ..... TF(-i) . pO), где WK W(\ . . . . . ., W(-> и TF()=P(. 5()-субпоследовательности для F. Нужно показать, что все циклические сдвиги W меньше V. Произвольный циклический сдвиг имеет вид С = S * TF(+i) ..... TF() .

* F(i) . TF(2) ..... H(fc-i) . где W") = PC) . Si"). Если Si) пустая последовательность, то С имеет префикс PF(+) - субпоследовательность для F. Ъсли последовательность S(") не пустая, то, согласно утверждению 12.32, она имеет префикс, который япляется субпоследовательностью для V и префиксом для С. В любом случае С имеет префикс - субпоследовательность для F. Следовательно, С <; F.

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

Если W - сцепление нескольких субпоследовательностей для V, т. е. TF.= TF(i) . TF(2) ..... TF(-i) . где TF(M, W(\ . . .

. . ., PF() - субпоследовательности для F и PF() - (возможно, пустой) собственный префикс субпоследовательности TF() . W> »

* TF() ..... TF(*), то длина W равна сумме длин WO-) и tF(i) .

* IF() ..... fF(*-2) . TFC). Для каждого А; существует F способов выбора последовательности TF(-i) длины А; и / (д, F, m - А:) способов выбора IF() * TF() ..... TF(-2) . TF().

12.36. Наименьшая последовательность. Предположим, что D - наименьшая последовательность длины т, большая чем V * {Q - 1).

Введя обозначения d = S у = S Fi?""-*, у = S

Получаем, что d + f = и + 1 или v = п + 1 - d. Согласно лемме 12.23, Iiq,n,d)=J {q, V, т).

12.36. Наибольшая последовательность. Пусть D - наименьшее сцепление суперпоследовательностей для V длины т. Тогда D - наибольшее сцепление суперпоследовательностей для V длины т. В обозначениях леммы 12.23 D ~ Y. Полагая d = 2 Di<f~, имеем d ~ п - d. Полагая п -f 1 - d = 2 получаем, что

и >. Y, так как ra-f-l-d>n - d. Теорема вытекает из утверждения 12.34 и леммы 12.23.

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

1) Определение дается ниже.

2) Этот код совпадает с двоичным БЧХ-кодом с блоковой длиной п и конструктивн расстоянием 2.

Здесь / {q, V, тп) подсчитано, согласно теореме 12.35, а констрз тинные расстояния - в соответствии с теоремой 12.36 при V = 001 с субпоследовательностями 1, 01 и ООН.

V *{Q - 1) = 001011111111... .

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

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

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

В общем случае нам необходимо определить число информационных позиций д-ичного БЧХ-кода с блоковой длиной п = q" - i и конструктивным расстоянием d = 2 Теоремы 12.23

п 12.35 дают решение этой задачи, если удастся найти последовательность V, которая больше всех своих собственных суффиксов и обладает тем свойством, что

F.((?-l)

наименьшее сцепление длины т

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

fнаибольшее сцепление длины тп [субпоследовательностей для V j

. Г(наибольшее сцепление длины ml

V>D*{Q-l)>{ Л>Х,

(субноследовательностей для F) * 0J

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

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

12.38. Теорема. Пусть X - кратчайший префикс D, такой,

что D = X * F, F * {Q - \) D * {Q - V), и пусть V - наименьшая суперпоследователъность для X. Тогда

12.381. V * {Q - 1) < Z? наименьшего сцепления длины т суперпоследовательностей для V.

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

Доказательство 12.381. Так как X - префикс i> и F - сунерпоследовательность для X, то V - сунерноследовательность

для D. Таким образом, V> D и V :> D * {Q - 1).

Дополнение дает неравенство V * {Q - 1) <i D * О, так что

V*{Q-i)<cD.

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

Таблица 12 1 \

Пусть Х") = X * X * . .* Z. Тогда неравенство F * (<? - 1) Z? • ((? - 1) эквивалентно неравенству ZC) * F « ((? - 1) > Х() *F *{Q - \). Следовательно, X * Х(0) . F . (<? - 1) > X . Х*) . F . - 1) или Z(i) . F . - 1) > Z(2) . F . {(? - 1). ИСПОЛ! зуя индукцию, получаем, что X() * F * {Q - I) Z(+) » F *{Q -I) и D * {Q- 1) > ХС") *F*{Q ~1) для всех А;. Так кав это справедливо для произвольно большого к, то D * {Q ~ I) Х

Переходя к дополнениям, получаем, что D * О X любо! бесконечного сцепления суперпоследовательностей для V. Следова тельно,

D (любое сцепление длины пг суперпоследовательностей для Vjl

Доказательство 12.382. Пусть X = Y * Z * L, где Fj Z - произвольные (возможно, нустые) последовательности и L последняя цифра последовательности X. Тогда

V = ¥ *Z*{L + 1), D = Y*Z*L*F,

F * {Q - I) * Z * L * F * (Q - i) = X * F * {Q - i); X*F*{Q - i) = Y*Z*L*F*{Q-i)>Z*L*F*{Q - i);

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

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

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

Z * {L + I) > Y * Z * {L + i) >Y * Z * L = X.

Если Z*L>X, то Z * L * F *{Q - !)> X * F * {Q - 1), дает противоречие. Если Z * L - префикс для X, то X = Z * L * и из неравенства

X*F*{Q -1)>Z*L*F*{Q -I)

выводим, что

Z * L *G*F * {Q - 1)>Z * L* F *{Q - I); G*F*{Q-i)>F*{Q-i)X *F*iQ -I).

Теперь Z * L - префикс, более короткий, чем X, что приводит к противоречию. Таким образом, Z * (L + 1) < У * Z * (L + 1) и, следовательно, V превосходит все свои собственные суффиксы, щ

*12.4. Примеры

12.41. Пример. Пусть g = 9, и = 728 = 9 - 1, d = 217. Тогда D = 261, D = 627, 5* 8 = 627888..., X = 62, F = 63, V = 25.

Расстояние Боуза

1) в этой и последующих таблицах для обозначения J (q, V, т) используется единственная буква J.

12.42. Пример. Пусть q = 2, п = 511, d = 185. Тогда D = = 010111001, D = ЮЮООШ, 5. 1 = 101000 110111111, X = = 101000, V = 101001, F = 010110. Суперпоследовательности: 010111, 011, 1.

12.43. Пример. Пусть g = 2, п = 511 = 2» - 1, d = 187. Тогда D = 010111011. D = 101000100 = X, F = 101000101, F = = 010111010.