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 11. Appendix: A 31 Point FFT Program

Appendix: A 31 Point FFT Program

As an example, we list a 31 point FFT program.

function y = fft31(x,u,ip,op)
% y = fft31(x,u,ip,op)
% y  : the 31 point DFT of x 
% u  : a vector of precomputed multiplicative constants
% ip : input permutation
% op : ouput permutation

y = zeros(31,1);
x = x(ip);                                        % input permutation
x(2:31) = KRED([2,3,5],[1,1,1],3,x(2:31));        % reduction operations
y(1) = x(1)+x(2);                                 % DC term calculation
% -------------------- block : 1 -------------------------------------------------
y(2) = x(2)*u(1);                       
% -------------------- block : 2 -------------------------------------------------
y(3) = x(3)*u(2);                       
% -------------------- block : 3 -------------------------------------------------
v = ID2I(1,1,x(4:5));              % v = (I(1) kron D2 kron I(1)) * x(4:5)
v = v.*u(3:5);                          
y(4:5) = ID2tI(1,1,v);             % y(4:5) = (I(1) kron D2' kron I(1)) * v
% -------------------- block : 6 = 2 * 3 -----------------------------------------
v = ID2I(1,1,x(6:7));              % v = (I(1) kron D2 kron I(1)) * x(6:7)
v = v.*u(6:8);                          
y(6:7) = ID2tI(1,1,v);             % y(6:7) = (I(1) kron D2' kron I(1)) * v
% -------------------- block : 5 -------------------------------------------------
v = ID2I(1,2,x(8:11));             % v = (I(1) kron D2 kron I(2)) * x(8:11)
v = ID2I(3,1,v);                   % v = (I(3) kron D2 kron I(1)) * v
v = v.*u(9:17);                         
v = ID2tI(1,3,v);                  % v = (I(1) kron D2' kron I(3)) * v
y(8:11) = ID2tI(2,1,v);            % y(8:11) = (I(2) kron D2' kron I(1)) * v
% -------------------- block : 10 = 2 * 5 ----------------------------------------
v = ID2I(1,2,x(12:15));            % v = (I(1) kron D2 kron I(2)) * x(12:15)
v = ID2I(3,1,v);                   % v = (I(3) kron D2 kron I(1)) * v
v = v.*u(18:26);                        
v = ID2tI(1,3,v);                  % v = (I(1) kron D2' kron I(3)) * v
y(12:15) = ID2tI(2,1,v);           % y(12:15) = (I(2) kron D2' kron I(1)) * v
% -------------------- block : 15 = 3 * 5 ----------------------------------------
v = ID2I(1,4,x(16:23));            % v = (I(1) kron D2 kron I(4)) * x(16:23)
v = ID2I(3,2,v);                   % v = (I(3) kron D2 kron I(2)) * v
v = ID2I(9,1,v);                   % v = (I(9) kron D2 kron I(1)) * v
v = v.*u(27:53);                        
v = ID2tI(1,9,v);                  % v = (I(1) kron D2' kron I(9)) * v
v = ID2tI(2,3,v);                  % v = (I(2) kron D2' kron I(3)) * v
y(16:23) = ID2tI(4,1,v);           % y(16:23) = (I(4) kron D2' kron I(1)) * v
% -------------------- block : 30 = 2 * 3 * 5 ------------------------------------
v = ID2I(1,4,x(24:31));            % v = (I(1) kron D2 kron I(4)) * x(24:31)
v = ID2I(3,2,v);                   % v = (I(3) kron D2 kron I(2)) * v
v = ID2I(9,1,v);                   % v = (I(9) kron D2 kron I(1)) * v
v = v.*u(54:80);                        
v = ID2tI(1,9,v);                  % v = (I(1) kron D2' kron I(9)) * v
v = ID2tI(2,3,v);                  % v = (I(2) kron D2' kron I(3)) * v
y(24:31) = ID2tI(4,1,v);           % y(24:31) = (I(4) kron D2' kron I(1)) * v
% --------------------------------------------------------------------------------
y(2) = y(1)+y(2);                                 % DC term calculation
y(2:31) = tKRED([2,3,5],[1,1,1],3,y(2:31));       % transpose reduction operations
y = y(op);                                        % output permutation

% For complex data - 
% Total Number of Real Multiplications : 160
% Total Number of Real Additions: 776

The constants, input and output permutations are:

% The multiplicative constants for the 31 point FFT

I = sqrt(-1);
u = [
       -1.033333333333333
        0.185592145427667*I
        0.251026872929094
        0.638094290379888
       -0.296373721102994
       -0.462201919825109*I
        0.155909426230360*I
        0.102097497864916*I
       -0.100498239164838
       -0.217421331841463
       -0.325082164955763
        0.798589508696894
       -0.780994042074251
       -0.256086011899669
        0.169494392220932
        0.711997889018157
       -0.060064820876732
       -1.235197570427205*I
       -0.271691369288525*I
        0.541789612349592*I
        0.329410560797314*I
        1.317497505049809*I
       -0.599508803858381*I
        0.093899154219231*I
       -0.176199088841836*I
        0.028003825226279*I
        1.316699050305790
        1.330315270540553
       -0.385122753006171
       -2.958666546021397
       -2.535301995146201
        2.013474028487015
        1.081897731187396
        0.136705213653014
       -0.569390844064251
       -0.262247009112805
        2.009855570455675
       -1.159348599757857
        0.629367699727360
        1.229312102919654
       -1.479874670425178
       -0.058279061554516
       -0.908786032252333
        0.721257672797977
       -0.351484013730995
       -1.113390280332076
        0.514823784254676
        0.776432948764679
        0.435329964075516
       -0.177866452687279
       -0.341206223210960
        0.257360272866440
       -0.050622276244575
       -2.745673340229639*I
        2.685177424507523*I
        0.880463026400118*I
       -5.028851220636894*I
       -0.345528375980267*I
        1.463210769729252*I
        3.328421083558774*I
       -0.237219367348867*I
       -1.086975102467855*I
       -1.665522956385442*I
        1.628826188810638*I
        0.534088072762272*I
       -3.050496586573981*I
       -0.209597199290132*I
        0.887582325001072*I
        2.019017208624242*I
       -0.143897052948668*I
       -0.659358110687783*I
        1.470398765538361*I
       -1.438001204439387*I
       -0.471517033054130*I
        2.693115935736959*I
        0.185041858423467*I
       -0.783597698243441*I
       -1.782479430727672*I
        0.127038806765845*I
        0.582111071051880*I
];


% The input permutation for the 31 point FFT

ip = [
   1
   2
   17
   9
   5
   3
   26
   29
   15
   8
   20
   6
   19
   10
   21
   11
   31
   16
   24
   28
   30
   7
   4
   18
   25
   13
   27
   14
   23
   12
   22
];


% The output permutation for the 31 point FFT

op = [
   1
   31
   30
   2
   29
   26
   6
   19
   28
   23
   25
   9
   5
   7
   18
   12
   27
   3
   22
   20
   24
   10
   8
   13
   4
   21
   11
   14
   17
   15
   16
];

References

Solutions