VLSI Digital Signal Processing Systems: Design and Implementation

14.7    REDUNDANT TO NONREDUNDANT CONVERTER

The problem of converting a redundant number to a nonredundant number is nontrivial and more interesting. For example, consider a radix-4 digit in maximally redundant format transmitted msd first, where the digits can take on values from the set {−3, −2, −1, 0, 1, 2, 3}. The problem is to transform this number into a parallel nonredundant number. It is important to note that in general it is not possible to know the value of any of the nonredundant digits until the least significant redundant digit becomes available. For example, consider the redundant number 1000. In nonredundant radix-4 format this number is expressed as (03333)₄. However, changing the lsd from – 1 to 1, it is immediately seen that the resulting number in nonredundant radix-4 format is (10001)₄, which means that changing the least significant digit from −1 to 1 causes all of the preceding (more significant) digits to be changed.

Fig. 14.20    Radix-2 redundant to nonredundant format converter operating in the lsd-first mode.

Therefore, if a redundant number is scanned msd-first and transformed to a nonredundant radix-4 format, it is impossible to output a single digit of the result until the lsd of the input has been processed.

14.7.1    LSD-First Conversion

The conversion ...