Exercício 03
Convolução de sinais discretos unidimensionais usando o Teorema da Convolução e a FFT
Introdução
O objetivo deste exercício é criar um programa que recebe como entrada dois sinais
unidimensionais discretos g(t) e h(t) e calcula a convolução entre eles, utilizando
o Teorema da Convolução, o que inclui a aplicação da Fast Fourier Transform (FFT).
Método Utilizado
O programa foi implementado para receber dois sinais complexos como entrada.
Uma descrição do formato do arquivo de entrada pode ser vista nos comentários
no código do EP.
O algoritmo utilizado foi baseado no Teorema da Convolução, que mostra que
para obtermos a convolução entre dois sinais g(t) e h(t) no domínio do tempo
podemos realizar a FFT de cada um dos sinais, obtendo dois sinais G(f) e H(f)
no domínio da freqüência; em seguida calcula-se a multiplicação de G(f) e H(f)
ponto a ponto, obtendo um novo sinal. Então basta calcular a IFFT (transformada
rápida inversa de Fourier) para obtermos a convolução de g(t) e h(t) no domínio do
tempo.
Se os tamanhos dos sinais de entrada são m e n, sendo que m é maior ou igual a n,
o sinal de tamanho m é acrescido de n / 2 zeros à direita antes de fazermos a FFT;
o sinal de tamanho n é acrescido de m - (n / 2) zeros e é feito um "shift"
para que o seu centro fique na origem, também antes de usarmos a FFT e
supondo que o sinal é periódico. Após o cálculo do
produto ponto a ponto e à aplicação da IFFT, os n / 2 últimos elementos do sinal
resultante são descartados, resultando assim num sinal de tamanho m como resposta.
O programa foi escrito na linguagem C. Foi utilizada a biblioteca
FFTW versão 2.1.3 para o cálculo da FFT.
O código do EP pode ser baixado aqui.
Resultados
Alguns resultados de convoluções simples obtidos pela execução do programa podem
ser vistos abaixo.
Os arquivos de entrada usados foram: 1,
2 e 3.
g(t) = [1 2 3 2 1]
h(t) = [0.5 0.5 0.5]
convolução = [1.5 3 3.5 3 1.5]
g(t) = [1 1 1 1 1]
h(t) = [1]
convolução = [1 1 1 1 1]
g(t) = [1 4]
h(t) = [10 14 17 30]
convolução = [54 73 98 120]
Conclusão
Este programa permite verificarmos a utilidade da FFT e do Teorema da
Convolução para realizar a convolução entre sinais. Embora os resultados da
convolução direta no domínio do tempo e da obtida através da aplicação do
Teorema da Convolução sejam os mesmos, o algoritmo da FFT permite a
realização da convolução de forma bem mais eficiente, sendo muito importante
quando temos um volume de dados muito grande.
Daniel André Vaquero
daniel at linux.ime.usp.br
Thu, 25 Sep 2003 22:31:49 -0300