Глава 12

Нахождение числа информационных СИМВОЛОВ в БЧХ-кодах

12.1. Сведение зада" перечислению некоторых чисел по модулю

Любой цикличес!* блоковой длиной п над нолем GF (q) можн определить порождР™"** многочленом g {х) - делителем многЫ члена а:" - 1 и щоверочным многочленом h {х) = (а:" - \)lg {х)1 Степень g (х) опы проверочных позиций, степей

h (х) - число шно? позиций, в дальнейшем числа й и предполагаются простыми, а рассмотрение проводите

в расширении GF (Л " мультипликативна

порядок q по модуля 1 расширении многочлен л; - 1 лагается на разлиые линейные множители:

x--l=f[(x-a%

где а - примитивней Р ""1 f единицы в нол« GF (о™) а" = 1 Ш разложения ж - 1 = g (х) h (х) следует, чт

каждая степень а явГ"" Р "1

ческий код задает разбиение всех степеней а на два ненересекающиг

ся нодмножества:«°«° Р* порождающего многочле! и множество KopneJ* проверочного многочлена. Обратно если дл1 g(x)iih (х) донуска/ коэффициенты из GF (g™), то любое разбив ние всех степеней а Два непересекающихся подмножества опреде ляет циклический коэффициенты многочленов g (а

и h (х) должны лежать « основном ноле GF (q). Следовательно вмест с корнями g (х) рляются и все с ним сопряженные: а а»*" ая Обратно» сопряженные с корнями g (х) гак-и

являются корнями сопряженные с корнями h (х) ними h (х), то коэффиенты полиномов g{x)Mh (х) лежат в (д). Предыдущие зам>™ справедливыдля всех циклических кодо1 Любой о-ичный ЧХ-код с блоковой длиной п над GF (q) може быть определен как 1иклический код, корнями порождающего многс члена которого явл/«« ? « « и сопряженные с нил™ Этот код исправляеткрайней мере d/2 ошибок (см. гл. 10) и mi мальное расстояние эмминга такого кода равно но меньшей мере Поэтому d называе конструктивным расстоянием кода (г-БЧХ-границей). . tttvi

Первым результа<°** " " информационных символов в БЧХ коде является следУщ

12.12, Лемма. Пусть I (q, п, d) - число информацион\ волов в q-ичном БЧХ-ко5е с блоковой длиной п и конструц расстоянием d. Определим L J J уравнениями

i = LiJmodn, 0<LfJ<n -1-

ых сим-Ьгивным

Тогда I{q, п, d) -число таких чисел i, что 0<;i<;n -1и1.й . < п + 1 - d для всех к. iq J<

Доказательство. 1/п и Г il d для

тогда и только тогда, когда Оп - уп - 1 и L(n п - d для всех к. Положим i п - j.

всех к

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

.fOB

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

Для обозначения последовательностей будем использова. питые буквы. Символ {Q - 1) обозначает носледовате.; состоящую из единственной буквы {q - 1). До тех нор, пока i* оговорено противное, допускаются как конечные, так и бескк Последовательности. печные

12.11. Лемма. Пусть I (q, п, d) - число информациот волов q-ичного БЧХ-ко9а с блоковой длиной п и конструктивг стоянием d. Определим ГП уравнениями ым рас-

i = Г il mod п, 1 < Г i"I < и.

Тогда l(q, п, d) -число таких чисел j, что 1 / ге и Г; ь-, , для всех к. Ч \

Доказательство. Для БЧХ-кода а является порождающего многочлена тогда и только тогда, когда сук Р** число к{}) такое, что Г}! <d. чествует

Наоборот, а-корень проверочного многочлена для Б5„ тогда и только тогда, когда Г У? "1 > d для всех к. щ -кода

Лемма 12.11 позволяет определить число информационна ций БЧХ-кода, не производя специальных вычислений в nojij , Г или его расширениях. Надо только вычислить некоторые тих сов вычетов mod п. Однако практически такое вычисленц? клас-трудоемко, особенно, когда п ш d велики. очень

Для получения более обозримых результатов при бодч и d эту лемму удобно переформулировать в следующем вид™

Назовем X субпоследовательностъю для У, если X = ХХ . . . .Хп конечна и = У, = Уа, . . ., Х-х = Уа 1, но

Xh < А- Последовательность У имеет У субпоследовательностей длины 1, У2 субпоследовательностей длины 2, . . ., Уд субпоследо-вательностей длины к. Если последовательность У имеет только конечное число ненулевых букв, то можно определить наибольшую субпоследовательность для У. Если У - последняя ненулевая буква последовательности У = УУд..., то У1У2 . . . Уа-i (Уй - 1) - наибольшая субпоследовательность для У. Если последовательность У содержит бесконечно много ненулевых букв, то У имеет бесконечно много субпоследовательностей. Каждая из них меньше У, но ни одна не является наибольшей.

Аналогично, У называется суперпоследовательностью для X, если У = У,У2 . . . Уь где У = Z, У2 = Z2, . . ., Уа 1 = Х., но Уд; > Хд. Если X = ХХ . . . Xk тз. Xk ф {Q - i), то наименьшей суперпоследовательностью для X является У = У1У2 . . . Ул, где Yi = Xi для i = 1, 2, . . ., А; - 1 и Уа = Zfc + 1. Ясно, что наименьшая суперпоследовательность лежит среди наиболее длин-нт.тх суперпоследовательностей, а наибольшая субпоследовательность - среди наиболее длинных субпоследовательностей.

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

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

п=(?"-1, n+\-d S Uiq-\ OUiq,

i = i

и = ии . . Ujn uY - некоторая q-ичная последовательность, то

I(q,n,d) = J (q, и . У, т).

Доказательство. Лемма 12.23 сводится к лемме 12.12 с помощью следующего соответствия. Согласно условию, последовательности и соответствует число п -\- i - d. Другой д-ичной последовательности TF = TFiH2 • • • Wm длины т можно сопоставить чис-

ло ц; = 2 ту.д"-». Тогда последовательности WWg . . . WmW,

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

число

S PFg+i- + Wi = qw- {q"- 1) PFi,

Пусть F = F1F2F3 . . .- некоторая д-ичная последовательност! О < F < g - 1. Обозначим через F = VyVV . . . дополнение к где Vi = {q - \) - Vi для всех i. Если W = TF1TF2 • Wk - коне») пая д-ичная последовательность, то под ее циклическими сдвигам понимаются WW . . . WkW, WWi . . . WkW, W, . . . . Ecj. X = XjZg . . . Xj - конечная д-ичная последовательность, то мои но построить сцепление X * V = ХХ, . . . ZFiF2F3 . . . . Сцеплв ние можно строить независимо от того, является ли F конечной ил: бесконечной д-ичной последовательностью. Если при этом F конечна то V * X является циклическим сдвигом X * V.

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

ным сцеплением: X = ХХ . ХХХ ... ... . В частност!

( - 1) означает бесконечную последовательность, всеми буква» которой является число q - 1.

Введем упорядочение: X<Y тогда и только тогда, когда сущ ствует такое /, что Xf = У; для i = 1, 2, . . ., 7 - 1, но Xj<.. Если X <(: У и У <}; X, то одна последовательность - префив другой.

Это упорядочение аналогично числовому упорядочению д-ичг дробей, но имеются и существенные различия. Например, 1/4 = 0,01 < 0,0101 = 5/16, но последовательности 01 и 0101 несра нимы, так как одна является префиксом другой. С другой сторог 0,0111111... = 0,1 = 1/2, но 0111... <1. Примеров, аналога этим, можно избежать, если всюду, где это возможно, принять зап1 в виде конечной дроби. Отсюда немедленно выводится следуюг утверждение:

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

u=Uiq-\ v=Viq-\ U = U,U2U3 ...,VV,V2V3

и пусть (<? -1) не является суффиксом последовательностей U и Тогда

С/ < F =Ф ы < 1, V Ф=:ф {U < V или и - префикс V}.

2 Viq-i 2 г?"»-*

2 f/.r- S 2Uiq--=i=

gm-1

= 1-

T. e. последовательность U является д-ичным представлением числ 1 - {d - l)/n. Это позволяет при больших и и d и фиксированно отношении (d - 1)/2п свести исследование числа / {q, п, d) к изучв

нию / {q, If, тп) как функции от т при фиксированных q ж U.

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

Из определения субпоследовательности для V ясно, что есл q-ичная последовательность W длины т меньше V, то некоторо субпоследовательность для V является префиксом W. Действительна если W <СУ, то суш;ествует номер к, такой, что Wt = Vt для i = 2, . . ., к - 1, но Ил <Fa и последовательность WiW является одновременно префиксом W и субноследовательность для V.

Предположим теперь, что некоторая последовательность W дл1 ны т и все ее циклические сдвиги меньше V. Так как сама послед вательность W меньше V, то некоторый ее префикс является субпс следовательностью для V. Являются ли все возможные субпослед вательности W возможными префиксами W? Вообще говоря, не так как некоторые субноследовательности могут иметь суффикс! которые больше, чем V. Если X *Y является субноследовательн стью для V ж Y больше F, то X * F не может быть префиксом Действительно, если W = X * Y * Z, то одним из циклическ! сдвигов W является последовательность Y * Z * X V.

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

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

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

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

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

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

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

W = Ж<1> . И<2> .... W* * VF<+i> .... W- . W\ lF(i), W(2), . . ., W(-i) - субноследовательности для V; W< . * Wl . И(2) . . . окаймляющая субпоследоеателъностъ.

Окаймляющая субпоследоеателъностъ имеет префикс W\ который является суффиксом для W, и суффикс W-> . W> ..... VF(), который является префиксом для W как сцепление более коротких субпоследователъностей W<i>, W\ . . .,

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

12.35. /((?, V, m) = mVm+ 2 VuJ(q, V,m-k), где Vj = 0, если j

ft=i

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

12.36. Пусть

n = q-i, d==Dtq-\ 0<Д-<д,

D = D1D2 . . .Dm.

-ели

F.(-1)<Z,

наименьшее сцепление длины m <суперпоследовательностей сля V

I(q,n,d)J (5, V, т).

сравнимое но модулю n - (f - 1 с числом qw. Следовательно, cooi ветствующим циклическим сдвигам W отвечают числа Lwj, \jvq \jvq, L"g™~ij. Эти числа исчерпывают все числа <inAri--{ тогда и только тогда, когда W<iU*Y для любого Y. щ

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