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

В обикновения живот обикновено използваме позиционната бройна система. В позиционната бройна система стойността на всеки цифров знак (число) в записа на число зависи от неговата позиция (цифра) [1]. Съществуват обаче и така наречените „непозиционни бройни системи“, една от които е „остатъчната бройна система“ (или в оригинала Residue Number System (RNS)), която е в основата на модулната аритметика. Модулната аритметика се основава на "китайската теорема за остатъка" [2], която за нашия случай звучи така:

За всяка система от взаимно прости числа p1, … pn всяко число X от диапазона [0; M), където M = p1*p2*…*pn е едно към едно представимо като вектор (a1, a2, …, an), където ai = 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. Грешка в една позиция на вектора не влияеза изчисления в други позиции на вектора. За разлика от позиционната бройна система, всички елементи на вектора са еквивалентни и грешка в един от тях води само до намаляване на динамичния диапазон. Този факт позволява проектиране на устройства с повишена отказоустойчивост и коригиране на грешки.

Редовно умножениеМодулно умножение
число
число

Но не всичко е толкова гладко, колкото бихме искали. За разлика от позиционната бройна система, следните операции (наречени „немодулни“) са по-сложни, отколкото в позиционната бройна система: сравнение на числа, контрол на препълване, деление, корен квадратен и др. Първите успешни опити за използване на модулна аритметика в микроелектрониката бяха направени през 50-те години на миналия век, но поради трудностите с немодулните операции интересът донякъде намаля. Модулната аритметика обаче сега отново се връща в микроелектрониката поради следните причини:

  • широкото използване на мобилни процесори, които изискват висока скорост с ниска консумация на енергия. Липсата на пренасяне при аритметични операции събиране/умножение намалява консумацията на енергия.
  • нарастващата плътност на елементите на чипа в някои случаи не позволява пълно тестване, следователно значението на стабилността на процесорите към възможни грешки нараства.
  • появата на специализирани процесори с голям брой операции върху вектори, които изискват висока скорост и включват главно събиране и умножение на числа (например умножение на матрици, скаларно произведение на вектори, преобразуване на Фурие и др.).

директно преобразуване

Директно преобразуване от позиционна бройна система (обикновенов двоична форма) в бройната система в остатъка е да се намери остатъкът от деленето за всеки от модулите на системата.

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

Прилагането на намиране на остатък в микроелектрониката с даден модул се основава на следните свойства на остатъците: (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) Проверка 8 0 = (80%3, 80%5, 80%7) = (2, 0, 3)

Обратна трансформация

Обратното преобразуване от бройната система в остатъчните класове към позиционната бройна система се извършва по един от двата начина:

  1. Въз основа на китайската теорема за остатъка или система от ортогонални бази
  2. Въз основа на полиадичния код (други имена за система със смесен радикс, система със смесена основа)

Останалите методи, предложени в различна литература, всъщност са смесица от тези два.

Метод, базиран на китайската теорема за останките, се основава на следната идея: x = (x1, x2, ... xn) = (x1, 0, ..., 0) + (0, x2, ..., 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 Сега преобразуваме някакво число в системата на остатъчния клас. Нека X = (2, 3, 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. СУМА = 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.