Бимодульная модулярная арифметика
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
Аддитивный характер вычислений в кольце вычетов <math> Z_p </math> порождает дополнительные расходы на выполнение арифметических операций. Это обусловлено тем, что результат выполненной операции может выйти за диапазон <math> Z_p </math>, тогда требуется корректировка результата, т.е. взятие результата выполненной операции по модулю. Мультипликативная операция над остатками x, y mod p более трудоемка, поэтому наиболее эффективным способом избежать прямой реализации мультипликативной операции является переход к индексам вычетов по основанию первообразного корня, однозначно связанных с данным модулярным кодом. | Аддитивный характер вычислений в кольце вычетов <math> Z_p </math> порождает дополнительные расходы на выполнение арифметических операций. Это обусловлено тем, что результат выполненной операции может выйти за диапазон <math> Z_p </math>, тогда требуется корректировка результата, т.е. взятие результата выполненной операции по модулю. Мультипликативная операция над остатками x, y mod p более трудоемка, поэтому наиболее эффективным способом избежать прямой реализации мультипликативной операции является переход к индексам вычетов по основанию первообразного корня, однозначно связанных с данным модулярным кодом. | ||
| − | В случае индексной арифметики операция «+» выполняется за один такт модульного суммирования, а операция «*» за такт модульного суммирования и два такта табличной операции. | + | В случае индексной арифметики операция «+» выполняется за один такт модульного суммирования, а операция «*» за такт модульного суммирования и два такта табличной операции. |
= Кодовая конструкция проф. Д.А. Поспелова = | = Кодовая конструкция проф. Д.А. Поспелова = | ||
| + | |||
| + | Для того, чтобы сбалансировать выполнение модульных операций Д.А. Поспелов ввел представление исходных операндов в виде пар <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<=i<=p-2 </math> . Таким образом, все операции поля выполняются над парами: если требуется найти сумму двух операндов по модулю <math> p </math>, то суммируются по модулю <math> p </math> первые компоненты пар; для формирования второй компоненты пары результата этот результат преобразуется в индекс путем выборки значения из таблицы индексов (рис.1). Если требуется найти произведение двух операндов по модулю <math> p </math>, то суммируются по модулю <math> p - 1 </math> вторые компоненты пар; для формирования первой компоненты пары результата этот результат преобразуется в антилогарифм (вычет) путем выборки значения из таблицы вычетов (рис.2): | ||
| + | |||
[[изображение:BimodModArith_fig1_add.PNG|200px|frame|center|Рис.1. Структурная схема операции сложения]] | [[изображение:BimodModArith_fig1_add.PNG|200px|frame|center|Рис.1. Структурная схема операции сложения]] | ||
[[изображение:BimodModArith_fig2_mult.PNG|200px|frame|center|Рис.2. Структурная схема операции умножения]] | [[изображение:BimodModArith_fig2_mult.PNG|200px|frame|center|Рис.2. Структурная схема операции умножения]] | ||
| + | |||
| + | |||
| + | Арифметику, построенную на парном представлении операндов, будем называть бимодульной арифметикой поля <math> GF(p)</math>. | ||
| + | Таким образом, операции сложения и умножения сведены к операциям сложения по модулю <math> p </math> и модулю <math> p-1 </math>, соответственно, и одной табличной операции выбора второй компоненты пары результата. Такое решение позволяет сократить время выполнения мультипликативной операции на один такт табличной операции и площадь на хранение двух таблиц преобразования в индексы, размерность каждой таблицы <math>2(p-1)</math>. При этом, Д.А. Поспелов утверждает [1, стр. 296], что, несмотря на то, что логика операции умножения по модулю <math> p </math> стала более сложной, чем в обычной системе кода в остатках, выигрыш состоит в «однотипности оборудования для производства операций сложения и умножения». Данное утверждение справедливо в общем случае, когда сумматоры по модулям <math> p </math> и <math> (p-1) </math> проектируются по методу прямой логической реализации с использованием двоичных функциональных блоков. В этом случае суммирование по модулю <math> m </math> для двух операндов <math> x </math> и <math> y </math>, находящихся в диапазоне <math>{0, 1,\ldots, m-1}</math>, выполняется по следующей формуле: | ||
| + | |||
= Модифицированная кодовая конструкция = | = Модифицированная кодовая конструкция = | ||
| + | |||
| + | = Ссылки = | ||
| + | |||
| + | * [1] Поспелов Д.А. Арифметические основы вычислительных машин дискретного действия. М.: Высш. шк., 1970. | ||
Версия 16:23, 28 мая 2014
Аддитивный характер вычислений в кольце вычетов 
порождает дополнительные расходы на выполнение арифметических операций. Это обусловлено тем, что результат выполненной операции может выйти за диапазон , тогда требуется корректировка результата, т.е. взятие результата выполненной операции по модулю. Мультипликативная операция над остатками x, y mod p более трудоемка, поэтому наиболее эффективным способом избежать прямой реализации мультипликативной операции является переход к индексам вычетов по основанию первообразного корня, однозначно связанных с данным модулярным кодом.
В случае индексной арифметики операция «+» выполняется за один такт модульного суммирования, а операция «*» за такт модульного суммирования и два такта табличной операции.
Кодовая конструкция проф. Д.А. Поспелова
Для того, чтобы сбалансировать выполнение модульных операций Д.А. Поспелов ввел представление исходных операндов в виде пар 
>, где 
есть вычет 
по модулю 
, 
- соответствующий вычету индекс, при этом условно считается, что вычету 0 соответствует специальный символ λ, который обладает свойством λ+i=i+λ для любого для любого индекса 
. Таким образом, все операции поля выполняются над парами: если требуется найти сумму двух операндов по модулю , то суммируются по модулю первые компоненты пар; для формирования второй компоненты пары результата этот результат преобразуется в индекс путем выборки значения из таблицы индексов (рис.1). Если требуется найти произведение двух операндов по модулю , то суммируются по модулю 
вторые компоненты пар; для формирования первой компоненты пары результата этот результат преобразуется в антилогарифм (вычет) путем выборки значения из таблицы вычетов (рис.2):
Арифметику, построенную на парном представлении операндов, будем называть бимодульной арифметикой поля 
.
Таким образом, операции сложения и умножения сведены к операциям сложения по модулю и модулю , соответственно, и одной табличной операции выбора второй компоненты пары результата. Такое решение позволяет сократить время выполнения мультипликативной операции на один такт табличной операции и площадь на хранение двух таблиц преобразования в индексы, размерность каждой таблицы 
. При этом, Д.А. Поспелов утверждает [1, стр. 296], что, несмотря на то, что логика операции умножения по модулю стала более сложной, чем в обычной системе кода в остатках, выигрыш состоит в «однотипности оборудования для производства операций сложения и умножения». Данное утверждение справедливо в общем случае, когда сумматоры по модулям и 
проектируются по методу прямой логической реализации с использованием двоичных функциональных блоков. В этом случае суммирование по модулю 
для двух операндов и 
, находящихся в диапазоне 
, выполняется по следующей формуле:
Модифицированная кодовая конструкция
Ссылки
- [1] Поспелов Д.А. Арифметические основы вычислительных машин дискретного действия. М.: Высш. шк., 1970.
