Transformadas de Fourier

1 Transformada de Fourier no tempo contínuo (TFTC)

A equação de análise

É uma transformação de um domínio de uma variável real $\mathrm{x}\mathrm{(}\mathrm{t}\mathrm{)}$ de tempo continuo em uma variável complexa $\mathrm{X}\mathrm{(}\mathrm{\Omega }\mathrm{)}$ de frequência contínua.

$\mathrm{D}\mathrm{T}\mathrm{\to }\mathrm{D}\mathrm{F}$.

$\mathrm{x}\mathrm{:}\mathbb{ℝ}\mathrm{\to }\mathbb{ℂ}$.

$$\mathrm{X}\mathrm{(}\mathrm{\Omega }\mathrm{)}\mathrm{\equiv }{ℱ}\mathrm{\{}\mathrm{x}\mathrm{(}\mathrm{t}\mathrm{)}\mathrm{\}}\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\underset{\mathrm{-}\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}\mathrm{x}\mathrm{(}\mathrm{t}\mathrm{)}{\mathrm{e}}^{\mathrm{-}\mathrm{j}\mathrm{\Omega }\mathrm{t}}\mathrm{d}\mathrm{t}$$

A equação de síntese

É uma transformação de um domínio de uma variável complexa $\mathrm{X}\mathrm{(}\mathrm{\Omega }\mathrm{)}$ de frequência contínua em uma variável real $\mathrm{x}\mathrm{(}\mathrm{t}\mathrm{)}$ de tempo continuo.

$\mathrm{D}\mathrm{F}\mathrm{\to }\mathrm{D}\mathrm{T}$.

$\mathrm{X}\mathrm{:}\mathbb{ℂ}\mathrm{\to }\mathbb{ℝ}$.

$$\mathrm{x}\mathrm{(}\mathrm{t}\mathrm{)}\mathrm{\equiv }{{ℱ}}^{\mathrm{-}\mathrm{1}}\mathrm{\{}\mathrm{X}\mathrm{(}\mathrm{\Omega }\mathrm{)}\mathrm{\}}\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\frac{1}{2\pi }\underset{\mathrm{-}\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}\mathrm{X}\mathrm{(}\mathrm{j}\mathrm{\Omega }\mathrm{)}{\mathrm{e}}^{\mathrm{j}\mathrm{\Omega }\mathrm{t}}\mathrm{d}\mathrm{\Omega }$$

2 Transformada de Fourier no tempo discreto (TFTD)

• O sinal $\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}$ é discreto no tempo, e o sinal $\mathrm{X}\mathrm{(}\mathrm{\Omega }\mathrm{)}$ é contínuo e periódico em $\mathrm{2}\mathrm{\pi }$.

A equação de análise

É uma transformação de um domínio de uma variável real $\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}$ de tempo discreto em uma variável complexa $\mathrm{X}\mathrm{(}\mathrm{\omega }\mathrm{)}$ frequência contínua periódica.

$\mathrm{D}\mathrm{T}\mathrm{\to }\mathrm{D}\mathrm{F}$.

$\mathrm{x}\mathrm{:}\mathbb{ℝ}\mathrm{\to }\mathbb{ℂ}$.

$$\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{\omega }}\mathrm{)}\mathrm{\equiv }{ℱ}\mathrm{\{}\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}\mathrm{\}}\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\sum _{\mathrm{n}\mathrm{=}\mathrm{-}\mathrm{\infty }}^{\mathrm{\infty }}\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}{\mathrm{e}}^{\mathrm{-}\mathrm{j}\mathrm{\omega }\mathrm{n}}$$

A equação de síntese

É uma transformação de um domínio de uma variável complexa $\mathrm{X}\mathrm{(}\mathrm{\omega }\mathrm{)}$ de frequência contínua periódica em uma variável real $\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}$ continua.

$\mathrm{D}\mathrm{F}\mathrm{\to }\mathrm{D}\mathrm{T}$.

$\mathrm{X}\mathrm{:}\mathbb{ℂ}\mathrm{\to }\mathbb{ℝ}$.

$$\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}\mathrm{\equiv }{{ℱ}}^{\mathrm{-}\mathrm{1}}\mathrm{\{}\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{\omega }}\mathrm{)}\mathrm{\}}\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\frac{1}{2\pi }\underset{\mathrm{-}\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{\omega }}\mathrm{)}{\mathrm{e}}^{\mathrm{j}\mathrm{\omega }\mathrm{n}}\mathrm{d}\mathrm{\omega }$$

3 Transformada de Discreta de Fourier (TDF)

3.1 Obtenção da TDF a partir da amostragem da TFTD

