離散フーリエ変換

図 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は偏微分方程式を効率的に解くためにも、畳み込みや大きな整数の 乗算などの他の演算を実行するためにも使用されます。

DFTは有限量のデータを扱うため、数値アルゴリズムや専用ハードウェアによってコンピュータに実装できます。これらの実装では通常、効率的な高速フーリエ変換（FFT）アルゴリズムが用いられます。^{[ 4 ]}そのため、「FFT」と「DFT」という用語はしばしば互換的に使用されます。現在のような用法になる前は、「FFT」という頭字語は、曖昧な用語である「有限フーリエ変換」にも使用されていた可能性があります。

意味

離散フーリエ変換は、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},}$

離散フーリエ変換

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}\cdot e^{-i2\pi {\tfrac {k}{N}}n}}$

式1

注：この定義ではサンプリング間隔が省略されているため、周波数軸は無次元となり、振幅は相対スケールのみで表現されます。ただし、FFT実装を含むほとんどのソフトウェアライブラリでは、この相対形式が使用されています。

変換は、 またはまたはのように、記号 で表されることもあります。^{[ 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は、次のようにさまざまな方法で解釈または導出できます。

• これは離散周波数成分のみを含む周期的シーケンスの離散時間フーリエ変換（DTFT）を完全に記述します。^{[ C ]}（周期的データでのDTFTの使用）${\displaystyle N}$
• また、有限長シーケンスの連続 DTFT の均一間隔のサンプルを提供することもできます。( § DTFT のサンプリング)
• これは、入力シーケンスと周波数における複素正弦波の相互相関です。したがって、これはその周波数の整合フィルタのように動作します。${\displaystyle x_{n}}$ ${\textstyle {\frac {k}{N}}.}$
• これはフーリエ級数の係数の式の離散的な類似物である。

  ${\displaystyle C_{k}={\frac {1}{P}}\int _{P}x(t)e^{-i2\pi {\tfrac {k}{P}}t}\,dt.}$

式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}$

逆変換は次のように与えられます。

逆変換

${\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において、各 は複素数であり、その極座標は関数の（離散フーリエ級数を参照）。正弦波の周波数はサンプルあたりサイクルです。 ${\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

DFT の標準定義を使用すると、インデックスがに従ってサンプリング間隔に対応する場合には、サンプリング間隔 (またはサンプリング距離) が省略されます。 ${\displaystyle \Delta t}$ ${\displaystyle n\Delta t=t}$

サンプリング間隔を含む連続フーリエ変換と一貫性のあるDFTを表現するために、サンプリング間隔は次のように明示的に含めることができる。

${\displaystyle X_{k}=\Delta t\sum _{n=0}^{N-1}x_{n}\cdot e^{-i2\pi {\tfrac {k}{N}}n}}$

注: ほとんどのソフトウェア ライブラリでは、この形式は使用されず、対応するFFT実装を含む相対形式が使用されます。

対応する逆変換は次のようになります。

${\displaystyle x_{n}=\Delta f\sum _{k=0}^{N-1}X_{k}\cdot e^{i2\pi {\tfrac {k}{N}}n}}$

ここで周波数間隔は です。 ${\displaystyle \Delta f={\frac {1}{\Delta tN}}}$

例

この例では、長さのシーケンスと入力ベクトル に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}}$

財産	時間領域${\displaystyle x_{n}}$	周波数領域${\displaystyle X_{k}}$
時間の中の本当の部分	${\displaystyle \operatorname {Re} {\left(x_{n}\right)}}$	${\displaystyle {\frac {1}{2}}\left(X_{k}+X_{N-k}^{*}\right)}$
時間における虚数部	${\displaystyle \operatorname {Im} {\left(x_{n}\right)}}$	${\displaystyle {\frac {1}{2i}}\left(X_{k}-X_{N-k}^{*}\right)}$
周波数の実部	${\displaystyle {\frac {1}{2}}\left(x_{n}+x_{N-n}^{*}\right)}$	${\displaystyle \operatorname {Re} {\left(X_{k}\right)}}$
周波数の虚数部	${\displaystyle {\frac {1}{2i}}\left(x_{n}-x_{N-n}^{*}\right)}$	${\displaystyle \operatorname {Im} {\left(X_{k}\right)}}$

直交性

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

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

シフト定理

ある整数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} .}$

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

