Nejednotná diskrétní Fourierova transformace - Non-uniform discrete Fourier transform

V aplikované matematice je nejednotná diskrétní Fourierova transformace ( NUDFT nebo NDFT ) signálu typem Fourierovy transformace související s diskrétní Fourierovou transformací nebo Fourierovou transformací v diskrétním čase , ale ve kterém není vstupní signál vzorkován ve stejně rozmístěných bodech nebo frekvence (nebo obojí). Jedná se o zobecnění posunutého DFT . Má důležité aplikace ve zpracování signálu, zobrazování magnetickou rezonancí a numerické řešení parciálních diferenciálních rovnic.

Jako všeobecné přístupu k nerovnoměrným odběr vzorků se NUDFT umožňuje získat informace ve frekvenční doméně o konečné délky signálu v jakékoli frekvenci. Jedním z důvodů přijetí NUDFT je, že mnoho signálů má svou energii distribuovanou nerovnoměrně ve frekvenční doméně. Proto může být nejednotné schéma vzorkování pohodlnější a užitečnější v mnoha aplikacích pro zpracování digitálního signálu . Například NUDFT poskytuje variabilní spektrální rozlišení řízené uživatelem.

Definice

Neuniformní diskrétní Fourierova transformace převádí posloupnost komplexních čísel do jiné sekvence komplexních čísel definovaných ${\ displaystyle N}$${\ displaystyle x_ {0}, \ ldots, x_ {N-1}}$${\ displaystyle X_ {0}, \ ldots, X_ {N-1}}$

${\ displaystyle X_ {k} = \ součet _ {n = 0} ^ {N-1} x_ {n} e ^ {- 2 \ pi ip_ {n} f_ {k}}, \ quad 0 \ leq k \ leq N-1,}$

( 1 )

kde jsou ukázkové body a jsou frekvence. Všimněte si, že pokud a pak se rovnice ( 1 ) redukuje na diskrétní Fourierovu transformaci . Existují tři typy NUDFT. ${\ displaystyle p_ {0}, \ ldots, p_ {N-1} \ v [0,1]}$${\ displaystyle f_ {0}, \ ldots, f_ {N-1} \ in [0, N]}$${\ displaystyle p_ {n} = n / N}$${\ displaystyle f_ {k} = k}$

• Neuniformní diskrétní Fourierova transformace typu I (NUDFT-I) používá jednotné vzorkovací body, ale nejednotné (tj. Neceločíselné ) frekvence . To odpovídá vyhodnocení zobecněné Fourierovy řady ve stejných bodech. Je také známý jako NDFT.${\ displaystyle p_ {n} = n / N}$${\ displaystyle f_ {k}}$
• Neuniformní diskrétní Fourierova transformace typu II (NUDFT-II) používá jednotné (tj. Celé číslo) frekvence, ale nejednotné vzorkovací body . To odpovídá vyhodnocení Fourierovy řady na nevychýlených bodech. Je také známý jako adjoint NDFT.${\ displaystyle f_ {k} = k}$${\ displaystyle p_ {n}}$
• Neuniformní diskrétní Fourierova transformace typu III (NUDFT-III) používá jak nejednotné vzorkovací body, tak nejednotné frekvence . To odpovídá vyhodnocení zobecněné Fourierovy řady v bodech bez mezery. Je také známý jako NNDFT.${\ displaystyle p_ {n}}$${\ displaystyle f_ {k}}$

Podobný sada NUDFTs lze definovat substitucí pro v rovnici ( 1 ). Na rozdíl od jednotného případu však tato substituce nesouvisí s inverzní Fourierovou transformací. Inverze NUDFT je samostatný problém, popsaný níže. ${\ displaystyle -i}$${\ displaystyle + i}$

Vícedimenzionální NUDFT

Vícedimenzionální NUDFT převádí -dimenzionální pole komplexních čísel na jiné -dimenzionální pole komplexních čísel definované ${\ displaystyle d}$${\ displaystyle x _ {\ mathbf {n}}}$${\ displaystyle d}$${\ displaystyle X _ {\ mathbf {k}}}$

${\ displaystyle X _ {\ mathbf {k}} = \ součet _ {\ mathbf {n} = \ mathbf {0}} ^ {\ mathbf {N} -1} x _ {\ mathbf {n}} e ^ {- 2 \ pi i \ mathbf {p} _ {\ mathbf {n}} \ cdot {\ boldsymbol {f}} _ {\ mathbf {k}}}}$

kde jsou ukázkové body, jsou frekvence a a jsou -dimenzionální vektory indexů od 0 do . Vícerozměrné NUDFT typu I, II a III jsou definovány analogicky k případu 1D. ${\ displaystyle \ mathbf {p} _ {\ mathbf {n}} \ v [0,1] ^ {d}}$${\ displaystyle {\ boldsymbol {f}} _ {\ mathbf {k}} \ v [0, N_ {1}] \ krát [0, N_ {2}] \ krát \ cdots \ krát [0, N_ {d }]}$${\ displaystyle \ mathbf {n} = (n_ {1}, n_ {2}, \ ldots, n_ {d})}$${\ displaystyle \ mathbf {k} = (k_ {1}, k_ {2}, \ ldots, k_ {d})}$${\ displaystyle d}$${\ displaystyle \ mathbf {N} -1 = (N_ {1} -1, N_ {2} -1, \ ldots, N_ {d} -1)}$

