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
0 comments:
Post a Comment