300 Гл. 12. Нахождение числа информационных символов в БЧХ-кодах ЧТО доказывает такую теорему:

12,62. Теорема.

J{q, V, т) = ЗрГ,

где рг - комплексные числа, определенные уравнением

1-(2)=n:{i-piz).

Эта теорема дает точное выражение для / (q, V, т), но оно зав сит от комплексных чисел р. Для конечных значений т вычисля / {q, V, т) обычно легче по рекуррентному соотношению tooj мы 12.35, так как эти вычисления относятся только к целым числг Однако полученное уравнение очень полезно для получения асв тотических результатов.

12.63. Определение. Пусть

p = maxpi и s = loggp.

Так как все коэффициенты многочлена V (z) неотрицателы числа, не превосходящие g - 1, то легко видеть, что числа pj с макс мальным модулем вещественны и положительны и 1 р д. Ясв что для больших т

J {q, V, т) ~ p"

в том смысле, что

Аналогично, Если

Иш p-V(g,F, т)=1.

га->оо

logg / (q, V, т) т logg р = ms.

где V превосходит все свои собственные суффиксы я X - мав мальная подпоследовательность V, то

7 (д, - 1, щП ~

или, более точно.

(12.64)

S (и) = Иш

Для данного q функция s (и) является довольно сложной. Для того чтобы ее найти, надо сначала написать д-ичное представление числа и. Если U превосходит все свой собственные суффиксы, то полагаем F = Z7; в противном случае полагаем U - X * F, где X - наименьший префикс, для которого Z7 F. В качестве F выбирается затем наименьшая суперпоследовательность для X, в. s определяется как логарифм (по основанию q) максимального взаимного корня многочлена 1 - F (z).

Пример функции s (и) для q = 2 приведен на рисунке 12.1.

м(и)

1,0 0,9 0,8

0,7 0,6 0,5 0,4 0,3 0,2 0,1

°0 0,0001 0,0010 0,0011 0,0100 0,0101 0,0110 0,0111 0,100 и (а двоичной системе)

Рис. 12.1. График поведения s (м) как функции от и.

Другими словами, если фиксировать отношение d/n п и d быстрорастущими, то

и и считать

Легко показать, что s (и) - непрерывная монотонно невозрастаю-щая функция от и. Нетрудно также показать, что производная от sj по ы в каждой точке либо равна О, либо не определена; при этом имеются точки неопределенности s (и) двух видов. Во-первых, концы интервалов, на которых s (и) постоянна. Точка и - левый конец такого интервала тогда и только тогда, когда U - конечная после» довательность, превосходящая все свои собственные суффиксы! i и - правый конец такого интервала тогда и только тогда, когд и - периодическая последовательность, равная некоторому своем£ суффиксу, но меньшая, чем все остальные суффиксы. В указанный концах интервалов s (и) не определена потому, что s (и) имеет нроиз водную толБко слева или только справа. Число точек такого типаЦ счетно.

Более интересными представляются точки, в которых s (и) н»1 имеет ни левой, ни правой производной. Это имеет место тогдй и только тогда, когда U - бесконечная последовательность, нре восходящая все свои собственные суффиксы, и О не является суффик сом и.

Множество точек и, в которых функция s (и) не дифференцируема несчетно, но имеет меру 0. Питчер [1966] доказал также, что это мне жество имеет размерность по Хаусдорфу 1. Это обусловливаете большой плотностью множества этих точек в окрестности точк U = 0. В общем случае можно высказать гипотезу, согласно которо зазмерность по Хаусдорфу множества точек на интервале а ы " где О < а < Ь < 1; s {а) Ф s (Ь)] равна s (а). В некотором смысл представляется справедливым, что множество точек недифферо! цируемости функции s (и) в любом интервале сосредоточено вблиЕ левого конца этого интервала.

Для частного случая и =д" изложенные выше результаты bhcj вые были получены Манном. Он также показал, что р - единстве! ный взаимный корень многочлена 1 - V (z), модуль которого боль ше 1. Таким образом, не только

~ р

но ДЛЯ достаточно больших т

где (х) означает ближайшее целое к х. К сожалению, этот боле сильный результат не имеет места в общем случае. Для некоторы значений и многочлен 1 - F (z) имеет только один взаимный коре! с модулем, большим единицы, а для других значений и многочле! 1 - F (z) имеет много таких взаимных корней. Мало также известн о том, какими функциями от и являются комплексные корни мног члена 1 - F (z) с меньшими модулями, хотя в этом нанравле! Логан [1967] получил некоторые предварительные неонубликова!

*12.7. Истинные расстояния

Если увеличивать конструктивное расстояние, то число информационных символов кода либо остается постоянным, либо уменьшается. Поэтому справедливо утверждение:

12.71. Т е о р е м а. I (q, п, d) равно максимальному числу информационных символов во всех БЧХ-кодах с конструктивным расстоянием d.

Будем отличать величину / от величины /, определенной следующим образом:

12.72. Определение. I (q, п, d) - максимальное число информационных символов для всех д-ичных БЧХ-кодов с истинным расстоянием d.

Очевидно, / ((?, n,d)I (q, п, d).

Например, есть три двоичных БЧХ-кода с блоковой длиной 23 и соответственно с 23, 12 и 1 информационными символами. Читателю нетрудно проверить, что

{23, если d= 1; 12, если 2<d<5; 1, если 6<d<23.

В разд. 15.2 будет показано, что

{23, если d=l; 12, если 2<d<7; 1, если g<d<23.

Следовательно, / (2, 23, 7) > / (2, 23, 7).

Случаев, когда / (д, п, d)> I (g, n, d), известно сравнительно немного. Казами, Лин и Питерсон [1966] высказали гипотезу о том, что / (2, 2" - 1, d) = / (2, 2"- - 1, d) для всех m и d, и доказали ее для некоторых частных случаев. Хотя в общем случае эта гипотеза остается гипотезой, можно получить некоторые результаты об асимптотическом поведении функции / (2, 2"* - 1, ы2"), отталкиваясь от известных частных случаев, когда / (2, 2"" - 1, d) = / (2, 2*" - - 1, d). Удобно было бы положить

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

,0 7Q\ \ 1- l0g2/{2, 2™ -1, иг"»)

12.73) S {и) = Iim sup -Lj-:-L

Очевидно, что s (и) s (и). Подобно s (и), функция s (и) - невоз-стающая функция от и, так как при d > d кодовые слова д-ичного 1Х-кода с расстоянием d образуют подмножество кодовых слов 1ЧН0Г0 БЧХ-кода с расстоянием d.

Мы докажем, что s {и) = s (и) для некоторых значений и, указан-[X в теореме 12.74.

12.74. Теорема. Если и 2", то s (и) s (2*).

Доказательство. Пусть и 2". Согласно следствию .63, для любого т к

1(2, 2\ u2")</(2, 2"-1, 2"--1) = /(2, 2"-1, 2"-"-

едовательно.

•1)-

log/(2, 2"-1. »2") log/(2, 2"-1, 2"-"-!)

i что в силу непрерывности функции s{u)

~, \ л- log/(2, 2"

1, 2™-"-!)

Это показывает, что s (ы) = s (и), если и = 1/2, 1/4, 1/8, . . . пользуя теоремы 11.66 и 13.12, можно также доказать, что s (и) S (ы) для различных других значений и. Представляется верпов ютеза о том, что s (и) = s (и) для всех и. Эта гипотеза являете* 1аблением предположения Питерсона о том, что / (2, 2™ - 1, d) I (2, 2™ - 1, d) для всех т и, d.

Согласно равенству (12.73), примитивный БЧХ-код с больше! эковой длиной п и конструктивным расстоянием d = ип имее иблизительно и") информационных символов. Скорость передач я этого кода приблизительно равна «[("-Ч. Так как s (и) я. всех U > О, то при фиксированном и = d/n скорость передач а длинных БЧХ-кодов стремится к О при и -v оо. Аналогично дл инных примитивных БЧХ-кодов с истинным расстоянием Щ орость передачи стремится к О как nts(")-i]. Хотя функция s (i не известна, согласно теореме 12.74, s (ы) < 1 для всех и

В гл. 13 будет показано, что «оптимальные» блоковые коды с бол! й блоковой длиной асимптотически намного лучше, чем примитв

ные БЧХ-коды с большой блоковой длиной. Скорость R (и) лучших блоковых кодов с большой длиной и истинным расстоянием ип не зависит от п. Хотя соотношение между R и d/n в обш;ем случае не известно, эти величины могут быть описаны с помош;ью различных границ, которые будут выведены в гл. 13.

Задачи

12.1. Показать, что результаты разд. 12.5 совпадают с результатами разд. 12.3, если / = 1.

12.2. Для каждой из приводимых ниже пар блоковых длин и конструктивных расстояний вычислить число информационных символов в двоичном БЧХ-коде любым из подходящих способов. Для каждого из этих кодов вычислить также расстояние Боуза.

(a) п = 511, d = 65,

(b) п = 511, d = 88,

(c) п = 1365, d = 200,

(d) п = 341, d = 50,

(e) п = 13107, d = 2180,

(f) п = 819, d = 137,

(g) ,1 = 79, d = И.

12.3 (Манн [1962]). Пусть V (z) и р; определены так же, как в разд. 12.6. Показать, что если и = q~k, то существует единственное число р., модуль которого больше 1.

12.4. Графически показать примерное поведение

logg/(?, gm-1, uqm) lim -

m-+oo ог

как функции от и для д = 3, i, 5.

12.5. При д =2 исследовать верхние границы длях (и). Начертить примерный график наиболее точной из границ, которую удастся получить. (Использовать теоремы 12.74 и 11.66.)

еть асимптотическое поведение лучпшх БЧХ-кодов, используем едующее определение: