Transformada discreta de Fourier

 Nota: Não confundir com Transformada de Fourier de tempo discreto.

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 complexa da frequência. O intervalo no qual é amostrada é o recíproco da duração da sequência de entrada.^[1] Uma DFT inversa (IDFT) é uma série de Fourier que usa as amostras da DTFT como coeficientes de onda senoidal complexa nas frequências da DTFT correspondentes. Ela possui os mesmos valores amostrais que a sequência de entrada original. Portanto, diz-se que a DFT é 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 é um ciclo de uma função periódica, a DFT fornece todos os valores diferentes de zero de um ciclo da DTFT.

A DFT é utilizada na análise de Fourier de muitas aplicações práticas.^[2] No processamento digital de sinais, a função é qualquer grandeza 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 (frequentemente definido por uma função de janela^[3]). No processamento de imagens, as amostras podem ser os valores de pixels ao longo de uma linha ou coluna de uma imagem raster. A DFT também é utilizada 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 mesmo por hardware dedicados. Essas implementações geralmente empregam algoritmos eficientes de transformada rápida de Fourier (FFT);^[4] tanto que os termos "FFT" e "DFT" são frequentemente usados ​​indistintamente. Antes de seu uso atual, o acrônimo "FFT" também pode ter sido usado para o termo ambíguo "transformada finita de Fourier".

Definição

Denotamos, em geral, a transformada discreta de Fourier (DFT) por ${\displaystyle {\mathcal {F}}}$.

A DFT transforma uma sequência de N números complexos ${\displaystyle \{x_{k}\}}$ em outra sequência de números complexos, ${\displaystyle \{{\hat {x}}_{k}\}}$. Defina os vetores ${\displaystyle u^{(k)}\in \mathbb {C} ^{n}}$ como:$${\displaystyle u^{(k)}={\begin{bmatrix}1\\e^{i2\pi {\frac {k}{n}}}\\e^{i2\pi {\frac {2k}{n}}}\\\vdots \\e^{i2\pi {\frac {(n-1)k}{n}}}\end{bmatrix}},~~~~0\leq k<n.}$$

O conjunto ${\displaystyle \{u^{(k)}\}_{k=0}^{n-1}}$ forma uma base ortogonal para ${\displaystyle \mathbb {C} ^{n}}$, isto é:$${\displaystyle \left\langle u^{(k)},u^{(j)}\right\rangle ={\begin{cases}n,&{\text{se }}k=j\\0,&{\text{se }}k\neq j\end{cases}}}$$

Assim, qualquer vetor ${\displaystyle x\in \mathbb {C} ^{n}}$ pode ser escrito como uma combinação linear dos vetores ${\displaystyle u^{(k)}}$:$${\displaystyle x={\frac {1}{n}}\sum _{k=0}^{n-1}{\hat {x}}_{k}u^{(k)}\;{\text{(Eq. 1)}}}$$Onde ${\displaystyle {\hat {x}}_{k}}$ são os coeficientes dados por:^[1]$${\displaystyle {\hat {x}}_{k}=\left\langle x,u^{(k)}\right\rangle =\sum _{j=0}^{n-1}x_{j}e^{-i2\pi {\frac {jk}{n}}}\;{\text{(Eq. 2)}}}$$Essa mudança de base é chamada de Transformada Discreta de Fourier e a matriz que a representa é dada por:$${\displaystyle {\begin{bmatrix}{\hat {x}}_{0}\\{\hat {x}}_{1}\\{\hat {x}}_{2}\\\vdots \\{\hat {x}}_{n-1}\end{bmatrix}}=\underbrace {\begin{bmatrix}1&1&1&\cdots &1\\1&e^{-i2\pi {\frac {1}{n}}}&e^{-i2\pi {\frac {2}{n}}}&\cdots &e^{-i2\pi {\frac {(n-1)}{n}}}\\1&e^{-i2\pi {\frac {2}{n}}}&e^{-i2\pi {\frac {4}{n}}}&\cdots &e^{-i2\pi {\frac {2(n-1)}{n}}}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&e^{-i2\pi {\frac {(n-1)}{n}}}&e^{-i2\pi {\frac {2(n-1)}{n}}}&\cdots &e^{-i2\pi {\frac {(n-1)^{2}}{n}}}\end{bmatrix}} _{F}{\begin{bmatrix}x_{0}\\x_{1}\\x_{2}\\\vdots \\x_{n-1}\end{bmatrix}}}$$Observe que ${\displaystyle \{x_{k}\}}$ são os coeficientes na base canônica e ${\displaystyle \{{\hat {x}}_{k}\}}$ são os coeficientes na nova base.

Uma consequência da ortogonalidade é que ${\displaystyle FF^{*}=nI_{d}}$, isto é:$${\displaystyle F^{-1}={\frac {1}{n}}F^{*}}$$Assim, a DFT é uma transformação linear invertível e sua inversa ${\displaystyle F^{-1}{\hat {x}}}$ é chamada de Transformada Discreta Inversa de Fourier (IDFT).

Exemplo

A matriz de Fourier ${\displaystyle F_{N}}$ no caso em que ${\displaystyle N=8}$, tem a raiz da unidade ${\displaystyle \omega =e^{-i{\frac {2\pi }{8}}}=e^{-i{\frac {\pi }{4}}}}$, podendo ser escrita em termos das potências de ${\displaystyle \omega }$.^[5]$${\displaystyle F_{8}={\begin{bmatrix}\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}&\omega ^{0}\\\omega ^{0}&\omega ^{1}&\omega ^{2}&\omega ^{3}&\omega ^{4}&\omega ^{5}&\omega ^{6}&\omega ^{7}\\\omega ^{0}&\omega ^{2}&\omega ^{4}&\omega ^{6}&\omega ^{8}&\omega ^{10}&\omega ^{12}&\omega ^{14}\\\omega ^{0}&\omega ^{3}&\omega ^{6}&\omega ^{9}&\omega ^{12}&\omega ^{15}&\omega ^{18}&\omega ^{21}\\\omega ^{0}&\omega ^{4}&\omega ^{8}&\omega ^{12}&\omega ^{16}&\omega ^{20}&\omega ^{24}&\omega ^{28}\\\omega ^{0}&\omega ^{5}&\omega ^{10}&\omega ^{15}&\omega ^{20}&\omega ^{25}&\omega ^{30}&\omega ^{35}\\\omega ^{0}&\omega ^{6}&\omega ^{12}&\omega ^{18}&\omega ^{24}&\omega ^{30}&\omega ^{36}&\omega ^{42}\\\omega ^{0}&\omega ^{7}&\omega ^{14}&\omega ^{21}&\omega ^{28}&\omega ^{35}&\omega ^{42}&\omega ^{49}\end{bmatrix}}}$$

Aproveitando a periodicidade ${\displaystyle \omega ^{k}=\omega ^{k{\pmod {8}}}}$, a matriz pode ser simplificada. Substituindo os valores numéricos, onde ${\displaystyle \omega ^{0}=1}$ ${\displaystyle \omega ^{1}={\frac {1-i}{\sqrt {2}}}}$, ${\displaystyle \omega ^{2}=-i}$, etc., obtemos a matriz explícita:

$${\displaystyle F_{8}={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&{\frac {1-i}{\sqrt {2}}}&-i&{\frac {-1-i}{\sqrt {2}}}&-1&{\frac {-1+i}{\sqrt {2}}}&i&{\frac {1+i}{\sqrt {2}}}\\1&-i&-1&i&1&-i&-1&i\\1&{\frac {-1-i}{\sqrt {2}}}&i&{\frac {1-i}{\sqrt {2}}}&-1&{\frac {1+i}{\sqrt {2}}}&-i&{\frac {-1+i}{\sqrt {2}}}\\1&-1&1&-1&1&-1&1&-1\\1&{\frac {-1+i}{\sqrt {2}}}&-i&{\frac {1+i}{\sqrt {2}}}&-1&{\frac {1-i}{\sqrt {2}}}&i&{\frac {-1-i}{\sqrt {2}}}\\1&i&-1&-i&1&i&-1&-i\\1&{\frac {1+i}{\sqrt {2}}}&i&{\frac {-1+i}{\sqrt {2}}}&-1&{\frac {-1-i}{\sqrt {2}}}&-i&{\frac {1-j}{\sqrt {2}}}\end{bmatrix}}}$$

Por inspeção, podemos ver que essa matriz é simétrica, que é uma das propriedades que vale para essa transformada.

Aliasing na Transformada Discreta de Fourier

Em processamento de sinais, o fenômeno conhecido como aliasing ocorre quando diferentes componentes espectrais se sobrepõem na Transformada Discreta de Fourier (DFT), causando distorção no espectro obtido.^[6]

Considere uma função real periódica ${\displaystyle f(t)}$ de período 1, expressa pela série de Fourier:

${\displaystyle f(t)=\sum _{\ell =-\infty }^{\infty }c_{\ell }e^{i2\pi \ell t}}$

Sejam as amostras definidas pelo vetor ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$:

${\displaystyle \mathbf {x} ={\begin{bmatrix}f(0)\\f\left({\frac {1}{n}}\right)\\f\left({\frac {2}{n}}\right)\\\vdots \\f\left({\frac {n-1}{n}}\right)\end{bmatrix}}}$

Note que ${\displaystyle f(0)=f(1)}$, de modo que a amostra em ${\displaystyle t=1}$ é redundante.

A transformada discreta de Fourier da função base ${\displaystyle e^{i2\pi \ell t}}$ satisfaz:

${\displaystyle {\hat {x}}^{k}={\begin{cases}n,&k\equiv \ell {\pmod {n}}\\0,&{\text{c.c.}}\end{cases}}}$

Portanto, a componente ${\displaystyle k}$-ésima da DFT do vetor ${\displaystyle \mathbf {x} }$ pode ser escrita como:

${\displaystyle {\hat {x}}^{k}=n\sum _{j=-\infty }^{\infty }c_{k+nj}=n\left[c_{k}+\sum _{j=1}^{\infty }\left(c_{k+nj}+c_{k-nj}\right)\right]}$

Como ${\displaystyle f(t)}$ é real, os coeficientes satisfazem a relação de conjugação complexa:

${\displaystyle c_{k-nj}={\overline {c_{-k+nj}}}}$

Assim, as componentes de frequência ${\displaystyle c_{\ell }}$ cujos índices diferem em múltiplos de ${\displaystyle n}$ se somam na TDF, fenômeno conhecido como aliasing ou superposição espectral.^[7]

Condição para ausência de aliasing

Para evitar o aliasing, é necessário que os coeficientes ${\displaystyle c_{\ell }}$ sejam nulos para todos os índices fora do intervalo fundamental ${\displaystyle [-n/2,n/2]}$, isto é:

${\displaystyle c_{k+nj}=0\quad {\text{para todo }}j\neq 0,\quad k=0,1,\ldots ,n-1}$

Essa condição significa que a função ${\displaystyle f(t)}$ é limitada em banda, com frequências menores que a frequência de Nyquist ${\displaystyle n/2}$. Sob essa hipótese, a DFT captura corretamente o espectro sem sobreposição.^[8]

Transformada inversa da Transformada Discreta de Fourier

A transformada inversa da Transformada Discreta de Fourier (TDF) é uma operação matemática fundamental no domínio do processamento digital de sinais, cuja finalidade é reconstruir uma sequência temporal finita a partir de sua representação no domínio da frequência. Essa operação é particularmente importante em sistemas de comunicação, análise espectral, compressão de dados e síntese de sinais.

Seja ${\displaystyle \{X_{k}\}}$ uma sequência complexa de comprimento ${\displaystyle N}$, correspondente à TDF de uma sequência temporal discreta ${\displaystyle \{x_{n}\}}$. A transformada inversa da DFT é definida formalmente por:

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

Essa equação constitui a transformada inversa no contexto da DFT, sendo o operador que desfaz a transformação direta, cujo formato é dado por:

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\cdot e^{-2\pi i\cdot {\frac {kn}{N}}},\quad k=0,1,\dots ,N-1.}$

As transformadas direta e inversa são simétricas, exceto pela inversão do sinal no expoente e pela presença do fator de normalização ${\displaystyle {\frac {1}{N}}}$ na fórmula da inversa. Tal fator garante que a operação de reconstrução mantenha a energia da sequência original e assegura a unicidade da inversa, desde que a TDF tenha sido aplicada sob a mesma convenção de normalização.

A transformada inversa pode ser interpretada como uma decomposição da série de Fourier discreta no tempo, reconstituindo cada valor de ${\displaystyle x_{n}}$ como uma combinação linear ponderada de senos e cossenos complexos. Na prática computacional, a transformada inversa da TDF é frequentemente implementada utilizando algoritmos eficientes, como a Transformada Rápida de Fourier Inversa (IFFT), que reduz significativamente o custo computacional da operação.^[9][10]

A correta aplicação da transformada inversa é essencial para garantir a fidelidade na reconstrução de sinais digitais após processos de filtragem, modulação, ou transformação espectral.

Propriedades[6]

Linearidade

Sejam ${\displaystyle {\hat {x}}_{k}}$ e ${\displaystyle {\hat {y}}_{k}}$ as transformadas de Fourier discretas de ${\displaystyle x_{k}}$ e ${\displaystyle y_{k}}$, respectivamente. Para quaisquer números complexos ${\displaystyle a,b}$, defina ${\displaystyle z_{k}}$ como:$${\displaystyle z_{k}:=ax_{k}+by_{k}}$$

A DFT de ${\displaystyle z_{k}}$ é obtida como:$${\displaystyle {\begin{aligned}{\hat {z}}_{k}&=\sum _{j=0}^{n-1}z_{j}e^{-i2\pi {\frac {kj}{n}}}\\&=\sum _{j=0}^{n-1}(ax_{j}+by_{j})e^{-i2\pi {\frac {kj}{n}}}\\&=\sum _{j=0}^{n-1}ax_{j}e^{-i2\pi {\frac {kj}{n}}}+\sum _{j=0}^{n-1}by_{j}e^{-i2\pi {\frac {kj}{n}}}\\&=a\left(\sum _{j=0}^{n-1}x_{j}e^{-i2\pi {\frac {kj}{n}}}\right)+b\left(\sum _{j=0}^{n-1}y_{j}e^{-i2\pi {\frac {kj}{n}}}\right)\\&=a{\hat {x}}_{k}+b{\hat {y}}_{k}\end{aligned}}}$$

Translação

Seja ${\displaystyle {\hat {x}}_{k}}$ a transformada de Fourier discreta de ${\displaystyle x_{k}}$. Defina um sinal deslocado ${\displaystyle y_{k}}$ como:$${\displaystyle y_{k}:=x_{k-k_{0}}}$$Em que ${\displaystyle k_{0}}$ é um inteiro que representa o deslocamento.

A DFT de ${\displaystyle y_{k}}$ é derivada fazendo a substituição de variável ${\displaystyle m=j-k_{0}}$:$${\displaystyle {\begin{aligned}{\hat {y}}_{k}&=\sum _{j=0}^{n-1}y_{j}e^{-i2\pi {\frac {kj}{n}}}\\&=\sum _{j=0}^{n-1}x_{j-k_{0}}e^{-i2\pi {\frac {kj}{n}}}\\&=\sum _{m=-k_{0}}^{n-1-k_{0}}x_{m}e^{-i2\pi {\frac {k(m+k_{0})}{n}}}\\&=\sum _{m=0}^{n-1}x_{m}e^{-i2\pi {\frac {k(m+k_{0})}{n}}}\quad \\&=\sum _{m=0}^{n-1}x_{m}e^{-i2\pi {\frac {km}{n}}}e^{-i2\pi {\frac {kk_{0}}{n}}}\\&=e^{-i2\pi {\frac {kk_{0}}{n}}}\left(\sum _{m=0}^{n-1}x_{m}e^{-i2\pi {\frac {km}{n}}}\right)\\&=e^{-i2\pi {\frac {kk_{0}}{n}}}{\hat {x}}_{k}\end{aligned}}}$$

Modulação

Seja ${\displaystyle {\hat {x}}_{k}}$ a transformada de Fourier discreta de ${\displaystyle x_{k}}$, defina ${\displaystyle y_{k}}$ como:$${\displaystyle y_{k}:=x_{k}\cos(2\pi fk)}$$Em que ${\displaystyle f}$ é um número inteiro. Temos:$${\displaystyle {\begin{aligned}{\hat {y}}_{k}&=\sum _{j=0}^{n-1}y_{j}e^{-i2\pi {\frac {jk}{n}}}\\&=\sum _{j=0}^{n-1}x_{j}\cos(2\pi fj)e^{-i2\pi {\frac {jk}{n}}}\\&={\frac {1}{2}}\sum _{j=0}^{n-1}x_{j}\left(e^{i2\pi fj}+e^{-i2\pi fj}\right)e^{-i2\pi {\frac {jk}{n}}}\\&={\frac {1}{2}}\sum _{j=0}^{n-1}x_{j}\left(e^{i2\pi \left(f-{\frac {k}{n}}\right)j}+e^{-i2\pi \left(f+{\frac {k}{n}}\right)j}\right)\\&={\frac {1}{2}}\left({\hat {x}}_{k-nf}+{\hat {x}}_{k+nf}\right)\end{aligned}}}$$

Aqui os índices ${\displaystyle k-nf}$ e ${\displaystyle k+nf}$ devem ser interpretados como números inteiros módulo ${\displaystyle n}$.

Assim, a modulação de um sinal ${\displaystyle x_{k}}$ por ${\displaystyle \cos(2\pi fk)}$ desloca os coeficientes da DFT de ${\displaystyle x_{k}}$ para as posições ${\displaystyle k-nf}$ e ${\displaystyle k+nf}$.

