Бимодульная модулярная арифметика - История изменений

Isaeva в 13:57, 18 июня 2014

2014-06-18T13:57:09Z

Isaeva в 13:44, 18 июня 2014

2014-06-18T13:44:09Z

Isaeva в 09:40, 18 июня 2014

2014-06-18T09:40:11Z

Isaeva в 08:15, 18 июня 2014

2014-06-18T08:15:43Z

Isaeva в 09:10, 10 июня 2014

2014-06-10T09:10:55Z

Isaeva в 14:07, 4 июня 2014

2014-06-04T14:07:01Z

Isaeva в 13:48, 4 июня 2014

2014-06-04T13:48:36Z

Isaeva в 13:46, 4 июня 2014

2014-06-04T13:46:19Z

Isaeva в 12:21, 4 июня 2014

2014-06-04T12:21:46Z

Isaeva в 11:06, 4 июня 2014

2014-06-04T11:06:19Z

@@ Строка 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> индекс по основанию <math> w </math>, при этом условно считается, что вычету 0 соответствует специальный символ <math> \lambda </math> (этот элемент, так называемая "сингулярность", не является элементом кольца Z_p, может быть обозначен <math> inf </math>), который обладает свойством <math> \lambda+i=i+\lambda </math> для любого для любого индекса <math> 0\le i\le p-2 </math>. Таким образом, все операции поля выполняются над парами.
+Д.А. Поспелов ввел представление исходных операндов в виде пар <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> индекс по основанию <math> w </math> (см. [[Модулярная логарифметика]]), при этом условно считается, что вычету 0 соответствует специальный символ <math> \lambda </math> (обозначается также <math> inf </math>), который обладает свойством <math> \lambda+i=i+\lambda </math> для любого для любого индекса <math> 0\le i\le p-2 </math>. Таким образом, все операции поля выполняются над парами чисел.
 Если требуется найти сумму двух операндов по модулю <math> p </math>, то суммируются по модулю <math> p </math> первые компоненты пар; для формирования второй компоненты пары результата этот результат преобразуется в индекс путем выборки значения из таблицы индексов (рис.1):

@@ Строка 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 соответствует специальный символ <math> \lambda </math>, который обладает свойством <math> \lambda+i=i+\lambda </math> для любого для любого индекса <math> 0\le i\le p-2 </math>. Таким образом, все операции поля выполняются над парами.
+Д.А. Поспелов ввел представление исходных операндов в виде пар  <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> индекс по основанию <math> w </math>, при этом условно считается, что вычету 0 соответствует специальный символ <math> \lambda </math> (этот элемент, так называемая "сингулярность", не является элементом кольца Z_p, может быть обозначен <math> inf </math>), который обладает свойством <math> \lambda+i=i+\lambda </math> для любого для любого индекса <math> 0\le i\le p-2 </math>. Таким образом, все операции поля выполняются над парами.
 Если требуется найти сумму двух операндов по модулю <math> p </math>, то суммируются по модулю <math> p </math> первые компоненты пар; для формирования второй компоненты пары результата этот результат преобразуется в индекс путем выборки значения из таблицы индексов (рис.1):
@@ Строка 84: / Строка 84: @@
 Найдем значение выражения (8+6) mod 11 обычным образом. Это первое число пары, представляющей результат сложения. (8+6) mod 11 = 14 mod 11 = 3. По таблице прямого преобразования находим, что числу 3 соответствует значение индекса 8. Это второе число пары. Итак.
-:<math> sum = <8,3> + <6,9> = <3,8> </math>.
+:<math> <sum, ind_2 {(sum)}> = <8,3> + <6,9> = <3,8> </math>.
 Найдем значение выражения (8*6) mod 11 используя средства логарифметики. Числа 8 и 6 имеют соответствующие индексы 3 и 9 (см. таблицу прямого преобразования). Просуммировав эти индексы по модулю (11-1) = 10 получим результат (3+9) mod 10 = 12 mod 10 = 2. Это второе число пары, представляющей результат умножения. По таблице обратного преобразования находим для индекса 2 конечный результат, равный 4. Это первое число пары. Итак,
-:<math> prod = <8,3> * <6,9> = <4,2> </math>.
+:<math> <prod, ind_2 {(prod)}> = <8,3> * <6,9> = <4,2> </math>.

