Ответ согласуется с примером 12.42, хотя рекур™ различив Это иллюстрирует тот факт, что хотя теорема 12.38 рисывает одж удовлетворительный метод отыскания F, но как показывают пеке торые примеры, результирующая последовательное* не опреде ляется однозначно. Простейшее рекуррентное правило отталкиваете* от возможно кратчайшей последовательности, что сооЧетствует наи- большей V или наименьшей последовательности D. fanan носледо вательность в общем случае может быть найдена нут# максимальщ возможного уменьшения D.

12.44. Пример. Пусть ге = 2" - 1, d = Ail Тогда D = 00110011011. Можно было бы взять D = 110011001*0 = X и дей ствовать согласно рекуррентному правилу. РассмоФ™, однако d = Ш ш D = 00110011010. Так как эта последовательность имеет циклический сдвиг, меньший чем она сама, то ки меняется! Но так как последовательности D = 11001100101, 1 = 110011001 не проще предыдущих, то продолжим процесс даньше. Отмет! штрихом начальную точку наименьшего циклического сдвига.

0011001101О 00110011001 00110011ООО ООН0010111 ООН0010110

ООН0010000 ООН0001111

001г0000000 00101111111

Так как последовательность 00101111111 не имеет циклических сдвигов, меньших чем она сама, то она определяет конструктивное расстояние, которое совпадает с расстоянием Боуза для отличного от исходного БЧХ-кода. Поэтому вместо первоначальных мы должны использовать D = 00110000000, D = 11001111111, X = = 1100, V =1101. Эта последовательность приведена в примере 12.37. Здесь / (2, 2"-1, 411) = 485. Такая же последовательность V получается, если начинать с D = 00110011000 или любой последовательности D, такой, что

00110000000 < л < 00110011000.

12.45. Пример. Пусть д = 2, n = 2-i, = 001010010100111, 7=110101101011001, 7 = 001010010100110 5. 1 = 1101011010110001111..., X = 110101101011000.

Хотя использованный сейчас грубый метод прямого вычисления приводит к правильному ответу, более легким оказывается окольный путь. Рассмотрим вместо D = 001010010100111 последовательность £1 = 001010010100101, X = 11010, V = 11011, V = 00100. Это приводит к множеству кодов (рассмотренных выше) со значительно более простой рекурсией. Код cD = 001010010100111 имеет на пять информационных позиций меньше, чем код с D = 001010010100101, в соответствии с пятью различными циклическими сдвигами последовательности 001010010100101.

*12.5. Определение числа информационных символов в непримитивных БЧХ-кодах

Хотя число информационных символов произвольного БЧХ-кода всегда может быть найдено в соответствии с леммой 12.12, во многих случаях счет удается значительно упростить путем сведения к задаче перечисления д-ичных последовательностей. Для примитивных БЧХ-кодов такая редукция дается теоремой 12.23 и позволяет применять все теоремы разд. 12.3. Аналогичный результат для непримитивных БЧХ-кодов дает теорема 12.51.

12.51. Теорема. Пусть заданы числа q,nvid,m - мультипликативный порядок q mod п, j = {q - i)/n, D - q-ичная последовательность, координаты которой совпадают с коэффициентами q-ичного представления числа jd = Dtq, V - последовательность,

определенная последовательностью D в соответствии с теоремой 12.38.

Тогда число I (q, п, d) равно числу q-ичных последовательностей W длины т, одновременно удовлетворяющих двум условиям:

1) W - сцепление субпоследовательностей для V, включая {воо-можно, пустую) окаймляющую субпоследовательность;

2) число W = Wtq делится на j.

Доказательство. Согласно лемме 12.12, число / {q, п, d) равно числу целых i, таких, что О i п - 1 и LiqJ <С п -\- I - d для всех к. Умножив это неравенство на /, получим, что / {q, п, d)

