64-point radix-2 fixed-point DIF FFT IV-KAT Tables



John Bryan





Table of Contents
Introduction
Input data Twiddle factors
P,b,n is the butterfly corresponding to loop P, sub-block b, butterfly n.
0,0,0 0,0,1 0,0,2 0,0,3 0,0,4 0,0,5 0,0,6 0,0,7 0,0,8 0,0,9 0,0,10 0,0,11 0,0,12 0,0,13 0,0,14 0,0,15
0,0,16 0,0,17 0,0,18 0,0,19 0,0,20 0,0,21 0,0,22 0,0,23 0,0,24 0,0,25 0,0,26 0,0,27 0,0,28 0,0,29 0,0,30 0,0,31
Data x after loop P=0
1,0,0 1,0,1 1,0,2 1,0,3 1,0,4 1,0,5 1,0,6 1,0,7 1,0,8 1,0,9 1,0,10 1,0,11 1,0,12 1,0,13 1,0,14 1,0,15
1,1,0 1,1,1 1,1,2 1,1,3 1,1,4 1,1,5 1,1,6 1,1,7 1,1,8 1,1,9 1,1,10 1,1,11 1,1,12 1,1,13 1,1,14 1,1,15
Data x after loop P=1
2,0,0 2,0,1 2,0,2 2,0,3 2,0,4 2,0,5 2,0,6 2,0,7 2,1,0 2,1,1 2,1,2 2,1,3 2,1,4 2,1,5 2,1,6 2,1,7
2,2,0 2,2,1 2,2,2 2,2,3 2,2,4 2,2,5 2,2,6 2,2,7 2,3,0 2,3,1 2,3,2 2,3,3 2,3,4 2,3,5 2,3,6 2,3,7
Data x after loop P=2
3,0,0 3,0,1 3,0,2 3,0,3 3,1,0 3,1,1 3,1,2 3,1,3 3,2,0 3,2,1 3,2,2 3,2,3 3,3,0 3,3,1 3,3,2 3,3,3
3,4,0 3,4,1 3,4,2 3,4,3 3,5,0 3,5,1 3,5,2 3,5,3 3,6,0 3,6,1 3,6,2 3,6,3 3,7,0 3,7,1 3,7,2 3,7,3
Data x after loop P=3
4,0,0 4,0,1 4,1,0 4,1,1 4,2,0 4,2,1 4,3,0 4,3,1 4,4,0 4,4,1 4,5,0 4,5,1 4,6,0 4,6,1 4,7,0 4,7,1
4,8,0 4,8,1 4,9,0 4,9,1 4,10,0 4,10,1 4,11,0 4,11,1 4,12,0 4,12,1 4,13,0 4,13,1 4,14,0 4,14,1 4,15,0 4,15,1
Data x after loop P=4
5,0,0 5,1,0 5,2,0 5,3,0 5,4,0 5,5,0 5,6,0 5,7,0 5,8,0 5,9,0 5,10,0 5,11,0 5,12,0 5,13,0 5,14,0 5,15,0
5,16,0 5,17,0 5,18,0 5,19,0 5,20,0 5,21,0 5,22,0 5,23,0 5,24,0 5,25,0 5,26,0 5,27,0 5,28,0 5,29,0 5,30,0 5,31,0
Data x after loop P=5
Bit Reversal Data x after bit reversal





Introduction
  • Algorithm is 64-point radix-2 16-bit fixed-point DIF FFT.
  • Fixed-point representation is Q15.
  • The 64 real and imaginary data pairs are stored in 16-bit 128-location random-access memory x.  Even-index locations hold the real parts; adjacent odd-index locations hold the corresponding imaginary parts.
  • Notation
    • P index is the loop index, indexed P=0...5.
    • b index is the sub-block index in a given loop, which for a given loop index P is indexed b=0...2P-1.
    • n index is butterfly index in a given sub-block, which for a given loop index P is indexed n=0...25-P-1.
  • Twiddle factors are stored in read-only memory t with 64 memory locations, indexed 0...63.  The even-index locations hold the negative of the real part of the twiddle factor. t[2n]=-cos(2πn/64).  The reason for holding the negative of the real part is to maintain greater fixed-point accuracy in the calculations using t[0] since the range for Q15 is [-1...1-2-15]. The odd-index locations hold the imaginary part of the twiddle factor.  t[2n+1]=-sin(2πn/64).
  • The 16-bit data values are extended to 17 bits for the butterfly calculations; at the end of each butterfly calculation the data values are divided by 2 to store in the corresponding 16-bit memory location. Hence, in the data values at the end of the final sixth stage of the FFT there is a 2-6 scaling factor difference from the desired FFT value.
  • Even-base index e=2Npb with b=sub-block index and Np=the size of a sub-block.
  • Odd-base index o=e+Np with Np=the size of a sub-block.
  • Twiddle factor step size s=2P+1 to account for the decrease by a factor of 2 of sub-block size for each increment in the pass index.
  • The input data:
    • Real component x[2n]=0.125 sin(2πn/4).
    • Imaginary component x[2n+1]=0.