Sinais discretos no tempo podem ser representados pela sua TFTD, que é uma função continua periódica em $\mathrm{2}\mathrm{\pi }$ de $\mathrm{\omega }$ :

$$\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{\omega }}\mathrm{)}\mathrm{=}\sum _{\mathrm{n}\mathrm{=}\mathrm{-}\mathrm{\infty }}^{\mathrm{\infty }}\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}{\mathrm{e}}^{\mathrm{-}\mathrm{j}\mathrm{\omega }\mathrm{n}}$$

Para que a mesma possa ser utilizada no processamento de sinais digitais é necessário que a variável frequência seja também discreta. Se amostrarmos uniformemente a frequência $\mathrm{\omega }$ em N amostras entre 0 e $\mathrm{2}\mathrm{\pi }$ é possível obter a TDF (ou DFT - Discrete Fourier Transform). Assim se tomarmos N frequências ${\mathrm{\omega }}_{\mathrm{k}}\mathrm{=}\mathrm{(}\mathrm{2}\mathrm{\pi }/\mathrm{N}\mathrm{)}\mathrm{k}$ com $k\in \mathbb{\mathbb{Z}}$, and $\mathrm{0}\mathrm{\le }\mathrm{k}\mathrm{\le }\mathrm{N}\mathrm{-}\mathrm{1}$, obtemos o espectro amostrado uniformemente:

$${\mathrm{X}}^{\prime }\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{\omega }}\mathrm{)}\mathrm{=}\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{\omega }}\mathrm{)}\sum _{\mathrm{k}\mathrm{=}\mathrm{-}\mathrm{\infty }}^{\mathrm{\infty }}\mathrm{\delta }(\omega -\frac{2\pi }{N}k)$$.

O sinal equivalente no tempo pode ser obtido aplicando a transformada inversa e a convolução:

$${\mathrm{x}}^{\prime }\mathrm{(}\mathrm{n}\mathrm{)}\mathrm{=}{{ℱ}}^{\mathrm{-}\mathrm{1}}\mathrm{\{}{\mathrm{X}}^{\prime }\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{\omega }}\mathrm{)}\mathrm{\}}\mathrm{=}\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}\mathrm{*}(\frac{N}{2\pi }\sum _{p=-\mathrm{\infty }}^{\mathrm{\infty }}\delta (n-Np))\mathrm{=}\frac{N}{2\pi }\sum _{\mathrm{p}\mathrm{=}\mathrm{-}\mathrm{\infty }}^{\mathrm{\infty }}\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{-}\mathrm{N}\mathrm{p}\mathrm{)}$$.

O que mostra que o sinal Esse sinal ${\mathrm{x}}^{\prime }\mathrm{(}\mathrm{n}\mathrm{)}$ são repetições periódicas (com período N) do sinal discreto $\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}$ original.

• Note que N o período de repetição do sinal ${\mathrm{x}}^{\prime }\mathrm{(}\mathrm{n}\mathrm{)}$ é o mesmo período de repetição das N amostras da TFTD $\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{\omega }}\mathrm{)}$ original.
• Se o comprimento L o sinal do $\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}$ for maior que N o período de repetição do sinal ${\mathrm{x}}^{\prime }\mathrm{(}\mathrm{n}\mathrm{)}$, haverá sobreposição das amostras no tempo (time aliasing), e não será possível recuperar o sinal original.
• Por outro lado, se $\mathrm{L}\mathrm{\le }\mathrm{N}$ então ${\mathrm{x}}^{\prime }\mathrm{(}\mathrm{n}\mathrm{)}$ é a repetição periódica exata de $\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}$.

$$\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}\mathrm{=}\frac{2\pi }{N}{\mathrm{x}}^{\prime }\mathrm{(}\mathrm{n}\mathrm{)}$$ , para $\mathrm{0}\mathrm{\le }\mathrm{n}\mathrm{\le }\mathrm{N}\mathrm{-}\mathrm{1}$ ou

$$\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}\mathrm{=}\frac{2\pi }{N}{\mathrm{x}}^{\prime }\mathrm{(}\mathrm{n}\mathrm{)}[u(n)-u(n-N)$$.

Portanto, é possível recuperar as amostras do sinal digital no tempo $\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}$ a partir das suas amostras digitais na frequência, desde que o período de repetição das N amostras de frequência seja maior ou igual ao comprimento L do sinal no tempo.

3.2 DFT e IDFT

• O sinal $\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}$ é discreto no tempo pode ser representado pelo o sinal $\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{(}\mathrm{2}\mathrm{\pi }/\mathrm{N}\mathrm{)}\mathrm{k}}\mathrm{)}$ discreto e periódico em $\mathrm{2}\mathrm{\pi }$.

