Transformada discreta de Fourier

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Tipo de transformação de Fourier em matemática discreta

Fig. 1: Relação entre o (contínua) Transformação de Fourier e a transformada de Fourier discreta. Coluna esquerda: Uma função contínua (top) e sua transformada Fourier (bottom). Coluna centro-esquerda: Somação periódica da função original (top). A transformação de Fourier (bottom) é zero, exceto em pontos discretos. A transformação inversa é uma soma de sinusóides chamada série Fourier. Coluna centro-direita: A função original é discreta (multiplicada por um pente de Dirac) (top). Sua transformação Fourier (bottom) é uma soma periódica (DTFT) da transformação original. Coluna direita: O DFT (bottom) computa amostras discretas do DTFT contínuo. O DFT inverso (top) é uma soma periódica das amostras originais. O algoritmo FFT computa um ciclo do DFT e seu inverso é um ciclo do inverso DFT.

Figo 2: Depicção de uma transformada de Fourier (à esquerda) e sua soma periódica (DTFT) no canto inferior esquerdo. As sequências espectrais na (a) superior direita e (b) direita inferior são respectivamente computadas de (a) um ciclo da soma periódica de s(t) e (b) um ciclo da soma periódica da sequência s(nT). As respectivas fórmulas são (a) a série Fourier integral e (b) o DFT somatório. Suas semelhanças com a transformação original, S(f) e sua relativa facilidade computacional são muitas vezes a motivação para a computação de uma sequência DFT.

Em matemática, a transformada discreta de Fourier (DFT) converte uma sequência finita de amostras igualmente espaçadas de uma função em uma sequência de mesmo comprimento de amostras igualmente espaçadas da transformada de Fourier em tempo discreto (DTFT), que é uma função de frequência de valor complexo. O intervalo no qual o DTFT é amostrado é o recíproco da duração da sequência de entrada. Uma DFT inversa é uma série de Fourier, usando as amostras DTFT como coeficientes de senoides complexas nas frequências DTFT correspondentes. Tem os mesmos valores de amostra que a sequência de entrada original. A DFT é, portanto, considerada uma representação no domínio da frequência da sequência de entrada original. Se a sequência original abrange todos os valores diferentes de zero de uma função, sua DTFT é contínua (e periódica) e a DFT fornece amostras discretas de um ciclo. Se a sequência original for um ciclo de uma função periódica, a DFT fornecerá todos os valores diferentes de zero de um ciclo da DTFT.

A DFT é a transformada discreta mais importante, usada para realizar a análise de Fourier em muitas aplicações práticas. No processamento de sinal digital, a função é qualquer quantidade ou sinal que varia ao longo do tempo, como a pressão de uma onda sonora, um sinal de rádio ou leituras diárias de temperatura, amostradas em um intervalo de tempo finito (geralmente definido por uma função de janela). No processamento de imagem, as amostras podem ser os valores de pixels ao longo de uma linha ou coluna de uma imagem raster. A DFT também é usada para resolver eficientemente equações diferenciais parciais e para realizar outras operações, como convoluções ou multiplicação de números inteiros grandes.

Como lida com uma quantidade finita de dados, pode ser implementado em computadores por algoritmos numéricos ou até mesmo por hardware dedicado. Essas implementações geralmente empregam algoritmos eficientes de transformada rápida de Fourier (FFT); tanto que os termos "FFT" e "DFT" são freqüentemente usados de forma intercambiável. Antes de seu uso atual, o "FFT" inicialismo também pode ter sido usado para o termo ambíguo "transformada de Fourier finita".

Definição

O discreto Transformação de Fourier transforma uma sequência de N números complexos ${displaystyle left{mathbf {x} _{n}right}:=x_{0},x_{1},ldotsx_{N-1}}$ em outra sequência de números complexos, ${displaystyle left{mathbf {X} _{k}right}:=X_{0},X_{1},ldotsX_{N-1},}$ que é definido por

{displaystyle X_{k}=sum _{n=0}^{N-1}x_{n}cdot e^{-{frac {i2pi }{N}}kn}}

(Eq.1)

A transformação é por vezes denotada pelo símbolo ${mathcal {F}}$ , como em $mathbf {X} ={mathcal {F}}left{mathbf {x} right}$ ou ${mathcal {F}}left(mathbf {x} right)$ ou ${mathcal {F}}mathbf {x}$ .

A DFT tem muitas aplicações, incluindo aplicações puramente matemáticas sem interpretação física. Mas fisicamente pode ser relacionado ao processamento de sinal como uma versão discreta (ou seja, amostras) da transformada de Fourier de tempo discreto (DTFT), que é uma função contínua e periódica. A DFT calcula N amostras igualmente espaçadas de um ciclo da DTFT. (ver Fig.2 e § Amostragem do DTFT)

Motivação

Eq.1 também pode ser avaliado fora do domínio ${displaystyle kin [0,N-1]}$ , e essa sequência estendida é $N$ -periódico. Assim, outras sequências de $N$ índices são às vezes usados, como ${textstyle left[-{frac {N}{2}},{frac {N}{2}}-1right]}$ (se) $N$ é mesmo) e ${textstyle left[-{frac {N-1}{2}},{frac {N-1}{2}}right]}$ (se) $N$ é estranho), o que equivale a trocar as metades esquerda e direita do resultado da transformação.

Eq.1 pode ser interpretada ou derivada de várias maneiras, por exemplo:

Ele descreve completamente a transformada de Fourier (DTFT) discreta de um $N$ -sequência periódica, que compreende apenas componentes de frequência discreta. (Usando o DTFT com dados periódicos)
Ele também pode fornecer amostras uniformemente espaçadas do DTFT contínuo de uma sequência de comprimento finito. (§ Sampling the DTFT)
É a correlação cruzada da entrada sequência, $x_{n}$ , e um sinusóide complexo na frequência ${textstyle {frac {k}{N}}}$ . Assim atua como um filtro combinado para essa frequência.

É o analógico discreto da fórmula para os coeficientes de uma série Fourier:

{displaystyle x_{n}={frac {1}{N}}sum _{k=0}^{N-1}X_{k}cdot e^{i2pi kn/N},quad nin mathbb {Z}}

(Eq.2)

que também $N$ -periódico. No domínio $n \in [0, N - 1...$ , este é o Transformação inversa de Eq.1. Nesta interpretação, cada $X_{k}$ é um número complexo que codifica a amplitude e a fase de um componente senoidal complexo ${displaystyle left(e^{i2pi kn/N}right)}$ de função $x_{n}$ . (veja a série Discrete Fourier) A frequência do sinusóide é k ciclos por N amostras. Sua amplitude e fase são:

{displaystyle {frac {1}{N}}|X_{k}|={frac {1}{N}}{sqrt {operatorname {Re} (X_{k})^{2}+operatorname {Im} (X_{k})^{2}}}}

{displaystyle arg(X_{k})=operatorname {atan2} {big (}operatorname {Im} (X_{k}),operatorname {Re} (X_{k}){big)}=-icdot ln left({frac {X_{k}}{|X_{k}|}}right),}

onde o atan2 é a forma de dois arranjos da função do arcotan. Em forma polar

{displaystyle X_{k}=|X_{k}|e^{iarg(X_{k})}=|X_{k}|operatorname {cis} arg(X_{k})}

onde cis é o mnemonic para cos + Eu... pecado.

O fator de normalização multiplicando o DFT e o IDFT (aqui 1 e ${textstyle {frac {1}{N}}}$ ) e os sinais dos expoentes são meramente convenções, e diferem em alguns tratamentos. Os únicos requisitos dessas convenções são que o DFT e o IDFT têm expoentes de sinal oposto e que o produto de seus fatores de normalização seja ${textstyle {frac {1}{N}}}$ . Uma normalização ${textstyle {sqrt {frac {1}{N}}}}$ tanto para o DFT quanto para o IDFT, por exemplo, faz as transformações unitárias. Um impulso discreto, ${displaystyle x_{n}=1}$ em n= 0 e 0 caso contrário; pode transformar-se ${displaystyle X_{k}=1}$ para todos k (utilizar fatores de normalização 1 para DFT e ${textstyle {frac {1}{N}}}$ para IDFT). Um sinal DC, ${displaystyle X_{k}=1}$ em k= 0 e 0 caso contrário; pode inversamente transformar-se ${displaystyle x_{n}=1}$ para todos $n$ (utilização) ${textstyle {frac {1}{N}}}$ para DFT e 1 para IDFT) que é consistente com a visualização DC como a média média do sinal.

