Бимодульная модулярная арифметика

Материал из Модулярная арифметики
Перейти к: навигация, поиск

Аддитивный характер вычислений в кольце вычетов  Z_p порождает дополнительные расходы на выполнение арифметических операций. Это обусловлено тем, что результат выполненной операции может выйти за диапазон  Z_p , тогда требуется корректировка результата, т.е. взятие результата выполненной операции по модулю. Мультипликативная операция над остатками x, y mod p более трудоемка, поэтому наиболее эффективным способом избежать прямой реализации мультипликативной операции является переход к индексам вычетов по основанию первообразного корня, однозначно связанных с данным модулярным кодом.

В случае индексной арифметики операция «+» выполняется за один такт модульного суммирования, а операция «*» за такт модульного суммирования и два такта табличной операции.


Кодовая конструкция проф. Д.А. Поспелова

Для того, чтобы сбалансировать выполнение модульных операций Д.А. Поспелов ввел представление исходных операндов в виде пар   <|x|_p, ind_w|x|_p> >, где  |x|_p есть вычет  x по модулю  p ,   i = ind_w|x|_p - соответствующий вычету  |x|_p индекс, при этом условно считается, что вычету 0 соответствует специальный символ λ, который обладает свойством λ+i=i+λ для любого для любого индекса  0\le i\le p-2 . Таким образом, все операции поля выполняются над парами: если требуется найти сумму двух операндов по модулю  p , то суммируются по модулю  p первые компоненты пар; для формирования второй компоненты пары результата этот результат преобразуется в индекс путем выборки значения из таблицы индексов (рис.1). Если требуется найти произведение двух операндов по модулю  p , то суммируются по модулю  p - 1 вторые компоненты пар; для формирования первой компоненты пары результата этот результат преобразуется в антилогарифм (вычет) путем выборки значения из таблицы вычетов (рис.2):


Рис.1. Структурная схема операции сложения
Рис.2. Структурная схема операции умножения


Арифметику, построенную на парном представлении операндов, будем называть бимодульной арифметикой поля  GF(p). Таким образом, операции сложения и умножения сведены к операциям сложения по модулю  p и модулю  p-1 , соответственно, и одной табличной операции выбора второй компоненты пары результата. Такое решение позволяет сократить время выполнения мультипликативной операции на один такт табличной операции и площадь на хранение двух таблиц преобразования в индексы, размерность каждой таблицы 2(p-1). При этом, Д.А. Поспелов утверждает [1, стр. 296], что, несмотря на то, что логика операции умножения по модулю  p стала более сложной, чем в обычной системе кода в остатках, выигрыш состоит в «однотипности оборудования для производства операций сложения и умножения». Данное утверждение справедливо в общем случае, когда сумматоры по модулям  p и  (p-1) проектируются по методу прямой логической реализации с использованием двоичных функциональных блоков. В этом случае суммирование по модулю  m для двух операндов  x и  y , находящихся в диапазоне {0, 1,\ldots, m-1}, выполняется по следующей формуле:

{|x+y|}_m = \begin{cases}
  x+y, & \mbox{if } (x+y) < m ; \\
  x+y-m,  & \mbox{if } (x+y) \ge m. 
\end{cases}


Модифицированная кодовая конструкция

Рассмотренный метод построения сумматоров по модулю, во-первых, позволяет в полной мере использовать современные наработки в области проектирования двоичных устройств, во-вторых, предоставляет большую гибкость при реализации каждого компонента в составе всего вычислительного блока в зависимости от требований к занимаемой площади и быстродействию. В-третьих, метод универсален, т.е. независим от специфики используемого базового модуля m.

Однако в настоящее время все большую популярность завоевывают гибридные методы построения базовых арифметических узлов модулярной арифметики. Такие методы представляют собой комбинацию методов прямой логической реализации и методов на основе таблиц состояний. Использование гибридных методов обеспечивает компромисс между быстродействием и затратами на занимаемую площадь для некоторых значений модулей. В случае же реализации арифметики в кодах Д.А. Поспелова требуется оценивать проектирование сумматоров не только относительно базового модуля  p , но и модуля  p-1 , иначе теряется основная идея данного кодирования, а именно, однотипность оборудования.

Следующая модификация кода Д.А. Поспелова развивает его идею однотипности. Развитие идеи однотипности состоит в том, чтобы аддитивные и мультипликативные операции модульной арифметики выполнялись не только аппаратно однотипно, но и однотипно в кодовом представлении операндов. Это достигается путем перехода от предствления компонент пар операндов по модулям  p , и  p-1 к однородному представлению по модулю  p-1 .


Введем понятие модифицированного вычета по модулю:


Ссылки

  • [1] Поспелов Д.А. Арифметические основы вычислительных машин дискретного действия. М.: Высш. шк., 1970.

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация