Transformada Rápida de Fourierpara FPGA

Aluno: Arthur Umbelino Alves Rolim(auar@cin.ufpe.br)

Orientador: Manoel Eusébio de Lima(mel@cin.ufpe.br)

Roteiro

• FFT• FloPoCo• Trabalho realizado

– Test Bench– Complex Adder– Complex Multiplier– Butterfly– Butterfly (1,0)– Butterfly (0,-1)– FFT8

• Trabalho a ser realizado

Fast Fourier Transform(FFT)

• Maneira mais eficiente de calcular um DFT com complexidade O(nlogn )

• Domínio do Tempo -> Domínio da Freqüência• Uma família de algoritmos

– Cooley-Tukey– Prime-factor– Bruun's– Rader's– Bluestein's

Fast Fourier Transform(FFT)

• Extensivamente utilizada em várias aplicações de DSP– Análise de espectro– Convolução de alta-velocidade (filtro linear)– Detecção e estimativa de sinais– Identificação de sistemas– Compressão de áudio– Síntese de modelo espectral de som

FFT

Radix-2 FFT

• Diagrama Borboleta

)( inLOWinUPwoutLOW

inLOWinUPoutUP

inLOWwinUPoutLOW

inLOWwinUPoutUP

DIF(Decimation in Frequency)

DIT(Decimation in Time)

FloPoCo (Floating-Point Cores)

• Gerador de cores aritméticos em VHDL com opções de:– Frequência– Fabricante do FPGA( Altera ou Xilinx )– Pipeline– Uso ou não de blocos DSP

• Padrão IEEE e LNS (logarithm number system)• Implementa todas as operações(+,*,/,sqr)• Parametrizada( tamanho de expoente e mantissa

variáveis )• Tratamento de exceções(+∞,-∞,NaN)

Trabalho realizado

• Implementação dos algoritmos de DFT e FFT em C++

• Construção do modelo de referência em SystemC

• Testes na biblioteca FloPoCo• Construção dos blocos básicos da FFT no FPGA• Geração de test benchs• Construção da FFT

Test bench

Entrada

Modelo deReferência

C++

Simulador HDL

Saída

Saída

Comparador

Relatório

idbcazz

dicz

biaz

)()(21

2

1

+

+

a

c

b

d

real

imag

Complex Adder

Relatório de Síntese Complex Adder

Logic Utilization Used Available

Utilization

Number of Slice Registers 1008 28800 3%

Number of Slice LUTs 1314 28800 4%

•32 bits

•64 bits

Frequência

303.538MHz

Frequência

304.095MHz

Logic Utilization Used

Available

Utilization

Number of Slice Registers 2098

28800 7%

Number of Slice LUTs 2702

28800 9%

Complex Multiplier

ibcadbdaczz

dicz

biaz

)()(21

2

1

x

x

+

+x

x

a

c

b

d

a

d

b

c

real

imag

Relatório de Síntese Complex Multiplier

•32 bits

•64 bits

Frequência

173.136MHz

Frequência

125.653MHz

Logic Utilization Used Available

Utilization

Number of Slice Registers 1256 28800 4%

Number of Slice LUTs 2252 28800 7%

Number of DSP48Es 16 48 33%

Logic Utilization Used Available

Utilization

Number of Slice Registers 3202 28800 11%

Number of Slice LUTs 6854 28800 23%

Number of DSP48Es 36 48 75%

)('

'

LOWUPLOW

LOWUPUP

zzwz

zzz

ComplexAdder

ComplexMult

ComplexAdder

UPz

LOWz

w

UPz'

LOWz'

ButterFly

Relatório de Síntese Butterfly

•32 bits

•64 bits

Frequência

173.136MHz

Frequência

125.653MHz

Logic Utilization Used

Available

Utilization

Number of Slice Registers 3648

28800 12%

Number of Slice LUTs 4952

28800 17%

Number of DSP48Es 16 48 33%

Logic Utilization Used Available

Utilization

Number of Slice Registers 8159 28800 28%

Number of Slice LUTs 12652

28800 43%

Number of DSP48Es 36 48 75%

)()('

01

'

LOWUPLOWUPLOW

LOWUPUP

zzzzwz

iw

zzz

ComplexAdder

ComplexAdder

UPz

LOWz

UPz'

LOWz'

ButterFly (1,0)

Relatório de Síntese Butterfly (1,0)

•32 bits

•64 bits

Frequência

303.538MHz

Frequência

304.095MHz

Logic Utilization Used

Available

Utilization

Number of Slice Registers 2392

28800 8%

Number of Slice LUTs 2832

28800 9%

Logic Utilization Used

Available

Utilization

Number of Slice Registers 4957

28800 17%

Number of Slice LUTs 5836

28800 20%

)()(

)()('

10

'

aibbiai

zzizzwz

iw

zzz

LOWUPLOWUPLOW

LOWUPUP

ButterFly (0,-1)

ComplexAdder

ComplexAdder

UPz

LOWz

UPz'

LOWz'Change

Relatório de Síntese Butterfly (0,-1)

•32 bits

•64 bits

Frequência

303.538MHz

Frequência

304.095MHz

Logic Utilization Used

Available

Utilization

Number of Slice Registers 2392

28800 8%

Number of Slice LUTs 2832

28800 9%

Logic Utilization Used

Available

Utilization

Number of Slice Registers 4957

28800 17%

Number of Slice LUTs 5837

28800 20%

FFT8

Relatório de Síntese FFT8 32 bits

•Normal

•Otimizado

Frequência

162.633MHz

Frequência

172.662MHz

Logic Utilization Used Available

Utilization

Number of Slice Registers 43336 28800 150%

Number of Slice LUTs 59771 28800 207%

Number of DSP48Es 48 48 100%

Logic Utilization Used Available

Utilization

Number of Slice Registers 30718 28800 106%

Number of Slice LUTs 36653 28800 127%

Number of DSP48Es 32 48 66%

Relatório de Síntese FFT8 64 bits

•Normal

•Otimizado

Frequência

126.276MHz

Frequência

172.662MHz

Logic Utilization Used Available Utilization

Number of Slice Registers 91014 28800 316%

Number of Slice LUTs 141447 28800 491%

Number of DSP48Es 48 48 100%

Logic Utilization Used Available

Utilization

Number of Slice Registers 65474 28800 227%

Number of Slice LUTs 89650 28800 311%

Number of DSP48Es 48 48 100%

Quantidade de Blocos Aritméticos

Op. de ponto flutuante

FFT-2 FFT-4 FFT-8

Somadores 6 24 72

Multiplicadores 4 12 48

Somadores Ot. 4 16 52

Multiplicadores Ot.

0 0 8

Trabalho a ser realizado

• Finalizar implementação de um case para validação

• Finalizar escrita da dissertação

Dúvidas