15.11 Übertragsvorausberechnung
Die Module im carry ripple adder seien von rechts her numeriert, beginnend mit 0 . Weiter seien x i, y i and c i die i-ten Eingabeziffern und Überträge (bei gegebenem c 0) .
Aus dem Entwurf lesen wir folgende Recurrenz ab:
c (i+1) = (p i /\ c i) \/ g i where
(g i, p i) = (x i /\ y i , x i \/ y i )
Mit den üblichen Techniken zum Lösen von Rekurrenzen erhlten wir eine geschlossene Darstellung der Überträge:
c (i+1) = foldr1 (\/)
[ ( foldr1 (/\) [ p k | k <- [j+1..i] ) /\ g j | j <- [-1..i] ]
where g (-1) = c 0
Dies wird zur Übertragsvorausberechnung benutzt.