← Предыдущая		Версия 09:40, 18 июня 2014
Строка 33:		Строка 33:

	== Пример ==		== Пример ==
		+
		+	Пусть надо выполнить сложение и умножение:
		+	:<math> sum = (a+b) \text{ mod } p </math>,
		+	:<math> prod = (a*b) \text{ mod } p </math>,
		+	где
		+	:<math> 0 <= a < p </math>,
		+	:<math> 0 <= b < p </math>,
		+	<math> p </math> – простое число,
		+	<math> \text{ mod } p </math> – операция нахождения остатка по модулю.
		+
		+
		+	Рассмотрим пример для модуля <math> p = 11 </math>. Первообразный корень <math> w </math> для этого значения модуля равен 2. А именно, возведение <math> w </math> в степень 0, 1, … 9 дает неповторяющиеся результаты:
		+
		+	:<math> (2^0) \text{ mod } 11 = 1 \text{ mod } 11 = 1 </math>
		+	:<math> (2^1) \text{ mod } 11 = 2 \text{ mod } 11 = 2 </math>
		+	:<math> (2^2) \text{ mod } 11 = 4 \text{ mod } 11 = 4 </math>
		+	:<math> (2^3) \text{ mod } 11 = 8 \text{ mod } 11 = 8 </math>
		+	:<math> (2^4) \text{ mod } 11 = 16 \text{ mod } 11 = 5 </math>
		+	:<math> (2^5) \text{ mod } 11 = 32 \text{ mod } 11 = 10 </math>
		+	:<math> (2^6) \text{ mod } 11 = 64 \text{ mod } 11 = 9 </math>
		+	:<math> (2^7) \text{ mod } 11 = 128 \text{ mod } 11 = 7 </math>
		+	:<math> (2^8) \text{ mod } 11 = 256 \text{ mod } 11 = 3 </math>
		+	:<math> (2^9) \text{ mod } 11 = 512 \text{ mod } 11 = 6 </math>
		+
		+
		+	Для получения таблицы преобразования между обычным и индексным представлением расположим полученные пары значений в порядке возрастания. Для модуля <math> p = 11 </math> таблицы будет выглядеть следующим образом.
		+
		+
		+	Таблица прямого преобразования:
		+
		+	{\| class="wikitable"
		+	\|-
		+	\| Число \|\|1\|\|2\|\|3\|\|4\|\|5\|\|6\|\|7\|\|8\|\|9\|\|10
		+	\|-
		+	\| Индекс \|\|0\|\|1\|\|8\|\|2\|\|4\|\|9\|\|7\|\|3\|\|6\|\|5
		+	\|}
		+
		+
		+	Таблица обратного преобразования:
		+
		+	{\| class="wikitable"
		+	\|-
		+	\| Индекс \|\|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. Это второе число пары. Итак.
		+	:<math> sum = <8,3> + <6,9> = <3,8> </math>.
		+
		+	Найдем значение выражения (8*6) mod 11 используя средства логарифметики. Числа 8 и 6 имеют соответствующие индексы 3 и 9 (см. таблицу прямого преобразования). Просуммировав эти индексы по модулю (11-1) = 10 получим результат (3+9) mod 10 = 12 mod 10 = 2. Это второе число пары, представляющей результат умножения. По таблице обратного преобразования находим для индекса 2 конечный результат, равный 4. Это первое число пары. Итак,
		+	:<math> prod = <8,3> * <6,9> = <4,2> </math>.

@@ Строка 5: / Строка 5: @@
-= Кодовая конструкция проф. Д.А. Поспелова =
+== Кодовая конструкция проф. Д.А. Поспелова ==
 Д.А. Поспелов ввел представление исходных операндов в виде пар  <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>. Таким образом, все операции поля выполняются над парами.
@@ Строка 32: / Строка 32: @@
-= Модифицированная кодовая конструкция =
+== Пример ==
 Рассмотренный метод построения сумматоров по модулю, во-первых, позволяет в полной мере использовать современные наработки в области проектирования двоичных устройств, во-вторых, предоставляет большую гибкость при реализации каждого компонента в составе всего вычислительного блока в зависимости от требований к занимаемой площади и быстродействию. В-третьих, метод универсален, т.е. независим от специфики используемого базового модуля m.
@@ Строка 117: / Строка 120: @@
-= Ссылки =
+== Ссылки ==
 * [1] Поспелов Д.А. Арифметические основы вычислительных машин дискретного действия. М.: Высш. шк., 1970.

@@ Строка 11: / Строка 11: @@
 Если требуется найти сумму двух операндов по модулю <math> p </math>, то суммируются по модулю <math> p </math> первые компоненты пар; для формирования второй компоненты пары результата этот результат преобразуется в индекс путем выборки значения из таблицы индексов (рис.1):
-[[изображение:BimodModArith_fig1_add.PNG|200px|frame|left|Рис.1. Структурная схема операции сложения]]
+[[изображение:BimodModArith_fig1_add.JPG|200px|frame|left|Рис.1. Структурная схема операции сложения]]
 <br style="clear:both" />
@@ Строка 17: / Строка 17: @@
 Если требуется найти произведение двух операндов по модулю <math> p </math>, то суммируются по модулю <math> p - 1 </math> вторые компоненты пар; для формирования первой компоненты пары результата этот результат преобразуется в антилогарифм (вычет) путем выборки значения из таблицы вычетов (рис.2):
-[[изображение:BimodModArith_fig2_mult.PNG|200px|frame|left|Рис.2. Структурная схема операции умножения]]
+[[изображение:BimodModArith_fig2_mult.JPG|200px|frame|left|Рис.2. Структурная схема операции умножения]]
 <br style="clear:both" />

@@ Строка 66: / Строка 66: @@
 :<math> |{\tilde x}|_p \ne 0 \Leftrightarrow |{w^{ind_w|{\tilde x}|_p}| = |{\tilde x}|_p} </math> .
-В этом случае полагается, что при t-битном простом числе <math> p </math> константный символ <math> {\lambda}_p = 2^t-1 </math>. Очевидно, что при любом простом <math> p </math> <math> {\lambda}_p \notin Z_{p-1} </math> .
+В этом случае полагается, что при <math> t </math>-битном простом числе <math> p </math> константный символ <math> {\lambda}_p = 2^t-1 </math>. Очевидно, что при любом простом <math> p </math> <math> {\lambda}_p \notin Z_{p-1} </math> .
 Распишем, как в бимодульной арифметике будут выполняться арифметические операции.

← Предыдущая		Версия 13:48, 4 июня 2014
Строка 39:		Строка 39:

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

@@ Строка 2: / Строка 2: @@
 Аддитивный характер вычислений в кольце вычетов <math> Z_p </math> порождает дополнительные расходы на выполнение арифметических операций. Это обусловлено тем, что результат выполненной операции может выйти за диапазон <math> Z_p </math>, тогда требуется корректировка результата, т.е. взятие результата выполненной операции по модулю. Мультипликативная операция над остатками <math> x, y \text{ mod }p </math> более трудоемка, поэтому наиболее эффективным способом избежать прямой реализации мультипликативной операции является переход к индексам вычетов по основанию первообразного корня, однозначно связанных с данным модулярным кодом.
-В случае индексной арифметики операция «+» выполняется за один такт модульного суммирования, а операция «*» за такт модульного суммирования и два такта табличной операции.
+В случае индексной арифметики операция «+» выполняется за один такт модульного суммирования, а операция «*» за такт модульного суммирования и два такта табличной операции. Бимодульная модулярная арифметика направлена на то, чтобы сбалансировать выполнение модульных операций.
 = Кодовая конструкция проф. Д.А. Поспелова =
-Для того, чтобы сбалансировать выполнение модульных операций Д.А. Поспелов ввел представление исходных операндов в виде пар  <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>  <|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):