Convolução

Sejam ${\displaystyle {\hat {x}}_{k}}$ e ${\displaystyle {\hat {y}}_{k}}$ as transformadas de Fourier discretas de ${\displaystyle x_{k}}$ e ${\displaystyle y_{k}}$. Defina a convolução circular ${\displaystyle z_{k}}$ como:$${\displaystyle z_{k}:=(x*y)_{k}=\sum _{m=0}^{n-1}x_{m}y_{k-m}}$$A DFT de ${\displaystyle z_{k}}$ é derivada como: $${\displaystyle {\begin{aligned}{\hat {z}}_{k}&=\sum _{j=0}^{n-1}\left(\sum _{m=0}^{n-1}x_{m}y_{j-m}\right)e^{-i2\pi {\frac {kj}{n}}}\\&=\sum _{m=0}^{n-1}x_{m}\left(\sum _{j=0}^{n-1}y_{j-m}e^{-i2\pi {\frac {kj}{n}}}\right)\\&=\sum _{m=0}^{n-1}x_{m}\left(e^{-i2\pi {\frac {km}{n}}}{\hat {y}}_{k}\right)\quad {\text{(usando a propriedade de deslocamento no tempo)}}\\&=\left(\sum _{m=0}^{n-1}x_{m}e^{-i2\pi {\frac {km}{n}}}\right){\hat {y}}_{k}\\&={\hat {x}}_{k}{\hat {y}}_{k}\end{aligned}}}$$

Multiplicação

Sejam ${\displaystyle {\hat {x}}_{k}}$ e ${\displaystyle {\hat {y}}_{k}}$ as transformadas de Fourier discretas de ${\displaystyle x_{k}}$ e ${\displaystyle y_{k}}$. Defina o sinal ${\displaystyle z_{k}}$ como o produto ponto a ponto de ${\displaystyle x_{k}}$ e ${\displaystyle y_{k}}$:$${\displaystyle z_{k}:=x_{k}y_{k}}$$A DFT de ${\displaystyle z_{k}}$ é derivada substituindo as fórmulas da Transformada de Fourier Inversa (IDFT) para ${\displaystyle x_{j}}$ e ${\displaystyle y_{j}}$:$${\displaystyle {\begin{aligned}{\hat {z}}_{k}&=\sum _{j=0}^{n-1}z_{j}e^{-i2\pi {\frac {kj}{n}}}\\&=\sum _{j=0}^{n-1}(x_{j}y_{j})e^{-i2\pi {\frac {kj}{n}}}\\&=\sum _{j=0}^{n-1}\left({\frac {1}{n}}\sum _{m=0}^{n-1}{\hat {x}}_{m}e^{i2\pi {\frac {mj}{n}}}\right)\left({\frac {1}{n}}\sum _{p=0}^{n-1}{\hat {y}}_{p}e^{i2\pi {\frac {pj}{n}}}\right)e^{-i2\pi {\frac {kj}{n}}}\\&={\frac {1}{n^{2}}}\sum _{m=0}^{n-1}{\hat {x}}_{m}\sum _{p=0}^{n-1}{\hat {y}}_{p}\left(\sum _{j=0}^{n-1}e^{i2\pi {\frac {(m+p-k)j}{n}}}\right)\end{aligned}}}$$A soma interna sobre ${\displaystyle j}$ é igual a ${\displaystyle n}$ se ${\displaystyle m+p-k}$ for um múltiplo de ${\displaystyle n}$, e 0 caso contrário. Isso nos permite simplificar a expressão:$${\displaystyle {\begin{aligned}{\hat {z}}_{k}&={\frac {1}{n^{2}}}\sum _{m=0}^{n-1}{\hat {x}}_{m}\sum _{p=0}^{n-1}{\hat {y}}_{p}(n\cdot \delta ((m+p-k){\pmod {n}}))\\&={\frac {1}{n}}\sum _{m=0}^{n-1}{\hat {x}}_{m}\left(\sum _{p=0}^{n-1}{\hat {y}}_{p}\delta (p-(k-m))\right)\\&={\frac {1}{n}}\sum _{m=0}^{n-1}{\hat {x}}_{m}{\hat {y}}_{k-m}\\&={\frac {1}{n}}({\hat {x}}*{\hat {y}})_{k}\end{aligned}}}$$Assim, a multiplicação ponto a ponto no domínio do tempo corresponde à convolução circular (escalada por ${\displaystyle 1/n}$) no domínio da frequência.

Correlação

Sejam ${\displaystyle {\hat {x}}_{k}}$ e ${\displaystyle {\hat {y}}_{k}}$ as transformadas de Fourier discretas de ${\displaystyle x_{k}}$ e ${\displaystyle y_{k}}$. Defina a correlação cruzada circular ${\displaystyle z_{k}}$ como:$${\displaystyle z_{k}:=(x\diamond y)_{k}=\sum _{j=0}^{n-1}x_{j+k}y_{j}^{*}}$$Onde ${\displaystyle y_{j}^{*}}$ é o conjugado complexo de ${\displaystyle y_{j}}$.

