Canonical signed digit

In computing canonical-signed-digit (CSD) is a special manner for encoding a value in a signed-digit representation, which itself is non-unique representation and allows one number to be represented in many ways. Probability of digit being zero is close to 66% (vs. 50% in two's complement encoding) and leads to efficient implementations of add/subtract networks (e.g. multiplication by a constant) in hardwired digital signal processing.[1]

The representation uses a sequence of one or more of the symbols, -1, 0, +1 (alternatively -, 0 or +) with each position possibly representing the addition or subtraction of a power of 2. For instance 23 is represented as +0-00-, which expands to $+2^{5}-2^{3}-2^{0}$ or $32-8-1=23$

Implementation

CSD is obtained by transforming every sequence of zero followed by ones (011...1) into + followed by zeros and the least significant bit by - (+0....0-).

As an example: the number 7 has a two's complement representation 0111

(7=0\times 2^{3}+1\times 2^{2}+1\times 2^{1}+1\times 2^{0}=4+2+1)

into +00-

(7=+1\times 2^{3}+0\times 2^{2}+0\times 2^{1}-1\times 2^{0}=8-1)

References

Hewlitt, R.M. (2000). "Canonical signed digit representation for FIR digital filters". Signal Processing Systems, 2000. SiPS 2000. 2000 IEEE Workshop on: 416–426. doi:10.1109/SIPS.2000.886740. ISBN 978-0-7803-6488-2.

External links

Introduction to Canonical Signed Digit Representation
Fractions in the Canonical-Signed-Digit Number System. Conference on Information Sciences and Systems. The Johns Hopkins University. March 21–23, 2001. CiteSeerX 10.1.1.126.5477.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Hewlitt, R.M. (2000). "Canonical signed digit representation for FIR digital filters". Signal Processing Systems, 2000. SiPS 2000. 2000 IEEE Workshop on: 416–426. doi:10.1109/SIPS.2000.886740. ISBN 978-0-7803-6488-2.