У. Питерсон - Коды, исправляющие ошибки (1267328), страница 41
Текст из файла (страница 41)
6.8 были независимо доказаны Пеле [229] и Берлекэмпом [21). Задачи 6.1. Постройте таблицу сложения и умножения элементов поля Вг(7). Найдите порядок каждого элемента. Какие элементы являются примитивными? 6.2. Найдите все неприводимые многочлены степени 5 или меньше над полем Сгг (2). Заметим, что если многочлен степени и не является неприводимым, то он обладает делителем, степень которого не превосходит лт ,'2.
Найдите неприводимый многочлен степени 5 над Сгг(3). (Первую часть задачи можно проверить с помощью приложения В.) 6.3. Сколько идеалов существует в алгебре многочленов по модулю Х' — 1 над полем 6г" (2)? Перечислите порождающие нх многочлены. (Ответ: семь нетривиальных идеалов.) 6.4. Многочлен Х'+ Хз+ Ха+ Х+ 1 = р(Х) неприводнм над тюлем Стг"(2), и поэтому алгебра многочленов по модулю р(Х) совпадает с полем бг(2'). Пусть через к обозначен класс вычетов [Х).
Покажите, что са не является примитивным элементом и, следовательно, р(Х) — не примитивный многочлен. Покажите, что а+ 1 — примитивный элемент и найдите его минимальный много- член, который является примитивным многочленом. (Ответ: минимальный многочлен для а+ 1 равен Х4+ Хз+ 1.) 6.5. Составьте таблицы, аналогичные табл. 6.1, для полей 6г (2з) и Ог (8») . 6.6. Определите, какие круговые миогочлены являются множителями в разложениях следующих многочлеиов: Х'а — 1, Хз' — 1, Х'ат — 1 и Хл'э — 1. Для каждого из круговых многочленов определите число и степень неприводимых множителей над полем бР(2).
Проверьте результаты при помощи приложения В. 6.7. Многочлен Г(Х), двойственный некоторому многочлену т"(Х), определяется как !"*(Х) = Х"'!'(1~Х), где гп — степень !(Х). Докажите следующие утверждения: а. Многочлен 1»(Х) неприводим тогда н только тогда, когда неприводим многочлен [(Х). б. Если !(Х) неприводим, то !(Х) и 1*(Х) принадлежат одному и тому же показателю. Следовательно, 1»(Х) примитивен тогда ж, ае ее 1Ю. ') Следует добавить к этому списку неболыпун» книгу М. М.
Постникова "Основы теории Галуа», Фнзматтнз, М., !960. — Прим. рад. в. Если !'(Х) = !(Х) и степень ~(Х) больше 2, то !'(Х) не является примитивным. (Двойственными самим себе примитивными многочленами являются только многочлены Х'+Х+ ! и Х+ ! над полем 6г" (2) и Х+ ! над полем 6г(3).) г. Если !'(Х) = ц(Х)л(Х), д(Х), й(Х) — нсприводимые много- члены и ((Х) = !'(Х), то либо й(Х) = а'(Х), либо д(Х) = д"(Х) н й(Х) = й'(Х). 9.9. Покажите, что в векторном пространстве наборов длины и с элементами иэ 6Р(р), где р — простое число, любая подгруппа по сложению является подяространством.
6.9. Выбрав некоторос двумерное подпространство Р пространства 6г" (2'), проверьте утверждения теоремы б.ЗО и следствия 6.2, вычисляя д(Х), Е(Х), д(Х), й(Х) и 0; проверьте, что д(Х)ай(Х) = й(Х)«-д(Х). (Не следует в качестве Г выбирать подполе поля 6г" (2').) 7 Линейные переключательные схемы Основу оборудования, используемого при кодировании и исправлении или обнаружении ошибок с помощью линейных кодов, составляют линейные переключательные схемы с конечным числом состояний.
В равд. 7.2 — 7.4 дается описание некоторых схем, используемых при реализации линейных кодов. Некоторые свойства этих схем приводятся в равд. 7.5, Равд. 7.6 представляет собой введение в общую теорию линейных переключательных схем с конечным числом состояний, причем там показывается, что любая линейная переключательная схема эквивалентна некоторой схеме типа схемы, описываемой в равд.
7.2. 7. Ь Определения Предполагается, что в линейных переключательных схемах информация представлена с помощью элементов поля бг" (д) Используется три вида устройств. Первое из них — сумматор, имекщий два входа и один выход, причем выходной символ равен сумме входных (в смысле ог(д)). Второе — запоминающееустройство с одным входом и одним выходом. Оно может быть устройством задержки, выходной символ которого всегда совпадает с входным символом в предшествующий момент времени.
Его можно рассматривать также как ячейку регистра сдвига. В регистре сдвига имеется сигнал сдвига, не показанный на схемах, который приходит обычно са схемы синхронизации. В момент прихода этого сигнала выходной символ каждой ячейки принимает значение, которое было на входе непосредственно перед сигналом сдвига. Третий вид устройств — это устройство умножения на константу, имеющее один вход и один выход, причем выходной символ равен входному символу, умноженному иа некоторую константу, которой может быть любой элемент поля.
В этих устройствах любое число входов может быть соединено с любым выходом, но никакие два выхода не могут быть соединены. Эти устройства изображаются так, как показано на фиг. 7.1. Линейными переключательными схемами с конечным числом состояний называются любые схемы, содержащие конечное число сумматоров, устройств памяти н устройств умножения на константу, соединенных любым допустимым способом. Любая линейная переключательная схема с конечным числом состояний может Фнг. 7Л.
Блоки, являющиеся составными элементами линейных нереклюпательных схем. а — сумматор; б — аапоминаюгиее устроастао, храпящее а, т. е. вмхоа его равен а; а — умножитель на постоиггг~ую веаичнву а. быть реализована при помоши электронных ламп, транзисторов, магнитных сердечников или других логических элементов, используемых в цифровых вычислительных машинах.
В бинарном случае сумматор представляет собой логический элемент «исключаюшего ИЛИ», а устройство памяти является устройством задержки, либо ячейкой дополнительного соединения обычного двоичного регистра сдвига. Введение в схему умножителя на константу, равную 1, эквивалентно введению дополнительного соединения, а умножитель на константу, равную О, соответствует отсутствию такого соединения.
Вход и выход предполагаются последовательными, т. е. входной сигнал состоит из элементов поля, подаваемых на входной конец последовательно, — по одному в единицу времени; аналогичным образом формируется выходной сигнал. Когда, как это часто бывает, на входе или выходе появляется многочлен, то на входном или выходном конце имеются только коэффициенты„ которые переда|отея начиная с высших порядков, потому что при делении у делимого сначала должны быть обработаны коэффициенты высших порядков. Так, миогочлен ПХ) = 1„Х" + 1„,Х ' + ... + й будет подаваться на входной конец или появляться иа выходном конце в виде последовательности из и элементов поля, которая будет начинаться с ~„, через единицу времени появится ~„ ь спустя еше единицу времени появится ~„ я и т.
д. 7.2. Умножение и деление многочлснов В этом разделе описываются схемы, используемые для умножения или деления любого многочлена на некоторый фиксированный многочлен. Схема, изображенная на фнг. 7.2, используется для умножения любого многочлена на входе: а(Х) =ааХа+па,Ха-1+ .. + а,Х+и на фиксированный многочлен Ь(Х)=Ь,Х" +Ь,Х"-'+ ... +Ь,Х+Ь, Предполагается, что первоначально устройство памяти содержит нули, а на вход поступают коэффициенты многочлена а(Х) начиная с коэффициентов высших порядков, после чего следует г нулей.
Произведение равно а(Х)Ь(Х) аяЬ Ха'>г+ (а~,Ь +ааЬ,,)Ха.>г-~+ +(аа аЬ„+па,Ь,+ааЬ а)Ха>'-з+... ° + (аойя + аА + аайо)Хз + (аА + а 1 Ьо) Х + аойа. Когда на вход подается первый коэффициент аа многочлена а(Х), то на выходе появляется первый коэффициент произведения а(Х)Ь(Х), равный аяЬ, В этот момент все ячейки устройства памяти содергкат нули. Спустя единицу времени на входе появляется аа „ аа находится в первой ячейке, а все остальные ячейки содержат нули. Как можно увидеть из фиг. 7.2, выход будет равен а„,Ь„ + аяЬ ь т. е. величине второго коэффициента в произведении а(Х)Ь(Х).
Аналогично через две единицы времени на входе появится аа ь а ячейки регистра сдвига будут содержать элементы аа ь аа, О, ..., О, О, О. Выход равен аа,Ь„+ а„,Ь„, + пай„я, т. е. величине третьего коэффициента произведения а(Х) Ь(Х). Дальнейшие операции производятся аналогичным образом. После г+ Ь вЂ” ! сдвигов в ячейках регистра содержатся элементы О, О, О, ..., О, ао, а, и выход равен аоЬ, + а,йо, т. е. предпоследнему коэффициенту произведеяия а(Х)Ь(Х).
После г+Ь сдвигов регистр сдвига содержит элементы О, О, О, ..., О, ао и выход равен аойо — последнему коэффициенту произведения а(Х)Ь(Х), так что произведение получено полностью. 7.З. Схема для умножения многочленов. Вддчду йг 2 Ьгч л„ йя Фнг, 7.3. другая схема для умножения многочненов. Другая схема умножения показана на фиг.
7.3. Коэффициенты произведения формируются в регистре сдвига. После подачи на вход первого символа выход равен адй„, а ячейки памяти содержат только нули. После одного сдвига ячейки содержат элементы адйо, адйь ..., адй, 1 и вход равен ад ь Поэтому выход равен адй„, + ад,й„т. е. второму коэффициенту. После следующего сдвига ячейки памяти содержат элементы ад,йо, адйо+ад — А* адй1+ад ~йя, ..., адй, в+ ад ~й, 1 н вход равен ад я. Следовательно, выход равен адй„я+ ад,й„~+ ад хй„т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