${\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 ]。}これは、線形畳み込みを効率的に計算するためによく使用されます。（巡回畳み込み、高速畳み込みアルゴリズム、オーバーラップセーブを参照） ${\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から（上記のようにほぼ0から10までではなく）のものであり、これは逆DFT式に似ています。この補間は傾きを最小化せず、実数 に対しては一般に実数値ではありません。そのため、この補間多項式の使用はよくある誤りです。 ${\displaystyle N-1}$ ${\displaystyle -N/2}$ ${\displaystyle +N/2}$ ${\displaystyle x_{n}}$

ユニタリーDFT

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の有用な特性の一つは、いくつかのよく知られた「トリック」を用いることで、逆DFTを（順方向）DFTを用いて簡単に表現できることです。（例えば、計算においては、まず一方の変換方向に対応する高速フーリエ変換のみを実装し、それからもう一方の変換方向を最初の変換方向から取得すると便利な場合がよくあります。）

まず、入力の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}$

これらの多重度問題はマクレランとパークス（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	メートル

言い換えると、の特性多項式は次のようになります。 ${\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 and Parks, 1972; Dickinson and Steiglitz, 1982; Grünbaum, 1982; Candan et al. , 2000; Hanna et al. , 2004; Gurevich and Hadani, 2008）。^{[ 12 ]}

固有値に対するDFT固有ベクトルを構築する1つの方法は、演算子の線形結合に基づいています。^{[ 13 ] [ 14 ] [ 15 ]}${\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行列の固有ベクトルである。演算子は、ベクトルを、の各値に対して直交する部分空間に投影する。^{[ 14 ]}つまり、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つの部分空間内では直交する固有ベクトルは生成されない。^{[ 15 ]}演算子は、列が の固有ベクトルである行列とみなすことができるが、それらは直交ではない。次元空間に張るベクトルの集合（ここでは固有値の重複度）を選択して、固有値 への固有ベクトルの集合を生成する場合、 の相互直交性は保証されない。しかし、 に直交化アルゴリズム（例えばグラム・シュミット過程）をさらに適用することで、直交集合を得ることができる。^{[ 16 ]}${\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に対する他のいくつかの単純な閉形式の解析的固有ベクトルが発見された（Casper-Yakimov, 2024）: ^{[ 17 ]}

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行列は、固有値を指数化することで分数べき乗にすることができます。^{[ 18 ]}連続フーリエ変換の場合、自然な直交固有関数はエルミート関数であるため、クラフチュク多項式など、これらのさまざまな離散類似物がDFTの固有ベクトルとして採用されています。^{[ 12 ]} しかし、分数離散フーリエ変換を定義するための「最良の」固有ベクトルの選択は、未解決の問題のままです。

不確定性原理

確率的不確定性原理

確率変数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に対しても同様に定義できるが、不確実性はシフト不変ではないため、同様の不確定性原理は有用ではない。それでも、マッサーとスピンデルによって意味のある不確定性原理が導入されている。^{[ 19 ]}${\displaystyle D_{0}(X)}$ ${\displaystyle D_{0}(x)}$ ${\displaystyle |X|^{2}}$ ${\displaystyle |x|^{2}}$

しかし、ヒルシュマンのエントロピー不確定性原理は、DFTの場合に有用な類似物を持つ。^{[ 20 ]}ヒルシュマンの不確定性原理は、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},}$

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

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

は、周期 のクロネッカーコムを適切に正規化した の平行移動と変調に等しいに対して等式が得られる。ここで はの任意の正確な整数約数である。確率質量関数は、周期 のクロネッカーコムを適切に平行移動したものに比例する。^{[ 20 ]}${\displaystyle P_{n}}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle N}$ ${\displaystyle Q_{m}}$ ${\displaystyle B=N/A}$

