DTFT・DFT・FFTの違いを整理する：定義・関係・Python実装

はじめに

「DTFT」「DFT」「FFT」――フーリエ解析を学ぶと類似した略語が次々に登場し、それぞれの違いと関係を曖昧なまま使ってしまうことが少なくありません。実際には3つは明確に区別されており、

DTFT（Discrete-Time Fourier Transform）：離散時間信号に対する連続な周波数表現
DFT（Discrete Fourier Transform）：DTFTを周波数軸でも離散化したもの
FFT（Fast Fourier Transform）：DFTを高速に計算するためのアルゴリズム

という関係にあります。本記事では、連続時間信号から標本化を経て離散信号に至る流れを起点に、DTFT・DFT・FFTの定義と相互関係を整理し、最後にPythonでDFTの直接計算と np.fft.fft の結果を比較して理解を確認します。

FFTの仕組みとPython実装と窓関数とPSD では実装中心に解説しましたが、本記事はその理論的な土台を整理する位置づけです。

連続信号から離散信号へ

連続時間フーリエ変換（CTFT）

連続時間信号 \(x_c(t)\) のフーリエ変換は次のように定義されます。

\[X_c(j\Omega) = \int_{-\infty}^{\infty} x_c(t)\, e^{-j\Omega t}\, dt \tag{1}\]

ここで \(\Omega\) は連続角周波数（rad/s）です。\(X_c(j\Omega)\) は連続関数であり、信号のあらゆる周波数成分を表します。

標本化による離散化

サンプリング定理で示したように、サンプリング周期 \(T_s\) （サンプリング周波数 \(f_s = 1/T_s\) ）で \(x_c(t)\) を標本化すると離散時間信号 \(x[n] = x_c(nT_s)\) が得られます。離散信号上の角周波数 \(\omega\) と連続信号上の角周波数 \(\Omega\) には次の関係があります。

\[\omega = \Omega T_s \tag{2}\]

\(\omega\) は単位「rad/sample」を持ち、\(2\pi\) で周期的です。これがDTFT/DFTを定義する自然な周波数軸になります。

DTFT：離散時間フーリエ変換

DTFTの定義

離散時間信号 \(x[n]\) （\(n \in \mathbb{Z}\) ）に対する**離散時間フーリエ変換（DTFT）**は次のように定義されます。

\[X(e^{j\omega}) = \sum_{n=-\infty}^{\infty} x[n]\, e^{-j\omega n} \tag{3}\]

ここで \(\omega \in \mathbb{R}\) は連続な角周波数（rad/sample）で、\(X(e^{j\omega})\) は \(\omega\) について 2π周期 の連続関数です。

逆DTFT

逆変換は次の積分で与えられます。

\[x[n] = \frac{1}{2\pi}\int_{-\pi}^{\pi} X(e^{j\omega})\, e^{j\omega n}\, d\omega \tag{4}\]

積分区間が \([-\pi, \pi]\) なのは、DTFTの周期性から1周期分で十分なためです。

DTFTの主な性質

周期性：\(X(e^{j(\omega + 2\pi)}) = X(e^{j\omega})\)
線形性：\(\mathcal{F}\{a x_1[n] + b x_2[n]\} = a X_1(e^{j\omega}) + b X_2(e^{j\omega})\)
時間シフト：\(\mathcal{F}\{x[n - k]\} = e^{-j\omega k} X(e^{j\omega})\)
畳み込み定理：\(\mathcal{F}\{x_1[n] * x_2[n]\} = X_1(e^{j\omega})\, X_2(e^{j\omega})\)
パーセバルの等式：\(\sum_{n} |x[n]|^2 = \dfrac{1}{2\pi}\int_{-\pi}^{\pi} |X(e^{j\omega})|^2 d\omega\)

Z変換との関係

Z変換の記事で示したように、Z変換 \(X(z) = \sum_n x[n] z^{-n}\) を単位円 \(z = e^{j\omega}\) 上で評価したものがDTFTです。すなわちDTFTはZ変換の特殊ケースで、ROCに単位円を含む場合のみ存在します。

DTFTの「困りごと」

DTFTは数学的に美しい定義ですが、計算機で扱う上では次の問題があります。

無限和：信号が無限長 \(n \in \mathbb{Z}\) の場合は厳密計算が困難
連続周波数軸：\(\omega \in \mathbb{R}\) が連続なので、計算機で表現するには離散化が必要

この2点を解決するのがDFTです。

DFT：離散フーリエ変換

DFTの定義

長さ \(N\) の有限長信号 \(x[n]\) （\(n = 0, 1, \ldots, N-1\) ）に対する**離散フーリエ変換（DFT）**は次のように定義されます。

\[X[k] = \sum_{n=0}^{N-1} x[n]\, e^{-j 2\pi kn/N}, \quad k = 0, 1, \ldots, N-1 \tag{5}\]

入力 \(N\) サンプル → 出力 \(N\) サンプルの有限長 → 有限長の写像である点が、DTFTとの最大の違いです。

逆DFT（IDFT）

\[x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k]\, e^{j 2\pi kn/N}, \quad n = 0, 1, \ldots, N-1 \tag{6}\]

DTFTとDFTの関係

DTFTを周波数軸 \(\omega\) について \(N\) 等分（\(\omega_k = 2\pi k / N\) 、\(k = 0, 1, \ldots, N-1\) ）でサンプリングしたものがDFTです。

\[X[k] = X(e^{j\omega})\big|_{\omega = 2\pi k/N} = \sum_{n=0}^{N-1} x[n]\, e^{-j 2\pi kn/N} \tag{7}\]

つまりDFTはDTFTを周波数軸でも離散化したものであり、計算機で扱える有限のデータ構造になります。\(X[k]\) は連続なDTFTスペクトル \(X(e^{j\omega})\) の「サンプル」であり、ビン間の値はサンプリングされていない点に注意が必要です。

周波数分解能

サンプリング周波数 \(f_s\) 、長さ \(N\) のDFTにおいて、ビン \(k\) に対応する物理周波数は

\[f_k = \frac{k}{N} f_s \tag{8}\]

であり、隣接ビン間の周波数分解能は \(\Delta f = f_s / N\) です。観測時間 \(T = N/f_s\) が長いほど分解能は細かくなります。

スペクトル漏れ

式 \((5)\) は \(x[n]\) を周期 \(N\) で周期的に拡張したものに対するDTFTサンプリングと等価です。実信号がこの仮想的な周期と一致しないと、有限長による打ち切りでスペクトル漏れが生じます。これを軽減するのが窓関数です。

FFT：高速フーリエ変換

FFTは「アルゴリズム」である

ここで強調したいのは、FFTは新しい変換ではなくDFTを高速に計算するアルゴリズムの総称であるという点です。出力 \(X[k]\) はDFTと完全に同一で、計算手順が異なるだけです。

DFTを式 \((5)\) どおりに素朴に計算すると、各 \(k\) について \(N\) 回の複素乗算と加算が必要なので、全体で \(O(N^2)\) 回の演算になります。\(N = 10^6\) の場合 \(10^{12}\) 回の演算となり、リアルタイム処理は不可能です。

Cooley-Tukey法のアイデア

1965年にCooleyとTukeyが発表したCooley-Tukey FFTは、\(N\) が合成数（特に2の冪乗）のとき、長さ \(N\) のDFTを長さ \(N/2\) の2つのDFTに分割することで計算量を削減します。

\(x[n]\) を偶数番目 \(x_e[m] = x[2m]\) と奇数番目 \(x_o[m] = x[2m+1]\) に分けると、

\[X[k] = \underbrace{\sum_{m=0}^{N/2-1} x_e[m]\, e^{-j 2\pi km/(N/2)}}_{E[k]} + W_N^k \underbrace{\sum_{m=0}^{N/2-1} x_o[m]\, e^{-j 2\pi km/(N/2)}}_{O[k]} \tag{9}\]

ここで \(W_N = e^{-j 2\pi / N}\) は回転因子です。回転因子の対称性 \(W_N^{k + N/2} = -W_N^k\) から、

\[X[k] = E[k] + W_N^k\, O[k], \quad X[k + N/2] = E[k] - W_N^k\, O[k] \tag{10}\]

が得られます。これがバタフライ演算です。長さ \(N\) のDFTを再帰的に2分割すると、計算量の漸化式は \(T(N) = 2T(N/2) + O(N)\) となり、解は

\[T(N) = O(N \log N) \tag{11}\]

になります。アルゴリズムの詳細な導出は FFTの記事を参照してください。

計算量の比較

サイズ \(N\)	DFT \(O(N^2)\)	FFT \(O(N \log_2 N)\)	高速化倍率
\(2^{10}\)	\(\approx 10^6\)	\(\approx 10^4\)	\(\sim 100\) 倍
\(2^{16}\)	\(\approx 4 \times 10^9\)	\(\approx 10^6\)	\(\sim 4000\) 倍
\(2^{20}\)	\(\approx 10^{12}\)	\(\approx 2 \times 10^7\)	\(\sim 50000\) 倍

\(N\) が大きくなるほどFFTの優位性が顕著になります。

radix-2以外のFFT

実用的なFFTライブラリは2の冪乗以外のサイズも扱えるよう、複数のアルゴリズムを組み合わせています。

radix-2 / radix-4 / split-radix：2の冪乗向けの基本アルゴリズム
mixed-radix：合成数 \(N = N_1 N_2\) を用いる一般化
Bluestein / chirp-Z：任意の \(N\) に対するチャープ畳み込み変換
Rader：素数長 \(N\) 向けの巡回畳み込みベース変換

NumPyの np.fft.fft 内部（FFTPACK / pocketfft）はこれらを使い分けるため、\(N\) が2の冪乗でなくても効率よく動作します。

最新の研究動向：GPUのTensor CoreとFFT

Cooley-Tukey型FFTは元来CPU上の逐次演算を前提に設計されたアルゴリズムですが、近年は行列乗算に特化したGPUのTensor Coreを活かすための再設計が研究テーマになっています。StanfordのFuらは2023年11月に発表した論文で、長い系列に対する畳み込みをFFTで計算する際、FFTを複数の小さな行列乗算に分解して定式化し直すことでTensor Coreを利用可能にし、PyTorchの標準実装に対して最大7.93倍の高速化を達成したと報告しています（ FlashFFTConv: Efficient Convolutions for Long Sequences with Tensor Cores 、Fu et al., 2023、ICLR 2024採択）。

これは「FFTのアルゴリズム的な計算量そのもの」ではなく「\(O(N \log N)\) の演算をどのハードウェア資源にどうマッピングするか」が実行時間を左右するという論点であり、前節でPythonの実測タイミングに見られた固定オーバーヘッドの支配と本質的に同根の問題です。大規模なFFT計算でも、メモリI/Oや演算ユニットの利用効率が理論計算量と同じかそれ以上に実行時間を左右します。

DTFT・DFT・FFTの関係まとめ

変換	入力	出力	周波数軸	性格
DTFT	離散・無限長	連続関数 \(X(e^{j\omega})\)	連続・\(2\pi\) 周期	数学的定義
DFT	離散・有限長 \(N\)	離散 \(N\) サンプル \(X[k]\)	\(\omega_k = 2\pi k/N\) で離散化	計算可能な変換
FFT	離散・有限長 \(N\)	DFTと同一	DFTと同一	DFT計算の高速アルゴリズム

要するに、

DTFT は理論上の定義
DFT はDTFTを周波数軸で離散化した有限版
FFT はDFTを \(O(N \log N)\) で計算するアルゴリズム

という階層関係です。FFTの結果はDFTそのものであり、両者を概念的に区別することが重要です。

PythonでDFT直接計算とFFTを比較

DFTの定義どおりの実装

行列形式で書くと、DFTは \(X = W x\) （\(W_{kn} = e^{-j 2\pi kn / N}\) のDFT行列）と表現できます。NumPyのブロードキャストで素直に実装できます。

import numpy as np

def dft_direct(x: np.ndarray) -> np.ndarray:
    """定義式どおりに O(N^2) で DFT を計算する。"""
    x = np.asarray(x, dtype=complex)
    N = x.shape[0]
    n = np.arange(N)
    k = n.reshape(-1, 1)               # 列ベクトル
    W = np.exp(-2j * np.pi * k * n / N)  # DFT 行列 (N x N)
    return W @ x

# --- np.fft.fft と結果を比較 ---
rng = np.random.default_rng(0)
x = rng.standard_normal(256) + 1j * rng.standard_normal(256)

X_dft = dft_direct(x)
X_fft = np.fft.fft(x)

abs_err = np.max(np.abs(X_dft - X_fft))
print(f"最大絶対誤差: {abs_err:.3e}")
# 出力例: 最大絶対誤差: 3.813e-12

両者の差は浮動小数点演算の丸め誤差レベル（\(10^{-12}\) 程度）で、FFTがDFTを正確に計算していることが確認できます。

計算時間の比較

長さ \(N\) を変えて両者の実行時間を比較すると、\(O(N^2)\) と \(O(N \log N)\) の差が体感できます。実行時間はOSのスケジューリングなどで揺らぐため、各 \(N\) で7回計測した中央値を採用します。

import time
import numpy as np

def dft_direct(x):
    x = np.asarray(x, dtype=complex)
    N = x.shape[0]
    n = np.arange(N)
    k = n.reshape(-1, 1)
    W = np.exp(-2j * np.pi * k * n / N)
    return W @ x

sizes = [2**p for p in range(6, 13)]  # 64, 128, ..., 4096
t_dft, t_fft = [], []
rng = np.random.default_rng(1)

for N in sizes:
    x = rng.standard_normal(N) + 1j * rng.standard_normal(N)

    times_dft = []
    for _ in range(7):
        t0 = time.perf_counter()
        _ = dft_direct(x)
        times_dft.append(time.perf_counter() - t0)
    t_dft.append(np.median(times_dft))

    times_fft = []
    for _ in range(7):
        t0 = time.perf_counter()
        _ = np.fft.fft(x)
        times_fft.append(time.perf_counter() - t0)
    t_fft.append(np.median(times_fft))

for N, td, tf in zip(sizes, t_dft, t_fft):
    print(f"N={N:5d}  DFT={td:.3e}s  FFT={tf:.3e}s  speedup={td / tf:8.1f}x")

# 両対数プロット上の傾き（べき指数）を最小二乗で推定
slope_dft = np.polyfit(np.log(sizes), np.log(t_dft), 1)[0]
slope_fft = np.polyfit(np.log(sizes), np.log(t_fft), 1)[0]
print(f"log-log 傾き  DFT: {slope_dft:.2f}   FFT: {slope_fft:.2f}")

出力（Python 3.13 / NumPy 2.4.2、Apple Silicon環境での実測値）:

N=   64  DFT=9.104e-05s  FFT=4.917e-06s  speedup=    18.5x
N=  128  DFT=2.760e-04s  FFT=4.334e-06s  speedup=    63.7x
N=  256  DFT=1.061e-03s  FFT=6.459e-06s  speedup=   164.3x
N=  512  DFT=4.023e-03s  FFT=6.542e-06s  speedup=   615.0x
N= 1024  DFT=1.703e-02s  FFT=1.067e-05s  speedup=  1597.0x
N= 2048  DFT=7.050e-02s  FFT=1.633e-05s  speedup=  4316.2x
N= 4096  DFT=2.759e-01s  FFT=2.938e-05s  speedup=  9393.9x
log-log 傾き  DFT: 1.95   FFT: 0.44

DFTの傾き1.95は理論値2（\(O(N^2)\) ）にほぼ一致します。一方FFTの傾きは0.44しかなく、\(O(N \log N)\) から期待される「ほぼ1」からは大きく外れています。これは計算量の理論値と実測時間の乖離という実務上の落とし穴です。この範囲の \(N\) （64〜4096）ではFFT自体の演算（マイクロ秒オーダー）よりも、Python関数呼び出しやNumPyのディスパッチにかかる固定オーバーヘッド（数μs）が支配的であり、傾きが理論値からずれます。真の漸近的挙動を測るには \(N\) をさらに大きく（\(10^5\) 以上）取るか、オーバーヘッドを差し引いた計測が必要です。FFTの実行時間をベンチマークする際、この固定コストの寄与を無視すると「FFTは遅い/速い」について誤った結論を導きかねない点に注意してください。

実測データをプロットすると次のようになります。

import matplotlib.pyplot as plt

