8.3. СПЕКТРАЛЬНОЕ ОПИСАНИЕ ЦИКЛИЧЕСКИХ КОДОВ

Каждое слово с циклического кода задается многочленом степени В несистематическом виде оно может быть записано как с где информационный многочлен

степени Во временной области это дает (циклическую) свертку:

Следовательно, в частотной области операция кодирования может быть записана в виде произведения

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

Хотя каждое слово циклического кода является вектором над спектр кодового слова является вектором над Следовательно, циклический код может быть определен как множество -значных обратных преобразований Фурье множества всех спектральных векторов, компоненты которых в заданном множестве частот равны нулю. Нельзя выбирать произвольный спектральный вектор, у которого стоят нули в заданном множестве частот; обратные преобразования некоторых из таких векторов могут иметь компоненты, не принадлежащие полю Для того чтобы кодовое слово принадлежало полю выбирать нужно только спектр, который удовлетворяет условиям сопряженности, приведенным в теореме 8.2.1.

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

Доказательство границы БЧХ в частотной области представляется простым и интуитивно очевидным. Следует, пожалуй, привести это второе доказательство, чтобы выявить различие в подходах и методах.

Теорема 8.3.1 (граница Пусть делит при некотором Единственным вектором из веса не более имеющим последовательных нулевых компонент спектра, является нулевой вектор.

Доказательство. Обозначим через индексы ненулевых компонент вектора Определим в частотной области вектор, обратное преобразование Фурье которого содержит нулевые компоненты для всех частот для которых Такой вектор может быть выбран многими способами. Один из возможных выборов основывается на многочлене локаторов

Вектор представляет собой частотный спектр, разумное определение которого сводится к тому, что его обратное преобразование равно нулю для каждого момента времени для которого Выписанное выше произведение во временной области равно нулю для ; следовательно, в частотной области циклическая свертка равна нулю:

Так как при то свертка может быть записана виде

Но на блоке длины вектор С равен нулю. Следовательно, но рекурсии вектор С всюду равен нулю, так что и с должен быть нулевым вектором.

Если (или делит то код БЧХ является кодом Рида-Соломона; кодовое слово и его спектр лежат в одном и том же поле. Используя для вычисления спектральных компонент информационные символы, можно осуществлять кодирование непосредственно в частотной области. Каждый спектр, у которого 21 последовательных компонент равны нулю, является кодовым словом. Кодирование осуществляется следующим образом. Какие-либо последовательных частот (например, первые 21) выбираются для обеспечения необходимого ограничения: символы в этих частотах полагаются равными нулю. Остальные координат спектра заполняются информационными символами из Тогда обратное преобразование Фурье дает (несистематическое) кодовое слово, как показано на рис. 8.2. Поскольку имеется частот, в которых записываются информационные символы, то получается -код Рида - Соломона.

Для более общего случая кодов БЧХ кодирование является более сложным. Теперь мы имеем два поля: поле символов и поле локаторов используемое для спектра. Опять последовательных компонент спектра выбираются для того, чтобы

Рис. 8.2. Кодирование кодом Рида-Соломона с помощью преобразования

в них записывались нули. Остальные компоненты представляют собой информационных символов, которые должны выбираться из такими способами, чтобы обратное преобразование Фурье принимало значение в В качестве иллюстрации на рис. 8.3 приводится соответствующая процедура для двоичного кода длины 63. Каждая компонента спектра здесь задается как -битовое двоичное число, а вектор спектра представлен как список -битовых чисел. Кодовое слово также представлено списком -битовых двоичных чисел, но с тем ограничением, что в каждом -битовом числе только бит наименьшего порядка может быть отличен от нуля. Таким образом, в действительности кодовое слово является -битовым двоичным словом. Мы хотим задать спектральный вектор так, чтобы сигнальный вектор был двоичным кодовым словом подобного вида. Теорема 8.2.1 дает нам ограничения, необходимые для построения подходящего спектрального вектора.

Хотя построение кода длины 63 можно выполнить сразу, мы предварительно рассмотрим более простой пример, а именно построим в частотной области -код Хэмминга, используя теорему 8 2.1. Такое построение показано на рис. 8.4. В качестве проверочных частот выбраны компоненты С, и так что одиночная ошибка может быть исправлена. Информация заключена в частотных компонентах и Остальные частоты заполняются согласно ограничениям, даваемым теоремой: Согласно теореме следовательно, может иметь только значения 0 или 1. Эквивалентное «битовое содержание» компоненты Со равно одному биту, а эквивалентное битовое содержание координаты равно трем битам. Таким образом, для однозначного задания спектра надо

Рис. 8.3. (см. скан) Кодирование кодом БЧХ с помощью преобразования Фурье.

зовать четыре информационных бита кода Хэмминга. Эти информационные биты связаны с частотной, а не с временной областью.

В общем случае числа по модулю разбиваются на классы сопряженных элементов:

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

Рис. 8.4. -код Хэмминга.

Следовательно, мы не можем произвольно выбирать элемент из в качестве возможного значения для С допустимы или только те элементы поля, порядок которых делит или нулевой элемент. Порядок каждого элемента поля делит ; следовательно, делит и ясно, что мощность каждого класса сопряженных элементов делит

Для описания кодера разобьем множество чисел на классы сопряженных элементов и выберем по одному числу из каждого класса в качестве представителя. Эти представители единственным образом определяют значимые символы. Для формирования кода БЧХ в качестве проверочных частот выбираются спектральных компонент, которые полагаются равными нулю. Остальные значимые символы являются информационными и могут принимать произвольные значения с учетом ограничений на порядок. Все остальные символы, индексы которых принадлежат тому же классу сопряженных элементов, не являются свободными; они образуют связанные частоты.

На рис. 8.5 изображена ситуация для поля В первый столбец вносятся компоненты свободных частот. Если выбрать в качестве проверочных частот, то получится

исправляющий три ошибки код БЧХ. Тогда являются информационными символами. должны равняться или нулю, или элементу порядка 7 (так как эти элементы принадлежат подполю должно равняться или нулю, или элемепту порядка 3 (так как эти элементы принадлежат подполю должно быть или нулем, или элементом порядка 1; эти элементы образуют подполе GF (2). Все остальиые элементы являются произвольными элементами поля Для определения этих символов требуется всего 45 битов информации. Таким образом, получается -код БЧХ, исправляющий три ошибки.

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

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