Версия 14:24, 28 мая 2014

Аддитивный характер вычислений в кольце вычетов $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 соответствует специальный символ $\lambda$ , который обладает свойством $\lambda+i=i+\lambda$ для любого для любого индекса $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$ .

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

${|\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)$ - кофункция Кронекера.

Ссылки

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

@@ Строка 7: / Строка 7: @@
 = Кодовая конструкция проф. Д.А. Поспелова =
-Для того, чтобы сбалансировать выполнение модульных операций Д.А. Поспелов ввел представление исходных операндов в виде пар  <math>  <|x|_p, ind_w|x|_p> </math>>, где  <math> |x|_p </math> есть вычет <math> x </math> по модулю <math> p </math>  ,  <math>  i = ind_w|x|_p </math> - соответствующий вычету  <math> |x|_p </math> индекс, при этом условно считается, что вычету 0 соответствует специальный символ λ, который обладает свойством λ+i=i+λ для любого для любого индекса <math> 0\le i\le p-2 </math> . Таким образом, все операции поля выполняются над парами: если требуется найти сумму двух операндов по модулю <math> p </math>, то суммируются по модулю <math> p </math> первые компоненты пар; для формирования второй компоненты пары результата этот результат преобразуется в индекс путем выборки значения из таблицы индексов (рис.1). Если требуется найти произведение двух операндов по модулю <math> p </math>, то суммируются по модулю <math> p - 1 </math> вторые компоненты пар; для формирования первой компоненты пары результата этот результат преобразуется в антилогарифм (вычет) путем выборки значения из таблицы вычетов (рис.2):
+Для того, чтобы сбалансировать выполнение модульных операций Д.А. Поспелов ввел представление исходных операндов в виде пар  <math>  <|x|_p, ind_w|x|_p> </math>>, где  <math> |x|_p </math> есть вычет <math> x </math> по модулю <math> p </math>  ,  <math>  i = ind_w|x|_p </math> - соответствующий вычету  <math> |x|_p </math> индекс, при этом условно считается, что вычету 0 соответствует специальный символ <math> \lambda </math>, который обладает свойством <math> \lambda+i=i+\lambda </math> для любого для любого индекса <math> 0\le i\le p-2 </math> . Таким образом, все операции поля выполняются над парами: если требуется найти сумму двух операндов по модулю <math> p </math>, то суммируются по модулю <math> p </math> первые компоненты пар; для формирования второй компоненты пары результата этот результат преобразуется в индекс путем выборки значения из таблицы индексов (рис.1). Если требуется найти произведение двух операндов по модулю <math> p </math>, то суммируются по модулю <math> p - 1 </math> вторые компоненты пар; для формирования первой компоненты пары результата этот результат преобразуется в антилогарифм (вычет) путем выборки значения из таблицы вычетов (рис.2):
@@ Строка 36: / Строка 36: @@
 Введем понятие модифицированного вычета по модулю:
+<math>  {|\tilde x|}_p = {\lambda}_p \cdot \delta \cdot ((p-1)-|x|_p) + {||x|_p|}_{p-1} \cdot {\hat \delta} \cdot ((p-1)-|x|_p)</math>
+где
+:<math> {\delta}(u) = \begin{cases}
+, & \mbox{if } u=0, \\
+, & \mbox{if } u\ne 0,
+\end{cases}
+</math>
+:- функция Кронекера
+<math> {\hat \delta}(u) = 1-{\delta}(u) </math> - кофункция Кронекера.

Бимодульная модулярная арифметика — различия между версиями

Версия 14:24, 28 мая 2014

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

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

Ссылки

Навигация

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

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты