Diskrétní Fourierova transformace - Discrete Fourier transform

Vztah mezi (kontinuální) Fourierova transformace a diskrétní Fourierova transformace. Levý sloupec: Spojitá funkce (nahoře) a její Fourierova transformace (dole). Sloupec vlevo nahoře: Periodické shrnutí původní funkce (nahoře). Fourierova transformace (dole) je nulová, s výjimkou diskrétních bodů. Inverzní transformace je součet nazývaných sinusoidů Fourierova řada. Sloupec vpravo nahoře: Původní funkce je diskretizována (vynásobena a Dirac hřeben ) (horní). Jeho Fourierova transformace (dole) je periodický součet (DTFT ) původní transformace. Pravý sloupec: DFT (dole) počítá diskrétní vzorky kontinuálního DTFT. Inverzní DFT (nahoře) je periodický součet původních vzorků. The FFT Algoritmus počítá jeden cyklus DFT a jeho inverze je jeden cyklus inverze DFT.

Zobrazení Fourierovy transformace (vlevo nahoře) a jejího periodického součtu (DTFT) v levém dolním rohu. Spektrální sekvence v (a) vpravo nahoře a (b) vpravo dole jsou počítány z (a) jednoho cyklu periodického součtu s (t) a (b) jednoho cyklu periodického součtu sekvence s (nT) . Příslušné vzorce jsou (a) Fourierova řada integrální a (b) DFT součet. Jeho podobnosti s původní transformací, S (f), a jeho relativní výpočetní jednoduchost jsou často motivací pro výpočet sekvence DFT.

v matematika, diskrétní Fourierova transformace (DFT) převede konečnou posloupnost rovnoměrně rozmístěných Vzorky a funkce do stejné délky sekvence stejně rozložených vzorků diskrétní Fourierova transformace (DTFT), což je a komplexní funkce frekvence. Interval, ve kterém je DTFT vzorkován, je převrácená hodnota doby trvání vstupní sekvence. Inverzní DFT je a Fourierova řada, pomocí vzorků DTFT jako koeficientů komplex sinusoidy na odpovídajících frekvencích DTFT. Má stejné vzorové hodnoty jako původní vstupní sekvence. DFT se proto říká, že je frekvenční doména reprezentace původní vstupní sekvence. Pokud původní sekvence zahrnuje všechny nenulové hodnoty funkce, její DTFT je spojitý (a periodický) a DFT poskytuje diskrétní vzorky jednoho cyklu. Pokud je původní sekvence jedním cyklem periodické funkce, poskytuje DFT všechny nenulové hodnoty jednoho cyklu DTFT.

DFT je nejdůležitější diskrétní transformace, zvyklý hrát Fourierova analýza v mnoha praktických aplikacích.^[1] v zpracování digitálních signálů, funkce je libovolná veličina nebo signál která se časem mění, například tlak a zvuková vlna, a rádio signál, nebo denně teplota odečty vzorkované v konečném časovém intervalu (často definované a funkce okna^[2]). v zpracování obrazu, vzorky mohou být hodnoty pixelů podél řádku nebo sloupce a rastrový obrázek. DFT se také používá k efektivnímu řešení parciální diferenciální rovnice, a provádět další operace, jako je závity nebo násobení velkých celých čísel.

Protože se zabývá konečným množstvím dat, lze jej implementovat v počítače podle numerické algoritmy nebo dokonce oddaný Hardware. Tyto implementace obvykle využívají efektivně rychlá Fourierova transformace (FFT) algoritmy;^[3] natolik, že výrazy „FFT“ a „DFT“ jsou často používány zaměnitelně. Před jeho současným použitím je „FFT“ inicialismus může být také použit pro dvojznačný výraz "konečná Fourierova transformace ".

Definice

The diskrétní Fourierova transformace transformuje a sekvence z N komplexní čísla ${displaystyle left {mathbf {x_ {n}} ight}: = x_ {0}, x_ {1}, ldots, x_ {N-1}}$ do jiné posloupnosti komplexních čísel, ${displaystyle left {mathbf {X_ {k}} ight}: = X_ {0}, X_ {1}, ldots, X_ {N-1},}$ který je definován

kde poslední výraz vyplývá z prvního pomocí Eulerův vzorec.

Transformace je někdy označena symbolem ${displaystyle {mathcal {F}}}$, jako v ${displaystyle mathbf {X} = {mathcal {F}} vlevo {mathbf {x} ight}}$ nebo ${displaystyle {mathcal {F}} vlevo (mathbf {x} ight)}$ nebo ${displaystyle {mathcal {F}} mathbf {x}}$.^[A]

Motivace

Rovnice 1 lze vyhodnotit i mimo doménu ${displaystyle kin [0, N-1]}$a tato rozšířená sekvence je ${displaystyle N}$-periodicky. V souladu s tím další sekvence ${displaystyle N}$ indexy se někdy používají, jako např ${extstyle left [- {frac {N} {2}}, {frac {N} {2}} - 1ight]}$ (li ${displaystyle N}$ je sudý) a ${extstyle left [- {frac {N-1} {2}}, {frac {N-1} {2}} ight]}$ (li ${displaystyle N}$ je lichý), což znamená výměnu levé a pravé poloviny výsledku transformace.^[4]

Rovnice 1 lze interpretovat nebo odvodit různými způsoby, například:

Normalizační faktor násobící DFT a IDFT (zde 1 a ${extstyle {frac {1} {N}}}$) a znaky exponentů jsou pouze konvence a liší se v některých způsobech léčby. Jedinými požadavky těchto konvencí jsou, že DFT a IDFT mají exponenty opačného znaménka a že produkt jejich normalizačních faktorů je ${extstyle {frac {1} {N}}}$. Normalizace ${extstyle {sqrt {frac {1} {N}}}}$ například pro DFT i IDFT činí transformace jednotnými. Diskrétní impuls, ${displaystyle x_ {n} = 1}$ na n = 0 a 0 jinak; se může transformovat na ${displaystyle X_ {k} = 1}$ pro všechny k (použijte normalizační faktory 1 pro DFT a ${extstyle {frac {1} {N}}}$ pro IDFT). DC signál, ${displaystyle X_ {k} = 1}$ na k = 0 a 0 jinak; se může nepřímo transformovat na ${displaystyle x_ {n} = 1}$ pro všechny ${displaystyle n}$ (použití ${extstyle {frac {1} {N}}}$ pro DFT a 1 pro IDFT), což odpovídá zobrazení DC jako průměrný průměr signálu.

