首頁 › 多語言檔案 Index › 分離傅立葉變換

頂10篇文章

土豆

烏龜

薑黃

Gmail

第二次世界大戰

DirectX

光合作用

菲律賓

第一次世界大戰

板岩

News:

分離傅立葉變換

傅立葉變換
連續的傅立葉變換
傅立葉系列
分離傅立葉變換
離散時間傅立葉變換
相關變換

在數學 分離傅立葉變換(DFT) 是其中一個具體形式傅立葉分析. 同樣地，它變換一個作用成另，稱頻域表示法或者簡單地 DFT經常是一個作用在的，原始的作用( 時間界域). 但DFT要求是的一個輸入函數分離并且非零值有被限制的(有限)期間。這樣輸入經常被創造採樣一個連續函數，像人的聲音。并且不同於離散時間傅立葉變換 (DTFT)，它只評估足够的頻率組分重建分析的有限段。它的反面變換不可能再生產整個時間界域，除非輸入偶然是週期性的(永遠)。所以它經常說DFT是一變換為對有限領域離散時間作用的傅立葉分析。分解的正弦依據作用有同樣物產。

因為輸入函數是一個有限序列真正或複雜形勢DFT為被存儲的處理信息是理想的計算機. 特別是， DFT廣泛被使用信號處理并且要分析頻率的相關領域包含在被抽樣的信號解決偏微分方程和進行其他操作例如捲積. DFT可以使用a實踐上高效率地被計算快速的傅立葉變換 (FFT)算法。

因為FFT算法那麼共同地被使用計算DFT，二個期限互換性是常用的在口語設置，雖然有清楚的分別：「DFT」提到數學變革，不管怎樣它被計算，而「FFT」提到任何一個幾種高效率的算法為DFT。這分別由同義詞進一步弄髒，然而，有限傅立葉變換為DFT，明顯地把期限「快速的傅立葉變換」日期填早(等Cooley， 1969)，但有同樣 initialism.

定義

序列 N 複雜形勢 x₀, ..., x_N−1 被變換成序列 N 複雜形勢 x₀, ..., x_N−1 由DFT根據慣例：

$X_k = \ sum_ {n=0} ^ {N-1} x_n e^ {- \ frac {2 \ pi i} {N} k n} \方形字體\方形字體k = 0， \加點， N-1$

那裡 $e^ {\ frac {2 \ pi i} {N}}$ 是原始N'th 團結根 .

變換由標誌有時表示 $\ mathcal {F}$ 作為 $\ mathbf {X} = \ mathcal {F} \被留下\ {\ mathbf {x} \正確\}$ 或 $\ mathcal {F} \被留下(\ mathbf {x} \正確)$ 或 $\ mathcal {F} \ mathbf {x}$ .

相反分離傅立葉變換(IDFT) 給

$x_n = \ frac {1} {N} \ sum_ {k=0} ^ {N-1} X_k e^ {\ frac {2 \ pi i} {N} k n} \方形字體\方形字體n = 0， \加點， N-1。$

這些等式的一個簡單的描述是複雜形勢 $x k$ 代表輸入「信號」的不同的正弦組分的高度和階段 $x n$ . DFT計算 $x k$ 從 $x n$ ，而IDFT顯示如何計算 $x n$ 作為正弦組分的一個總和 $x k exp (2π i k n / N) / N$ 與頻率 $k / N$ 週期每個樣品。通過寫等式在這形式，我們做廣泛的用途 Euler的慣例表達sinusoids根據複雜exponentials，是更加容易操作。 (相似，由文字 $x k$ 在極性形式我們立刻得到sinusoid高度從 $| x k |$ 并且階段從複雜論據.) 這個表示法一重要微妙，混淆現象下面被談論。

注意倍增DFT和IDFT的正常化因素(這裡1和1N)和方次數的標誌僅僅是大會，并且不同在有些治療。這些大會的唯一的要求是DFT和IDFT有相反標誌方次數，并且他們的正常化因素產品是1N. 正常化 $1 \ sqrt {N}$ 為DFT和IDFT牌子變換單一有一些理論好處，但是它經常是實用在數字計算同時執行結垢如上所述(和單位結垢可以是方便的用其他方式)。

(大會負號方次數經常是方便的，因為它意味那 $x k$ 是「正面頻率的」高度 $2π k / N$ . 等效地， DFT經常被重視作為a 被匹配的過濾器: 當尋找頻率+1時，你關聯接踵而來的信號以−1頻率。)

在以下討論中期限「序列」和「傳染媒介」將被認為互換性。

物產

完整性

分離傅立葉變換是可轉位的，線性變革

$\ mathcal {F} ：\ mathbb {C} ^N \ \ mathbb {C} ^N$

與 $\ mathbb {C}$ 表示套複雜形勢. 換句話說，為其中任一 N > 0， N-尺寸複雜傳染媒介有DFT和是反之的IDFT N-尺寸複雜傳染媒介。

正交性

