Элементы yXjw и yX/w удовлетворяют уравнению

У + У-

Это уравнение разрешимо в поле тогда и только тогда, когда

= Тг()+Тг()Чт,()=Тг().

Полагая u = /S.i/w, можно начать декодирование с произвольного элемента и, след которого равен 0. Выделив кубический кореш W - (Ai/u), можно определить локатор ошибки по формуле

u{z)-ll + {Si + w)z][l+wz+[si + SiW + -)z .

Для того чтобы выделить кубический корень из А/и при прс извольном выборе А, надо подобрать такие три различных значенш и, что Тг {щ) = Тг Ы = Тг (из) = О и = , uf = д, тр g, д g GF (2) - CF (2). Выбрав эти три элемента щ, щ и и, можно внести их в декодер, который декодирует согласно следующему алгс ритму.

16.481. Полный алгоритм декодировани для двоичных БЧХ-кодов с исправление двух ошибок. Вычисляем А = -}- iSiSj.

Если Ai = 5i = О, то полагаем а (z) = 1.

Если SiO и Тг (Ai/Sl) = О, то полагаем ст (z) = 1 -Ь Sz + iJSi) z\

Если 6i = 0 и AiO или Тг (AjZ/SJ) О, то полагаем w--= (Al/u,)l) и

o{z) = \i + {S, + w)z\[].wz+[sl + S,w) z .

Число возможных выборов и, U2 и Us зависит от числа ненулевь кубов и некубов с нулевым следом в поле GF (2""). Согласно тес реме Велча 16.46, число ненулевых кубов с нулевым следом равяй

га-1±2Уии:. 6

) Для определения w декодер сначала пытается выделить кубически корень из Ai/ui с помощью методов разд. 11.1. Если Ащ имеет в GF (2"») тр кубических корня, то любой из них может быть выбран в качестве w. Есл в GF (2"») нет кубических корней из AJui, то декодер пытается выделить куби ческий корень из Ai/u2 и т. д.

В случае нечетного т этой проблемы не возникает: любой ненулевой элв мент поля с нулевым следом может быть выбран в качестве щ. В элементах Г и Из нет надобности, так как Aj/it, всегда имеет единственный кубический корен в GF (2т).

n+i + 2 Vre + 1 6

ЧИСЛО некубов с нулевым следом равно

д -1 =F"i/» + l 3

ЧИСЛО некубов с единичным следом равно

Здесь ± Yn 4- 1 = - (-2)™. В любом случае недоразумений не произойдет, так как неправильный выбор знака приведет к элементу, не являющемуся целым числом. Используя этот результат, можно дать классификацию смежных классов двоичного БЧХ-кода длины 2" - 1, исправляющего две ошибки, как показано в табл. 16.6.

Например, рассмотрим случай, когда О и Aj - некуб,

такой, что Тг {AJSl) = 1. Всего имеется п способов выбора и столько способов выбора Ai, сколько существует способов выбора элемента A/Sl - некуба с единичным следом. Как мы видели, в поле GF (п -f 1) содержится (тг -}- 1 ± Y + 1)/3 таких элементов. Эта величина отмечена в столбце «Число смежных классов в типе». Вес смежных классов этого типа, очевидно, равен 3.

