Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 2.4. УмножениеДля описания умножения в поле классов вычетов по модулю неприводимого двоичного многочлена Любой элемент У этого поля может быть однозначно представлен в виде многочлена от а степени 2.41. Умножение «регистра» на фиксированную константу. Рассмотрим прежде всего умножение элемента Выражая
Таким образом, умножение элемента
Равенство
Такая операция легко может быть реализована с помощью схемы, изображенной на рис. 2.11. Если требуется умножить записанный в регистре элемент
Такая схема приведена на рис. 2.12.
Рис. 2.11. Схема для умножения на
Рис. 2.12. Схема для умножения на а
Рис. 2.13. Схема для умножения на Аналогично, если произвольный элемент У, записанный в регистре, требуется улшожить на элемент
Такая схема изображена на рис. 2.13. Обозначим через случае умножение на а или а 1 может быть выполнено с помощью только одного сумматора с двумя входами. 2.42. Умножение двух «регистров». Рассмотрим произведение
Рис. 2.14. Схема для умножения
Рис. 2.15. Схема циклического сдвига V вправо. Каждая из
Рис. 2.16. Схема для прибавления кратных Даже при хорошем выборе неприводимого многочлена столь большое число сумматоров с двумя входами делает эту процедуру чрезвычайно дорогой для больших Пусть множитель Начальное состояние Более дешевым методом восстановления исходного состояния регистра множимого является
Такой метод умножения позволяет получать произведение за 2.43. Таблицы логарифмов. В качестве последнего метода выполнения операций умножения, деления, возведения в степень и извлечения корня рассмотрим использование таблиц логарифмов. Такие таблицы могут быть построены для ненулевых элементов в любом поле. Например, если а — корень неприводимого двоичного многочлена
Рис. 2.17. Регистр сдвига с обратной связью для умножения на а. Использование подобных таблиц сильно упрощает ручное вычисление произведения, частного, степеней и извлечение корней для элементов поля. Например, рассмотрим произведение
частное
степень
и корень
так как В общем случае построение таких таблиц возможно тогда и только тогда, когда каждый ненулевой элемент поля является степенью одного, так называемого примитивного элемента. В теореме 4.24 мы докажем, что каждое конечное поле содержит такой элемент. Следовательно, подобные таблицы логарифмов и антилогарифмов могут быть построены для любого конечного поля. Хотя таблицы такого рода являются чрезвычайно полезными при ручных вычислениях, их ценность для машинного счета весьма сомнительна. Действительно, одним очевидным методом реализации машинных вычислений с помощью таких таблиц является использование двух устройств постоянной памяти, содержащих по как Если известен некоторый метод, позволяющий легко вычислять логарифмы элементов поля (основанный не на просмотре таблиц, а на операциях над координатами двоичных представлений элементов поля в виде многочленов от а), то логарифмический подход может составить основу экономной реализации операций умножения и деления. В общем случае, однако, не известно никаких простых методов непосредственного вычисления логарифмов. Некоторые очень частные результаты в этом направлении содержатся в задачах 4.3 и 4.4. 2.44. Квадраты и квадратные корни. Другим частным случаем умножения, заслуживающим отдельного рассмотрения, является умножение элемента поля, записанного в регистре
так что преобразование
Это матричное умножение может быть выполнено с помощью схемы, приведенной на рис. 2.18. Обратная матрица имеет вид
Очевидно, что извлечение из элементов поля квадратного корня может быть осуществлено путем умножения на эту матрицу.
Рис. 2.18. Схема для вычисления
Рис. 2.19. Схема для вычисления Таким образом, преобразование
|
1 |
Оглавление
|