een snelle parallelle adder
naar deel 1
naar deel 2: flipflops

Inleiding

In dit artikel beschrijf ik de theorie en uitvoering van een snelle parallelle opteller.
Op een vorige pagina kwam al een zogenaamde "ripple adder" ter sprake.
Die is relatief traag omdat het carry signaal een lange weg heeft af te leggen.
In het geval van een 32 bit adder zijn dat zo'n 38 poorten.
 0111 1111 1111 1111 1111 1111 1111 1111 
 0000 0000 0000 0000 0000 0000 0000 0001
 --------------------------------------- +
 1000 0000 0000 0000 0000 0000 0000 0000
Door een hoop extra poorten in te zetten is een parallelle verwerking van de carry signalen te bereiken,
wat de opteller veel sneller maakt.

Theorie

We tellen twee getallen (a en b) van elk 32 bit op en noemen de bits a31..a0 en b31..b0
Twee bits an, bn noemen we Bits n (Bn).
Voor wat de carry betreft zijn er 3 mogelijkheden:
    1. een inkomende carry wordt niet doorgegeven ( 0 + 0)
    2. een inkomende carry wordt wel doorgegeven ( 0 + 1 of 1 + 0) naam: Pass
    3. er wordt een carry gegenereerd (1 + 1) naam: Carry
Bits n Pass schrijven we als BnP.
Bits n Carry schrijven we als BnC.

BnC samen met BnP noemen we de Bits translations

We nemen nu 4 opvolgende Bits samen en noemen die een Groep (G).
Op een zelfde manier kunnen we hebben
    Een groep Pass : een inkomende carry wordt naar de volgende groep doorgegeven
    Een groep Carry : de groep genereert een carry naar de volgende groep
 G0C = B3C + B2C.B3P + B1C.B2P.B3P + B0C.B1P.B2P.B3P
 G0P = B0P.B1P.B2P.B3P

G0C en G0P zijn de groep translations van groep 0.

Vier opvolgende groepen nemen we ook samen, dat is een sectie.
Er is een sectie Pass en een sectie Carry, net als bij de groepen hiervoor.
S0P en S0C zijn de sectie translations van sectie 0.

In totaal hebben we nu de Bits translations 0..31 ,
groep translations 0..7 en section translations 0..1

Eerst bepalen we welke sectie een carry binnen krijgt:
Sectie 0 niet, want waar zou die carry vandaan moeten komen?
Sectie 1 carry in S1Ci = S0C

We bepalen nu de carries naar groepen 0..3 in sectie 0:
G0Ci = 0
G1Ci = G0C
G2Ci = G1C + G0C.G1P
G3Ci = G2C + G1C.G2P + G0C.G1P.G2P

De carries naar groepen 4..7 in sectie 1:
G4Ci = S0C
G5Ci = G4C + S0C.G4P
G6Ci = G5C + G4C.G5P + S0C.G4P.G5P
G7Ci = G6C + G5C.G6P + G4C.G5P.G6P + S0C.G4P.G5P.G6P

De carries naar Bits 0..3:
B0Ci = 0
B1Ci = B0C
B2Ci = B1C + B0C.B1P
B3Ci = B2C + B1C.B2P + B0C.B1P.B2P

................
De carries naar Bits 28..31:
B28Ci = S6C
B29Ci = B28C + S6C.B28P
B30Ci = B29C + B28C.B29P + S6C.B28P.B29P
B31Ci = B30C + B29C.B30P + B28C.B29P.B30P + S6C.B28P.B29P.B30P

Uitvoering

De som Sn van an en bn is 1 als het een Bit Pass is.
Maar een inkomende carry draait de bitwaarde om.
Dit is de beschrijving van de snelle parallelle opteller.
Wat is de snelheidswinst?
De maximale weg van een (carry) signaal is 12 poorten,
waarbij een XOR poort voor 3 is gerekend.
Deze opteller is dus ruim drie maal sneller.
Een 64 bits opteller wordt door deze techniek zes maal sneller.