// ************************************************************************** // // // // 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 computation is done by summing up the usual partial products by the use// // of carry-ripple adders both for the intermediate steps and the final step. // // The depth of the circuit is seen by observing that the evaluation can // // proceed diagonally through the array. Thus, the depth of the circuit // // is O(M+N) and therefore not optimal. // // ************************************************************************** // 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([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-1) { let(xyin = (i==M-1 xor j==N-1 ? !(x[i]&y[j]) : x[i]&y[j])) let(pin = (i==0 ? (j==N-1) : 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 = (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)); }