3.2 Limiting Factors
3.2.5 Vibration
Nesta seção vamos estudar dois algoritmos rápidos para o cálculo da transformada de Fourier e da transformada Z em pontos de amostra igualmente espaçados. Começaremos estudando a Transformada Rápida de Fourier (FFT – fast Fourier transform) e depois veremos um caso mais geral que é o da transformada Z CHIRP (CZT – chirp z-transform).
4.1.1 Transformada Rápida de Fourier – FFT
A transformada rápida de Fourier (FFT) é um conjunto de algoritmos que pode calcular a transformada discreta de Fourier (DFT) muito mais rapidamente do que o cálculo direto. Por esta razão, nossa discussão da FFT é endereçada apenas ao aspecto computacional do algoritmo. Vamos nos restringir à versão de COOLEY E TUKEY (1965) do algoritmo em BRIGHAM (1974).
Nesta subseção, primeiro construímos o algoritmo FFT para qualquer , com avaliado nos inteiros, e depois fazemos uma generalização para em que é um inteiro. Veremos que esses algoritmos resultam em uma enorme economia do tempo de computação.
4.1.1.1 Para valores de
Vimos que a transformada discreta de Fourier é dada por (9). Em , podemos representar os inteiros e como números binários da seguinte forma
(30)
em que e podem assumir os valores e apenas. Usando esta representação, podemos reescrever (9) como
( ) ∑ ∑ ∑ ( )
Algoritmos para os Cálculos das Transformadas
Tiago Cavalcanti da Rocha, Fevereiro/2016. 30
em que ( )( ), e a formulação (9) foi substituída por somas a fim de enumerar todos os bits da representação binária de .
Como , escrevemos como
( )( ) ( )( )
( ) (32)
Agora considere o primeiro termo de (32),
( )( ) ( ) ( )
( ) ( )
( ) (33)
pois [ ] . Analogamente, o segundo termo de (32) resulta
( )( )
( ) ( )
( ) ( )
(34)
Note que à medida que progredimos pelos termos de (32), adicionamos outro fator que não se cancela pela condição . Esse processo continua até atingirmos o último termo que não tenha cancelamento.
( ) ∑ ∑ ∑ ( ) ( ) ( ) (35)
Realizando cada um dos somatórios separadamente e rotulando os resultados intermediários, obtemos ( ) ∑ ( ) ( ) ( ) ∑ ( ) ( ) ∑ ( )
Algoritmos para os Cálculos das Transformadas
Tiago Cavalcanti da Rocha, Fevereiro/2016. 31
( ) ( ) (36)
Ou seja, os bits do resultado final ( ), da forma como foram obtidos, estão invertidos com relação aos valores desejados ( ).
Esse conjunto de equações recursivas representa a formulação Cooley-Tukey da FFT, . Relembre que a avaliação direta da transformação de um ponto requer aproximadamente multiplicações complexas. Agora considere o número de multiplicações necessárias para calcular as relações (36). Existem equações somatórias em que cada um representa equações. Cada um das últimas equações contém duas multiplicações complexas; entretanto a primeira multiplicação de cada equação é na verdade uma multiplicação por unidade. Isso segue do fato de que a primeira multiplicação é sempre da forma , em que . Assim, apenas multiplicações complexas são necessárias (BRIGHAM, 1974).
4.1.1.2 Para fatores arbitrários
O algoritmo FFT para qualquer , com avaliado nos inteiros resultou em uma enorme economia do tempo de computação, mas a condição é muito restritiva. Então, nesta seção desenvolvemos o algoritmo FFT que remove esta condição. Mostraremos que significante economia de tempo pode ser obtida desde que seja altamente composto; ou seja, em que é um inteiro.
Assuma que o número de pontos a ser transformado discretamente satisfaz , em que são valores inteiros. Expressamos primeiro o índice de e na representação da variável radix (BRIGHAM, 1974)
(37)
em que , com , , e com .
Podemos, agora, escrever a Equação (9) como
∑ ∑
(38) em que ∑ representa um somatório sobre , com . Note que
(39)
e o primeiro termo do somatório expande para
Algoritmos para os Cálculos das Transformadas
Tiago Cavalcanti da Rocha, Fevereiro/2016. 32
(40)
Uma vez que , então a Equação (40) pode ser escrita como
(41)
e, assim, a Equação (39) torna-se
(42)
A equação (38) agora pode ser reescrita como
∑ ∑ ∑
(43)
Note que a soma interna é sobre e é apenas uma função de variáveis e
. Assim, definimos uma nova matriz como
∑
(44) A Equação (43) agora pode ser reescrita como
∑ ∑ ∑
(45)
Por argumentos análogos aos que levam à Equação (41), obtemos
(46)
A identidade (46) permite a soma interna de (45) a ser escrita como ∑
(47) Podemos agora reescrever (45) na forma
∑ ∑ ∑
(48)
Se continuarmos reduzindo (48) desta maneira, obtemos um conjunto de equações recursivas da forma ∑
Algoritmos para os Cálculos das Transformadas
Tiago Cavalcanti da Rocha, Fevereiro/2016. 33
(49)
A expressão (49) é válida quando definimos para e
.
Os resultados finais são dados por
(50)
A expressão (49) é uma extensão devida a BERGLAND (1968) do algoritmo original de COOLEY e TUKEY (1965). Notemos que existem elementos na matriz , cada um requerendo operações (uma multiplicação complexa e uma soma complexa), dando um total de operações para obter . Analogamente, se gasta operações para calcular de . Assim, o cálculo de requer operações. Este limite não leva em conta as simetrias da exponencial complexa que podem ser exploradas. Essas simetrias são discutidas em pormenor em BRIGHAM (1974).
4.1.2 Transformada Z CHIRP – CZT
Para o cálculo rápido da transformada Z em pontos que estão no contorno circular ou espiral, começando em qualquer ponto arbitrário do plano , com espaçamento angular constante, introduziu-se a transformada Z CHIRP. Usamos em (17) a substituição devida a BLUESTEIN (1970), para o expoente de . Isso produz uma expressão aparentemente mais pesada (BAGCHI e MITRA, 1967)
∑
(51) A Equação (51) pode ser expressa como uma convolução discreta da forma
[( ) ] (52)
chamada transformada Z CHIRP (CZT – chirp z-transform). Por MARTIN (2005), temos
[ ( ) ( )]
O cálculo de requer multiplicações. Técnicas de convolução de alta velocidade usando a FFT podem ser usadas para avaliar a CZT de forma eficiente com ( ) operações, para valores muito grandes de e . O produto do resultado da convolução por requer multiplicações.
Como o número de amostras de ou cresce muito, o cálculo do tempo para a CZT crescer assintoticamente como algo proporcional a . Este é o mesmo
Algoritmos para os Cálculos das Transformadas
Tiago Cavalcanti da Rocha, Fevereiro/2016. 34
tipo de dependência assintótica da FFT, mas a constante de proporcionalidade é maior para a CZT porque duas ou três FFT‘s são necessárias ao invés de uma, e porque é maior do que ou . Ainda, a CZT é mais rápida do que o cálculo direto de (18) mesmo para valores relativamente modestos de e , da ordem de 50 (RABINER, SCHAFER e RADER, 1969).