A Windowing Booth Recoding Algorithm for the Constant Multiplication Problem

In this paper, we introduce a novel windowing Booth (wBooth) recoding algorithm aimed at minimizing the average number of additions in the single/multiple constant multiplication (S/MCM) problem. Utilizing an exact average Hamming-weight formula of wBooth, we derive precise analytical expressions for the average number of additions, the maximum number of additions, and the maximum adder-depth for S/MCM. Our findings reveal that the wBooth recoding method results in an average reduction of $\mathbf{1 1. 2 6 \%}$ and $\mathbf{1 2. 5 4 \%}$ in additions for a 32 -bit constant compared to our previously published algorithms RADIX-2 ${ }^{w}$ SCM and RADIX-2 ${ }^{w}$ MCM, respectively.