// ************************************************************************** // // // // 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. // // The algorithm is essentially the same as in IntMulCRACRA_V0, except that // // several redundant negations have been eliminated: it can be seen in the // // algorithm IntMulCRACRA_V0 that the carry outputs of the leftmost full // // adders are first negated and their only use as inputs in these full adders // // also negates these values. Thus, we can restrict the negation to the pin // // input of the uppermost leftmost full adder, and the pout output of the // // lowest leftmost full adder. // // ************************************************************************** // 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 IntMulCRACRA_V1([M]bool ?x,[N]bool ?y,[M+N]bool p) { event [M-1][N]bool pp; // digits of partial products event [M][N-1]bool cp; // carries for summation event sM; // construct M x N multiplier array for(i=0..M-1) { // IntAdd/IntSub of pp[i-1][N-1..0] and x[i]&y[N-1..0] for(j=0..N-2) { let(xyin = (i==M-1 ? !(x[i]&y[j]) : x[i]&y[j])) let(pin = (i==0 ? false : pp[i-1][j])) let(cin = (j==0 ? (i==M-1) : cp[i][j-1])) let(pout = (j==0 | i==M-1 ? p[i+j] : pp[i][j-1])) let(cout = cp[i][j]) FullAdd(xyin,pin,cin,cout,pout); } // most significant digits pp[i-1][N-1] and x[i]&y[N-1] let(xyin = (i==M-1 ? x[M-1]&y[N-1] : !(x[i]&y[N-1]))) let(pin = (i==0 ? true : pp[i-1][N-1])) let(cin = cp[i][N-2]) let(pout = (i==M-1 ? p[M+N-2] : pp[i][N-2])) let(cout = (i==M-1 ? sM : pp[i][N-1])) 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)); }