離散フーリエ変換

数学において、離散フーリエ変換( 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」という頭字語は、あいまいな用語「有限フーリエ変換」 にも使用されていた可能性があります。

DFT には、物理​​的解釈のない純粋に数学的なものも含め、多くの用途があります。しかし、物理的には、連続的かつ周期的な関数である離散時間フーリエ変換(DTFT)の離散バージョン (つまりサンプル) として信号処理に関連付けることができます。DFT は、DTFT の 1 サイクルの N 個の等間隔のサンプルを計算します (図 2 および§ DTFT のサンプリングを参照) 。

離散フーリエ変換は、 N個の複素数のシーケンスを次のように定義される 別の複素数のシーケンスに 変換します。 ${\displaystyle \left\{\mathbf {x} _{n}\right\}:=x_{0},x_{1},\ldots ,x_{N-1}}$${\displaystyle \left\{\mathbf {X} _{k}\right\}:=X_{0},X_{1},\ldots ,X_{N-1},}$

変換は、またはまたは のように、記号 で表されることもあります。^[B]${\displaystyle {\mathcal {F}}}$${\displaystyle \mathbf {X} ={\mathcal {F}}\left\{\mathbf {x} \right\}}$${\displaystyle {\mathcal {F}}\left(\mathbf {x} \right)}$${\displaystyle {\mathcal {F}}\mathbf {x} }$

式1は、次のようにさまざまな方法で解釈または導出できます。

式1はドメインの外側でも評価することができ、その拡張されたシーケンスは周期的である。したがって、（が偶数の場合）や（が奇数の場合）などの他のインデックスシーケンスが使用されることもあり、これは変換結果の左半分と右半分を入れ替えることに相当する。^[5]${\displaystyle k\in [0,N-1]}$${\displaystyle N}$${\displaystyle N}$${\textstyle \left[-{\frac {N}{2}},{\frac {N}{2}}-1\right]}$${\displaystyle N}$${\textstyle \left[-{\frac {N-1}{2}},{\frac {N-1}{2}}\right]}$${\displaystyle N}$

逆変換は次のように表されます。

式2 も-周期的です (インデックス n で)。式 2では、それぞれが複素数であり、その極座標は関数の複素正弦波成分の振幅と位相です(離散フーリエ級数を参照)。正弦波の周波数はサンプルあたりサイクルです。 ${\displaystyle N}$${\displaystyle X_{k}}$${\displaystyle \left(e^{i2\pi {\tfrac {k}{N}}n}\right)}$${\displaystyle x_{n}.}$${\displaystyle k}$${\displaystyle N}$

DFT と IDFT を乗算する正規化係数 (ここでは 1 と) と指数の符号は、最も一般的な規則です。これらの規則の唯一の実際の要件は、DFT と IDFT の指数が反対の符号であることと、それらの正規化係数の積が であることです。DFT と IDFT の両方に対するの珍しい正規化により、変換ペアがユニタリになります。 ${\displaystyle {\tfrac {1}{N}}}$${\displaystyle {\tfrac {1}{N}}.}$${\displaystyle {\sqrt {\tfrac {1}{N}}}}$

この例では、長さのシーケンスと入力ベクトル にDFTを適用する方法を示します。${\displaystyle N=4}$

$${\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を計算する${\displaystyle \mathbf {x} }$

$${\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}}}$$

結果的に $${\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 は線形変換です。つまり、および の場合、任意の複素数 に対して次のようになります。 ${\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}}$${\displaystyle {\mathcal {F}}(\{y_{n}\})_{k}=Y_{k}}$${\displaystyle a,b}$

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

時間を逆転させる（つまりを に置き換える）^[D]は、周波数を逆転させる（つまりを に置き換える）ことに対応する。^{[6] : p.421}数学的には、 がベクトルxを表す場合、 ${\displaystyle n}$${\displaystyle N-n}$${\displaystyle x_{n}}$${\displaystyle k}$${\displaystyle N-k}$${\displaystyle \{x_{n}\}}$

もし${\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}}$

それから${\displaystyle {\mathcal {F}}(\{x_{N-n}\})_{k}=X_{N-k}}$

もしそうなら。^{[6] : p.423}${\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}}$${\displaystyle {\mathcal {F}}(\{x_{n}^{*}\})_{k}=X_{N-k}^{*}}$

この表は、時間領域におけるいくつかの数学的演算と、周波数領域における DFT に対する対応する効果を示しています。${\displaystyle x_{n}}$${\displaystyle X_{k}}$

ベクトルは、N次元複素ベクトルの集合上の直交基底を形成します。 ${\displaystyle u_{k}=\left[\left.e^{{\frac {i2\pi }{N}}kn}\;\right|\;n=0,1,\ldots ,N-1\right]^{\mathsf {T}}}$

