Radix-2 over-redundant digit set converters

Often radix-2 division algorithms make use of over redundant digit-set in the selection of the quotient digits. The final step in such a division algorithm is the conversion of the quotient to the conventional two's complement notation. The best approach for this conversion, in the case of non-over-redundant digit sets, is the on-the-fly technique. In this paper, we explore two different alternatives to the on-the-fly conversion algorithm, for the conversion of an integer number from the radix-2 over-redundant representation into the two's complement notation. In the direct conversion approach, the conversion is realized in one step. In the redundancy reduction approach, the conversion is achieved in two steps: a redundancy reduction step and a binary conversion step. The discussion is carried out assuming no restrictions on the sequence of radix-2 over-redundant digits. Our main conclusion is that the redundancy reduction approach is the most efficient.