Canonical signed digit
In computing canonical-signed-digit (CSD, also known as non-adjacent form) is a unique way of encoding a value in a signed-digit representation (also known as redundant binary 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 [math]\displaystyle{ +2^5 -2^3 -2^0 }[/math] or [math]\displaystyle{ 32 - 8 - 1 = 23 }[/math]
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
- [math]\displaystyle{ (7=0\times 2^3+1\times 2^2+1\times 2^1+1\times 2^0 = 4+2+1) }[/math]
into +00-
- [math]\displaystyle{ (7=+1\times 2^3+0\times 2^2+0\times 2^1-1\times 2^0 = 8-1) }[/math]
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.
 |