${\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 の式を導くために使用でき、以下のユニタリー性特性と同等です。 ${\displaystyle \delta _{kk'}}$${\displaystyle k=k'}$

および がそれぞれおよびの DFT である場合、パーセバルの定理は次のように述べます。 ${\displaystyle X_{k}}$${\displaystyle Y_{k}}$${\displaystyle x_{n}}$${\displaystyle y_{n}}$

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

ここで星印は複素共役を表します。プランシュレルの定理はパーセバルの定理の特殊なケースであり、次のことを述べています。

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

これらの定理は、以下のユニタリ条件とも同等です。

周期性は定義から直接示されます。

${\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 式は周期的な拡張につながることが示されます。

ある整数mに対して線形位相を乗じることは、出力の循環シフトに対応する。は に置き換えられ、ここで添え字はNを法として解釈される（つまり、周期的）。同様に、入力の循環シフトは、出力に線形位相を乗じることに対応する。数学的には、 がベクトル xを表す場合、${\displaystyle x_{n}}$ ${\displaystyle e^{{\frac {i2\pi }{N}}nm}}$${\displaystyle X_{k}}$${\displaystyle X_{k}}$${\displaystyle X_{k-m}}$ ${\displaystyle x_{n}}$${\displaystyle X_{k}}$${\displaystyle \{x_{n}\}}$

もし${\displaystyle {\mathcal {F}}(\{x_{n}\})_{k}=X_{k}}$

それから${\displaystyle {\mathcal {F}}\left(\left\{x_{n}\cdot e^{{\frac {i2\pi }{N}}nm}\right\}\right)_{k}=X_{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 § 周期データを参照)、連続関数との積もゼロではないため、ここで と表記されます  。これにより、逆変換が大幅に簡略化されます。 ${\displaystyle y_{_{N}},}$${\displaystyle \scriptstyle {\text{DTFT}}\displaystyle \{y_{_{N}}\}}$${\displaystyle \scriptstyle {\text{DTFT}}\displaystyle \{x\}.}$

${\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],}$

ここで、 は次の数列の周期的な和である。${\displaystyle x_{_{N}}}$${\displaystyle x}$ ${\displaystyle (x_{_{N}})_{n}\ \triangleq \sum _{m=-\infty }^{\infty }x_{(n-mN)}.}$

通常、DFT と逆 DFT の合計は領域 で行われます。これらの DFT を および として定義すると、結果は次のようになります。${\displaystyle [0,N-1]}$${\displaystyle X}$${\displaystyle Y}$

${\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 のシーケンスの周期的な拡張であり、円関数として表現することもできます。${\displaystyle x}$${\displaystyle y_{_{N}}}$${\displaystyle y}$

${\displaystyle (y_{_{N}})_{n}=\sum _{p=-\infty }^{\infty }y_{(n-pN)}=y_{(n\operatorname {mod} N)},\quad n\in \mathbb {Z} .}$

畳み込みは次のように記述できます。

これは、およびの巡回畳み込みとして解釈される^{[7] [8]}これは、線形畳み込みを効率的に計算するためによく使用されます。（巡回畳み込み、高速畳み込みアルゴリズム、およびオーバーラップ保存を参照） ${\displaystyle x}$${\displaystyle y.}$

同様に、との相互相関は次のように表されます。${\displaystyle x}$${\displaystyle 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! 個の線形かつ可逆なマップが存在します。

また、次のことも示せます。

${\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}}$

${\displaystyle ={\frac {1}{N}}(\mathbf {X*Y_{N}} )_{k},}$これはとの円畳み込みです。${\displaystyle \mathbf {X} }$${\displaystyle \mathbf {Y} }$

三角補間多項式

${\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によって与えられ、の補間特性を満たします。 ${\displaystyle p(n/N)=x_{n}}$${\displaystyle n=0,\ldots ,N-1}$

偶数Nの場合、ナイキスト成分 が特別に処理されることに注意してください。 ${\textstyle {\frac {X_{N/2}}{N}}\cos(N\pi t)}$

この補間は一意ではありません。エイリアシングは、補間特性を変更せずに、任意の複素正弦波周波数にNを追加（たとえば、に変更）できることを意味しますが、ポイント間の値は異なります。ただし、上記の選択は、2 つの便利な特性があるため一般的です。まず、これは周波数が可能な限り最小の大きさを持つ正弦波で構成されます。補間は帯域制限です。次に、 が 実数の場合、も実数です。 ${\displaystyle e^{-it}}$${\displaystyle e^{i(N-1)t}}$${\displaystyle x_{n}}$${\displaystyle x_{n}}$${\displaystyle p(t)}$

対照的に、最も明白な三角関数補間多項式は、周波数が 0 から(上記のようにおよそからではなく) の範囲にあるもので、逆 DFT 式に似ています。この補間は傾きを最小化せず、実数 に対して一般に実数値ではありません。この補間の使用はよくある間違いです。 ${\displaystyle N-1}$${\displaystyle -N/2}$${\displaystyle +N/2}$${\displaystyle x_{n}}$

DFTを別の視点から見ると、上記の議論において、DFTは1867年に シルベスターによって導入されたヴァンデルモンド行列である DFT行列として表現できることに注目することです。

${\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乗根です。 ${\displaystyle \omega _{N}=e^{-i2\pi /N}}$

例えば、、、および ${\displaystyle N=2}$${\displaystyle \omega _{N}=e^{-i\pi }=-1}$

${\displaystyle \mathbf {F} ={\begin{bmatrix}1&1\\1&-1\\\end{bmatrix}},}$

（これはアダマール行列）または 離散フーリエ変換 § 上の例のように、および ${\displaystyle N=4}$${\displaystyle \omega _{N}=e^{-i\pi /2}=-i}$

${\displaystyle \mathbf {F} ={\begin{bmatrix}1&1&1&1\\1&-i&-1&i\\1&-1&1&-1\\1&i&-1&-i\\\end{bmatrix}}.}$

逆変換は上記の行列の逆行列で与えられる。

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

ユニタリ正規化定数を使用すると、DFT はユニタリ変換になり、ユニタリ行列によって定義されます。 ${\textstyle 1/{\sqrt {N}}}$

${\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 で見つけることができます。 ${\displaystyle \det()}$${\displaystyle \pm 1}$${\displaystyle \pm i}$

DFT の直交性は、正規直交性条件 (単位根で説明されているように数学の多くの分野で発生する) として表現されます。

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

Xがベクトルx のユニタリDFTとして定義されている場合、

${\displaystyle X_{k}=\sum _{n=0}^{N-1}U_{kn}x_{n}}$

そしてパーセバルの定理は次のように表現される。

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

DFT を、新しい座標系でベクトルの成分を指定するだけの座標変換と見なすと、上記は、 2 つのベクトルのドット積がユニタリ DFT 変換で保存されるという単なる記述になります。特殊なケースでは、これはベクトルの長さも保存されることを意味します。これはプランシュレルの定理です。 ${\displaystyle \mathbf {x} =\mathbf {y} }$

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

循環畳み込み定理の結果として、DFT 行列F は任意の循環行列を対角化します。

DFT の便利な特性は、いくつかのよく知られた「トリック」を介して、逆 DFT を (順方向) DFT で簡単に表現できることです。(たとえば、計算では、1 つの変換方向に対応する高速フーリエ変換のみを実装し、最初の変換方向から他の変換方向を取得すると便利なことがよくあります。)

まず、入力の1つを除いてすべてを逆にすることで逆DFTを計算することができます（Duhamel et al.、1988）。

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

(通常通り、下付き文字はN を法として 解釈されます。したがって、 の場合、 となります。) ${\displaystyle n=0}$${\displaystyle x_{N-0}=x_{0}}$

2番目に、入力と出力を組み合わせることもできます。

${\displaystyle {\mathcal {F}}^{-1}(\mathbf {x} )={\frac {1}{N}}{\mathcal {F}}\left(\mathbf {x} ^{*}\right)^{*}}$

3 番目に、この共役トリックのバリエーションとして、実部と虚部を入れ替える方法があります。これは、データ値を変更する必要がないため、好まれることがあります (これは、コンピュータ上でポインタ を変更するだけで実行できます)。を、実部と虚部を入れ替えたものとして定義します。つまり、 の場合、となります。同様に、は と等しくなります。次に、 ${\textstyle \operatorname {swap} (x_{n})}$${\displaystyle x_{n}}$${\displaystyle x_{n}=a+bi}$${\textstyle \operatorname {swap} (x_{n})}$${\displaystyle b+ai}$${\textstyle \operatorname {swap} (x_{n})}$${\displaystyle ix_{n}^{*}}$

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

つまり、逆変換は、正規化まで、入力と出力の両方で実数部と虚数部が交換された順方向変換と同じです (Duhamel et al.、1988)。

共役トリックは、DFT に密接に関連した、逆変換である新しい変換を定義するのにも使用できます。つまり、 はそれ自身の逆です。特に、は明らかにそれ自身の逆です。密接に関連した逆変換 ( の係数による) は です。これは、 の係数が2 を打ち消すためです。 実数入力 の場合、 の実数部は離散ハートレー変換に他なりません。これも逆変換です。 ${\displaystyle T(\mathbf {x} )={\mathcal {F}}\left(\mathbf {x} ^{*}\right)/{\sqrt {N}}}$${\displaystyle T(T(\mathbf {x} ))=\mathbf {x} }$${\textstyle {\frac {1+i}{\sqrt {2}}}}$${\displaystyle H(\mathbf {x} )={\mathcal {F}}\left((1+i)\mathbf {x} ^{*}\right)/{\sqrt {2N}}}$${\displaystyle (1+i)}$${\displaystyle H(H(\mathbf {x} ))}$${\displaystyle \mathbf {x} }$${\displaystyle H(\mathbf {x} )}$

DFT行列の固有値は単純でよく知られているが、固有ベクトルは複雑で一意ではなく、現在も研究が続けられている。明示的な式は数論のかなりの部分を伴って与えられている。^[11]

長さNのDFTについて上で定義したユニタリ形式を考える。ここで ${\displaystyle \mathbf {U} }$

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

この行列は行列多項式方程式を満たします。

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

これは上記の逆特性からわかります。2回演算すると元のデータが逆の順序で返されるため、4 回演算すると元のデータに戻り、単位行列になります。これは、固有値が次の式を満たすことを意味します。 ${\displaystyle \mathbf {U} }$${\displaystyle \mathbf {U} }$${\displaystyle \lambda }$

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

したがって、 の固有値はの4乗根、つまり+1、−1、+ i、または − iです。 ${\displaystyle \mathbf {U} }$${\displaystyle \lambda }$

この行列には 4 つの異なる固有値しかないため、重複度を持ちます。重複度は、各固有値に対応する線形独立な固有ベクトルの数を表します。( N 個の独立した固有ベクトルがあり、ユニタリ行列に欠陥 が存在することはありません。) ${\displaystyle N\times N}$

多重度の問題は McClellan と Parks (1972) によって解決されましたが、後にGauss (Dickinson と Steiglitz、1982) によって解決された問題と同等であることが示されました。多重度はN の4 を 法とする値に依存し、次の表で与えられます。

言い換えると、の特性多項式は次のようになります。 ${\displaystyle \mathbf {U} }$

${\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 および Parks、1972 年、Dickinson および Steiglitz、1982 年、Grünbaum、1982 年、Atakishiyev および Wolf、1997 年、Candan他、2000 年、Hanna他、2004 年、Gurevich および Hadani、2008 年)。

固有値に対するDFT固有ベクトルを構築する一つの方法は、演算子の線形結合に基づいています: ^{[12] [13] [14]}${\displaystyle \lambda }$

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

任意のベクトルに対して、ベクトルは次を満たします。 ${\displaystyle \mathbf {v} }$${\displaystyle \mathbf {u} (\lambda )={\mathcal {P}}_{\lambda }\mathbf {v} }$

${\displaystyle {\textbf {U}}\mathbf {u} (\lambda )=\lambda \mathbf {u} (\lambda )}$

したがって、ベクトルは、実際にはDFT行列の固有ベクトルです。演算子は、ベクトルを各値に対して直交する部分空間に投影します。^[13]つまり、2つの固有ベクトルとに対して、次の式が得られます。 ${\displaystyle \mathbf {u} (\lambda )}$${\displaystyle \mathbf {U} }$${\displaystyle {\mathcal {P}}_{\lambda }}$${\displaystyle \lambda }$${\displaystyle \mathbf {u} (\lambda )={\mathcal {P}}_{\lambda }\mathbf {v} }$${\displaystyle \mathbf {u} '(\lambda ')={\mathcal {P}}_{\lambda '}\mathbf {v} '}$

${\displaystyle \mathbf {u} ^{\dagger }(\lambda )\mathbf {u} '(\lambda ')=\delta _{\lambda \lambda '}\mathbf {u} ^{\dagger }(\lambda )\mathbf {v} '}$

しかし、一般に、射影演算子法では、1 つの部分空間内では直交する固有ベクトルは生成されません。[ ^14]演算子は、列が の固有ベクトルである行列と見ることができますが、それらは直交していません。 次元空間にまたがるベクトルの集合（ここで、は固有値 の重複度）を選択して、固有値 への固有ベクトルの集合を生成する場合、 の相互直交性は保証されません。ただし、直交集合は、集合 にさらに直交化アルゴリズム、たとえばグラム・シュミット過程を適用することで取得できます。^[15]${\displaystyle {\mathcal {P}}_{\lambda }}$${\displaystyle \mathbf {U} }$${\displaystyle \{\mathbf {v} _{n}\}_{n=1,\dots ,N_{\lambda }}}$${\displaystyle N_{\lambda }}$${\displaystyle N_{\lambda }}$${\displaystyle \lambda }$${\displaystyle \{\mathbf {u} _{n}(\lambda )={\mathcal {P}}_{\lambda }\mathbf {v} _{n}\}_{n=1,\dots ,N_{\lambda }}}$${\displaystyle \lambda }$${\displaystyle \mathbf {u} _{n}(\lambda )}$${\displaystyle \{\mathbf {u} _{n}(\lambda )\}_{n=1,\dots ,N_{\lambda }}}$

DFT 固有ベクトルを取得する最も簡単な方法は、連続フーリエ変換の固有関数を離散化することです。その中で最も有名なのはガウス関数です。関数の周期的な和は周波数スペクトルの離散化を意味し、離散化はスペクトルの周期的な和を意味するため、離散化され周期的に和されたガウス関数は、離散変換の固有ベクトルを生成します。

• ${\displaystyle F(m)=\sum _{k\in \mathbb {Z} }\exp \left(-{\frac {\pi \cdot (m+N\cdot k)^{2}}{N}}\right).}$

この級数の閉じた形式表現は、ヤコビ・シータ関数によって次のように 表される。

• ${\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 の固有ベクトルは次のようになります。

• ${\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 の固有ベクトルは次のようになります 。

• ${\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]}$
• ${\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 の固有ベクトルは次のようになります。

• ${\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)}$
• ${\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 と Santhanam、2005)。連続フーリエ変換の場合、自然な直交固有関数はエルミート関数であるため、これらのさまざまな離散類似物が、 Kravchuk 多項式など、DFT の固有ベクトルとして採用されてきました(Atakishiyev と Wolf、1997)。ただし、分数離散フーリエ変換を定義するための「最善の」固有ベクトルの選択は、未解決の問題のままです。

確率変数X _kが

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

それから

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

は、 nの離散確率質量関数を表すものと考えられる。この関数は、変換された変数から構築された関連する確率質量関数を持つ。

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

連続関数およびの場合、ハイゼンベルクの不確定性原理によれば、 ${\displaystyle P(x)}$${\displaystyle Q(k)}$

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

ここで、およびはそれぞれおよびの分散であり、適切に正規化されたガウス分布の場合に等式が達成される。分散はDFTに対して同様に定義される可能性があるが、不確実性はシフト不変ではないため、類似の不確定性原理は有用ではない。それでも、意味のある不確定性原理がMassarとSpindelによって導入されている。^[16]${\displaystyle D_{0}(X)}$${\displaystyle D_{0}(x)}$${\displaystyle |X|^{2}}$${\displaystyle |x|^{2}}$

しかし、ヒルシュマンのエントロピー不確実性は、DFTの場合に有用な類似物となる。^{[17]ヒルシュマンの不確定性原理は、2つの確率関数の}シャノンエントロピーによって表現される。

離散的な場合、シャノンエントロピーは次のように定義される。

${\displaystyle H(X)=-\sum _{n=0}^{N-1}P_{n}\ln P_{n}}$

そして

${\displaystyle H(x)=-\sum _{m=0}^{N-1}Q_{m}\ln Q_{m},}$

そしてエントロピー的不確定性原理は^[17]

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

は、周期 の適切に正規化されたクロネッカーコームの平行移動および変調に等しい場合に等式が得られます。ここで、は の正確な整数約数です。確率質量関数は、周期 の適切に平行移動されたクロネッカーコームに比例します。^[17]${\displaystyle P_{n}}$${\displaystyle A}$${\displaystyle A}$${\displaystyle N}$${\displaystyle Q_{m}}$${\displaystyle B=N/A}$

信号のスパース性（または非ゼロ係数の数）を使用するよく知られた決定論的不確定性原理もあります。^[18]とをそれぞれ時間および周波数シーケンスとにおける非ゼロ要素の数とします。すると、 ${\displaystyle \left\|x\right\|_{0}}$${\displaystyle \left\|X\right\|_{0}}$${\displaystyle x_{0},x_{1},\ldots ,x_{N-1}}$${\displaystyle X_{0},X_{1},\ldots ,X_{N-1}}$

${\displaystyle N\leq \left\|x\right\|_{0}\cdot \left\|X\right\|_{0}.}$

算術平均と幾何平均の不等式から直接導かれる帰結として、 も成り立つ。 両方の不確定性原理は、特別に選択された「ピケットフェンス」シーケンス（離散インパルス列）に対して厳密であることが示されており、信号回復アプリケーションに実用的である。^[18]${\displaystyle 2{\sqrt {N}}\leq \left\|x\right\|_{0}+\left\|X\right\|_{0}}$

• 実際のアプリケーションではよくあるように、 が実数である場合、 DFT は対称的です。${\displaystyle x_{0},\ldots ,x_{N-1}}$${\displaystyle X_{0},\ldots ,X_{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\}}$ここで、 は複素共役を表します。${\displaystyle X^{*}\,}$

したがって、偶数とについては実数値であり、DFT の残りの部分は複素数だけで完全に指定されます。 ${\displaystyle N}$ ${\displaystyle X_{0}}$${\displaystyle X_{N/2}}$${\displaystyle N/2-1}$

• が純虚数の場合、DFT は奇対称です。${\displaystyle x_{0},\ldots ,x_{N-1}}$${\displaystyle X_{0},\ldots ,X_{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\}}$ここで、 は複素共役を表します。${\displaystyle X^{*}\,}$

時間領域および/または周波数領域で変換サンプリングをそれぞれ実シフトaおよびbでシフトすることが可能です。これは一般化 DFT (またはGDFT ) と呼ばれることもあり、シフト DFTまたはオフセット DFTとも呼ばれ、通常の DFT と類似した特性を持ちます。

${\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 ² DFT）として知られています。このようなシフトされた変換は、異なる境界対称性を表すために対称データに最もよく使用され、実対称データの場合は離散コサイン変換と離散サイン変換のさまざまな形式に対応します。 ${\displaystyle 1/2}$${\displaystyle a=1/2}$${\displaystyle X_{k+N}=-X_{k}}$${\displaystyle b=1/2}$${\displaystyle a=b=1/2}$

もう一つの興味深い選択肢は、中心化DFT（またはCDFT ）と呼ばれるものです。中心化DFTには、Nが4の倍数の場合、その4つの固有値（上記参照）すべてが等しい重複度を持つという便利な性質があります（Rubio and Santhanam、2005）^[19]${\displaystyle a=b=-(N-1)/2}$

GDFT という用語は、DFT の非線形位相拡張にも使用されます。したがって、GDFT 法は、線形および非線形位相タイプを含む定振幅直交ブロック変換の一般化を提供します。GDFT は、適切に設計された位相成形関数 (一般に非線形) を元の線形位相関数に追加することにより、従来の DFT の時間領域および周波数領域の特性 (自己相関/相互相関など) を改善するためのフレームワークです (Akansu および Agirman-Tosun、2010)。^[20]

離散フーリエ変換は、複素平面上の単位円上で評価されるz 変換の特殊なケースとして見ることができます。より一般的な z 変換は、上記の複素シフトaとbに対応します。

通常の DFT は、正確に 1 つの離散変数nの関数である1 次元シーケンスまたは配列を変換します。 の d 個の離散変数の関数である多次元配列の多次元 DFT は、次のように定義されます。 ${\displaystyle x_{n}}$${\displaystyle x_{n_{1},n_{2},\dots ,n_{d}}}$${\displaystyle n_{\ell }=0,1,\dots ,N_{\ell }-1}$${\displaystyle \ell }$${\displaystyle 1,2,\dots ,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次元ベクトルとして定義し、 と定義します。 ${\displaystyle \omega _{N_{\ell }}=\exp(-i2\pi /N_{\ell })}$${\displaystyle k_{\ell }=0,1,\dots ,N_{\ell }-1}$${\displaystyle \mathbf {n} =(n_{1},n_{2},\dots ,n_{d})}$${\displaystyle \mathbf {k} =(k_{1},k_{2},\dots ,k_{d})}$${\displaystyle \mathbf {N} -1}$${\displaystyle \mathbf {N} -1=(N_{1}-1,N_{2}-1,\dots ,N_{d}-1)}$

${\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} }\,,}$

ここで、除算は要素ごとに実行されるように定義され、合計は上記のネストされた合計の集合を表します。 ${\displaystyle \mathbf {n} /\mathbf {N} }$${\displaystyle \mathbf {n} /\mathbf {N} =(n_{1}/N_{1},\dots ,n_{d}/N_{d})}$

多次元 DFT の逆は、1 次元の場合と同様に、次のように表されます。

${\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 次元)から偏微分方程式の解法まで、あらゆる場合に非常に重要です。解は平面波に分解されます。 ${\displaystyle x_{n}}$${\displaystyle \mathbf {k} /\mathbf {N} }$${\displaystyle X_{\mathbf {k} }}$

多次元 DFT は、各次元に沿った一連の 1 次元 DFT を合成することで計算できます。2 次元の場合、行の独立 DFT (つまり、 に沿った)が最初に計算され、新しい配列 が形成されます。次に、列に沿ったyの独立 DFT ( に沿った) が計算され、最終結果 が形成されます。または、最初に列を計算し、次に行を計算することもできます。上記の入れ子になった合計は と交換できるため、順序は重要ではありません。 ${\displaystyle x_{n_{1},n_{2}}}$${\displaystyle N_{1}}$${\displaystyle n_{2}}$${\displaystyle y_{n_{1},k_{2}}}$${\displaystyle N_{2}}$${\displaystyle n_{1}}$${\displaystyle X_{k_{1},k_{2}}}$

したがって、1 次元 DFT を計算するアルゴリズムは、多次元 DFT を効率的に計算するのに十分です。このアプローチは、行列アルゴリズムとして知られています。本質的に多次元の FFT アルゴリズムも存在します。

実数からなる入力データの場合、DFT出力は上記の1次元の場合と同様の共役対称性を持ちます。 ${\displaystyle x_{n_{1},n_{2},\dots ,n_{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 }$${\displaystyle N_{\ell }}$${\displaystyle \ell =1,2,\ldots ,d}$

DFT は多くの分野で幅広く使用されていますが、以下にいくつかの例を示します (最後の参考文献も参照してください)。DFT のすべてのアプリケーションは、離散フーリエ変換とその逆を計算する高速アルゴリズム、つまり高速フーリエ変換が利用可能であることに大きく依存しています。

DFT を信号スペクトル解析に使用する場合、シーケンスは通常、何らかの信号 の均一に間隔を置いた時間サンプルの有限セットを表します。ここで、 は時間を表します。連続時間からサンプル (離散時間) への変換により、 の基礎となるフーリエ変換が離散時間フーリエ変換(DTFT)に変更されますが、これには一般にエイリアシングと呼ばれる一種の歪みが伴います。適切なサンプル レート (ナイキスト レートを参照) を選択することが、その歪みを最小限に抑える鍵となります。同様に、非常に長い (または無限の) シーケンスから扱いやすいサイズへの変換には、リークと呼ばれる一種の歪みが伴い、DTFT の詳細 (解像度) の損失として現れます。適切なサブシーケンス長を選択することが、その影響を最小限に抑える主な鍵となります。使用可能なデータ (およびそれを処理するための時間) が、必要な周波数解像度を達成するために必要な量より多い場合、標準的な手法では、たとえばスペクトログラムを作成するために、複数の DFT を実行します。望ましい結果がパワースペクトルであり、データにノイズまたはランダム性が存在する場合、複数の DFT の振幅成分を平均化することは、スペクトルの分散を減らすための有用な手順です (この文脈ではピリオドグラムとも呼ばれます)。このような手法の 2 つの例として、ウェルチ法とバートレット法があります。ノイズの多い信号のパワースペクトルを推定する一般的な主題は、スペクトル推定と呼ばれます。 ${\displaystyle \{x_{n}\}}$${\displaystyle x(t)\,}$${\displaystyle t}$${\displaystyle x(t)}$

歪み（あるいは錯覚）の最終的な原因は DFT 自体です。これは、連続周波数領域の関数である DTFT の離散サンプリングにすぎないためです。これは、DFT の解像度を上げることで軽減できます。その手順は、§ DTFT のサンプリングで説明されています。

• この手順はゼロパディングと呼ばれることもあり、高速フーリエ変換(FFT) アルゴリズムと組み合わせて使用​​される特定の実装です。ゼロ値の「サンプル」を使用して乗算と加算を実行することの非効率性は、FFT の本来の効率性によって十分に相殺されます。
• すでに述べたように、漏れは DTFT の固有の解像度に制限を課すため、細粒度 DFT から得られる利点には実質的な制限があります。

離散フーリエ変換は、空間周波数とともに、光、電子、その他のプローブが光学系を通過し、2 次元および 3 次元の物体から散乱する方法をモデル化するために広く使用されています。3 次元物体の二重 (直接/逆) ベクトル空間により、さらに 3 次元逆格子が利用可能になります。この逆格子は、半透明の物体の影から (フーリエ スライス定理を介して) 構築され、現代医学など、幅広い用途で 3 次元物体の断層撮影再構成が可能になります。

§ FFT フィルタ バンクと§ DTFT のサンプリングを参照してください。

デジタル信号処理の分野では、周波数領域 (つまり、フーリエ変換) の操作に大きく依存しています。たとえば、いくつかの非可逆画像および音声圧縮方法では、離散フーリエ変換が採用されています。つまり、信号は短いセグメントに分割され、それぞれが変換された後、目立たないと考えられる高周波のフーリエ係数が破棄されます。解凍器は、この削減された数のフーリエ係数に基づいて逆変換を計算します。(圧縮アプリケーションでは、多くの場合、DFT の特殊な形式である離散コサイン変換、または場合によっては修正離散コサイン変換が使用されます。) ただし、比較的最近の圧縮アルゴリズムの中には、ウェーブレット変換を使用するものもあります。ウェーブレット変換では、データをセグメントに切り分けて各セグメントを変換する場合よりも、時間領域と周波数領域の間でより均一な妥協点が得られます。JPEG2000の場合、これにより、元のJPEGで画像を高度に圧縮した場合に現れる偽の画像特徴が回避されます。

離散フーリエ変換は偏微分方程式を解くのによく使われますが、ここでも DFT はフーリエ級数の近似として使われます(これは無限Nの極限で回復されます)。この方法の利点は、信号を複素指数 で展開することです。これは微分化の固有関数です: 。したがって、フーリエ表現では微分化は簡単で、 を掛けるだけです。 (ただし、エイリアシングのため の選択は一意ではありません。この方法が収束するためには、上記の三角関数補間のセクションでの選択に似た選択を使用する必要があります。)定数係数の線形微分方程式は、簡単に解ける代数方程式に変換されます。次に、逆 DFT を使用して結果を通常の空間表現に変換します。このような方法はスペクトル法と呼ばれます。 ${\displaystyle e^{inx}}$${\displaystyle {{\text{d}}{\big (}e^{inx}{\big )}}/{\text{d}}x=ine^{inx}}$${\displaystyle in}$${\displaystyle n}$

多項式積c ( x ) = a ( x ) · b ( x )を計算したいとします。 cの係数の通常の積式には、インデックスが「ラップアラウンド」しない線形 (非巡回) 畳み込みが含まれます。 これは、定数項を持つa ( x ) とb ( x ) の係数ベクトルを最初に取り、次にゼロを追加して、結果の係数ベクトルaとb の次元がd  > deg( a ( x )) + deg( b ( x ))になるようにすることで、巡回畳み込みとして書き直すことができます。

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

ここでcはc ( x )の係数のベクトルであり、畳み込み演算子は次のように定義される。 ${\displaystyle *\,}$

${\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 では畳み込みは乗算になります。

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

ここでベクトル積は要素ごとに取られます。したがって、積多項式c ( x )の係数は、係数ベクトルの 項0、...、deg( a ( x )) + deg( b ( x ))になります。

${\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 など)。

非常に大きな整数を乗算する最も高速な既知のアルゴリズムは、上で概説した多項式乗算法を使用します。整数は、特に基数で評価された多項式の値として扱うことができ、多項式の係数はその基数の数字に対応します (例: )。多項式乗算の後、比較的複雑度の低いキャリー伝搬ステップで乗算が完了します。 ${\displaystyle 123=1\cdot 10^{2}+2\cdot 10^{1}+3\cdot 10^{0}}$

大きなサンプリング比によるダウンサンプリングなど、サポート範囲の広い関数でデータを畳み込む場合、畳み込み定理と FFT アルゴリズムにより、データを変換し、フィルターの変換を点ごとに乗算してから逆変換する方が高速になる場合があります。または、変換されたデータを単純に切り捨て、短縮されたデータ セットを再変換するだけで、適切なフィルターが得られます。

DFT は、有限巡回群の複素数値表現として解釈できます。言い換えると、複素数のシーケンスは、次元複素空間の要素、または同等に、の有限巡回群から複素数 への関数として考えることができます。 は有限巡回群上のクラス関数であるため 、このグループの既約な指標 (単位根) の線形結合として表現できます。 ${\displaystyle n}$${\displaystyle n}$${\displaystyle \mathbb {C} ^{n}}$${\displaystyle f}$${\displaystyle n}$${\displaystyle \mathbb {Z} _{n}\mapsto \mathbb {C} }$${\displaystyle f}$

この観点から、DFT を一般に表現理論に一般化することも、より狭義には有限群の表現理論に一般化することもできます。

さらに狭義には、ターゲット (複素数以外のフィールドの値を取る) またはドメイン (有限巡回群以外のグループ) を変更することで DFT を一般化できます (詳細は後述)。

DFT の特性の多くは、が の原始的な 1 の根であり、または(したがって) と表記されるという事実のみに依存します。このような特性には、上記の完全性、直交性、プランシュレル/パーセバル、周期性、シフト、畳み込み、および 1 の根の特性のほか、多くの FFT アルゴリズムが含まれます。このため、離散フーリエ変換は複素数以外の体の 1 の根を使用して定義することができ、このような一般化は有限体の場合に一般に数論的変換(NTT) と呼ばれます。詳細については、数論的変換および離散フーリエ変換 (一般)を参照してください。 ${\displaystyle e^{-{\frac {i2\pi }{N}}}}$${\displaystyle \omega _{N}}$${\displaystyle W_{N}}$${\displaystyle \omega _{N}^{N}=1}$

標準DFTは複素数のシーケンスx ₀ , x ₁ , ..., x _{N −1に作用し、これは関数{0, 1, ...,} N − 1} → Cとして見ることができます。多次元DFTは多次元シーケンスに作用し、これは関数として見ることができます。

${\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行列
• 高速フーリエ変換
• FTPACK について
• FFTW
• パウリ行列の一般化
• 最小二乗スペクトル解析
• フーリエ関連変換の一覧
• 多次元変換
• ザックトランスフォーム
• 量子フーリエ変換

• ブリガム、E. オラン (1988)。高速フーリエ変換とその応用。ニュージャージー州エングルウッドクリフス: プレンティスホール。ISBN 978-0-13-307505-2。
• スミス、スティーブン W. (1999)。「第 8 章: 離散フーリエ変換」。科学者および技術者のためのデジタル信号処理ガイド(第 2 版)。カリフォルニア州サンディエゴ: カリフォルニア テクニカル パブリッシング。ISBN 978-0-9660176-3-2。
• Cormen, Thomas H. ; Charles E. Leiserson ; Ronald L. Rivest ; Clifford Stein (2001)。「第 30 章: 多項式と FFT」。アルゴリズム入門(第 2 版)。MIT Press および 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。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。CiteSeerX 10.1.1.434.5279。doi :10.1109/TASSP.1982.1163843 。 (この論文の固有値多重度の表には明らかな誤植があることに注意してください。+ i /− i列が入れ替わっています。正しい表は McClellan と Parks (1972) に掲載されており、数値的に簡単に確認できます。)
• FA Grünbaum (1982). 「離散フーリエ変換の固有ベクトル」.数学解析応用ジャーナル. 88 (2): 355–363. doi : 10.1016/0022-247X(82)90199-8 .
• Natig M. Atakishiyev、 Kurt Bernardo Wolf (1997)。「分数フーリエ-クラフチュク変換」。Journal of the Optical Society of America A。14 (7): 1467–1477。Bibcode :1997JOSAA..14.1467A。doi :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-09-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. 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。 プレプリント。
• 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。doi : 10.1109 /TCSII.2007.909865。S2CID  5154718。
• Casper, William; Yakimov, Milen (2024). 「制限付き離散フーリエ変換」. arXiv : 2407.20379 [math.CA].

• DFTのインタラクティブな説明
• 離散フーリエ変換に関する Matlab チュートリアル 2016-03-04 にWayback Machineでアーカイブされました
• DFT に関するインタラクティブなフラッシュチュートリアル
• 離散フーリエ変換の数学、ジュリアス・O・スミス3世著
• FFTW: DFT の高速実装 - C でコーディングされ、General Public License (GPL) に基づいている
• 汎用FFTパッケージ: CとFORTRANで実装されたもう一つの高速DFT、許容ライセンス
• 解説: 離散フーリエ変換
• 離散フーリエ変換
• 離散フーリエ変換のインデックスとシフト
• 離散フーリエ変換の特性
• 非線形位相を持つ一般化離散フーリエ変換 (GDFT)