A DFT de ${\displaystyle z_{k}}$ é derivada como:$${\displaystyle {\begin{aligned}{\hat {z}}_{p}&=\sum _{k=0}^{n-1}z_{k}e^{-i2\pi {\frac {pk}{n}}}\\&=\sum _{k=0}^{n-1}\left(\sum _{j=0}^{n-1}x_{j+k}y_{j}^{*}\right)e^{-i2\pi {\frac {pk}{n}}}\\&=\sum _{j=0}^{n-1}y_{j}^{*}\left(\sum _{k=0}^{n-1}x_{j+k}e^{-i2\pi {\frac {pk}{n}}}\right)\end{aligned}}}$$Fazendo a substituição de variável ${\displaystyle m=j+k}$ na soma interna:$${\displaystyle {\begin{aligned}\sum _{k=0}^{n-1}x_{j+k}e^{-i2\pi {\frac {pk}{n}}}&=\sum _{m=j}^{n-1+j}x_{m}e^{-i2\pi {\frac {p(m-j)}{n}}}\\&=\sum _{m=0}^{n-1}x_{m}e^{-i2\pi {\frac {p(m-j)}{n}}}\quad \\&=e^{i2\pi {\frac {pj}{n}}}\left(\sum _{m=0}^{n-1}x_{m}e^{-i2\pi {\frac {pm}{n}}}\right)\\&=e^{i2\pi {\frac {pj}{n}}}{\hat {x}}_{p}\end{aligned}}}$$Substituindo este resultado de volta:$${\displaystyle {\begin{aligned}{\hat {z}}_{p}&=\sum _{j=0}^{n-1}y_{j}^{*}\left(e^{i2\pi {\frac {pj}{n}}}{\hat {x}}_{p}\right)\\&={\hat {x}}_{p}\left(\sum _{j=0}^{n-1}y_{j}^{*}e^{i2\pi {\frac {pj}{n}}}\right)\\&={\hat {x}}_{p}\left(\sum _{j=0}^{n-1}y_{j}e^{-i2\pi {\frac {pj}{n}}}\right)^{*}\\&={\hat {x}}_{p}{\hat {y}}_{p}^{*}\end{aligned}}}$$Assim, a correlação cruzada no domínio do tempo corresponde à multiplicação ponto a ponto do espectro de um sinal pelo conjugado complexo do espectro do outro.

Simetria Conjugada

Se ${\displaystyle x_{k}\in \mathbb {C} ^{n}}$ é um vetor de números reais, então:^[7]$${\displaystyle {\hat {x}}_{n-k}={\overline {{\hat {x}}_{k}}}}$$Ou seja, o coeficiente da DFT de ${\displaystyle x}$ na posição ${\displaystyle n-k}$ é o conjugado do coeficiente na posição ${\displaystyle k}$.

Demonstração

$${\displaystyle {\begin{aligned}{\hat {x}}_{n-k}&=\sum _{j=0}^{n-1}x_{j}e^{-i2\pi {\frac {j(n-k)}{n}}}\\&=\sum _{j=0}^{n-1}x_{j}e^{-i2\pi {\frac {jn}{n}}}e^{i2\pi {\frac {jk}{n}}}\\&=\sum _{j=0}^{n-1}x_{j}e^{i2\pi {\frac {jk}{n}}}\\&={\overline {\hat {x}}}\end{aligned}}}$$

Observação

Um sinal real pode ser reconstruído a partir de ${\displaystyle \left\lceil {\frac {n}{2}}\right\rceil }$ coeficientes da DFT.

Tipos da transformada discreta de Fourier

Sinal sinusoidal

Caso 1

Seja ${\displaystyle f(t)=e^{i2\pi ft}}$ com ${\displaystyle f\in \mathbb {R} }$ e defina o vetor ${\displaystyle x\in \mathbb {C} ^{n}}$ como: $${\displaystyle x={\begin{bmatrix}f(0)\\[5pt]f\left({\frac {1}{n}}\right)\\[5pt]f\left({\frac {2}{n}}\right)\\[5pt]\vdots \\[5pt]f\left({\frac {n-1}{n}}\right)\end{bmatrix}}={\begin{bmatrix}1\\[5pt]e^{i{\frac {2\pi f}{n}}}\\[5pt]e^{i{\frac {4\pi f}{n}}}\\[5pt]\vdots \\[5pt]e^{i{\frac {2(n-1)\pi f}{n}}}\end{bmatrix}}}$$

A transformada de Fourier discreta deste vetor é dada por: $${\displaystyle {\begin{aligned}{\hat {x}}_{k}&=\sum _{j=0}^{n-1}x_{j}e^{-i2\pi {\frac {jk}{n}}}\\&=\sum _{j=0}^{n-1}e^{i2\pi {\frac {jf}{n}}}e^{-i2\pi {\frac {jk}{n}}}\\&=\sum _{j=0}^{n-1}e^{i2\pi {\frac {j(f-k)}{n}}}\\&=\sum _{j=0}^{n-1}z^{j},~~z:=e^{i2\pi {\frac {(f-k)}{n}}}\\\end{aligned}}}$$

Assim, temos que: $${\displaystyle {\begin{aligned}{\hat {x}}_{k}&={\begin{cases}n,&{\frac {f-k}{n}}\in \mathbb {Z} ,~~{\text{isto é}}~~k\equiv f\mod n,\\{\frac {z^{n}-1}{z-1}},&c.c.\end{cases}}\end{aligned}}}$$

Observação

se ${\displaystyle f=mn+{\hat {f}}}$ com ${\displaystyle m}$ inteiro, então a DFT não depende de m.

Caso particular: frequência inteira

Se ${\displaystyle f}$ é um número inteiro, então: $${\displaystyle {\begin{aligned}{\hat {x}}_{k}&={\begin{cases}n,&k\equiv f\mod n\\0,&c.c.\end{cases}}\end{aligned}}}$$

Observação

Seja ${\displaystyle {\hat {x}}_{k}(f)}$ a transformada de Fourier discreta do vetor ${\displaystyle x}$ definido acima, então, como $${\displaystyle \sum _{j=0}^{n-1}e^{i2\pi {\frac {j(f-k)}{n}}}}$$ $${\displaystyle \lim _{f\to m}{\hat {x}}_{k}(f)={\begin{cases}n,&k\equiv m\mod n\\0,&c.c.\end{cases}}}$$

Caso 2

No caso ${\displaystyle f(t)=\cos(2\pi ft-\varphi )}$ com ${\displaystyle f\in \mathbb {R} }$, temos: $${\displaystyle {\begin{aligned}f(t)&={\frac {e^{i(2\pi ft-\varphi )}+e^{-i(2\pi ft-\varphi )}}{2}}\\&={\frac {e^{-i\varphi }}{2}}e^{i2\pi ft}+{\frac {e^{i\varphi }}{2}}e^{-i2\pi ft}\end{aligned}}}$$

