Automatic Generation of Prime Length FFT Programs by C. Sidney Burrus - HTML preview

/ Home / Mathematics (Academic) / Automatic Generation of Prime Length FFT Programs

PLEASE NOTE: This is an HTML preview only and some elements such as links or page numbers may be incorrect.
Download the book in PDF, ePub, Kindle for a complete version.

Chapter 10. Appendix: A 45 Point Circular Convolution Program

Appendix: 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

References

Solutions