FFT em hardware¶
A FFT é o algoritmo que junta tudo o que a Parte V apresentou: números complexos, ponto flutuante dimensionado e um recurso que só o SAPHO tem na linguagem: o índice bit-reverso.
O problema do embaralhamento¶
A FFT radix-2 com decimação no tempo consome as amostras em ordem bit-reversa: para 8 pontos, a posição binária 001 vira 100, então x[1] é lido como x[4], e assim por diante. Em software comum, isso custa uma rotina de embaralhamento antes da transformada.
No SAPHO, o embaralhamento custa zero: a linguagem tem um modo de indexação que inverte os bits do índice no próprio hardware de endereçamento.
data[j] // acesso normal
data[j) // acesso com os bits de j invertidos
O parêntese no lugar do colchete final é a sintaxe. Quantos bits são invertidos é definido pela diretiva #FFTSIZ: para uma FFT de 8 pontos, #FFTSIZ 3 (diretivas no manual do YANC).
O programa¶
Crie um processador proc_fft (32 bits, mantissa 23, expoente 8) e escreva a FFT de 8 pontos:
1#NUBITS 32
2#NBMANT 23
3#NBEXPO 8
4#NDSTAC 8
5#SDEPTH 2
6#NUIOIN 1
7#NUIOOU 1
8#FFTSIZ 3
9
10#define N 8
11#define NL 3 // log2(N)
12
13void main()
14{
15 comp data[N];
16 comp tw, t, u;
17 int n, j, k, par, salto;
18 float ang;
19
20 while (1)
21 {
22 // carrega as amostras ja em ordem bit-reversa:
23 // data[n) grava na posicao com os bits de n invertidos
24 for (n = 0; n < N; n++)
25 {
26 data[n) = complex(fin(0), 0.0);
27 }
28
29 // as tres etapas de borboletas
30 salto = 1;
31 for (k = 0; k < NL; k++)
32 {
33 for (par = 0; par < N; par = par + 2 * salto)
34 {
35 for (j = 0; j < salto; j++)
36 {
37 ang = -3.14159265 * j / salto;
38 tw = exp(complex(0.0, ang));
39
40 u = data[par + j];
41 t = tw * data[par + j + salto];
42
43 data[par + j] = u + t;
44 data[par + j + salto] = u - t;
45 }
46 }
47 salto = salto * 2;
48 }
49
50 // publica o espectro: modulo de cada raia
51 for (n = 0; n < N; n++)
52 {
53 fout(0, abs(data[n]));
54 }
55 }
56}
Os pontos de atenção:
A linha 27 é o truque inteiro:
data[n)grava a amostranjá na posição embaralhada. Nenhuma rotina de reordenação, nenhum ciclo gasto.O índice de amostra se chama
n, e nãoi, porqueié reservado no C± e usá-lo como variável é erro de compilação (C± em uma página).O twiddle
twsai deexpcomplexo, que o compilador implementa por rotina. Uma versão otimizada usaria uma tabela pré-calculada em arquivo (comp tw[4] "twiddles.txt"não existe paracomp; use dois vetoresfloatcom as partes real e imaginária), bom exercício para a turma.absde complexo devolve o módulo, direto para a saída.
Verificando¶
Alimente input_0.txt com 8 amostras de uma senoide que caiba em um período da janela e simule. No espectro de saída, duas raias simétricas devem se destacar. Compare com o numpy.fft.fft das mesmas amostras: os módulos devem bater dentro do erro do formato de ponto flutuante escolhido, o que fecha o laço com o capítulo de ponto flutuante.
Para tamanhos maiores, ajuste N, NL e #FFTSIZ juntos, e acompanhe no TASM o crescimento do programa.
Ver também
O índice bit-reverso nasceu de um projeto de processador dedicado à FFT: Projeto de um Processador Embarcado Otimizado para Aplicação com Transformada de Fourier (2016).