Введення у модулярну арифметику

У звичайному житті ми користуємося позиційною системою числення. У позиційній системі числення значення кожного числового знака (цифри) у записі числа залежить від його позиції (розряду) [1]. Проте існують і звані «непозиційні системи числення», до однієї з яких належить «система числення в залишках» (чи оригіналі Residue Number System (RNS)), що є основою модулярної арифметики. Модулярна арифметика базується на «Китайській теоремі про залишки» [2], яка для нашого випадку звучить так:

Для будь-якої системи взаємно простих чисел p1, … pn будь-яке число X з діапазону [0; M) , де M = p1*p2*…*pn взаємооднозначно представимо у вигляді вектора (a1, a2, …, an) , де ai = X%pi (тут і далі «%» — операція взяття залишку від цілого чисельного поділу X на pi). p1, … pn – модулі системи a1, a2, …, an – залишки (відрахування) числа за заданою системою модулів

На перший погляд, незрозуміло, яку перевагу може дати така система, проте існує 2 властивості, які дозволяють ефективно використовувати модулярну арифметику в деяких областях мікроелектроніки:

  1. Відсутність перенесення розрядів у додаванні та множенні. Нехай нам дано два числа X1 та X2, представлені у вигляді системи залишків (x11, x12, …, x1n) та (x21, x22, …, x2n) за системою взаємнопростих чисел (p1, p2, …, pn). У цьому випадку: X3 = X1 + X2 = ((x11+x21)%p1, (x12+x22)%p2, …, (x1n+x2n)%pn) X4 = X1 * X2 = ( (x11*x21)%p1, (x12*x22)%p2, …, (x1n*x2n)%pn) Тобто що б скласти або помножити два числа, достатньо скласти або помножити відповідні елементи вектора, що для мікроелектроніки означає, що це можна зробити паралельно і через малі розмірності p1, p2, …, pn зробити дуже швидко.
  2. Помилка однієї позиції вектора не впливаєна розрахунки інших позиціях вектора. На відміну від позиційної системи числення всі елементи вектора рівнозначні і помилка в одному з них веде лише до скорочення динамічного діапазону. Цей факт дозволяє проектувати пристрої з підвищеною стійкістю до відмови і корекцією помилок.

Звичайне множенняМодулярне множення
системи
системи

Але не все так гладко, як хотілося б. На відміну від позиційної системи числення, наступні операції (називаються «немодульними») виконуються складніше, ніж у позиційній системі числення: порівняння чисел, контроль переповнення, поділ, квадратний корінь і т.д. Перші успішні спроби застосування модулярної арифметики в мікроелектроніці були зроблені ще в 1950-х роках, але через складнощі з немодульними операціями інтерес трохи вщух. Проте в даний час модулярна арифметика знову повертається до мікроелектроніки з таких причин:

  • велике поширення мобільних процесорів, у яких потрібна висока швидкість при невеликому споживанні енергії. Відсутність перенесення в арифметичних операціях додавання/множення дозволяє знизити споживання енергії.
  • щільність елементів, що збільшується, на кристалі в деяких випадках не дозволяє провести повне тестування, тому зростає важливість стійкості процесорів до можливих помилок.
  • поява спеціалізованих процесорів з великою кількістю операцій над векторами, які вимагають високої швидкості і включають переважно додавання і множення чисел (наприклад множення матриць, скалярний добуток векторів, перетворення Фур'є і.т.д).

Пряме перетворення

Пряме перетворення з позиційної системи числення (зазвичайу двійковому вигляді) у систему числення в залишках полягає у знаходженні залишків від поділу по кожному з модулів системи.

Приклад: Нехай потрібно знайти уявлення числа X = 25 за системою модулів (3, 5, 7). X = (25% 3, 25% 5, 25% 7) = (1, 0, 4) .

Реалізація знаходження відрахування в мікроелектроніці за заданим модулем будується на наступних властивостях відрахувань: (2) (a+b) % p = (a % p + b % p) % p (a * b) % p = (a % p * b%p)%p

Будь-яке число X можна записати у вигляді X%p = (xn-1*2 n-1 + xn-2*2 n-2 + x0*2 0 )%p = ((xn-1)%p*2 n- 1 %p) + ((xn-2)%p*2 n-2 %p) + … + x0%p)%p . Оскільки в даному випадку xn-1, … x0 дорівнюють 0 або 1, то фактично нам потрібно скласти відрахування виду (2 i %p) .

