У. Питерсон - Коды, исправляющие ошибки (1267328), страница 42
Текст из файла (страница 42)
е. третьему коэффициенту произведения. Дальнейшие операции производятся аналогичным образом. Эту схему можно истолковать и по-другому. Совокупность г ячеек устройства памяти образует регистр, в котором записан некоторый многочлен. Первоначально этот многочлен равен нулю. Появление на входе коэффициента ад прибавляет к содержимому регистра многочлен адй(Х). В результате сдвига производится умножение на Х, и на выходе появляется первый коэффициент, вычисление которого закончено. После появления на входе коэффициента ад 1 к многочлену, находящемуся в регистре, прибавляется многочлен ад,й(Х); при сдвиге снова производится умножение на Х, а на выходе появляется второй коэффициент и т.
д. Схемы такого вида, как показано на фиг. 7.3, могут иметь более чем один вход. Например, схема, изображенная на фиг. 7.4, имеет два входа а~(Х) и ав(Х), а выход равен Ь(Х) =а,(Х)Ь(Х)+а,(Х) Ь(Х), где Ь(Х)=Ь„Х" + Ь,,Х" '+ ... +Ьм й(Х)=Ь,Х" +Ь„,Х" + ... +Ьо. Схема изображена для случая, когда многочлены й(Х) и Ь(Х) имеют одну и ту же степень. Однако если степени многочленов не совпадают, то в качестве г можно выбрать наибольшую степень и положить коэффициенты высших порядков одного из многочленов равными О. ЛХЯ7ая(4 Фнг. 7ХП Схема умножения с двумя нходамн. Заметим, что во всех этих схемах коэффициент прн Х"+' поступает на вход в момент времени, когда коэффициент при Х* появляется на выходе.
Коэффициент при Х' в произведении появляется на выходе через г единиц времени после того, как коэффициент при Хо поступил на вход. Таким образом, в некотором смысле задержка на выходе равна г единицам времени. Пример. С помощью схемы, изображенной на фиг.
73, производится умножение входного многочлена на многочлен й(Х)= =Ха-(-Ха-)-Х'+Ха-(-1 над полем из двух элементов. Поучительно записать содержимое устройства памяти для каждого шага процесса вычисления и сравнить запись с промежуточными результатами обычного вычисления произведения от руки. Схема деления многочлена Ы(Х) = д„Х" +д„,Х -'+ ...
+г(о на многочлен а(Х) = д,Хг+ д, ~Х"-'+ ... + до показана на фиг. 7.6. Устройство памяти вначале должно содержать нули. Выходной символ принимает значения, равные О, для первых сдвигов, т. е. до тех пор, пока первый входной символ не достигнет конца регистра сдвига. После этого появляется первый ненулевой мнг 7.6. Схема для умноження на многочаен Ха+Ха+Х'+Х~+1. Уа -Уг Дг 'Зг-а у -я англ у~г + + + + + Фяг. 7.В. Схема лля деленян многочленоя. выходной символ, который равен И й„-~ — первому коэффициенту частного. Для каждого коэффициента частного дт необходимо вычесть из делимого многочлен дай~Х).
Это вычитание производится с помощью 'обратной связи. После всех п сдвигов на выходе появится частное от деления, а остаток от деления будет находиться в регистре сдвига. Работу схемы легче всего понять с помощью подробных примеров. Пример. Схема„изображенная на фиг. 7.7, предназначена для деленна многочлена на входе на многочлен д(Х) = Ха+ Х'+ +Х'+Ха+ 1 над полем из двух элементов. В табл. 7.1 последовательные этапы деления многочлена Х'а+Х" + Х'о+Хг+Х'+ + Ха + Х + 1 на многочлен Ха+ Х'+ Х'+ Ха + 1 сравниваются с последовательными операциями по этой схеме.
Заметим, что при обычном делении столбиком члены высших порядков расположены слева, тогда как в регистре сдвига члены высших порядков располагаются справа. Первые шесть сдвигов не имеют аналогий при делении «столбиком». После шестого сдвига содержимое регистра сдвига соответствует многочлену, обозначенному в табл. 7Л буквой А. Его старший коэффициент равен первому символу частного и, кроме того, выходу после седьмого сдвига.
Обратной связи соответствует многочлен, обозначенный через В, а входу — одночлен С, сносимый вниз при делении столбиком. После седьмого сдвига содержимому регистра сдвига соответствует многочлен, обозначенный буквой П. Обратная связь дает многочлен Е; одночлен г, сносимый вниз, совпадает с входным символом; после восьмого сдвига регистра сдвига его содержимым является многачлен 6. Этот процесс продолжается до тех пор, пока после четырнадцати сдвигов, по одному для каждого коэффициента делимого, содержимым регистра не станет остаток от деления и все коэффициенты частного не появятся на выходе. Фяг.
7.7. Схема для деления на многочлен Ла+ Ха+ Х'+ Х'+ 1. 7аблица 7.!. Сравнение деления столбиком и операций в схеме для деления а) Обычное деление столбиком Хе+Хе+Хе+а +а +Хт+Х+1 0 ч-х4+ ха+О +х+1 Хе+ Хл+ Хв+ Хл+ О+ ха а +о +ха+о +хл+х'+хв 0 +а +о +о +а +О +О о +х'+а +х'+х'+хе+Ха а +о +а +О +о +О +о Ха+О +Ха+Ха+ Хе+ да+О Ха+ Хт+ Ха+ Хй 4-О + 0 + Хт Хе+О +О +Х4+Хл+Хе+Х Хт+Х +Ха+Ха+О +О +Х ха+х'+а +хв+х'+о+! Х +Ха+Хе+Ха+а +а+1 О +Хе+О +Хе+а+О б) Последовательные операции в схеме для деления Содержнмое регнстра сдвига восле ! сдвнгов Выходной *нмвол после /-го сданга Осратнаа связь в момент 1-го сдвнта Входной символ в момент Г-го сдвига 0 1 2 3 4 б 6 7 6 9 10 11 12 13 14 000000 100000 010000 101000 110100 011010 001101 00000! 1001!! 110100 111010 111!01 11100! О!1011 001010 0 0 0 0 0 0 1 1 1 0 0 1 1 1 0 000000 000000 000000 000000 000000 000000 100111 !0011! 10011! 000000 000000 1001 11 100111 100111 1 0 1 1 0 0 1 0 0 1 1 0 1 ! г-г Угл Уг' Игл Ьг яг-г )а иг-з Фнг.
7.8. Схема для умножения на многочлен л (Х) и деления на многочлен л (Х), В этой схеме коэффициент при Х) в частном появляется на выходе в тот же момент времени, когда коэффициент при Х) появляется на входе. Таким образом, вход и частное синхронны.
Схема регистра сдвига, с помощью которой может производиться сначала умножение на многочлен й(Х), а затем деление на многочлен д(Х), изображена на фиг. 7.8. Как видно из рисунка, она получается комбинированием схемы умножения, изображенной на фиг. 7.3, и схемы деления, изображенной на фиг. 7.6. Здесь предполагается, что степень многочлена й(Х) не превосходит степени многочлена д(Х) (см. следующий пример). Пример.
На фиг. 7.9 показана схема регистра сдвига, используемого для умножения входного мпогочлена на многочлен Хв+ + Х+ 1 и для деления результата на многочлен Ха+ Хв+Х'+ + Ха+1. Регистр сдвига содержит часть делимого, находящегося в процессе обработки. Входные соединения прибавляют к содержимому регистра сдвига произведение многочлепа Хв +Х + 1 и входного символа вместо того, чтобы просто прибавлять входной символ, как это было в схеме деления (фиг. 7.6). Если постоянный множитель имеет степень, более высокую, чем делитель, то в конце регистра сдвига, соответствующем членам низшего порядка, должны быть помещены дополнительные ячейки. В этом случае, для того чтобы закончить деление, требуется произвести столько же дополнительных сдвигов с нулем на входе, сколько ячеек было добавлено. На фиг. 7.10 приведен Фиг. 7.9.
Схема для одновременного умножения на миогочлен Ха+ Х+ 1 н деления на многочлен Хе+Ха+ Хг+Х'+ 1, Выход фиг„7.10. Схема длЯ одновРеменного Унножениа на нногочлен Х'а+ Хч+ Хг+ 1 и деления на инагочнен Ха+ Ха+ Х'-1-Ха -1-1. пример схемы умножения входного многочлена на многочлен Х~о+ Ха+ Ха+ 1 н деления получившегося произведения на многочлен Ха+ Ха+ Х4+Ха+ 1. В этом случае, для того чтобы закончить вычисление частного и остатка, после подачи на вход коэффициента при слагаемом нулевой степени приходится производить четыре сдвига с нулем на входе. 7.3. Вычисления в алгебрах многочленов и полях Галуа Схемы, описанные в предыдущих разделах, могут быть приспособлены для использования их при выполнении различных вычислений в алгебре многочленов по модулю д(Х), где д(Х) — заданный многочлен.
В регистре сдвига, состоящем из г ячеек памяти (фиг. 7.6), хранится г элементов поля, которые можно рассматривать как коэффициенты многочлена Ь(Х)=Ь,,Х" '+Ь, аХ" +...+Ьо степени г — 1 или меныпей. При сдвиге регистра на единицу вправо этот многочлен переходит в многочлен Ь' (Х) = Ь, Х" '+ Ь,,Х" а+... + Ь,Х + Ь Х вЂ” Ь,,(д, '(Х) — Х'). Последнее слагаемое появляется из-за наличия обратной связи. Это соотношение может быть записано в виде Ь'(Х) = ХЬ (Х) — Ь,,д„-'д (Х). (7.1) Таким образом, многочлены Ь'(Х) и ХЬ(Х) лежат в одном н том же классе вычетов по модулю д(Х), и поскольку степень много- члена Ь'(Х) меньше чем г; то многочлен Ь'(Х) должен совпадать с единственным миогочлепом в классе вычетов (ХЬ(Х)), степень которого меньше чем и. Это утверждение можно сформулировать также следующим образом.
Если через В обозначен класс вычетов, содержащий Х, то (Ь(Х)) = Ь(Б) и (ХЬ(Х)) = ЯЬ(5). Поэтому сдвиг регистра на единицу вправо соответствует умножению на 5, и содержимым Регистра сдвига оказываются всегда коэффициенты единственного многочлена из ЗЬ(5), степень которого меньше чем и. Фиг. 7.11. Схема для вычисления в поле Галуа. Используем для иллюстрации этих построений многочлен д(Х) = Х'+ Х+1 и поле из двух элементов. Это примитивный многочлен, и поэтому класс вычетов (Х) = а, где а — корень многочлена Х«+ Х+ 1, является примитивным элементом поля 6г"(2').
Соответствующий регистр сдвига показан на фиг. 7.11. Если в ячейку младшего разряда поместить единицу, а в остальные ячейки — нули, то последовательные сдвиги регистра дадут представление последовательных степеней элемента сл в форме, в какой они приведены в табл. 6.1. Заметим, что единице, сдвигаемой из ячейки старшего разряда, соответствует элемент х' и наличие обратной связи позволяет заменить его на равный ему элемент а+,1. Другой вариант подобной схемы приводится на фиг.7.12.Сдвиг влево соответствует делению на а, так что единица, выходящая из ячейки младшего разряда, дает значение а — ', заменяемое эквивалентным ему значением 1+ма. Таким образом, эта схема может использоваться для счета «назад», т. е.
для получения элементов поля Галуа, перечисляемых в обратном порядке. Умножение элементов поля можно производить, помещая один сомножитель в устройство А, изображенное на фиг. 7.11, а другой сомножитель в устройство В, изображенное на фиг. 7 12. В обоих устройствах производятся сдвиги до тех пор, пока в схеме В не появится единица. Тогда в схеме А появится произведение.
Деление осуществляется аналогичным способом. Умножение можно также проводить способом, аналогичным обычно используемому в цифровых вычислительных машинах'). Для этого регистр сдвига типа регистра, изображенного на фиг. 7.11, используется в качестве накопителя. Этот способ применим для элементов в любой алгебре многочленов по модулю многочлена д(Х), и в частности в полях Галуа. Для примера рассмотрим умножение сс'о и ат как элементов из поля 6г(24), представленного в табл. б.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
