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