Приклад: нехай задано число 25 або в двійковій системі числення 11001 і потрібно знайти залишок за модулем 7. 25%7 = (1*2 4 + 1*2 3 + 0*2 2 + 0 * 1 + 1*2 0 )%7 = (2 4 %7 + 2 3 %7 + 1%7)%7 = (2 + 1 + 1)%7 = 4

Систему модулів підбирають під конкретне завдання. Наприклад, для представлення 32-х бітних чисел достатньо наступної системи модулів: (7, 11, 13, 17, 19, 23, 29, 31) - всі вони взаємнопрості один з одним, їх добуток дорівнює 6685349671 > 4294967296 . Кожен із модулів не перевищує 5 біт, тобто операції складання та множення будуть проводитися над 5-бітними числами. Особое значення має система модулів виду: (2 n -1, 2 n , 2 n +1) у зв'язку з тим, що пряме і зворотне перетворення їм виконується найпростішим образом. Щоб отримати залишок від розподілу на 2 n достатньо взяти останні n цифр двійкового уявлення числа.

Арифметичні операції

Приклад: нехай задана система модулів (3, 5, 7), тобто ми можемо виконувати операції, результат яких не перевищує 3 * 5 * 7 = 105. Помножимо два числа 8 і10. 8 = (8%3, 8%5, 8%7) = (2, 3, 1) 10 = (10%3, 10%5, 10%7) = (1, 0, 3) 8*10 = ((2*1)%3, (3*0)%5, (1*3)%7) = (2, 0, 3) Перевіряємо 80 = (80%3, 80%5, 80%7) = (2, 0, 3)

Зворотне перетворення

Зворотне перетворення із системи числення в залишкових класах у позиційну систему числення проводиться одним із двох способів:

  1. На базі Китайської теореми про залишки або системи ортогональних базисів
  2. На базі поліадичного коду (інші назви mixed-radix system, система зі змішаною основою)

Інші запропоновані у різній літературі методи, власне, є сумішшю цих двох.

Спосіб, заснований на китайській теоремі про залишки, базується на наступній ідеї: X = (x1, x2, … xn) = (x1, 0, …, 0) + (0, x2, …, 0) + … + (0, 0, …, xn) = x1*(1, 0, …, 0) + x2*(0, 1, …, 0) + … + xn*(0, 0, …, 1). Тобто для зворотного перетворення потрібно знайти систему ортогональних базисів B1 = (1, 0, …, 0), B2 = (0, 1, …, 0), …, BN = (0, 0, …, 1) . Ці вектори знаходяться один раз для заданого базису, а для їх пошуку потрібно вирішити рівняння виду: (Mi * bi) % pi = 1, де Mi = M / pi, а bi - число, що шукається. У цьому випадку позиційне уявлення Bi = Mi*bi та X = (x1*(M1*b1) + x2*(M2*b2) + … + xn*(Mn*bn))%M

Приклад: нехай задана система модулів (3, 5, 7) , знайдемо значення Mi та bi (0 M = 3*5*7 = 105 M1 = 105/3 = 35 M2 = 105/5 = 21 M3 = 105/7 = 15 (35*b1)%3 = 1 =>b1 = 2 (21*b2)%5 = 1 = b2 = 1 (15*b3)%7 = 1 =>b3 = 1 Тепер перетворимо якесь число в системі залишкових класів. = (2 * 35 * 2 + 3 * 21 * 1 + 1 * 15 * 1) % 105 = (140 + 63 + 15) % 105 = 218% 105 = 8

Мінус цього методу полягає в тому, що для зворотного перетворенняпотрібно множення та додавання великих чисел (M1, …, Mn), а так само операція взяття залишку по модулю великого числа M.

Спосіб на базі поліадичного коду, що базується на ідеї, що будь-яке число X може бути представлене в системі взаємно простих чисел p1, … pn , як [4]: ​​X = a1 + a2 * p1 + a3 * p1 * p1 + an -1 * p1 * p2 * ... * pn-2 + an * p1 * p2 * ... * pn-1, де 0

Звідси випливає наступний ітеративний процес пошуку вихідного числа:

Приклад: Розглянемо той самий приклад - знайдемо позиційне уявлення числа X = (2, 3, 1) у системі модулів (3, 5, 7)

  1. SUM = 2
  2. SUM = SUM + (x2-SUM) % p2 = 2 + (3-2) % 5 = 3
  3. SUM = SUM + (x3-SUM) % p3 = 3 + (1 - 3) % 7 = 3 + (-2) % 7 = 3 + (7-2) % 7 = 3 + 5 = 8

Зауваження: у разі у процесі віднімання ми отримали негативне число, яке ми хіба що скомпенсували, додавши 7%7 = 0.