Сделаем замену переменных, полагая х - SyZ. Тогда новый многочлен, который мы также обозначим через Л, будет иметь вид

Л(г) = 2 + г + (1+5Г5з).

Этот многочлен имеет корни в поле GF(2") тогда и только тогда, когда tr (l + SrSs) равен нулю. В четных расширениях GF (4) всегда tr (1) = О, и это условие преобразуется так:

tr(SrS3)==0.

Далее, в полях характеристики 2, согласно теореме 8.2.3, ровно половина элементов имеет равный нулю след. При каждом значении элемент Sg может принимать только 2"" значений, которые образуют в GF (2") подпространство размерности т - 1. Один бит в Sg «не используется». На первый взгляд может показаться, что на частоте Cg кодового слова можно ввести дополнительный бит информации. Это невозможно, так как неиспользуемый бит элемента Ss зависит от Si. Но коды Препараты позволяют лучше распорядиться этим обстоятельством: если спектр лежит в расширении поля GF (4), то можно переупорядочить другие информационные биты так, чтобы ввести дополнительный информационный бит.

(2"-1, 2"*-2т, 5)-код Препараты над GF (2) существует для каждого четного т, большего 2. По сравнению с соответствующим кодом БЧХ, исправляющим двеошибки, код Препараты всегда содержит один дополнительный информационный бит. Мы рассмотрим только (15, 8, 5)-код Препараты.

Определение 8.9.1. Двоичный (15,8)-код Препараты определяется) как множество двоичных слов длины 15, спектр которых удовлетворяет следующим ограничениям: Ci = О, Cg = Л, Cs = = В, где либо

1) Л 6 {1, a сс*. а«, а2} и В = О,

либо

2) В е {1, a а"} и Л = О,

и, кроме того, выполняются условия сопряженности.

Отметим, что, согласно условиям сопряженности, Ct - Cs, так что Cg может быть только элементом поля GF (4). Так как Со представляет собой произвольный элемент поля GF (2), а C произвольный элемент поля GF (16), то Со и С, вместе содержат

) При таком определении нулевое слово не является кодовым. В других определениях используется такой сдвиг кода, при котором нулевое слово вклю чается Б КО.Ц.

8.9. КОДЫ ПРЕПАРАТЫ 281

ПЯТЬ битов информации. Остальные три бита описываются восемью выборами А и В, так что код является (15, 8)-кодом.

Покажем теперь, как исправляются двойные ошибки, и тем самым докажем, что минимальное расстояние этого кода равно по меньшей мере 5. Пусть vj, ] ~ О, п- 1, представляют собой спектральные компоненты принятого слова. Определим синдромы

5, = 1 = I/i,

$2 == = 12.

= Es+A 1/3.

S, = E,+B= v,.

Выбор A n В приемнику не известен, но ограничен условиями определения 8.9.1. Далее,

5з = X? -I-Xi +Л, SsX\+xl+B.

Сначала разрешим эти уравнения относительно А и В; затем вычитание А из S3 сведет задачу к декодированию исправляющего две ошибки кода БЧХ. Простые вычисления дают

S? + (Ss -f Л) = X1X2S,,

(S3 + Af + Si (Ss +В) = X.XzSt.

Исключая X1X2, получаем квадратное уравнение

А + SU + (S?S3 + Si + Sf + S.Ss + S,B) = 0.

Ономожет быть разрешено относительно А и В следующим образом. Сначала положим В = О и решим получающееся при этом квадратное уравнение относительно А. Затем положим Л = О и решим получающееся линейное уравнение относительно В. Это даст нам три решения для пары (Л, В). Из доказательства приведенной ниже теоремы следует, что только одно из них удовлетворяет ограничениям определения 8.9.1.

Теорема 8.9.2. Минимальное расстояние (15, 8)-кода Препараты равно 5.

Доказательство. Докажем, что минимальное расстояние кода равно по меньшей мере пяти, построив процедуру декодирования, исправляющую две ошибки. Для этого достаточно дать правило нахождения по принятому слову величин Л и В, так как после

этого задача сводится к декодированию исправляющего две ошибки кода БЧХ.

Предположим, что произошло не более двух ошибок. Если Si = О, то ошибок не произошло. Мы предполагаем, что Si было вычислено и оказалось отличным от нуля.

Сначала положим 5 = О и найдем корни квадратного относительно А уравнения

Л + S\A -f (SfSs -Ь Si -Ь S? + S,S,) = 0.

Удовлетворяющие нашим ограничениям возможные решения для Л исчерпываются ненулевыми кубами. Затем положим Л = 0 и найдем решение линейного относительно В уравнения

* (S?S3 -Ь S\ + S\ + S.Ss) -h S,5 = 0.

Шаг I. Сначала покажем, что рассматриваемое квадратное уравнение не может иметь двух решений, которые оба являются ненулевыми кубами. Если л1 и Лг - корни данного квадратного уравнения, то л1 -f Лг = S?, так что сумма двух корней также является ненулевым кубом. Необходимо только доказать, что в поле GF (16) сумма двух ненулевых кубов не может быть равна ненулевому кубу. Выпишем множество ненулевых кубов

i/g = {1, a аб, а\ а}.

Тогда прямое вычисление всех возможных сумм дает множество

3 + 3 = {о, а, а\ а\ а\ а\ а\ а", а", а"},

которое не содержит ненулевых кубов. Таким образом, в поле GF (16) сумма двух ненулевых кубов не может быть ненулевым кубом, и поэтому л1 и Лг не могут одновременно удовлетворять ограничениям определения 8.9.1.

Шаг 2. Предположим теперь, что (Л, 0)!и (О, В) -два решения исходного уравнения.Покажем,что оба они не могут удовлетворять накладываемым ограничениям. Разность двух уравнений дает

Л + SM + SiB = 0. Пусть Л = SM. Тогда

(АУ + А + STB = 0.

Но как Si, так и В являются ненулевыми элементами поля GF (4). Следовательно, элемент Л должен удовлетворять одному из следующих уравнений:

{АГ + Л -f 1 = О, • {Ау + Л = О, .

:{Af -f Л + а" = 0.