Application Center - Maplesoft
  Submit your work
Application Center Applications Wallace Tree Decoder Preview

App Preview:

Wallace Tree Decoder

You can switch back to the summary page by clicking here.

Learn about Maple
Download Application

 

Wallace Tree Decoder

Ron Dotson, (c) May 23, 2003

> with (Logic):
Environment(2):
# 3-bit Decoder (3 inputs, 2 outputs)
# Out1:= &xor(i1,i2,i3);                           # LSB
# Out2:= &or(&and(i1,i2),&and(i1,i3),&and(i2,i3)); # MSB
# ______________________________________________________
# 'decode' Creates subsequent stages of a Wallace Tree Decoder
# from elements in the input list, and returns either a single
# element, or a two element nested list in which the first list
# element is the LSB (2^0) bit of the decoded count, and the
# second list element is itself a list of the carries generated
# for bit position 2^1. The last element of the input list 'inL'
# must itself be a list of prior carries into the MSB position of
# the two bits being output, which will be appended to by 'decoder'.
# Called by: decoder
#
decode:= proc(inL::list)::list; # LSB = inL[1]
 local N::integer, n::integer, i::integer:
 global S, Cy;
 use Logic in
 S:=[];
 Cy:=[];
 n:= nops(inL)-1;    # ignore the sublist on the MSB end
 #print(`decode: n=`,n);
 #print(`decode: inL=`,inL);
 ASSERT(n>0,`Error(decode): Parameter list empty`);
 if n<=3 then
   if n=1 then        # one LSB (nothing to decode)
     return inL;
   elif n=2 then      # two LSBs
     return [&xor(inL[1],inL[2]),[&and(inL[1],inL[2]),op(inL[3])]];
   else               # three LSBs
     return [&xor(inL[1],inL[2],inL[3]),[&or(&and(inL[1],inL[2]),&and(inL[1],inL[3]),&and(inL[2],inL[3])),op(inL[4])]];
   fi;
 fi;
 for i from 1 by 3 while n>3 do
           S:= [op(S),&xor(inL[i],inL[i+1],inL[i+2])];                                     # LSB
           Cy:= [op(Cy),&or(&and(inL[i],inL[i+1]),&and(inL[i],inL[i+2]),&and(inL[i+1],inL[i+2]))]; # MSB
   n:= n - 3;
 od;
 if n=1 then        # one remaining LSB
   ASSERT(i+1 = nops(inL),`Error(decode): i+1 = nops(inL) FAILED`);
   S:= [op(S),inL[i]];
   Cy:= [op(Cy),false];
 elif n=2 then      # two LSBs
   ASSERT(i+2 = nops(inL),`Error(decode): i+2 = nops(inL) FAILED`);
   S:= [op(S),&xor(inL[i],inL[i+1])];
   Cy:= [op(Cy),&and(inL[i],inL[i+1])];
 else               # three LSBs
   ASSERT(i+3 = nops(inL),`Error(decode): i+3 = nops(inL) FAILED`);
   S:= [op(S),&xor(inL[i],inL[i+1],inL[i+2])];
   Cy:= [op(Cy),&or(&and(inL[i],inL[i+1]),&and(inL[i],inL[i+2]),&and(inL[i+1],inL[i+2]))];
 fi;
 return decode([op(S),[op(Cy),op(inL[nops(inL)])]]);
 end use;
end proc:                           # decode