Exemplo

Este exemplo demonstra como aplicar o DFT a uma sequência de comprimento $N=4$ e o vetor de entrada

${displaystyle mathbf {x} ={begin{pmatrix}x_{0}\x_{1}\x_{2}\x_{3}end{pmatrix}}={begin{pmatrix}1\2-i\-i\-1+2iend{pmatrix}}.}$

Calculando o DFT de $mathbf {x}$ usando Eq.1

${displaystyle X_{0}=e^{-i2pi 0cdot 0/4}cdot 1+e^{-i2pi 0cdot 1/4}cdot (2-i)+e^{-i2pi 0cdot 2/4}cdot (-i)+e^{-i2pi 0cdot 3/4}cdot (-1+2i)=2}$ ${displaystyle X_{1}=e^{-i2pi 1cdot 0/4}cdot 1+e^{-i2pi 1cdot 1/4}cdot (2-i)+e^{-i2pi 1cdot 2/4}cdot (-i)+e^{-i2pi 1cdot 3/4}cdot (-1+2i)=-2-2i}$ ${displaystyle X_{2}=e^{-i2pi 2cdot 0/4}cdot 1+e^{-i2pi 2cdot 1/4}cdot (2-i)+e^{-i2pi 2cdot 2/4}cdot (-i)+e^{-i2pi 2cdot 3/4}cdot (-1+2i)=-2i}$ ${displaystyle X_{3}=e^{-i2pi 3cdot 0/4}cdot 1+e^{-i2pi 3cdot 1/4}cdot (2-i)+e^{-i2pi 3cdot 2/4}cdot (-i)+e^{-i2pi 3cdot 3/4}cdot (-1+2i)=4+4i}$

Resultados ${displaystyle mathbf {X} ={begin{pmatrix}X_{0}\X_{1}\X_{2}\X_{3}end{pmatrix}}={begin{pmatrix}2\-2-2i\-2i\4+4iend{pmatrix}}.}$

Transformação inversa

A transformada discreta de Fourier é uma transformação linear invertível

{mathcal {F}}colon mathbb {C} ^{N}to mathbb {C} ^{N}

com $mathbb {C}$ denotando o conjunto de números complexos. Seu inverso é conhecido como Inverse Discrete Fourier Transform (IDFT). Em outras palavras, para qualquer $0}" xmlns="http://www.w3.org/1998/Math/MathML">N>0- Sim. 0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6b5e672f875388753faa233a18e9f2cf1275aaa4" style="vertical-align: -0.338ex; width:6.325ex; height:2.176ex;"/>$ , um Nvetor complexo -dimensional tem um DFT e um IDFT que estão por sua vez $N$ - vetores complexos dimensionais.

A transformada inversa é dada por:

{displaystyle x_{n}={frac {1}{N}}sum _{k=0}^{N-1}X_{k}cdot e^{i{frac {2pi }{N}}kn}}

(Eq.3)

Propriedades

Linearidade

O DFT é uma transformação linear, ou seja, se ${mathcal {F}}({x_{n}})_{k}=X_{k}$ e ${displaystyle {mathcal {F}}({y_{n}})_{k}=Y_{k}}$ , então para qualquer número complexo $a,b$ :

{displaystyle {mathcal {F}}({ax_{n}+by_{n}})_{k}=aX_{k}+bY_{k}}

Reversão de tempo e frequência

Reversão do tempo (ou seja, substituição $n$ por $N-n$ ) em $x_{n}$ corresponde a reverter a frequência (i.e. $k$ por $N-k$ ). Matematicamente, se ${x_{n}}$ representa o vetor x então

{mathcal {F}}({x_{n}})_{k}=X_{k}

então

{displaystyle {mathcal {F}}({x_{N-n}})_{k}=X_{N-k}}

Conjugação no tempo

Se ${displaystyle {mathcal {F}}({x_{n}})_{k}=X_{k}}$ então ${displaystyle {mathcal {F}}({x_{n}^{*}})_{k}=X_{N-k}^{*}}$ .

Parte real e imaginária

Esta tabela mostra algumas operações matemáticas em $x_{n}$ no domínio do tempo e os efeitos correspondentes em seu DFT $X_{k}$ no domínio de frequência.

Propriedade	Domínio de tempo $x_{n}$	Domínio de frequência $X_{k}$
Parte real no tempo	${displaystyle Re {left(x_{n}right)}}$	${displaystyle {frac {1}{2}}left(X_{k}+X_{N-k}^{*}right)}$
Parte imaginária no tempo	${displaystyle Im {left(x_{n}right)}}$	${displaystyle {frac {1}{2i}}left(X_{k}-X_{N-k}^{*}right)}$
Parte real na frequência	${displaystyle {frac {1}{2}}left(x_{n}+x_{N-n}^{*}right)}$	${displaystyle Re {left(X_{k}right)}}$
Parte imaginária na frequência	${displaystyle {frac {1}{2i}}left(x_{n}-x_{N-n}^{*}right)}$	${displaystyle Im {left(X_{k}right)}}$

Ortogonalidade

Os vetores ${displaystyle u_{k}=left[left.e^{{frac {i2pi }{N}}kn};right|;n=0,1,ldotsN-1right]^{mathsf {T}}}$ formar uma base ortogonal sobre o conjunto de Nvetores complexos dimensionais:

{displaystyle u_{k}^{mathsf {T}}u_{k'}^{*}=sum _{n=0}^{N-1}left(e^{{frac {i2pi }{N}}kn}right)left(e^{{frac {i2pi }{N}}(-k')n}right)=sum _{n=0}^{N-1}e^{{frac {i2pi }{N}}(k-k')n}=N~delta _{kk'}}

