Главная » Защита информации » Непосредственное вычисление значений логарифма Якоби

Непосредственное вычисление значений логарифма Якоби

Непосредственное вычисление значений логарифма Якоби имеет сложность дискретного логарифма. Табличная реализация логарифма Якоби, в силу технических ограничений на допустимый объем используемых таблиц, ограничена сверху количеством разрядов базисного модуля p поля Галуа GF(p).

Тем самым, структурная схема МАС, построенная на основе модулярной логарифметики и использующая метод ассоциативности (сокращенно RLMACnew), представлена на Рис.3.

Ree A

Reg_B

3

Adder mod(p-1)

Reg_S

LE

Sub mod(p-l)

* JwM

Adder mod(p-1)

Reg_C

I

C[N-1:01

Рис. 3. Один канал RLMACnew блока Рассмотрим метод, основанный на обобщенном преобразовании Гор-нера.

Подлогарифмическое выражение уравнения (2) примет вид:

±w^

W^'-1

LW^'JlW"

«-llp-l

(3)

P-i

= Z;+(p-Z;_1)p_1,/>2.

Гдеiz(,(_iip-i=h-vi

Такой метод позволяет получить конвейерную структуру алгоритма вычисления логарифма Гаусса большой арности.

Структурная схема МАС, построенная на основе модулярной логарифметики и использующая метод обобщенной схемы Горнера (сокращенно RLMAC-2L), представлена на Рис. 4.

104

А N-1:0

В N-1:0

I

P

!=1

Го

Р—1

Р—1

P

P

P

(=1

P

P

P

P

P

Р-1

P

I Д,/7\М;СУ I BJN-liOl I A2[N-1:0]\ B2[N-1:0]

Reg_Ai

Reg_Bi

Reg_A2

Reg_B2

R ^r ^r^

Add_Sub unit

Add_Sub unit

Л. М

I

REG_Accumulate

Reg_C

T C[N-1:0]

Рис. 4. Один канал RLMAC-2L блока

5. Результаты синтеза.

Структурный синтез проводился средствами САПР Synopsys Synplify в базисе ПЛИС Altera Stratix II EP2S15F484C3. Симуляция и верификация VHDL проектов проводились средствами ModelSim Mentor Graphics. Быстродействие схемы определяется тактовой частотой, сложность реализации измеряется числом адаптивных логических блоков табличного типа (ALUT, Adaptive Look Up Table).

Таблица 1. Результаты сравнения архитектур.

Clock, Mhz

ALUT

MAC unit

168

387

RLMAC unit

376

254

RLMAC_new unit

394

323

RLMAC-2L unit

333

878

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

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

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

Список литературы.

1. Amondi Аmos, Premkumar Benjamin Residue Number Systems: Theory and Impemetation // Imperial Colledge Press, 2007.

2. Корнилов А. И., Семенов М. Ю., Ласточкин О. В. Принципы построения модулярных индексных умножителей // Изв. ВУЗов. Электроника. – 2004. -№ 2. – С. 48-55.

3. Акушский И. Я., Юдицкий Д. И. Машинная арифмеика в остаточных классах // М.: Советское радио, 1968, 439 с.

4. M. Dugdale Residue multipliers using factored decomposition // IEEE Trans. Circuits Syst. — II, vol. 41, no. 9, pp. 623-627, Sept. 1994.

5. Балака Е. С. Алгоритм вычисления скалярных произведений в поле GF // 15-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов "Микроэлектроника и информатика — 2008".

6. Preethy A. P. , Radhakrishnan D. An RNS based logarithmic adder // IEE Proceedings – Computers and Digital Techniques, Vol.147, Issue 4, July 2000

7. Лидл Р., Ниддерайтер Р. Конечные поля // том 1, перев. с англ. М.: Мир, 1988.

8. Hoang T., Själander M., and Larsson-Edefors P. High-Speed, Energy-Efficient 2-Cycle Multiply-Accumulate Architec-ture// IEEE International SoC Conference Belfast, Northern Ireland, UK, September 9-11, 2009.LIFO Modulo

Этот домен продается здесь: telderi.ru, и еще много других