У. Питерсон - Коды, исправляющие ошибки (1267328), страница 50
Текст из файла (страница 50)
Опишем этот способ. Для любого многочлена с коэффициентами из поля ОР(д ) а(Х) =а,Х» '+а,Х» 2+ ... +ао рассмотрим вектор Ь = (а (а" '), а (аи 2), °, *, а (1) ) где а — элемент из поля 6Р(д'") порядка и. Далее, рассмотрим многочлен Ь(Х)=Ь„,Х +3» Х + ... +Зов ( и- )Хи-ь+ ( и-2)х~-~+ + (1) Хи-4(а а(и-П(и — Н+ <и-Н~"-21+ +а ) 1 + Х» 2 Г (и-П (и — П ю [и — 21 (»-21 ю Ф ~а +а .2а + +ао)+ + ° ° ° +1(аи 1+а 2+ ...
+ао)= аи,((а - Х)" '+(а — Х)и-2+ +1)+ +а ~((ай 2Х)и '+ (аи-2Х)и-2+ + 1)+ +...+..(х-+х:-+ ... +1). (3.1О) Заметим, что элементы 1, а, а', ..., а — ' представляют собой вса корни многочлена Х" — 1=(Х вЂ” 1)(Х"-'+Х"-'+ ... + 1) и, следовательно, все эти элементы, за исключением 1, являются корнями многочлена Х"-'+Х" — з+ ... + 1. Значение 1"-'+ + 1" ~+ ...
+! равно и. Отсюда следует, что Ь(а — ') = пас Таким образом, справедлива следующая теорема: Теорема 8.2. Пусть а(Х) — произвольный многочлен степени, меныией чем и, над полем 6Е(в") и Ь(Х) — многочлен, Ьй коэффициент которого равен а(а'), 1= О, 1, ..., и — 1, где и — элемент из 6Е(у ) порядка и. Тогда 1-й коэффициент мпогочлена а(Х) задается равенством па Ь(а-ю) (8.!1) Следствие 8.1. Если (п,р)=1, где р — характеристика поля 6Г(д), то а; = п — 'Ь(а-').
Заметим, что для каждого корня многочлена а(Х) найдется коэффициент мвогочлена Ь(Х), который равен нулю, и если (и, р) = 1, то для каждого корня многочлена Ь(Х) должен найтись равный нулю коэффициент а(Х). В остальной части этого раздела будем предполагать, что (и, р) = 1. Рассмотрим совокупность многочленов а(Х), удовлетворяющих следующим условиям: 1. Для любого 1 значение многочлена а(а') является элементом поля 6Е(д)„где а — элемент порядка и. Другими словами, коэффициенты мвогочлена Ь(Х) являются элементами 6Р(д).
2. Для любого многочлена а(Х) все коэффициенты а~и а;,, ... ..., а; равны нулю. Поскольку любая линейная комбинация многочленов, удовлетворяющих этим условиям, также удовлетворяет этим условиям, то рассматриваемая совокупность многочленов является подпространством. Теперь рассмотрим совокупность многочленов Ь(Х), ассоциированных с многочленами а(Х). Многочлен принадлежит этой совокупности ассоциированных многочленов тогда и только тогда, когда все его коэффициенты принадлежат полю 6Р(д) и по теореме 8.2 элементы а ", а ", ..., а * являются корнями Ь(Х). Таким образом, совокупность многочленов Ь(Х) образует циклический код, причем элементы а ', а ", ..., а т являются корнями порождающего многочлена этого кода.
Требование, состоящее в том, чтобы коэффициенты многочлена Ь(Х) принадлежали 6Р(д), накладывает ограничение на коэффициенты ассоциированного с Ь(Х) многочлена а(Х). Поскольку коэффициенты Ь; равны а(а'), то это означает, что значения а(Х) должны принадлежать 6Р(д) при Х = 1, а, аз, ..., й '. Тогда [а (Х)) б = а (Х) (8.12) или аб Хбм-14 + аб,Хб(-а + =й„— 1Х +а 2Х + ... +об. Отсюда следует, в частности, что 1 М а~1Хб = а41Л"' ° где в каждом случае 111 приведено по модулю и.
Таким образом, вообше а ; = (а1)б. Более того, это условие является не только необходимым, но и достаточным, поскольку если оно справедливо для любого коэффициента, то должно выполняться равенство (8.12) и значения, являющиеся корнями многочлена Хч — Х, должны принадлежать 6т 41) по теореме 6.18. еорема 8.3. Многочлен а(Х) над 6Г(д ) принимает значения из 6Р(д) при Х = 1, а, аз, ..., й" ', где а — элемент порядка и и (и, д) = 1, тогда и только тогда, когда для любого 1 а21 — — (а1)2 (Ф приведено по модулю п), Пример.
Рассмотрим совокупность всех многочленов а(Х) с коэффициентами из 6т(24), степень которых меньше 9, таких, что онн принимают значения из 61".(2). Пусть а — примитивный элемент поли 6т (24), так что и = 15. По теореме 8.3 й =й, 2— аз =а, 12 б' аз=а З 1 ° йб аз аз =й аз = 12 и и ап Тогда элемент аб должен быть равен О или 1. Далее, в качестве а1 можно выбрать произвольный элемент из 6т'(24), но после этого элементы аз, а4 и аз уже определяются однозначно.
Поскольку требуется, чтобы степень а(Х) была меньше чем 9, то элемент а,з — — О и, слеДовательно, элементы аз, аб и аб тоже Равны ну ю. Аналогично аз= ам = О и аз =аи= а1з = аи = О. Итак, многочлен а(Х) имеет вид ( Х ) а з Х з + а 4 1 Х 4 + 4 1 1 Х + а 1 Х + йо о о аз=а, 1 2' а'=а, 3 б' а2 — а а,'= аьн а,'=а„ аз=а б 12' а' =а и б> аб =й 14 13' Теперь рассмотрим кодовый мпогочлен Ь(Х), ассоциированный с многочленом а(Х). В соответствии с определением (8.10) Ь(Х) аз~(пвХ)~ — 1 ( (пеХ)в-з (( (паХД+ +а",~(а'Х)" +(а'Х)" ~+ ... +(аэХ) 3+ пз( (пзХ)'з-~ ( (птХ)л -~ ) + (пхХ)") + +и ((пХ) -~+(пХ)ь-в+ +(пХ)о(+ +и ((поХ)" '+(поХ)" '+ +(поХ)о) Все корни Ь(Х), за исключением па, а-', а-', а-~ и а-~, являются элементами 6Р(4).
Это можно проверить непосредственно. Обозначим через Т(х) частное (Хм+1)~'(Х+ 1); тогда, например, Ь(а-а) азТ(1)+аТ(а х)+азТ(а-в)+а Т(а-г)+а Т(п-в) ав поскольку все ненулевые элементы 6Р(4), за исключением сна, являются корнями Т(Х). Элемент а~ может быть выбран шестнадцатью способами, а элемевт аз- — двумя, и, таким образом, существует 32 = 2а многочленов Ь(Х). Эти многочлены образуют двоичный циклический код, содержащий 2а кодовых слов, т. е. (15,5)-код.
Это код из предыдущего примера, поскольку его порождающий многочлен имеет те же самые корни. В теоремах 8.2 и 8.3 утверждается, что для любого кодового слова Ь(Х) циклического кода над 6г (д) существует ассоциированный с ним многочлен а(Х), такой, что Ьй коэффициент много- члена а(Х) в соответствии с равенством (8.11) получается как значение кодового многочлена Ь(Х) при Х = а †'.
Этн теоремы полезны при анализе произведений циклических кодов (равд. 8.12), мажоритарно-декодируемых кодов (гл. 10) и в некоторых других случаях. 8.4. Коды Хзмминга Двоичные (2'" — 1,2'" — гп — 1)-коды Хэмминга, рассмотренные в равд. 5.1, эквивалентны циклическим кодам. Пусть а — примитивный элемент поля 6г" (2"').
Рассмотрим нулевое пространство матрицы Н=(пэ ~, а' з, ..., а, 1). Если степени элемента а представить в виде векторов-столбцов из 0 и 1, то каждый ненулевой столбец длины и будет одним из столбцов матрицы Н. Следовательно, ненулевое пространство матрицы Н является кодом Хэмминга, исправляющим одну ~шибку.
Как циклический код код Хэмминга полностью определяется условием, что вектор (1(Х)) принадлежит коду тогда и только тогда, когда элемент сг является корнем многочлена !(Х). Минимальная функция для а — примитиваый многочлен, и, следовательно, образующий многочлен этого кода примитивен.
И наоборот, любой код, порождаемый примитивным многочленом, является кодом Хэмминга. Пример. Пусть и = 4 и а — корень примитивного многочлена Х4+ Х+ 1. Тогда проверочная матрица Н (!5, 11)-кода Хэммннга, порожденного этим многочленом, имеет вид 1!110!011001000 0111!0101100100 Н =(ам а" "' " ' ') = 00 !111010110010 !110101100!0001 (см. табл. 6.1). При этом (2™,2'" — т — 1)-код, который образуется из кода Хэмминга присоединением проверки на четность по всем символам, обладает минимальным расстоянием, равным 4, как это было показано в равд. 5.!. Этот код можно рассматривать как нулевое пространство матрицы (8.! 4) Н= '" '" 1 2 — 2 2 ...
11* (8.16) Этот код несколько отличается от рассмотренного выше кода с расстоянием, равным 4. Хотя здесь добавлена дополнительная проверка на четность, длина кода не увеличилась, ибо при это исключается один из информационных символов. Для этого кода вектор ЯХ)) является кодовым вектором тогда и только тогда, гюгда элементы а и 1 являются корнями ((Х). Совокупность котовых векторов представляет собой совокупность кодовых векторов четного веса первоначального кода Хэмминга с расстоя- Это не циклический код, а пример расширенноао циклического кода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