Příklad

Nechat ${displaystyle N = 4}$ a

${displaystyle mathbf {x} = {egin {pmatrix} x_ {0} x_ {1} x_ {2} x_ {3} konec {pmatrix}} = {egin {pmatrix} 1 2-i -i -1 + 2iend {pmatrix}}}$

Zde ukážeme, jak vypočítat DFT z ${displaystyle mathbf {x}}$ použitím Rovnice 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}$

${displaystyle mathbf {X} = {egin {pmatrix} X_ {0} X_ {1} X_ {2} X_ {3} konec {pmatrix}} = {egin {pmatrix} 2 -2-2i - 2i 4 + 4iend {pmatrix}}}$

Inverzní transformace

Diskrétní Fourierova transformace je invertibilní, lineární transformace

${displaystyle {mathcal {F}} dvojtečka mathbb {C} ^ {N} o mathbb {C} ^ {N}}$

s ${displaystyle mathbb {C}}$ označující množinu komplexní čísla. Jeho inverze je známá jako inverzní diskrétní Fourierova transformace (IDFT). Jinými slovy, pro všechny ${displaystyle N> 0}$, an N-dimenzionální komplexní vektor má zase DFT a IDFT ${displaystyle N}$-dimenzionální komplexní vektory.

Inverzní transformace je dána vztahem:

Vlastnosti

Linearita

DFT je lineární transformace, tj. Pokud ${displaystyle {mathcal {F}} ({x_ {n}}) _ {k} = X_ {k}}$ a ${displaystyle {mathcal {F}} ({y_ {n}}) _ {k} = Y_ {k}}$, pak pro všechna komplexní čísla ${displaystyle a, b}$:

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

Obrácení času a frekvence

Obrácení času (tj. Výměna ${displaystyle n}$ podle ${displaystyle N-n}$)^[B] v ${displaystyle x_ {n}}$ odpovídá obrácení frekvence (tj. ${displaystyle k}$ podle ${displaystyle N-k}$).^{[5]:str. 421} Matematicky, pokud ${displaystyle {x_ {n}}}$ představuje vektor X pak

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

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

Konjugace v čase

Li ${displaystyle {mathcal {F}} ({x_ {n}}) _ {k} = X_ {k}}$ pak ${displaystyle {mathcal {F}} ({x_ {n} ^ {*}}) _ {k} = X_ {N-k} ^ {*}}$.^{[5]:str. 423}

Skutečná a imaginární část

Tato tabulka ukazuje některé matematické operace na ${displaystyle x_ {n}}$ v časové doméně a odpovídající účinky na její DFT ${displaystyle X_ {k}}$ ve frekvenční doméně.

Vlastnictví	Časová doména ${displaystyle x_ {n}}$	Frekvenční doména ${displaystyle X_ {k}}$
Skutečná část času	${displaystyle Re {left (x_ {n} ight)}}$	${displaystyle {frac {1} {2}} vlevo (X_ {k} + X_ {N-k-1} ^ {*} ight)}$
Imaginární část v čase	${displaystyle Im {left (x_ {n} ight)}}$	${displaystyle {frac {1} {2i}} vlevo (X_ {k} -X_ {N-k-1} ^ {*} vpravo)}$
Skutečná část frekvence	${displaystyle {frac {1} {2}} vlevo (x_ {n} + x_ {N-n-1} ^ {*} vpravo)}$	${displaystyle Re {left (X_ {k} ight)}}$
Fiktivní část ve frekvenci	${displaystyle {frac {1} {2i}} vlevo (x_ {n} -x_ {N-n-1} ^ {*} vpravo)}$	${displaystyle Im {left (X_ {k} ight)}}$

Ortogonalita

Vektory ${displaystyle u_ {k} = left [left.e ^ {{frac {i2pi} {N}} kn}; ight |; n = 0,1, ldots, N-1ight] ^ {mathsf {T}}}$ pro muže ortogonální základ přes sadu N-dimenzionální komplexní vektory:

${displaystyle u_ {k} ^ {mathsf {T}} u_ {k '} ^ {*} = součet _ {n = 0} ^ {N-1} vlevo (e ^ {{frac {i2pi} {N}} kn} ight) left (e ^ {{frac {i2pi} {N}} (- k ') n} ight) = součet _ {n = 0} ^ {N-1} e ^ {{frac {i2pi} { N}} (k-k ') n} = N ~ delta _ {kk'}}$

kde ${displaystyle ~ delta _ {kk '}}$ je Kroneckerova delta. (V posledním kroku je součet triviální, pokud ${displaystyle k = k '}$, kde je to 1 + 1 + ⋅⋅⋅ =N, a jinak je a geometrické řady které lze explicitně sečíst pro získání nuly.) Tuto podmínku ortogonality lze použít k odvození vzorce pro IDFT z definice DFT a je ekvivalentní vlastnosti unitarity níže.

Plancherelova věta a Parsevalova věta

Li ${displaystyle X_ {k}}$ a ${displaystyle Y_ {k}}$ jsou DFT z ${displaystyle x_ {n}}$ a ${displaystyle y_ {n}}$ respektive pak Parsevalova věta uvádí:

${displaystyle sum _ {n = 0} ^ {N-1} x_ {n} y_ {n} ^ {*} = {frac {1} {N}} součet _ {k = 0} ^ {N-1} X_ {k} Y_ {k} ^ {*}}$

