Parallel Canonical Recoding

C. K. Koc

Electronics Letters, 32(22):2063-2065, 24th October 1996.

Abstract

We introduce a parallel algorithm for generating the canonical signed-digit expansion of an n-bit number in O(log(n)) time using O(n) gates. The algorithm is similar to the computation of the carries in a carry look-ahead circuit. We also prove that if the binary number x+ [x/2] is given, then the canonical signed-digit recoding of x can be computed in O(1) time using O(n) gates.