Se, como no exemplo anterior, ${\displaystyle x_{k}}$ é definido como: ${\displaystyle x_{k}:=f\left({\frac {k}{n}}\right)}$ Temos: $${\displaystyle {\begin{aligned}{\hat {x}}_{k}&=\sum _{j=0}^{n-1}x_{j}e^{-i2\pi {\frac {jk}{n}}}\\&={\frac {e^{-i\varphi }}{2}}\sum _{j=0}^{n-1}e^{i2j\pi {\frac {(f-k)}{n}}}+{\frac {e^{i\varphi }}{2}}\sum _{j=0}^{n-1}e^{i2j\pi {\frac {(-f-k)}{n}}}.\end{aligned}}}$$

Caso particular: frequência inteira

Se ${\displaystyle f}$ é um número inteiro, então: $${\displaystyle {\begin{aligned}{\hat {x}}_{k}&={\begin{cases}{\frac {n}{2}}e^{-i\varphi },&k\equiv f\mod n\\{\frac {n}{2}}e^{i\varphi },&k\equiv -f\mod n\\0,&c.c.\end{cases}}\end{aligned}}}$$

Real

Definição

Trabalharemos com ${\displaystyle x}$ real e n ímpar. Seja ${\displaystyle n=2d+1}$ e os vetores ${\displaystyle u^{(k)}\in \mathbb {C} ^{n}}$ dados por: $${\displaystyle u^{(k)}={\begin{bmatrix}1\\e^{i2\pi {\frac {k}{n}}}\\e^{i2\pi {\frac {2k}{n}}}\\\vdots \\e^{i2\pi {\frac {(n-1)k}{n}}}\end{bmatrix}},~~~~0\leq k<n.}$$

Defina a nova base dada por: $${\displaystyle {\begin{aligned}c^{(0)}&=u^{(0)}={\begin{bmatrix}1\\1\\1\\\vdots \\1\end{bmatrix}},\\c^{(k)}&={\frac {1}{2}}\left(u^{(k)}+u^{(n-k)}\right)=\Re (u^{k}),~~~1\leq k\leq d,\\s^{(k)}&={\frac {1}{2i}}\left(u^{(k)}-u^{(n-k)}\right)=\Im (u^{k}),~~~1\leq k\leq d.\end{aligned}}}$$

Agora temos: $${\displaystyle {\begin{aligned}x={\frac {1}{n}}\sum _{k=0}^{n-1}{\hat {x}}_{k}u^{(k)}={\frac {1}{n}}\left[{\hat {x}}_{0}c^{(0)}+\sum _{k=1}^{d}{\hat {x}}_{k}\left(c^{(k)}+is^{(k)}\right)+\sum _{k=1}^{d}{\hat {x}}_{n-k}\left(c^{(k)}-is^{(k)}\right)\right]\end{aligned}}}$$

Do lema, temos que ${\displaystyle {\hat {x}}_{n-k}={\overline {{\hat {x}}_{k}}}}$, logo: $${\displaystyle {\begin{aligned}x&={\frac {1}{n}}\sum _{k=0}^{n-1}{\hat {x}}_{k}u^{(k)}={\frac {1}{n}}\left[{\hat {x}}_{0}c^{(0)}+\sum _{k=1}^{d}{\hat {x}}_{k}\left(c^{(k)}+is^{(k)}\right)+\sum _{k=1}^{d}{\overline {{\hat {x}}_{k}}}\left(c^{(k)}-is^{(k)}\right)\right]\\&={\frac {1}{n}}\sum _{k=0}^{n-1}{\hat {x}}_{k}u^{(k)}={\frac {1}{n}}\left[a_{0}c^{(0)}+\sum _{k=1}^{d}({\hat {x}}^{(k)}+{\overline {{\hat {x}}^{(k)}}})c^{(k)}+i\sum _{k=1}^{d}({\hat {x}}^{(k)}-{\overline {{\hat {x}}^{(k)}}})s^{(k)}\right]\end{aligned}}}$$ onde, $${\displaystyle {\begin{aligned}a_{0}&={\frac {2}{n}}{\hat {x}}_{0},\\a_{k}&={\frac {1}{n}}\left({\hat {x}}_{k}+{\overline {{\hat {x}}_{k}}}\right)=2\Re ({\hat {x}}_{k}),\\b_{k}&={\frac {i}{n}}\left({\hat {x}}_{k}-{\overline {{\hat {x}}_{k}}}\right)=-2\Im ({\hat {x}}_{k}).\end{aligned}}}$$ assim, $${\displaystyle {\begin{aligned}x&={\frac {a_{0}}{2}}+\sum _{k=1}^{d}a_{k}c^{(k)}+\sum _{k=1}^{d}b_{k}s^{(k)}\end{aligned}}}$$ onde, $${\displaystyle {\begin{aligned}a_{0}&={\frac {2}{n}}\sum _{j=0}^{n-1}x_{j},\\a_{k}&={\frac {2}{n}}\sum _{j=0}^{n-1}x_{j}\cos \left(2\pi {\frac {jk}{n}}\right),\\b_{k}&={\frac {2}{n}}\sum _{j=0}^{n-1}x_{j}\sin \left(2\pi {\frac {jk}{n}}\right).\end{aligned}}}$$

Aplicações

A DFT tem sido amplamente utilizada em inúmeros campos; apresentamos apenas alguns exemplos abaixo. 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.

Exemplo de algoritmo para a FFT

Este código apresenta uma implementação da Transformada Rápida de Fourier (FFT) utilizando o método recursivo de Cooley-Tukey. A FFT é, essencialmente, um algoritmo de 'dividir para conquistar' que otimiza o cálculo da Transformada de Fourier Discreta (DFT), tornando sua execução em computadores muito mais rápida e viabilizando seu uso em uma vasta gama de aplicações.^[11]

# Bibliotecas essenciais para a execução do programa
import cmath
import math
import numpy as np

