Mentés-összetevő szállítása

A hordozható összeadó [ 1] [2] egyfajta digitális összeadó , amelyet a számítógépes mikroarchitektúrában használnak három vagy több n bites szám összegének kiszámítására a bináris számrendszerben . Abban különbözik a többi digitális összeadótól, hogy a kimenetei a bemenetekkel azonos méretű két szám, amelyek közül az egyik a bitek részösszege, a másik pedig egy átviteli bitsorozat .

Motiváció

Fontolja meg az összeget:

12345678 +87654322 =100000000

Aritmetika segítségével jobbról balra: "8+2=0, cipel 1", "7+2+1=0, cipel 1", "6+3+1=0, cipel 1" és így tovább a végéig az összegből. Tudjuk azonban, hogy amíg az eredmény utolsó számjegyét meg nem kapjuk, addig nem ismerjük a bal oldali első számjegyet, amíg a számítás során végig nem megyünk minden számjegyen, és átvisszük az átvitelt minden számjegyről a következőre. Így két n-bites szám összeadása n-nel arányos időt vesz igénybe, még akkor is, ha az általunk használt gép egyszerre több számítás elvégzésére is képes.

Elektronikus értelemben, bitek (bináris számjegyek) használatával ez azt jelenti, hogy még ha n darab egybites összeadó is áll rendelkezésünkre, akkor is n-nel arányos időt kell töltenünk, hogy a átvitel a szám egyik végéről a Egyéb. Miközben ezt csináljuk

1. Az összeadás eredményét nem ismerjük. 2. Nem tudjuk, hogy az összeadás eredménye kisebb vagy nagyobb lesz-e a megadott számnál (például nem tudjuk, hogy pozitív vagy negatív lesz).

Az átviteli összeadó csökkentheti a késleltetést. A késleltetést elvileg úgy lehet csökkenteni, hogy az arányos legyen log n -nel , de nagy számoknál ez már nem így van, mert még gyorsított átvitel esetén is arányosan növekszik az a távolság, amelyet a jel a chipen megtesz, ill. a terjedési késleltetés növekszik ebben az azonos attitűdben. Miután megkaptuk a nyilvános kulcsú titkosítási rendszerekben szükséges 512-2048 bites számokat, a továbbítás már nem segít.

Alapfogalom

Neumann Jánosé az az ötlete, hogy az átadás lezárását a végére kell halasztani, vagy megtartani . [3]

Íme egy példa a bináris összeadásra:

10111010101011011111000000001101 + 11011110101011011011111011101111.

A hordozó aritmetika úgy működik, hogy elhagyja a bináris jelölést, miközben továbbra is a 2-es bázisban dolgozik. Számjegyenként számítja ki az összeget, mint

10111010101011011111000000001101 + 11011110101011011011111011101111 = 21122120202022022122111011102212.

A jelölés nem szokványos, de az eredmény egyértelmű marad. Sőt, adott n összeadó (itt n = 32 teljes összeadó) az eredmény a bemenetek egy összeadón (egy generátorciklusban) való áthaladása után számítható ki, mivel az eredmény minden számjegye független a többitől.

Ha két szám összeadásához és az eredmény kiszámításához összeadóra van szükség, akkor a hordozó-megőrző összeadás nem alkalmas, mivel az eredmény visszaváltható binárissá, ami azt jelenti, hogy a hordozók még nem terjedtek jobbról balra. De a nagy egész számok aritmetikájában az összeadás nagyon ritka művelet, és általában az átvitelt megőrző összeadókat használnak részösszegek felhalmozására egy szorzóban.

Mentés meghajtók hordozása

Tegyük fel, hogy az eredmény minden számjegyéhez két bitnyi memória van, akkor használhatunk redundáns bináris ábrázolást , minden számjegy pozícióban tárolva a 0, 1, 2 vagy 3 értékeket. Ez azért van így, mert egynél több bináris számot is hozzá lehet adni a hordozásmegőrző eredményünkhöz anélkül, hogy túlcsordulnánk memóriakapacitásunk: de akkor mi van?

A megértés kulcsa az, hogy minden részleges összeadás során három bitet adunk hozzá:

Más szóval, a hordozó számjegyet a jobb oldali pozícióból vesszük, és a hordozó számjegyet balra visszük, ugyanúgy, mint a hagyományos összeadásnál; de a balra átadott hordozószám az előző számítás eredménye, nem az aktuális. A generátor minden ciklusában a hordozók csak egy lépést tesznek előre, és nem n lépést, mint a hagyományos összeadásnál.

Mivel a jelek nem jutnak el olyan messzire, a generátor gyorsabban tud ketyegni.

A számítás végén továbbra is szükség van az eredményt binárisra konvertálni, ami valójában csak azt jelenti, hogy a hordozók végigmennek a számon, mint egy hagyományos összeadónál. De ha 512 összeadást végeztünk az 512 bites szorzás során, akkor ennek a végső átalakításnak a nagy költsége el van osztva mind az 512 összeadással, tehát minden összeadás csak 1/512-ét hordozza a végső „normál” nagy költségének. kiegészítés.

Hátrányok

Az adagolás minden szakaszában transzfer tartósítással,

  1. Az összeadás eredményét azonnal tudjuk.
  2. Még mindig nem tudjuk, hogy az összeadás eredménye nagyobb vagy kisebb-e a megadott számnál (például nem tudjuk, hogy pozitív vagy negatív).

Ez utóbbi pont hátrányt jelent, ha átvitelt megőrző összeadókat használunk modulo szorzások végrehajtására (az osztást követő szorzások, csak a maradék megtartása). Ha nem tudhatjuk, hogy a köztes eredmény nagyobb vagy kisebb, mint a modulus, akkor honnan tudhatjuk, hogy ki kell-e vonni a modulusokat?

A Montgomery-szorzás , amely az eredmény jobb szélső számjegyétől függ, az egyik megoldás; ami inkább maga a hordozás-megőrző összeadás, állandó rezsije van, így a Montgomery szorzási szekvencia időt takarít meg, de az egyetlen nem. Szerencsére a hatványozás, amely valójában szorzások sorozata, a nyilvános kulcsú kriptográfiában a leggyakoribb művelet.

Technikai részletek

Egy átvitelt megtakarító eszköz n teljes összeadóból áll , amelyek mindegyike egy egybites összeget és egy átviteli bitet számít ki teljes egészében a három bemeneti szám megfelelő bitjei alapján. Adott három n bites a , b és c szám egy ps részösszeget és egy eltolt hordozó sc :

A teljes összeg ezután kiszámítható:

  1. Az sc átviteli sorrendet egy hellyel balra tolva.
  2. 0 hozzáadásával a ( legjelentősebb bit ) részösszeg sorozat ps bal oldalához .
  3. Egy hordozható összeadó segítségével a kettőt összeadjuk, és előállítjuk a kapott n + 1 bites értéket.

Ha három vagy több számot összeadunk, a hordozós mentési összeadó és egy egymást követő összeadó használata gyorsabb, mint két egymást követő átviteli összeadó használata. Ennek az az oka, hogy a szekvenciális összeadó nem tudja kiszámítani a bitek összegét anélkül, hogy megvárná az előző hordozóbit kiszámítását, és így ugyanaz a késleltetése, mint az n teljes összeadónak. Egy hordozható összeadó párhuzamosan számítja ki az összes kimeneti mennyiségét, így ugyanaz a késleltetési idő, mint egy teljes összeadóé. Így a teljes számítási idő (a teljes összeadási késleltetési idő egységeiben) egy átvitel-mentő összeadó plusz egy átviteli sorrendű összeadó esetén n + 1, míg két egymást követő összeadónál 2 n -nek kell lennie .

Lásd még

Jegyzetek

  1. ↑ Earle, JG és munkatársai 3 340 388 számú amerikai egyesült államokbeli szabadalom, „Latched Carry Save Adder Circuit for Multipliers”, benyújtva 1965. július 12-én
  2. ↑ Earle, J. (1965. március), Latched Carry-Save Adder, IBM Technical Disclosure Bulletin Vol . 7 (10): 909–910  
  3. ↑ Neumann János, Összegyűjtött művek.