Function in discrete mathematics
図 1: （連続）フーリエ変換 と離散フーリエ変換 の関係。 左: 連続関数（上）とそのフーリエ変換（下）。 中央左:元の関数の 周期的和 （上）。フーリエ変換（下）は、離散点を除いてゼロです。逆変換は、 フーリエ級数 と呼ばれる正弦波の和です。 中央右:元の関数が離散化（ ディラック コーム で乗算）されます（上）。そのフーリエ変換（下）は 、元の変換の 周期的和（ DTFT ）です。 右: DFT（下）は、連続 DTFT の離散サンプルを計算します。逆 DFT（上）は、元のサンプルの周期的和です。FFTアルゴリズム は DFT の 1 サイクルを計算し、その逆は DFT 逆の 1 サイクルです。 図2：フーリエ変換（左上）とその周期的和（DTFT）を左下隅に図示。右上（a）と右下（b）のスペクトル列は、それぞれ（a）s(t)の周期的和の1周期、（b）s(nT)列の周期的和の1周期から計算される。それぞれの式は、（a） フーリエ級数 積分 と（b） DFT 和 である。元の変換S(f)との類似性と比較的計算が容易なことから、DFT列を計算する動機となることが多い。 数学 において 、 離散フーリエ変換 ( DFT ) は、関数 の等間隔 サンプルの有限シーケンスを、 周波数 の複素数値関数である 離散時間フーリエ変換 ( DTFT ) の等間隔サンプルの同じ長さのシーケンスに変換する フーリエ変換の離散バージョンです。 DTFT がサンプリングされる間隔は、入力シーケンスの持続時間の逆数です。 [A] [1] 逆 DFT ( IDFT ) は、 DTFT サンプルを対応する DTFT 周波数で の複素 正弦 波 の係数として使用する フーリエ級数 です。元の入力シーケンスと同じサンプル値を持ちます。したがって、 DFT は元の入力シーケンスの 周波数領域 表現であると言われています。元のシーケンスが関数のゼロ以外の値すべてにまたがる場合、その DTFT は連続 (および周期的) であり、 DFT は 1 サイクルの離散サンプルを提供します。元のシーケンスが周期関数の 1 サイクルである場合、DFT は 1 つの DTFT サイクルのすべてのゼロ以外の値を提供します。
DFTは 多くの実用アプリケーションの フーリエ解析に利用されています。 [2] デジタル信号処理 において 、関数とは、 音波 の圧力 、 無線 信号、日々の 温度測定値など、時間とともに変化する任意の量または 信号 であり、有限の時間間隔（多くの場合、 ウィンドウ関数 [3] によって定義されます）にわたってサンプリングされます。 画像処理 において、サンプルは ラスター画像 の行または列に沿った ピクセルの値である場合があります。DFTは、 偏微分方程式を効率的に解くためにも、 畳み込み や大きな整数の 乗算などの他の演算を実行するために も使用されます。
有限量のデータを扱うため、 数値アルゴリズム や専用 ハードウェア によって コンピュータ に実装できます。これらの実装では通常、効率的な 高速フーリエ変換 （FFT）アルゴリズムが用いられます。 [4] そのため、「FFT」と「DFT」という用語はしばしば互換的に使用されます。現在のような用法になる前は、「FFT」という 頭字語は、曖昧な用語である「 有限フーリエ変換 」 にも使用されていた可能性があります。
意味 離散 フーリエ変換は、 N個の 複素数 の 列 を次のように定義される 別の複素数の列に 変換します。 { x n } := x 0 , x 1 , … , x N − 1 {\displaystyle \left\{\mathbf {x} _{n}\right\}:=x_{0},x_{1},\ldots ,x_{N-1}} { X k } := X 0 , X 1 , … , X N − 1 , {\displaystyle \left\{\mathbf {X} _{k}\right\}:=X_{0},X_{1},\ldots ,X_{N-1},}
離散フーリエ変換 X k = ∑ n = 0 N − 1 x n ⋅ e − i 2 π k N n {\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\cdot e^{-i2\pi {\tfrac {k}{N}}n}}
式1
注：この定義ではサンプリング間隔が省略されているため、周波数軸は無次元となり、振幅は相対スケールのみで表現されます。ただし、 FFT 実装を含むほとんどのソフトウェアライブラリでは、この相対形式が使用されています。
変換は、 または または のように、 記号 で表されることもあります 。 [B] F {\displaystyle {\mathcal {F}}} X = F { x } {\displaystyle \mathbf {X} ={\mathcal {F}}\left\{\mathbf {x} \right\}} F ( x ) {\displaystyle {\mathcal {F}}\left(\mathbf {x} \right)} F x {\displaystyle {\mathcal {F}}\mathbf {x} }
式1は 、次のようにさまざまな方法で解釈または導出できます。
これは離散周波数成分のみを含む周期的シーケンスの 離散時間フーリエ変換 （DTFT）を完全に記述します 。 [C] （ 周期的データでのDTFTの使用 ） N {\displaystyle N} また、有限長シーケンスの連続 DTFT の均一間隔のサンプルを提供することもできます。( § DTFT のサンプリング ) これは、 入力 シーケンス と周波数における複素正弦波 の 相互相関 です。したがって、これはその周波数の 整合フィルタ のように動作します。 x n {\displaystyle x_{n}} k N . {\textstyle {\frac {k}{N}}.} これはフーリエ級数 の係数の式の離散的な類似物である 。 C k = 1 P ∫ P x ( t ) e − i 2 π k P t d t . {\displaystyle C_{k}={\frac {1}{P}}\int _{P}x(t)e^{-i2\pi {\tfrac {k}{P}}t}\,dt.} 式1は 定義域外でも評価可能であり 、その拡張された数列は 周期的 である 。したがって、 ( が偶数の場合)や (が奇数の場合) といった他の添え字列が用いられることも あり、これは変換結果の左半分と右半分を入れ替えることに相当する。 [5] k ∈ [ 0 , N − 1 ] {\displaystyle k\in [0,N-1]} N {\displaystyle N} N {\displaystyle N} [ − N 2 , N 2 − 1 ] {\textstyle \left[-{\frac {N}{2}},{\frac {N}{2}}-1\right]} N {\displaystyle N} [ − N − 1 2 , N − 1 2 ] {\textstyle \left[-{\frac {N-1}{2}},{\frac {N-1}{2}}\right]} N {\displaystyle N}
逆変換は次のように与えられます。
逆変換 x n = 1 N ∑ k = 0 N − 1 X k ⋅ e i 2 π k N n {\displaystyle x_{n}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}\cdot e^{i2\pi {\tfrac {k}{N}}n}} 式2
式2 も -周期的です （指数nにおいて）。式2 において 、各 は 複素数であり、その極座標は 関数の複素正弦波成分の振幅と位相です （ 離散フーリエ級数 を参照）。正弦波の 周波数 はサンプルあたりサイクル です 。 N {\displaystyle N} X k {\displaystyle X_{k}} ( e i 2 π k N n ) {\displaystyle \left(e^{i2\pi {\tfrac {k}{N}}n}\right)} x n . {\displaystyle x_{n}.} k {\displaystyle k} N {\displaystyle N}
DFTとIDFT（ここでは1と ）を乗じる正規化係数と指数の符号は、最も一般的な 慣例 です。これらの慣例における唯一の実際の要件は、DFTとIDFTの指数が逆符号であることと、それらの正規化係数 の積が となることです。DFTとIDFTの両方で を正規化するという珍しい方法は、 変換ペアをユニタリにします。 1 N {\displaystyle {\tfrac {1}{N}}} 1 N . {\displaystyle {\tfrac {1}{N}}.} 1 N {\displaystyle {\sqrt {\tfrac {1}{N}}}}
サンプリング間隔を含むDFT DFT の標準定義を使用すると、 インデックスがに従ってサンプリング間隔に対応する場合には、サンプリング間隔 (またはサンプリング距離) が省略されます 。 Δ t {\displaystyle \Delta t} n Δ t = t {\displaystyle n\Delta t=t}
サンプリング間隔を含む連続フーリエ変換と一貫性のあるDFTを表現するために、サンプリング間隔は次のように明示的に含めることができる。
X k = Δ t ∑ n = 0 N − 1 x n ⋅ e − i 2 π k N n {\displaystyle X_{k}=\Delta t\sum _{n=0}^{N-1}x_{n}\cdot e^{-i2\pi {\tfrac {k}{N}}n}}
注: ほとんどのソフトウェア ライブラリでは、この形式は使用されず、対応する FFT 実装を含む相対形式が使用されます。
対応する逆変換は次のようになります。
x n = Δ f ∑ k = 0 N − 1 X k ⋅ e i 2 π k N n {\displaystyle x_{n}=\Delta f\sum _{k=0}^{N-1}X_{k}\cdot e^{i2\pi {\tfrac {k}{N}}n}}
ここで周波数間隔は です 。 Δ f = 1 Δ t N {\displaystyle \Delta f={\frac {1}{\Delta tN}}}
例 この例では、長さのシーケンスと入力ベクトル にDFTを適用する方法を示します。 N = 4 {\displaystyle N=4}
x = ( x 0 x 1 x 2 x 3 ) = ( 1 2 − i − i − 1 + 2 i ) . {\displaystyle \mathbf {x} ={\begin{pmatrix}x_{0}\\x_{1}\\x_{2}\\x_{3}\end{pmatrix}}={\begin{pmatrix}1\\2-i\\-i\\-1+2i\end{pmatrix}}.}
式1 を使用し てDFTを計算する x {\displaystyle \mathbf {x} }
X 0 = e − i 2 π 0 ⋅ 0 / 4 ⋅ 1 + e − i 2 π 0 ⋅ 1 / 4 ⋅ ( 2 − i ) + e − i 2 π 0 ⋅ 2 / 4 ⋅ ( − i ) + e − i 2 π 0 ⋅ 3 / 4 ⋅ ( − 1 + 2 i ) = 2 X 1 = e − i 2 π 1 ⋅ 0 / 4 ⋅ 1 + e − i 2 π 1 ⋅ 1 / 4 ⋅ ( 2 − i ) + e − i 2 π 1 ⋅ 2 / 4 ⋅ ( − i ) + e − i 2 π 1 ⋅ 3 / 4 ⋅ ( − 1 + 2 i ) = − 2 − 2 i X 2 = e − i 2 π 2 ⋅ 0 / 4 ⋅ 1 + e − i 2 π 2 ⋅ 1 / 4 ⋅ ( 2 − i ) + e − i 2 π 2 ⋅ 2 / 4 ⋅ ( − i ) + e − i 2 π 2 ⋅ 3 / 4 ⋅ ( − 1 + 2 i ) = − 2 i X 3 = e − i 2 π 3 ⋅ 0 / 4 ⋅ 1 + e − i 2 π 3 ⋅ 1 / 4 ⋅ ( 2 − i ) + e − i 2 π 3 ⋅ 2 / 4 ⋅ ( − i ) + e − i 2 π 3 ⋅ 3 / 4 ⋅ ( − 1 + 2 i ) = 4 + 4 i {\displaystyle {\begin{aligned}X_{0}&=e^{-i2\pi 0\cdot 0/4}\cdot 1+e^{-i2\pi 0\cdot 1/4}\cdot (2-i)+e^{-i2\pi 0\cdot 2/4}\cdot (-i)+e^{-i2\pi 0\cdot 3/4}\cdot (-1+2i)=2\\X_{1}&=e^{-i2\pi 1\cdot 0/4}\cdot 1+e^{-i2\pi 1\cdot 1/4}\cdot (2-i)+e^{-i2\pi 1\cdot 2/4}\cdot (-i)+e^{-i2\pi 1\cdot 3/4}\cdot (-1+2i)=-2-2i\\X_{2}&=e^{-i2\pi 2\cdot 0/4}\cdot 1+e^{-i2\pi 2\cdot 1/4}\cdot (2-i)+e^{-i2\pi 2\cdot 2/4}\cdot (-i)+e^{-i2\pi 2\cdot 3/4}\cdot (-1+2i)=-2i\\X_{3}&=e^{-i2\pi 3\cdot 0/4}\cdot 1+e^{-i2\pi 3\cdot 1/4}\cdot (2-i)+e^{-i2\pi 3\cdot 2/4}\cdot (-i)+e^{-i2\pi 3\cdot 3/4}\cdot (-1+2i)=4+4i\end{aligned}}}
結果的に X = ( X 0 X 1 X 2 X 3 ) = ( 2 − 2 − 2 i − 2 i 4 + 4 i ) . {\displaystyle \mathbf {X} ={\begin{pmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{pmatrix}}={\begin{pmatrix}2\\-2-2i\\-2i\\4+4i\end{pmatrix}}.}
プロパティ
直線性 DFT は線形変換です。つまり、 および の場合、任意の複素数 に対して次のようになります 。 F ( { x n } ) k = X k {\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}} F ( { y n } ) k = Y k {\displaystyle {\mathcal {F}}(\{y_{n}\})_{k}=Y_{k}} a , b {\displaystyle a,b}
F ( { a x n + b y n } ) k = a X k + b Y k {\displaystyle {\mathcal {F}}(\{ax_{n}+by_{n}\})_{k}=aX_{k}+bY_{k}}
時間と周波数の逆転 時間を逆転させる（つまり を に置き換える ）こと [D] は、 周波数を逆転させる（ つまり を に置き換える ）ことに相当する。 [6] : p.421 数学的には 、 が ベクトル xを表す場合、 n {\displaystyle n} N − n {\displaystyle N-n} x n {\displaystyle x_{n}} k {\displaystyle k} N − k {\displaystyle N-k} { x n } {\displaystyle \{x_{n}\}}
もし F ( { x n } ) k = X k {\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}} それから F ( { x N − n } ) k = X N − k {\displaystyle {\mathcal {F}}(\{x_{N-n}\})_{k}=X_{N-k}}
時間における活用 もし そうなら 。 [6] : p.423 F ( { x n } ) k = X k {\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}} F ( { x n ∗ } ) k = X N − k ∗ {\displaystyle {\mathcal {F}}(\{x_{n}^{*}\})_{k}=X_{N-k}^{*}}
実部と虚部 この表は、 時間領域におけるいくつかの数学的演算と、 周波数領域における DFT に対する対応する効果を示しています。 x n {\displaystyle x_{n}} X k {\displaystyle X_{k}}
財産 時間領域 x n {\displaystyle x_{n}} 周波数領域 X k {\displaystyle X_{k}} 時間の中の本当の部分 Re ( x n ) {\displaystyle \operatorname {Re} {\left(x_{n}\right)}} 1 2 ( X k + X N − k ∗ ) {\displaystyle {\frac {1}{2}}\left(X_{k}+X_{N-k}^{*}\right)} 時間における虚数部 Im ( x n ) {\displaystyle \operatorname {Im} {\left(x_{n}\right)}} 1 2 i ( X k − X N − k ∗ ) {\displaystyle {\frac {1}{2i}}\left(X_{k}-X_{N-k}^{*}\right)} 周波数の実部 1 2 ( x n + x N − n ∗ ) {\displaystyle {\frac {1}{2}}\left(x_{n}+x_{N-n}^{*}\right)} Re ( X k ) {\displaystyle \operatorname {Re} {\left(X_{k}\right)}} 周波数の虚数部 1 2 i ( x n − x N − n ∗ ) {\displaystyle {\frac {1}{2i}}\left(x_{n}-x_{N-n}^{*}\right)} Im ( X k ) {\displaystyle \operatorname {Im} {\left(X_{k}\right)}}
直交性 ベクトル は 、 に対して 、 N 次元複素ベクトル の集合上の 直交基底を形成します。 u k = [ e i 2 π N k n | n = 0 , 1 , … , N − 1 ] T {\displaystyle u_{k}=\left[\left.e^{{\frac {i2\pi }{N}}kn}\;\right|\;n=0,1,\ldots ,N-1\right]^{\mathsf {T}}} k = 0 , 1 , … , N − 1 {\displaystyle k=0,1,\ldots ,N-1}
u k T u k ′ ∗ = ∑ n = 0 N − 1 ( e i 2 π N k n ) ( e i 2 π N ( − k ′ ) n ) = ∑ n = 0 N − 1 e i 2 π N ( k − k ′ ) n = N δ k k ′ {\displaystyle u_{k}^{\mathsf {T}}u_{k'}^{*}=\sum _{n=0}^{N-1}\left(e^{{\frac {i2\pi }{N}}kn}\right)\left(e^{{\frac {i2\pi }{N}}(-k')n}\right)=\sum _{n=0}^{N-1}e^{{\frac {i2\pi }{N}}(k-k')n}=N~\delta _{kk'}} ここで 、 は クロネッカーのデルタ です。(最後のステップでは、 の場合には合計は自明です。つまり 、 は 1 + 1 + ⋯ = N であり、それ以外の場合には は明示的に合計してゼロを得ることができる 幾何級数 です 。) この直交条件は、DFT の定義から IDFT の式を導くために使用でき、以下のユニタリー性の特性と同等です。 δ k k ′ {\displaystyle \delta _{kk'}} k = k ′ {\displaystyle k=k'}
プランシュレルの定理とパーセヴァルの定理 および が それぞれ および の DFT である 場合 、パーセバルの定理は 次を述べています。 X k {\displaystyle X_{k}} Y k {\displaystyle Y_{k}} x n {\displaystyle x_{n}} y n {\displaystyle y_{n}}
∑ n = 0 N − 1 x n y n ∗ = 1 N ∑ k = 0 N − 1 X k Y k ∗ {\displaystyle \sum _{n=0}^{N-1}x_{n}y_{n}^{*}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}Y_{k}^{*}} ここで、星印は 複素共役 を表す。 プランシュレルの定理は パーセヴァルの定理の特殊な場合であり、次のように述べている。
∑ n = 0 N − 1 | x n | 2 = 1 N ∑ k = 0 N − 1 | X k | 2 . {\displaystyle \sum _{n=0}^{N-1}|x_{n}|^{2}={\frac {1}{N}}\sum _{k=0}^{N-1}|X_{k}|^{2}.} これらの定理は、以下のユニタリ条件とも同等です。
周期性 周期性は定義から直接示されます。
X k + N ≜ ∑ n = 0 N − 1 x n e − i 2 π N ( k + N ) n = ∑ n = 0 N − 1 x n e − i 2 π N k n e − i 2 π n ⏟ 1 = ∑ n = 0 N − 1 x n e − i 2 π N k n = X k . {\displaystyle X_{k+N}\ \triangleq \ \sum _{n=0}^{N-1}x_{n}e^{-{\frac {i2\pi }{N}}(k+N)n}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {i2\pi }{N}}kn}\underbrace {e^{-i2\pi n}} _{1}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {i2\pi }{N}}kn}=X_{k}.} 同様に、IDFT 式は の周期的拡張につながることが示されます 。 x n {\displaystyle x_{n}}
シフト定理 ある整数 mに対する 線形位相 を 乗じることは、 出力の 円周シフト に対応する 。 は に置き換えられる。ここで、添え字は N を法 として解釈される （つまり周期的）。同様に、 入力の 円周シフト は、出力 に 線形位相 を乗じることに対応する。数学的には、 が ベクトル xを表す 場合、 x n {\displaystyle x_{n}} e i 2 π N n m {\displaystyle e^{{\frac {i2\pi }{N}}nm}} X k {\displaystyle X_{k}} X k {\displaystyle X_{k}} X k − m {\displaystyle X_{k-m}} x n {\displaystyle x_{n}} X k {\displaystyle X_{k}} { x n } {\displaystyle \{x_{n}\}}
もし F ( { x n } ) k = X k {\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}} それから F ( { x n ⋅ e i 2 π N n m } ) k = X k − m {\displaystyle {\mathcal {F}}\left(\left\{x_{n}\cdot e^{{\frac {i2\pi }{N}}nm}\right\}\right)_{k}=X_{k-m}} そして F ( { x n − m } ) k = X k ⋅ e − i 2 π N k m {\displaystyle {\mathcal {F}}\left(\left\{x_{n-m}\right\}\right)_{k}=X_{k}\cdot e^{-{\frac {i2\pi }{N}}km}}
円畳み込み定理と相互相関定理
離散時間フーリエ変換 （DTFT）の 畳み込み 定理は 、2つのシーケンスの畳み込みは、個々の変換の積の逆変換として得られることを示しています。シーケンスの1つがN周期（ここでは と表記）である場合、重要な簡略化が起こります。これは、 が離散周波数でのみ非ゼロとなる ため（ DTFT § 周期データ を参照）、連続関数 との積も非ゼロとなるためです。これ により、 逆変換が大幅に簡略化されます。 y N , {\displaystyle y_{_{N}},} DTFT { y N } {\displaystyle \scriptstyle {\text{DTFT}}\displaystyle \{y_{_{N}}\}} DTFT { x } . {\displaystyle \scriptstyle {\text{DTFT}}\displaystyle \{x\}.}
x ∗ y N = D T F T − 1 [ D T F T { x } ⋅ D T F T { y N } ] = D F T − 1 [ D F T { x N } ⋅ D F T { y N } ] , {\displaystyle x*y_{_{N}}\ =\ \scriptstyle {\rm {DTFT}}^{-1}\displaystyle \left[\scriptstyle {\rm {DTFT}}\displaystyle \{x\}\cdot \scriptstyle {\rm {DTFT}}\displaystyle \{y_{_{N}}\}\right]\ =\ \scriptstyle {\rm {DFT}}^{-1}\displaystyle \left[\scriptstyle {\rm {DFT}}\displaystyle \{x_{_{N}}\}\cdot \scriptstyle {\rm {DFT}}\displaystyle \{y_{_{N}}\}\right],} ここで、 は次の 数列 の 周期的な和 である 。 x N {\displaystyle x_{_{N}}} x {\displaystyle x} ( x N ) n ≜ ∑ m = − ∞ ∞ x ( n − m N ) . {\displaystyle (x_{_{N}})_{n}\ \triangleq \sum _{m=-\infty }^{\infty }x_{(n-mN)}.}
通常、DFTと逆DFTの和は領域 上で行われます 。これらのDFTを および と定義すると 、 結果は となります 。 [ 0 , N − 1 ] {\displaystyle [0,N-1]} X {\displaystyle X} Y {\displaystyle Y}
( x ∗ y N ) n ≜ ∑ ℓ = − ∞ ∞ x ℓ ⋅ ( y N ) n − ℓ = F − 1 ⏟ D F T − 1 { X ⋅ Y } n . {\displaystyle (x*y_{_{N}})_{n}\triangleq \sum _{\ell =-\infty }^{\infty }x_{\ell }\cdot (y_{_{N}})_{n-\ell }=\underbrace {{\mathcal {F}}^{-1}} _{\rm {DFT^{-1}}}\left\{X\cdot Y\right\}_{n}.} 実際には、 シーケンスの長さは通常 N 以下であり、 長さ N のシーケンスの周期的な拡張であり、 円関数 として表現することもできます 。 x {\displaystyle x} y N {\displaystyle y_{_{N}}} y {\displaystyle y}
( y N ) n = ∑ p = − ∞ ∞ y ( n − p N ) = y ( n mod N ) , n ∈ Z . {\displaystyle (y_{_{N}})_{n}=\sum _{p=-\infty }^{\infty }y_{(n-pN)}=y_{(n\operatorname {mod} N)},\quad n\in \mathbb {Z} .} 畳み込みは次のように記述できます 。
F − 1 { X ⋅ Y } n = ∑ ℓ = 0 N − 1 x ℓ ⋅ y ( n − ℓ ) mod N {\displaystyle {\mathcal {F}}^{-1}\left\{X\cdot Y\right\}_{n}=\sum _{\ell =0}^{N-1}x_{\ell }\cdot y_{_{(n-\ell )\operatorname {mod} N}}} これは、およびの 巡回 畳み込み として解釈される [7] [8]。これは、線形畳み込みを効率的に計算するためによく使用されます。（ 巡回畳み込み 、 高速畳み込みアルゴリズム 、および オーバーラップセーブを 参照 ） x {\displaystyle x} y . {\displaystyle y.}
同様に、 と の 相互相関は 次のように与えられます 。 x {\displaystyle x} y N {\displaystyle y_{_{N}}}
( x ⋆ y N ) n ≜ ∑ ℓ = − ∞ ∞ x ℓ ∗ ⋅ ( y N ) n + ℓ = F − 1 { X ∗ ⋅ Y } n . {\displaystyle (x\star y_{_{N}})_{n}\triangleq \sum _{\ell =-\infty }^{\infty }x_{\ell }^{*}\cdot (y_{_{N}})_{n+\ell }={\mathcal {F}}^{-1}\left\{X^{*}\cdot Y\right\}_{n}.}
上で見たように、離散フーリエ変換は、畳み込みを成分ごとの積に変換するという基本的な性質を持っています。当然の疑問として、この変換がこの機能を持つ唯一の変換なのかどうかが挙げられます。畳み込みを点ごとの積に変換する任意の線形変換は、係数の順列を除いてDFTであることが示されています [9] [10] 。n個の要素の順列の数はn!個なので、畳み込みに関してDFTと同じ基本的な性質を持つ線形かつ可逆な写像は、正確にn!個存在します。
畳み込み定理の双対性 また、次のことも示せます 。
F { x ⋅ y } k ≜ ∑ n = 0 N − 1 x n ⋅ y n ⋅ e − i 2 π N k n {\displaystyle {\mathcal {F}}\left\{\mathbf {x\cdot y} \right\}_{k}\ \triangleq \sum _{n=0}^{N-1}x_{n}\cdot y_{n}\cdot e^{-i{\frac {2\pi }{N}}kn}} = 1 N ( X ∗ Y N ) k , {\displaystyle ={\frac {1}{N}}(\mathbf {X*Y_{N}} )_{k},} これは、と の循環畳み込みです 。 X {\displaystyle \mathbf {X} } Y {\displaystyle \mathbf {Y} }
三角関数の補間多項式 三角 関数の補間多項式
p ( t ) = { 1 N [ X 0 + X 1 e i 2 π t + ⋯ + X N 2 − 1 e i 2 π ( N 2 − 1 ) t + X N 2 cos ( N π t ) + X N 2 + 1 e − i 2 π ( N 2 − 1 ) t + ⋯ + X N − 1 e − i 2 π t ] N even 1 N [ X 0 + X 1 e i 2 π t + ⋯ + X N − 1 2 e i 2 π N − 1 2 t + X N + 1 2 e − i 2 π N − 1 2 t + ⋯ + X N − 1 e − i 2 π t ] N odd {\displaystyle p(t)={\begin{cases}\displaystyle {\frac {1}{N}}\left[{\begin{alignedat}{3}X_{0}+X_{1}e^{i2\pi t}+\cdots &+X_{{\frac {N}{2}}-1}e^{i2\pi {\big (}\!{\frac {N}{2}}-1\!{\big )}t}&\\&+X_{\frac {N}{2}}\cos(N\pi t)&\\&+X_{{\frac {N}{2}}+1}e^{-i2\pi {\big (}\!{\frac {N}{2}}-1\!{\big )}t}&+\cdots +X_{N-1}e^{-i2\pi t}\end{alignedat}}\right]&N{\text{ even}}\\\displaystyle {\frac {1}{N}}\left[{\begin{alignedat}{3}X_{0}+X_{1}e^{i2\pi t}+\cdots &+X_{\frac {N-1}{2}}e^{i2\pi {\frac {N-1}{2}}t}&\\&+X_{\frac {N+1}{2}}e^{-i2\pi {\frac {N-1}{2}}t}&+\cdots +X_{N-1}e^{-i2\pi t}\end{alignedat}}\right]&N{\text{ odd}}\end{cases}}} ここで、係数 X k は上記のx n のDFTによって与えられ、 の 補間特性を満たします 。 p ( n / N ) = x n {\displaystyle p(n/N)=x_{n}} n = 0 , … , N − 1 {\displaystyle n=0,\ldots ,N-1}
偶数 N の場合、 ナイキスト成分 が特別に処理されることに注意してください。 X N / 2 N cos ( N π t ) {\textstyle {\frac {X_{N/2}}{N}}\cos(N\pi t)}
この補間は 一意ではありません 。エイリアシングとは、複素正弦波の任意の周波数に N を加算（例えば に変更 ）しても補間特性は変化せず、点 間の値が 異なること を意味します。しかし、上記の選択は2つの有用な特性を持つため、典型的です。まず、この補間は、周波数の振幅が可能な限り小さい正弦波で構成されます。つまり、補間は 帯域制限されます 。次に、 が 実数である場合、 も実数です。 e − i t {\displaystyle e^{-it}} e i ( N − 1 ) t {\displaystyle e^{i(N-1)t}} x n {\displaystyle x_{n}} x n {\displaystyle x_{n}} p ( t ) {\displaystyle p(t)}
対照的に、最も分かりやすい三角関数の補間多項式は、周波数範囲が0から （上記のようにほぼ0から 10までではなく ）のものであり、これは逆DFT式に似ています。この補間は 傾きを最小化せ ず 、実数 に対しては一般に実数値では ありません 。そのため、この補間多項式の使用はよくある誤りです。 N − 1 {\displaystyle N-1} − N / 2 {\displaystyle -N/2} + N / 2 {\displaystyle +N/2} x n {\displaystyle x_{n}}
ユニタリーDFT DFTを別の視点から見ると、上記の議論において、DFTは 1867年に シルベスターによって導入された ヴァンデルモンド行列で ある DFT 行列として表現できることに注目する。
F = [ ω N 0 ⋅ 0 ω N 0 ⋅ 1 ⋯ ω N 0 ⋅ ( N − 1 ) ω N 1 ⋅ 0 ω N 1 ⋅ 1 ⋯ ω N 1 ⋅ ( N − 1 ) ⋮ ⋮ ⋱ ⋮ ω N ( N − 1 ) ⋅ 0 ω N ( N − 1 ) ⋅ 1 ⋯ ω N ( N − 1 ) ⋅ ( N − 1 ) ] {\displaystyle \mathbf {F} ={\begin{bmatrix}\omega _{N}^{0\cdot 0}&\omega _{N}^{0\cdot 1}&\cdots &\omega _{N}^{0\cdot (N-1)}\\\omega _{N}^{1\cdot 0}&\omega _{N}^{1\cdot 1}&\cdots &\omega _{N}^{1\cdot (N-1)}\\\vdots &\vdots &\ddots &\vdots \\\omega _{N}^{(N-1)\cdot 0}&\omega _{N}^{(N-1)\cdot 1}&\cdots &\omega _{N}^{(N-1)\cdot (N-1)}\\\end{bmatrix}}} ここで 、 は原始 N 乗根 です。 ω N = e − i 2 π / N {\displaystyle \omega _{N}=e^{-i2\pi /N}}
例えば 、、、 および N = 2 {\displaystyle N=2} ω N = e − i π = − 1 {\displaystyle \omega _{N}=e^{-i\pi }=-1}
F = [ 1 1 1 − 1 ] , {\displaystyle \mathbf {F} ={\begin{bmatrix}1&1\\1&-1\\\end{bmatrix}},} （これは アダマール行列 ）または 離散フーリエ変換 § 上の例のように 、 および N = 4 {\displaystyle N=4} ω N = e − i π / 2 = − i {\displaystyle \omega _{N}=e^{-i\pi /2}=-i}
F = [ 1 1 1 1 1 − i − 1 i 1 − 1 1 − 1 1 i − 1 − i ] . {\displaystyle \mathbf {F} ={\begin{bmatrix}1&1&1&1\\1&-i&-1&i\\1&-1&1&-1\\1&i&-1&-i\\\end{bmatrix}}.} 逆変換は上記の行列の逆行列で与えられ、
F − 1 = 1 N F ∗ {\displaystyle \mathbf {F} ^{-1}={\frac {1}{N}}\mathbf {F} ^{*}} ユニタリ 正規化定数 を使用すると 、DFT は ユニタリ変換 になり、ユニタリ行列によって定義されます。 1 / N {\textstyle 1/{\sqrt {N}}}
U = 1 N F U − 1 = U ∗ | det ( U ) | = 1 {\displaystyle {\begin{aligned}\mathbf {U} &={\frac {1}{\sqrt {N}}}\mathbf {F} \\\mathbf {U} ^{-1}&=\mathbf {U} ^{*}\\\left|\det(\mathbf {U} )\right|&=1\end{aligned}}} ここでは 行列式 関数です 。行列式は固有値の積であり、固有値は常に または となります。実ベクトル空間では、ユニタリ変換は座標系の単純な剛体回転と考えることができ、剛体回転のすべての特性はユニタリDFTに見出すことができます。 det ( ) {\displaystyle \det()} ± 1 {\displaystyle \pm 1} ± i {\displaystyle \pm i}
DFT の直交性は、現在では 直交性条件 ( 単位根 で説明されているように数学の多くの分野で発生する ) として表現されます。
∑ m = 0 N − 1 U k m U m n ∗ = δ k n {\displaystyle \sum _{m=0}^{N-1}U_{km}U_{mn}^{*}=\delta _{kn}} X がベクトル x のユニタリDFTとして定義されている場合 、
X k = ∑ n = 0 N − 1 U k n x n {\displaystyle X_{k}=\sum _{n=0}^{N-1}U_{kn}x_{n}} パーセバル の定理は 次のように表される。
∑ n = 0 N − 1 x n y n ∗ = ∑ k = 0 N − 1 X k Y k ∗ {\displaystyle \sum _{n=0}^{N-1}x_{n}y_{n}^{*}=\sum _{k=0}^{N-1}X_{k}Y_{k}^{*}} DFTを、ベクトルの成分を新しい座標系で指定するだけの座標変換と見なすと、上記は、 2つのベクトルの 内積 がユニタリDFT変換において保存されるという単なる記述に過ぎません。特殊なケースでは 、これはベクトルの長さも保存されることを意味します。これは プランシュレルの定理 に他なりません。 x = y {\displaystyle \mathbf {x} =\mathbf {y} }
∑ n = 0 N − 1 | x n | 2 = ∑ k = 0 N − 1 | X k | 2 {\displaystyle \sum _{n=0}^{N-1}|x_{n}|^{2}=\sum _{k=0}^{N-1}|X_{k}|^{2}} 循環畳み込み定理の結果として、DFT 行列 F は任意の 循環行列 を対角化します。
逆DFTをDFTで表現する DFTの有用な特性の一つは、いくつかのよく知られた「トリック」を用いることで、逆DFTを（順方向）DFTを用いて簡単に表現できることです。（例えば、計算においては、まず一方の変換方向に対応する高速フーリエ変換のみを実装し、それからもう一方の変換方向を最初の変換方向から取得すると便利な場合がよくあります。）
まず、入力の1つを除いてすべてを逆にすることで逆DFTを計算できます（Duhamel et al. 、1988）。
F − 1 ( { x n } ) = 1 N F ( { x N − n } ) {\displaystyle {\mathcal {F}}^{-1}(\{x_{n}\})={\frac {1}{N}}{\mathcal {F}}(\{x_{N-n}\})} (通常通り、下付き文字は N を法として 解釈されます。したがって、 の場合 、 となります 。) n = 0 {\displaystyle n=0} x N − 0 = x 0 {\displaystyle x_{N-0}=x_{0}}
2番目に、入力と出力を組み合わせることもできます。
F − 1 ( x ) = 1 N F ( x ∗ ) ∗ {\displaystyle {\mathcal {F}}^{-1}(\mathbf {x} )={\frac {1}{N}}{\mathcal {F}}\left(\mathbf {x} ^{*}\right)^{*}} 3つ目に、この共役トリックの変種として、実部と虚部を入れ替える方法があります。これはデータ値を変更する必要がないため、好まれる場合もあります（コンピュータでは ポインタを 変更するだけで実行できます）。を実部と虚部を入れ替えた と定義します。 つまり、 のときは です 。同様に、 は と等しくなります 。そして、 swap ( x n ) {\textstyle \operatorname {swap} (x_{n})} x n {\displaystyle x_{n}} x n = a + b i {\displaystyle x_{n}=a+bi} swap ( x n ) {\textstyle \operatorname {swap} (x_{n})} b + a i {\displaystyle b+ai} swap ( x n ) {\textstyle \operatorname {swap} (x_{n})} i x n ∗ {\displaystyle ix_{n}^{*}}
F − 1 ( x ) = 1 N swap ( F ( swap ( x ) ) ) {\displaystyle {\mathcal {F}}^{-1}(\mathbf {x} )={\frac {1}{N}}\operatorname {swap} ({\mathcal {F}}(\operatorname {swap} (\mathbf {x} )))} つまり、逆変換は、正規化まで、入力と出力の両方で実部と虚部が交換された順方向変換と同じです (Duhamel et al. 、1988)。
共役トリックは、DFTに密接に関連する、つまり逆変換である新しい変換を定義するためにも使用できます 。 特に、 は明らかに逆変換です： 。密接に関連する逆変換（ の係数による ）は です。これは、 の係数が 2 を打ち消す ためです。実数入力 の場合 、 の実部は 離散ハートレー変換 に 他なりません 。これも逆変換です。 T ( x ) = F ( x ∗ ) / N {\displaystyle T(\mathbf {x} )={\mathcal {F}}\left(\mathbf {x} ^{*}\right)/{\sqrt {N}}} T ( T ( x ) ) = x {\displaystyle T(T(\mathbf {x} ))=\mathbf {x} } 1 + i 2 {\textstyle {\frac {1+i}{\sqrt {2}}}} H ( x ) = F ( ( 1 + i ) x ∗ ) / 2 N {\displaystyle H(\mathbf {x} )={\mathcal {F}}\left((1+i)\mathbf {x} ^{*}\right)/{\sqrt {2N}}} ( 1 + i ) {\displaystyle (1+i)} H ( H ( x ) ) {\displaystyle H(H(\mathbf {x} ))} x {\displaystyle \mathbf {x} } H ( x ) {\displaystyle H(\mathbf {x} )}
固有値と固有ベクトル DFT行列の固有値は単純でよく知られているが、 固有ベクトル は 複雑 で一意ではなく、現在も研究が続けられている。明示的な公式は、かなりの数論的知識を伴って与えられている。 [11]
長さN のDFTについて上で定義した ユニタリ形式を考える 。 U {\displaystyle \mathbf {U} }
U m , n = 1 N ω N ( m − 1 ) ( n − 1 ) = 1 N e − i 2 π N ( m − 1 ) ( n − 1 ) . {\displaystyle \mathbf {U} _{m,n}={\frac {1}{\sqrt {N}}}\omega _{N}^{(m-1)(n-1)}={\frac {1}{\sqrt {N}}}e^{-{\frac {i2\pi }{N}}(m-1)(n-1)}.} この行列は 行列多項式 方程式を満たします。
U 4 = I . {\displaystyle \mathbf {U} ^{4}=\mathbf {I} .} これは上記の逆行列の性質から分かります。2 回演算すると元のデータが逆順で返されますが、 4回演算すると元のデータに戻り、 単位行列 となります。これは、固有値が 以下の式を満たすことを意味します。 U {\displaystyle \mathbf {U} } U {\displaystyle \mathbf {U} } λ {\displaystyle \lambda }
λ 4 = 1. {\displaystyle \lambda ^{4}=1.} したがって、 の固有値は の 4 乗根 、つまり +1、-1、+ i 、または - i です。 U {\displaystyle \mathbf {U} } λ {\displaystyle \lambda }
この行列 には4つの異なる固有値しかないため、それらは 重複度 を持ちます。重複度は、各固有値に対応する 線形独立な 固有ベクトルの数を表します。（ N個 の独立な固有ベクトルがあり 、ユニタリ行列に 欠陥 が存在する ことはありません。） N × N {\displaystyle N\times N}
これらの多重度問題はマクレランとパークス（1972）によって解決されましたが、後に ガウス（ディキンソンとステイグリッツ、1982）によって解決された問題と等価であることが示されました。多重度は Nの4 を法とする 値に依存し 、以下の表で与えられます。
変換サイズN の関数としての ユニタリ DFT 行列 Uの固有値 λ の多重度 (整数 m に関して )。 サイズ N λ = +1 λ = −1 λ = − i λ = + i 4 メートル m + 1 メートル メートル メートル − 1 4 メートル +1 m + 1 メートル メートル メートル 4 メートル +2 m + 1 m + 1 メートル メートル 4 メートル +3 m + 1 m + 1 m + 1 メートル
言い換えると、 の 特性多項式 は次のようになります。 U {\displaystyle \mathbf {U} }
det ( λ I − U ) = ( λ − 1 ) ⌊ N + 4 4 ⌋ ( λ + 1 ) ⌊ N + 2 4 ⌋ ( λ + i ) ⌊ N + 1 4 ⌋ ( λ − i ) ⌊ N − 1 4 ⌋ . {\displaystyle \det(\lambda I-\mathbf {U} )=(\lambda -1)^{\left\lfloor {\tfrac {N+4}{4}}\right\rfloor }(\lambda +1)^{\left\lfloor {\tfrac {N+2}{4}}\right\rfloor }(\lambda +i)^{\left\lfloor {\tfrac {N+1}{4}}\right\rfloor }(\lambda -i)^{\left\lfloor {\tfrac {N-1}{4}}\right\rfloor }.} 一般固有ベクトルに対する単純な解析公式は知られていない。さらに、同じ固有値に対する固有ベクトルの任意の線形結合は、その固有値の固有ベクトルでもあるため、固有ベクトルは一意ではない。様々な研究者が、直交 性 などの有用な性質を満たし、「単純な」形となるように選択された様々な固有ベクトルを提案してきた（例：McClellan and Parks, 1972; Dickinson and Steiglitz, 1982; Grünbaum, 1982; Atakishiyev and Wolf, 1997; Candan et al. , 2000; Hanna et al. , 2004; Gurevich and Hadani, 2008）。
固有値に対するDFT固有ベクトルを構築する一つの方法は、 演算子の線形結合に基づくものである: [12] [13] [14] λ {\displaystyle \lambda }
P λ = 1 4 ( I + λ − 1 U + λ − 2 U 2 + λ − 3 U 3 ) {\displaystyle {\mathcal {P}}_{\lambda }={\frac {1}{4}}\left(\mathbf {I} +\lambda ^{-1}\mathbf {U} +\lambda ^{-2}\mathbf {U} ^{2}+\lambda ^{-3}\mathbf {U} ^{3}\right)}
任意のベクトル に対して 、ベクトル は 次を満たします。 v {\displaystyle \mathbf {v} } u ( λ ) = P λ v {\displaystyle \mathbf {u} (\lambda )={\mathcal {P}}_{\lambda }\mathbf {v} }
U u ( λ ) = λ u ( λ ) {\displaystyle {\textbf {U}}\mathbf {u} (\lambda )=\lambda \mathbf {u} (\lambda )}
したがって、ベクトル は、実際にはDFT行列の固有ベクトルである 。演算子は、 ベクトルを、の各値に対して直交する部分空間に投影する 。 [13] つまり、2つの固有ベクトル、 およびに対して、 次式が成り立つ。 u ( λ ) {\displaystyle \mathbf {u} (\lambda )} U {\displaystyle \mathbf {U} } P λ {\displaystyle {\mathcal {P}}_{\lambda }} λ {\displaystyle \lambda } u ( λ ) = P λ v {\displaystyle \mathbf {u} (\lambda )={\mathcal {P}}_{\lambda }\mathbf {v} } u ′ ( λ ′ ) = P λ ′ v ′ {\displaystyle \mathbf {u} '(\lambda ')={\mathcal {P}}_{\lambda '}\mathbf {v} '}
u † ( λ ) u ′ ( λ ′ ) = δ λ λ ′ u † ( λ ) v ′ {\displaystyle \mathbf {u} ^{\dagger }(\lambda )\mathbf {u} '(\lambda ')=\delta _{\lambda \lambda '}\mathbf {u} ^{\dagger }(\lambda )\mathbf {v} '}
しかし、一般に、射影演算子法では、1つの部分空間内では直交する固有ベクトルは生成されない。 [14] 演算子は 、列が の固有ベクトルである行列とみなすことができるが、それらは直交ではない。 次元空間 に張る ベクトルの集合（ここで は固有値 の重複度）を選択して、 固有値 への 固有ベクトルの集合を生成する場合 、 の相互直交性は保証されない。しかし、 に直交化アルゴリズム （例えば グラム・シュミット過程 ）をさらに適用することで、直交集合を得ることができる。 [ 15] P λ {\displaystyle {\mathcal {P}}_{\lambda }} U {\displaystyle \mathbf {U} } { v n } n = 1 , … , N λ {\displaystyle \{\mathbf {v} _{n}\}_{n=1,\dots ,N_{\lambda }}} N λ {\displaystyle N_{\lambda }} N λ {\displaystyle N_{\lambda }} λ {\displaystyle \lambda } { u n ( λ ) = P λ v n } n = 1 , … , N λ {\displaystyle \{\mathbf {u} _{n}(\lambda )={\mathcal {P}}_{\lambda }\mathbf {v} _{n}\}_{n=1,\dots ,N_{\lambda }}} λ {\displaystyle \lambda } u n ( λ ) {\displaystyle \mathbf {u} _{n}(\lambda )} { u n ( λ ) } n = 1 , … , N λ {\displaystyle \{\mathbf {u} _{n}(\lambda )\}_{n=1,\dots ,N_{\lambda }}}
DFT固有ベクトルを得る最も簡単な方法は、連続 フーリエ変換 の固有関数を離散化することです。その中で最も有名なのは ガウス関数 です。関数の 周期的な和 は周波数スペクトルの離散化を意味し、離散化はスペクトルの周期的な和を意味するため、離散化され周期的に和されたガウス関数は、離散変換の固有ベクトルを生成します。
F ( m ) = ∑ k ∈ Z exp ( − π ⋅ ( m + N ⋅ k ) 2 N ) . {\displaystyle F(m)=\sum _{k\in \mathbb {Z} }\exp \left(-{\frac {\pi \cdot (m+N\cdot k)^{2}}{N}}\right).} この級数の閉じた形式表現はヤコビ・シータ関数 で次のように 表される。
F ( m ) = 1 N ϑ 3 ( π m N , exp ( − π N ) ) . {\displaystyle F(m)={\frac {1}{\sqrt {N}}}\vartheta _{3}\left({\frac {\pi m}{N}},\exp \left(-{\frac {\pi }{N}}\right)\right).} 特別なDFT周期N に対する他のいくつかの単純な閉形式の解析的固有ベクトルが 発見されました（Kong、2008およびCasper-Yakimov、2024）。
DFT 周期 N = 2 L + 1 = 4 K + 1（ K は整数）の場合、DFT の固有ベクトルは次のようになります。
F ( m ) = ∏ s = K + 1 L [ cos ( 2 π N m ) − cos ( 2 π N s ) ] {\displaystyle F(m)=\prod _{s=K+1}^{L}\left[\cos \left({\frac {2\pi }{N}}m\right)-\cos \left({\frac {2\pi }{N}}s\right)\right]} DFT周期 N = 2 L = 4 K （ K は整数）の場合、DFTの固有ベクトルは次のようになります 。
F ( m ) = sin ( 2 π N m ) ∏ s = K + 1 L − 1 [ cos ( 2 π N m ) − cos ( 2 π N s ) ] {\displaystyle F(m)=\sin \left({\frac {2\pi }{N}}m\right)\prod _{s=K+1}^{L-1}\left[\cos \left({\frac {2\pi }{N}}m\right)-\cos \left({\frac {2\pi }{N}}s\right)\right]} F ( m ) = cos ( π N m ) ∏ s = K + 1 3 K − 1 sin ( π ( s − m ) N ) {\displaystyle F(m)=\cos \left({\frac {\pi }{N}}m\right)\prod _{s=K+1}^{3K-1}\sin \left({\frac {\pi (s-m)}{N}}\right)} DFT 周期 N = 4 K - 1（ K は整数）の場合、DFT の固有ベクトルは次のようになります。
F ( m ) = sin ( 2 π N m ) ∏ s = K + 1 3 K − 2 sin ( π ( s − m ) N ) {\displaystyle F(m)=\sin \left({\frac {2\pi }{N}}m\right)\prod _{s=K+1}^{3K-2}\sin \left({\frac {\pi (s-m)}{N}}\right)} F ( m ) = ( cos ( 2 π N m ) − cos ( 2 π N K ) ± sin ( 2 π N K ) ) ∏ s = K + 1 3 K − 2 sin ( π ( s − m ) N ) {\displaystyle F(m)=\left(\cos \left({\frac {2\pi }{N}}m\right)-\cos \left({\frac {2\pi }{N}}K\right)\pm \sin \left({\frac {2\pi }{N}}K\right)\right)\prod _{s=K+1}^{3K-2}\sin \left({\frac {\pi (s-m)}{N}}\right)} DFT行列の固有ベクトルの選択は、近年、 分数フーリエ変換 の離散類似物を定義する上で重要になっています。DFT行列は、固有値を指数化することで分数べき乗をとることができます（例：Rubio and Santhanam, 2005）。 連続フーリエ変換 の場合、自然な直交固有関数は エルミート関数であるため、 クラフチュク多項式 （Atakishiyev and Wolf, 1997）など、これらの様々な離散類似物がDFTの固有ベクトルとして用いられてきました 。しかしながら、分数離散フーリエ変換を定義するための「最適な」固有ベクトルの選択については、依然として未解決の問題です。
不確定性原理
確率的不確定性原理 確率変数 X k が
∑ n = 0 N − 1 | X n | 2 = 1 , {\displaystyle \sum _{n=0}^{N-1}|X_{n}|^{2}=1,} それから
P n = | X n | 2 {\displaystyle P_{n}=|X_{n}|^{2}} は、 n の離散 確率質量関数 を表すものと考えられる 。この関数は、変換された変数から構築された関連する確率質量関数を持つ。
Q m = N | x m | 2 . {\displaystyle Q_{m}=N|x_{m}|^{2}.} 連続関数との場合 、 ハイゼンベルク の不確定性原理 によれば、 P ( x ) {\displaystyle P(x)} Q ( k ) {\displaystyle Q(k)}
D 0 ( X ) D 0 ( x ) ≥ 1 16 π 2 {\displaystyle D_{0}(X)D_{0}(x)\geq {\frac {1}{16\pi ^{2}}}} ここで 、およびはそれぞれ 、および の分散であり、適切に正規化された ガウス分布 の場合に等式が達成される 。分散はDFTに対しても同様に定義できるが、不確実性はシフト不変ではないため、同様の不確定性原理は有用ではない。それでも、マッサーとスピンデルによって意味のある不確定性原理が導入されている。 [16] D 0 ( X ) {\displaystyle D_{0}(X)} D 0 ( x ) {\displaystyle D_{0}(x)} | X | 2 {\displaystyle |X|^{2}} | x | 2 {\displaystyle |x|^{2}}
しかし、ヒルシュマンの エントロピー不確定性原理 は、DFTの場合に有用な類似物を持つ。 [17] ヒルシュマンの不確定性原理は、2つの確率関数の シャノンエントロピー によって表現される。
離散的な場合、シャノンエントロピーは次のように定義される。
H ( X ) = − ∑ n = 0 N − 1 P n ln P n {\displaystyle H(X)=-\sum _{n=0}^{N-1}P_{n}\ln P_{n}} そして
H ( x ) = − ∑ m = 0 N − 1 Q m ln Q m , {\displaystyle H(x)=-\sum _{m=0}^{N-1}Q_{m}\ln Q_{m},} そして エントロピー的不確定性 原理は [17]
H ( X ) + H ( x ) ≥ ln ( N ) . {\displaystyle H(X)+H(x)\geq \ln(N).} は、周期 の クロネッカーコム を適切に正規化した の平行移動と変調に等しい に対して等式が得られる。 ここで は の任意の正確な整数約数である 。確率質量関数は、 周期 の クロネッカーコム を適切に平行移動させたものに比例する 。 [17] P n {\displaystyle P_{n}} A {\displaystyle A} A {\displaystyle A} N {\displaystyle N} Q m {\displaystyle Q_{m}} B = N / A {\displaystyle B=N/A}
決定論的不確定性原理 信号のスパース性（または非ゼロ係数の数）を用いた、よく知られた決定論的不確定性原理もある。 [18] とを、 それぞれ 時間系列と周波数系列の非ゼロ要素の数とする 。 すると、 ‖ x ‖ 0 {\displaystyle \left\|x\right\|_{0}} ‖ X ‖ 0 {\displaystyle \left\|X\right\|_{0}} x 0 , x 1 , … , x N − 1 {\displaystyle x_{0},x_{1},\ldots ,x_{N-1}} X 0 , X 1 , … , X N − 1 {\displaystyle X_{0},X_{1},\ldots ,X_{N-1}}
N ≤ ‖ x ‖ 0 ⋅ ‖ X ‖ 0 . {\displaystyle N\leq \left\|x\right\|_{0}\cdot \left\|X\right\|_{0}.} 算術平均と幾何平均の不等式 から直接導かれる帰結として 、 も成り立ちます 。これらの不確定性原理は、特定の「ピケットフェンス」シーケンス（離散インパルス列）に対して厳密に適用できることが示されており、信号回復アプリケーションにおいて実用的に使用されています。 [18] 2 N ≤ ‖ x ‖ 0 + ‖ X ‖ 0 {\displaystyle 2{\sqrt {N}}\leq \left\|x\right\|_{0}+\left\|X\right\|_{0}}
加法的な不確定性原理 加法的な不確定性原理は、信号がどの程度スパースであるかを、信号変換の非ゼロ要素の加法的なエネルギーの観点から定量化する。 [19] より具体的には、 との場合 、2つの加法的な不確定性原理は次のように述べている。 E = { i ∈ { 0 , 1 , . . . , N − 1 } | x i ≠ 0 } {\displaystyle E=\{i\in \{0,1,...,N-1\}\;|\;x_{i}\neq 0\}} F = { i ∈ { 0 , 1 , . . . , N − 1 } | X i ≠ 0 } {\displaystyle F=\{i\in \{0,1,...,N-1\}\;|\;X_{i}\neq 0\}}
N ≤ Λ ( E ) 1 3 ⋅ ‖ X ‖ 0 & N ≤ Λ ( F ) 1 3 ⋅ ‖ x ‖ 0 , {\displaystyle N\leq \Lambda (E)^{\frac {1}{3}}\cdot \left\|X\right\|_{0}\;\;\;\;\&\;\;\;\;N\leq \Lambda (F)^{\frac {1}{3}}\cdot \left\|x\right\|_{0},} N ≤ ( max U ⊆ E { Λ ( U ) | U | 2 } ) ⋅ ‖ X ‖ 0 & N ≤ ( max U ⊆ F { Λ ( U ) | U | 2 } ) ⋅ ‖ x ‖ 0 . {\displaystyle N\leq \left(\max _{U\subseteq E}\left\{{\frac {\Lambda (U)}{|U|^{2}}}\right\}\right)\cdot \left\|X\right\|_{0}\;\;\;\;\&\;\;\;\;N\leq \left(\max _{U\subseteq F}\left\{{\frac {\Lambda (U)}{|U|^{2}}}\right\}\right)\cdot \left\|x\right\|_{0}.} ここで、集合の加法エネルギー は定義され、 と表記されます。 加法的な組合せ論 では 、 と のランダムな部分集合はしばしば低い加法エネルギーを持つこと がよく知られています 。したがって、加法的な不確定性原理のどちらのバリエーションも、前述の決定論的な不確定性原理よりも強く、 と の両方の加法エネルギーが 最大となる場合、すなわち と のときのみ、 が成立します 。 A ⊆ { 0 , 1 , 2 , . . . , N − 1 } {\displaystyle A\subseteq \{0,1,2,...,N-1\}} Λ ( A ) = | { ( x 1 , x 2 , y 1 , y 2 ) ∈ A 4 | x 1 + x 2 ≡ y 1 + y 2 mod N } | . {\displaystyle \Lambda (A)=\left|\{(x_{1},x_{2},y_{1},y_{2})\in A^{4}\;|\;x_{1}+x_{2}\equiv y_{1}+y_{2}\mod N\}\right|.} 2 | A | 2 − | A | ≤ Λ ( A ) ≤ | A | 3 , {\displaystyle 2|A|^{2}-|A|\leq \Lambda (A)\leq |A|^{3},} { 0 , 1 , . . . , N − 1 } {\displaystyle \{0,1,...,N-1\}} E {\displaystyle E} F {\displaystyle F} Λ ( E ) = | E | 3 {\displaystyle \Lambda (E)=|E|^{3}} Λ ( F ) = | F | 3 {\displaystyle \Lambda (F)=|F|^{3}}
実信号と純虚信号のDFT 実際のアプリケーションではよくあるように、が実数 である 場合 、 DFT は 対称 でも あります 。 x 0 , … , x N − 1 {\displaystyle x_{0},\ldots ,x_{N-1}} X 0 , … , X N − 1 {\displaystyle X_{0},\ldots ,X_{N-1}} x n ∈ R ∀ n ∈ { 0 , … , N − 1 } ⟹ X k = X − k mod N ∗ ∀ k ∈ { 0 , … , N − 1 } {\displaystyle x_{n}\in \mathbb {R} \quad \forall n\in \{0,\ldots ,N-1\}\implies X_{k}=X_{-k\mod N}^{*}\quad \forall k\in \{0,\ldots ,N-1\}} ここで、 は 複素共役 を表します 。 X ∗ {\displaystyle X^{*}\,} したがって、 と は偶数 で 実数値であり、 DFT の残りの部分は 複素数だけで完全に指定されます。 N {\displaystyle N} X 0 {\displaystyle X_{0}} X N / 2 {\displaystyle X_{N/2}} N / 2 − 1 {\displaystyle N/2-1}
が純虚数の 場合、DFTは 奇対称 です 。 x 0 , … , x N − 1 {\displaystyle x_{0},\ldots ,x_{N-1}} X 0 , … , X N − 1 {\displaystyle X_{0},\ldots ,X_{N-1}} x n ∈ i R ∀ n ∈ { 0 , … , N − 1 } ⟹ X k = − X − k mod N ∗ ∀ k ∈ { 0 , … , N − 1 } {\displaystyle x_{n}\in i\mathbb {R} \quad \forall n\in \{0,\ldots ,N-1\}\implies X_{k}=-X_{-k\mod N}^{*}\quad \forall k\in \{0,\ldots ,N-1\}} ここで、 は 複素共役 を表します 。 X ∗ {\displaystyle X^{*}\,}
一般化DFT（シフトおよび非線形位相） 時間領域および／または周波数領域における変換サンプリングを、それぞれ実数シフトa および b だけシフトすることが可能です 。これは 一般化DFT （ GDFT ）と呼ばれることもあり、 シフトDFT または オフセットDFT とも呼ばれ、通常のDFTと同様の特性を持ちます。
X k = ∑ n = 0 N − 1 x n e − i 2 π N ( k + b ) ( n + a ) k = 0 , … , N − 1. {\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {i2\pi }{N}}(k+b)(n+a)}\quad \quad k=0,\dots ,N-1.} ほとんどの場合、 （サンプルの半分）のシフトが使用されます。通常のDFTは時間領域と周波数領域の両方で周期信号に対応するのに対し、 は周波数領域で反周期的な信号（ ）を生成し、 の場合はその逆となります 。したがって、 の特定のケースは 奇数時間奇数周波数 離散フーリエ変換（またはO 2 DFT）と呼ばれます 。このようなシフト変換は、対称データで異なる境界対称性を表すために最もよく使用され、実対称データの場合は、離散 コサイン 変換と 離散サイン 変換の異なる形式に対応します。 1 / 2 {\displaystyle 1/2} a = 1 / 2 {\displaystyle a=1/2} X k + N = − X k {\displaystyle X_{k+N}=-X_{k}} b = 1 / 2 {\displaystyle b=1/2} a = b = 1 / 2 {\displaystyle a=b=1/2}
もう一つの興味深い選択肢は、 中心DFT （または CDFT ）と呼ばれるものです。中心DFTは、 Nが 4の倍数であるとき、その4つの固有値（上記参照）すべてが等しい重複度を持つという有用な性質 を持っています（Rubio and Santhanam, 2005） [20] a = b = − ( N − 1 ) / 2 {\displaystyle a=b=-(N-1)/2}
GDFTという用語は、DFTの非線形位相拡張にも用いられます。したがって、GDFT法は、線形および非線形位相型を含む定振幅直交ブロック変換の一般化を提供します。GDFTは、適切に設計された位相整形関数（一般的には非線形）を元の線形位相関数に追加することで、従来のDFTの時間領域および周波数領域特性（例えば自己相関／相互相関）を改善するための枠組みです（Akansu and Agirman-Tosun, 2010）。 [21]
離散フーリエ変換は、 複素平面の 単位円 上で評価される z 変換の特殊なケースとして考えることができます。より一般的な z 変換は、上記の 複素 シフト a および b に対応します。
時間と空間に埋め込まれた離散変換
多次元DFT 通常のDFTは、ちょうど1つの離散変数n の関数である 1次元列または 配列 を変換します。inにおける d個 の 離散変数 の関数である 多次元配列の多次元DFTは、 次のように定義されます。 x n {\displaystyle x_{n}} x n 1 , n 2 , … , n d {\displaystyle x_{n_{1},n_{2},\dots ,n_{d}}} n ℓ = 0 , 1 , … , N ℓ − 1 {\displaystyle n_{\ell }=0,1,\dots ,N_{\ell }-1} ℓ {\displaystyle \ell } 1 , 2 , … , d {\displaystyle 1,2,\dots ,d}
X k 1 , k 2 , … , k d = ∑ n 1 = 0 N 1 − 1 ( ω N 1 k 1 n 1 ∑ n 2 = 0 N 2 − 1 ( ω N 2 k 2 n 2 ⋯ ∑ n d = 0 N d − 1 ω N d k d n d ⋅ x n 1 , n 2 , … , n d ) ) , {\displaystyle X_{k_{1},k_{2},\dots ,k_{d}}=\sum _{n_{1}=0}^{N_{1}-1}\left(\omega _{N_{1}}^{~k_{1}n_{1}}\sum _{n_{2}=0}^{N_{2}-1}\left(\omega _{N_{2}}^{~k_{2}n_{2}}\cdots \sum _{n_{d}=0}^{N_{d}-1}\omega _{N_{d}}^{~k_{d}n_{d}}\cdot x_{n_{1},n_{2},\dots ,n_{d}}\right)\right),} ここで は上記と同じで、 d 個 の出力インデックスは から までの範囲 です。これは ベクトル 表記でより簡潔に表現され、と を 0 から までのインデックスを持つ d 次元ベクトル として定義し ます。 これは と定義されます 。 ω N ℓ = exp ( − i 2 π / N ℓ ) {\displaystyle \omega _{N_{\ell }}=\exp(-i2\pi /N_{\ell })} k ℓ = 0 , 1 , … , N ℓ − 1 {\displaystyle k_{\ell }=0,1,\dots ,N_{\ell }-1} n = ( n 1 , n 2 , … , n d ) {\displaystyle \mathbf {n} =(n_{1},n_{2},\dots ,n_{d})} k = ( k 1 , k 2 , … , k d ) {\displaystyle \mathbf {k} =(k_{1},k_{2},\dots ,k_{d})} N − 1 {\displaystyle \mathbf {N} -1} N − 1 = ( N 1 − 1 , N 2 − 1 , … , N d − 1 ) {\displaystyle \mathbf {N} -1=(N_{1}-1,N_{2}-1,\dots ,N_{d}-1)}
X k = ∑ n = 0 N − 1 e − i 2 π k ⋅ ( n / N ) x n , {\displaystyle X_{\mathbf {k} }=\sum _{\mathbf {n} =\mathbf {0} }^{\mathbf {N} -1}e^{-i2\pi \mathbf {k} \cdot (\mathbf {n} /\mathbf {N} )}x_{\mathbf {n} }\,,} ここで、除算は 要素ごとに実行されるよう に定義され、合計は上記の入れ子になった合計のセットを表します。 n / N {\displaystyle \mathbf {n} /\mathbf {N} } n / N = ( n 1 / N 1 , … , n d / N d ) {\displaystyle \mathbf {n} /\mathbf {N} =(n_{1}/N_{1},\dots ,n_{d}/N_{d})}
多次元DFTの逆は、1次元の場合と同様に、次のように表されます。
x n = 1 ∏ ℓ = 1 d N ℓ ∑ k = 0 N − 1 e i 2 π n ⋅ ( k / N ) X k . {\displaystyle x_{\mathbf {n} }={\frac {1}{\prod _{\ell =1}^{d}N_{\ell }}}\sum _{\mathbf {k} =\mathbf {0} }^{\mathbf {N} -1}e^{i2\pi \mathbf {n} \cdot (\mathbf {k} /\mathbf {N} )}X_{\mathbf {k} }\,.} 1次元DFTでは入力を 正弦波の重ね合わせとして表現するのに対し、多次元DFTでは入力を 平面波 、つまり多次元正弦波の重ね合わせとして表現します。空間における振動の方向は です 。振幅は です。この分解は 、デジタル画像処理 （2次元）から 偏微分方程式の 解法まで、あらゆる場面で非常に重要です 。解は平面波に分解されます。 x n {\displaystyle x_{n}} k / N {\displaystyle \mathbf {k} /\mathbf {N} } X k {\displaystyle X_{\mathbf {k} }}
多次元DFTは、各次元に沿った1次元DFTの列を 合成する ことで計算できます。2次元の場合、まず 行（つまり ）の独立DFTを 計算 し、新しい配列 を形成します 。次に、 列（ ）に沿った y の独立DFTを 計算し、最終結果 を形成します。あるいは、最初に列を計算し、次に行を計算することもできます。上記の 入れ子 になった和は と入れ子になった和の交換が可能なので、順序は重要ではありません 。 x n 1 , n 2 {\displaystyle x_{n_{1},n_{2}}} N 1 {\displaystyle N_{1}} n 2 {\displaystyle n_{2}} y n 1 , k 2 {\displaystyle y_{n_{1},k_{2}}} N 2 {\displaystyle N_{2}} n 1 {\displaystyle n_{1}} X k 1 , k 2 {\displaystyle X_{k_{1},k_{2}}}
したがって、1次元DFTを計算するアルゴリズムは、多次元DFTを効率的に計算するのに十分です。このアプローチは 行-列アルゴリズムとして知られています。また、本質的に 多次元のFFTアルゴリズム も存在します 。
実数 からなる 入力データの場合 、DFT出力は上記の1次元の場合と同様の共役対称性を持ちます。 x n 1 , n 2 , … , n d {\displaystyle x_{n_{1},n_{2},\dots ,n_{d}}}
X k 1 , k 2 , … , k d = X N 1 − k 1 , N 2 − k 2 , … , N d − k d ∗ , {\displaystyle X_{k_{1},k_{2},\dots ,k_{d}}=X_{N_{1}-k_{1},N_{2}-k_{2},\dots ,N_{d}-k_{d}}^{*},} ここでも星印は複素共役を表し、 - 番目の下付き文字は を法として解釈されます ( の場合 )。 ℓ {\displaystyle \ell } N ℓ {\displaystyle N_{\ell }} ℓ = 1 , 2 , … , d {\displaystyle \ell =1,2,\ldots ,d}
アプリケーション DFTは多くの分野で広く利用されていますが、ここではいくつかの例を挙げるにとどめます（末尾の参考文献も参照）。DFTのあらゆる応用は、離散フーリエ変換とその逆変換を計算する高速アルゴリズム、 すなわち高速フーリエ変換 の利用可能性に大きく依存しています。
スペクトル分析 DFT を 信号スペクトル解析 に使用する場合、 シーケンスは通常、何らかの信号 の均一に間隔を置いた時間サンプルの有限セットを表します。 ここで、 は 時間を表します。連続時間からサンプル (離散時間) への変換により、 の基礎となる フーリエ変換 が 離散時間フーリエ変換 (DTFT)に変更されますが、これには通常、 エイリアシング と呼ばれる一種の歪みが伴います 。適切なサンプル レート ( ナイキスト レート を 参照) を選択することが、その歪みを最小限に抑える鍵となります。同様に、非常に長い (または無限の) シーケンスを扱いやすいサイズに変換すると、 リーク と呼ばれる一種の歪みが伴い、これは DTFT の詳細 (解像度) の損失として現れます。適切なサブシーケンスの長さを選択することが、その影響を最小限に抑える主な鍵となります。使用可能なデータ (およびそれを処理するための時間) が、必要な周波数解像度を達成するために必要な量より多い場合、標準的な手法では、たとえば スペクトログラム を作成します。望ましい結果がパワー スペクトルであり、データにノイズまたはランダム性が存在する場合、複数の DFT の振幅成分を平均化する手順は、 スペクトルの 分散(この文脈では ピリオドグラム とも呼ばれます) を減らすのに役立ちます。このような手法の 2 つの例として、 ウェルチ法 と バートレット法 があります。ノイズの多い信号のパワー スペクトルを推定する一般的な主題は、 スペクトル推定 と呼ばれます。 { x n } {\displaystyle \{x_{n}\}} x ( t ) {\displaystyle x(t)\,} t {\displaystyle t} x ( t ) {\displaystyle x(t)}
歪み（あるいは 錯覚 ）の最後の原因はDFTそのものです。DFTは連続周波数領域の関数であるDTFTの離散サンプリングに過ぎないからです。これはDFTの解像度を上げることで軽減できます。その手順は 「§ DTFTのサンプリング」 で説明されています。
この手順はゼロパディング と呼ばれることもあり、 高速フーリエ変換 （FFT）アルゴリズムと組み合わせて使用される特別な実装です 。ゼロ値の「サンプル」を用いて乗算や加算を実行することの非効率性は、FFT本来の効率性によって十分に補われます。 すでに述べたように、漏れは DTFT の固有の解像度に制限を課すため、細粒度 DFT から得られる利点には実際的な制限があります。
光学、回折、トモグラフィー 離散フーリエ変換は、空間周波数を用いて、光、電子、その他のプローブが光学系を通過し、2次元および3次元の物体から散乱する様子をモデル化する際に広く用いられています。3次元物体の双対（順ベクトル空間／逆ベクトル空間）ベクトル空間は、さらに3次元逆格子を可能にします。この逆格子は、半透明物体の影から（ フーリエスライス定理 を用いて）構築され、現代医学など幅広い応用分野において3次元物体の断層画像再構成を可能にします。
フィルタバンク § FFT フィルタ バンク と § DTFT のサンプリングを 参照してください 。
データ圧縮 デジタル信号処理の分野では、周波数領域 (つまり、フーリエ変換) の操作に大きく依存しています。たとえば、いくつかの 非可逆 画像および音声圧縮方法では、離散フーリエ変換が使用されます。つまり、信号は短いセグメントに分割され、それぞれが変換された後、目立たないと考えられる高周波数のフーリエ係数が破棄されます。解凍器は、この削減された数のフーリエ係数に基づいて、逆変換を計算します。(圧縮アプリケーションでは、多くの場合、DFT の特殊な形式である 離散コサイン変換 、または場合によっては 修正離散コサイン変換が 使用されます。) ただし、比較的最近の圧縮アルゴリズムでは、 ウェーブレット変換 が使用されます。これは、データをセグメントに切り分けて各セグメントを変換するよりも、時間領域と周波数領域の間でより均一な妥協点をもたらします。JPEG2000 の場合、これにより、元 の JPEG で 画像を高度に圧縮した場合に現れる偽の画像特徴が回避されます 。
偏微分方程式 離散フーリエ変換は偏微分方程式 を解くのによく使われますが 、ここでも DFT は フーリエ級数（無限 N の極限で回復される ）の近似として使われます。この方法の利点は、信号を複素指数 （微分固有関数）で展開することです 。したがって、フーリエ表現では微分は簡単で、 を掛けるだけです 。（ただし、 の選択は エイリアシングのために一意ではありません。この方法を収束させるには、上記の三角関数補間のセクションの場合と同様の選択を使用する必要があります。）定数係数の 線形微分方程式は 、簡単に解ける代数方程式に変換されます。次に、逆 DFT を使用して結果を通常の空間表現に変換します。このような方法は スペクトル法 と呼ばれます。 e i n x {\displaystyle e^{inx}} d ( e i n x ) / d x = i n e i n x {\displaystyle {{\text{d}}{\big (}e^{inx}{\big )}}/{\text{d}}x=ine^{inx}} i n {\displaystyle in} n {\displaystyle n}
多項式の乗算 多項式積 c ( x ) = a ( x ) · b ( x ) を計算したいとします。c の係数の通常の積式は 、インデックスが「ラップアラウンド」しない線形（非巡回）畳み込みを伴います。これは、まず定数項を持つ a ( x ) と b ( x ) の係数ベクトルを取り、その後にゼロを付加することで巡回畳み込みとして書き直すことができます。 その 結果 得 られる 係数 ベクトル a と b の 次元 は d > deg ( a ( x )) + deg( b ( x )) となります。すると、
c = a ∗ b {\displaystyle \mathbf {c} =\mathbf {a} *\mathbf {b} } ここで cは c ( x )の係数のベクトルであり 、畳み込み演算子は 次のように定義される。 ∗ {\displaystyle *\,}
c n = ∑ m = 0 d − 1 a m b n − m m o d d n = 0 , 1 … , d − 1 {\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} しかし、DFT では畳み込みは乗算になります。
F ( c ) = F ( a ) F ( b ) {\displaystyle {\mathcal {F}}(\mathbf {c} )={\mathcal {F}}(\mathbf {a} ){\mathcal {F}}(\mathbf {b} )} ここではベクトル積は要素ごとに取られる。したがって、積多項式 c ( x )の係数は、係数ベクトルの
0,...,deg( a ( x ))+deg( b ( x ))の項となる。
c = F − 1 ( F ( a ) F ( b ) ) . {\displaystyle \mathbf {c} ={\mathcal {F}}^{-1}({\mathcal {F}}(\mathbf {a} ){\mathcal {F}}(\mathbf {b} )).} 高速フーリエ変換を 用いると 、結果として得られるアルゴリズムは O ( N log N )回の算術演算を必要とします。その単純さと速度のため、変換演算には、 合成 サイズに制限される Cooley-Tukey FFTアルゴリズムが しばしば選択されます。この場合、 dは 、入力多項式の次数の合計よりも大きく、かつ小さな素因数に因数分解可能な最小の整数（FFTの実装に応じて、例えば2、3、5など）として選択する必要があります。
大きな整数の乗算 非常に大きな整数 の乗算を行う 既知の最高速 アルゴリズムは 、上記で概説した多項式乗算法を用いています。整数は、その基数で評価された多項式の値として扱うことができ、多項式の係数はその基数の桁に対応します（例 ：）。多項式乗算の後、比較的計算量の少ない繰り上がり伝播ステップによって乗算が完了します。 123 = 1 ⋅ 10 2 + 2 ⋅ 10 1 + 3 ⋅ 10 0 {\displaystyle 123=1\cdot 10^{2}+2\cdot 10^{1}+3\cdot 10^{0}}
畳み込み 大きなサンプリング比によるダウンサンプリングなど、サポート範囲の広い関数でデータを 畳み込む 場合、 畳み込み定理 とFFTアルゴリズムの原理により、データを変換し、フィルタの変換を点ごとに乗算してから逆変換する方が高速になる場合があります。あるいは、変換後のデータを単純に切り捨て、短縮されたデータセットを再変換するだけで、適切なフィルタが得られます。
いくつかのDFTペア x n = 1 N ∑ k = 0 N − 1 X k e i 2 π k n / N {\displaystyle x_{n}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}e^{i2\pi kn/N}} X k = ∑ n = 0 N − 1 x n e − i 2 π k n / N {\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-i2\pi kn/N}} 注記 x n e i 2 π n ℓ / N {\displaystyle x_{n}e^{i2\pi n\ell /N}\,} X k − ℓ {\displaystyle X_{k-\ell }\,} 周波数シフト定理 x n − ℓ {\displaystyle x_{n-\ell }\,} X k e − i 2 π k ℓ / N {\displaystyle X_{k}e^{-i2\pi k\ell /N}\,} 時間シフト定理 x n ∈ R {\displaystyle x_{n}\in \mathbb {R} } X k = X N − k ∗ {\displaystyle X_{k}=X_{N-k}^{*}\,} 実数DFT a n {\displaystyle a^{n}\,} { N if a = e i 2 π k / N 1 − a N 1 − a e − i 2 π k / N otherwise {\displaystyle \left\{{\begin{matrix}N&{\mbox{if }}a=e^{i2\pi k/N}\\{\frac {1-a^{N}}{1-a\,e^{-i2\pi k/N}}}&{\mbox{otherwise}}\end{matrix}}\right.} 等比数列の 公式 から ( N − 1 n ) {\displaystyle {N-1 \choose n}\,} ( 1 + e − i 2 π k / N ) N − 1 {\displaystyle \left(1+e^{-i2\pi k/N}\right)^{N-1}\,} 二項定理 から { 1 W if 2 n < W or 2 ( N − n ) < W 0 otherwise {\displaystyle \left\{{\begin{matrix}{\frac {1}{W}}&{\mbox{if }}2n<W{\mbox{ or }}2(N-n)<W\\0&{\mbox{otherwise}}\end{matrix}}\right.} { 1 if k = 0 sin ( π W k N ) W sin ( π k N ) otherwise {\displaystyle \left\{{\begin{matrix}1&{\mbox{if }}k=0\\{\frac {\sin \left({\frac {\pi Wk}{N}}\right)}{W\sin \left({\frac {\pi k}{N}}\right)}}&{\mbox{otherwise}}\end{matrix}}\right.} x n {\displaystyle x_{n}} はn =0を中心とした W 点 の 矩形 窓関数であり、 Wは 奇数 であり 、 sinc のような関数（具体的に は ディリクレ核 ） である。 X k {\displaystyle X_{k}} X k {\displaystyle X_{k}} ∑ j ∈ Z exp ( − π c N ⋅ ( n + N ⋅ j ) 2 ) {\displaystyle \sum _{j\in \mathbb {Z} }\exp \left(-{\frac {\pi }{cN}}\cdot (n+N\cdot j)^{2}\right)} c N ⋅ ∑ j ∈ Z exp ( − π c N ⋅ ( k + N ⋅ j ) 2 ) {\displaystyle {\sqrt {cN}}\cdot \sum _{j\in \mathbb {Z} }\exp \left(-{\frac {\pi c}{N}}\cdot (k+N\cdot j)^{2}\right)} のスケールされた ガウス関数 の 離散化 と 周期的な和 。またはのいずれ か が1より大きいため、2つの級数のうちの1つが高速に収束することが保証されるため、 が大きい場合は、 周波数スペクトルを計算し、離散フーリエ変換を使用して時間領域に変換することができます。 c > 0 {\displaystyle c>0} c {\displaystyle c} 1 c {\displaystyle {\frac {1}{c}}} c {\displaystyle c}
一般化
表現論 DFT は、有限 巡回群 の複素数値 表現 として解釈できます。言い換えれば、複素数列は - 次元複素空間の元、あるいはそれと同義的に、 の位数 有限巡回群 から 複素数 への 関数 と考えることができます 。 も 有限巡回群上の 類関数 であり 、したがって、この群の既約指標（単位元）の線形結合として表現できます。 n {\displaystyle n} n {\displaystyle n} C n {\displaystyle \mathbb {C} ^{n}} f {\displaystyle f} n {\displaystyle n} Z n ↦ C {\displaystyle \mathbb {Z} _{n}\mapsto \mathbb {C} } f {\displaystyle f}
この観点から、DFT を一般に表現理論に一般化することも、より狭義には 有限群の表現理論 に一般化することもできます。
さらに限定的に言えば、後述のとおり、ターゲット (複素数以外のフィールドの値を取る) またはドメイン (有限巡回群以外の群) を変更することで、DFT を一般化できます。
その他の分野 DFT の特性の多くは、 が の原始根 （ または と表記されることもある ）で あるという事実のみに依存します （したがって ）。このような特性には、上記の完全性、直交性、プランシェレル/パーセバル、周期性、シフト、畳み込み、ユニタリー性の特性や、多くの FFT アルゴリズムが含まれます。このため、離散フーリエ変換は 複素数以外の体の の根を使って定義することができ、このような一般化は有限体 の場合に一般に数論的変換 (NTT) と呼ばれます 。 詳細 について は 、 「数論的変換」 および 「離散フーリエ変換（一般）」 を参照してください。 e − i 2 π N {\displaystyle e^{-{\frac {i2\pi }{N}}}} ω N {\displaystyle \omega _{N}} W N {\displaystyle W_{N}} ω N N = 1 {\displaystyle \omega _{N}^{N}=1}
その他の有限群 標準DFTは 複素数列 x 0 , x 1 , ..., x N −1に作用し、これは関数{0, 1, ..., N − 1} → C として見ることができる。多次元DFTは多次元列に作用し、これは関数として見ることができる。
{ 0 , 1 , … , N 1 − 1 } × ⋯ × { 0 , 1 , … , N d − 1 } → C . {\displaystyle \{0,1,\ldots ,N_{1}-1\}\times \cdots \times \{0,1,\ldots ,N_{d}-1\}\to \mathbb {C} .} これは、関数G → C （ただし G は 有限群） に作用する 任意の有限群上のフーリエ変換 への一般化を示唆している。この枠組みでは、標準的な DFT は 巡回群 上のフーリエ変換とみなされ 、多次元 DFT は巡回群の直和上のフーリエ変換とみなされる。
さらに、フーリエ変換はグループの剰余類に対して行うことができます。
代替案 DFT の代替手法は様々な用途で存在しますが、中でも ウェーブレット 変換は最もよく知られています。DFT の類似物は 離散ウェーブレット変換(DWT) です。 時間周波数解析 の観点から見ると 、フーリエ変換の主な制約は、 位置 情報が含まれず 周波数 情報のみが含まれるため、過渡現象の表現が難しいことです。ウェーブレットは周波数だけでなく位置も扱うため、位置の表現能力は優れていますが、周波数の表現はより困難になります。詳細については、 離散ウェーブレット変換と離散フーリエ変換の比較を 参照してください。
参照
注記 ^ 同様に、サンプリング周波数とサンプル数の比率でもあります。 ^ 有限次元ベクトル空間 上の 線形変換 として 、DFT 式はDFT 行列 で表すこともできます 。適切にスケーリングするとユニタリ行列 になり 、 X k は 直交基底 における x の係数として見ることができます 。 ^ 周期的シーケンスの DTFT の非ゼロ成分は、DFT と同一の離散的な周波数セットです。 ^ DFT の時間反転は、負のインデックスを避けるために を で置き換え、 を で 置き換えないことを意味します 。 n {\displaystyle n} N − n {\displaystyle N-n} n {\displaystyle n} − n {\displaystyle -n}
参考文献 ^ Taboga, Marco (2021). 「離散フーリエ変換 - 周波数」, 行列代数の講義. https://www.statlect.com/matrix-algebra/discrete-Fourier-transform-frequencies. ^ Strang, Gilbert (1994年5～6月). 「ウェーブレット」. American Scientist . 82 (3): 250– 255. Bibcode :1994AmSci..82..250S. JSTOR 29775194. これは私たちの人生で最も重要な数値アルゴリズムです… ^ Sahidullah, Md.; Saha, Goutam (2013年2月). 「話者認識におけるMFCCの効率的な計算のための新しいウィンドウイング手法」. IEEE Signal Processing Letters . 20 (2): 149– 152. arXiv : 1206.2437 . Bibcode :2013ISPL...20..149S. doi :10.1109/LSP.2012.2235067. S2CID 10900793. ^ J. Cooley , P. Lewis, P. Welch (1969). 「有限フーリエ変換」. IEEE Transactions on Audio and Electroacoustics . 17 (2): 77– 85. Bibcode :1969ITAuE..17...77C. doi :10.1109/TAU.1969.1162036. {{cite journal }}: CS1 maint: multiple names: authors list (link )^ 「ゼロ周波数成分をスペクトルの中心にシフトする – MATLAB fftshift」. mathworks.com . Natick, MA 01760: The MathWorks, Inc . 2014年 3月10日 閲覧 。 {{cite web }}: CS1 maint: location (link )^ ab Proakis, John G.; Manolakis, Dimitri G. (1996), Digital Signal Processing: Principles, Algorithms and Applications (3 ed.), Upper Saddle River, NJ: Prentice-Hall International, Bibcode :1996dspp.book.....P, ISBN 978-0-13-394289-7 、sAcfAQAAIAAJ ^ Oppenheim, Alan V. ; Schafer, Ronald W. ; Buck, John R. (1999). 離散時間信号処理 （第2版）. Upper Saddle River, NJ: Prentice Hall. p. 571. ISBN 0-13-754920-2 。 ^ マクギレム, クレア・D.; クーパー, ジョージ・R. (1984). 連続および離散信号とシステム解析 （第2版）. ホルト, ライナーハート, ウィンストン. pp. 171– 172. ISBN 0-03-061703-0 。 ^ アミオット、エマニュエル (2016). フーリエ空間を通じた音楽. 計算音楽科学. チューリッヒ: シュプリンガー. p. 8. doi :10.1007/978-3-319-45581-5. ISBN 978-3-319-45581-5 . S2CID 6224021。 ^ Isabelle Baraquin; Nicolas Ratier (2023). 「離散フーリエ変換の一意性」. 信号処理 . 209 109041. Bibcode :2023SigPr.20909041B. doi : 10.1016/j.sigpro.2023.109041 . ISSN 0165-1684. ^ モートン、パトリック (1980). 「シュアー行列の固有ベクトルについて」. 数論ジャーナル . 12 (1): 122– 127. doi :10.1016/0022-314X(80)90083-9. hdl : 2027.42/23371 . ^ Bose, NK「1次元およびn次元DFT行列の固有ベクトルと固有値」 AEU — International Journal of Electronics and Communications 55.2 (2001): 131-133. ^ ab Candan, Ç. (2011). DFT行列の固有構造について [DSP教育]. IEEE Signal Processing Magazine, 28(2), 105-108. ^ ab Pei, SC, Ding, JJ, Hsue, WL, & Chang, KW (2008). DFT、オフセットDFT、その他の周期演算のための一般化可換行列とその固有ベクトル．IEEE Transactions on Signal Processing, 56(8), 3891-3904. ^ Erseghe, T., & Cariolaro, G. (2003). 高い対称性を持つ正確かつ単純なDFT固有ベクトルの直交クラス．IEEE Transactions on Signal Processing, 51(10), 2527-2539. ^ Massar, S.; Spindel, P. (2008). 「離散フーリエ変換における不確定性関係」. Physical Review Letters . 100 (19) 190401. arXiv : 0710.0723 . Bibcode :2008PhRvL.100s0401M. doi :10.1103/PhysRevLett.100.190401. PMID: 18518426. S2CID : 10076374. ^ abc DeBrunner, Victor; Havlicek, Joseph P.; Przebinda, Tomasz; Özaydin, Murad (2005). 「L 2 ( R n ) , ℓ 2 ( Z ) {\displaystyle L^{2}(\mathbb {R} ^{n}),\ell ^{2}(\mathbb {Z} )} , and ℓ 2 ( Z / N Z ) {\displaystyle \ell ^{2}(\mathbb {Z} /N\mathbb {Z} )} のエントロピーベースの不確実性尺度と ℓ 2 ( Z / N Z ) {\displaystyle \ell ^{2}(\mathbb {Z} /N\mathbb {Z} )} のヒルシュマン最適変換」 (PDF) . IEEE Transactions on Signal Processing . 53 (8): 2690. Bibcode :2005ITSP...53.2690D. doi :10.1109/TSP.2005.850329. S2CID 206796625. 2011年6月23日 閲覧 。 ^ ab Donoho, DL; Stark, PB (1989). 「不確定性原理と信号回復」. SIAM Journal on Applied Mathematics . 49 (3): 906– 931. Bibcode :1989SJAM...49..906D. doi :10.1137/0149053. S2CID 115142886. ^ Aldahleh, K.; A. Iosevich; J. Iosevich; J. Jaimangal; A. Mayeli; S. Pack (2025). 「有限調和振動子とそのシーケンス、通信、レーダーへの応用」 IEEE Transactions on Information Theory . 54 (9): 4239– 4253. arXiv : 2504.14702 . doi :10.1109/TIT.2008.926440. ^
Santhanam, Balu; Santhanam, Thalanayar S. 「離散ガウス・エルミート関数と中心離散フーリエ変換の固有ベクトル」、第32回IEEE 国際音響・音声・信号処理会議 論文集（ICASSP 2007、SPTM-P12.4）、第3巻、pp. 1385-1388。 ^
Akansu, Ali N.; Agirman-Tosun, Handan「非線形位相を伴う一般化離散フーリエ変換」、IEEE Transactions on Signal Processing 、vol. 58、no. 9、pp. 4547–4556、2010年9月。
さらに読む ブリガム、E. オラン (1988). 高速フーリエ変換とその応用 . エングルウッド・クリフス、ニュージャージー州: プレンティス・ホール. ISBN 978-0-13-307505-2 。 スミス、スティーブン・W. (1999). 「第8章 離散フーリエ変換」. 科学者と技術者のためのデジタル信号処理ガイド （第2版）. サンディエゴ、カリフォルニア州: カリフォルニア・テクニカル・パブリッシング. ISBN 978-0-9660176-3-2 。 コーメン、トーマス・H・ レイソン、 チャールズ・E・ライサーソン 、 ロナルド・L・リベスト 、 クリフォード・スタイン (2001). 「第30章 多項式とFFT」 アルゴリズム入門 （第2版）MIT Press and McGraw-Hill. pp. 822–848. ISBN 978-0-262-03293-3 。 特にセクション30.2: DFTとFFT、pp. 830–838。 P. Duhamel; B. Piron; JM Etcheto (1988). 「逆DFTの計算について」. IEEE Transactions on Acoustics, Speech, and Signal Processing . 36 (2): 285– 286. Bibcode :1988ITASS..36..285D. doi :10.1109/29.1519. JH McClellan; TW Parks (1972). 「離散フーリエ変換の固有値と固有ベクトル」 IEEE Transactions on Audio and Electroacoustics . 20 (1): 66– 74. doi :10.1109/TAU.1972.1162342. Bradley W. Dickinson; Kenneth Steiglitz (1982). 「離散フーリエ変換の固有ベクトルと関数」 (PDF) . IEEE Transactions on Acoustics, Speech, and Signal Processing . 30 (1): 25– 31. Bibcode :1982ITASS..30...25D. CiteSeerX 10.1.1.434.5279 . doi :10.1109/TASSP.1982.1163843. （この論文の固有値多重度の表には明らかな誤植があることに注意してください。+ i /− i の 列が入れ替わっています。正しい表は McClellan and Parks (1972) に掲載されており、数値的に簡単に確認できます。） FA Grünbaum (1982). 「離散フーリエ変換の固有ベクトル」. Journal of Mathematical Analysis and Applications . 88 (2): 355– 363. doi : 10.1016/0022-247X(82)90199-8 . ナティグ・M・アタキシエフ。カート・ベルナルド・ウルフ (1997)。 「分数フーリエ クラフチュク変換」。 アメリカ光学学会誌 A. 14 (7): 1467–1477 。 書誌コード :1997JOSAA..14.1467A。 土井 ：10.1364/JOSAA.14.001467。 C. Candan; MA Kutay; HMOzaktas (2000). 「離散分数フーリエ変換」 (PDF) . IEEE Transactions on Signal Processing . 48 (5): 1329– 1337. Bibcode :2000ITSP...48.1329C. doi :10.1109/78.839980. hdl : 11693/11130 . 2017年9月21日時点のオリジナルより アーカイブ (PDF) . Magdy Tawfik Hanna、Nabila Philip Attalla Seif、Waleed Abd El Maguid Ahmed (2004). 「直交射影行列の特異値分解に基づく離散フーリエ変換行列のエルミート-ガウス型固有ベクトル」 IEEE Transactions on Circuits and Systems I: Regular Papers . 51 (11): 2245– 2254. Bibcode :2004ITCSE..51.2245H. doi :10.1109/TCSI.2004.836850. S2CID 14468134. {{cite journal }}: CS1 maint: multiple names: authors list (link )Shamgar Gurevich; Ronny Hadani (2009). 「離散フーリエ変換の対角化について」. 応用・計算調和解析 . 27 (1): 87– 99. arXiv : 0808.3281 . doi :10.1016/j.acha.2008.11.003. S2CID 14833478. プレプリント at. Shamgar Gurevich、Ronny Hadani、Nir Sochen (2008). 「有限調和振動子とそのシーケンス、通信、レーダーへの応用」 IEEE Transactions on Information Theory . 54 (9): 4239– 4253. arXiv : 0808.1495 . Bibcode :2008arXiv0808.1495G. doi :10.1109/TIT.2008.926440. S2CID 6037080. プレプリントはこちら. Juan G. Vargas-Rubio; Balu Santhanam (2005). 「多角度中心離散分数フーリエ変換について」. IEEE Signal Processing Letters . 12 (4): 273– 276. Bibcode :2005ISPL...12..273V. doi :10.1109/LSP.2005.843762. S2CID 1499353. FN Kong (2008). 「2つの離散エルミート-ガウス信号の解析的表現」. IEEE Transactions on Circuits and Systems II: Express Briefs . 55 (1): 56– 60. Bibcode :2008ITCSE..55...56K. doi :10.1109/TCSII.2007.909865. S2CID 5154718. キャスパー，ウィリアム；ヤキモフ，ミレン (2024). 「制限付き離散フーリエ変換」 arXiv : 2407.20379 [math.CA].
外部リンク DFTのインタラクティブな説明 離散フーリエ変換に関するMATLABチュートリアル 2016年3月4日アーカイブ Wayback Machine DFTに関するインタラクティブなフラッシュチュートリアル 離散フーリエ変換の数学 ジュリアス・O・スミス3世著 FFTW: DFT の高速実装 - C 言語で記述され、一般公衆利用許諾書 (GPL) に基づいている 汎用FFTパッケージ：CとFORTRANで実装されたもう一つの高速DFT、許容ライセンス 離散フーリエ変換の解説 離散フーリエ変換 離散フーリエ変換のインデックスとシフト 離散フーリエ変換の特性 非線形位相を持つ一般化離散フーリエ変換（GDFT）
![{\displaystyle k\in [0,N-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df0b5695ab6bf8e6af35829e5b5a4054420941ca)
![{\textstyle \left[-{\frac {N}{2}},{\frac {N}{2}}-1\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1982d4116a4f6901876df1093452533db119bb15)
![{\textstyle \left[-{\frac {N-1}{2}},{\frac {N-1}{2}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0930e7277fcce6245ebc905098666c45ed43234b)
![{\displaystyle u_{k}=\left[\left.e^{{\frac {i2\pi }{N}}kn}\;\right|\;n=0,1,\ldots ,N-1\right]^{\mathsf {T}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc6e26a9a620236b53fb23bf2622aa8989983792)
![{\displaystyle x*y_{_{N}}\ =\ \scriptstyle {\rm {DTFT}}^{-1}\displaystyle \left[\scriptstyle {\rm {DTFT}}\displaystyle \{x\}\cdot \scriptstyle {\rm {DTFT}}\displaystyle \{y_{_{N}}\}\right]\ =\ \scriptstyle {\rm {DFT}}^{-1}\displaystyle \left[\scriptstyle {\rm {DFT}}\displaystyle \{x_{_{N}}\}\cdot \scriptstyle {\rm {DFT}}\displaystyle \{y_{_{N}}\}\right],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2dee320f94cdd64f21327865994d5e25ab7031c7)
![{\displaystyle [0,N-1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d4099dcd12fea62ad089a8d26d2a14c54fc88f5)
![{\displaystyle p(t)={\begin{cases}\displaystyle {\frac {1}{N}}\left[{\begin{alignedat}{3}X_{0}+X_{1}e^{i2\pi t}+\cdots &+X_{{\frac {N}{2}}-1}e^{i2\pi {\big (}\!{\frac {N}{2}}-1\!{\big )}t}&\\&+X_{\frac {N}{2}}\cos(N\pi t)&\\&+X_{{\frac {N}{2}}+1}e^{-i2\pi {\big (}\!{\frac {N}{2}}-1\!{\big )}t}&+\cdots +X_{N-1}e^{-i2\pi t}\end{alignedat}}\right]&N{\text{ 偶数}}\\\displaystyle {\frac {1}{N}}\left[{\begin{alignedat}{3}X_{0}+X_{1}e^{i2\pi t}+\cdots &+X_{\frac {N-1}{2}}e^{i2\pi {\frac {N-1}{2}}t}&\\&+X_{\frac {N+1}{2}}e^{-i2\pi {\frac {N-1}{2}}t}&+\cdots +X_{N-1}e^{-i2\pi t}\end{alignedat}}\right]&N{\text{ 奇数}}\end{場合}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c142568b1ef75882b26929005d75d8464902b1c4)
![{\displaystyle F(m)=\prod _{s=K+1}^{L}\left[\cos \left({\frac {2\pi}{N}}m\right)-\cos \left({\frac {2\pi}{N}}s\right)\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/452500005f28e338188d3008d9c99760f2b290ae)
![{\displaystyle F(m)=\sin \left({\frac {2\pi}{N}}m\right)\prod _{s=K+1}^{L-1}\left[\cos \left({\frac {2\pi}{N}}m\right)-\cos \left({\frac {2\pi}{N}}s\right)\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7090fae53ffec58d0ebcbcfc4dc74b70e110ac30)