Onde? ${displaystyle delta _{kk'}}$ é a delta de Kronecker. (No último passo, a soma é trivial se $k=k'$ , onde está 1 + 1 + ≡ = N, e de outra forma é uma série geométrica que pode ser explicitamente resumida para obter zero.) Esta condição de ortogonal pode ser usada para derivar a fórmula para o IDFT da definição do DFT, e é equivalente à propriedade de unidade abaixo.

O teorema de Plancherel e o teorema de Parseval

Se $X_{k}$ e $Y_{k}$ são os DFTs de $x_{n}$ e $y_{n}$ respectivamente, em seguida, o teorema de Parseval afirma:

sum _{n=0}^{N-1}x_{n}y_{n}^{*}={frac {1}{N}}sum _{k=0}^{N-1}X_{k}Y_{k}^{*}

onde a estrela denota conjugação complexa. O teorema de Plancherel é um caso especial do teorema de Parseval e afirma:

sum _{n=0}^{N-1}|x_{n}|^{2}={frac {1}{N}}sum _{k=0}^{N-1}|X_{k}|^{2}.

Esses teoremas também são equivalentes à condição unitária abaixo.

Periodicidade

A periodicidade pode ser mostrada diretamente da definição:

{displaystyle X_{k+N} triangleq sum _{n=0}^{N-1}x_{n}e^{-{frac {i2pi }{N}}(k+N)n}=sum _{n=0}^{N-1}x_{n}e^{-{frac {i2pi }{N}}kn}underbrace {e^{-i2pi n}} _{1}=sum _{n=0}^{N-1}x_{n}e^{-{frac {i2pi }{N}}kn}=X_{k}.}

Da mesma forma, pode-se mostrar que a fórmula IDFT leva a uma extensão periódica.

Teorema da mudança

Multiplicação $x_{n}$ por um fase linear ${displaystyle e^{{frac {i2pi }{N}}nm}}$ para alguns inteiros m corresponde a um mudança circular da saída $X_{k}$ : $X_{k}$ é substituído por $X_{k-m}$ , onde o subscript é interpretado modulo N (i.e., periodicamente). Da mesma forma, uma mudança circular da entrada $x_{n}$ corresponde a multiplicar a saída $X_{k}$ por uma fase linear. Matematicamente, se ${x_{n}}$ representa o vetor x então

{mathcal {F}}({x_{n}})_{k}=X_{k}

então

{displaystyle {mathcal {F}}left(left{x_{n}cdot e^{{frac {i2pi }{N}}nm}right}right)_{k}=X_{k-m}}

{displaystyle {mathcal {F}}left(left{x_{n-m}right}right)_{k}=X_{k}cdot e^{-{frac {i2pi }{N}}km}}

Teorema da convolução circular e teorema da correlação cruzada

O teorema da convolução para a transformada de Fourier (DTFT) discreta indica que uma convolução de duas sequências pode ser obtida como a transformação inversa do produto das transformações individuais. Uma simplificação importante ocorre quando uma das sequências é N-periódica, denotada aqui por ${displaystyle y_{_{N}},}$ porque ${displaystyle scriptstyle {text{DTFT}}displaystyle {y_{_{N}}}}$ é não-zero em apenas frequências discretas (ver DTFT § dados periódicos), e, portanto, é seu produto com a função contínua ${displaystyle scriptstyle {text{DTFT}}displaystyle {x}.}$ Isso leva a uma simplificação considerável da transformação inversa.

{displaystyle x*y_{_{N}} = scriptstyle {rm {DTFT}}^{-1}displaystyle left[scriptstyle {rm {DTFT}}displaystyle {x}cdot scriptstyle {rm {DTFT}}displaystyle {y_{_{N}}}right] = scriptstyle {rm {DFT}}^{-1}displaystyle left[scriptstyle {rm {DFT}}displaystyle {x_{_{N}}}cdot scriptstyle {rm {DFT}}displaystyle {y_{_{N}}}right],}

Onde? ${displaystyle x_{_{N}}}$ é uma soma periódica do $x$ sequência: ${displaystyle (x_{_{N}})_{n} triangleq sum _{m=-infty }^{infty }x_{(n-mN)}.}$

Personalamente, as somas DFT e DFT inversa são tomadas sobre o domínio ${displaystyle [0,N-1]}$ . Definindo esses DFTs como $X$ e $Y$ , o resultado é:

{displaystyle (x*y_{_{N}})_{n}triangleq sum _{ell =-infty }^{infty }x_{ell }cdot (y_{_{N}})_{n-ell }=underbrace {{mathcal {F}}^{-1}} _{rm {DFT^{-1}}}left{Xcdot Yright}_{n}.}

Na prática, $x$ a sequência é geralmente comprimento N ou menos, e ${displaystyle y_{_{N}}}$ é uma extensão periódica de um comprimento N $y$ -sequência, que também pode ser expressa como função circular:

{displaystyle (y_{_{N}})_{n}=sum _{p=-infty }^{infty }y_{(n-pN)}=y_{(noperatorname {mod} N)},quad nin mathbb {Z}.}

Então a convolução pode ser escrita como:

${displaystyle {mathcal {F}}^{-1}left{Xcdot Yright}_{n}=sum _{ell =0}^{N-1}x_{ell }cdot y_{_{(n-ell)operatorname {mod} N}}}$

que dá origem à interpretação como um circular circular convolução de $x$ e $y.$ Muitas vezes é usado para calcular de forma eficiente sua convolução linear. (veja Convolução circular, algoritmos de convolução rápida e Overlap-save)

Da mesma forma, a correlação cruzada de $x$ e ${displaystyle y_{_{N}}}$ é dado por:

{displaystyle (xstar y_{_{N}})_{n}triangleq sum _{ell =-infty }^{infty }x_{ell }^{*}cdot (y_{_{N}})_{n+ell }={mathcal {F}}^{-1}left{X^{*}cdot Yright}_{n}.}

Foi demonstrado que qualquer transformação linear que transforme a convolução em produto pontual é a DFT (até uma permutação de coeficientes).

Dualidade do teorema da convolução

Também pode ser mostrado que:

{displaystyle {mathcal {F}}left{mathbf {xcdot y} right}_{k} triangleq sum _{n=0}^{N-1}x_{n}cdot y_{n}cdot e^{-i{frac {2pi }{N}}kn}}

{displaystyle ={frac {1}{N}}(mathbf {X*Y_{N}})_{k},}

que é a convolução circular de

mathbf {X}

mathbf {Y}

Polinômio de interpolação trigonométrica

O polinômio de interpolação trigonométrica

{displaystyle p(t)={begin{cases}{frac {1}{N}}left[X_{0}+X_{1}e^{i2pi t}+cdots +X_{N/2-1}e^{i2pi (N/2-1)t}+X_{N/2}cos(Npi t)+X_{N/2+1}e^{-i2pi (N/2-1)t}+cdots +X_{N-1}e^{-i2pi t}right]&N{text{ even}}\{frac {1}{N}}left[X_{0}+X_{1}e^{i2pi t}+cdots +X_{(N-1)/2}e^{i2pi (N-1)t}+X_{(N+1)/2}e^{-i2pi (N-1)t}+cdots +X_{N-1}e^{-i2pi t}right]&N{text{ odd}}end{cases}}}

onde os coeficientes X_k são dados pelo DFT de x_n acima, satisfaz a propriedade de interpolação $p(n/N)=x_{n}$ para ${displaystyle n=0,ldotsN-1}$ .

Pelo menos N, notar que o componente Nyquist ${textstyle {frac {X_{N/2}}{N}}cos(Npi t)}$ é tratado especialmente.

Esta interpolação é não único: aliasing implica que um poderia adicionar N para qualquer uma das frequências complexa-sinusóide (por exemplo, alteração $e^{-it}$ para $e^{i(N-1)t}$ ) sem alterar a propriedade de interpolação, mas dando diferente valores entre $x_{n}$ pontos. A escolha acima, no entanto, é típica porque tem duas propriedades úteis. Primeiro, consiste em sinusóides cujas frequências têm as menores magnitudes possíveis: a interpolação é limitada. Segundo, se o $x_{n}$ são números reais, então $p(t)$ também é real.

Em contraste, o polinômio de interpolação trigonométrica mais óbvio é aquele em que as frequências variam de 0 a $N-1$ (em vez de aproximadamente $-N/2$ para $+N/2$ como acima), semelhante à fórmula DFT inversa. Esta interpolação faz não minimizar a inclinação, e é não geralmente real para real $x_{n}$ ; seu uso é um erro comum.

A DFT unitária

Outra maneira de olhar para a DFT é observar que na discussão acima, a DFT pode ser expressa como a matriz DFT, uma matriz de Vandermonde, introduzido por Sylvester em 1867,

{displaystyle mathbf {F} ={begin{bmatrix}omega _{N}^{0cdot 0}&omega _{N}^{0cdot 1}&cdots &omega _{N}^{0cdot (N-1)}\omega _{N}^{1cdot 0}&omega _{N}^{1cdot 1}&cdots &omega _{N}^{1cdot (N-1)}\vdots &vdots &ddots &vdots \omega _{N}^{(N-1)cdot 0}&omega _{N}^{(N-1)cdot 1}&cdots &omega _{N}^{(N-1)cdot (N-1)}\end{bmatrix}}}

Onde? ${displaystyle omega _{N}=e^{-i2pi /N}}$ é uma Nth raiz primitiva da unidade.

Por exemplo, no caso em que $N=2$ , ${displaystyle omega _{N}=e^{-ipi }=-1}$ e

{displaystyle mathbf {F} ={begin{bmatrix}1&1\1&-1\end{bmatrix}},}

(que é uma matriz Hadamard) ou quando ${displaystyle N=4}$ como na Transformação Discreta Fourier § Exemplo acima, ${displaystyle omega _{N}=e^{-ipi /2}=i}$ e

{displaystyle mathbf {F} ={begin{bmatrix}1&1&1&1\1&i&-1&-i\1&-1&1&-1\1&-i&-1&I\end{bmatrix}}.}

A transformada inversa é então dada pelo inverso da matriz acima,

mathbf {F} ^{-1}={frac {1}{N}}mathbf {F} ^{*}

Com constantes de normalização unitária ${textstyle 1/{sqrt {N}}}$ , o DFT se torna uma transformação unitária, definida por uma matriz unitária:

{displaystyle {begin{aligned}mathbf {U} &={frac {1}{sqrt {N}}}mathbf {F} \mathbf {U} ^{-1}&=mathbf {U} ^{*}\left|det(mathbf {U})right|&=1end{aligned}}}

Onde? ${displaystyle det()}$ é a função determinante. O determinante é o produto dos autovalores, que são sempre $pm 1$ ou $pm i$ como descrito abaixo. Em um espaço vetorial real, uma transformação unitária pode ser pensada como simplesmente uma rotação rígida do sistema de coordenadas, e todas as propriedades de uma rotação rígida podem ser encontradas no DFT unitário.

A ortogonalidade da DFT agora é expressa como uma condição de ortonormalidade (que surge em muitas áreas da matemática, conforme descrito na raiz da unidade):

{displaystyle sum _{m=0}^{N-1}U_{km}U_{mn}^{*}=delta _{kn}}

Se X for definido como a DFT unitária do vetor x, então

{displaystyle X_{k}=sum _{n=0}^{N-1}U_{kn}x_{n}}

e o teorema de Parseval é expresso como

sum _{n=0}^{N-1}x_{n}y_{n}^{*}=sum _{k=0}^{N-1}X_{k}Y_{k}^{*}

Se nós vemos o DFT como apenas uma transformação de coordenadas que simplesmente especifica os componentes de um vetor em um novo sistema de coordenadas, então o acima é apenas a afirmação de que o produto do ponto de dois vetores é preservado sob uma transformação DFT unitária. Para o caso especial $mathbf {x} =mathbf {y}$ , isto implica que o comprimento de um vetor também é preservado — este é apenas o teorema de Plancherel,

{displaystyle sum _{n=0}^{N-1}|x_{n}|^{2}=sum _{k=0}^{N-1}|X_{k}|^{2}}

Uma consequência do teorema da convolução circular é que a matriz DFT $F$ diagonaliza qualquer matriz circulante.

Expressando a DFT inversa em termos da DFT

Uma propriedade útil da DFT é que a DFT inversa pode ser facilmente expressa em termos da DFT (direta), por meio de vários "truques" bem conhecidos. (Por exemplo, em cálculos, geralmente é conveniente implementar apenas uma transformada rápida de Fourier correspondente a uma direção de transformação e, em seguida, obter a outra direção de transformação a partir da primeira.)

Primeiro, podemos calcular a DFT inversa invertendo todas as entradas, exceto uma (Duhamel et al., 1988):

{displaystyle {mathcal {F}}^{-1}({x_{n}})={frac {1}{N}}{mathcal {F}}({x_{N-n}})}

(Como de costume, os subescritos são interpretados modulo N; assim, para $n=0$ nós temos ${displaystyle x_{N-0}=x_{0}}$ .)

Em segundo lugar, também é possível conjugar as entradas e saídas:

{displaystyle {mathcal {F}}^{-1}(mathbf {x})={frac {1}{N}}{mathcal {F}}left(mathbf {x} ^{*}right)^{*}}

Em terceiro lugar, uma variante deste truque de conjugação, que às vezes é preferível porque não requer modificação dos valores de dados, envolve trocar partes reais e imaginárias (que pode ser feito em um computador simplesmente modificando ponteiros). Definir ${textstyle operatorname {swap} (x_{n})}$ como $x_{n}$ com suas partes reais e imaginárias trocadas — isto é, se $x_{n}=a+bi$ então ${textstyle operatorname {swap} (x_{n})}$ o $b+ai$ . Equivalentemente, ${textstyle operatorname {swap} (x_{n})}$ iguais $ix_{n}^{*}$ . Então...

{displaystyle {mathcal {F}}^{-1}(mathbf {x})={frac {1}{N}}operatorname {swap} ({mathcal {F}}(operatorname {swap} (mathbf {x})))}

Ou seja, a transformada inversa é igual à transformada direta com as partes real e imaginária trocadas tanto para entrada quanto para saída, até uma normalização (Duhamel et al., 1988).

O truque de conjugação também pode ser usado para definir uma nova transformação, estreitamente relacionada com o DFT, que é involutória - isto é, que é seu próprio inverso. Em particular, ${displaystyle T(mathbf {x})={mathcal {F}}left(mathbf {x} ^{*}right)/{sqrt {N}}}$ é claramente seu próprio inverso: $T(T(mathbf {x}))=mathbf {x}$ . Uma transformação involutória estreitamente relacionada (por um fator de ${textstyle {frac {1+i}{sqrt {2}}}}$ ) ${displaystyle H(mathbf {x})={mathcal {F}}left((1+i)mathbf {x} ^{*}right)/{sqrt {2N}}}$ , desde o ${displaystyle (1+i)}$ fatores $H(H(mathbf {x}))$ cancelar o 2. Para entradas reais $mathbf {x}$ , a parte real de $H(mathbf {x})$ não é mais do que a transformada de Hartley discreta, que também é involutória.

Autovalores e autovetores

Os autovalores da matriz DFT são simples e bem conhecidos, enquanto os autovetores são complicados, não únicos e são objeto de pesquisas em andamento.

Considere a forma unitária $mathbf {U}$ definido acima para o DFT de comprimento N, onde

{displaystyle mathbf {U} _{m,n}={frac {1}{sqrt {N}}}omega _{N}^{(m-1)(n-1)}={frac {1}{sqrt {N}}}e^{-{frac {i2pi }{N}}(m-1)(n-1)}.}

Esta matriz satisfaz a equação polinomial da matriz:

mathbf {U} ^{4}=mathbf {I}.

Isso pode ser visto a partir das propriedades inversas acima: operando $mathbf {U}$ duas vezes dá os dados originais em ordem reversa, então operando $mathbf {U}$ quatro vezes devolve os dados originais e é assim a matriz de identidade. Isso significa que os autovalores $lambda$ satisfazer a equação:

lambda ^{4}=1.

Portanto, os eigenvalues de $mathbf {U}$ são as quartas raízes da unidade: $lambda$ é +1, −1, +Eu..., ou −Eu....

Uma vez que há apenas quatro eigenvalues distintos para isso $Ntimes N$ matriz, eles têm alguma multiplicidade. A multiplicidade dá o número de eigenvectores linearmente independentes correspondentes a cada eigenvalue. (Há N eigenvectors independentes; uma matriz unitária nunca é defeituosa.)

O problema da sua multiplicidade foi resolvido por McClellan e Parks (1972), embora mais tarde tenha sido demonstrado ter sido equivalente a um problema resolvido por Gauss (Dickinson e Steiglitz, 1982). A multiplicidade depende do valor de N módulo 4, e é dada pela seguinte tabela:

Multiplicidades dos autovalores λ da matriz DFT unitária U como uma função do tamanho da transformação N (em termos de um inteiro m).
tamanho N	λ = +1	λ = −1	λ = −Eu...	λ = +Eu...
4m	m + 1	m	m	m - 1
4m + 1	m + 1	m	m	m
4m + 2	m + 1	m + 1	m	m
4m + 3	m + 1	m + 1	m + 1	m

De outra forma, o polinômio característico de $mathbf {U}$ é:

det(lambda I-mathbf {U})=(lambda -1)^{leftlfloor {tfrac {N+4}{4}}rightrfloor }(lambda +1)^{leftlfloor {tfrac {N+2}{4}}rightrfloor }(lambda +i)^{leftlfloor {tfrac {N+1}{4}}rightrfloor }(lambda -i)^{leftlfloor {tfrac {N-1}{4}}rightrfloor }.

Nenhuma fórmula analítica simples para autovetores gerais é conhecida. Além disso, os autovetores não são únicos porque qualquer combinação linear de autovetores para o mesmo autovalor também é um autovetor para esse autovalor. Vários pesquisadores propuseram diferentes escolhas de autovetores, selecionados para satisfazer propriedades úteis como ortogonalidade e ter propriedades "simples" formas (por exemplo, McClellan e Parks, 1972; Dickinson e Steiglitz, 1982; Grünbaum, 1982; Atakishiyev e Wolf, 1997; Candan et al., 2000; Hanna et al., 2004; Gurevich e Hadani, 2008).

Uma abordagem direta é discretizar uma autofunção da transformada contínua de Fourier, das quais a mais famosa é a função gaussiana. Como a soma periódica da função significa discretizar seu espectro de frequência e discretização significa soma periódica do espectro, a função Gaussiana discretizada e periodicamente somada produz um autovetor da transformada discreta:

${displaystyle F(m)=sum _{kin mathbb {Z} }exp left(-{frac {pi cdot (m+Ncdot k)^{2}}{N}}right).}$

A expressão de forma fechada para a série pode ser expressa por funções theta de Jacobi como

${displaystyle F(m)={frac {1}{sqrt {N}}}vartheta _{3}left({frac {pi m}{N}},exp left(-{frac {pi }{N}}right)right).}$

Dois outros autovetores analíticos simples de forma fechada para o período DFT especial N foram encontrados (Kong, 2008):

Para o período DFT N = 2L + 1 = 4K + 1, onde K é um integer, o seguinte é um autovetor de DFT:

${displaystyle F(m)=prod _{s=K+1}^{L}left[cos left({frac {2pi }{N}}mright)-cos left({frac {2pi }{N}}sright)right]}$

Para o período DFT N = 2L = 4K, onde K é um número inteiro, o seguinte é um autovetor de DFT:

${displaystyle F(m)=sin left({frac {2pi }{N}}mright)prod _{s=K+1}^{L-1}left[cos left({frac {2pi }{N}}mright)-cos left({frac {2pi }{N}}sright)right]}$

A escolha dos autovetores da matriz DFT tornou-se importante nos últimos anos para definir um análogo discreto da transformada fracionária de Fourier - a matriz DFT pode ser levada a potências fracionárias exponenciando os autovalores (por exemplo, Rubio e Santhanam, 2005). Para a transformada de Fourier contínua, as autofunções ortogonais naturais são as funções de Hermite, então vários análogos discretos destas têm sido empregados como autovetores da DFT, como os polinômios de Kravchuk (Atakishiyev e Wolf, 1997). O "melhor" escolha de autovetores para definir uma transformada de Fourier discreta fracionária permanece uma questão em aberto, no entanto.

Princípios de incerteza

Princípio da incerteza probabilística

Se a variável aleatória $X k$ for restrita por

{displaystyle sum _{n=0}^{N-1}|X_{n}|^{2}=1,}

então

P_{n}=|X_{n}|^{2}

pode ser considerado como representando uma função de massa de probabilidade discreta de $n$ , com uma função de massa de probabilidade associada construída a partir da variável transformada,

{displaystyle Q_{m}=N|x_{m}|^{2}.}

Para o caso de funções contínuas $P(x)$ e $Q(k)$ , o princípio de incerteza de Heisenberg afirma que

D_{0}(X)D_{0}(x)geq {frac {1}{16pi ^{2}}}

Onde? $D_{0}(X)$ e $D_{0}(x)$ são as variações de $|X|^{2}$ e $|x|^{2}$ respectivamente, com a igualdade alcançada no caso de uma distribuição gaussiana adequadamente normalizada. Embora as variâncias possam ser analógicamente definidas para o DFT, um princípio de incerteza analógica não é útil, porque a incerteza não será invariante de turno. Ainda assim, um princípio de incerteza significativa foi introduzido por Massar e Spindel.

No entanto, a incerteza entrópica de Hirschman terá um análogo útil para o caso da DFT. O princípio da incerteza de Hirschman é expresso em termos da entropia de Shannon das duas funções de probabilidade.

No caso discreto, as entropias de Shannon são definidas como

H(X)=-sum _{n=0}^{N-1}P_{n}ln P_{n}

{displaystyle H(x)=-sum _{m=0}^{N-1}Q_{m}ln Q_{m},}

e o princípio da incerteza entrópica torna-se

{displaystyle H(X)+H(x)geq ln(N).}

A igualdade é obtida para $P_{n}$ igual a traduções e modulações de um pente de Kronecker adequadamente normalizado de período $A$ Onde? $A$ é qualquer divisor inteiro exato de $N$ . A função de massa de probabilidade $Q_{m}$ será então proporcional a um devidamente traduzido pente de Kronecker de período $B=N/A$ .

Princípio da incerteza determinística

Há também um conhecido princípio de incerteza determinística que usa esparsidade de sinal (ou o número de coeficientes não-zero). Vamos. ${displaystyle left|xright|_{0}}$ e ${displaystyle left|Xright|_{0}}$ ser o número de elementos não-zero das sequências de tempo e frequência $x_{0},x_{1},ldotsx_{N-1}$ e $X_{0},X_{1},ldotsX_{N-1}$ , respectivamente. Então,

{displaystyle Nleq left|xright|_{0}cdot left|Xright|_{0}.}

Como consequência imediata da desigualdade de meios aritméticos e geométricos, um também tem ${displaystyle 2{sqrt {N}}leq left|xright|_{0}+left|Xright|_{0}}$ . Ambos os princípios de incerteza foram mostrados para seqüências "picket-fence" especificamente escolhidas (comboios de impulso discretos), e encontrar uso prático para aplicações de recuperação de sinais.

DFT de sinais reais e puramente imaginários

Se $x_{0},ldotsx_{N-1}$ são números reais, como muitas vezes estão em aplicações práticas, em seguida, o DFT ${displaystyle X_{0},ldotsX_{N-1}}$ é mesmo simétrica:

{displaystyle x_{n}in mathbb {R} quad forall nin {0,ldotsN-1}implies X_{k}=X_{-kmod N}^{*}quad forall kin {0,ldotsN-1}}

, onde

X^{*},

denota conjugação complexa.

Segue-se que até $N$ $X_{0}$ e ${displaystyle X_{N/2}}$ são reais, e o restante do DFT é completamente especificado por apenas ${displaystyle N/2-1}$ números complexos.

Se $x_{0},ldotsx_{N-1}$ são números puramente imaginários, então o DFT ${displaystyle X_{0},ldotsX_{N-1}}$ é odd simétrica:

{displaystyle x_{n}in imathbb {R} quad forall nin {0,ldotsN-1}implies X_{k}=-X_{-kmod N}^{*}quad forall kin {0,ldotsN-1}}

, onde

X^{*},

denota conjugação complexa.

DFT generalizado (fase deslocada e não linear)

É possível deslocar a amostragem transformada no domínio do tempo e/ou da frequência por alguns deslocamentos reais a e b, respectivamente. Às vezes, isso é conhecido como DFT generalizado (ou GDFT), também chamado de DFT deslocado ou DFT de deslocamento, e tem propriedades análogas à DFT comum:

{displaystyle X_{k}=sum _{n=0}^{N-1}x_{n}e^{-{frac {i2pi }{N}}(k+b)(n+a)}quad quad k=0,dotsN-1.}

Na maioria das vezes, turnos de $1/2$ (meia amostra) são usados. Enquanto o DFT comum corresponde a um sinal periódico em ambos os domínios de tempo e frequência, $a=1/2$ produz um sinal que é anti-peródico no domínio de frequência ( $X_{k+N}=-X_{k}$ ) e vice-versa para $b=1/2$ . Assim, o caso específico de $a=b=1/2$ é conhecido como um odd-time odd-frequency transformada de Fourier discreta (ou O² DFT). Tais transformaçÃμes deslocadas são mais frequentemente usadas para dados simétricos, para representar diferentes simetrias de fronteira, e para dados simétricos reais que correspondem a diferentes formas das transformaçÃμes de cossenos e seios discretas.

Outra escolha interessante é $a=b=-(N-1)/2$ , que é chamado de DFT centralizado (ou CDFT). O DFT centralizado tem a propriedade útil que, quando N é um múltiplo de quatro, todos os quatro de seus valores de eigen (ver acima) têm multiplicidades iguais (Rubio e Santhanam, 2005)

O termo GDFT também é usado para as extensões de fase não lineares de DFT. Portanto, o método GDFT fornece uma generalização para transformadas de blocos ortogonais de amplitude constante, incluindo tipos de fase linear e não linear. GDFT é uma estrutura para melhorar as propriedades do domínio do tempo e da frequência da DFT tradicional, por ex. auto/correlações cruzadas, pela adição da função de modelagem de fase adequadamente projetada (não linear, em geral) às funções de fase lineares originais (Akansu e Agirman-Tosun, 2010).

A transformada discreta de Fourier pode ser vista como um caso especial da transformada z, avaliada no círculo unitário no plano complexo; as transformações z mais gerais correspondem aos deslocamentos complexos a e b acima.

DFT multidimensional

O DFT comum transforma uma sequência ou matriz unidimensional $x_{n}$ que é uma função de exatamente uma variável discreta n. O DFT multidimensional de uma matriz multidimensional $x_{n_{1},n_{2},dotsn_{d}}$ que é uma função de D variáveis discretas $n_{ell }=0,1,dotsN_{ell }-1$ para $ell$ em $1,2,dotsd$ é definido por:

{displaystyle X_{k_{1},k_{2},dotsk_{d}}=sum _{n_{1}=0}^{N_{1}-1}left(omega _{N_{1}}^{~k_{1}n_{1}}sum _{n_{2}=0}^{N_{2}-1}left(omega _{N_{2}}^{~k_{2}n_{2}}cdots sum _{n_{d}=0}^{N_{d}-1}omega _{N_{d}}^{~k_{d}n_{d}}cdot x_{n_{1},n_{2},dotsn_{d}}right)right),}

Onde? ${displaystyle omega _{N_{ell }}=exp(-i2pi /N_{ell })}$ como acima e o D índices de saída rodam de $k_{ell }=0,1,dotsN_{ell }-1$ . Isso é mais compactamente expresso em notação vetorial, onde definimos $mathbf {n} =(n_{1},n_{2},dotsn_{d})$ e $mathbf {k} =(k_{1},k_{2},dotsk_{d})$ como Dvetores dimensionais de índices de 0 a $mathbf {N} -1$ , que definemos como $mathbf {N} -1=(N_{1}-1,N_{2}-1,dotsN_{d}-1)$ :

{displaystyle X_{mathbf {k} }=sum _{mathbf {n} =mathbf {0} }^{mathbf {N} -1}e^{-i2pi mathbf {k} cdot (mathbf {n} /mathbf {N})}x_{mathbf {n} },,}

onde a divisão $mathbf {n} /mathbf {N}$ é definido como $mathbf {n} /mathbf {N} =(n_{1}/N_{1},dotsn_{d}/N_{d})$ para ser realizada element-wise, e a soma denota o conjunto de somas aninhadas acima.

O inverso da DFT multidimensional é, análogo ao caso unidimensional, dado por:

{displaystyle x_{mathbf {n} }={frac {1}{prod _{ell =1}^{d}N_{ell }}}sum _{mathbf {k} =mathbf {0} }^{mathbf {N} -1}e^{i2pi mathbf {n} cdot (mathbf {k} /mathbf {N})}X_{mathbf {k} },.}

Como o DFT unidimensional expressa a entrada $x_{n}$ como uma superposição de sinusóides, o DFT multidimensional expressa a entrada como uma superposição de ondas planas, ou seios multidimensionais. A direção da oscilação no espaço é $mathbf {k} /mathbf {N}$ . As amplitudes são $X_{mathbf {k} }$ . Esta decomposição é de grande importância para tudo, desde o processamento digital de imagens (duas dimensões) para resolver equações diferenciais parciais. A solução é quebrada em ondas de avião.

O DFT multidimensional pode ser computado pela composição de uma sequência de DFTs unidimensionais ao longo de cada dimensão. No caso bidimensional $x_{n_{1},n_{2}}$ o $N_{1}$ DFTs independentes das linhas (i.e., ao longo $n_{2}$ ) são computados primeiro para formar um novo array $y_{n_{1},k_{2}}$ . Então, $N_{2}$ DFTs independentes de Sim. ao longo das colunas (ao longo $n_{1}$ ) são computados para formar o resultado final $X_{k_{1},k_{2}}$ . Alternativamente as colunas podem ser computadas primeiro e depois as linhas. A ordem é immaterial porque as somas aninhadas acima commute.

Um algoritmo para calcular uma DFT unidimensional é, portanto, suficiente para calcular eficientemente uma DFT multidimensional. Essa abordagem é conhecida como algoritmo linha-coluna. Existem também algoritmos FFT intrinsecamente multidimensionais.

A DFT multidimensional de entrada real

Para dados de entrada $x_{n_{1},n_{2},dotsn_{d}}$ consistindo em números reais, as saídas DFT têm uma simetria conjugada semelhante ao caso unidimensional acima:

X_{k_{1},k_{2},dotsk_{d}}=X_{N_{1}-k_{1},N_{2}-k_{2},dotsN_{d}-k_{d}}^{*},

onde a estrela novamente denota a conjugação complexa e a $ell$ -o subscript é novamente interpretado modulo $N_{ell }$ (para $ell =1,2,ldotsd$ ).

Aplicativos

O DFT tem sido amplamente utilizado em um grande número de campos; apenas esboçamos alguns exemplos abaixo (veja também as referências no final). Todas as aplicações da DFT dependem crucialmente da disponibilidade de um algoritmo rápido para calcular transformadas discretas de Fourier e suas inversas, uma transformada rápida de Fourier.

Análise espectral

Transformações discretas incorporadas no tempo e espaço.

Quando o DFT é usado para análise espectral de sinal, o ${x_{n}}$ a sequência geralmente representa um conjunto finito de amostras de tempo uniformemente espaçadas de algum sinal $x(t),$ , onde $t$ representa tempo. A conversão de tempo contínuo para amostras (tempo de discreto) muda a transformação de Fourier subjacente $x(t)$ em uma transformada de Fourier de tempo discreto (DTFT), que geralmente implica um tipo de distorção chamado aliasing. Escolha de uma taxa de amostra adequada (ver Taxa de Nyquist) é a chave para minimizar essa distorção. Da mesma forma, a conversão de uma sequência muito longa (ou infinita) para um tamanho gerenciável implica um tipo de distorção chamado vazamento, que se manifesta como uma perda de detalhes (a.k.a. resolução) no DTFT. A escolha de um comprimento de sub-sequência apropriado é a chave primária para minimizar esse efeito. Quando os dados disponíveis (e tempo para processá-lo) é mais do que a quantidade necessária para alcançar a resolução de frequência desejada, uma técnica padrão é executar vários DFTs, por exemplo para criar um espectrograma. Se o resultado desejado é um espectro de energia e ruído ou aleatoriedade está presente nos dados, a média dos componentes de magnitude dos DFTs múltiplos é um procedimento útil para reduzir a variância do espectro (também chamado de periodograma neste contexto); dois exemplos dessas técnicas são o método Welch e o método Bartlett; o sujeito geral de estimar o espectro de energia de um sinal ruidoso é chamado de estimativa espectral.

Uma fonte final de distorção (ou talvez ilusão) é a própria DFT, porque é apenas uma amostragem discreta da DTFT, que é uma função de um domínio de frequência contínuo. Isso pode ser mitigado aumentando a resolução da DFT. Esse procedimento é ilustrado em § Amostragem do DTFT.

O procedimento é por vezes referido como zero de pagamento, que é uma implementação particular usada em conjunto com o algoritmo de transformação rápida de Fourier (FFT). A ineficiência de realizar multiplicações e adições com "amostras" de valor zero é mais do que compensada pela eficiência inerente do FFT.
Como já afirmado, o vazamento impõe um limite para a resolução inerente do DTFT, portanto, há um limite prático para o benefício que pode ser obtido a partir de um DFT de granulação fina.

Óptica, difração e tomografia

A transformada discreta de Fourier é amplamente usada com frequências espaciais na modelagem da maneira como a luz, os elétrons e outras sondas viajam através de sistemas ópticos e se espalham de objetos em duas e três dimensões. O espaço vetorial dual (direto/recíproco) de objetos tridimensionais disponibiliza ainda uma rede recíproca tridimensional, cuja construção a partir de sombras de objetos translúcidos (através do teorema da fatia de Fourier) permite a reconstrução tomográfica de objetos tridimensionais com uma ampla gama de aplicações, por exemplo, na medicina moderna.

Banco de filtros

Consulte § Bancos de filtro FFT e § Amostragem do DTFT.

Compressão de dados

O campo de processamento de sinal digital depende fortemente de operações no domínio da frequência (ou seja, na transformada de Fourier). Por exemplo, vários métodos de compressão de imagem e som com perdas empregam a transformada discreta de Fourier: o sinal é cortado em segmentos curtos, cada um é transformado e, em seguida, os coeficientes de Fourier de altas frequências, que são considerados imperceptíveis, são descartados. O descompressor calcula a transformada inversa com base neste número reduzido de coeficientes de Fourier. (Os aplicativos de compactação geralmente usam uma forma especializada da DFT, a transformada discreta de cosseno ou, às vezes, a transformada discreta de cosseno modificada.) Alguns algoritmos de compressão relativamente recentes, no entanto, usam transformadas wavelet, que fornecem um compromisso mais uniforme entre o domínio do tempo e da frequência do que o obtido dividindo os dados em segmentos e transformando cada segmento. No caso do JPEG2000, isso evita os recursos de imagem espúrios que aparecem quando as imagens são altamente compactadas com o JPEG original.

Equações diferenciais parciais

Transformações de Fourier discretas são frequentemente usadas para resolver equações diferenciais parciais, onde novamente o DFT é usado como uma aproximação para a série Fourier (que é recuperado no limite de infinito N). A vantagem desta abordagem é que expande o sinal em exponenciais complexos ${displaystyle e^{inx}}$ , que são eigenfunctions da diferenciação: ${displaystyle {{text{d}}{big (}e^{inx}{big)}}/{text{d}}x=ine^{inx}}$ . Assim, na representação de Fourier, a diferenciação é simples - nós apenas multiplicamos por $in$ . (No entanto, a escolha de $n$ não é único devido ao aliasing; para o método ser convergente, uma escolha semelhante à que na seção de interpolação trigonométrica acima deve ser usada.) Uma equação diferencial linear com coeficientes constantes é transformada em uma equação algébrica facilmente solvável. Um então usa o DFT inverso para transformar o resultado de volta para a representação espacial comum. Essa abordagem é chamada de método espectral.

Multiplicação polinomial

Suponha que desejamos calcular o produto polinomial c(x) = a(x) · b(x). A expressão de produto comum para os coeficientes de c envolve uma convolução linear (acíclica), onde os índices não "envolvem." Isso pode ser reescrito como uma convolução cíclica, tomando os vetores de coeficiente para a(x) e b(x) com termo constante primeiro, depois anexando zeros para que os vetores de coeficientes resultantes a e b tenham dimensão d > deg(a(x)) + deg(b(x)). Então,

mathbf {c} =mathbf {a} *mathbf {b}

Onde? c é o vetor de coeficientes para c(x), e o operador de convolução $*,$ é definido assim

c_{n}=sum _{m=0}^{d-1}a_{m}b_{n-m mathrm {mod} d}qquad qquad qquad n=0,1dotsd-1

Mas a convolução torna-se multiplicação sob a DFT:

{mathcal {F}}(mathbf {c})={mathcal {F}}(mathbf {a}){mathcal {F}}(mathbf {b})

Aqui o produto vetorial é obtido elemento a elemento. Assim, os coeficientes do produto polinomial c(x) são apenas os termos 0,..., deg(a(x )) + deg(b(x)) do vetor de coeficientes

mathbf {c} ={mathcal {F}}^{-1}({mathcal {F}}(mathbf {a}){mathcal {F}}(mathbf {b})).

Com uma transformação rápida de Fourier, o algoritmo resultante realiza O(N log N) operações aritméticas. Devido à sua simplicidade e velocidade, o algoritmo Cooley-Tukey FFT, que é limitado a tamanhos compostos, é frequentemente escolhido para a operação de transformação. Nesse caso, d deve ser escolhido como o menor inteiro maior que a soma dos graus polinomiais de entrada que é fatorável em pequenos fatores primos (por exemplo, 2, 3 e 5, dependendo da implementação da FFT).

Multiplicação de inteiros grandes

Os algoritmos mais conhecidos para a multiplicação de inteiros muito grandes usam o método de multiplicação polinomial descrito acima. Os inteiros podem ser tratados como o valor de um polinômio avaliado especificamente na base de números, com os coeficientes do polinômio correspondente aos dígitos nessa base (ex. ${displaystyle 123=1cdot 10^{2}+2cdot 10^{1}+3cdot 10^{0}}$ ). Após a multiplicação polinomial, uma etapa de transpropagação relativamente baixa complexidade completa a multiplicação.

Convolução

Quando os dados são convoluídos com uma função com amplo suporte, como para redução de amostragem por uma grande taxa de amostragem, devido ao teorema da convolução e ao algoritmo FFT, pode ser mais rápido transformá-los, multiplicar ponto a ponto pela transformação do filtro e, em seguida, transformá-lo inversamente. Alternativamente, um bom filtro é obtido simplesmente truncando os dados transformados e retransformando o conjunto de dados encurtado.

Alguns pares discretos de transformada de Fourier

**Alguns pares DFT**
$x_{n}={frac {1}{N}}sum _{k=0}^{N-1}X_{k}e^{i2pi kn/N}$	$X_{k}=sum _{n=0}^{N-1}x_{n}e^{-i2pi kn/N}$	Nota
$x_{n}e^{i2pi nell /N},$	$X_{k-ell },$	Teorem de deslocamento de frequência
$x_{n-ell },$	$X_{k}e^{-i2pi kell /N},$	Teorem de turnos
$x_{n}in mathbb {R}$	$X_{k}=X_{N-k}^{*},$	Real DFT
$a^{n},$	$left{{begin{matrix}N&{mbox{if }}a=e^{i2pi k/N}\{frac {1-a^{N}}{1-a,e^{-i2pi k/N}}}&{mbox{otherwise}}end{matrix}}right.$	da fórmula de progressão geométrica
${N-1 choose n},$	$left(1+e^{-i2pi k/N}right)^{N-1},$	do teorema binomial
$<math alttext="{displaystyle left{{begin{matrix}{frac {1}{W}}&{mbox{if }}2n<W{mbox{ or }}2(N-n)(1Wse2n<Wou2(N- Sim. - Sim. n)<W0caso contrário{displaystyle left{{begin{matrix}{frac {1}{W}}&{mbox{if }}2n<W{mbox{ or }}2(N-n)<W\0&{mbox{otherwise}}end{matrix}}right.}<img alt="left{{begin{matrix}{frac {1}{W}}&{mbox{if }}2n<W{mbox{ or }}2(N-n)$	$left{{begin{matrix}1&{mbox{if }}k=0\{frac {sin left({frac {pi Wk}{N}}right)}{Wsin left({frac {pi k}{N}}right)}}&{mbox{otherwise}}end{matrix}}right.$	$x_{n}$ é uma função de janela retangular W pontos centrados em n=0, onde W é um inteiro estranho, e $X_{k}$ é uma função semelhante a sinc (especificamente, $X_{k}$ é um kernel Dirichlet)
$sum _{jin mathbb {Z} }exp left(-{frac {pi }{cN}}cdot (n+Ncdot j)^{2}right)$	${sqrt {cN}}cdot sum _{jin mathbb {Z} }exp left(-{frac {pi c}{N}}cdot (k+Ncdot j)^{2}right)$	Discretização e síntese periódica das funções gaussianas dimensionadas para $0}" xmlns="http://www.w3.org/1998/Math/MathML">c>0- Sim. 0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ba126f626d61752f62eaacaf11761a54de4dc84" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;"/>$ . Desde que $c$ ou ${frac {1}{c}}$ é maior que um e, portanto, garante a convergência rápida de uma das duas séries, para grande $c$ você pode optar por calcular o espectro de frequência e converter para o domínio do tempo usando a transformada discreta de Fourier.

Generalizações

Teoria da representação

O DFT pode ser interpretado como uma representação complexa do grupo cíclico finito. Em outras palavras, uma sequência de $n$ números complexos podem ser pensados como um elemento de $n$ - espaço complexo dimensional $mathbb {C} ^{n}$ ou equivalente a uma função $f$ do grupo cíclico finito de ordem $n$ para os números complexos, ${displaystyle mathbb {Z} _{n}mapsto mathbb {C} }$ . Então... $f$ é uma função de classe no grupo cíclico finito, e assim pode ser expressa como uma combinação linear dos caracteres irredutíveis deste grupo, que são as raízes da unidade.

Desse ponto de vista, pode-se generalizar a DFT para a teoria da representação em geral, ou mais especificamente para a teoria da representação de grupos finitos.

Mais especificamente, pode-se generalizar a DFT alterando o alvo (obtendo valores em um campo diferente dos números complexos) ou o domínio (um grupo diferente de um grupo cíclico finito), conforme detalhado a seguir.

Outros campos

Muitas das propriedades do DFT dependem apenas do fato de que ${displaystyle e^{-{frac {i2pi }{N}}}}$ é uma raiz primitiva da unidade, às vezes denotada $omega _{N}$ ou $W_{N}$ (para $omega _{N}^{N}=1$ ). Tais propriedades incluem a totalidade, ortogonalidade, Plancherel/Parseval, periodicidade, deslocamento, convolução e propriedades unitaridade acima, bem como muitos algoritmos FFT. Por esta razão, a transformada de Fourier discreta pode ser definida usando raízes de unidade em campos diferentes dos números complexos, e tais generalizações são comumente chamadas de transformadores teóricos do número (NTTs) no caso de campos finitos. Para obter mais informações, consulte a transformação número-teórico e a transformada de Fourier discreta (geral).

Outros grupos finitos

A DFT padrão atua em uma sequência x₀, x₁,..., x_N−1 de números complexos, que podem ser vistos como uma função {0, 1,..., N − 1} → C. A DFT multidimensional atua em sequências multidimensionais, que podem ser vistas como funções

{0,1,ldotsN_{1}-1}times cdots times {0,1,ldotsN_{d}-1}to mathbb {C}.

Isto sugere a generalização para transformadas de Fourier em grupos finitos arbitrários, que atuam em funções G → C onde G é um grupo finito. Nesta estrutura, a DFT padrão é vista como a transformada de Fourier em um grupo cíclico, enquanto a DFT multidimensional é uma transformada de Fourier em uma soma direta de grupos cíclicos.

Além disso, a transformada de Fourier pode estar em coconjuntos de um grupo.

Alternativas

Existem várias alternativas ao DFT para diversas aplicações, destacando-se entre elas as wavelets. O análogo da DFT é a transformada discreta wavelet (DWT). Do ponto de vista da análise tempo-frequência, uma limitação importante da transformada de Fourier é que ela não inclui informações de localização, apenas informações de frequência e, portanto, tem dificuldade em representando transientes. Como as wavelets têm localização e frequência, elas são mais capazes de representar a localização, mas apresentam maior dificuldade em representar a frequência. Para obter detalhes, consulte a comparação da transformada wavelet discreta com a transformada discreta de Fourier.

Contenido relacionado

Más resultados...