Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 2.3. Мультипликативное обращениеРассмотрим теперь задачу определения мультипликативного обратного для элементов поля классов вычетов по модулю некоторого неприводимого двоичного многочлена
что эквивалентно равенству
Затем полагаем
Итерацию продолжаем до тех пор, пока не получим Прежде чем переходить к логическим устройствам, рассмотрим пример. Предположим, что 2.31. Вычисления.
(кликните для просмотра скана) Начиная с
Чтобы избежать запоминания коэффициентов 2.32. Вычисления. (см. скан)
Коэффициенты для 2.33. Вычисления. (см. скан)
(Вычисления 2.33 являются сокращением вычислений 2.31 и 2.32.) Здесь мы используем запись, при которой старшие коэффициенты 2.34. Алгоритм вычисления мультипликативного обратного. В начальном положении в верхнем регистре записаны неприводимый многочлен Если крайний левый элемент верхнего регистра равен нулю, то сдвигаем верхний регистр (вместе с его запятой) на одну позицию влево. Если крайний левый элемент нижнего регистра равен нулю, то сдвигаем нижний регистр (вместе с его запятой) на одну позицию влево. Если крайние левые элементы и верхнего и нижнего регистров равны единице и к четно, то прибавляем к верхнему регистру ту часть содержимого нижнего регистра, которая стоит слева от запятой, а к нижнему регистру ту часть содержимого верхнего регистра, которая стоит справа от запятой. Если крайние левые элементы и нижнего и верхнего регистров равны единице и к нечетно, то прибавляем к нижнему регистру ту часть содержимого верхнего регистра, которая стоит слева от запятой, а к содержимому верхнего регистра ту часть нижнего регистра, которая стоит справа от запятой. После установки запятых и осуществления сдвига четность к изменяется. Для четных к нижняя запятая находится слева от (или совпадает с) верхней запятой; для нечетных к нижняя запятая находится справа от (или совпадает с) верхней запятой. Вычисление заканчивается, когда обе запятые сдвигаются на левый конец своего регистра. Регистр, запятая в котором выдвинута совсем, содержит Описанный метод сводит итерацию алгоритма деления (многочленов) и алгоритма Евклида в единую процедуру, каждый шаг которой заключается лишь в сдвиге регистра или в сложении. Общее число сдвигов равно Практически эта процедура может быть реализована с помощью различных логических схем. Одним из возможных методов фиксации местоположения запятых является использование специального (маркерного) регистра, в котором всюду содержатся единицы, за исключением одного отрезка нулей, первая и последняя позиции которого соответствуют запятым. При выполнении операций сдвига символы маркерного регистра перемещаются путем выполнения логических операций И и ИЛИ над символом в данной позиции и в соседней справа в соответствии с четностью числа к и положением (верхний, нижний) сдвигаемого регистра. Так как единственный нуль содержится в маркерном регистре тогда и только тогда, когда в нем нет двух смежных нулей, то условие совпадения запятых может быть проверено с помощью операции ИЛИ, примененной к логическому произведению И символов в четных позициях маркерного регистра и логическому произведению И символов, стоящих в его нечетных позициях. Для иллюстрации приведем несколько первых шагов вычислений 2.33 с использованием маркерного регистра вместо запятых. 2.35. Вычисления.
Заметим, что окончание алгоритма отмечается появлением нуля в крайней левой позиции маркерного регистра. При использовании синхронной логики и двухтактовых часов для наиболее дешевой реализации данной процедуры требуется до Использование описанных в предыдущем разделе устройств позволяет сравнительно просто строить схемы, выполняющие правила алгоритма 2.34. На рис. 2.10 изображено устройство управления для такой схемы. Рис. 2.10 (см. скан) Схема управления для вычисления с помощью алгоритма Евклида мультипликативного обратного по модулю неприводимого двоичного многочлена. (Здесь
|
1 |
Оглавление
|