決定論的不確定性原理

信号のスパース性（または非ゼロ係数の数）を用いた、よく知られた決定論的不確定性原理もある。^{[ 21 ]}とを、それぞれ時間系列と周波数系列の非ゼロ要素の数とする。すると、 ${\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}.}$

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

加法的な不確定性原理

加法的な不確実性原理は、信号がどの程度スパースであるかを、信号変換の非ゼロ要素の加法的なエネルギーの観点から定量化する。^{[ 22 ]}より具体的には、との場合、2つの加法的な不確実性原理は次のように述べている。 ${\displaystyle E=\{i\in \{0,1,...,N-1\}\;|\;x_{i}\neq 0\}}$ ${\displaystyle F=\{i\in \{0,1,...,N-1\}\;|\;X_{i}\neq 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},}$
• ${\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}.}$

ここで、集合の加法エネルギーは定義され、 と表記されます。加法的な組合せ論では、 と のランダムな部分集合はしばしば低い加法エネルギーを持つことがよく知られています。したがって、加法的な不確定性原理のどちらのバリエーションも、前述の決定論的な不確定性原理よりも強く、と の両方の加法エネルギーが最大となる場合、すなわちと のときのみ、 が成立します。 ${\displaystyle A\subseteq \{0,1,2,...,N-1\}}$ ${\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|.}$ ${\displaystyle 2|A|^{2}-|A|\leq \Lambda (A)\leq |A|^{3},}$ ${\displaystyle \{0,1,...,N-1\}}$ ${\displaystyle E}$ ${\displaystyle F}$ ${\displaystyle \Lambda (E)=|E|^{3}}$ ${\displaystyle \Lambda (F)=|F|^{3}}$

実信号と純虚信号のDFT

• 実際のアプリケーションではよくあるように、が実数である場合、 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^{*}\,}$

一般化DFT（シフトおよび非線形位相）

時間領域および／または周波数領域における変換サンプリングを、それぞれ実数シフト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つの固有値（上記参照）すべてが等しい重複度を持つという便利な性質があります。^{[ 23 ] [ 18 ]}${\displaystyle a=b=-(N-1)/2}$

GDFTという用語は、DFTの非線形位相拡張にも用いられる。したがって、GDFT法は、線形および非線形位相型を含む定振幅直交ブロック変換の一般化を提供する。GDFTは、従来のDFTの時間領域および周波数領域特性（例えば、自己相関／相互相関）を改善する枠組みであり、適切に設計された位相整形関数（一般的には非線形）を元の線形位相関数に追加することで実現される。^{[ 24 ]}

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

時間と空間に埋め込まれた離散変換

多次元DFT

通常のDFTは、ちょうど1つの離散変数nの関数である1次元列または配列 を変換します。inにおける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

