| << Chapter < Page | Chapter >> Page > |
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 constantsx = pfp([9,5],2,x); % prime factor permuationx = 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*1v = 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*7v = ID2I(1,5,v); % v = (I(1) kron D2 kron I(5)) * v a : 5=5*1
v = v.*u(5:19); % 15 Multiplicationsv = 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*1v = ID2I(3,1,v); % v = (I(3) kron D2 kron I(1)) * v a : 3=3*1
v = v.*u(20:28); % 9 Multiplicationsv = 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*1v = 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*1v = v.*u(29:55); % 27 Multiplications
v = ID2tI(1,9,v); % v = (I(1) kron D2' kron I(9)) * v a : 18=9*2v = 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*7v = 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*1v = ID2I(45,1,v); % v = (I(45) kron D2 kron I(1)) * v a : 45=45*1
v = v.*u(56:190); % 135 Multiplicationsv = 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*2v = 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*9y = 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
Notification Switch
Would you like to follow the 'Automatic generation of prime length fft programs' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|