дійсненні перетворення в ступеневу форму (так зване ступовий обчислення), в якому множення може більш швидко здійснюватися за допомогою операції підсумовування.
Метод роботи цього помножувача пов'язаний з математичними властивостями полів Галуа [14, 15], що позначаються GF (p), де p - просте число. Всі ненульові елементи поля Галуа можуть бути отримані шляхом багаторазового зведення в ступінь примітивного елемента - породжує поле GF (p) елемента gj. Ця властивість полів Галуа можна використовувати для множення в GF (mj) завдяки використанню ізоморфізму між мультипликативной по модулю mj групою Q={1,2, ..., m - 1}, і адитивної по модулю (mj - 1) - групою I={ 0,1, ..., m - 2}. Цей ізоморфізм може бути встановлений таким чином:
(2.4)
і множення над полем GF (m) може здійснюватися за формулою:
(2.5)
Таким чином, множення двох чисел qj і qk можна виробляти обчислюючи модулярную суму відповідних покажчиків ij і ik, а потім проводячи зворотне перетворення з статечного простору у вихідний вид. Необхідно спеціально обробляти випадки, коли один з операндів на вході помножувача дорівнює нулю і в цьому випадку призначати нульовий результат твору. Це відбувається тому, що не визначений елемент у статечному просторі, відповідний нульовому елементу групи Q.
Ступені ij і ik для qj і qk, відповідно, можуть бути заздалегідь обчислені і поміщені в LUT. Додавання ступенів виконує суматор по модулю mj - 1. Зворотне перетворення з статечного подання ij і ik у вихідне qj і qk також може бути виконано за допомогою попередньо обчислених LUT.
Рисунок 2.2 (б) - Схема модулярного помножувача, заснованого на обчисленні ступенів (помножувач Галуа)
Розглянемо як приклад роботу цього помножувача на прикладі множення двох чисел 14 і 28 по модулю 31.
Так як 31 - просте число, існує породжує елемент g, що дає можливість асоціювати кожен елемент мультиплікативної групи
Q={1,2, ..., 31} з елементом адитивної групи I={0,1, ..., 30}. Відповідність задається виразом. У табл.1 розраховане відповідність між елементами групи Q і відповідним ступенем з адитивної групи I. Ця таблиця по суті і являє собою зміст LUT розміром 2 травня? 5 прямого і зворотного перетворення в умножителе, зображеному на рис. 2.2 (б).
Розглянемо роботу помножувача Галуа (рис. 2.2 (б), рис. 2.2 (в), табл. 1) на прикладі множення | 14? 28 | 31. Отже, qj=14 і qk=28, а твір | qj? qk | 31 виходить за допомогою підсумовування відповідних їм елементів ij і ik, вибраних з табл. 1. Таким чином, покажчики виявляються ij=22 і ik=16 і | ij + ik | 30=8. Елементу in=8 в табл. 1 відповідає qn=20, отже, | 14? 28 | 31=20.
Рисунок 2.2 (в) - Схема роботи 5-бітного помножувача Галуа
На рис. 2.2 (в) показано, яким чином відбувається множення чисел 14 і 28 по модулю 31 за схемою, зображеної на рис. 2.2 (б). Для простоти дві таблиці LUT1 і LUT2 об'єднані в одну і являють собою таблиці, що переводять множити числа в ступовий подання з табл. 1, а в якості суматора виступає простий модулярні суматор, зображений на рис. 2.1 (а). LUT3 виконує додавання по модулю 30, а LUT4 переводить результат з ста...
