What is a canonical signed digit?

What is a canonical signed digit (CSD) and how does one convert a binary number to a CSD and a CSD back to a binary number? How do you know if a digit of a CSD should be canonically chosen to be +, -, or 0?

回答1:

Signed-digit binary uses three symbols in each power-of-two position: -1, 0, 1. The value represented is the sum of the positional coefficients times the corresponding power of 2, just like binary, the difference being that some of the coefficients may be -1. A number can have multiple distinct representations in this system.

Canonical signed digit representation is the same, but subject to the constraint that no two consecutive digits are non-0. It works out that each number has a unique representation in CSD.

See slides 31 onwards in Parhi's Bit Level Arithmetic for more, including a binary to CSD conversion algorithm.

回答2:

What is canonical signed digit format?

Canonical Signed Digit (CSD) is a type of number representation. The important characteristics of the CSD presentation are:

CSD presentation of a number consists of numbers 0, 1 and -1. [1, 2].
The CSD presentation of a number is unique [2].
The number of nonzero digits is minimal [2].
There cannot be two consecutive non-zero digits [2].

How to convert a number into its CSD presentation?

First, find the binary presentation of the number.

Example 1 Lets take for example a number 287, which is 1 0001 1111 in binary representation. (256 + 16 + 8 + 4 + 2 + 1 = 287)

1 0001 1111

Starting from the right (LSB), if you find more than non-zero elements (1 or -1) in a row, take all of them, plus the next zero. (if there is not zero at the left side of the MSB, create one there). We see that the first part of this number is

01 1111

Add 1 to the number (i.e. change the 0 to 1, and all the 1's to 0's), and force the rightmost digit to be -1.

01 1111 -> 10 000-1

You can check that the number is still the same: 16 + 8 + 4 + 2 + 1 = 31 = 32 + (-1). Now the number looks like this

1 0010 000-1

Since there are no more consecutive non-zero digits, the conversion is complete. Thus, the CSD presentation for the number 287 is 1 0010 000-1, which is 256 + 31 - 1.

Example 2

How about a little more challenging example. Number 345. In binary, it is

1 0101 1001

Find the first place (starting from righ), where there are more than one non-zero numbers in a row. Take also the next zero. Add one to it, and force the rightmost digit to be -1.

1 0110 -1001

Now we just created another pair of ones, which has to be transformed. Take the 011, and add one to it (get 100), and force the last digit to be -1. (get 10-1). Now the number looks like this

1 10-10 -1001

Do the same thing again. This time, you will have to imagine a zero in the left side of the MSB.

10 -10-10 -1001

You can make sure that this is the right CSD presentation by observing that: 1) There are no consecutive non-zero digits. 2) The sum adds to 325 (512 - 128 - 32 - 8 + 1 = 345).

More formal definitions of this algorithm can be found in [2].

Motivation behind the CSD presentation

CSD might be used in some other applications, too, but this is the digital microelectronics perspective. It is often used in digital multiplication. [1, 2]. Digital multiplication consists of two phases: Computing partial products and summing up the partial product. Let's consider the multiplication of 1010 and 1011:

       1010
x      1011

=   1101110

As we can see, the number of non-zero partial products (the 1010's), which are has to be summed up depends on the number of non-zero digits in the multiplier. Thus, the computation time of the sum of the partial products depends on the number of non-zero digits in the multiplier. Therefore the digital multiplication using CSD converted numbers is faster than using conventional digital numbers. The CSD form contains 33% less non-zero digits than the binary presentation (on average). For example, a conventional double precision floating point multiplication might take 100.2 ns, but only 93.2 ns, when using the CSD presentation. [1]

And how about the negative ones, then. Are there actually three states (voltage levels) in the microcircuit? No, the partial products calculated with the negative sign are not summed right away. Instead, you add the 2's complement (i.e. the negative presentation) of these numbers to the final sum.

Sources:

[1] D. Harini Sharma, Addanki Purna Ramesh: Floating point multiplier using Canonical Signed Digit

[2] Gustavo A. Ruiz, Mercedes Grand: Efficient canonic signed digit recoding