Para obter a equação de análise (DFT) pode ser feito o cálculo das amostras do espectro de frequências em ${\mathrm{\omega }}_{\mathrm{k}}\mathrm{=}\mathrm{(}\mathrm{2}\mathrm{\pi }/\mathrm{N}\mathrm{)}\mathrm{k}$ em:

$$\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{\omega }}\mathrm{)}\mathrm{=}\sum _{\mathrm{n}\mathrm{=}\mathrm{-}\mathrm{\infty }}^{\mathrm{\infty }}\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}{\mathrm{e}}^{\mathrm{-}\mathrm{j}\mathrm{\omega }\mathrm{n}}$$

$$\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{(}\mathrm{2}\mathrm{\pi }/\mathrm{N}\mathrm{)}\mathrm{k}}\mathrm{)}\mathrm{=}\sum _{\mathrm{n}\mathrm{=}\mathrm{-}\mathrm{\infty }}^{\mathrm{\infty }}\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}{\mathrm{e}}^{\mathrm{-}\mathrm{j}\mathrm{(}\mathrm{2}\mathrm{\pi }/\mathrm{N}\mathrm{)}\mathrm{k}\mathrm{n}}$$

Conforme mostrado, o espectro é periódico em N, e portanto é suficiente calcular apenas os valores para $\mathrm{0}\mathrm{\le }\mathrm{k}\mathrm{\le }\mathrm{N}\mathrm{-}\mathrm{1}$. Assim obtém-se

A equação de análise (DFT)

É uma transformação de um domínio de uma variável real $\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}$ de tempo discreto em uma variável complexa $\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{(}\mathrm{2}\mathrm{\pi }/\mathrm{N}\mathrm{)}\mathrm{k}}\mathrm{)}$ frequência discreta periódica.

$\mathrm{D}\mathrm{T}\mathrm{\to }\mathrm{D}\mathrm{F}$.

$\mathrm{x}\mathrm{:}\mathbb{ℝ}\mathrm{\to }\mathbb{ℂ}$.

$$\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{(}\mathrm{2}\mathrm{\pi }/\mathrm{N}\mathrm{)}\mathrm{k}}\mathrm{)}\mathrm{\equiv }{ℱ}\mathrm{\{}\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}\mathrm{\}}\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\sum _{\mathrm{n}\mathrm{=}\mathrm{0}}^{\mathrm{N}\mathrm{-}\mathrm{1}}\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}{\mathrm{e}}^{\mathrm{-}\mathrm{j}\mathrm{(}\mathrm{2}\mathrm{\pi }/\mathrm{N}\mathrm{)}\mathrm{k}\mathrm{n}}$$ , para $\mathrm{0}\mathrm{\le }\mathrm{k}\mathrm{\le }\mathrm{N}\mathrm{-}\mathrm{1}$

A equação de síntese (IDFT)

É uma transformação de um domínio de uma variável complexa $\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{(}\mathrm{2}\mathrm{\pi }/\mathrm{N}\mathrm{)}\mathrm{k}}\mathrm{)}$ de frequência discreta periódica em uma variável real $\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}$ discreta.

$\mathrm{D}\mathrm{F}\mathrm{\to }\mathrm{D}\mathrm{T}$.

$\mathrm{X}\mathrm{:}\mathbb{ℂ}\mathrm{\to }\mathbb{ℝ}$.

$$\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}\mathrm{\equiv }{{ℱ}}^{\mathrm{-}\mathrm{1}}\mathrm{\{}\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{(}\mathrm{2}\mathrm{\pi }/\mathrm{N}\mathrm{)}\mathrm{k}}\mathrm{)}\mathrm{\}}\stackrel{\mathrm{d}\mathrm{e}\mathrm{f}}{=}\frac{1}{N}\sum _{\mathrm{k}\mathrm{=}\mathrm{0}}^{\mathrm{N}\mathrm{-}\mathrm{1}}\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{(}\mathrm{2}\mathrm{\pi }/\mathrm{N}\mathrm{)}\mathrm{k}}\mathrm{)}{\mathrm{e}}^{\mathrm{j}\mathrm{(}\mathrm{2}\mathrm{\pi }/\mathrm{N}\mathrm{)}\mathrm{k}\mathrm{n}}$$ , para $\mathrm{0}\mathrm{\le }\mathrm{n}\mathrm{\le }\mathrm{N}\mathrm{-}\mathrm{1}$

Ao usar a equação de análise, se o comprimento L de $\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}$ for menor que o período de repetição N, é necessário que $\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}$ seja preenchido com amostras nulas até atingir o comprimento N (zero-padding).