傳染媒介 $e^ {\ frac {2 \ pi i} {N} kn}$ 形成正交依據套 N-尺寸複雜傳染媒介：

$\ sum_ {n=0} ^ {\被留下的 N-1} \被留下(e^ {\ frac {2 \ pi i} {N} kn} \ 正確) (e^ {- \ frac {2 \ pi i} {N} k'n} \正確) =N~ \ delta_ {kk'}$

那裡 $~ \ delta_ {kk'}$ 是 Kronecker三角洲. 這個正交性情況可以用於從DFT的定義獲得慣例為IDFT，并且與unitarity物產是等效的如下。

Plancherel定理和Parseval的定理

如果 x_k 并且 Y_k 是DFTs x_n 并且 y_n 分別然後 Plancherel定理狀態：

$\ sum_ {n=0} ^ {N-1} x_n y^*_n = \ frac {1} {N} \ sum_ {k=0} ^ {N-1} X_k Y^*_k$

那裡星表示複雜結合. Parseval的定理是Plancherel定理和狀態的一個特殊情況：

$\ sum_ {n=0} ^ {N-1} |x_n|^2 = \ frac {1} {N} \ sum_ {k=0} ^ {N-1} |X_k|^2.$

這些定理也是等值到單一的情況如下。

週期性

如果定義了DFT的表示為所有整數被評估 $k$ 而不是為 $k = 0， \加點， N-1$ 然後發生的無窮序列是DFT的一個週期性引伸，週期性以期間 N.

週期性可以直接地從定義顯示：

$X_ {k+N} = \ sum_ {n=0} ^ {N-1} x_n e^ {- \ frac {2 \ pi i} {N} (k+N) n} = \ sum_ {n=0} ^ {N-1} x_n e^ {- \ frac {2 \ pi i} {N} k n} e^ {- 2 \ pi i n} = \ sum_ {n=0} ^ {N-1} x_n e^ {- \ frac {2 \ pi i} {N} k n} = X_k$

那裡我們使用了事實那 $e - 2π i = 1$ . 它可以相似顯示IDFT慣例導致一個週期性引伸。

轉移定理

倍增 $x n$ 由a 線性階段 $e^ {\ frac {2 \ pi i} {N} n m}$ 為某一整數 $m$ 對應於a 循環位移 產品 $x k$ : $x k$ 被替換 $x k - m$ 下標被解釋的地方模數 $N$ (即，週期性地)。同樣，輸入的一個循環位移 $x n$ 對應於倍增產品 $x k$ 在一個線性階段以前。數學上，如果 ${x n}$ 代表傳染媒介 x 然後

如果 $\ mathcal {F} (\ {x_n \}) _k=X_k$

然後 $\ mathcal {F} (\ {x_n \ cdot e^ {\ frac {2 \ pi i} {N} n m} \}) _k=X_ {公里}$

并且 $\ mathcal {F} (\ {x_ {n-m} \}) _k=X_k \ cdot e^ {- \ frac {2 \ pi i} {N} k m}$

圓捲積定理和互相關定理

捲積定理為連續和離散時間傅立葉變換表明二個無窮序列的捲積可以獲得作為反面變換個體的產品變換。以序列和變換長度N， a 環狀升起:

$\開始{排列} \ mathcal {F} ^ {- 1} \左\ {\ mathbf {X \ cdot Y} \正確\} _n \ & \ stackrel {\ mathrm {def}} {=} \ \ frac {1} {N} \ sum_ {k=0} ^ {N-1} X_k \ cdot Y_k \ cdot e^ {\ frac {2 \ pi i} {N} k n} \ \ &= \ frac {1} {N} \ sum_ {k=0} ^ {N-1} \左(\ sum_ {l=0} ^ {N-1} x_l e^{- \ frac {2 \ pi i} {N} k l} \正確) \ cdot \被留下的(\ sum_ {m=0} ^ {N-1} y_m e^ {- \ frac {2 \ pi i} {N} k m} \正確) \ cdot e^ {\ frac {2 \ pi i} {N} k n} \ \ &= \ sum_ {l=0} ^ {N-1} x_l \ sum_ {m=0} ^ {N-1} y_m \離開(\ frac {1} {N} \ sum_ {k=0} ^ {N-1} e^ {\ frac {2 \ pi i} {N} k (n-l-m)} \正確)。 \末端{排列}$

數量括號內是0為所有價值 $m$ 除了那些形式 $n - l - p N$ 的地方 $p$ 是任何整數。在那些價值，它是1。因此它可能被一個無限總和替換 Kronecker三角洲作用和我們相應地繼續。注意我們可以也擴大極限 $m$ 到無限，以理解 $x$ 并且 $y$ 序列被定義成0外部[0， N-1]:

$\開始{排列} \ mathcal {F} ^ {- 1} \左\ {\ mathbf {X \ cdot Y} \正確\} _n &= \ sum_ {l=0} ^ {N-1} x_l \ sum_ {m=- \ infty} ^ {\ infty} y_m \左(\ sum_ {p=- \ infty} ^ {\ infty} \ delta_ {m (n lpN)} \正確) \ \ &= \ sum_ {l=0} ^ {N-1} x_l \ sum_ {p=- \ infty} ^ {\ infty} \被留下(\ sum_ {m=- \ infty} ^ {\ infty} y_m \ cdot \ delta_ {m (n lpN)}\正確) \ \ &= \ sum_ {l=0} ^ {N-1} x_l \被留下的(\ sum_ {p=- \ infty} ^ {\ infty} y_ {n lpN} \正確) \ \ stackrel {\ mathrm {def}} {=} \ (\ mathbf {x * y_N}) _n \， \末端{排列}$

哪些是捲積 $\ mathbf {x}$ 序列與a 週期性地延長 $\ mathbf {y}$ 被定義的序列 :

$(\ mathbf {y_N}) _n \ \ stackrel {\ mathrm {def}} {=} \ \ sum_ {p=- \ infty} ^ {\ infty} y_ {(npN)}。\，$

同樣，它可以顯示那:

$\ mathcal {F} ^ {- 1} \被留下\ {\ mathbf {X^* \ cdot Y} \正確\} _n = \ sum_ {l=0} ^ {N-1} x_l^* \ cdot (y_N) _ {n+l} \ \ \ stackrel {\ mathrm {def}} {=} \ \ (\ mathbf {x \星y_N}) _n \，$

哪些是互相關 $\ mathbf {x}$ 并且 $\ mathbf {y_N}。$

捲積或交互作用總和的一個直接評估(上述)要求 $O (N 2)$ 操作為長度N.產品序列。一個間接方法，使用變換，可能利用 $O (N 日誌 N)$ 效率快速的傅立葉變換 (FFT)完成好表現。此外，捲積可以用於高效率地計算DFTs通過 Rader的FFT算法并且 Bluestein的FFT算法.

方法也被開發使用圓捲積作為達到正常的一個高效率的過程一部分(non-circular)捲積與 $\ mathbf {x}$ 或 $\ mathbf {y}$ 比實用變換大小(潛在地長期程序化N). 二個這樣方法叫重疊保存并且重疊增加^[1].

三角插值法多項式

$p (t) = \ frac {X_0} {N} + \ frac {X_1} {N} e^ {它} + \ cdots + \ frac {X_ {N/2}} {N} \ COS (Nt/2) + \ frac {X_ {N/2+1}} {N} e^ {(- N/2+1)它} + \ cdots + \ frac {X_ {N-1}} {N} e^ {-它}$ 為

N

均勻 ,

$p (t) = \ frac {X_0} {N} + \ frac {X_1} {N} e^ {它} + \ cdots + \ frac {X_ {\ lfloor N/2 \ rfloor}} {N} e^ {\ lfloor N/2 \ rfloor它} + \ frac {X_ {\ lfloor N/2 \ rfloor+1}} {N} e^ {- \ lfloor N/2 \ rfloor它} + \ cdots + \ frac {X_ {N-1}} {N} e^ {-它}$ 為

N

奇怪，

那裡系數 x_k /N 由DFT給 x_n 上面，滿足插值法物產 $p (2π n / N) = x n$ 為 $n=0， \ ldots， N-1$ .

為均勻 $N$ 注意 Nyquist組分 $\ frac {X_ {N/2}} {N} \ COS (Nt/2)$ 特別地被處理。

這插值法是 不獨特: 混淆現象暗示一個可能增加 N 對任何複雜sinusoid頻率(即。改變 $e - i t$ $e i (N - 1) t$ )沒有改變插值法物產，但給不同價值在之間 $x n$ 點。因為它有二有用的物產，選擇上面，然而，是典型的。首先，它包括頻率有最小的可能的巨大的sinusoids，並且使均方減到最小傾斜 $\ int |p'(t)|^2 dt$ 內插的作用。其次，如果 $x n$ 是實數，然後 $p (t)$ 是真正的。

相反，最明顯的三角插值法多項式是頻率範圍從0的那個 $N - 1$ (而不是大致 $- N / 2$ $+ N / 2$ 如上所述)，相似於相反DFT慣例。這插值法沒有使傾斜減到最小，并且是沒有一般real-valued為真正 $x n$ ; 它的用途是一個常見錯誤。

單一的DFT

看DFT另一個方式將注意到，在上述討論中， DFT可以被表達作為a Vandermonde矩陣:

$\ mathbf {F} = \開始{bmatrix} \ omega_N^ {0 \ cdot 0} & \ omega_N^ {0 \ cdot 1} & \ ldots & \ omega_N^ {0 \ cdot (N-1)} \ \ \ omega_N^ {1 \ cdot 0} & \ omega_N^ {1 \ cdot 1} & \ ldots & \ omega_N^ {1 \ cdot (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)} \ \ \末端{bmatrix}$

那裡

$\ omega_N = e^ {- 2 \ pi i/N} \，$

是原始團結第n根 . 反面變換由上述矩陣的反面然後給：

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

與單一正常化常數 $1 \ sqrt {N}$ DFT成為a 單一的變革由一個單式矩陣定義：

$\ mathbf {U} = \ mathbf {F}/\ sqrt {N}$

$\ mathbf {U} ^ {- 1} = \ mathbf {U} ^*$

$|\ det (\ mathbf {U})|=1$

那裡 det () 是定列式作用。定列式是本徵值的產品，總是 $\ pm 1$ 或 $\ pm i$ 如下所述。在一個真正的向量空間，單一的變革可以簡單地被重視作為坐標系的剛性自轉，并且剛性自轉的所有物產在單一的DFT可以被發現。

DFT的正交性現在被表達作為 orthonormality 在數學許多區域出現如所描述的情況( 團結根 ):

$\ sum_ {m=0} ^ {N-1} U_ {公里} U_ {mn} ^*= \ delta_ {kn}$

如果 $\ mathbf {X}$ 被定義作為傳染媒介的單一的DFT $\ mathbf {x}$ 然後

$X_k= \ sum_ {n=0} ^ {N-1} U_ {kn} x_n$

并且 Plancherel定理被表達如下：

$\ sum_ {n=0} ^ {N-1} x_n y_n^* = \ sum_ {k=0} ^ {N-1} X_k Y_k^*$

如果我們觀看DFT作為在一個新的坐標系簡單地指定傳染媒介組分的同等的變革，則以上是聲明二傳染媒介數量積被保存在單一的DFT變革之下。為特殊情況 $\ mathbf {x} = \ mathbf {y}$ 這暗示傳染媒介的長度被保存，因為很好這是正義的 Parseval的定理:

$\ sum_ {n=0} ^ {N-1}|x_n|^2 = \ sum_ {k=0} ^ {N-1}|X_k|^2$

表達相反DFT根據DFT

DFT的有用的物產是相反DFT可以容易地被表達根據(向前) DFT，通過幾個知名的「把戲」。 (例如，在計算，只實施對應到一个的快速的傅立葉變換變換方向經常是方便的然後得到其他變換方向從一開始。)

首先，我們可以通過扭轉輸入計算相反DFT ：

$\ mathcal {F} ^ {- 1} (\ {x_n \}) = \ mathcal {F} (\ {x_ {N - n} \})/N$

(照常，下標被解釋模數 $N$ ; 因此，為 $n = 0$ 我們有 $x N - 0 = x 0$ .)

其次，你可能也共軛輸入和輸出：

$\ mathcal {F} ^ {- 1} (\ mathbf {x}) = \ mathcal {F} (\ mathbf {x} ^*) ^*/N$

第三，這個結合把戲變形，是有時更好的，因為它不要求數據值的修改，介入交換在計算機可以簡單地完成通過修改的真正和虛構部分( 尖). 定義交換( $x n$ ) $x n$ 與它真正和虛構部分交換是，如果 $x n = a + b i$ 然後交換( $x n$ )是 $b + a i$ . 等效地，交換( $x n$ )均等 $i x_n^*$ . 然後

$\ mathcal {F} ^ {- 1} (\ mathbf {x}) = \ textrm {交換} (\ mathcal {F} (\ textrm {交換} (\ mathbf {x}))) /N$

即反面變換是相同像向前變換與為輸入和輸出交換的真正和虛構部分，由正常化(Duhamel決定等。, 1988).

結合把戲可能也用於定義新變換，接近DFT，是 involutary- i。e，是它自己的反面。特別是， $T (\ mathbf {x}) = \ mathcal {F} (\ mathbf {x} ^*)/\ sqrt {N}$ 清楚地是它自己的反面： $T (T (\ mathbf {x})) = \ mathbf {x}$ . 緊密地相關的involutary變革(由因素(1+i)/√2)是 $H (\ mathbf {x}) = \ mathcal {F} ((1+i) \ mathbf {x} ^*)/\ sqrt {2N}$ 從 $(1 + i)$ 因素 $H (H (\ mathbf {x}))$ 取消2。為真正的輸入 $\ mathbf {x}$ 真正的部分 $H (\ mathbf {x})$ 是分離Hartley變換也involutary。

本徵值和特徵向量

本徵值 DFT矩陣是簡單和知名的，而特徵向量是複雜，不獨特的，并且是持續的研究主題。

考慮單一的形式 $\ mathbf {U}$ 為長度DFT定義以上 $N$ 的地方 $\ mathbf {U} _ {m， n} = \ omega_N^ {mn}/\ sqrt {N} = \ exp (- 2 \ pi i mn/N)/\ sqrt {N}$ . 這個矩陣滿足等式：

$\ mathbf {U} ^4 = \ mathbf {I}。$

這能從相反物產被看見上面：操作 $\ mathbf {U}$ 在逆序兩次給原始的數據，如此運行 $\ mathbf {U}$ 四次給原始的數據并且因而是單位矩陣. 這意味著本徵值 $λ$ 滿足a 特徵方程:

λ 4 = 1.

所以，本徵值 $\ mathbf {U}$ 是四團結根 : $λ$ 是+1， −1， +i或者−i.

因為只有四分明本徵值為此 $N \時期N$ 矩陣，他們有一些多樣性. 多樣性給數字線性獨立對應於每本徵值的特徵向量。 (筆記有 N 獨立特徵向量; 一個單式矩陣從未是瑕疵.)

他們的多樣性的問題是由McClellan解決的，并且Parks (1972)，雖然更晚顯示對與解決的問題是等效的高斯 (Dickinson和Steiglitz 1982)。多樣性取決於價值 $N$ 模數和下表給4 ：

單一的DFT矩陣的本徵值λ的Multiplicities U 作為變換大小功能 N (根據整數 m).
大小 N	λ = +1	λ = −1	λ = -i	λ = +i
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

不幸地，簡單的分析慣例為特徵向量不被知道。而且，因為特徵向量的所有線性組合為同一本徵值也是一個特徵向量為那本徵值，特徵向量不是獨特的。各種各樣的研究員提出了特徵向量不同的選擇，選擇滿足有用的物產像正交性并且有「簡單的」形式(即， McClellan和Parks 1972年; dickinson和Steiglitz 1982年; grunbaumm 1982年; atakishiyev和Wolf 1997年; Candan 等。, 2000; 漢納等。, 2004).

DFT矩陣的特徵向量選擇近年來變得重要為了定義一個分離類似物分數傅立葉變換- DFT矩陣可以被採取對分數冪通過exponentiating本徵值(即， Rubio和Santhanam 2005)。為連續的傅立葉變換自然正交特徵函數是 Hermite作用，因此這些的各種各樣的分離類似物被使用了作為DFT的特徵向量，例如 Kravchuk多項式 (Atakishiyev和Wolf 1997)。定義分數分離傅立葉變換的特徵向量然而「最佳的」選擇依然是一個未解決的問題。

真正輸入DFT

如果 $x_0， \ ldots， x_ {N-1}$ 是實數，當他們經常在實際應用，然後DFT服從對稱：

$X_k = X_ {N-k} ^*，$

那裡星表示複雜結合并且下標是被解釋的模數 N.

所以，為真正的輸入輸出的DFT是半重複的，并且你通過只看產品的粗礪一半得到完全信息 $X_0， \ ldots， X_ {N-1}$ . 在這種情況下，「DC」元素 $x 0$ 為均勻是純粹真正的，和 N 「Nyquist」元素 $x N / 2$ 有也真正的，那麼確切地是 N 非冗餘的實數在前半+複雜產品的Nyquist元素 x.

使用 Euler的慣例內插的三角多項式可能然後被解釋作為正弦和餘弦函數的一個總和。

廣義或被轉移的DFT

由一些真正的轉移轉移變換採樣及時並且/或者頻域是可能的 a 并且 b分別。這有時通認作為a 廣義DFT (或 GDFT)，也叫 被轉移的DFT 或 垂距DFT和有近似物產對普通的DFT ：

$X_k = \ sum_ {n=0} ^ {N-1} x_n e^ {- \ frac {2 \ pi i} {N} (k+b) (n+a)} \方形字體\方形字體k = 0， \加點， N-1$

經常，轉移 $1 / 2$ (一半樣品)使用。當普通的DFT在時間和頻域時對應於一個週期性信號， $a = 1 / 2$ 導致是反週期性的在頻域(的一個信號 $x k + N = - x k$ )反之亦然為 $b = 1 / 2$ . 因此，具體事例 $a = b = 1 / 2$ 通認作為 奇怪時間奇怪頻率 分離傅立葉變換(或O² DFT)。被轉移的這樣變換為相稱數據是最常用的，代表不同的界限對稱，并且為真正相稱數據他們對應於不同的形式的分離餘弦并且正弦變換。

另一個有趣的選擇是 $a = b = - (N - 1) / 2$ 稱 被集中的DFT (或 CDFT). 被集中的DFT有，當的有用的物產 $N$ 是倍數的四，全部四它的本徵值(參見上述)有相等的multiplicities (Rubio和Santhanam 2005)。

分離傅立葉變換可以被觀看作為一個特殊情況 z變換評估在單位圓在複平面; 更加一般z變換對應複雜轉移 a 并且 b 上面。

多維DFT

普通的DFT計算「一維」數據集的變換：序列(或列陣) $x n$ 那是一分離可變物的作用 $n$ . 更加一般，你可能定義多維一個多維列陣的DFT $x_ {n_1、n_2， \小點， n_d}$ 那是作用 $d$ 分離可變物 $n_ \側房= 0， 1， \加點， N_ \側房1$ 為 $\側房$ 在 $1， 2， \小點， d$ :

$X_ {k_1， k_2， \加點， k_d} = \ sum_ {n_1=0} ^ {N_1-1} \左(\ omega_ {N_1} ^ {~k_1 n_1} \ sum_ {n_2=0} ^ {N_2-1} \左(\ 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， \加點， n_d} \正確) \ cdots \正確) \，$

那裡 $\ omega_ {N_ \側房} = \ exp (- 2 \ pi i/N_ \側房)$ 如上所述和 $d$ 產品索引跑從 $k_ \側房= 0， 1， \加點， N_ \側房1$ . 這更加緊湊地被表達傳染媒介記法，我們定義了的地方 $\ mathbf {n} = (n_1， n_2， \加點， n_d)$ 并且 $\ mathbf {k} = (k_1， k_2， \加點， k_d)$ $d$ -索引尺寸傳染媒介從0 $\ mathbf {N} - 1$ 我們定義了 $\ mathbf {N} - 1 = (N_1 - 1， N_2 - 1， \加點， N_d - 1)$ :

$X_ \ mathbf {k} = \ sum_ {\ mathbf {n} =0} ^ {\ mathbf {N} - 1} e^ {- 2 \ pi i \ mathbf {k} \ cdot (\ mathbf {n}/\ mathbf {N})} x_ \ mathbf {n} \，$

那裡分裂 $\ mathbf {n}/\ mathbf {N}$ 被定義 $\ mathbf {n}/\ mathbf {N} = (n_1/N_1， \加點， n_d/N_d)$ 要是執行的元素明智和總和表示套被築巢的總和上面。

多維DFT的反面是，類似於一維案件給出：

$x_ \ mathbf {n} = \ frac {1} {\ prod_ {\ ell=1} ^d N_ \側房} \ sum_ {\ mathbf {k} =0} ^ {\ mathbf {N} - 1} e^ {2 \ pi i \ mathbf {n} \ cdot (\ mathbf {k}/\ mathbf {N})} X_ \ mathbf {k} \。$

多維DFT有一個簡單的解釋。正一維DFT表達輸入 $x n$ 作為sinusoids的疊置，多維DFT表達輸入作為疊置平面波或者擺動沿方向的sinusoids $\ mathbf {k}/\ mathbf {N}$ 在空間和有高度 $X_ \ mathbf {k}$ . 這樣分解是重要性為一切從數字式圖像處理 (d = 2)到解決偏微分方程在三個維度(d = 3)通過打破解答平面波。

計算上，多維DFT簡單地是構成一維DFTs序列沿每個維度。例如，在二維案件 $x_ {n_1， n_2}$ 你可能首先計算 $N 1$ 列的獨立DFTs (即， $n 2$ )形成一個新的列陣 $y_ {n_1， k_2}$ 然後計算 $N 2$ 獨立DFTs $y$ 沿專欄(沿 $n 1$ )形成決賽成績 $X_ {k_1， k_2}$ . 或者，你可能變換專欄然後列這順序是非物質的，因為被築巢的總和上面通勤.

因此給出方式計算一維DFT (即。一種普通的一維FFT算法)，一个立刻有一個方式高效率地計算多維DFT。這通認作為a 列專欄 算法，雖然內在地也有多維FFT算法.

真正輸入多維DFT

如果輸入 $x_ {n_1、n_2， \小點， n_d}$ 是實數，當他們經常在實際應用，然後DFT產品有一個共軛對稱相似與一維案件上面：

$X_ {k_1， k_2， \加點， k_d} = X_ {N_1 - k_1， N_2 - k_2， \加點， N_d - k_d} ^*，$

那裡星表示複雜結合和 $\側房$ - th下標是被解釋的模數 $N_ \側房$ (為 $\側房= 1,2， \ ldots， d$ ).

應用

DFT看了寬用法橫跨很大數量的領域; 我們只速寫幾個例子如下(也參見參考在末端)。 DFT的所有應用取決於關鍵地一種快速的算法的可及性計算分離傅立葉變換和他們的反面， a 快速的傅立葉變換.

光譜分析

當DFT使用為光譜分析 $\ {x_n \} \，$ 序列通常代表有限套某一信號一致間隔的時間樣品 $x (t) \，$ 的地方 t 代表時間。轉換從連續的時間嚮樣品(離散時間)改變強調傅立葉變換 x (t)到a裡離散時間傅立葉變換 (DTFT)，一般需要畸變的類型叫混淆現象. 適當的樣品率的選擇(參見 Nyquist頻率)是鑰匙到使那個畸變減到最小。同樣，轉換從一個非常長(或無限)序列於易處理的大小需要叫的畸變的類型漏出被體現作為損失細節(aka決議)在DTFT。適當的次級序列長度的選擇是主關鍵字到使那個作用減到最小。當可利用的數據(和時刻處理它)時比必要的數額是更多獲得期望頻率決議，一個標準技術是執行多DFTs，例如創造a 譜圖. 如果預期的結果是能譜，并且噪聲或隨機性是存在數據，平均為多DFTs的巨大組分是減少的一個有用的做法變化光譜(也稱a periodogram 在這上下文); 二個例子的這樣技術是威爾士方法并且巴特利特方法。

畸變的一個最後的來源或許(或幻覺)是DFT，因為它是DTFT的分離採樣，是連續的頻域的作用。那可以通過增加DFT的決議緩和。那個做法在被說明離散時間傅立葉變換文章。

做法有時被稱為 零填料是特殊實施與一道使用了快速的傅立葉變換 (FFT)算法。進行增殖和加法無效用與零被重視的「樣品」是更多比由FFT的固有效率抵銷了。
如已經被注意，漏出強加一個極限給DTFT的固有決議。因此有一個實用極限對可以從細顆粒的DFT獲得的好處。

數據壓縮

數字信號處理的領域在頻域沉重依靠操作(即。在傅立葉變換)。例如，數 lossy 圖像和聲音壓縮方法使用分離傅立葉變換：信號被削減成短的段，其中每一被變換，假設是不顯明的，然後放棄高頻率傅立葉系數。減壓裝置計算反面變換基於傅立葉系數的這個減少的數字。 (壓縮應用經常使用DFT的一個專業形式，分離餘弦變換或有時修改過的分離餘弦變換.)

偏微分方程

分離傅立葉變換是常用的解決偏微分方程DFT再使用作為略計為的地方傅立葉系列 (在極限恢復無限 N). 這種方法的好處是它在複雜exponentials擴展信號 e^inx是分化的特徵函數： d/dx e^inx = 在 e^inx. 因此，在傅立葉表示法，分化是簡單我們倍增 i n. 線性微分方程以恆定的系數被變換成一個容易地可解的代數等式。你然後使用相反DFT變換結果回到普通的空間表示法。這樣方法稱a 鬼方法.

多項增殖

假設我們希望計算多項產品 c(x) = a(x) · b(x). 普通的產品表示為系數 c 介入線性(非週期性的)捲積，索引「不包裹」。這可以被重寫作為循環捲積通過採取系數傳染媒介為 a(x)和 b(x)以首先常數項，然後添附零，以便結果系數傳染媒介 a 并且 b 有維度 d > 程度(a(x)) +程度(b(x)). 然後，

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

那裡 c 是系數傳染媒介為 c(x)和捲積操作員 $*\,$ 如此被定義得

$c_n = \ sum_ {m=0} ^ {d-1} a_m b_ {n-m \ \ mathrm {mod} \ d} \ qquad \ qquad \ qquad n=0,1，…， d-1$

但捲積成為增殖在DFT之下：

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

向量積這裡被採取elementwise。因而產品多項式的系數 c(x)是期限0，…，程度(a(x)) +程度(b(x)) 系數傳染媒介

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

與a 快速的傅立葉變換發生的算法採取O (N 日誌 N)算術運算。由於它的樸素和速度， Cooley-Tukey FFT算法被限制綜合大小，為變換操作經常被選擇。在這種情況下， d 應該選擇輸入多項程度的總和作為最小的整數大於是factorizable入小主因(即。 2， 3和5，取決於FFT實施)。

大整數的增殖

快速地已知的算法為增殖非常大整數使用被概述的多項增殖方法以上。整數在那個基地可以對待多項式的價值具體地被評估在數基，以多項對應的系數於數字。在多項增殖以後，低複雜運載傳播步相對地完成增殖。

一些分離傅立葉變換對

**某一DFT對**
$x_n = \ frac {1} {N} \ sum_ {k=0} ^ {N-1} X_k e^ {i 2 \ pi kn/N}$	$X_k = \ sum_ {n=0} ^ {N-1} x_n e^ {- i 2 \ pi kn/N}$	筆記
$x_n e^ {i 2 \ pi n \ ell/N} \，$	$X_ {k- \側房} \，$	轉移定理
$x_ {n- \側房} \，$	$X_k e^ {- i 2 \ pi k \ ell/N} \，$	轉移定理
$x_n \在\ mathbb {R}$	$X_k=X_ {N-k} ^* \，$	真正的DFT
$a^n \，$	$\離開\ {\開始{矩陣} N & \ mbox {如果} a = e^ {i 2 \ pi k/N} \ \ \ frac {1-a^N} {1-a \， e^ {- i 2 \ pi k/N}} & \ mbox {否則} \末端{矩陣} \正確。$	從幾何級數慣例
${N-1 \選擇n} \，$	$\離開(1+e^ {- i 2 \ pi k/N} \正確) ^ {N-1} \，$	從二項展開式
$\離開\ {\開始{矩陣} \ frac {1} {W} & \ mbox {如果} 2n < W \ mbox {或} 2 (N-n) < W \ \ 0 & \ mbox {否則} \末端{矩陣} \正確。$	$\離開\ {\開始{矩陣} \ frac {\罪孽\左(\ frac {\ pi W k} {N} \正確)} {W \罪孽\離開(\ frac {\ pi k} {N} \正確)} & \ mbox {如果} k \ neq 0 \ \ 1 & \ mbox {否則} \末端{矩陣} \正確。$	$x n$ 是長方形窗口作用 $W$ 點集中了 $x 0$ 的地方 $W$ 是奇怪的整數和 $x k$ 是a sinc-像作用

派生當傅立葉系列

主要文章：分離傅立葉變換的派生

DFT可以獲得作為截傅立葉系列一個週期性序列衝動.

除複雜形勢之外的DFT結束領域

許多DFT的物產只取決於事實那 $e^ {- \ frac {2 \ pi i} {N}}$ 是a 團結本原根有時表示 $ω N$ 或 $W N$ (以便 $\ omega_N^N = 1$ ). 這樣物產包括完整性、正交性、Plancherel/Parseval、週期性、轉移、捲積和unitarity物產上面，並且許多FFT算法。為此，分離傅立葉變換可以通過使用團結根定義領域除複雜形勢之外; 對於更多信息，看見分離傅立葉變換(一般).

參見

DFT矩陣

名單與傅立葉相關變換

筆記

^ T. G. Stockham、Jr.、「高速捲積和交互作用， 1966年」 Proc。 AFIPS春天聯合計算的Conf。 重印在數字信號處理， L。 R. Rabiner和C。 M. Rader，編輯，紐約： IEEE按， 1972年。

參考

Brigham， E。奧蘭(1988)。 快速的傅立葉變換和它的應用. Englewood峭壁，新澤西：學徒霍爾。國際標準書號0-13-307505-2.
Oppenheim，阿倫v。; Schafer， R。 W.; 并且大型裝配架， J。 R. (1999). 離散時間信號處理. 上部馬鞍河，新澤西：學徒霍爾。國際標準書號0-13-754920-2.
史密斯，史蒂文W。 (1999). 「第8章：分離傅立葉變換"， 對數字信號處理的科學家和工程師的指南再版，聖迭戈，加利福尼亞：加利福尼亞技術出版。國際標準書號0-9660176-3-3.
Cormen，托馬斯H。; 查爾斯E。 Leiserson, 羅納德L。 Rivest和 Clifford斯坦 (2001). 「第30章：多項式和FFT "， 算法介紹再版、MIT新聞和McGraw小山， pp.822-848。國際標準書號0-262-03293-7. 特別是。第30.2部分： DFT和FFT， pp.830-838。
P. Duhamel， B。 Piron和J。 M. etcheto (1988)。「在計算相反DFT」。 IEEE Trans。 Acoust。，講話和信號。處理 36 (2): 285–286.
J. H. McClellan和T。 W. parks (1972)。「分離傅立葉變革的本徵值和特徵向量」。 IEEE Trans。音頻Electroacoust。 20 (1): 66-74.
布雷得里W。 Dickinson和肯尼斯・ Steiglitz (1982)。「分離傅立葉變換的特徵向量和作用」。 IEEE Trans。 Acoust。，講話和信號。處理 30 (1): 25-31. (筆記本文有一個明顯的錯別字在它的本徵值multiplicities的桌裡： +i/−i 專欄被互換。正確桌在McClellan可以被發現和Parks 1972年和數字上容易地被證實。)
F. A. grunbaumm (1982)。「分離傅立葉變換的特徵向量」。 J. 算術。肛門。 Appl. 88 (2): 355-363.
Natig M。 Atakishiyev和Kurt Bernardo Wolf (1997)。「分數傅立葉Kravchuk變換」。 J. Opt. Soc. Am. A 14 (7): 1467-1477.
C. Candan， M。 A. Kutay和H。 M.Ozaktas (2000)。「分離分數傅立葉變換」。 IEEE Trans。在信號處理 48 (5): 1329-1337.
Magdy Tawfik漢納， Nabila菲利普Attalla Seif和Waleed Abd El Maguid Ahmed (2004)。「Hermite高斯像根據它的正交投影矩陣的單一價值分解的分離傅立葉變換矩陣的特徵向量」。 IEEE Trans。 Circ。 Syst. I 51 (11): 2245-2254.
胡安G。 VargasRubio和Balu Santhanam (2005)。「在multiangle圍繞分離分數傅立葉變換」。 IEEE信號。 Proc。 Lett。 12 (4): 273-276.
J. Cooley P。劉易斯和P。 welch (1969)。「有限傅立葉變換」。 IEEE Trans。音頻Electroacoustics 17 (2): 77-85.

外部鏈接

v • d • e 數字信號處理

理論	分離頻率 \| Nyquist-Shannon採樣定理 \| 估算理論 \| 偵查理論

子體	音頻信號處理 \| 控制工程 \| 數字式圖像處理 \| 語言信息處理 \| 統計信號處理

技術	分離傅立葉變換 (DFT) \| 離散時間傅立葉變換 (DTFT) \| 衝動不變性 \| 雙線變換 \| Z變換, 先進Z變換

採樣	oversampling \| undersampling \| downsampling \| upsampling \| 混淆現象 \| 圖形保真過濾器 \| 採樣率 \| Nyquist率/頻率

The original article is from Wikipedia. To view the original article please click here.
Creative Commons Licence

Custom Search