plt.figure(figsize=(8, 5))
plt.loglog(sizes, t_dft, "o-", label="DFT direct  (O(N^2))")
plt.loglog(sizes, t_fft, "s-", label="np.fft.fft  (O(N log N))")
plt.xlabel("N (signal length)")
plt.ylabel("Elapsed time [s]")
plt.title("DFT vs FFT: computational cost")
plt.grid(True, which="both", alpha=0.3)
plt.legend()
plt.tight_layout()
plt.savefig("dft_fft_timing.png", dpi=150)

DFT直接計算とnp.fft.fftの計算時間比較（両対数プロット、7回計測の中央値）。N=64からN=4096まで、DFT直接計算（青、傾き1.95）はnp.fft.fft（赤、傾き0.44）より一貫して遅く、N=4096では約9394倍の速度差になる

図から、\(N=64\) ではDFT/FFTの実行時間差は約18.5倍にとどまるのに対し、\(N=4096\) では約9394倍まで拡大していることが分かります。前節の理論値の表と合わせると、\(N=2^{20}\) 付近まで外挿すれば数万倍規模の差になることが見積もれます。

DTFTの可視化（参考）

DFTビンの「間」の値を見たい場合は、信号をゼロパディングしてからFFTすると、DTFTを細かくサンプリングしたものが得られます。これは新しい情報を追加するわけではなく、連続スペクトル \(X(e^{j\omega})\) の補間表示です。

import numpy as np
import matplotlib.pyplot as plt

N = 32
n = np.arange(N)
x = np.cos(2 * np.pi * 0.1 * n)  # 正規化周波数 0.1 cycles/sample

# DFT（N点）
X_dft = np.fft.fft(x)
freqs_dft = np.fft.fftfreq(N)

# ゼロパディングでDTFTを近似（4096点に拡張）
N_pad = 4096
X_dtft = np.fft.fft(x, n=N_pad)
freqs_dtft = np.fft.fftfreq(N_pad)

# 正の周波数のみプロット
mask_dft = freqs_dft >= 0
mask_dtft = freqs_dtft >= 0

# それぞれのピーク位置と大きさを比較する
peak_dft = np.argmax(np.abs(X_dft[mask_dft]))
peak_dtft = np.argmax(np.abs(X_dtft[mask_dtft]))
print(f"DFT  ピーク: freq={freqs_dft[mask_dft][peak_dft]:.4f}  |X|={np.abs(X_dft[mask_dft])[peak_dft]:.2f}")
print(f"DTFT ピーク: freq={freqs_dtft[mask_dtft][peak_dtft]:.4f}  |X|={np.abs(X_dtft[mask_dtft])[peak_dtft]:.2f}")

plt.figure(figsize=(9, 4))
plt.plot(freqs_dtft[mask_dtft], np.abs(X_dtft[mask_dtft]),
         'b-', alpha=0.6, label='DTFT (zero-padded approx.)')
plt.stem(freqs_dft[mask_dft], np.abs(X_dft[mask_dft]),
         linefmt='r-', markerfmt='ro', basefmt=' ',
         label='DFT bins')
plt.xlabel('Normalized frequency [cycles/sample]')
plt.ylabel('Magnitude')
plt.title('DFT bins as samples of the continuous DTFT')
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig("dtft_visualization.png", dpi=150)

出力:

DFT  ピーク: freq=0.0938  |X|=15.39
DTFT ピーク: freq=0.1003  |X|=16.66

DFTビン（赤、N=32）と、ゼロパディングで密にサンプリングしたDTFT近似（青、N_pad=4096）の比較。信号の真の周波数0.1 cycles/sampleがDFTのビン間隔1/32=0.03125の整数倍でないため、最も近いDFTビン（freq=0.0938）の振幅15.39は、DTFT上の真のピーク振幅16.66より約7.6%低くなっている（スペクトル漏れ）

DFTビン（赤）が連続なDTFT曲線（青）の特定の点を取り出したものであることが直観的に分かります。さらにこの実測値はスペクトル漏れを具体的に示しています。信号の真の周波数は \(0.1\) cycles/sample ですが、\(N=32\) 点のDFTのビン間隔は \(\Delta f = 1/32 = 0.03125\) であり、\(0.1 / 0.03125 = 3.2\) は整数になりません。つまり信号の周期が観測窓 \(N\) の整数倍と一致せず、最も近いDFTビン（\(k=3\) 、\(f=0.0938\) ）の振幅は \(15.39\) にとどまります。一方、ゼロパディングで密にサンプリングしたDTFTでは真のピークに近い \(f=0.1003\) で振幅 \(16.66\) を記録しており、両者の差は

