Análise e Implementação da Transformada Rápida de

Fourier (FFT)
Felipe Bastos Meneses
24 de julho de 2025

1 Introdução
A Transformada Discreta de Fourier (DFT) é uma ferramenta fundamental na análise
de sinais, permitindo a transformação de um sinal do domı́nio do tempo para o domı́nio
da frequência. A aplicação direta da DFT, porém, requer um número significativo de
operações computacionais, limitando sua eficiência para sinais de grande dimensão.
Este trabalho tem como objetivos:

• Apresentar os conceitos fundamentais da DFT e da Transformada Rápida de Fourier

(FFT).

• Implementar a FFT utilizando recursividade em Python.

• Aplicar técnicas de zero-padding para adequação do tamanho do vetor de entrada.

• Analisar os espectros de magnitude e fase gerados pela FFT.

2 Fundamentação Teórica
2.1 DFT Convencional
A Transformada Discreta de Fourier (DFT) é uma ferramenta essencial na análise de
sinais digitais, que permite decompor um sinal discreto no tempo em suas componentes
espectrais de frequência.
Dado um sinal discreto x(n) com N amostras, a DFT é definida como:
N
X −1
X[k] = x(n)WNkn , k = 0, 1, . . . , N − 1
n=0
2π
onde WN = e−j N é a chamada raiz complexa da unidade, que representa a base da
transformação.
Cada coeficiente X[k] representa a contribuição da frequência k no sinal original, sendo
a decomposição do sinal em uma soma ponderada de senos e cossenos complexos.

Propriedades importantes da DFT:

• Periodicidade: A DFT é periódica em N , isto é, X[k + N ] = X[k].

1
 • Linearidade: A DFT é uma transformação linear.
• Simetria conjugada: Para sinais reais, os coeficientes da DFT apresentam simetria
conjugada.

Complexidade Computacional:
O cálculo direto da DFT, conforme a fórmula acima, exige calcular N coeficientes
X[k], cada um resultando de uma soma com N termos. Portanto, o número total de
multiplicações e somas é da ordem de N 2 , o que pode ser proibitivo para sinais com
grande número de amostras.
Este alto custo computacional motivou o desenvolvimento de algoritmos mais efici-
entes, como a Transformada Rápida de Fourier (FFT), que reduz significativamente a
complexidade para O(N log N ), viabilizando aplicações práticas em tempo real e proces-
samento digital de sinais em larga escala.

2.2 FFT
A FFT pelo método matricial divide o sinal em subsequências pares e ı́mpares, cal-
culando DFTs menores e combinando os resultados.
Divisão do Sinal
N/2−1 N/2−1
X X
X[k] = x(n)WNkn + x(n)WNkn
n par nı́mpar

Fazendo n = 2r e n = 2r + 1 em cada um dos somatórios, reescrevemos:

• Índices pares: xpar (n) = x(2r)

• Índices ı́mpares: ximpar (n) = x(2r + 1)

N/2−1 N/2−1
X X (2r+1)k
X[k] = x(2r)WN2kr + x(2r + 1)WN
r=0 r=0

Mas, WN2 = WN/2 já que:

WN2 = e−j2π/N ·2 = e−j2π/(N/2) = WN/2

Então, podemos reescrever X[k] como:
N/2−1 N/2−1
X X
X[k] = x(2r)(WN/2 )kr + WNk x(2r + 1)(WN/2 )kr
r=0 r=0

X[k] = G[k] + WNk H[k]

X[k + N/2] = G[k] − WNk H[k]

onde:
• G[k]: FFT dos pares
• H[k]: FFT dos ı́mpares

2
3 Implementação
Nesta seção, é apresentado o código desenvolvido para a implementação da Transformada
Rápida de Fourier (FFT) em Python, explicando detalhadamente cada componente.

Função FFT Recursiva

