б. Пусть при использовании кода из п. а по принятсй последовательности V вычислены компоненты синдрома

Si= v(a) = а+а, 8з=ю(№<)=а, S5-=v(a)=\.

li) Найти Sa, S4 и Sg.

(ii) Найти число ошибок v, если известно, что v 3.

(iii) Найти многочлен локаторов ошибок.

(iv) Найти вектор ошибок.

ЗАМЕЧАНИЯ

Коды БЧХ независимо открыли Хоквингем [1959] и Боуз и Рой-Чоудхури [I960]. Вскоре Горенстейн и Цирлер [1961] установили, что открытые ранее Ридом и Соломоном [1960] коды являются частным случаем недвоичных кодов БЧХ.

Поведение минимального расстояния и скорости кодов БЧХ большой длины исследовалось многими авторами на протяжении большого промежутка времени. Коды БЧХ длины qf - 1 становятся неудовлетворительными, когда эта длина оказывается много больше q. Для умеренных длин кодов так происходит потому, что в случае двоичных кодов на каждую исправляемую ошибку приходится порядка m проверочных символов, а в случае кода с q 2 - порядка 2т. проверочных символов. Асимптотическое поведение таких кодов несколько лучше, хотя все еш,е остается неудовлетворительным. Точное изложение этих вопросов потребовало бы значительных усилий.

Касами и Токура [1969] открыли бесконечный подкласс примитивных кодов БЧХ, для которых граница БЧХ строго меньше истинного минимального расстояния; первым примером такого кода был (127,43)-код БЧХ с d = 29 и d* = 31. Чинь [1970] придумал примеры циклических кодов, которые лучше кодов БЧХ; одним из таких примеров является циклический (63, 28, 15)-код.

Впервые процедура исправления ошибок для двоичных кодов БЧХ была предложена Питерсоном [1960], а для кодов БЧХ с произвольным алфавитом - Горенстейном и Цирлером [1961]. Чень [1964] и Форни [1965] упростили эту процедуру. Итеративный алгоритм нахоадения многочлена локаторов ошибок был предложен Берлекэмпом [1968]. Месси [1969] представил этот алгоритм в виде процедуры построения авторегрессионных фильтров. Бартон [1971 ] показал, как осуществить алгоритм Берлекэмпа-Месси, не используя деления, хотя для вычисления значений ошибок деление все равно необходимо.

Сугияма, Касахара, Хирасава и Намекава [1975] впервые предложили использовать при декодировании алгоритм Евклида. Велч и Шольц [1979] построили использующий разложение в непрерывную дробь декодер, совершенно эквивалентный декодеру, использующему алгоритм Евклида. Другой способ использования алгоритма Евклида при декодировании был предложен Ман-дельбаумом [1977] и будет рассмотрен в § 9.1.

ГЛАВА 8

КОДЫ, ОСНОВАННЫЕ

НА СПЕКТРАЛЬНЫХ МЕТОДАХ

Обработка дискретных сигналов основывается на применении преобразования Фурье. Исследование сигналов с непрерывным временем, принимающих вещественные и комплексные значения, существенно связано с преобразованием Фурье; в случае сигналов с дискретным временем аналогичную роль играет дискретное преобразование Фурье. Для многих значений п существуют также преобразования Фурье на векторном пространстве последовательностей длины п над полем Галуа GF (q). Преобразования Фурье в поле Галуа могут играть важную роль в исследовании и обработке GF (9)-значных сигналов, т. е. кодовых слов. Основываясь на преобразовании Фурье, можно построить теорию кодирования существенно отличным от использовавшегося ранее способом. Циклические коды можно определить как коды, в которых некоторые спектральные компоненты слов равны нулю. Декодирование кодов БЧХ и кодов Рида-Соломона также может быть описано на спектральном языке.

В данной и Б последующих главах коды и алгоритмы изучаются с частотной точки зрения. Пересматривая многие положения с частотной точки зрения, мы можем углубить наше понимание предмета и найти альтернативные методы кодирования и декодирования. Частотный подход мы используем также для введения некоторых дополнительных классов кодов.

8.1. ПРЕОБРАЗОВАНИЯ ФУРЬЕ В ПОЛЕ ГАЛУА

В поле комплексных чисел дискретное преобразование Фурье вектора р = \pi, i == О, iV - 1} с комплексными компонентами определяется как вектор Р = \Ри, k = О, N - 1}, задаваемый равенствами

где / = -1 . Ядро преобразования Фурье ехр (-2я/iV-) равно корню степени N из единицы в поле комплексных чисел. В конечном поле GF (q") элемент а порядка п равен корню степени п из единицы. Проводя аналогию между™ехр (-2njN-) и а, получаем следующее определение.

Определение 8.1.1. Пусть v = \Vi, г = О, n - 1 - вектор над GF (q), где п делит q" - 1 при некотором т, и пусть а - элемент порядка п в поле GF {q). Преобразование Фурье в поле Галуа вектора v определяется как вектор V = Vj, / = О, п - - \ \, задаваемыйравенствами

Vj=Ia4vu / = 0, 1.

Дискретный индекс i естественно назвать временем, а v - временной функцией или сигналом. Аналогично индекс / можно назвать частотой, а V - частотной функцией или спектром.

В качестве длины преобразования Фурье можно выбрать произвольный делитель числа q" - 1, но наиболее важную роль играют примитивные длины п = q" - 1. В последнем случае а является примитивным элементом поля GF (q"). В отличие от поля комплексных чисел в поле Галуа преобразование Фурье существует не для любой длины п, так как не для любого п в поле существует элемент этого порядка. Для многих целей, однако, таких элементов оказывается достаточно. Если т - наименьшее целое, такое, что п делит - 1, то над полем GF {q) существует преобразование Фурье длины п и компоненты этого преобразования лежат в поле GF (q"). К сожалению, для некоторых значений п преобразования, хотя они и существуют, лежат в столь большом расширении поля, что неприемлемы для данного практического применения. te.

В случае дискретного преобразования Фурье преобразование Р вещественнозначной временной функции р является комплексным. Аналогично если в случае преобразования в поле Галуа временная функция v принимает значения в поле GF (q), то ее спектр V лежит в расширении поля GF {q"). В применениях, связанных с контролем ошибок, все связанные с декодированием действия осуществляются на самом деле в большом поле GF (q), однако начинать мы должны с вектора на входе канала, т. е. в малом поле GF (q).

Теорема 8.1.2. Над полем GF (q) характеристики р вектор и его спектр связаны соотношениями

11-1 п-1

Vj = S аhi, Vi = (1/n) D a~Oy.,

(=0 ;=0

где n интерпретируется как число поля, т. е. пр модулю р.