жз (Т2), yl,v/2 -из (Т1). Согласно (Т5), 0 = - 30(yV - 2) - 1) X

X (Л - 4) + 8\Bs, откуда можно найти В.

Рассмотрим теперь 1-удлиненный БЧХ-код со скоростью {5m-r-i)/N, т>17. Согласно БЧХ-границе, =0 для всех i>7. Согласно предыдущему BgN{N-1) {N~2) {N-8)/{8 х 7 х б X i). С другой стороны, этот код является подкодом РМ-кода второго порядка, и поэтому дуальный к нему код есть надкод для 1ода, дуального к РМ-коду второго порядка. Этот дуальный код, согласно теореме 15.329, содержит точно N {N - 1){N-2){N-8)/{8 х 7 х 6x4) кодовых слов веса 8. Поэтому ==Л(Л -1) (Л -2) (Л -8)/(8 X

Х7х6х4). Затем вычисляем А/а) из уравнения (Т5), Л/(5) -из (Т4), Л/о, - из (ТЗ), Л/а,- из (Т2), Л]у/2 - из (Т1). Согласно уравнению (Т6),

О = N{N -2) [150 (N -1){N - 4) {25N + 48)] -

- 8! (125Ж + 240) 58 + ЮШ,

откуда Вю = 0.

Наконец, рассмотрим 1-удлиненный БЧХ-код со скоростью (6т + l)/N, т > 23. Согласно БЧХ-границе, Af = О для i > 9. В силу предыдущих рассмотрений Bq = 0. Следовательно, можно определить Л/о, из уравнения (Т6); Af„-, из (Т5), ....

Для каждого кода этой последовательности вычисляется следующее В}. Благодаря чрезвычайно благоприятному стечению обстоятельств каждое Bj оказывается равным числу слов веса / в коде, дуальном к РМ-коду второго порядка. Тот факт, что для каждого следующего кода величина Bj оказывается ограниченной сверху и снизу дву.мд равными величинами, позволяет продолжать вычисления и определять нумераторы весов последовательности БЧХ-кодов с малыми скоростями. Наши вычисления заканчивались на БЧХ-коде со скоростью {бт + i)IN, т 23, не потому, что мы не хотим дальше искушать судьбу, а потому, что это достаточно однообразное занятие. Конечно, мы не беремся наверняка утверждать, что благоприятные условия, сопутствовавшие нам пять раз, должны выполняться и впредь. Но можно сделать

16.43. Предположение. Если т &v ~ 13, то число с.гов веса 2v в коде, дуальном к 1-удлиненному ВЧХ-коду со скоростью {mi --1)/Л, равно чисгу слов с весом 2v в коде, дуальном к РШ-коду второго порядка.

Из этого предположения вытекает, что для нечетных т нумераторы весов последовательности тех БЧХ-кодов с низкими скоростями, которые являются подкодами РМ-кода второго порядка, могут быть вычислены с использованием только тождеств Плесе. Будучи оптимистом, автор надеется не только на доказательство предположения 16.43, но и на вывод простых точных формул для нумераторов.

Согласно табл. 16.4, число кодовых слов наименьшего ненулевого веса в 1-удлиненном БЧХ-коде со скоростью {vm 1)/2", mhv -13, для нечетных т, очевидно, задается равенством

(N - i) N T-r N - 21-1 li 2»-223-1

где i = 2у - 3. Хотелось бы найти прямое доказательство этой формулы. Хотелось бы также найти характеристики кодовых слов малого веса, аналогичные теореме 15.329.

16.44. т - нечетное; БЧХ - коды с большими скоростями. При фиксированном т только три из 1-удлиненных БЧХ-кодов имеют дуальные коды, содержащиеся в РМ-коде второго порядка,- это БЧХ-коды с исправлением одной, двух и трех ошибок. Если ti, то код, дуальный к 1-удлиненному БЧХ-коду с исправлением t ошибок, не является подкодом РМ-кода второго порядка, так как - корень порождающего многочлена БЧХ-кода, а двоичная запись 111 числа 7 - слово веса 3.

При нечетном т нумераторы весов кодов, дуальных к 1-удлинен-ным БЧХ-кодам с исправлением двух и трех ошибок, могут быть определены но формулам, приведенным в табл. 16.3. Для дуального к коду с исправлением двух ошибок у = 2 и, согласно БЧХ-границе, Bi = В = 0. Уравнение (ТЗ) при этом принимает вид

2 2*(2-2)Л/,г, = 0.

г нечетн.

