Hostname: page-component-7c8c6479df-94d59 Total loading time: 0 Render date: 2024-03-29T07:41:03.444Z Has data issue: false hasContentIssue false

FUNCTIONAL PEARL Derivation of a logarithmic time carry lookahead addition circuit

Published online by Cambridge University Press:  27 October 2004

JOHN T. O'DONNELL
Affiliation:
Computing Science Department, University of Glasgow, Glasgow G12 8QQ, UK (email: jtod@dcs.gla.ac.uk)
GUDULA RÜNGER
Affiliation:
Department of Computer Science, Chemnitz University of Technology, 09107 Chemnitz, Germany (email: ruenger@informatik.tu-chemnitz.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Using Haskell as a digital circuit description language, we transform a ripple carry adder that requires $O(n)$ time to add two $n$-bit words into a parallel carry lookahead adder that requires $O(\log n)$ time. The ripple carry adder uses a scan function to calculate carry bits, but this scan cannot be parallelized directly since it is applied to a non-associative function. Several techniques are applied in order to introduce parallelism, including partial evaluation and symbolic function representation. The derivation given here constitutes a semi-formal correctness proof, and it also brings out explicitly each of the ideas underlying the algorithm.

Type
Functional pearls
Copyright
© 2004 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.