Transformadas de Fourier

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

O sinal $\mathrm{x}\mathrm{(}\mathrm{t}\mathrm{)}$ é contínuo no tempo, e o sinal $\mathrm{X}\mathrm{(}\mathrm{j}\mathrm{\Omega }\mathrm{)}$ é contínuo na frequência.

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{j}\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{j}\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{j}\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{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{j}\mathrm{\Omega }\mathrm{)}{\mathrm{e}}^{\mathrm{j}\mathrm{\Omega }\mathrm{t}}\mathrm{d}\mathrm{\Omega }$$

A transformada de Fourier $\mathrm{X}\mathrm{(}\mathrm{j}\mathrm{\Omega }\mathrm{)}$, por simplificação é muitas vezes representada apenas por $\mathrm{X}\mathrm{(}\mathrm{\Omega }\mathrm{)}$ ou $\mathrm{X}\mathrm{(}\mathrm{\omega }\mathrm{)}$, mas é importante lembrar que tratasse de uma frequência complexa, representada pelo eixo imaginário do plano s.

Figura 1 - Sinal $\mathrm{x}\mathrm{(}\mathrm{t}\mathrm{)}$ e sua transformada de Fourier $\mathrm{X}\mathrm{(}\mathrm{\Omega }\mathrm{)}$ Fonte: Elaborado pelo autor.

2 Transformada Z

A transformada Z de um sinal de tempo discreto $x(n)$ é a função $X(z)$ definida como

$X(z)=Z\{x(n)\}=\sum _{n=-\mathrm{\infty }}^{\mathrm{\infty }}x(n)z^{-n}$

onde $n$ é um inteiro; $z=A{e}^{j\varphi }$ é um número complexo, com $A$ sendo sua magnitude, e $\varphi$ sua frequência angular (em radianos por amostra).

A transformada Z inversa é

$x(n)=Z^{-1}\{X(z)\}=\frac{1}{2\pi j}{\oint }_{C}X(z)z^{n-1}dz$

onde $C$ é o caminho antihorário envolvendo a origem, dentro da região de convergencia (ROC) de $X(z)$.

3 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{e}}^{\mathrm{j}\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{e}}^{\mathrm{j}\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 }$$

Como a transformada de Fourier $\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{\omega }}\mathrm{)}$ é periódica com período $\mathrm{2}\mathrm{\pi }$, pois $\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{\omega }}\mathrm{)}\mathrm{=}\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{(}\mathrm{\omega }\mathrm{+}\mathrm{2}\mathrm{\pi }\mathrm{k}\mathrm{)}}\mathrm{)}$, para $\mathrm{k}\mathrm{\in }\mathbb{\mathbb{Z}}$, ela pode ser calculada em qualquer faixa de $\mathrm{2}\mathrm{\pi }$, por exemplo $\mathrm{\omega }\mathrm{\in }\mathrm{[}\mathrm{-}\mathrm{\pi },\mathrm{\pi }\mathrm{)}$.

$$\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{\pi }}{\overset{\mathrm{\pi }}{\int }}\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{\omega }}\mathrm{)}{\mathrm{e}}^{\mathrm{j}\mathrm{\omega }\mathrm{n}}\mathrm{d}\mathrm{\omega }$$

Figura 2 - Sinal discreto $\mathrm{x}\mathrm{(}\mathrm{n}\mathrm{)}$ e sua TFDT $\mathrm{X}\mathrm{(}{\mathrm{e}}^{\mathrm{j}\mathrm{\omega }}\mathrm{)}$ Fonte: Elaborado pelo autor.

4 Transformada de Discreta de Fourier (TDF)

4.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.

4.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.3 Transformada Rápida de Fourier (FFT)

As FFTs são algoritmos que reduzem a complexidade do cálculo da DFT, obtendo ordens de $\mathrm{O}\mathrm{(}\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{N}\mathrm{\times }\mathrm{N}\mathrm{)}$.

5 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}$