Сколькими способами смежный класс может быть декодирован в вектор шума веса 3? Сначала надо выбрать элемент и с нулевым следом, для которого в поле существует кубический корень из А/и. Всего в GF {2) имеется {{п - 1)+ (/тг4-1)/3 некубов с нулевым следом. Так как квадрат недопустимого элемента и также недопустим и наоборот, то точно половина этих (тг - 1 + Yn + 1)/3 некубов с нулевым весом недопустима в качестве элемента и. Следовательно, и может быть выбрано (тг - 1 + Yn + l)/6 различными способами. Хотя имеется три выбора w в качестве кубического корня из Ai/u, каждому кубическому многочлену ошибки также соответствуют три различных выбора и> (не обязательно при одном и том же выборе и). Таким образом, происходит сокращение этих двух троек и число слов веса 3 в ка>кдом смежном классе рассматриваемого типа равно (тг - 1 + Yh + 1)/6. Эта величина внесена в столбец «Кратность элементов минимального веса в смежном классе» таблицы 16.6. Остальные члены этой таблицы могут быть получены аналогичным образом.

Заметим, что ни один смежный класс не имеет веса >3. Этот факт впервые был отмечен Горенстейном, Питерсоном и Цирлером [1960], которые доказали, что при четном т двоичный БЧХ-код длины 2" - 1, исправляющий две ошибки, является квазисовершенным

ЧИСЛО ненулевых кубов с единичным следом равно

(см. разд. 13.2). Из алгоритма 16.481 видно, что при нечетном т двоичный БЧХ-код с блоковой длиной 2" - 1 также квазисовер-пхенен.

Остается еще несколько вопросов. Сколько слов веса 3 принадлежат смежным классам веса 3? Ответ дает следующая формула:

т I-6-)+т \--6-

, + 1 ± Уге+1\ /ге -1 Уге + Ц

+"1 3 )\ 6

, /ге-1-l =р2Уге-1-1\ /ге-1±2Уге+1\ ге rfi-Ъ

Общее число всех слов веса 3 во всех смежных классах равно ( 3 ) =

= п{п - i) {п - 2)1%. Тогда число слов веса 3, принадлежащих смежным классам веса 2, равно га (га - 1) (тг - 2)/6 - п {п - 5)/12 =

= тг (тг - 3)/12. Для каждого кодового слова веса 5 имеется ( 3 ) =

= 10 векторов ошибок в смежных классах веса 2, так что код должен содержать тг (тг - 3)/5! кодовых слов веса 5.

Так как БЧХ-код с исправлением двух ошибок содержит = - jifi - 3)2/5! кодовых слов веса 5, то, согласно теореме 10.38, 1-удлиненный БЧХ-код содержит 5в = (тг -f- 1) тг (га - 3)V6! = = TV(/V-.1) (/V - 4)2/6! кодовых слов веса 6. Уравнение (Т8) из табл. 16.3 соответственно принимает вид

2 22-1) (2*-4) Л, (0 = 0,

откуда следует, что Af <;> = О для всех i > 2. Величины Af ,2), Af (о, и 4jv/2 определяются затем из (Т7), (Т2) и (Т1). Соответствующие результаты приведены в табл. 16.5.

16.49. Четное т; 1-удлиненные БЧХ -коды с исправлением трех ошибок. В заключение раздела рассмотрим код, дуальный к 1-удлиненному БЧХ-коду с исправлением трех ошибок при v = Ъ. Согласно БЧХ-границе, = = = 5в = 0. В силу (Т8)

24(24 1)(2*-4)Л/<4,+2<(2«-1)(2«-4)Л/<б,+ ... =3/V(/V-l)(/V-4), или

л . 8/4 . jv(jv-i)(jv 4) Ajw -г04Л/(в) -h------64 X 15

Казами [1968] показал, что величины А fa) должны делиться на N {N - 1)/16, и, следовательно, если 84 < (Ж - 4)/60, то = О для всех i > 4. Это условие выполняется для всех N 2. В этих случаях величины Л/(4,, Л/,2„ Лу и А/ можно определить из

уравнений (Т8), (Т7), (Т2) и (Т1). Согласно (Т9), В = N {N - i) X X (/V - 4) {N -\- QN + 68)/8!. Это уравнение доказано для т 12, и представляется очень правдоподобным, что оно справедливо для всех т. Гипотетическая формула для В эквивалентна предположению о том, что А fa) = О для всех i > 4. Доказательство любой из этих гипотез дает доказательство гипотетической формулы для нумератора весов кода, дуального к 1-удлиненному БЧХ-коду с исправлением трех ошибок. Нам представляется, что эту формулу для можно доказать с помощью нумераторов смежных классов для БЧХ-кода с исправлением трех ошибок аналогично тому, как это сделано в разд. 16.48. Однако такое вычисление будет достаточно запутанным, и возможно, что существует более непосредственное доказательство.