Input data
x[0]=0000 x[1]=0000
x[2]=1000 x[3]=0000
x[4]=0000 x[5]=0000
x[6]=f000 x[7]=0000
x[8]=0000 x[9]=0000
x[10]=1000 x[11]=0000
x[12]=0000 x[13]=0000
x[14]=f000 x[15]=0000
x[16]=0000 x[17]=0000
x[18]=1000 x[19]=0000
x[20]=0000 x[21]=0000
x[22]=f000 x[23]=0000
x[24]=0000 x[25]=0000
x[26]=1000 x[27]=0000
x[28]=0000 x[29]=0000
x[30]=f000 x[31]=0000
x[32]=0000 x[33]=0000
x[34]=1000 x[35]=0000
x[36]=0000 x[37]=0000
x[38]=f000 x[39]=0000
x[40]=0000 x[41]=0000
x[42]=1000 x[43]=0000
x[44]=0000 x[45]=0000
x[46]=f000 x[47]=0000
x[48]=0000 x[49]=0000
x[50]=1000 x[51]=0000
x[52]=0000 x[53]=0000
x[54]=f000 x[55]=0000
x[56]=0000 x[57]=0000
x[58]=1000 x[59]=0000
x[60]=0000 x[61]=0000
x[62]=f000 x[63]=0000
x[64]=0000 x[65]=0000
x[66]=1000 x[67]=0000
x[68]=0000 x[69]=0000
x[70]=f000 x[71]=0000
x[72]=0000 x[73]=0000
x[74]=1000 x[75]=0000
x[76]=0000 x[77]=0000
x[78]=f000 x[79]=0000
x[80]=0000 x[81]=0000
x[82]=1000 x[83]=0000
x[84]=0000 x[85]=0000
x[86]=f000 x[87]=0000
x[88]=0000 x[89]=0000
x[90]=1000 x[91]=0000
x[92]=0000 x[93]=0000
x[94]=f000 x[95]=0000
x[96]=0000 x[97]=0000
x[98]=1000 x[99]=0000
x[100]=0000 x[101]=0000
x[102]=f000 x[103]=0000
x[104]=0000 x[105]=0000
x[106]=1000 x[107]=0000
x[108]=0000 x[109]=0000
x[110]=f000 x[111]=0000
x[112]=0000 x[113]=0000
x[114]=1000 x[115]=0000
x[116]=0000 x[117]=0000
x[118]=f000 x[119]=0000
x[120]=0000 x[121]=0000
x[122]=1000 x[123]=0000
x[124]=0000 x[125]=0000
x[126]=f000 x[127]=0000



Return to Table of Contents



Twiddle factors
t[0]=8000 t[1]=0000
t[2]=809d t[3]=f374
t[4]=8275 t[5]=e707
t[6]=8582 t[7]=dad7
t[8]=89be t[9]=cf04
t[10]=8f1d t[11]=c3a9
t[12]=9592 t[13]=b8e3
t[14]=9d0d t[15]=aecc
t[16]=a57d t[17]=a57d
t[18]=aecc t[19]=9d0d
t[20]=b8e3 t[21]=9592
t[22]=c3a9 t[23]=8f1d
t[24]=cf04 t[25]=89be
t[26]=dad7 t[27]=8582
t[28]=e707 t[29]=8275
t[30]=f374 t[31]=809d
t[32]=ffff t[33]=8000
t[34]=0c8b t[35]=809d
t[36]=18f8 t[37]=8275
t[38]=2528 t[39]=8582
t[40]=30fb t[41]=89be
t[42]=3c56 t[43]=8f1d
t[44]=471c t[45]=9592
t[46]=5133 t[47]=9d0d
t[48]=5a82 t[49]=a57d
t[50]=62f2 t[51]=aecc
t[52]=6a6d t[53]=b8e3
t[54]=70e2 t[55]=c3a9
t[56]=7641 t[57]=cf04
t[58]=7a7d t[59]=dad7
t[60]=7d8a t[61]=e707
t[62]=7f62 t[63]=f374



Return to Table of Contents