# Função FFT recursiva (transformada rápida de fourier)
# 'a' -> array de entrada | 'invert' -> 1 para FFT, -1 para IFFT
def fft(a, invert):
    n = len(a)

    # Caso base da recursão: um único elemento
    if n == 1:
        return

    # Divisão
    # Separa o array em elementos de índice par (a_0) e ímpar (a_1)
    n_2 = n // 2
    a_0 = np.array([a[2 * i] for i in range(n_2)], dtype=np.complex128)
    a_1 = np.array([a[2 * i + 1] for i in range(n_2)], dtype=np.complex128)

    # Conquista
    # Chama a função recursivamente para as duas metades
    fft(a_0, invert)
    fft(a_1, invert)

    # Combinação
    # Combina os resultados das metades para obter a transformada completa
    omega_n = cmath.exp(2 * math.pi * 1j / n * invert) # Raiz da unidade
    omega = 1.0 + 0.0j                                # Fator de torção w^k

    for i in range(n_2):
        # Operação "Borboleta": calcula os termos da DFT
        t = omega * a_1[i]
        a[i] = a_0[i] + t
        a[i + n_2] = a_0[i] - t

        # Normalização necessária apenas para a transformada inversa
        if invert == -1:
            a[i] /= 2
            a[i + n_2] /= 2

        # Atualiza o fator de torção para a próxima iteração
        omega *= omega_n

Análise espectral

Quando a DFT é usada para análise espectral de sinais, a sequência ${\displaystyle \{x_{n}\}}$ geralmente representa um conjunto finito de amostras temporais uniformemente espaçadas de algum sinal ${\displaystyle x(t)}$, onde ${\displaystyle t}$ representa o tempo. A conversão de tempo contínuo para amostras (tempo discreto) transforma a transformada de Fourier subjacente de ${\displaystyle x(t)}$ em uma transformada de Fourier em tempo discreto (DTFT), que geralmente envolve um tipo de distorção chamada aliasing. A escolha de uma taxa de amostragem apropriada (veja Taxa de Nyquist) é a chave para minimizar essa distorção. Em geral também é necessário o uso de filtros passa baixo na aquisição da amostra. Da mesma forma, a conversão de uma sequência muito longa (ou infinita) para um tamanho gerenciável acarreta um tipo de distorção chamada vazamento, que se manifesta como perda de detalhes (também conhecida como resolução) na DTFT. A escolha de um comprimento de subsequência apropriado é a chave primária para minimizar esse efeito. Quando os dados disponíveis (e o tempo para processá-los) são maiores do que a quantidade necessária para atingir a resolução de frequência desejada, uma técnica padrão é dividir a amostra e realizar múltiplas DFTs, por exemplo, para criar um espectrograma. Se o resultado desejado for um espectro de potência e os dados apresentarem ruído e aleatoriedade, calcular a média das magnitudes das múltiplas DFTs é 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 de Welch e o método de Bartlett; o assunto geral da estimativa do espectro de potência de um sinal ruidoso é chamado de estimativa espectral.

Uma fonte final de distorção (ou talvez ilusão) é a própria DFT, pois ela é apenas uma amostragem finita 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 § Relação com a amostragem.

• O procedimento é às vezes chamado de preenchimento com zeros, que é uma implementação específica usada em conjunto com o algoritmo transformada 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 da FFT.
• Como já mencionado, o vazamento impõe um limite à resolução inerente da DTFT, portanto, há um limite prático para o benefício que pode ser obtido com uma DFT de granulação fina.

Óptica, difração e tomografia

