Thursday, May 31, 2012

A 45 Point Circular Convolution Program


A 45 Point Circular Convolution Program


A 45 Point Circular Convolution Program

As an example, we list a 45 point circular convolution program.
function y = cconv45(x,u) % y = ccconv45(x,u) % y : the 45 point circular convolution of x and h % where u is a vector of precomputed multiplicative constants  x = pfp([9,5],2,x);                % prime factor permuation x = KRED([3,5],[2,1],2,x);         % reduction operations (152 Additions) y = zeros(45,1); % -------------------- block : 1 ------------------------------------------------- y(1) = x(1)*u(1);             % 1 Multiplication % -------------------- block : 3 ------------------------------------------------- v = ID2I(1,1,x(2:3));         % v = (I(1) kron D2 kron I(1)) * x(2:3)           a : 1=1*1 v = v.*u(2:4);                % 3 Multiplications y(2:3) = ID2tI(1,1,v);        % y(2:3) = (I(1) kron D2' kron I(1)) * v          a : 2=1*2 % -------------------- block : 9 ------------------------------------------------- v = ID3I(2,1,x(4:9));         % v = (I(2) kron D3 kron I(1)) * x(4:9)           a : 14=2*7 v = ID2I(1,5,v);              % v = (I(1) kron D2 kron I(5)) * v                a : 5=5*1 v = v.*u(5:19);               % 15 Multiplications v = ID2tI(1,5,v);             % v = (I(1) kron D2' kron I(5)) * v               a : 10=5*2 y(4:9) = ID3tI(2,1,v);        % y(4:9) = (I(2) kron D3' kron I(1)) * v          a : 18=2*9 % -------------------- block : 5 ------------------------------------------------- v = ID2I(1,2,x(10:13));       % v = (I(1) kron D2 kron I(2)) * x(10:13)         a : 2=2*1 v = ID2I(3,1,v);              % v = (I(3) kron D2 kron I(1)) * v                a : 3=3*1 v = v.*u(20:28);              % 9 Multiplications v = ID2tI(1,3,v);             % v = (I(1) kron D2' kron I(3)) * v               a : 6=3*2 y(10:13) = ID2tI(2,1,v);      % y(10:13) = (I(2) kron D2' kron I(1)) * v        a : 4=2*2 % -------------------- block : 15 = 3 * 5 ---------------------------------------- v = ID2I(1,4,x(14:21));       % v = (I(1) kron D2 kron I(4)) * x(14:21)         a : 4=4*1 v = ID2I(3,2,v);              % v = (I(3) kron D2 kron I(2)) * v                a : 6=6*1 v = ID2I(9,1,v);              % v = (I(9) kron D2 kron I(1)) * v                a : 9=9*1 v = v.*u(29:55);              % 27 Multiplications v = ID2tI(1,9,v);             % v = (I(1) kron D2' kron I(9)) * v               a : 18=9*2 v = ID2tI(2,3,v);             % v = (I(2) kron D2' kron I(3)) * v               a : 12=6*2 y(14:21) = ID2tI(4,1,v);      % y(14:21) = (I(4) kron D2' kron I(1)) * v        a : 8=4*2 % -------------------- block : 45 = 9 * 5 ---------------------------------------- v = ID3I(2,4,x(22:45));       % v = (I(2) kron D3 kron I(4)) * x(22:45)         a : 56=8*7 v = ID2I(1,20,v);             % v = (I(1) kron D2 kron I(20)) * v               a : 20=20*1 v = ID2I(15,2,v);             % v = (I(15) kron D2 kron I(2)) * v               a : 30=30*1 v = ID2I(45,1,v);             % v = (I(45) kron D2 kron I(1)) * v               a : 45=45*1 v = v.*u(56:190);             % 135 Multiplications v = ID2tI(1,45,v);            % v = (I(1) kron D2' kron I(45)) * v              a : 90=45*2 v = ID2tI(10,3,v);            % v = (I(10) kron D2' kron I(3)) * v              a : 60=30*2 v = ID2tI(20,1,v);            % v = (I(20) kron D2' kron I(1)) * v              a : 40=20*2 y(22:45) = ID3tI(2,4,v);      % y(22:45) = (I(2) kron D3' kron I(4)) * v        a : 72=8*9  y = tKRED([3,5],[2,1],2,y);        % transpose reduction operations (152 Additions) y = pfpt([9,5],2,y);               % prime factor permuation y = y(45:-1:1);  % Total Number of Multiplications : 190 % Total Number of Additions: 839 

No comments:

Post a Comment