A função fft implementa a FFT usando a abordagem recursiva baseada na divisão do
sinal em subsequências pares e ı́mpares:
1 def fft ( x ) :
2 N = len ( x )
3 if N == 1:
4 return [ x [0]]
5
6 x_par = [ x [ n ] for n in range (0 , N , 2) ]
7 x_impar = [ x [ n ] for n in range (1 , N , 2) ]
8
9 X_par = fft ( x_par )
10 X_impar = fft ( x_impar )
11
12 X = [0] * N
13 for k in range ( N // 2) :
14 W = np . exp ( -2 j * np . pi * k / N )
15 X [ k ] = X_par [ k ] + W * X_impar [ k ]
16 X [ k + N // 2] = X_par [ k ] - W * X_impar [ k ]
17
18 return X
Listing 1: Implementação da FFT recursiva
Explicação:

• Quando o tamanho do vetor de entrada N é 1, a FFT retorna o próprio valor.

• O vetor é dividido em duas partes: pares e ı́mpares.

• Aplica-se recursivamente a FFT nessas subsequências menores.

• Calcula-se o fator complexo W = e−j2πk/N , conhecido como twiddle factor.

• Combina-se os resultados das FFTs menores para formar o resultado completo.

Função para Zero-Padding

Para garantir que o tamanho do vetor seja uma potência de 2 (requisito para a FFT
recursiva), foi utilizada a função add zero:

3
 1 def add_zero ( sinal_entrada ) :
2 if np . log2 ( len ( sinal_entrada ) ) % 1 != 0:
3 N_novo = 2 ** int ( np . ceil ( np . log2 ( len ( sinal_entrada ) ) ) )
4 else :
5 N_novo = len ( sinal_entrada )
6

7 num_zeros_add = N_novo - len ( sinal_entrada )

8 sinal_novo = np . pad ( sinal_entrada , (0 , num_zeros_add ) , ’ constant ’)
9 return sinal_novo
Listing 2: Função para aplicar zero-padding
Explicação:

• Calcula o próximo número inteiro que é potência de 2 maior ou igual ao tamanho

do sinal.

• Completa o vetor original com zeros no final para atingir esse tamanho.

• Retorna o novo vetor com tamanho ajustado.

Geração de Sinais a partir de Expressões

A função gerar sinal permite a criação dinâmica de sinais a partir de expressões ma-
temáticas:
1 def gerar_sinal ( expressao , comprimento ) :
2 sinal = np . zeros ( comprimento , dtype = float )
3
4 dic_base = {
5 ’ sin ’: np . sin ,
6 ’ cos ’: np . cos ,
7 ’ pi ’: np . pi ,
8 }
9
10 for n_indice in range ( comprimento ) :
11 def delta_local ( delay ) :
12 return 1.0 if n_indice == delay else 0.0
13
14 dic_it = dic_base . copy ()
15 dic_it [ ’n ’] = n_indice
16 dic_it [ ’ delta ’] = delta_local
17
18 try :
19 sinal [ n_indice ] = eval ( expressao , { " __builtins__ " : None } ,
dic_it )
20 except Exception as e :
21 raise ValueError ( f " Erro ␣ ao ␣ avaliar ␣ a ␣ e x p r e s s o ␣ ’{ expressao
} ’ ␣ no ␣ ndice ␣ n ={ n_indice }: ␣ { e } " )
22
23 return sinal . tolist ()
Listing 3: Função para gerar sinais a partir de expressões
Explicação:

• Recebe uma expressão matemática como string e o comprimento do sinal desejado.

• Utiliza eval para interpretar a expressão para cada ı́ndice n.

4
 • Fornece funções trigonométricas e a constante π para a expressão.

• Define a função delta para permitir o uso do impulso unitário (δ(n)).

• Retorna o vetor de amostras gerado.

Visualização dos Resultados

A função plot fft cria gráficos para análise visual do sinal e sua FFT:
1 def plot_fft ( resultado_fft_np , sinal_novo_np , titulo = " " ) :
2 N_sinal = len ( sinal_novo_np )
3 N_fft = len ( resultado_fft_np )
4
5 num_linhas = 3
6
7 plt . figure ( figsize =(14 , 12) )
8 plt . suptitle ( f ’{ titulo } ’ , fontsize =16)
9
10 ax1 = plt . subplot ( num_linhas , 1 , 1)
11 ax1 . stem ( np . arange ( N_sinal ) , sinal_novo_np . real )
12 ax1 . set_title ( f ’ Sinal ␣ ( N ={ N_sinal }) ’)
13 ax1 . set_xlabel ( ’ Amostra ␣ ( n ) ’)
14 ax1 . set_ylabel ( ’ Amplitude ’)
15 ax1 . grid ( True )
16
17 ax2 = plt . subplot ( num_linhas , 2 , 3)
18 ax2 . stem ( np . arange ( N_fft ) , np . abs ( resultado_fft_np ) )
19 ax2 . set_title ( f ’ Magnitude ’)
20 ax2 . set_xlabel ( ’ F r e q u n c i a ␣ ( k ) ’)
21 ax2 . set_ylabel ( r ’$ | X [ k ]| $ ’)
22 ax2 . grid ( True )
23
24 fase = np . angle ( resultado_fft_np )
25
26 ax3 = plt . subplot ( num_linhas , 2 , 4)
27 ax3 . stem ( np . arange ( N_fft ) , fase )
28 ax3 . set_title ( f ’ Fase ’)
29 ax3 . set_xlabel ( ’ F r e q u n c i a ␣ ( k ) ’)
30 ax3 . set_ylabel ( r ’$ \ angle ␣ X [ k ] $ ’)
31 ax3 . grid ( True )
32

33 plt . tight_layout ( rect =[0 , 0.03 , 1 , 0.95])

34 plt . show ()
Listing 4: Função para plotar sinal, magnitude e fase
Explicação:

• Plota o sinal original no domı́nio do tempo.

• Plota a magnitude do espectro obtido pela FFT.

• Plota a fase do espectro.

• Utiliza o stem para destacar os valores discretos.

5
Função Principal para Execução
Por fim, a função run controla o fluxo do programa, recebendo entrada do usuário, gerando
o sinal, aplicando zero-padding, calculando a FFT e exibindo os gráficos:
1 def run () :
2 try :
3 entr ada_ex pressa o = input ( " \ nDigite ␣ a ␣ e x p r e s s o ␣ do ␣ sinal :\ n ␣ ex :
␣ delta ( n ) ,␣ sin ((2* pi *2* n ) / N ) ␣ " ) . strip ()
4 e nt r a da _ c om p r im e n to = input ( " Digite ␣ o ␣ valor ␣ de ␣ N : ␣ " ) . strip ()
5 comprimento = int ( e n t r ad a _ co m p ri m e nt o )
6 if comprimento <= 0:
7 print ( " O ␣ comprimento ␣ do ␣ sinal ␣ deve ␣ ser ␣ um ␣ n m e r o ␣ inteiro ␣
positivo . ␣ Encerrando . " )
8 return
9
10 sinal = gerar_sinal ( entrada_expressao , comprimento )
11
12 sinal_np = np . asarray ( sinal , dtype = np . complex128 )
13
14 if len ( sinal_np ) == 0:
15 print ( " Sinal ␣ original ␣ e s t ␣ vazio . ␣ N o ␣ ␣poss vel␣
processar ␣ a ␣ FFT . " )
16 return
17

18 sinal_novo_np = add_zero ( sinal_np )

19
20 if len ( sinal_novo_np ) == 0:
21 print ( " Sinal ␣ a p s ␣ padding ␣ e s t ␣ vazio . ␣ N o ␣ ␣poss vel␣
calcular ␣ FFT . " )
22 return
23
24 resultado_fft = fft ( sinal_novo_np . tolist () )
25 resultado_fft_np = np . asarray ( resultado_fft , dtype = np . complex128
)
26
27 plot_fft ( resultado_fft_np , sinal_novo_np , titulo = f ’ E x p r e s s o : ␣ {
ent rada_e xpress ao } ’)
28
29 except ValueError as erro_valor :
30 print ( f " Erro ␣ de ␣ entrada : ␣ { erro_valor } " )
31 except Exception as erro_geral :
32 print ( f " Ocorreu ␣ um ␣ erro ␣ inesperado : ␣ { erro_geral } " )
33
34 if __name__ == " __main__ " :
35 run ()
Listing 5: Função principal do programa
Explicação:
• Recebe a expressão do sinal e o comprimento via entrada padrão.
• Gera o vetor do sinal utilizando a expressão.
• Aplica zero-padding para garantir potência de 2.
• Calcula a FFT recursiva.
• Exibe os gráficos para análise.

6
 • Trata exceções para entradas inválidas ou erros inesperados.

Exemplo 1: Teste com Impulso Unitário (Delta)

O sinal impulso unitário δ(n) é um vetor onde o valor é 1 em n = 1 e zero para os demais
ı́ndices. A FFT desse sinal apresenta magnitude constante, pois o impulso contém todas
as frequências igualmente.

Figura 1: Análise do sinal impulso unitário δ(n): (a) sinal no domı́nio do tempo, (b)
magnitude da FFT, (c) fase da FFT.

Exemplo 2: Teste com Sinal Senoidal

Neste teste, utilizamos um sinal senoidal definido pela expressão sin 2π2n


N
com N =120.
A FFT revela picos claros na frequência correspondente ao seno, evidenciando a decom-
posição espectral correta.

2π2n


Figura 2: Análise do sinal senoidal sin N
: (a) sinal no domı́nio do tempo, (b) magni-
tude da FFT, (c) fase da FFT.

7
4 Conclusão
A implementação recursiva da FFT mostrou-se eficiente para sinais cujo tamanho é
potência de dois, evidenciando a importância do zero-padding para adequação dos sinais
à exigência do algoritmo.
A abordagem adotada permitiu a análise clara tanto da magnitude quanto da fase do
espectro, o que é fundamental para aplicações práticas de processamento de sinais.
Por fim, este trabalho contribui para o aprendizado prático e aprofundado dos concei-
tos fundamentais da transformada de Fourier, fornecendo uma base sólida para aplicações
em engenharia, fı́sica e outras áreas que dependem do processamento de sinais.