// ************************************************************************** // // // // eses eses // // eses eses // // eses eseses esesese eses Embedded Systems Group // // ese ese ese ese ese // // ese eseseses eseseses ese Department of Computer Science // // eses eses ese eses // // eses eseses eseseses eses University of Kaiserslautern // // eses eses // // // // ************************************************************************** // // The following module implements a multiplication of 2-complement numbers // // by Booth recoding. In addition to Booth recoding, we also further optimize // // the Booth recoding by bit-pair recoding so that the number of zeros is // // increased and as many as possible additions can be skipped. // // Note that the Booth multiplier has depth O(M+N) and size O(M*N) and is thus// // not optimal and concerning the worst case complexity comparable to the // // paper-and-pencil methods. In practice, it is reported to behave better due // // to the high probability of numbers with small absolute values. Such numbers// // have 2-complement representations with large blocks of 1's or 0's so that // // the Booth multiplier can simply skip these blocks. // // ************************************************************************** // macro M = 5; // number of digits used macro N = 3; // number of digits used macro dval(x,i,k) = (i==k-1 ? -(x[i]?1:0) : (x[i]?1:0)); macro intval(x,k) = sum(i=0..k-1) (dval(x,i,k) * exp(2,i)); module IntMulBooth([M]bool ?x,[N]bool ?y,[M+N]bool p) { event [M]int{2} bx; // Booth recoding of x event [M]int{2} bpx; // bit-pair optimization of bx event [M-1][N]bool pp; // digits of partial products event [M][N-1]bool cp; // carries for summation event sM; // Booth encoding of x bx[0] = (x[0] ? -1 : 0); for(i=1..M-1) bx[i] = (x[i] <-> x[i-1] ? 0 : (x[i] ? -1 : +1)); // bit-pair optimization of Booth encoding for(i=0..(M/2)-1) case (bx[2*i+1] == +1 & bx[2*i] == -1) do { bpx[2*i+1] = 0; bpx[2*i] = +1; } (bx[2*i+1] == -1 & bx[2*i] == +1) do { bpx[2*i+1] = 0; bpx[2*i] = -1; } default { bpx[2*i+1] = bx[2*i+1]; bpx[2*i] = bx[2*i]; } if(2*(M/2) != M) bpx[M-1] = bx[M-1]; // construct M x N multiplier array for(i=0..M-1) { // IntAdd/IntSub of pp[i-1][N-1..0] and y[N-1..0] depending on bpx[i] for(j=0..N-1) { let(doSkp = bpx[i] == 0) let(doSub = bpx[i] == -1) let(yj = !doSkp & (doSub xor y[j])) let(xyin = (j==N-1 ? !yj : yj)) let(pin = (i==0 ? (j==N-1) : pp[i-1][j])) let(cin = (j==0 ? doSub : cp[i][j-1])) let(pout = (j==0 | i==M-1 ? p[i+j] : pp[i][j-1])) let(cout = (j==N-1 ? (i==M-1 ? sM : pp[i][N-1]) : cp[i][j])) FullAdd(xyin,pin,cin,cout,pout); } } p[M+N-1] = !sM; // check the result assert(intval(p,M+N) == intval(x,M) * intval(y,N)); }