@@ Строка 1: / Строка 1: @@
-Аддитивный характер вычислений в кольце вычетов <math> Z_p </math> порождает дополнительные расходы на выполнение арифметических операций. Это обусловлено тем, что результат выполненной операции может выйти за диапазон <math> Z_p </math>, тогда требуется корректировка результата, т.е. взятие результата выполненной операции по модулю. Мультипликативная операция над остатками x, y mod p более трудоемка, поэтому наиболее эффективным способом избежать прямой реализации мультипликативной операции является переход к индексам вычетов по основанию первообразного корня, однозначно связанных с данным модулярным кодом.
+Аддитивный характер вычислений в кольце вычетов <math> Z_p </math> порождает дополнительные расходы на выполнение арифметических операций. Это обусловлено тем, что результат выполненной операции может выйти за диапазон <math> Z_p </math>, тогда требуется корректировка результата, т.е. взятие результата выполненной операции по модулю. Мультипликативная операция над остатками <math> x, y \text{ mod }p </math> более трудоемка, поэтому наиболее эффективным способом избежать прямой реализации мультипликативной операции является переход к индексам вычетов по основанию первообразного корня, однозначно связанных с данным модулярным кодом.
 В случае индексной арифметики операция «+» выполняется за один такт модульного суммирования, а операция «*» за такт модульного суммирования и два такта табличной операции.
@@ Строка 22: / Строка 22: @@
 Арифметику, построенную на парном представлении операндов, будем называть бимодульной арифметикой поля <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>, выполняется по следующей формуле:
@@ Строка 113: / Строка 114: @@
-Тем самым, переход к однородному представлению операндов позволил выполнять аддитивные и мультипликативные операции на одном оборудовании, а именно на сумматоре по модулю ''р-1''. Что положительно влияет и на требования к затратам по занимаемой площади и на контроль выполнения арифметических операций, при этом сохраняется требование однотипности используемого оборудования.
+Тем самым, переход к однородному представлению операндов позволил выполнять аддитивные и мультипликативные операции на одном оборудовании, а именно на сумматоре по модулю <math> p-1 </math>. Это положительно влияет и на требования к затратам по занимаемой площади и на контроль выполнения арифметических операций, при этом сохраняется требование однотипности используемого оборудования.