преобразование Фурье. Однако конструкция кодера во временной области обычно проще.

Минимальноэ расстояние циклических ОРМ-кодов должно удовлетворять границе БЧХ. Эту границу устанавливает следующая теорема.

Теорема 13.6.3. Циклический ОРМ-код над GF (2) порядка г и длины п ~ q ~\ представляет собой подкод кода БЧХ с конструктивным, расстоянием d = 2"- - 1; его минимальное расстояние не меньше указанного конструктивного.

Доказательство. В двоичном представлении 2"- - I записывается {т - /)-разрядным двоичным числом, состоящим из одних единиц. Числа, меньшие 2""- 1, имеют менее т - г единиц. Поэтому Wzd) < т ~ г - \ при / = 1,2, 2"- - 2 на являются корнями g{x) при / = 1, 2, 2"- - 2. Следовательно, этот код является подкодом кода БЧХ с конструктивным расстоянием d = 2"-- - 1. □

Недвоичный циклический ОРМ-код порядка г также представляет собой* подкод кода БЧХ, конструктивное расстояние которого равно ф"~- 1, если г меньше q - 1. Если последнее условие не выполняется, то выражение для конструктивного расстояния несколько сложнее, что отражено в следующей теореме.

Теорема 13.6.4. Пусть г = (q - I) Q + R, где О < R < q ~ - 1. Циклический ОРМ-код над GF (q) порядка г и длины п = = q" - 1 представляет собой подкод кода БЧХ над GF (q) с конструктивным расстоянием

d = 1;

его минимальное расстояние не меньше указанного конструктивного.

Доказательство. Рассмотрим -ичное разложение числа (д - - 1. Максимальный значащий символ этого чис-

ла равен q - R ~ I; остальныет - Q - 1 символов равны - 1. Следовательно,

W, {{q - - 1) = (9 1) (m - Q - 1) -f 9 - - 1 =

= {q~l)m-r.

Но тогда 9-ичные веса всех /, меньших (9 - i?) - 1,

меньше (q - I) т - г. Следовательно, при всех /, удовлетворяющих неравенству О < ]"<-(q - i?)?""-) 2, а являются корнями порождающего многочлена, а циклический ОРМ-код является подкодом кода БЧХ с теми же корнями порождающего многочлена. Это завершает доказательство, □

13.6. ОБОБЩЕННЫЕ КОДЫ РИДА-МАЛЛЕ1>А 473

Рис. 13.7. Параметры некоторых обобщенных кодов Рида-Маллера.

Характеристики некоторых обобщенных кодов Рида-Маллера представлены на рис. 13.7. При 9 = 2 коды эквивалентны кодам Рида-Маллера. Приведенные на рисунке минимальные расстояния в действительности являются определяемыми теоремой 13.6.4 нижними границами минимальных расстояний. Число информационных символов получается подсчетом: так как код определяется через корни g {х), число проверочных символов находится подсчетом положительных целых чисел, меньших п, для которых

(}) < (q - I) т - г - I.

Теорема 13.6.5. Код, дуальный ОРМ-коду над GF (q) порядка г и длины п - q", эквивалентен ОРМ-коду порядка {q - \) т - - г - 1 и длины п = cf.

Доказательство. Пусть - ОРМ-код, и пусть - циклический ОРМ-код, получаемый укорочением f. Доказательство теоремы распадается на три шага. На шаге 1 находится порождающий многочлен Я {х) кода -l, дуального циклическому ОРМ-юду . На шаге 2 показывается, что проверочные многочлены как , так и "g-L имеют множителем х - 1. НашагеЗ производится расширение кодов и до ОРМ-кодов и и показывается, что расширенные коды дуальны.

Шаг 1. является множеством слов с проверочными частотами, которые при всех / удовлетворяют неравенствам

О < / < - 1

<. {q- \) т - г ~\.

При всех указанных / величины aJ являются корнями порождающего многочлена g{x). Для удобства мы заменили О на q" - I в интервале изменения / (см. примечание на с. 469), так что да, (/) > > О при всех /. Из теории циклических кодов следует, что для определения проверочных частот дуального кода нужно заменить / на - 1 - / и обратить нестрогое неравенство для -ичного веса, заменив его строгим неравенством. Поэтому индексами проверочных частот служат те /, для которых

да, (9 - 1 - /) >(9 - 1) /тг - г - 1.

Но если

/ = /о -Ь Ы f -I------f /m-i9"-.

r~I-/ = (9-I-/o) +

+ (9 - 1 - /i) 9 + • • • -b (9 - 1 - W i) 9"-. что может быть проверено сложением равенств. Следовательно, Wq{q - 1 - /) = - 1) m - (j). Поэтому дуальный код имеет проверочные частоты при /, удовлетворяющих неравенству О < < / < 9"-, и

Щ (/) = (q - I) т ~ W, (q" - I - j)< г + I.

Соответствующие этим / числа а являются корнями порождающего многочлена Я (х) дуального кода f

Шаг 2. Число а" не является корнем ни g(x), ни Я (х). Следовательно, проверочные многочлены как W, так и W- содержат множители X - 1.