kde hvězda označuje komplexní konjugace. Plancherelův teorém je speciální případ Parsevalovy věty a uvádí:

${displaystyle sum _ {n = 0} ^ {N-1} | x_ {n} | ^ {2} = {frac {1} {N}} součet _ {k = 0} ^ {N-1} | X_ {k} | ^ {2}.}$

Tyto věty jsou také ekvivalentní jednotkové podmínce níže.

Periodicita

Periodicitu lze zobrazit přímo z definice:

${displaystyle X_ {k + N} riangleq součet _ {n = 0} ^ {N-1} x_ {n} e ^ {- {frac {i2pi} {N}} (k + N) n} = součet _ { n = 0} ^ {N-1} x_ {n} e ^ {- {frac {i2pi} {N}} kn} spodní výztuha {e ^ {- i2pi n}} _ {1} = součet _ {n = 0 } ^ {N-1} x_ {n} e ^ {- {frac {i2pi} {N}} kn} = X_ {k}.}$

Podobně lze ukázat, že vzorec IDFT vede k periodickému rozšíření.

Věta o posunu

Násobení ${displaystyle x_ {n}}$ podle a lineární fáze ${displaystyle e ^ {{frac {i2pi (n-1)} {N}} m}}$ pro celé číslo m odpovídá a kruhový posun výstupu ${displaystyle X_ {k}}$: ${displaystyle X_ {k}}$ je nahrazen ${displaystyle X_ {k-m}}$, kde je dolní index interpretován modulo N (tj. pravidelně). Podobně kruhový posun vstupu ${displaystyle x_ {n}}$ odpovídá vynásobení výstupu ${displaystyle X_ {k}}$ lineární fází. Matematicky, pokud ${displaystyle {x_ {n}}}$ představuje vektor X pak

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

pak ${displaystyle {mathcal {F}} vlevo (vlevo {x_ {n} cdot e ^ {{frac {i2pi} {N}} nm} ight} ight) _ {k} = X_ {k-m}}$

a ${displaystyle {mathcal {F}} vlevo (vlevo {x_ {n-m} ight} ight) _ {k} = X_ {k} cdot e ^ {- {frac {i2pi} {N}} km}}$

Věta o kruhové konvoluci a věta o vzájemné korelaci

The konvoluční věta pro diskrétní Fourierova transformace (DTFT) naznačuje, že lze získat konvoluci dvou sekvencí jako inverzní transformaci produktu jednotlivých transformací. Důležité zjednodušení nastane, když je jedna ze sekvencí N-periodická, zde označená ${displaystyle y _ {_ {N}},}$ protože ${displaystyle scriptstyle {ext {DTFT}} displaystyle {y _ {_ {N}}}}$ je nenulová pouze při diskrétních frekvencích (viz DTFT § Periodická data ), a tedy i jeho produkt s nepřetržitou funkcí ${displaystyle scriptstyle {ext {DTFT}} displaystyle {x}.}$ To vede ke značnému zjednodušení inverzní transformace.

${displaystyle x * y _ {_ {N}} = scriptstyle {m {DTFT}} ^ {- 1} displaystyle left [scriptstyle {m {DTFT}} displaystyle {x} cdot scriptstyle {m {DTFT}} displaystyle {y_ { _ {N}}} ight] = scriptstyle {m {DFT}} ^ {- 1} displaystyle left [scriptstyle {m {DFT}} displaystyle {x _ {_ {N}}} cdot scriptstyle {m {DFT}} displaystyle {y _ {_ {N}}} hned],}$

kde ${displaystyle x _ {_ {N}}}$ je periodický součet z ${displaystyle x}$ sekvence:  ${displaystyle (x _ {_ {N}}) _ {n} riangleq suma _ {m = -infty} ^ {infty} x _ {(n-mN)}.}$

Obvykle jsou doménou převzaty součty DFT a inverzní DFT ${displaystyle [0, N-1].}$ Definování těchto DFT jako ${displaystyle X}$ a ${displaystyle Y,}$ výsledek je:

${displaystyle (x * y _ {_ {N}}) _ {n} riangleq suma _ {ell = -infty} ^ {infty} x_ {ell} cdot (y _ {_ {N}}) _ {n-ell} = underbrace {{mathcal {F}} ^ {- 1}} _ {m {DFT ^ {- 1}}} vlevo {Xcdot Yight} _ {n}.}$

V praxi se ${displaystyle x}$ sekvence je obvykle délka N nebo menší a ${displaystyle y _ {_ {N}}}$ je periodické prodloužení délky N. ${displaystyle y}$-sekvence, kterou lze také vyjádřit jako a kruhová funkce:

${displaystyle (y _ {_ {N}}) _ {n} = součet _ {p = -infty} ^ {infty} y _ {(n-pN)} = y _ {(noperatorname {mod} N)}, quin nin mathbb {Z}.}$

Pak lze konvoluci napsat jako:

což vede k výkladu jako a oběžník konvoluce ${displaystyle x}$ a ${displaystyle y.}$^[6][7] Často se používá k efektivnímu výpočtu jejich lineární konvoluce. (vidět Kruhová konvoluce, Algoritmy rychlé konvoluce, a Uložení překrytí )

Podobně vzájemná korelace z${displaystyle x}$ a${displaystyle y _ {_ {N}}}$ darováno:

${displaystyle (xstar y _ {_ {N}}) _ {n} riangleq sum _ {ell = -infty} ^ {infty} x_ {ell} ^ {*} cdot (y _ {_ {N}}) _ {n + ell} = {mathcal {F}} ^ {- 1} vlevo {X ^ {*} cdot Yight} _ {n}.}$

Dualita věty o konvoluci

To lze také ukázat:

${displaystyle {mathcal {F}} vlevo {mathbf {xcdot y} ight} _ {k} riangleq součet _ {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} ,,}$ což je kruhová konvoluce ${displaystyle mathbf {X}}$ a ${displaystyle mathbf {Y}}$.