# ______________________________________________________
# 'decoder' Creates the first stage of a Wallace Tree Decoder from
# elements in the input list, and returns either a single element, or
# a two element nested list in which the first list element is the
# LSB (2^0) bit of the decoded count, and the second list element
# is itself a list of the carries generated for bit position 2^1.
# Calls: decode
#
decoder:= proc(inL::list)::list; # LSB = inL[1]
 local N::integer, n::integer, i::integer, j::integer, car;
 global S, Cy, U;
 use Logic in
 S:=[];
 Cy:=[];
 n:= nops(inL);
 #print(`decoder: n=`,n);
 #print(`decoder: inL=`,inL);
 ASSERT(n>0,`Error(decoder): Parameter list empty`);
 if n<=3 then
   if n=1 then
     return inL;
   elif n=2 then
     ASSERT(nops(&and(inL[1],inL[2]))=2,`Error(decoder): nops(&and(inL[1],inL[2]))=2 FAILED`);
             return [&xor(inL[1],inL[2]),[&and(inL[1],inL[2])]];
   else  # n=3
             car:= &or(&and(inL[1],inL[2]),&and(inL[1],inL[3]),&and(inL[2],inL[3])); # MSB
             return [&xor(inL[1],inL[2],inL[3]),[car]];
   fi;
 fi;
 for i from 1 by 3 while n>3 do
           S:= [op(S),&xor(inL[i],inL[i+1],inL[i+2])];                                     # LSB
           Cy:= [op(Cy),&or(&and(inL[i],inL[i+1]),&and(inL[i],inL[i+2]),&and(inL[i+1],inL[i+2]))]; # MSB
   n:= n - 3;
 od;
 if n=1 then        # one remaining LSB
   S:= [op(S),inL[i]];
   Cy:= [op(Cy),false];
 elif n=2 then      # two LSBs
   S:= [op(S),&xor(inL[i],inL[i+1])];
   Cy:= [op(Cy),&and(inL[i],inL[i+1])];
 else               # three LSBs
   S:= [op(S),&xor(inL[i],inL[i+1],inL[i+2])];
   Cy:= [op(Cy),&or(&and(inL[i],inL[i+1]),&and(inL[i],inL[i+2]),&and(inL[i+1],inL[i+2]))];
 fi;
 U:= decode([op(S),Cy]);               # Cy is already a list
 ASSERT(nops(U)<=2);
 if nops(U)=1 then
   return [U[1]];
 else                                 # nops(U)=2
   if type(U[2],list) then
     return [U[1],op(decode(U[2]))];  # decode sublist and return w/o sublist
   else
     return [op(decoder([U[1],U[2]]))]; # else NO sublist
   fi;
 fi;
 end use;
end proc:                           # decoder


# ______________________________________________________
wallace:= proc(inL::list)::list; # LSB = inL[1]
 local R::list, r;
 use Logic in
 R:= decoder(inL);
 r:= R[nops(R)];
 if type(r,list) then
   R:= subsop(nops(R)=seq(r[i],i=1..nops(r)),R)
 fi;
 return R;
 end use;
end proc: # wallace

> Result1:= wallace([a1,b1]);

Result1 := [`&or`(`&and`(a1, `¬`(b1)), `&and`(b1, `¬`(a1))), `&and`(a1, b1)]

> Result2:= wallace([true,true,false,true,false,true,true,false,true]); # count number of one bits in parameter list

Result2 := [false, false, true, true]

> Result3:= wallace([m,n,o,p,q,r]);

Result3 := [`&or`(`&and`(`&or`(`&and`(m, `¬`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))))), `&and`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))), `¬`(m))), `¬`(`&or`(`&and`(p, `¬...Result3 := [`&or`(`&and`(`&or`(`&and`(m, `¬`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))))), `&and`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))), `¬`(m))), `¬`(`&or`(`&and`(p, `¬...Result3 := [`&or`(`&and`(`&or`(`&and`(m, `¬`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))))), `&and`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))), `¬`(m))), `¬`(`&or`(`&and`(p, `¬...Result3 := [`&or`(`&and`(`&or`(`&and`(m, `¬`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))))), `&and`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))), `¬`(m))), `¬`(`&or`(`&and`(p, `¬...Result3 := [`&or`(`&and`(`&or`(`&and`(m, `¬`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))))), `&and`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))), `¬`(m))), `¬`(`&or`(`&and`(p, `¬...Result3 := [`&or`(`&and`(`&or`(`&and`(m, `¬`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))))), `&and`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))), `¬`(m))), `¬`(`&or`(`&and`(p, `¬...Result3 := [`&or`(`&and`(`&or`(`&and`(m, `¬`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))))), `&and`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))), `¬`(m))), `¬`(`&or`(`&and`(p, `¬...Result3 := [`&or`(`&and`(`&or`(`&and`(m, `¬`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))))), `&and`(`&or`(`&and`(n, `¬`(o)), `&and`(o, `¬`(n))), `¬`(m))), `¬`(`&or`(`&and`(p, `¬...

>