Transformada Rápida de Fourier
para FPGA
Aluno: Arthur Umbelino Alves Rolim([email protected])
Orientador: Manoel Eusébio de Lima([email protected])
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
DIF(Decimation in Frequency)
outUP  inUP  inLOW
outLOW  w  (inUP  inLOW)
DIT(Decimation in Time)
outUP  inUP  w  inLOW
outLOW  inUP  w  inLOW
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
Modelo de
Referência
C++
Saída
Comparador
Entrada
Relatório
Simulador
HDL
Saída
Complex Adder
a
c
+
real
z1  a  bi
z2  c  di
b
d
+
imag
z1  z2  (a  c)  (b  d )i
Relatório de Síntese Complex Adder
•32 bits
Logic Utilization
Used
Available Utilization
Number of Slice Registers
1008
28800
3%
Number of Slice LUTs
1314
28800
4%
Frequência
303.538MHz
•64 bits
Logic Utilization
Used
Available Utilization
Number of Slice Registers
2098
28800
7%
Number of Slice LUTs
2702
28800
9%
Frequência
304.095MHz
Complex Multiplier
a
c
x
+
b
d
real
z1  a  bi
x
z2  c  di
a
d
x
b
c
x
z1  z2  (ac  bd)  (ad  bc)i
+
imag
Relatório de Síntese Complex Multiplier
•32 bits
Logic Utilization
Used
Available
Utilization
Number of Slice Registers
1256
28800
4%
Number of Slice LUTs
2252
28800
7%
16
48
33%
Number of DSP48Es
Frequência
173.136MHz
•64 bits
Logic Utilization
Used
Available
Utilization
Number of Slice Registers
3202
28800
11%
Number of Slice LUTs
6854
28800
23%
36
48
75%
Number of DSP48Es
Frequência
125.653MHz
ButterFly
z 'UP  zUP  z LOW
z 'LOW  w  ( zUP  z LOW )
zUP
z LOW
Complex
Adder
Complex
Adder
z'UP
w
Complex
Mult
z'LOW
Relatório de Síntese Butterfly
•32 bits
Logic Utilization
Used
Number of Slice Registers
3648
28800
12%
Number of Slice LUTs
4952
28800
17%
16
48
33%
Number of DSP48Es
Available Utilization
Frequência
173.136MHz
•64 bits
Logic Utilization
Used
Number of Slice Registers
8159
28800
28%
Number of Slice LUTs
12652
28800
43%
36
48
75%
Number of DSP48Es
Available Utilization
Frequência
125.653MHz
ButterFly (1,0)
z 'UP  zUP  z LOW
w  1  0i
z 'LOW  w  ( zUP  z LOW )  ( zUP  z LOW )
zUP
z LOW
Complex
Adder
z'UP
Complex
Adder
z'LOW
Relatório de Síntese Butterfly (1,0)
•32 bits
Logic Utilization
Used
Available Utilization
Number of Slice Registers
2392
28800
8%
Number of Slice LUTs
2832
28800
9%
Frequência
303.538MHz
•64 bits
Logic Utilization
Used
Available Utilization
Number of Slice Registers
4957
28800
17%
Number of Slice LUTs
5836
28800
20%
Frequência
304.095MHz
ButterFly (0,-1)
z 'UP  zUP  z LOW
w  0  1i
z 'LOW  w  ( zUP  z LOW )  i  ( zUP  z LOW ) 
 i  (a  bi)  (b  ai)
zUP
z LOW
Complex
Adder
z'UP
Complex
Adder
Change
z'LOW
Relatório de Síntese Butterfly (0,-1)
•32 bits
Logic Utilization
Used
Available Utilization
Number of Slice Registers
2392
28800
8%
Number of Slice LUTs
2832
28800
9%
Frequência
303.538MHz
•64 bits
Logic Utilization
Used
Available Utilization
Number of Slice Registers
4957
28800
17%
Number of Slice LUTs
5837
28800
20%
Frequência
304.095MHz
FFT8
Relatório de Síntese FFT8 32 bits
•Normal
Logic Utilization
Used
Available
Utilization
Number of Slice Registers
43336
28800
150%
Number of Slice LUTs
59771
28800
207%
48
48
100%
Number of DSP48Es
Frequência
162.633MHz
•Otimizado
Logic Utilization
Used
Available
Utilization
Number of Slice Registers
30718
28800
106%
Number of Slice LUTs
36653
28800
127%
32
48
66%
Number of DSP48Es
Frequência
172.662MHz
Relatório de Síntese FFT8 64 bits
•Normal
Logic Utilization
Used
Available
Utilization
Number of Slice Registers
91014
28800
316%
Number of Slice LUTs
141447
28800
491%
Frequência
48
48
100%
126.276MHz
Logic Utilization
Used
Available
Utilization
Number of Slice Registers
65474
28800
227%
Number of Slice LUTs
89650
28800
311%
Frequência
48
48
100%
172.662MHz
Number of DSP48Es
•Otimizado
Number of DSP48Es
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