Trigonometrický interpolační polynom

The trigonometrický interpolační polynom

${displaystyle p (t) = {egin {cases} {frac {1} {N}} left [X_ {0} + X_ {1} e ^ {i2pi t} + cdots + X_ {N / 2-1} e ^ {i (N / 2-1) 2pi t} + X_ {N / 2} cos (Npi t) + X_ {N / 2 + 1} e ^ {i (-N / 2 + 1) 2pi t} + cdots + X_ {N-1} e ^ {- i2pi t} ight] & N {ext {even}} {frac {1} {N}} vlevo [X_ {0} + X_ {1} e ^ {i2pi t } + cdots + X_ {lfloor N / 2floor} e ^ {ilfloor N / 2floor 2pi t} + X_ {lfloor N / 2floor +1} e ^ {- ilfloor N / 2floor 2pi t} + cdots + X_ {N-1 } e ^ {- i2pi t} ight] & N {ext {odd}} end {cases}}}$

kde koeficienty X_k jsou dány DFT z X_n výše, splňuje interpolační vlastnost ${displaystyle p (n / N) = x_ {n}}$ pro ${displaystyle n = 0, ldots, N-1}$.

Dokonce i Nsi všimněte, že Nyquistova složka ${displaystyle {frac {X_ {N / 2}} {N}} cos (Npi t)}$ je zacházeno speciálně.

Tato interpolace je není jedinečný: aliasing znamená, že by se dalo přidat N na kteroukoli z komplexně sinusových frekvencí (např. měnící se ${displaystyle e ^ {- it}}$ na ${displaystyle e ^ {i (N-1) t}}$ ) beze změny vlastnosti interpolace, ale s uvedením odlišný hodnoty mezi ${displaystyle x_ {n}}$ bodů. Výše uvedená volba je však typická, protože má dvě užitečné vlastnosti. Nejprve se skládá ze sinusoidů, jejichž frekvence mají nejmenší možné velikosti: interpolace je pásmo omezeno. Zadruhé, pokud ${displaystyle x_ {n}}$ jsou tedy skutečná čísla ${displaystyle p (t)}$ je také reálné.

Naproti tomu nejzřejmější trigonometrický interpolační polynom je ten, ve kterém se frekvence pohybují od 0 do ${displaystyle N-1}$ (místo zhruba ${displaystyle -N / 2}$ na ${displaystyle + N / 2}$ jak je uvedeno výše), podobně jako inverzní vzorec DFT. Tato interpolace ano ne minimalizovat sklon a je ne obecně reálné za skutečné ${displaystyle x_ {n}}$; jeho použití je častou chybou.

Unitární DFT

Jiným způsobem pohledu na DFT je poznamenat, že ve výše uvedené diskusi lze DFT vyjádřit jako DFT matice, a Vandermondeova matice, představil Sylvester v roce 1867,

${displaystyle mathbf {F} = {egin {bmatrix} omega _ {N} ^ {0cdot 0} & omega _ {N} ^ {0cdot 1} & ldots & omega _ {N} ^ {0cdot (N-1)} omega _ {N} ^ {1cdot 0} & omega _ {N} ^ {1cdot 1} & ldots & omega _ {N} ^ {1cdot (N-1)} vdots & vdots & ddots & vdots omega _ {N} ^ {(N-1 ) cdot 0} & omega _ {N} ^ {(N-1) cdot 1} & ldots & omega _ {N} ^ {(N-1) cdot (N-1)} end {bmatrix}}}$

kde ${displaystyle omega _ {N} = e ^ {- i2pi / N}}$ je primitivní Nth kořen jednoty.

Inverzní transformace je pak dána inverzí výše uvedené matice,

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

S unitární normalizační konstanty ${displaystyle 1 / {sqrt {N}}}$, DFT se stává a unitární transformace, definované jednotkovou maticí:

${displaystyle {egin {aligned} mathbf {U} & = {frac {1} {sqrt {N}}} mathbf {F} mathbf {U} ^ {- 1} & = mathbf {U} ^ {*} | det (mathbf {U}) | & = 1end {zarovnáno}}}$

kde ${displaystyle det ()}$ je určující funkce. Determinant je produktem vlastních čísel, která jsou vždy ${displaystyle pm 1}$ nebo ${displaystyle pm i}$ jak je popsáno níže. V reálném vektorovém prostoru lze jednotnou transformaci považovat za jednoduše tuhou rotaci souřadnicového systému a všechny vlastnosti tuhé rotace lze najít v jednotné DFT.

Ortogonalita DFT je nyní vyjádřena jako ortonormalita podmínka (která vzniká v mnoha oblastech matematiky, jak je popsáno v kořen jednoty ):

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

Li X je definován jako jednotný DFT vektoru X, pak

${displaystyle X_ {k} = součet _ {n = 0} ^ {N-1} U_ {kn} x_ {n}}$

a Parsevalova věta je vyjádřena jako

${displaystyle sum _ {n = 0} ^ {N-1} x_ {n} y_ {n} ^ {*} = součet _ {k = 0} ^ {N-1} X_ {k} Y_ {k} ^ {*}}$

Podíváme-li se na DFT jako na souřadnicovou transformaci, která jednoduše specifikuje komponenty vektoru v novém souřadnicovém systému, pak výše uvedené je pouze tvrzení, že bodový produkt dvou vektorů je zachován pod jednotnou DFT transformací. Pro zvláštní případ ${displaystyle mathbf {x} = mathbf {y}}$, to znamená, že je zachována také délka vektoru - to je spravedlivé Plancherelův teorém,

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

Důsledek věta o kruhové konvoluci je to DFT matice F diagonalizuje všechny cirkulační matice.

Vyjádření inverzní DFT ve smyslu DFT

Užitečnou vlastností DFT je, že inverzní DFT lze snadno vyjádřit pomocí (dopředného) DFT pomocí několika známých „triků“. (Například ve výpočtech je často vhodné implementovat pouze rychlou Fourierovu transformaci odpovídající jednomu směru transformace a poté získat druhý směr transformace z prvního.)

