Описание работы пирамидального прямого преобразователя

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

Содержание

Принципы построения прямых преобразователей

Пусть нам необходимо выполнить прямое преобразование по модулю p некоторого двоичного числа X разрядностью N. Искомый остаток записывается следующим образом: |X|_p. В двоичной форме число X представляется как: X = 2^0 \cdot x_0 + 2^1 \cdot x_1 + ... + 2^{N-1} \cdot x_{N-1}, где x_i - двоичные разряды числа. Таким образом, необходимо вычислить:

|X|_p = |2^0 \cdot x_0 + 2^1 \cdot x_1 + ... + 2^{N-1} \cdot x_{N-1}|_p

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

|a*b|_p = ||a|_p*|b|_p|_p

Это свойство позволяет вносить знак модуля для любых слагаемых или групп слагаемых. Например, как в описанном методе универсального прямого преобразователя, можно обрабатывать блоки по одному биту:

|X|_p = ||2^0 \cdot x_0|_p + |2^1 \cdot x_1|_p + ... + |2^{N-1} \cdot x_{N-1}|_p|_p

Fig1 1bit reduction.jpg

Можно обрабатывать группами по два бита:

|X|_p = ||2^0 \cdot x_0 + 2^1 \cdot x_1 |_p + |2^2|_p \cdot |2^0 \cdot x_2 + 2^1 \cdot x_3 |_p + ...|_p

Fig2 2bit reduction.jpg

Также различными группами исследователей предлагается разбивать по блокам длины равной разрядности модуля. Следует отметить, что эффективность способа разбиения может отличаться для разных входных битностей, разных оснований, а также различных используемых САПР. Более того, являясь задачей прямого преобразования некоторого числа меньшей размерности блок финальной редукции может быть также реализован с произвольным разбиением.

Пирамидальный прямой преобразователь

Базовым разбиением пирамидального преобразователя является разбиение входного числа на два блока по N/2 бит. Не ограничивая общности рассуждений примем N = 2^k бит – разрядность равна некоторой степени двойки. После первого разбиения получаем:

|X|_p= ||L|_p + |M|_p \cdot |2^{(N/2)}|_p|_p

где L и M – младшие и старшие N/2 бит числа X соответственно.

Дальше проводится второе разбиение чисел L и M по такому же принципу:

|L|_p= ||L_2|_p + |M_2|_p \cdot |2^{(N/4)}|_p|_p

|M|_p= ||L_3|_p + |M_3|_p \cdot |2^{(N/4)}|_p|_p

Далее процедура повторяется для L_2, L_3, M_2, M_3 и далее до тех пор пока L_i, M_i не станут соизмеримыми с разрядностью модуля для тривиального нахождения их остатка. Структура пирамидального прямого преобразователя для восьмибитного входного числа и двухбитного модуля выглядит следующим образом:

Fig3 pyramid reduction.jpg

Численный пример

Поэтапно рассмотрим принцип работы пирамидального прямого преобразователя для числа 10010101_2 = 149 и p = 3.

  • Первое разбиение:

Представим число 149 = 10012 ∙ 24 + 01012 = 9∙24 + 5

|9 \cdot 2^4 + 5|_3 = ||9|_3 \cdot |2^4 |_3  + |5|_3|_3=||9|_3 \cdot 1 + |5|_3|_3

  • Второе разбиение:

Разбиваем числа 9 (1001_2) и 5 (0101_2) на двухбитные числа:

9 = 10012 = 2∙ 22 + 1

5 = 10012 = 1∙ 22 + 1

|9|_3 = ||2|_3 \cdot |2^2 |_3 + |1|_3|_3 = ||2|_3 \cdot 1 + |1|_3|_3

|5|_3 = ||1|_3 \cdot |2^2 |_3 + |1|_3|_3 = ||1|_3 \cdot 1 + |1|_3|_3

  • Тривиальное преобразование:

Оставшиеся двухбитные числа преобразуются с использованием таблиц перекодировок. Конечная формула выглядит следующим образом:

|149|_3=|(||2|_3 \cdot 1 + |1|_3 |_3 \cdot 1)  + (||1|_3 \cdot 1 + |1|_3 |_3 )|_3

Для данного примера все константы |2^i |_3 получились равными единице, что в общем случае не всегда так. Данный факт произошел благодаря тому что использовался модуль специального вида. Обратившись к рисунку, нетрудно установить, что для нашего примера функции Ci выглядят следующим образом:

C1 = |x|_3

C2 = |1 \cdot y + x|_3

C3 = |1 \cdot y + x|_3


Преимущества и недостатки метода:

В сравнении с традиционными методами прямого преобразования данный метод обладает некоторыми особенностями, которые обуславливают его достоинства и недостатки. Основным отличием является его высокая регулярность. Под этим подразумевается большое количество однотипных блоков. Это с одной стороны позволяет строить высокоскоростные устройства с высоким уровнем параллелизма. Для этого достаточно каждый уровень отделить регистрами, увеличивая тактовую частоту преобразователя. С другой стороны появляется возможность существенно экономить площадь устройства реализуя все базовые операции на одном вычислительном блоке. Однако, основным недостатком метода является низкая его эффективность в комбинационном варианте. Результаты синтеза традиционных и пирамидальных преобразователей представлены в таблице:

Fig4 experiments.jpg

Генератор Verilog


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

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