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 ];