| << Chapter < Page | Chapter >> Page > |
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 permutationy = zeros(31,1);
x = x(ip); % input permutationx(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)) * vv = v.*u(27:53);
v = ID2tI(1,9,v); % v = (I(1) kron D2' kron I(9)) * vv = 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)) * vv = v.*u(54:80);
v = ID2tI(1,9,v); % v = (I(1) kron D2' kron I(9)) * vv = 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 calculationy(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.0333333333333330.185592145427667*I
0.2510268729290940.638094290379888
-0.296373721102994-0.462201919825109*I
0.155909426230360*I0.102097497864916*I
-0.100498239164838-0.217421331841463
-0.3250821649557630.798589508696894
-0.780994042074251-0.256086011899669
0.1694943922209320.711997889018157
-0.060064820876732-1.235197570427205*I
-0.271691369288525*I0.541789612349592*I
0.329410560797314*I1.317497505049809*I
-0.599508803858381*I0.093899154219231*I
-0.176199088841836*I0.028003825226279*I
1.3166990503057901.330315270540553
-0.385122753006171-2.958666546021397
-2.5353019951462012.013474028487015
1.0818977311873960.136705213653014
-0.569390844064251-0.262247009112805
2.009855570455675-1.1593485997578570.629367699727360
1.229312102919654-1.479874670425178
-0.058279061554516-0.908786032252333
0.721257672797977-0.351484013730995
-1.1133902803320760.514823784254676
0.7764329487646790.435329964075516
-0.177866452687279-0.341206223210960
0.257360272866440-0.050622276244575
-2.745673340229639*I2.685177424507523*I
0.880463026400118*I-5.028851220636894*I
-0.345528375980267*I1.463210769729252*I
3.328421083558774*I-0.237219367348867*I
-1.086975102467855*I-1.665522956385442*I
1.628826188810638*I0.534088072762272*I
-3.050496586573981*I-0.209597199290132*I
0.887582325001072*I2.019017208624242*I
-0.143897052948668*I-0.659358110687783*I
1.470398765538361*I-1.438001204439387*I
-0.471517033054130*I2.693115935736959*I
0.185041858423467*I-0.783597698243441*I
-1.782479430727672*I0.127038806765845*I
0.582111071051880*I];% The input permutation for the 31 point FFT
ip = [1
217
95
326
2915
820
619
1021
1131
1624
2830
74
1825
1327
1423
1222
];
% The output permutation for the 31 point FFTop = [
131
302
2926
619
2823
259
57
1812
273
2220
2410
813
421
1114
1715
16];
Notification Switch
Would you like to follow the 'Automatic generation of prime length fft programs' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|