\[ \frac{16.66 - 15.39}{16.66} \approx 7.6\% \]

に達します。この振幅の過小評価が、観測周波数がDFTビンにちょうど一致しない場合に生じるスペクトル漏れの実測的な現れです。

まとめ

DTFT は離散信号に対する連続周波数表現で、Z変換を単位円上に制限したもの
DFT はDTFTを周波数軸で \(N\) 等分にサンプリングした有限版で、計算機で扱える形
FFT はDFTを \(O(N \log N)\) で計算するアルゴリズム（出力はDFTと同一）
計算量は \(N\) が大きいほどFFTが圧倒的に有利で、\(N = 2^{20}\) では数万倍の高速化
ゼロパディングは新情報を加えず、DTFTの密なサンプリング表示として機能する

3つの関係を整理しておくと、窓関数・PSD推定・フィルタ設計などの応用記事を読んだときに「いまどの軸の話をしているのか」が明確になります。

参考文献

Cooley, J. W., & Tukey, J. W. (1965). “An algorithm for the machine calculation of complex Fourier series.” Mathematics of Computation, 19(90), 297-301.
Oppenheim, A. V., & Schafer, R. W. (2009). Discrete-Time Signal Processing (3rd ed.). Prentice Hall.
Proakis, J. G., & Manolakis, D. G. (2006). Digital Signal Processing (4th ed.). Prentice Hall.
Fu, D. Y., Kumbong, H., Nguyen, E., & Ré, C. (2023). “FlashFFTConv: Efficient Convolutions for Long Sequences with Tensor Cores.” arXiv:2311.05908 (ICLR 2024). https://arxiv.org/abs/2311.05908
NumPy FFT documentation

DTFT・DFT・FFTの違いを整理する：定義・関係・Python実装

はじめに

連続信号から離散信号へ

連続時間フーリエ変換（CTFT）

標本化による離散化

DTFT：離散時間フーリエ変換

DTFTの定義

逆DTFT

DTFTの主な性質

Z変換との関係

DTFTの「困りごと」

DFT：離散フーリエ変換

DFTの定義

逆DFT（IDFT）

DTFTとDFTの関係

周波数分解能

スペクトル漏れ

FFT：高速フーリエ変換

FFTは「アルゴリズム」である

Cooley-Tukey法のアイデア

計算量の比較

radix-2以外のFFT

最新の研究動向：GPUのTensor CoreとFFT

DTFT・DFT・FFTの関係まとめ

PythonでDFT直接計算とFFTを比較

DFTの定義どおりの実装

計算時間の比較

DTFTの可視化（参考）

まとめ

おすすめ書籍

関連記事

参考文献

はじめに

連続信号から離散信号へ

連続時間フーリエ変換（CTFT）

標本化による離散化

DTFT：離散時間フーリエ変換

DTFTの定義

逆DTFT

DTFTの主な性質

Z変換との関係

DTFTの「困りごと」

DFT：離散フーリエ変換

DFTの定義

逆DFT（IDFT）

DTFTとDFTの関係

周波数分解能

スペクトル漏れ

FFT：高速フーリエ変換

FFTは「アルゴリズム」である

Cooley-Tukey法のアイデア

計算量の比較

radix-2以外のFFT

最新の研究動向：GPUのTensor CoreとFFT

DTFT・DFT・FFTの関係まとめ

PythonでDFT直接計算とFFTを比較

DFTの定義どおりの実装

計算時間の比較

DTFTの可視化（参考）

まとめ

おすすめ書籍

関連記事

参考文献

この記事に関連する無料ツール

関連記事

離散信号処理の基礎ロードマップ：標本化・補間・DFT・Z変換・自己相関の体系的理解

Prometheusメトリクスの異常検知：EWMA適応閾値とカルマンフィルタをPythonで比較

RLS（逐次最小二乗法）アルゴリズムの理論とPython実装：カルマンフィルタとの等価性と忘却係数