実数からなる入力データの場合、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 の振幅成分を平均化する手順は、スペクトルの分散(この文脈ではピリオドグラムとも呼ばれます) を減らすのに役立ちます。このような手法の 2 つの例として、ウェルチ法とバートレット法があります。ノイズの多い信号のパワー スペクトルを推定する一般的な主題は、スペクトル推定と呼ばれます。 ${\displaystyle \{x_{n}\}}$ ${\displaystyle x(t)\,}$ ${\displaystyle 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 を使用して結果を通常の空間表現に変換します。このような方法はスペクトル法と呼ばれます。 ${\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 x_{n}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}e^{i2\pi kn/N}}$	${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-i2\pi kn/N}}$	注記
${\displaystyle x_{n}e^{i2\pi n\ell /N}\,}$	${\displaystyle X_{k-\ell }\,}$	周波数シフト定理
${\displaystyle x_{n-\ell }\,}$	${\displaystyle X_{k}e^{-i2\pi k\ell /N}\,}$	時間シフト定理
${\displaystyle x_{n}\in \mathbb {R} }$	${\displaystyle X_{k}=X_{N-k}^{*}\,}$	実数DFT
${\displaystyle a^{n}\,}$	${\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.}$	等比数列の公式 から
${\displaystyle {N-1 \choose n}\,}$	${\displaystyle \left(1+e^{-i2\pi k/N}\right)^{N-1}\,}$	二項定理から
${\displaystyle \left\{{\begin{matrix}{\frac {1}{W}}&{\mbox{if }}2n<W{\mbox{ or }}2(N-n)<W\\0&{\mbox{otherwise}}\end{matrix}}\right.}$	${\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.}$	${\displaystyle x_{n}}$ はn =0を中心としたW点の矩形窓関数であり、 Wは奇数であり、sincのような関数（具体的にはディリクレ核） である。${\displaystyle X_{k}}$ ${\displaystyle X_{k}}$
${\displaystyle \sum _{j\in \mathbb {Z} }\exp \left(-{\frac {\pi }{cN}}\cdot (n+N\cdot j)^{2}\right)}$	${\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つが高速に収束することが保証されるため、 が大きい場合は、周波数スペクトルを計算し、離散フーリエ変換を使用して時間領域に変換することができます。 ${\displaystyle c>0}$ ${\displaystyle c}$ ${\displaystyle {\frac {1}{c}}}$ ${\displaystyle c}$

一般化

表現論

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 の特性の多くは、が の原始根（ または と表記されることもある）であるという事実のみに依存します（したがって）。このような特性には、上記の完全性、直交性、プランシェレル/パーセバル、周期性、シフト、畳み込み、ユニタリー性の特性や、多くの FFT アルゴリズムが含まれます。このため、離散フーリエ変換は複素数以外の体の の根を使って定義することができ、このような一般化は有限体 の場合に一般に数論的変換 (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行列
• 高速フーリエ変換
• FFTPACK
• 西洋最速のフーリエ変換
• パウリ行列の一般化
• 最小二乗スペクトル解析
• フーリエ関連変換の一覧
• 多次元変換
• ザック変換
• 量子フーリエ変換

注記

1. 同様に、サンプリング周波数とサンプル数の比率になります。
2. 有限次元ベクトル空間上の線形変換として、DFT 式はDFT 行列で表すこともできます。適切にスケーリングするとユニタリ行列になり、 X _{k は}直交基底におけるxの係数として見ることができます。
3. 周期的シーケンスの DTFT の非ゼロ成分は、DFT と同一の離散的な周波数セットです。
4. DFT の時間反転は、を でで置き換えないこと。${\displaystyle n}$ ${\displaystyle N-n}$ ${\displaystyle n}$ ${\displaystyle -n}$

参考文献

1. 「離散フーリエ変換周波数」 www.statlect.com . 2025年11月25日閲覧。
2. Strang , Gilbert (1994年5～6月). 「ウェーブレット」. American Scientist . 82 (3): 250– 255. Bibcode : 1994AmSci..82..250S . JSTOR 29775194.これは私たちの人生で最も重要な数値アルゴリズムです… 
3. 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 . 
4. 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 .
5. 「ゼロ周波数成分をスペクトルの中心にシフト – MATLAB fftshift」 . mathworks.com . Natick, MA 01760: The MathWorks, Inc . 2014年3月10日閲覧。
6. 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
7. Oppenheim, Alan V. ; Schafer, Ronald W. ; Buck, John R. (1999).離散時間信号処理（第2版）. Upper Saddle River, NJ: Prentice Hall. p.  571. ISBN 0-13-754920-2。
8. マクギレム, クレア・D.; クーパー, ジョージ・R. (1984).連続および離散信号とシステム解析（第2版）. ホルト, ライナーハート, ウィンストン. pp.  171– 172. ISBN 0-03-061703-0。
9. アミオット、エマニュエル (2016).フーリエ空間を通じた音楽. 計算音楽科学. チューリッヒ: シュプリンガー. p. 8. doi : 10.1007/978-3-319-45581-5 . ISBN 978-3-319-45581-5. S2CID  6224021 .
10. Isabelle Baraquin; Nicolas Ratier (2023). 「離散フーリエ変換の一意性」 .信号処理. 209 109041. Bibcode : 2023SigPr.20909041B . doi : 10.1016/j.sigpro.2023.109041 . ISSN 0165-1684 . 
11. モートン、パトリック (1980). 「シュアー行列の固有ベクトルについて」.数論ジャーナル. 12 (1): 122– 127. doi : 10.1016/0022-314X(80)90083-9 . hdl : 2027.42/23371 .
12. ナティグ・M・アタキシエフ;カート・ベルナルド・ウルフ (1997)。 「分数フーリエ クラフチュク変換」。アメリカ光学学会誌A. 14 (7): 1467–1477。書誌コード: 1997JOSAA..14.1467A。土井：10.1364/JOSAA.14.001467。
13. Bose, NK「1次元およびn次元DFT行列の固有ベクトルと固有値」 AEU — International Journal of Electronics and Communications 55.2 (2001): 131-133.
14. Candan, Ç. (2011). DFT行列の固有構造について [DSP教育]. IEEE Signal Processing Magazine, 28(2), 105-108.
15. Pei, SC, Ding, JJ, Hsue, WL, & Chang, KW (2008). DFT、オフセットDFT、その他の周期演算のための一般化可換行列とその固有ベクトル．IEEE Transactions on Signal Processing, 56(8), 3891-3904.
16. Erseghe, T., & Cariolaro, G. (2003). 高い対称性を持つ正確かつ単純なDFT固有ベクトルの直交クラス．IEEE Transactions on Signal Processing, 51(10), 2527-2539.
17. 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 . 
18. 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 . 
19. 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 .  
20. DeBrunner, Victor; Havlicek, Joseph P.; Przebinda, Tomasz; Özaydin, Murad (2005). 「エントロピーに基づく不確実性尺度、およびに対する Hirschman 最適変換を用いた」(PDF) . IEEE Transactions on Signal Processing . 53 (8): 2690. Bibcode : 2005ITSP...53.2690D . doi : 10.1109/TSP.2005.850329 . S2CID 206796625. 2011年6月23日閲覧.${\displaystyle L^{2}(\mathbb {R} ^{n}),\ell ^{2}(\mathbb {Z} )}$ ${\displaystyle \ell ^{2}(\mathbb {Z} /N\mathbb {Z} )}$ ${\displaystyle \ell ^{2}(\mathbb {Z} /N\mathbb {Z} )}$  
21. Donoho, DL; Stark, PB (1989). 「不確定性原理と信号回復」. SIAM Journal on Applied Mathematics . 49 (3): 906– 931. Bibcode : 1989SJAM...49..906D . doi : 10.1137/0149053 . S2CID 115142886 . 
22. 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 .
23. Santhanam, Balu; Santhanam, Thalanayar S.「離散ガウス・エルミート関数と中心離散フーリエ変換の固有ベクトル」 、第32回IEEE国際音響・音声・信号処理会議論文集（ICASSP 2007、SPTM-P12.4）、第3巻、pp. 1385-1388。
24. 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). 「離散フーリエ変換の固有ベクトル」 . J​​ournal of Mathematical Analysis and Applications . 88 (2): 355– 363. doi : 10.1016/0022-247X(82)90199-8 .
• 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 .
• 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.プレプリントはこちら.
• キャスパー，ウィリアム；ヤキモフ，ミレン (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）