Nejprve můžeme vypočítat inverzní DFT obrácením všech vstupů kromě jednoho (Duhamel et al., 1988):

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

(Jako obvykle jsou dolní indexy interpretovány modulo N; tedy pro ${displaystyle n = 0}$, my máme ${displaystyle x_ {N-0} = x_ {0}}$.)

Zadruhé lze také konjugovat vstupy a výstupy:

${displaystyle {mathcal {F}} ^ {- 1} (mathbf {x}) = {frac {1} {N}} {mathcal {F}} vlevo (mathbf {x} ^ {*} ight) ^ {* }}$

Za třetí, varianta tohoto konjugačního triku, která je někdy výhodnější, protože nevyžaduje žádnou úpravu datových hodnot, zahrnuje výměnu skutečných a imaginárních částí (což lze provést na počítači jednoduše úpravou ukazatele ). Definovat ${extstyle operatorname {swap} (x_ {n})}$ tak jako ${displaystyle x_ {n}}$ s jeho skutečnými a imaginárními částmi vyměněnými - tedy pokud ${displaystyle x_ {n} = a + bi}$ pak ${extstyle operatorname {swap} (x_ {n})}$ je ${displaystyle b + ai}$. Ekvivalentně $operatorname {swap} (x_ {n})$ rovná se ${displaystyle ix_ {n} ^ {*}}$. Pak

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

To znamená, že inverzní transformace je stejná jako dopředná transformace s reálnou a imaginární částí zaměněnou za vstup i výstup až po normalizaci (Duhamel et al., 1988).

Konjugační trik lze také použít k definování nové transformace, která úzce souvisí s DFT nedobrovolný —To je, což je jeho vlastní inverzní. Zejména, ${displaystyle T (mathbf {x}) = {mathcal {F}} vlevo (mathbf {x} ^ {*} ight) / {sqrt {N}}}$ je jasně jeho vlastní inverzní: ${displaystyle T (T (mathbf {x})) = mathbf {x}}$. Úzce související involutory transformace (faktorem (1 + i)/√2) je ${displaystyle H (mathbf {x}) = {mathcal {F}} vlevo ((1 + i) mathbf {x} ^ {*} ight) / {sqrt {2N}}}$, protože ${displaystyle (1 + i)}$ faktory v ${displaystyle H (H (mathbf {x}))}$ zrušte 2. Pro skutečné vstupy ${displaystyle mathbf {x}}$, skutečná část ${displaystyle H (mathbf {x})}$ není nikdo jiný než diskrétní Hartleyova transformace, což je také involutory.

Vlastní čísla a vlastní vektory

The vlastní čísla matice DFT jsou jednoduché a dobře známé, zatímco vlastní vektory jsou komplikované, nejsou ojedinělé a jsou předmětem probíhajícího výzkumu.

Zvažte jednotnou formu ${displaystyle mathbf {U}}$ definované výše pro DFT délky N, kde

${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)}.}$

Tato matice splňuje maticový polynom rovnice:

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

To lze vidět z inverzních vlastností výše: provozní ${displaystyle mathbf {U}}$ dvakrát dává původní data v opačném pořadí, takže fungující ${displaystyle mathbf {U}}$ čtyřikrát vrátí původní data a je tedy matice identity. To znamená, že vlastní čísla ${displaystyle lambda}$ uspokojit rovnici:

${displaystyle lambda ^ {4} = 1.}$

Proto vlastní čísla ${displaystyle mathbf {U}}$ jsou čtvrtí kořeny jednoty: ${displaystyle lambda}$ je +1, -1, +ineboi.

Protože pro to existují pouze čtyři odlišné vlastní hodnoty ${displaystyle N imes N}$ matice, nějaké mají multiplicita. Násobnost udává počet lineárně nezávislé vlastní vektory odpovídající každé vlastní hodnotě. (Existují N nezávislé vlastní vektory; unitární matice nikdy není vadný.)

Problém jejich multiplicity vyřešili McClellan a Parks (1972), i když se později ukázalo, že byl ekvivalentem problému vyřešeného Gauss (Dickinson a Steiglitz, 1982). Násobnost závisí na hodnotě N modulo 4 a je dán následující tabulkou:

Jinak uvedeno, charakteristický polynom z ${displaystyle mathbf {U}}$ je:

${displaystyle det (lambda I-mathbf {U}) = (lambda -1) ^ {leftlfloor {frac {N + 4} {4}} ightfloor} (lambda +1) ^ {leftlfloor {frac {N + 2} { 4}} ightfloor} (lambda + i) ^ {leftlfloor {frac {N + 1} {4}} ightfloor} (lambda -i) ^ {leftlfloor {frac {N-1} {4}} ightfloor}.}$

Žádný jednoduchý analytický vzorec pro obecné vlastní vektory není znám. Vlastní vektory navíc nejsou jedinečné, protože libovolná lineární kombinace vlastních vektorů pro stejnou vlastní hodnotu je také vlastním vektorem pro tuto vlastní hodnotu. Různí vědci navrhli různé možnosti vlastních vektorů, které byly vybrány tak, aby vyhovovaly užitečným vlastnostem ortogonalita a mít „jednoduché“ formy (např. McClellan a Parks, 1972; Dickinson a Steiglitz, 1982; Grünbaum, 1982; Atakishiyev a Wolf, 1997; Candan et al., 2000; Hanna et al.2004; Gurevich a Hadani, 2008).

Přímý přístup spočívá v diskriminaci vlastní funkce kontinua Fourierova transformace, z nichž nejznámější je Gaussova funkce.Od té doby periodický součet funkce znamená diskretizaci jeho kmitočtového spektra a diskretizace znamená periodické sčítání spektra, diskretizovaná a periodicky sčítaná Gaussova funkce poskytuje vlastní vektor diskrétní transformace:

• ${displaystyle F (m) = součet _ {kin mathbb {Z}} exp vlevo (- {frac {pi cdot (m + Ncdot k) ^ {2}} {N}} vpravo)}$.

Uzavřený formulářový výraz pro řadu lze vyjádřit pomocí Jacobi theta funkce tak jako

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

Dva další jednoduché uzavřené analytické vlastní vektory pro speciální období DFT N byly nalezeny (Kong, 2008):

Pro období DFT N = 2L + 1 = 4K. + 1, kde K. je celé číslo, následující je vlastní vektor DFT:

• ${displaystyle F (m) = prod _ {s = K + 1} ^ {L} vlevo [protože vlevo ({frac {2pi} {N}} může) -cos vlevo ({frac {2pi} {N}} zrak) ) ight]}$

Pro období DFT N = 2L = 4K., kde K. je celé číslo, následující je vlastní vektor DFT:

• ${displaystyle F (m) = hřích vlevo ({frac {2pi} {N}} může) prod _ {s = K + 1} ^ {L-1} vlevo [protože vlevo ({frac {2pi} {N}} může) -kos vlevo ({frac {2pi} {N}} zrak) přímo]}$

Volba vlastních vektorů DFT matice se v posledních letech stala důležitou pro definování diskrétního analogu frakční Fourierova transformace —DFT matici lze převést na zlomkové mocniny umocněním vlastních čísel (např. Rubio a Santhanam, 2005). Pro spojitá Fourierova transformace, přirozené ortogonální vlastní funkce jsou Hermitovské funkce Jako vlastní vektory DFT byly použity různé jejich diskrétní analogy, například Kravčukovy polynomy (Atakishiyev a Wolf, 1997). „Nejlepší“ volba vlastních vektorů k definování frakční diskrétní Fourierovy transformace však zůstává otevřenou otázkou.

Principy nejistoty

Princip pravděpodobnostní nejistoty

Pokud náhodná proměnná X_k je omezen

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

pak

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

lze považovat za diskrétní funkce pravděpodobnostní hmotnosti z n, s přidruženou funkcí pravděpodobnostní hmotnosti vytvořenou z transformované proměnné,

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

Pro případ spojitých funkcí ${displaystyle P (x)}$ a ${displaystyle Q (k)}$, Heisenbergův princip nejistoty tvrdí, že

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

kde ${displaystyle D_ {0} (X)}$ a ${displaystyle D_ {0} (x)}$ jsou odchylky ${displaystyle | X | ^ {2}}$ a ${displaystyle | x | ^ {2}}$ respektive s dosaženou rovností v případě vhodně normalizované Gaussovo rozdělení. I když lze odchylky analogicky definovat pro DFT, analogický princip nejistoty není užitečný, protože nejistota nebude invariantní posunem. Massar a Spindel přesto zavedli smysluplný princip nejistoty.^[8]

Nicméně, Hirschman entropická nejistota bude mít užitečný analog pro případ DFT.^[9] Princip Hirschmanovy nejistoty je vyjádřen pomocí Shannonova entropie dvou pravděpodobnostních funkcí.

V diskrétním případě jsou Shannonovy entropie definovány jako

${displaystyle H (X) = - součet _ {n = 0} ^ {N-1} P_ {n} ln P_ {n}}$

a

${displaystyle H (x) = - součet _ {m = 0} ^ {N-1} Q_ {m} ln Q_ {m} ~,}$

a entropická nejistota princip se stává^[9]

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

Rovnost je získána pro ${displaystyle P_ {n}}$ rovná se překladům a modulacím vhodně normalizovaných Kronecker hřeben období ${displaystyle A}$ kde ${displaystyle A}$ je jakýkoli přesný dělitel celého čísla ${displaystyle N}$. Funkce pravděpodobnostní hmotnosti ${displaystyle Q_ {m}}$ pak bude úměrná vhodně přeloženému Kronecker hřeben období ${displaystyle B = N / A}$.^[9]

Princip deterministické nejistoty

Existuje také známý princip deterministické nejistoty, který využívá řídkost signálu (nebo počet nenulových koeficientů).^[10] Nechat ${displaystyle | x | _ {0}}$ a ${displaystyle | X | _ {0}}$ být počet nenulových prvků časové a frekvenční sekvence ${displaystyle x_ {0}, x_ {1}, ldots, x_ {N-1}}$ a ${displaystyle X_ {0}, X_ {1}, ldots, X_ {N-1}}$, resp. Pak,

${displaystyle Nleq | x | _ {0} cdot | X | _ {0}.}$

Okamžitým důsledkem nerovnost aritmetických a geometrických prostředků, jeden také má ${displaystyle 2 {sqrt {N}} leq | x | _ {0} + | X | _ {0}}$. Ukázalo se, že oba principy nejistoty jsou přísné pro konkrétně zvolené sekvence „piketového plotu“ (diskrétní sledy impulsů) a že nacházejí praktické využití pro aplikace obnovy signálu.^[10]

DFT skutečných a čistě imaginárních signálů

• Li ${displaystyle x_ {0}, ldots, x_ {N-1}}$ jsou reálná čísla, jak jsou často v praktických aplikacích, pak DFT ${displaystyle X_ {0}, ldots, X_ {N-1}}$ je dokonce symetrické:

${displaystyle x_ {n} v mathbb {R} quad forall nin {0, ldots, N-1} implikuje X_ {k} = X _ {- kmod N} ^ {*} quad for all kin {0, ldots, N-1 }}$, kde ${displaystyle X ^ {*},}$ označuje komplexní konjugace.

Z toho vyplývá, že pro sudé ${displaystyle N}$ ${displaystyle X_ {0}}$ a ${displaystyle X_ {N / 2}}$ mají skutečnou hodnotu a zbytek DFT je zcela specifikován jen ${displaystyle N / 2-1}$ komplexní čísla.

• Li ${displaystyle x_ {0}, ldots, x_ {N-1}}$ jsou čistě imaginární čísla, pak DFT ${displaystyle X_ {0}, ldots, X_ {N-1}}$ je liché symetrické:

${displaystyle x_ {n} in imathbb {R} quad forall nin {0, ldots, N-1} implikuje X_ {k} = - X _ {- kmod N} ^ {*} quad for all kin {0, ldots, N- 1}}$, kde ${displaystyle X ^ {*},}$ označuje komplexní konjugace.

Zobecněný DFT (posunutá a nelineární fáze)

Je možné posunout vzorkování transformace v časové a / nebo frekvenční doméně o některé skutečné posuny A a b, resp. Toto je někdy známé jako zobecněný DFT (nebo GDFT), také nazývaný posunul DFT nebo offset DFT, a má analogické vlastnosti jako běžný DFT:

${displaystyle X_ {k} = součet _ {n = 0} ^ {N-1} x_ {n} e ^ {- {frac {i2pi} {N}} (k + b) (n + a)} quad quad k = 0, tečky, N-1.}$

Nejčastěji směny ${displaystyle 1/2}$ (polovina vzorku). Zatímco obyčejný DFT odpovídá periodickému signálu v časové i frekvenční doméně, ${displaystyle a = 1/2}$ produkuje signál, který je antiodiodický ve frekvenční doméně (${displaystyle X_ {k + N} = - X_ {k}}$) a naopak pro ${displaystyle b = 1/2}$Specifický případ tedy ${displaystyle a = b = 1/2}$ je známý jako lichý čas lichá frekvence diskrétní Fourierova transformace (nebo O.² Tyto posunuté transformace se nejčastěji používají pro symetrická data, k reprezentaci různých hraničních symetrií a pro reálná symetrická data odpovídají různým formám diskrétních kosinus a sinus transformuje.

Další zajímavá volba je ${displaystyle a = b = - (N-1) / 2}$, kterému se říká střed DFT (nebo CDFT). Vycentrovaný DFT má užitečnou vlastnost, když N je násobkem čtyř, všechny čtyři jeho vlastní hodnoty (viz výše) mají stejnou multiplicitu (Rubio a Santhanam, 2005)^[11]

Termín GDFT se také používá pro nelineární fázová rozšíření DFT. Metoda GDFT tedy poskytuje zobecnění pro ortogonální blokové transformace s konstantní amplitudou, včetně lineárních a nelineárních fázových typů. GDFT je rámec pro zlepšení vlastností časové a frekvenční domény tradičního DFT, např. automatické / vzájemné korelace přidáním správně navržené funkce tvarování fáze (obecně nelineární) k původním funkcím lineární fáze (Akansu a Agirman-Tosun, 2010).^[12]

Na diskrétní Fourierovu transformaci lze pohlížet jako na zvláštní případ z-transformace, vyhodnoceno na jednotkové kružnici v komplexní rovině; obecnější z-transformace odpovídají komplex směny A a b výše.

Vícerozměrný DFT

Obyčejný DFT transformuje jednorozměrnou sekvenci nebo pole ${displaystyle x_ {n}}$ to je funkce přesně jedné diskrétní proměnné n. Vícedimenzionální DFT vícerozměrného pole ${displaystyle x_ {n_ {1}, n_ {2}, tečky, n_ {d}}}$ to je funkce d diskrétní proměnné ${displaystyle n_ {ell} = 0,1, tečky, N_ {ell} -1}$ pro ${displaystyle ell}$ v ${displaystyle 1,2, tečky, d}$ je definováno:

${displaystyle X_ {k_ {1}, k_ {2}, tečky, k_ {d}} = součet _ {n_ {1} = 0} ^ {N_ {1} -1} vlevo (omega _ {N_ {1} } ^ {~ k_ {1} n_ {1}} součet _ {n_ {2} = 0} ^ {N_ {2} -1} vlevo (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}, tečky, n_ {d}} hned) hned) ,,}$

kde ${displaystyle omega _ {N_ {ell}} = exp (-i2pi / N_ {ell})}$ jak je uvedeno výše a d výstupní indexy běží od ${displaystyle k_ {ell} = 0,1, tečky, N_ {ell} -1}$. To je kompaktněji vyjádřeno v vektor notace, kde definujeme ${displaystyle mathbf {n} = (n_ {1}, n_ {2}, tečky, n_ {d})}$ a ${displaystyle mathbf {k} = (k_ {1}, k_ {2}, tečky, k_ {d})}$ tak jako d-dimenzionální vektory indexů od 0 do ${displaystyle mathbf {N} -1}$, které definujeme jako ${displaystyle mathbf {N} -1 = (N_ {1} -1, N_ {2} -1, tečky, N_ {d} -1)}$:

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

kde rozdělení ${displaystyle mathbf {n} / mathbf {N}}$ je definován jako ${displaystyle mathbf {n} / mathbf {N} = (n_ {1} / N_ {1}, dots, n_ {d} / N_ {d})}$ má být provedeno po prvcích a součet označuje sadu vnořených součtů výše.

Inverze vícerozměrného DFT je, analogicky k jednorozměrnému případu, dána vztahem:

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

Protože jednorozměrný DFT vyjadřuje vstup ${displaystyle x_ {n}}$ as a superposition of sinusoids, the multidimensional DFT expresses the input as a superposition of rovinné vlny, or multidimensional sinusoids. The direction of oscillation in space is ${displaystyle mathbf {k} /mathbf {N} }$. The amplitudes are ${displaystyle X_{mathbf {k} }}$. This decomposition is of great importance for everything from digitální zpracování obrazu (two-dimensional) to solving parciální diferenciální rovnice. The solution is broken up into plane waves.

The multidimensional DFT can be computed by the složení of a sequence of one-dimensional DFTs along each dimension. In the two-dimensional case ${displaystyle x_{n_{1},n_{2}}}$ the ${displaystyle N_{1}}$ independent DFTs of the rows (i.e., along ${displaystyle n_{2}}$) are computed first to form a new array ${displaystyle y_{n_{1},k_{2}}}$. Pak ${displaystyle N_{2}}$ independent DFTs of y along the columns (along ${displaystyle n_ {1}}$) are computed to form the final result ${displaystyle X_{k_{1},k_{2}}}$. Alternatively the columns can be computed first and then the rows. The order is immaterial because the nested summations above dojíždět.