Так как 2 {2 - 2) Л/,;, О для всех нечетных i, то для этих i 2 (2 - 2) Л/((, = О и Л/(г) = О для всех i > 1. Это позволяет теперь определить Л/а, из уравнения (Т2) и Л,у/2 из уравнения (Т1).

Теперь рассмотрим код, дуальный к 1-удлиненному БЧХ-коду с исправлением трех ошибок. Так как, согласно БЧХ-границе, 2 = 4 = 5g = О, то уравнение (Т4) .можно записать в виде

t нечетн.

Отсюда следует, что Л/(, О для всех i > 3. Затем определим величины Л/(з,, Л/(1, и Ам/2 из уравнений (ТЗ), (Т2) и (Т1). Результаты приведены в табл. 16.5.

Найденное распределение весов для кодов, дуальных к 1-удли-ненны.м БЧХ-кодам с исправление.м двух и трех ошибок, позволяет вычислить распределение весов в 1-удлинепцых БЧХ-кодах с исправлением двух и трех ошибок на основании фор.мулы Мак-Вильямс (16.21). Мы опускаем эти непосредственные, но утомительные выкладки.

Для нечетных т вывод нумераторов весов 1-удлиненных двоичных БЧХ-кодов (являющихся подкодами РМ-кодов порядка 2 или

то уравнение (Т4)

2*(2*-2)(2*-8)Л/,о = 0.

дуальных к ним кодов) значительно упрощается благодаря членам 1)-2 - j 0 3 - 1 соответственно в уравнениях (ТЗ) и (Т4). Аналогичные уравнения для четных т [(Т7) и (Т8)] не содержат этих членов, и это значительно усложняет вычисление нумераторов весов. Здесь решение найдено для очень малого числа случаев, а полученные результаты могут служить лишь основой для дальнейшего изучения кодов. К таким результатам относятся теоремы 16.45 и 16.46. Как и в разд. 4.7, через Ж) {х) будем обозначать минимальный многочлен элемента а.

16.45. Теорема (Казами). Двоичный циклический код с блоковой длиной 2™ - 1 и порождающим многочленом g{x) =

= ilf (1) {х) П Tlf(х) содержит точно а - (2™ - 1) (2"- °- - 2)/3!

кодовых слов веса 3, где н. о. д.- наибольший общий делитель т и всех Ci.

Доказательство. Так как циклический код инвариантен относительно транзитивной циклической группы подстановок, то число кодовых слов веса 3 в! (2" - 1)/3 раз больше числа кодовых слов веса 3, содержащих единицу в позиции с локатором а". Если 1, X и г/ - локаторы трех единиц в кодовом слове веса 3, то х, yGF (2") - GF (2) и

(16.451) x-\-y + i = Q,

(16.452) х2Ч1 + г/2Ч1 + 1 = 0 для всех г.

Подставляя равенство (16.451) в (16.452), получаем, что для всех i

Отсюда

(г/ + 1)"+Ч2/+ = 1.

-b!/4-l-f-i/2+i = l ДЛЯ всех г;

1/2-}-г/= О для всех i;

yGF (20 - GF (2) для всех i;

yGF (2"-°- )-GF (2).

Таким образом, имеется точно 2"* °- - 2 выборов упорядоченных пар элементов (х, у) и (2"" °- 2)/2 способов для неупорядоченных пар.

16.453. Следствие. Код с блоковой длиной N = 2", полученный как i-удлинение кода из теоремы 16.45, содержит точно

кодовых слов всех 4,

Доказательство. Согласно теореме 10.37, 1-удлиненный код инвариантен относительно транзитивной аффинной группы подстановок. Значит, по теореме 10.38 а = AAJN.

16.46. Теорема (Велч [1967J). Уравнение Tr(x2"+i)=0 имеет

точно 22аЬ-14.( 1)Ь+12а6+а-1 pJuil GF(2<).

Доказательство. Пусть щ, щ, Ugab -базис СР(22аь)

над GF{2). Тогда х= 2 Хмь XiGF{2),

2аЬ 2аЬ

i=l 3=1 2аЬ 2аЬ

Тг(х2«+1)=2 XtXjTriuiuf).

i=l 3=1

Последнее равенство дает квадратичную форму от переменных Xj. Согласно теореме Диксона 16.35, существует такой базис щ, и, . . . . . ., Uzab, такое число с, с < аЬ, и такой элемент XGF (2), что

Tr(x2"+l) = Zi+i-f 2Z2J.iX2j,

(16.461) или

(16.462) Tr(x2"+i)=(ZL i-f zL)-b 2 X2i.,X,,.

в первом случае Tr(x2"+i) не зависит от 2а& -2с -1 координат, а во втором -от 2аЬ -2с координат. Для определения с надо найти такое число v, что для всех wGF(2"-)

Тг {W -f vf = Тг («32"+!).

Имеем

Тг [(м; f у)2"+* - и;2"+1] = Тг {w% + v2w + г;2"+1) =

= Тг {w%) -LTr {vw) Тг (i;2"+i) =

= Тг {w%) -f Тг-(г;22) + Тг (i;2"+i) =

= Тг [W2° (г;22" -1- v)] -f- Тг (i;2"+i).

Это равенство не зависит от w тогда и только тогда, когда vGF{2). Если vqGF{2n\0, то (y2«+i)2"-i i 2-+i г

2аЬ , а .

GF{2) и Тг(.2«+1)= 2 {v+f =2& 2 ("+) = 0. Следователь-

»=1 1=1

но, Тг[(и;-Ьу)"+*] = Тг(и;2»-Ц) ддя всех wGF{2>) тогда и только

тогда, когда vGFil""). Так как Tr(a;2+i) не зависит от 2а координат, то 2а = 2аЪ - 2с и Tr(.x2"+i) задается формулой (16.462), а но (16.461).

Согласно равенству (16.354), число Л, способов выбора 2аЪ двоичных чисел Xl, Хг, Агаь, удовлетворяющих уравнению

SX2h-iX2fe = i, c=ab - a, задается равенствами

iVo = 22«b-i + 2«b-i,

J\r 22ab-ba-l 2<*+<-1.

Следовательно, если Х=-0, то уравнение Тг (a+i) = О имеет в GF(22ab) 22<Ь-1 L. 2°+"-1 решений; еси Я=1, то уравнение

О = Тг (:г2+1) = Хгс-Дгс + Хс-1 Ч-Хзс 4- .S 20-12; - 1 + (Хс + 1) X

X (Х2С-1 +1) + S 2с-Д2г имеет в GF{2ь) 22аь 22аь-1 решений.

Чтобы определить, равен ли элемент X нулю или единице, заметим, что число ненулевых решений уравнения Тг (a:2+i) = О должно быть кратно 2" -f 1. Следовательно,

22аь-14- ( 1) 2<ь-1 1 = о mod (2" + 1)

22аь .1. ( i) 2"+ = 2 mod (2 -f 1). Так как 2 = -1, то отсюда получаем

1 f ( 1) ( 1)<+1) = 2 mod {2"-f 1),

(-1) = (-!)«. I

16.47. Четное т; 1-уд линейные БЧХ -коды с малой скоростью. Рассмотрим теперь приведенный в табл. 16.5 1-удлиыепный двоичный БЧХ-код со скоростью (Зт/2 + i)IN. Так как, согласно БЧХ-границе, минимальное рас-

стояние этого кода равно по меньшей мере 2"~ - 2 Afi., = О для всех i > 0. Так как рассматриваемый код содержит РМ-код первого порядка, то дуальный к нему код - подкод кода Хэмминга, и 2 =0. Величины Л/,о) и yljv/2 определяются соответственно из уравнений (Т2) и (Т1) таблицы 16.3 при v = 3/2.

Рассмотрим далее 1-удлиненный двоичный БЧХ-код со скоростью (5т/2 4- )IN. В соответствии с БЧХ-границей, Л/»-, = О

ДЛЯ всех i > 2. Так как наибольший общий делитель чисел т, т/2 и {т/2 - 1) равен 1, то по следствию 16.453 = 0. Величины Afu Лиа) И An/z определяются из уравнений (Т7), (Т2) п (Т1) при v = 5/2.

Распределения весов для двоичных БЧХ-кодов со скоростями (7т/2 -f i)/N, (9т/2 + 1)/Л, . . ., к сожалению, не известны.

16.48. Четное т; 1 - у д л и н е п н ы е БЧХ -код ы, исправляющие две ошибки. Для определения распределения весов в БЧХ-кодах, исправляющих две ошибки, выберем относительно обходный путь. Сначала рассмотрим полный алгоритлг декодирования для этих кодов. Это позволит вычислить число слов веса 3 в смежных классах веса 2 и 3. Отсюда легко найти число кодовых слов веса 5 в (циклическом) БЧХ-коде с блоковой длиной п = 2" - 1. Оказывается, этой информации уже достаточно для вычисления нумератора весов по формулам таблицы 16.3. Казами дал более прямой метод вычисления нумератора весов БЧХ-кодов с исправлением двух ошибок. Однако полный алгоритм декодирования и нумераторы для сменгпого класса представляют существенный самостоятельный интерес, и поэтому мы предпочли более обходный путь.

Если произошло не более двух ошибок, то, согласно разд. 1.4 (или алгоритму 7.4), многочлен локаторов ошибок для БЧХ-кода, исправляющего две ошибки, задается равенством

о (2) =

l+lZ, I+S1Z-

если ошибок нет, если произошла 1 ошибка,

если произошли 2 ошибки.

Здесь Ai = 5з + SS = 8 + SI Если Тг {AJSD О, то по теореме 6.695 пе все корни 0(2) лежат в поле GF {п -f 1). В этом случае декодер фиксирует отказ от декодирования, обнаруживая тем самым существование не менее трех ошибок. Если предположить, что произошли три ошибки с локаторами Х, Х и Xg, то, согласно проверочным уравнениям для S и S., получим

Xi--Xz + XsSi,

xi+xu-xis,.

Полагая w = X3-l.Si и исключая Х3, приходим к равенствам

Xl f Х2 = w, XI + = 3 + SI + Sliv + Sw + w\

Возведем первое уравнение в куб, прибавим его ко второму и раз-делим сумму на первое. Тогда получим