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:

Listagem 10 proc_fft.cmm, FFT radix-2 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 amostra n já na posição embaralhada. Nenhuma rotina de reordenação, nenhum ciclo gasto.

  • O índice de amostra se chama n, e não i, porque i é reservado no C± e usá-lo como variável é erro de compilação (C± em uma página).

  • O twiddle tw sai de exp complexo, 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 para comp; use dois vetores float com as partes real e imaginária), bom exercício para a turma.

  • abs de complexo devolve o módulo, direto para a saída.

Editor com o codigo da FFT mostrando o indice bit-reverso e a diretiva FFTSIZ.

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).