Vztah k Z-transformaci

NUDFT-I lze vyjádřit jako Z-transformaci . NUDFT-I sekvence délky je ${\ displaystyle x [n]}$${\ displaystyle N}$

${\ displaystyle X (z_ {k}) = X (z) | _ {z = z_ {k}} = \ součet _ {n = 0} ^ {N-1} x [n] z_ {k} ^ { -n}, \ quad k = 0,1, ..., N-1,}$

kde je Z-transformace , a jsou libovolně odlišné body v rovině z. Všimněte si, že NUDFT se redukuje na DFT, když jsou vzorkovací body umístěny na jednotkové kružnici ve stejných rozestupech úhlů. ${\ displaystyle X (z)}$${\ displaystyle x [n]}$${\ displaystyle \ {z_ {i} \} _ {i = 0,1, ..., N-1}}$

Vyjádříme-li výše uvedené jako matici, dostaneme

${\ displaystyle \ mathbf {X} = \ mathbf {D} \ mathbf {x}}$

kde

${\ displaystyle \ mathbf {X} = {\ začátek {bmatrix} X (z_ {0}) \\ X (z_ {1}) \\\ vdots \\ X (z_ {N-1}) \ end {bmatrix }}, \ quad \ mathbf {x} = {\ begin {bmatrix} x [0] \\ x [1] \\\ vdots \\ x [N-1] \ end {bmatrix}}, {\ text { and}} \ quad \ mathbf {D} = {\ begin {bmatrix} 1 & z_ {0} ^ {- 1} & z_ {0} ^ {- 2} & \ cdots & z_ {0} ^ {- (N-1) } \\ 1 & z_ {1} ^ {- 1} & z_ {1} ^ {- 2} & \ cdots & z_ {1} ^ {- (N-1)} \\\ vdots & \ vdots & \ vdots & \ ddots & \ vdots \\ 1 & z_ {N-1} ^ {- 1} & z_ {N-1} ^ {- 2} & \ cdots & z_ {N-1} ^ {- (N-1)} \ end {bmatrix} }.}$

Přímá inverze NUDFT-I

Jak vidíme, NUDFT-I je charakterizován body, a tedy body. Pokud bychom dále faktorizovali , vidíme, že je to nesingulární, pokud jsou body odlišné. Pokud je nesingulární, můžeme získat jedinečný inverzní NUDFT-I takto: ${\ displaystyle \ mathbf {D}}$${\ displaystyle N}$ ${\ displaystyle {z_ {k}}}$${\ displaystyle \ det (\ mathbf {D})}$${\ displaystyle \ mathbf {D}}$${\ displaystyle N}$ ${\ displaystyle {z_ {k}}}$${\ displaystyle \ mathbf {D}}$

${\ displaystyle \ mathbf {x} = \ mathbf {D ^ {- 1}} \ mathbf {X}}$.

Vzhledem k tomu můžeme použít Gaussovu eliminaci k řešení pro . Složitost této metody je však . Abychom tento problém vyřešili efektivněji, nejprve určíme přímo polynomiální interpolací: ${\ displaystyle \ mathbf {X} {\ text {a}} \ mathbf {D}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle O (N ^ {3})}$${\ displaystyle X (z)}$

${\ displaystyle {\ hat {X}} [k] = X (z_ {k}), \ quad k = 0,1, ..., N-1}$.

Pak jsou koeficienty výše uvedeného interpolačního polynomu. ${\ displaystyle x [n]}$

Vyjádříme- li Lagrangeův polynom řádu , dostaneme ${\ displaystyle X (z)}$${\ displaystyle N-1}$

${\ displaystyle X (z) = \ součet _ {k = 0} ^ {N-1} {\ frac {L_ {k} (z)} {L_ {k} (z_ {k})}} {\ klobouk {X}} [k],}$

kde jsou základní polynomy: ${\ displaystyle \ {L_ {i} (z) \} _ {i = 0,1, ..., N-1}}$

${\ displaystyle L_ {k} (z) = \ prod _ {i \ neq k} (1-z_ {i} z ^ {- 1}), \ quad k = 0,1, ..., N-1 }$.

Vyjádříme- li Newtonovou interpolační metodu, dostaneme ${\ displaystyle X (z)}$

${\ displaystyle X (z) = c_ {0} + c_ {1} (1-z_ {0} z ^ {- 1}) + c_ {2} (1-z_ {0} z ^ {- 1}) (1-z_ {1} z ^ {- 1}) + \ cdots + c_ {N-1} \ prod _ {k = 0} ^ {N-2} (1-z_ {k} z ^ {- 1 }),}$

