Como visto anteriormente, os algoritmos de decimação no tempo estão baseados na decomposição da computação da DFT, formando-se subsequências cada vez menores da sequência de entrada x(n). Alternativamente, é possível dividir a sequência de saída, X(k), em subsequências cada vez menores. A classe de algoritmos FFT baseadas neste processo é denominada "Decimation-in-Frequency" (Decimação na Frequência). Para construir tal algoritmo quando N é uma potência de 2, pode-se dividir a sequência de entrada em 2 metades, tal que:
  ou
 

(14)

É importante observar que enquanto a equação (14) contém dois somatórios, cada um desses somatórios não é uma transformada de N/2 pontos. Combinando os somatórios da equação (14) e usando o fato de que

tem-se
 

(15)

Considere-se agora separadamente k par e k ímpar, com X(2r) representando os pontos de índice par e X(2r+1) representando os pontos de índice ímpar. Assim:
 

	(16)
	(17)

As equações (16) e (17), podem ser reconhecidas como DFT’s de N/2 pontos, pois

Então, fazendo-se g(n) = x(n) + x(n+N/2) e h(n) = x(n) - x(n+N/2), a DFT pode ser calculada primeiro formando-se as sequências g(n) e h(n), depois calculando-se , e finalmente calculando-se as DFT's de N/2 pontos dessas duas sequências, para se obter os X(k) de índice par e os X(k) de índice ímpar. O processo descrito pelas equações (16) e (17), para o caso de uma transformada de oito pontos, está ilustrado na fig.7, reproduzida de Oppenheim e Schafer, Digital Signal Processing,1975.
 

Figura 7

Como no caso da decomposição original, que levou às equações (16) e (17), isto é realizado combinando-se a 1ª e a 2ª metade da sequência de entrada para cada uma das DFT’s de N/2 pontos, e depois computando-se as DFT’s de N/4 pontos. O diagrama de fluxo que ilustra este processo para o exemplo de 8 pontos é mostrado na fig. 8, reproduzida de Oppenheim e Schafer, Digital Signal Processing,1975.
 
 

Figura 8

 
 

Para este exemplo, o cálculo foi reduzido ao cálculo de DFT’s de 2 pontos, os quais são os pontos da sequência de entrada.

Procedendo de forma similar àquela utilizada no algoritmo de decimação no tempo, nota-se que, como N é uma potência de 2, N/2 é par e consequentemente as DFT’s podem ser calculadas computando-se separadamente os X(k) de índice par e os de índice ímpar.

Assim as DFT’s de 2 pontos na fig.8 podem ser substituídas pelo esquema montado na fig.9 reproduzida de Oppenheim e Schafer, Digital Signal Processing,1975, gerando então a fig.10 também reproduzida de Oppenheim e Schafer, Digital Signal Processing,1975, que esquematiza o cálculo da DFT de 8 pontos.
 
 

Figura 9

 

Figura 10

Contando-se as operações aritméticas na fig.10, e generalizando para N igual a uma potência de 2, observa-se que o esquema da fig.10 requer N/2 log2 N multiplicações complexas e N log2 N adições complexas. Então o tempo de computação é o mesmo para os algoritmos de decimação no tempo e os de decimação na frequência.