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

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

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

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

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

Если требуется найти сумму двух операндов по модулю $p$, то суммируются по модулю $p$ первые компоненты пар; для формирования второй компоненты пары результата этот результат преобразуется в индекс путем выборки значения из таблицы индексов (рис.1):

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

Если требуется найти произведение двух операндов по модулю $p$, то суммируются по модулю $p - 1$ вторые компоненты пар; для формирования первой компоненты пары результата этот результат преобразуется в антилогарифм (вычет) путем выборки значения из таблицы вычетов (рис.2):

Рис.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}$

Пример

Пусть надо выполнить сложение и умножение:

$sum = (a+b) \text{ mod } p$,

$prod = (a*b) \text{ mod } p$,

где 

$0 <= a < p$,

$0 <= b < p$,

$p$ – простое число, $\text{ mod } p$ – операция нахождения остатка по модулю.

Рассмотрим пример для модуля $p = 11$. Первообразный корень $w$ для этого значения модуля равен 2. А именно, возведение $w$ в степень 0, 1, … 9 дает неповторяющиеся результаты:

$(2^0) \text{ mod } 11 = 1 \text{ mod } 11 = 1$

$(2^1) \text{ mod } 11 = 2 \text{ mod } 11 = 2$

$(2^2) \text{ mod } 11 = 4 \text{ mod } 11 = 4$

$(2^3) \text{ mod } 11 = 8 \text{ mod } 11 = 8$

$(2^4) \text{ mod } 11 = 16 \text{ mod } 11 = 5$

$(2^5) \text{ mod } 11 = 32 \text{ mod } 11 = 10$

$(2^6) \text{ mod } 11 = 64 \text{ mod } 11 = 9$

$(2^7) \text{ mod } 11 = 128 \text{ mod } 11 = 7$

$(2^8) \text{ mod } 11 = 256 \text{ mod } 11 = 3$

$(2^9) \text{ mod } 11 = 512 \text{ mod } 11 = 6$

Для получения таблицы преобразования между обычным и индексным представлением расположим полученные пары значений в порядке возрастания. Для модуля $p = 11$ таблицы будет выглядеть следующим образом.

Таблица прямого преобразования:

Число	1	2	3	4	5	6	7	8	9	10
Индекс	0	1	8	2	4	9	7	3	6	5

Таблица обратного преобразования:

Индекс	0	1	2	3	4	5	6	7	8	9
Число	1	2	4	8	5	10	9	7	3	6

В качестве примера возьмем числа 8 и 6. Эти числа представляются парами <8,3> и <6,9>.

Найдем значение выражения (8+6) mod 11 обычным образом. Это первое число пары, представляющей результат сложения. (8+6) mod 11 = 14 mod 11 = 3. По таблице прямого преобразования находим, что числу 3 соответствует значение индекса 8. Это второе число пары. Итак.

$<sum, ind_2 {(sum)}> = <8,3> + <6,9> = <3,8>$.

Найдем значение выражения (8*6) mod 11 используя средства логарифметики. Числа 8 и 6 имеют соответствующие индексы 3 и 9 (см. таблицу прямого преобразования). Просуммировав эти индексы по модулю (11-1) = 10 получим результат (3+9) mod 10 = 12 mod 10 = 2. Это второе число пары, представляющей результат умножения. По таблице обратного преобразования находим для индекса 2 конечный результат, равный 4. Это первое число пары. Итак,

$<prod, ind_2 {(prod)}> = <8,3> * <6,9> = <4,2>$.

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

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

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

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

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

${|\tilde x|}_p = {\lambda}_p \cdot \delta \cdot ((p-1)-|x|_p) + {||x|_p|}_{p-1} \cdot {\hat \delta} \cdot ((p-1)-|x|_p)$,

где

${\delta}(u) = \begin{cases} 1, & \mbox{if } u=0, \\ 0, & \mbox{if } u\ne 0, \end{cases}$ - функция Кронекера ,

