Ripple-carry-opteller versus carry-lookahead-opteller versus carry-save-opteller: vertraging, oppervlakte en toepassingen
Alle drie zijn optellers die uit volledige optellers zijn opgebouwd, maar ze behandelen carry's verschillend. Een ripple-carry-opteller schakelt volledige optellers in een keten, zodat de carry van de laagste naar de hoogste bit doorschuift, en de vertraging groeit evenredig met de bitbreedte n (O(n)). Een carry-lookahead-opteller berekent alle carry's parallel uit generate- en propagate-signalen per bit, en met een hiërarchische lookahead groeit de vertraging slechts als O(log n). Een carry-save-opteller reduceert drie getallen tot twee, een somwoord en een carrywoord, zonder carry's door te geven, dus de vertraging is die van één volledige opteller, ongeacht de breedte. Vermenigvuldigers reduceren partiële producten met bomen van carry-save-optellers (zoals Wallace-bomen) en tellen de laatste twee getallen op met een snelle opteller.
| Kenmerk | Ripple-carry-opteller | Carry-lookahead-opteller | Carry-save-opteller |
|---|---|---|---|
| Ingangen en uitgangen | Telt twee getallen (en een carry-in) op tot één som en een carry-out | Telt twee getallen (en een carry-in) op tot één som en een carry-out | Reduceert drie getallen tot twee, een somwoord S en een carrywoord Cy (A + B + C = S + Cy) |
| Behandeling van de carry | Elke volledige opteller wacht op de carry van de lagere bit en geeft die beurtelings naar boven door | Gebruikt generate g = a·b en propagate p = a ⊕ b en werkt c(i+1) = g(i) + p(i)·c(i) uit om carry's parallel te berekenen | Carry's gaan niet naar de naburige bit; ze gaan naar de volgende trap als een woord dat één bit naar links is verschoven |
| Groei van de vertraging | O(n); in het slechtste geval loopt de carry van de laagste naar de hoogste bit | O(log n) (met een hiërarchische lookahead) | O(1); de vertraging van één volledige opteller, ongeacht de breedte |
| Cijfers voor 64 bits | De carry gaat door 64 volledige optellers | Drie niveaus van 4-bitblokken; in een Kogge-Stone-parallel-prefixopteller kost de carryberekening log₂64 = 6 trappen | Eén trap kost de vertraging van één volledige opteller; een Wallace-boom die 64 partiële producten tot twee reduceert, heeft 10 trappen nodig |
| Oppervlakte | Het kleinst: n volledige optellers voor n bits | Groter door de lookahead-logica; snellere ontwerpen gebruiken meer poorten en bedrading (ruwweg n log n voor Kogge-Stone) | Eén trap bestaat uit n volledige optellers zonder carryketen; een volledige vermenigvuldigerboom schaalt met het aantal bits van de partiële producten (ongeveer n²) |
| Resultaatformaat | Gewoon binair | Gewoon binair | Redundante vorm, gesplitst in een somwoord en een carrywoord; aan het eind is een gewone opteller nodig om één waarde te krijgen |
| Typische toepassingen | Kleine of zuinige schakelingen waarin snelheid niet kritisch is; in FPGA's vaak gebouwd op speciale carryketenlogica | ALU's van CPU's, adresberekening, floating-point-eenheden, de laatste optelling in vermenigvuldigers | Reductie van partiële producten in vermenigvuldigers (Wallace- en Dadda-bomen), accumulatie in multiply-accumulate-eenheden, optellen van veel getallen |
| Verwante ontwerpen | Carry-skip- en carry-select-optellers (qua snelheid en oppervlakte tussen beide in) | Parallel-prefixoptellers (Kogge-Stone, Brent-Kung en andere) | 4:2-compressoren, combinatie met het algoritme van Booth om partiële producten te verminderen |
De getalswaarden zijn typische ordegroottes en variëren per procesgeneratie en product.