Redundant binary Booth recoding

Abstract

We investigate the efficiencies attainable pursuing Booth recoding directly from redundant binary input with limited carry propagation. As a digit conversion problem we extend the important result that each radix 4 Booth recoded digit can be determined from 5 consecutive input signed bits to obtain that each radix 2/sup k/ Booth recoded digit can be determined from 2k+1 consecutive input signed bits and prove this to be the minimum possible for any k/spl ges/2. Analysis of alternative bit pair encodings of signed bits yields the improved result that each radix 2/sup k/ Booth recoded digit can be determined from only 2k encoded bit pairs employing sign and magnitude bit encoding, a result which does not extend to conventional borrow-save or carry-save redundant binary digit encodings. Radices 4 and 8 gate level designs are illustrated for alternative encodings, with our signed bit design shown to yield smaller depth and fewer gates than existing redundant binary Booth recoding circuits from the literature.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>