${\hat \delta}(u) = 1-{\delta}(u)$ - кофункция Кронекера.

Для представления второй компоненты пары операнда будем использовать дискретно-логарифметическое представление. Этот способ представления является эффективным при использовании небольших значений модулей порядка 8 бит, что является достаточным при проектировании большинства вычислительных устройств, предназначенных для решения специальных задач из области применения модулярной арифметики. Тем самым вторая компонента пары операндов будет иметь вид:

$log_w{|\tilde x|}_p = \delta({|\tilde x|}_p) \cdot {\lambda}_p + {\hat \delta}({|\tilde x|}_p) \cdot ind_w (x_p)$ , где

$ind_w|{\tilde x}|_p$ - индекс вычета $|{\tilde x}|_p$ по основанию $w$, т.е.

$|{\tilde x}|_p \ne 0 \Leftrightarrow |{w^{ind_w|{\tilde x}|_p}| = |{\tilde x}|_p}$ .

В этом случае полагается, что при $t$-битном простом числе $p$ константный символ ${\lambda}_p = 2^t-1$. Очевидно, что при любом простом $p$ ${\lambda}_p \notin Z_{p-1}$ .

Распишем, как в бимодульной арифметике будут выполняться арифметические операции.

Реализация мультипликативных операций останется без изменений:

если

$<|{\tilde x}|_{p}, log_w{|{\tilde x}|}_p>$, $<|{\tilde y}|_{p}, log_w{|{\tilde y}|}_p>$,

то

$(x \cdot y) \text{mod }p \longrightarrow < log^{-1} (|{log_w|{\tilde x}|_p + log_w|{\tilde y}|_p}|_{p-1}), log^{-1} (|{log_w|{\tilde x}|_p + log_w|{\tilde y}|_p}|_{p-1}) >$

т.е.

$(x \cdot y) \text{mod }p = \begin{cases} {\lambda}_p, & \mbox{if } {\delta(log_w|{\tilde x}|_p - {\lambda}_p})\vee {\delta(log_w|{\tilde y}|_p - {\lambda}_p}) = 1, \\ ||{log_w|{\tilde x}|_p + log_w|{\tilde y}|_p}|_{p-1}|_{p-1} ; \end{cases}$

Логика выполнения аддитивных операций усложнится за счет введения дополнительных логических функций, связанных с переходом к однородному представлению. Аддитивные операции выполняются согласно выражению:

если

$<|{\tilde x}|_{p}, log_w{|{\tilde x}|}_p>$, $<|{\tilde y}|_{p}, log_w{|{\tilde y}|}_p>$,

то

$(x + y) \text{mod }p \longrightarrow < |{\tilde x} + {\tilde y}|_{p-1} , log_w(|{\tilde x} + {\tilde y}|_{p-1}) >$,

т.е.

$(x + y) \text{mod }p = \begin{cases} p-2, & \mbox{if } {\tilde x} = {\tilde y} = p-1 , \\ {\lambda}_p, & \mbox{if } {\tilde x} + {\tilde y} = p-1 , \\ {\tilde x}-1, & \mbox{if } {\tilde x}\ne 0 , {\tilde y} = {\lambda}_p , \\ {\tilde y}-1, & \mbox{if } {\tilde y}\ne 0 , {\tilde x} = {\lambda}_p , \\ {\tilde x} + {\tilde y}, & \mbox{if } {\tilde x} + {\tilde y} < p-1 , \\ |{\tilde x} + {\tilde y}|_{p-1}-1, & \mbox{if } {\tilde x} + {\tilde y} > p-1 ; \end{cases}$

Тем самым, переход к однородному представлению операндов позволил выполнять аддитивные и мультипликативные операции на одном оборудовании, а именно на сумматоре по модулю $p-1$. Это положительно влияет и на требования к затратам по занимаемой площади и на контроль выполнения арифметических операций, при этом сохраняется требование однотипности используемого оборудования.

Ссылки

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