kde je dělený rozdíl th pořadí s ohledem na : ${\ displaystyle c_ {j}}$${\ displaystyle j}$${\ displaystyle {\ hat {X}} [0], {\ hat {X}} [1], ..., {\ hat {X}} [j]}$${\ displaystyle z_ {0}, z_ {1}, ..., z_ {j}}$

${\ displaystyle c_ {0} = {\ hat {X}} [0],}$

${\ displaystyle c_ {1} = {\ frac {{\ hat {X}} [1] -c_ {0}} {1-z_ {0} z_ {1} ^ {- 1}}},}$

${\ displaystyle c_ {2} = {\ frac {{\ hat {X}} [2] -c_ {0} -c_ {1} (1-z_ {0} z ^ {- 1})}} {(1 -z_ {0} z_ {2} ^ {- 1}) (1-z_ {1} z_ {2} ^ {- 1})}}}}$

${\ displaystyle \ vdots}$

Nevýhodou Lagrangeovy reprezentace je, že jakýkoli další zahrnutý bod zvýší pořadí interpolačního polynomu, což vede k potřebě přepočítat všechny základní polynomy. Jakýkoli další bod zahrnutý do reprezentace Newtona však vyžaduje pouze přidání dalšího termínu.

Můžeme použít dolní trojúhelníkový systém k řešení : ${\ displaystyle \ {c_ {j} \}}$

${\ displaystyle \ mathbf {L} \ mathbf {c} = \ mathbf {X}}$

kde

${\ displaystyle \ mathbf {X} = {\ begin {bmatrix} {\ hat {X}} [0] \\ {\ hat {X}} [1] \\\ vdots \\ {\ hat {X}} [N-1] \ end {bmatrix}}, \ quad \ mathbf {c} = {\ begin {bmatrix} c_ {0} \\ c_ {1} \\\ vdots \\ c_ {N-1} \ end {bmatrix}}, {\ text {and}} \ quad \ mathbf {L} = {\ begin {bmatrix} 1 & 0 & 0 & 0 & \ cdots & 0 \\ 1 & (1-z_ {0} z_ {1} ^ {- 1}) & 0 & 0 & \ cdots & 0 \\ 1 & (1-z_ {0} z_ {2} ^ {- 1}) & (1-z_ {0} z_ {2} ^ {- 1}) (1-z_ {1} z_ {2} ^ {- 1}) & 0 & \ cdots & 0 \\\ vdots & \ vdots & \ vdots & \ vdots & \ ddots & \ vdots \\ 1 & (1-z_ {0} z_ {N-1} ^ { -1}) & (1-z_ {0} z_ {N-1} ^ {- 1}) (1-z_ {1} z_ {N-1} ^ {- 1}) & \ cdots & \ prod _ {k = 0} ^ {N-2} (1-z_ {k} z_ {N-1} ^ {- 1}) \ end {bmatrix}}.}$

Podle výše uvedené rovnice lze vypočítat v rámci operací. Tímto způsobem je Newtonova interpolace účinnější než Lagrangeova interpolace, pokud tato není upravena pomocí ${\ displaystyle \ {c_ {j} \}}$${\ displaystyle O (N ^ {2})}$

${\ displaystyle L_ {k + 1} (z) = {\ frac {(1-z_ {k + 1} z ^ {- 1})} {(1-z_ {k} z ^ {- 1})} } L_ {k} (z), \ quad k = 0,1, ..., N-1}$.

Neuniformní rychlá Fourierova transformace

Zatímco naivní aplikace rovnice ( 1 ) vede k algoritmu pro výpočet NUDFT, existují algoritmy založené na rychlé Fourierově transformaci (FFT). Takové algoritmy se označují jako NUFFT nebo NFFT a byly vyvinuty na základě převzorkování a interpolace, min-max interpolace a aproximace nízkého řádu. Obecně platí, že NUFFT využívá FFT převedením neuniformního problému na jednotný problém (nebo posloupnost uniformních problémů), na který lze FFT aplikovat. Softwarové knihovny pro provádění NUFFT jsou k dispozici v 1D, 2D a 3D. ${\ displaystyle O (N ^ {2})}$${\ displaystyle O (N \ log N)}$

Aplikace

Mezi aplikace NUDFT patří:

• Zpracování digitálních signálů
• Magnetická rezonance
• Numerické parciální diferenciální rovnice
• Semi-Lagrangian schémata
• Spektrální metody
• Spektrální analýza
• Návrh digitálního filtru
• Design anténního pole
• Detekce a dekódování duálních vícefrekvenčních signálů (DTMF)

Viz také

• Diskrétní Fourierova transformace
• Rychlá Fourierova transformace
• Nerovnoměrně rozmístěné časové řady
• Spektrální odhad
• Periodogram Lomb – Scargle

Reference

externí odkazy

• Nerovnoměrná Fourierova transformace: Výukový program .
• NFFT 3.0 - výuka
• Softwarová knihovna NUFFT