🚀 go-pugleaf

In article <1992Sep25.110131.17771@donau.et.tudelft.nl>
maarten@dutecaj.et.tudelft.nl (M. Hofman) writes:

>I'm doing a research on the usability of signed digit notation (and other
>redundant binary notations) in general purpose microprocessors. After checking
>the add, multiply, shift, divide and square root I finally came to the big
>question of the compare. Needed is a very fast compare (on less than zero) 
>algorithm, that can be implemented in VLSI and uses signed digit notation (in 
>specific: (0,0) for 0, (0,1) for 1 and (1,0) for -1, but I'm also interested in 
>compares using other ways of coding the redundancy). If anyone knows about papers 
>on this subject, or has developed something she/he is willing to share, please 
>mail me.
>
>I have already developed a simple method myself:
>
>In parallel check:
>  1) If the MSB is -1
>  2) If the MSB is 0 and the MSB-1 is -1
>  3) If the MSB is 0 and the MSB-1 is 0 and the MSB-2 is -1
>  4) Et cetera
>If one of the above yields true, the number is less than zero.
>
>But I don't know if this algorithm can be easily made in VLSI.

Doing this fast should be possible using techniques similar to those used in
a carry-propagate adder. I.e. at the bit level, define generate and
propagate signals for each digit position i (with the LSB being position 0)
by:

  G[i,0] = (Digit i is -1)
  P[i,0] = (Digit i is 0)

Then define similar signals on say 4-digit blocks by:

  G[4*i,1] = G[4*i+3,0]
             OR (G[4*i+2,0] AND P[4*i+3,0])
             OR (G[4*i+1,0] AND P[4*i+2,0] AND P[4*i+3,0])
             OR (G[4*i,0] AND P[4*i+1,0] AND P[4*i+2,0] AND P[4*i+3,0])

  P[4*i,1] = P[4*i,0] AND P[4*i+1,0] AND P[4*i+2,0] AND P[4*i+3,0]

This can then be repeated for 16-digit blocks, etc.

Other fast adder techniques (e.g. carry-select adders, Ling adders, etc.)
may generalise similarly.

David Seal
dseal@armltd.co.uk

All opinions are mine only...