Simplificação da notação

Para simplificar a notação é frequente utilizar:

$\mathrm{X}\mathrm{(}\mathrm{k}\mathrm{)}\mathrm{=}\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{(}\mathrm{2}\mathrm{\pi }/\mathrm{N}\mathrm{)}\mathrm{k}}\mathrm{)}$ para a frequência discreta periódica.

E ainda definir:

${\mathrm{W}}_{\mathrm{N}}\mathrm{=}{\mathrm{e}}^{\mathrm{-}\mathrm{j}\mathrm{2}\mathrm{\pi }/\mathrm{N}}$

o qual representa um segmento $1/N$ do circulo unitário no plano complexo. Assim termos por exemplo que:

${\mathrm{W}}_{\mathrm{1}}\mathrm{=}{\mathrm{e}}^{\mathrm{-}\mathrm{j}\mathrm{2}\mathrm{\pi }}=+1$

${\mathrm{W}}_{\mathrm{-}\mathrm{1}}\mathrm{=}{\mathrm{e}}^{\mathrm{j}\mathrm{2}\mathrm{\pi }}=+1$

${\mathrm{W}}_{\mathrm{2}}\mathrm{=}{\mathrm{e}}^{\mathrm{-}\mathrm{j}\mathrm{\pi }}=-1$

${\mathrm{W}}_{\mathrm{-}\mathrm{2}}\mathrm{=}{\mathrm{e}}^{\mathrm{j}\mathrm{\pi }}=-1$

${\mathrm{W}}_{\mathrm{4}}\mathrm{=}{\mathrm{e}}^{\mathrm{-}\mathrm{j}\mathrm{\pi }/\mathrm{2}}=-j$

${\mathrm{W}}_{\mathrm{-}\mathrm{4}}\mathrm{=}{\mathrm{e}}^{\mathrm{j}\mathrm{\pi }/\mathrm{2}}=+j$

Também é importante lembrar que se $N$ é múltiplo de $k$ então:

$W_{\mathrm{N}}^{\mathrm{k}}\mathrm{=}{\mathrm{e}}^{\mathrm{-}\mathrm{j}\mathrm{(}\mathrm{2}\mathrm{\pi }/\mathrm{N}\mathrm{)}\mathrm{k}}\mathrm{=}{\mathrm{e}}^{\mathrm{-}\mathrm{j}\mathrm{2}\mathrm{\pi }/\mathrm{(}\mathrm{N}/\mathrm{k}\mathrm{)}}\mathrm{=}{\mathrm{W}}_{\mathrm{N}/\mathrm{k}}$

Dessa forma as equações da DFT e IDFT passam a ser escritas de forma simplificada como:

$$\mathrm{X}\mathrm{(}\mathrm{k}\mathrm{)}\mathrm{=}\sum _{\mathrm{n}\mathrm{=}\mathrm{0}}^{\mathrm{N}\mathrm{-}\mathrm{1}}\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}{W}_{\mathrm{N}}^{\mathrm{k}\mathrm{n}}$$ , para $\mathrm{0}\mathrm{\le }\mathrm{k}\mathrm{\le }\mathrm{N}\mathrm{-}\mathrm{1}$

$$\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}\mathrm{=}\frac{1}{N}\sum _{\mathrm{k}\mathrm{=}\mathrm{0}}^{\mathrm{N}\mathrm{-}\mathrm{1}}\mathrm{X}\mathrm{(}\mathrm{k}\mathrm{)}{W}_{\mathrm{N}}^{\mathrm{-}\mathrm{k}\mathrm{n}}$$ , para $\mathrm{0}\mathrm{\le }\mathrm{n}\mathrm{\le }\mathrm{N}\mathrm{-}\mathrm{1}$

Dessas equações é possível perceber que o cálculo da DFT e da IDFT requerem a ${\mathrm{N}}^{\mathrm{2}}$ multiplicações e $\mathrm{N}\mathrm{(}\mathrm{N}\mathrm{-}\mathrm{1}\mathrm{)}$ somas, sendo portanto um algoritmo de $\mathrm{O}\mathrm{(}{\mathrm{N}}^{\mathrm{2}}\mathrm{)}$.

4 Soma dos termos de uma Progressão Geométrica

A soma aritmética dos termos de uma P.G. a partir do primeiro termo, é definida por:

$S_n==a_1+a_{1}q+a_1{q}^2+\dots +a_1{q}^{n-1}=\sum _{i=1}^n{a}_1{q}^{i-1}$

Caso $q\ne 1$, a soma pode ser descrita por:

$S_n=\frac{a_1(1-q^n)}{1-q}$