A transformada discreta de Fourier é amplamente utilizada 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 a partir de objetos em duas e três dimensões. O espaço vetorial dual (direto/recíproco) de objetos tridimensionais também disponibiliza uma rede recíproca tridimensional, cuja construção a partir de sombras translúcidas de objetos (por meio 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 filtros FFT e § Relação com a amostragem.

Compressão de dados

O campo do processamento digital de sinais depende fortemente de operações no domínio da frequência (ou seja, da 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 se supõe serem imperceptíveis, são descartados. O descompressor calcula a transformada inversa com base nesse número reduzido de coeficientes de Fourier. (Aplicações de compressão frequentemente usam uma forma especializada da DFT, a transformada discreta do cosseno ou, às vezes, a transformada discreta modificada do cosseno.) 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 pela divisão dos dados em segmentos e pela transformação de 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

Transformadas discretas de Fourier são frequentemente usadas para resolver equações diferenciais parciais, onde, novamente, a DFT é usada como uma aproximação para a série de Fourier (que é recuperada no limite de N infinito). A vantagem dessa abordagem é que ela expande o sinal em exponenciais complexas ${\displaystyle e^{inx}}$, que são autofunções de diferenciação: ${\displaystyle {{\text{d}}{\big (}e^{inx}{\big )}}/{\text{d}}x=ine^{inx}}$. Assim, na representação de Fourier, a diferenciação é simples — basta multiplicar por ${\displaystyle in}$. (No entanto, a escolha de ${\displaystyle n}$ não é única devido ao aliasing; para que o método seja convergente, uma escolha semelhante à da seção interpolação trigonométrica acima deve ser usada.) Uma equação diferencial linear com coeficientes constantes é transformada em uma equação algébrica facilmente solucionável. Usa-se então a DFT inversa para transformar o resultado de volta na representação espacial ordinária. Tal abordagem é chamada de método espectral.

Multiplicação polinomial

Suponha que desejamos calcular o produto polinomial ${\displaystyle c(x)=a(x)\cdot b(x)}$. A expressão do produto comum para os coeficientes de ${\displaystyle c(x)}$ envolve uma convolução linear (acíclica), onde os índices não se "envolvem". Isso pode ser reescrito como uma convolução cíclica, tomando os vetores de coeficientes para ${\displaystyle a(x)}$ e ${\displaystyle b(x)}$ primeiro com termo constante, e depois acrescentando zeros de forma que os vetores de coeficientes resultantes ${\displaystyle \mathbf {b} }$ e ${\displaystyle \mathbf {c} }$ tenham dimensão ${\displaystyle {\mathit {d}}>\mathrm {deg} (a(x))+\mathrm {deg} (b(x))}$. Então,

${\displaystyle \mathbf {c} =\mathbf {a} *\mathbf {b} }$

Onde c é o vetor de coeficientes para c(x), e o operador de convolução ${\displaystyle *\,}$ é definido como

${\displaystyle c_{n}=\sum _{m=0}^{d-1}a_{m}b_{n-m\ \mathrm {mod} \ d}\qquad \qquad \qquad n=0,1\dots ,d-1}$

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

${\displaystyle {\mathcal {F}}(\mathbf {c} )={\mathcal {F}}(\mathbf {a} ){\mathcal {F}}(\mathbf {b} )}$

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

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

Com uma transformada 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. Neste caso, d deve ser escolhido como o menor inteiro maior que a soma dos graus do polinômio de entrada que pode ser fatorado em pequenos fatores primos (por exemplo, 2, 3 e 5, dependendo da implementação da FFT).

Multiplicação de números inteiros grandes

Os algoritmos de multiplicação mais rápidos conhecidos para a multiplicação de números inteiros muito grandes utilizam 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 numérica, com os coeficientes do polinômio correspondendo aos dígitos dessa base (ex.: 123 = 1 ≤ 10^2 + 2 ≤ 10^1 + 3 ≤ 10^0). Após a multiplicação polinomial, uma etapa de propagação de transporte de complexidade relativamente baixa 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 razão de amostragem, devido ao Teorema da Convolução e ao algoritmo FFT, pode ser mais rápido transformá-los, multiplicá-los pontualmente pela transformada do filtro e, em seguida, realizar a transformação reversa. Alternativamente, um bom filtro é obtido simplesmente truncando os dados transformados e retransformando o conjunto de dados reduzido.

Exemplo

Este código implementa um método altamente eficiente para multiplicar dois polinômios usando a FFT. A ideia central baseia-se no Teorema da Convolução, que afirma que a convolução de duas sequências é equivalente à multiplicação elemento a elemento de suas transformadas de Fourier. Multiplicar polinômios é uma forma de convolução. Esta abordagem baseada em FFT é muito mais rápida (${\displaystyle O(n\log n)}$) para polinômios grandes do que o método padrão de "multiplicação longa" (${\displaystyle O(n^{2})}$).^[11]

# Função para multiplicar dois polinômios (representados como listas/arrays 'a' e 'b')
# usando o algoritmo de FFT.
def multiply(a, b):
    # 1. PREPARAÇÃO E PADDING
    n = 1
    n_a = len(a)
    n_b = len(b)

    # O polinômio resultante terá grau (n_a-1) + (n_b-1).
    # Precisamos de um array de tamanho n_a + n_b para guardar o resultado.
    # O loop encontra a menor potência de 2 (n) que é maior que n_a + n_b.
    # Usar uma potência de 2 é ideal para a eficiência do algoritmo FFT.
    while n < n_a + n_b:
        n *= 2;

    # Cria arrays de números complexos com o tamanho 'n', preenchidos com zeros.
    fa = np.zeros(n, dtype=np.complex128)
    fb = np.zeros(n, dtype=np.complex128)

    # Copia os coeficientes dos polinômios 'a' e 'b' para os novos arrays.
    # O espaço restante (padding) continua como zero.
    for i in range(0, n):
        if i < n_a:
            fa[i] = a[i]

        if i < n_b:
            fb[i] = b[i]

    # 2. TRANSFORMAÇÃO PARA O DOMÍNIO DA FREQUÊNCIA
    # Aplica a FFT em ambos os polinômios.
    # Isso converte a representação de coeficientes para uma de pontos/valores.
    fft(fa, 1)  # O '1' indica a transformada direta.
    fft(fb, 1)

    # 3. MULTIPLICAÇÃO NO DOMÍNIO DA FREQUÊNCIA
    # No domínio da frequência, a convolução (multiplicação de polinômios)
    # se torna uma simples multiplicação elemento por elemento.
    for i in range(0, n):
        fa[i] *= fb[i]

    # 4. TRANSFORMAÇÃO DE VOLTA PARA O DOMÍNIO DO TEMPO
    # Aplica a FFT Inversa para converter o resultado de volta para
    # a representação de coeficientes do polinômio.
    fft(fa, -1) # O '-1' indica a transformada inversa.

    # 5. EXTRAÇÃO DO RESULTADO
    # O resultado agora está em 'fa' como os coeficientes do polinômio produto.
    result = np.zeros(n, dtype=np.complex128)
    for i in range(0, n):
        result[i] = fa[i]

    # 6. DEVOLVE O RESULTADO
    # Retorna o polinômio
    return result

# Exemplo de chamada da função (p_a e p_b precisariam ser definidos)
p_a = [1, 5, 2]          # 1 +  5*x +  2*x^2
p_b = [6, 1, 4, 3]       # 6 +  1*x +  4*x^2 + 3*x^3
p_c = multiply(p_a, p_b) # 6 + 31*x + 21*x^2 + 25*x^3 + 23*x^4 + 6*x^5

# Imprime os coeficientes do polinômio resultante.
# A parte real é extraída, pois pequenos erros numéricos podem criar partes imaginárias insignificantes.
# O loop vai até len(p_a) + len(p_b) - 1, que é o número de coeficientes do resultado.
for i in range(0, len(p_a) + len(p_b) - 1):
    x = p_c[i].real
    print(f"{round(x)} ", end="") # Arredonda para um resultado mais limpo

Alternativas

Há várias alternativas à DFT, para várias aplicações, salientando-se entre elas as wavelets. O análogo da DFT é a DWT, ou transformada discreta de wavelet. Uma limitação da DFT é que ela não informa a "posição" ou o instante dos eventos em frequência e, portanto, não é muito útil para analisar transientes. Como as wavelets tem definição em tempo e frequência, a DWT é melhor para representar a posição, a despeito de ter menor resolução em frequência.^[6]