*16.5. Нумераторы весов для кодов Рида - Соломона

Согласно теореме 13.35, коды Рида - Соломона достигают общей границы d п -\- \ - к. Этот факт позволяет вычислить нумераторы весов кодов Рида - Соломона на основании теоремы 16.51, доказанной независимо друг от друга тремя группами исследователей: Ассмусом, Мэттсоном и Турином [1965]; Форни [1966[; Казами, Лином и Питерсоном [1967] (часть доказательства принадлежит Глизону и Кохленбергу).

16.51. Теорема. Если минимальное расстояние по Хэммингу кода с блоковой длиной п и размерностью к над GF (q) равно d = = тг -[- 1 - к, то для и> d число J\.io кодовых слов веса w (в метрике Хэмминга) задается формулой

S (-1)(;)(?----1)=

= (:)(-1)Е(-1гГ7>

Доказательство. Пусть В, S ж Т - подмножества мно-I жестка тг позиций кода соответственно с мощностями \ В \ , \ S \ ,и I Г I и дополнениями В, S я Т. Пусть - число кодовых слов, I которые имеют нули в позициях из В я ненулевые координаты в нози-циях из в. Полагая, что непулевые символы нулевого слова лежат в пустом множестве 0, получим, что М0 = 1. Тогда число кодовых слов, нулевые символы которых расположены в координатах мно-1жества S, равно

1(16.52) Mn-f{S),

(16.53)

, если I 6" <d - 1, если о( < I 5 I.

Равенство (16.53) вытекает из того факта, что, как показано в разд. 13.3, существует единственное кодовое слово, символы которого в фиксированном множестве из к позиций принимают любые наперед заданные значения. Для обращения равенства (16.52) умножим (16.52) на некоторую функцию 1 (S, Т) и просуммируем по S Т. Получим

(16.54) 2 S fl-. Т)Мп-= S v.{S, T)f{S).

Если (16.55)

Д, S,

sczT

S li{S, T) = f- если R = T, 10,

RCS(ZT

если RczT, TO уравнение (16.54) можно записать в виде

(16.56)

Мг= 2 [i{S,T)f{S).

Таким образом, вопрос о разрешимости уравнения (16.52) сводится к нахождению функции [i {S, Т), удовлетворяющей (16.56). Разумный выбор дает формула:

(16.57) }г (5, Г) = (-1)-.

Для проверки того, что эта функция удовлетворяет (16.55), заметим, . j выборов S, таких, что R S Т ц I 5 I = I В I -- /. Значит, если В < Г , то

2 (-l)lHSlJ2"(7)(-l)-""-=(l-l)-"=0.

S, 3=0

Следовательно, функция (16.57) удовлетворяет (16.55) и решение уравнения (16.52) задается формулой (16.56).

Более простое решение, однако, получается, если Мд заменить функцией Mr, которая определяется равенствами М% = Mr, если R ф 0 ж М.*0 = 0. При этом уравнение (16.52) приводится к виду

2 M*H=U"+""" еслий<5, Rs I О, В остальных случаях.

Согласно формуле (16.56),

м*т== S (-1)-«(?"+--1)-

S, dt IS

Полагая 1 = 151, запишем это равенство в виде

м*г=2(-1)"-(Г)(""-1)-

Подстановка / = 7 - i дает

(16.58) М*, = 2 (- 1) ( ) (З -1)•

Если шфО, то

\T\Lw

Так как существует j способов выбора Т, то первая часть формулы 16.51 вытекает непосредственно из равенства (16.58). Для получения второй части рассмотрим равенства

= 2 (-1)4(7) +(/-i)]"""-!)

(:) -

= s(-i)47)(""""-i+

w-d w-o

= S (-1) (7) (??"---i)-2 (7) (3"---i)=

= 2(-ir (7)(-i)""*-

Читатель может заметить некоторую аналогию между функцией [I {S, Т) - решением уравнения (16.55), и функцией \ji (А) из теоремы 3.41. Рота [1964] показал, что обе эти функции являются част ным случаем функции Мёбиуса, которая может быть определена на произвольном частично упорядоченном множестве.