| Japanese | English |

# 15th LSI Design ContestsEin Okinawa Design Specification - 3-3

## Radix-2 algorithm

3. Radix-2 algorithmWe talk about Radix-2 algorithm and butterfly computation. It shows fourier transform result of X(k) in last chapter.

Their formulas are coordinated of even or odd at sigma, as (3.1)

One FFT can divide two FFT at N even and N odd.

NIf N is power of 2, it can divide FFT and more. Finally, it divide several FFT(butterfly computation) of N=2. This is Radix-2 algorithm. Its algorithm usually reduce of calculation, reason of using complex adder-subtractor only.

Fig.1 shows butterfly computation circuit using of butterfly computation.

Fig.2 shows calculation flow about discrete fourier coefficient of N =4. Note,

under the arrow of -1 is subtraction, twiddle factor at the top of line is multiplication.

Calculated results used of are changed (3.3) ,(3.4), (3.5), (3.6). Their results equal DFT results.