Введение в прикладную комбинаторику, Кофман А. (984071), страница 57
Текст из файла (страница 57)
(Б3.86) Неприводимый многочлен р(»), для которого Ь является корнем, не будет примитивным, Период любого элемента конечного поля с р = д~ элементами — делитель д" — 1. П р и м е р. Многочлен р (») = 1 +»+»'+»'+»' (Б3.87) неприводим над Сб(2). Если присоединить к Сб(2) элемент Ь такой, что р(Ь) 1+Ь+Ье+Ьз 1 Ь4 О (БЗ.88) то имеем ф<э эь ьь и (Б3.89) ьь 458 о ЬО ы ь ьэ ь о ! ь~ ь ьз !+ ь +ь +ь' оооо !ооо о!оа оо!о ооо! ! ! ! ! Период Ь равен 6, делителю 2' — 1 = 16.
Корнями р(г) будут Ь', Ь', Ь', Ь' = Ь', и мы имеем р (г) = (г — Ь) (г — Ьо) (г — Ьо) (» — Ь'). (Б3,90) С помощью степеней элемента Ь мы не можем получить все классы вычетов по модулю р(г). Принцип обнаружения и исправления ошибок. Пусть р(г) — неприводимый над Сб(2) многочлен степени Ь. Построим с его помощью код со словами длины и ) й. Для этого рассмотрим все возможные кратные многочлена р(г) степени не выше и: С(г) =аого+ а~»' + ...
+ а ~гл-1 р(г) 9(г) (БЗ 91) кодовое слово С=~)аоа, ... ао ... ал,)~, ао ен СС(2). (Б3.92) Сообщение будем записывать с помощью многочлена М(г) степени не выше ио = и — й. Если умножить М(г) на го, то символы, составляющие сообщение, будут коэффициентами при более высоких степенях, как показано на таблице: о г~ о о ьы оя ел~ М (») (Б3.93) а а, а, а, » м(л) ао а, а, ... ат-1 Разделим, далее, глМ(г) на р(г): »~М(г) =р(г) . 9(г)+г(г), (Б3.94) откуда »~М (г) + г (г) = р (г) д (г) = С (г) (Б 3.95) Коэффициенты многочлена С(г) дают кодовое слово длины и для исходного сообщения. При этом коэффициенты г(г) располагаются на А последних местах кодового слова, так как степень г(г) не выше й — степени р(г).
Как показано выше, с помощью многочлена р(г) можно получить е А-выборок, соответствующих г(г), где е ( 2о — 1 и е делит 2о — 1; эти Ь-выборки будут служить для выявления и исправления ошибок. Кодирование. Пусть имеем сообщение М !!аоа, ... аг ... а~,)). (Б3.96) Представим его с помощью многочлена М(г)=аого+ а г'+ ... +а~»'+ ... +а,„г ' (Б397) 459 Затем умножим М(г) на га (см. (Б3.93) ), разделим произведение на р(г) и получающийся остаток г(г) вычтем из г"М(г): С (г) = г'М (г) — г (г). (Б3.98) Получаем кодовое слово С =~)аоаг ... а~, ... а„, )!. (Б3.99) Декодирование. В случае, когда полученное слово С' совпадает с переданным словом С, при делении С'(г) на р(г) не может получиться ненулевого остатка; поэтому если С' (г) = р (г) д (г) + г (г) (БЗ.!00) и г(г) Ф О, то при передаче была допущена ошибка.
3 а м е ч а н и е. При г(г) = 0 можно сделать вывод лишь об отсутствии ошибок определенного типа, но не об отсутствии ошибок вообще. П р и м е р. Предположим, что требуется передать сообщение ))1 0 0 1(! с помощью кода с длиной слова 7, позволяющего исправить простую ошибку. Имеем т = 4, й = п — т = 3; многочлен р(г) =1+г+г'— примитивный многочлен. Действуем по правилам, изложенным выше; М(г) 1+гз «зМ(г) гз ! га (1 ! г ! гз)(«+ аз) ! (г ! гз) С(г)=г+«'+гз+га и С=)10 ! 1 1 0 0 11!. ипоиепии ииоивиимии Пусть прн передаче С мы получили С' = ))О 1 1 1 ! 0 1)~.
Прн делении С'(г) = г + г' + г' + г' + г' на р(г) = 1 + г + г' получаем остаток г+ г', который указывает на наличие простой ошибки. Б4. Аналогия между циклическими и линейными кодами Как мы показали, многочлен р(г) степени й над ССг(д), который мы будем предполагать примитивным '), разлагается на неприводимые множители над некоторым расширением Сб(г)) (а) = ССг(р) поля Сб(д), р = да: р(г) =(г — а) (г — а') ... (г — а' ).
Порядок а равен п = г)а — 1. Возьмем а — й элементов мультипликативной группы поля: аа! ач для гФО, 1, ..., й — 11 1 1 2, ..., и — й, (Б4.2) и образуем многочлен Ь(г): Ь(г) (г — а ')(г — а з)... (г — а!)... (Б4,3) г) Если р(г) не предполагать примитивным, то можно легко установить существование такого многочлена Ь(з), что р(в))г(в) = ви — 1 и г( делит пи — 1. 460 Тогда ( " — 1) = р (г) и (г). (Б4.4) Действительно, все а', ! = 1, 2, ..., дь — 1, различны и являются корнями г" — 1 в силу (а')" = (а")' = 1. (Б4.5) Так как г' — 1 не может иметь более п корней, то все его корни а', а', ..., а', ..., а" ', а"=а'=! (Б 4.6) Миогочлен й(г) называется дополнительным для р(г).
Для кольца А(г) многочленов ~ь(г) над Сб(е) можно рассмотреть фактор-множество А(г)/(г" — 1), п = е" — 1. Это множество имеет структуру кольца, но не будет полем, так как многочлен г — 1 = р(г) й(г) не является неприводимым. Каждый элемент фактор-кольца А(г)/(г" — 1) представляется многочленом ~р(г) степени не больше и — 1: ~р(г) = аьгь + а,г' + ... + а~г' + ... + а„ ,г"-', а~ ен СС (д), (Б4.7) или и-выборкой ам аь..., а, ~ из элементов СС(д). Заметим, что эр(г) =аьг'+а~ге+ ...
+а;гню+ ... + а„г" (той(г" — 1)) (Б4.8) или г~Р(г) =а„,ге+ а г'+... +а г+'+... +а„зг' '(гпоо(г" — 1)). (Б4.9) Поэтому, если ~р(г) соответствует и-выборка [а„а„..., ао... ..., а„,[, то гф(г) соответствует выборка [а„н аь, ..., а1,,... ..., а„з[, г'~р (г) — выборка [а„м а„„..., а~ ьм ..., а„,] и т. д. В частности, если р(г) = аьгь+ аф + ... + а~г'+ ... + аьгь (Б4.10) — примитивный многочлен степени /з, то имеем (по модулю Й !) р(г)=ах'+аг'+ ...
+е,г~+ ... +агь, ь гр(г) = оог + +а;г+ + ... +аьг +'~ ь-ь-!р( ) + е гь-~ (Б4.11) Векторы, компоненты которых совпадают с коэффициентами многочленов из (Б4.11), определяют (и — и) -мерное подпространство пространства А(г)/(г" — 1). 4б! ...а, 0 0 ...0 (Б4 12) ао " ал ао а! .. ° а! а ... а! 11 У'~1= тхл 0 0 Ее ранг равен и! = п — й. Подпространство, порожденное векторами строками ~!У'!~, циклическое в том смысле, что если оно содержит вектор ~атос!!... а„!~~, то оно содержит также ~~со„!ао... ... а о!! и т.
д. Пусть Ь(г) = б,г'+ б,г'+ ... + б г" — дополнительный многочлен для р (г): гл — 1 = р (г) Ь (г) (Б4.13) Тогда имеем Ь(г)=бог'+б!г'+ ... +бтг", г" (г) = бог'+ б!г'+ ° + б„г +', (Б4 14) го !Ь(г) = б го-! + + б гл-! и матрица бо б! ° бт О 0...0 — 0 бо" бт 0...0 олл 0 0 ...бо б! ...бл (Б4.15) аналогично определяет й-мерное подпространство пространства А(г)Яг" — 1). Если изменить порядок столбцов в матрице 2Мл'6! О...О Об„,...б,б О ...О бт ...б О бт...б, б О ...О О )1 М' !1- (Б4.16) ЙХл то, как легко проверить, получаем соотношение 'б У' !! ~~ М' 11 = ~~ 0 1~ (Б4.17) — хорошо известное основное соотношение для линейных кодов, показывающее, что пространство, порожденное матрнцей ~~У'~~— нулевое пространство для пространства, порожденного !!М'!~, и наоборот.
П р и м е р ы. 1) Покажем, что циклический код, построенный с помощью многочлена () 1(г(гз (Б4.18) 462 Заменим последовательность многочленов (Б4.11) матрицей '6 У' $ тХл над СО(2), фактически совпадает с кодом Хэмминга (3,4). Имеем + аз+ г4+ г4). (Б4 19) г' + 1 = (1 + г'+ г') (1 Построим матрицу для д(г): о ооо о о о о о ! о оо!о ооо Ф'Ц= (Б4.20) Она приводится к канонической форме, если к первой строке прибавить третью, затем к новой первой строке прибавить чет- вертую, а затем ко второй прибавить четвертую: ооо!о о!оо оо!о1!о ооо4о (Б4.21) 1! У 1!= Аналогично для /г (г) = 1+ г'+ г'+ г' имеем оо!!!о цыц=о!!!о!6. о 1оо~ (Б4.22) или о!оо Црй~! о 4 ! ! о 4 о о!оо (Б4.23) ЦЯЦ получается из Ц '4в'(), если поменять местами первую и третью строки и затем прибавить к третьей строке первую.
Очевидно, что Ц У Ц и Ц Ж Ц представляют собой матрицы линейного кода Хэмминга: (Б4.24) ЦУ!1= — ЦЦ 1 Ц!Ц А ЦЦ 4Х4 ЦЖ Ц=Ц вЂ” Ц А Ц' ~! 1 !!Ц. (Б4.25) зхз (Б4.26) 463 2) Мы попытаемся определить вид многочленов, которые при построении по ним линейного кода позволяют обнаружить: а) простую ошибку, б) нечетное число ошибок, в) две ошибки, г) три ошибки. Заметим, что если передаваемое слово определяется много- членом С(г), а принимаемое — многочленом С'(г), то С' (г) = С (г) + Е (г), тде Е(г) — «полипом ошибок», обладающий ненулевым коэффициентом для каждой из степеней г, у которой коэффициент был передан неправильно.
Например, если многочлен С (г) = 1 + гэ + г'+ г" (Б4.27) определяется двоичной последовательностью 1 0 1 1 0 0 0 1. (Б4.28) при передаче которой 2-й, 4-й и 6-й символы изменяются: 11100101, (Б4.29) то миогочлен С' (г) = 1 + г + г' + г' + г' (Б4.30) представляется в виде С() (! ( ) з( ~)(( ( з! з) (Б4.31) и полипом ошибок равен Е (г) = г + г'+ гз (Б4.32) Поэтому для выявления ошибки данного типа необходимо, чтобы Е(г) не делился на р(г), так как, по определению, много- члены, соответствующие кодовым словам, делятся на р(г). а) Если ошибка простая, то Е(г) имеет вид Е(г)=г', 1=0, 1, ..., и — 1.
(Б4.33) В качестве р(г) достаточно взять полинам, не делящий никакой одночлен г', например Р (г) = 1 + г. б) Многочлен вида 1+ гх можно записать в виде ф(г)=1+г'=(1+г)(1+г+г'+ ... +г'-'). (Б4.35) Очевидно, что ~р(1)=(1+1)(1+1+1+ ... +1)=0. (Б4,36) Следовательно, если многочлен С(г), соответствующий кодовому слову, делится на ~р(г): С (г) = ~а (г) з (г), (Б4.37) то С (1) = ~р (1) з (1) = 0 з (1) = О.
(Б4.38) Каждый такой С(г) обладает четным числом ненулевых коэффициентов, и любое нечетное число ошибок можно обнаружить. в) В случае двух ошибок полнном ошибок можно записать в виде Е (г) = г'+ г', ! < ! < а — 1 (Б4.39) или Е(г)=г (1+г ). (Б4.40) Тогда достаточно в качестве р(г) взять примитивный многочлен степени й. Действительно, этот многочлен о р(г) =ао+а,г+ ... + а„г, (Б4.41) будучи примитивным, не может делить многочлен г' — 1 при е < 2о — 1 = п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
