PARALLEL CANONICAL RECODING

Authors
KOC CK
Citation
Ck. Koc, PARALLEL CANONICAL RECODING, Electronics Letters, 32(22), 1996, pp. 2063-2065
Citations number
6
Categorie Soggetti
Engineering, Eletrical & Electronic
Journal title
Electronics Letters → ACNP
ISSN journal
00135194
Volume
32
Issue
22
Year of publication
1996
Pages
2063 - 2065
Database
ISI
SICI code
0013-5194(1996)32:22<2063:PCR>2.0.ZU;2-3
Abstract
The author introduces a parallel algorithm for generating thr canonica l signed-digit expansion of an n-bit number in O(logn) time using O(n) gates. The algorithm is similar to the computation of the carries in a carry look-ahead circuit. It is also proven that if the binary numbe r x + right perpendicular x/2 left perpendicular is given, then the ca nonical signed-digit recoding of x can be computed in O(1) time using O(n) gates.