о числу целых чисел w, кратных j и таких, что О w j {п - I) jvqJ <ii {п -\- i - d) для всех к, где число LwJ теперь опре-ется условиями: \ wJ = wq mod re и О LwqJ jn - 1. как между / (ге - 1) и jn или между / (ге + 1 - d) и / (ге - d) чисел, кратных /, то последние два условия эквивалентны нера-твам 0<ц;<7ге - 1=(?" - 2 и LwqJ < /ге + 1 - jd = - jd. Так как д-ичное представление числа LwJ есть цикли-кий сдвиг д-ичного представления числа w, то теорема 12.51 выте-из теорем 12.38, 12.33 и 12.34. щ

\ля пересчета д-ичных последовательностей длины т, удовлетво-IX теореме 12.51, полезно ввести следующие обозначения:

J.52. Определение. Обозначим через КС) (q, V, т, j) число шх последовательностей длины т, являющихся сцеплением суб-дователъностей для V, которым соответствуют числа, сравни-г mod /.

усть Vh (/) - число субпоследовательностей для V, сравнимых mod /.

ри фиксированных д, / и F теорема 12.53 дает рекурсивное пра-вычисления К) (д, V, т, }) для всех значений г при соответ-ющих значениях т. Условимся, что все арифметические опера-над верхним индексом чисел К выполняются по модулю j. 112.53. Теорема

! (д, V, т, }) ==

О, если гег < О, •

0, если т = 0 и гфО,

1, если гег = 0 и г = 0,

K4Q,V,fn-f(JWk"4}) в остальных

I h

случаях.

оказательство. При делении на / пустая последова-ость длины О дает остаток 0. При m > О имеется Fft* {}) спо-выбора такой последней субпоследовательности в сцеплении, длина равна к, а остаток при делении на / равен х. Предшест-й ей {т - й;)-мерный вектор является сцеплением субпосле-;тельностей для V. Если это сцепление длины т - к имеет оста-, то сцепление длины т имеет остаток qH -\- х, который равен г а и только тогда, когда х = г - (jl. щ

i2.54. Теорема. В предположениях теорем 12.51 и 12.53 обозначениях определения 12.52 имеет место равенство

I{q, ге, = S I

\кЮ> (д, F,m-fc,/)F(- (/).-

Доказательство. Так как / д™ - 1, то делимость q-ш ной последовательности длины пг на / не зависит от фазы ее окайл ляющей (или конечной) субпоследовательности. Поэтому теоре ма 12.54 вытекает из теоремы 12.53 и того факта, что каждая данна окаймляющая (или конечная) субпоследовательность длины к имее к возможных фаз. щ

При малых i теоремы 12.51, 12.53 и 12.54 и определение 12.5 дают простой метод вычисления / {q, (g"* - 1) , d). Для больших такое вычисление требует уже больших усилий.

12.55. Пример. Сколько информационных символов имее БЧХ-код с блоковой длиной 1365 и конструктивным расстоянием 26

Решение. п = 1365; /тг = 12; у = 3; 3 X 260 = OOllOOOOlK (в двоичной записи), так что D = 001100001100, D = 110011110011 X = 1100, V = 1101. Субпоследовательностями для V являются 10, 1100, так что Vf (3) = F" (3) = (3) = 1; в остальных слз

чаях Fft (3) = 0. Выпишем Ff" (3) в виде таблиц:

Теперь можно вычислить К> (2, 1101, т, 3):

Согласно теореме 12.54, / (2, 1365, 260)= 100 -f 2 X 56 -f 4 X 18 = 284.

Для определения расстояния Боуза для этого кода найдем на меньшее сцепление длины т суперпоследовательностей для F, ра

делим соответствующее число на / и произведем округление. В данном примере F = 0010. Наименьшим сцеплением длины 12 ее суперпоследовательностей является последовательность 001100110011, равная 3 X 273, так что расстояние Боуза равно 273.

12.6. Асимптотические результаты

Определим нумератор

J{q,U;z)= S J{q, U,m)z,

И сопоставим заданной последовательности F, превосходящей все свои собственные суффиксы, ряд

F(z) = SFftz\

Тогда

zV {z) = kVuz\ Рекуррентное соотношение

/{q, F, т) =mVm+ У, VJ{q, V,m-k)

ft = 1

приводит к уравнению

/ {q, V; z) = zV (z) + V{z)J {q, V; z),

откуда

(12.61)

Пусть pi, p2, . . .- (не обязательно различные) комплексные корни многочлена 1 - F (z). Тогда

1-F(z) = n(l-Ptz),

-F(z)=-Sp, П(1-Р.-2),

i ]ф1

l-F(z) Следовательно,

» i m=i , m=l i

m=l i