Рис. 8.5. Структура спектра над полем GF (64).

исправляющий три ошибки код БЧХ. Тогда Со, €,, Сд, Сц, С13, Cis, С21, Саз, С27 и Csi являются информационными символами. Сэ и С27 должны равняться или нулю, или элементу порядка 7 (так как С = Сд и С = С„7); эти элементы принадлежат под-полю GF (8). должно равняться или нулю, или элементу порядка 3 (так как Cgj = C„j); эти элементы принадлежат под-полю GF (4). Со должно быть или нулем, или элементом порядка 1; эти элементы образуют подполе GF (2). Все остальные элементы являются произвольными элементами поля GF (64). Для определения этих символов требуется всего 45 битов информации. Таким образом, получается (63,45)-код БЧХ, исправляющий три ошибки.

После выбора компоненты свободной частоты компоненты связанных частот определяются как ее соответствующие степени. Затем полный спектр преобразуется в кодовое слово. Формируемые таким образом 2* кодовых слов являются в точности теми же 2* кодовыми словами, которые получаются кодированием во временной области. Вплоть до момента, пока не понадобится выделение информации, декодеру не приходится заботиться о том, каким способом осуществлялось кодирование. Однако на последнем шаге, когда из исправленного кодового слова извлекается информация, декодеру необходимо знать, как эта информация была закодирована. Если кодирование осуществлялось в частотной области, то информационные символы должны вычисляться в частотной области.

8.4. РАСШИРЕННЫЕ КОДЫ РИДА-СОЛОМОНА

К коду Рида-Соломона в общем случае можно добавить две дополнительные компоненты; мы будем всегда помещать одну из них Б начале, а другую в конце кодового слова. Коды, получаемые путем добавления одной или обеих дополнительных компонент, называются расширенными кодами Рида-Соломона. Каждый из добавленных символов может использоваться и как информационный, и как проверочный, т. е. либо для увеличения скорости передачи, либо для увеличения минимального расстояния кода. Мы используем этот менее конкретный термин - расширенные* коды Рида-Соломона, хотя эти же коды можно построить увеличением числа слов в кодах Рида-Соломона с минимальным расстоянием d* или удлинением кодов Рида-Соломона с минимальным расстоянием d* - 2. В любом случае получится один и тот же расширенный код Рида-Соломона.

Надо определить два новых локатора и соответственно ввести некоторые ноЬые обозначения. Если исходные компоненты нумеруются элементами поля, то для одной новой компоненты можно использовать нулевой элемент поля, так что остается определить еще один дополнительный символ для другой. Обычно используется символ оо 1). Если исходные компоненты нумеруются показателями степени примитивного элемента, то для обозначения нового локатора нельзя использовать нуль и необходимо ввести два новых символа. В качестве этих двух символов мы будем пользоваться знаками - и -f. Таким образом, слово расширенного кода записывается в виде

(С , Со, Ci, С2, Сн з, С-п 2, С+),

и п = д" + 1. Вектор, получающийся исключением символов с и с+, будем называть внутренним. Мы будем изучать расширенные коды с помощью свойств преобразований Фурье внутренних векторов, дополняя их свойствами расширенного векторного пространства. Когда мы будем говорить о спектре кодового слова, то будем иметь в виду спектр внутреннего вектора.

Сначала дадим определение расширенного циклического кода, а затем - в качестве частного случая - определение расширенного кода Рида-Соломона.

Определение 8./. 1, Расширенным циклическим (п, )-кодом над GF (cj) называется линейный код длины п = д" -f 1, каждое

) Для расширения поля вещественны.х чисел общепринятым и удобным соглашением является использование символов +оо и -оо с доопределением на ни.х арифметнчески.х операций. Такое расширение не образует поля. То же самое можно сделать с полем Галуа, добавив символ оо и определив операции равенствами а -- оо = оо, а-оо = оо. Такое множество не является полем.

8.4. РАСШИРЕННЫЕ коды РИДА-СОлОмОНА 265

СЛОВО которого удовлетворяет следующим условиям: спектр (Со, Си Cn-s) кодового слова (с, Cq, с, с„ з, с+) содержит нули в заданном множестве п - k - 2 позиций с индексами /i, /п-й-2. а две оставшиеся спектральные компоненты удовлетворяют равенствам С/ = с , С/ = с+.

Расширенный циклический код в общем случае не является циклическим.

Определение 8.4.2. Расширенным кодом Рида-Соломона называется линейный код длины п = g -j- 1 над GF (q), спектр кодовых слов (с . Со, Ci, с„ 2, с+) которого при любых целых /о И t удовлетворяет следующим условиям:

1) Cj = 0, / = /о -Ь 1, /о + 2/ - 2;

2) С/. = с ;

3) Cj„+2t~l = с+.

Число 2/ -f- 1 называется конструктивным расстоянием расширенного кода Рида-Соломона. Определение содержит ограничения, состоящие в том, что 2t - 2 соответствующих спектральных компонент должны равняться нулю, а компоненты, окаймляющие эти 2t - 2 компонент, должны равняться с и с+ соответственно. Эти две специальные частоты называются граничными частотами.

По сравнению с кодом Рида-Соломона, который получается удалением с и с+ и приравниванием нулю спектральных компонент С/„ и С/„+2/-1, расширенный код Рида-Соломона всегда содержит два дополнительных информационных символа при неизменном минимальном расстоянии. Впоследствии мы выясним, что это означает в частотной области, а сначала приведем основанное на свойствах матрицы Вандермонда доказательство этого факта.

Теорема 8.4.3. Расширенный код Рида-Соломона над GF (q) является (д -f- 1, к)-кодом с минимальным расстоянием 2t ~\- I = = п - k + I = q - k + 2.

Доказательство. Сначала предположим для простоты, что /о = 0. Проверочная матрица кода равна

--11 1 . . . 1 1 О

О к «2 . . . а«-2 с4?-> о