An algorithm to compute a one-dimensional DFT is thus sufficient to efficiently compute a multidimensional DFT. This approach is known as the row-column algoritmus. There are also intrinsically multidimensional FFT algorithms.

The real-input multidimensional DFT

For input data ${displaystyle x_{n_{1},n_{2},dots ,n_{d}}}$ skládající se z reálná čísla, the DFT outputs have a conjugate symmetry similar to the one-dimensional case above:

${displaystyle X_{k_{1},k_{2},dots ,k_{d}}=X_{N_{1}-k_{1},N_{2}-k_{2},dots ,N_{d}-k_{d}}^{*},}$

where the star again denotes complex conjugation and the ${displaystyle ell}$-th subscript is again interpreted modulo ${displaystyle N_{ell }}$ (pro ${displaystyle ell =1,2,ldots ,d}$).

Aplikace

The DFT has seen wide usage across a large number of fields; we only sketch a few examples below (see also the references at the end). All applications of the DFT depend crucially on the availability of a fast algorithm to compute discrete Fourier transforms and their inverses, a rychlá Fourierova transformace.

Spectral analysis

When the DFT is used for signal spectral analysis, ${displaystyle {x_{n}},}$ sequence usually represents a finite set of uniformly spaced time-samples of some signal ${displaystyle x(t),}$, kde ${displaystyle t}$ představuje čas. The conversion from continuous time to samples (discrete-time) changes the underlying Fourierova transformace z ${displaystyle x (t)}$ do diskrétní Fourierova transformace (DTFT), which generally entails a type of distortion called aliasing. Choice of an appropriate sample-rate (see Nyquistova sazba ) is the key to minimizing that distortion. Similarly, the conversion from a very long (or infinite) sequence to a manageable size entails a type of distortion called leakage, which is manifested as a loss of detail (a.k.a. resolution) in the DTFT. Choice of an appropriate sub-sequence length is the primary key to minimizing that effect. When the available data (and time to process it) is more than the amount needed to attain the desired frequency resolution, a standard technique is to perform multiple DFTs, for example to create a spektrogram. If the desired result is a power spectrum and noise or randomness is present in the data, averaging the magnitude components of the multiple DFTs is a useful procedure to reduce the rozptyl of the spectrum (also called a periodogram in this context); two examples of such techniques are the Welch method a Bartlett method; the general subject of estimating the power spectrum of a noisy signal is called spectral estimation.

A final source of distortion (or perhaps iluze) is the DFT itself, because it is just a discrete sampling of the DTFT, which is a function of a continuous frequency domain. That can be mitigated by increasing the resolution of the DFT. That procedure is illustrated at § Sampling the DTFT.

• The procedure is sometimes referred to as zero-padding, which is a particular implementation used in conjunction with the rychlá Fourierova transformace (FFT) algoritmus. The inefficiency of performing multiplications and additions with zero-valued "samples" is more than offset by the inherent efficiency of the FFT.
• As already stated, leakage imposes a limit on the inherent resolution of the DTFT, so there is a practical limit to the benefit that can be obtained from a fine-grained DFT.

Banka filtru

Vidět § FFT filter banks a § Sampling the DTFT.

Komprese dat

The field of digital signal processing relies heavily on operations in the frequency domain (i.e. on the Fourier transform). For example, several ztrátový image and sound compression methods employ the discrete Fourier transform: the signal is cut into short segments, each is transformed, and then the Fourier coefficients of high frequencies, which are assumed to be unnoticeable, are discarded. The decompressor computes the inverse transform based on this reduced number of Fourier coefficients. (Compression applications often use a specialized form of the DFT, the diskrétní kosinová transformace nebo někdy modifikovaná diskrétní kosinová transformace.)Some relatively recent compression algorithms, however, use wavelet transforms, which give a more uniform compromise between time and frequency domain than obtained by chopping data into segments and transforming each segment. V případě JPEG2000, this avoids the spurious image features that appear when images are highly compressed with the original JPEG.

Parciální diferenciální rovnice

Discrete Fourier transforms are often used to solve parciální diferenciální rovnice, where again the DFT is used as an approximation for the Fourierova řada (which is recovered in the limit of infinite N). The advantage of this approach is that it expands the signal in complex exponentials ${displaystyle e^{inx}}$, which are eigenfunctions of differentiation: ${displaystyle {{ ext{d}}{ ig (}e^{inx}{ ig )}}/{ ext{d}}x=ine^{inx}}$. Thus, in the Fourier representation, differentiation is simple—we just multiply by ${displaystyle in}$. (However, the choice of ${displaystyle n}$ is not unique due to aliasing; for the method to be convergent, a choice similar to that in the trigonometric interpolation section above should be used.) A linear differential equation with constant coefficients is transformed into an easily solvable algebraic equation. One then uses the inverse DFT to transform the result back into the ordinary spatial representation. Such an approach is called a spectral method.

Polynomial multiplication

Suppose we wish to compute the polynomial product C(X) = A(X) · b(X). The ordinary product expression for the coefficients of C involves a linear (acyclic) convolution, where indices do not "wrap around." This can be rewritten as a cyclic convolution by taking the coefficient vectors for A(X) a b(X) with constant term first, then appending zeros so that the resultant coefficient vectors A a b have dimension d > deg(A(X)) + deg(b(X)). Pak,

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

Kde C is the vector of coefficients for C(X), and the convolution operator ${displaystyle *,}$ is defined so

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

But convolution becomes multiplication under the DFT:

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

Here the vector product is taken elementwise. Thus the coefficients of the product polynomial C(X) are just the terms 0, ..., deg(A(X)) + deg(b(X)) of the coefficient vector

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