15th LSI Design Contests・in Okinawa  Design Specification - 4-2-3

4-2-3. FFT circuit : N=16

(1) Circuit design

Figure 32

Figure 32:  16 points FFT architecture

Figure 33

Figure 33:  Block diagram of 16 points FFT architecture for serial input

A serial input signal is delayed and carried into Butterfly arithmetic circuit. Then, system separates output signals of Butterfly processing circuit into required signals for calculating FFT and no required signals by using Multiplexer.

After that, required signals are carried into next Butterfly arithmetic circuit. A circuit which we have made is shown by figure 34.

Figure 34

Figure 34:  16 points FFT circuit for serial input


1) MUX_control

MUX Control block controls input signal carried into selector of multiplexer. Output signal of Multiplexer is decided by this control.

The sequence parameter is shown by figure 35.

Figure 35

Figure 35:  MUX_control sequence parameter

In figure 35, output signal from MUX_control varies on each step. The only signals required for FFT are sent to next Butterfly arithmetic circuit by the signal varying.


2) W_control

W_control is sequence representing twiddle factor W.

Butterfly arithmetic is done by varying W complex multiplied on each step.

Each W are…Symbol 1, Symbol 2, Symbol 3, Symbol 4, Symbol 5, Symbol 6, Symbol 7, Symbol 8 Sequence parameters are shown by table 9.

Table 9:  W_control sequence parameter

Table 9

In Table 9, Symbol 9 is expressed as 0.7071, Symbol 10 is expressed as 0.9239 and Symbol 11 is expressed as 0.3827.

In Figure 30, as will be noted from the Table 9, first step on MULT0 is multiplying by Symbol 12 and the next steps are multiplying by Symbol 13, Symbol 14, Symbol 15, Symbol 16, Symbol 17, Symbol 18, Symbol 19 in order. First step on MULT1 is multiplying by Symbol 12 and the next steps are multiplying by Symbol 14 Symbol 16 Symbol 18 in order. First step on MULT2 is multiplying by Symbol 12 and the next step are multiplying by Symbol 16 All steps on MULT3 is multiplying by Symbol 12

Timing diagram of 16-points FFT circuit for serial input is shown in Figure 36.

Figure 36

Figure 36:  Timing diagram of 16-points FFT circuit for serial input


(2) Verification　

A simulation result for input signals that x(0)=0+0j, x(1)=1+1j, x(2)=2+2j, x(3)=3+3j, x(4)=4+4j, x(5)=5+5j, x(6)=6+6j, x(7)=7+7j, x(8)=8+8j, x(9)=9+9j, x(10)=10+10j, x(11)=11+11j, x(12)=12+12j, x(13)=13+13j, x(14)=14+14j, x(15)=15+15j is shown in Figure 37.

Figure 37

Figure 37:  

Calculation results on MATLAB and the errors are shown in Table 10.

Figure 10:  Output waveform of 16-points FFT circuit for serial input

Table 10

By Figure 37, the Latency between an input and an output for this circuit is 15.

The verification of 16-points FFT circuit is making m-file for test, and calculation of mean square error (MSE) between result on MATLAB and result for circuit by random inputs a hundred times. The result is shown in Table 11.

Table 11:   Calculation result of MSE

Table 11

By the Verification, this 16-points FFT circuit perform that MSE of real part is Symbol 20、 and image part is Symbol 21