NumpyのFFT入門(1) （FT -> DFT -> FFTの解説）

# 1. はじめに

## この記事の目的

本記事では、NumPyを用いたFFT（高速フーリエ変換）の基本概念と応用方法について詳しく解説します。信号処理やデータ解析の分野で頻繁に用いられるFFTの理解は、大学生にとって重要です。この記事を通じて、FFTの理論から実装、そして実際の応用例までを学び、実践的なスキルを身につけることを目指します。

## FFTの重要性

FFTは、信号を時間領域から周波数領域に変換するための効率的なアルゴリズムであり、音声解析、画像処理、振動解析、通信システムなど、さまざまな分野で不可欠な技術です。FFTを用いることで、信号の周波数成分を迅速に抽出し、データの特性をより深く理解することが可能になります。

![img](https://miro.medium.com/v2/resize:fit:700/1*w1mcpi8gCgQI4FrqWFJ2GA.png)

[image source]: https://kinder-chen.medium.com/denoising-data-with-fast-fourier-transform-a81d9f38cc4c	"Denoising Data with Fast Fourier Transform"



# 2. フーリエ変換の基礎

## フーリエ変換とは

フーリエ変換は、信号を周波数成分に分解する数学的手法です。ある信号がどのような周波数を含んでいるかを明らかにすることで、信号の特性を分析することができます。フーリエ変換は、連続信号に対する解析手法であり、通常は以下の数式で表されます。

$$
F(\omega) = \int_{-\infty}^{\infty} f(t) e^{-i\omega t} dt 
$$
ここで、

- $ F(\omega)   $  は信号の周波数成分、
- $f(t)$ は時間領域の信号、
- $\omega$ は角周波数、
- $ i$ は虚数単位を表します。

## 離散フーリエ変換（DFT）の数式と概念

デジタル信号処理においては、信号は離散的なサンプルで表現されます。このため、離散フーリエ変換（DFT）が用いられます。DFTは、次の数式で定義されます。

$$
X_k = \sum_{n=0}^{N-1} x_n e^{-i \frac{2\pi}{N} kn} 
$$

ここで、

- $ X_k $ は周波数成分の強度（複素数）、
- $ x_n $ は時間領域の信号サンプル、
- $ N $ はサンプル数、
- $ k $ は周波数インデックスです。

DFTは、時間領域の信号を周波数領域に変換し、その中の各周波数成分の大きさと位相を求めることができます。

## 逆離散フーリエ変換（IDFT）

逆離散フーリエ変換（IDFT）は、周波数領域から時間領域に信号を戻すための手法です。IDFTの数式は次の通りです。

$$
x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k e^{i \frac{2\pi}{N} kn} 
$$

IDFTを用いることで、周波数領域で操作した信号を再び時間領域に戻すことができます。これにより、例えばフィルタリングや圧縮後の信号を元の形式で再構築することが可能になります。

## まとめ

以下の表にフーリエ変換と離散フーリエ変換（DFT）の基本概念と数式を整理します。

| 項目                       | 数式                                                         | 説明                               |
| -------------------------- | ------------------------------------------------------------ | ---------------------------------- |
| フーリエ変換               | $ F(\omega) = \int_{-\infty}^{\infty} f(t) e^{-i\omega t} dt $ | 連続信号を周波数領域に変換         |
| 離散フーリエ変換（DFT）    | $ X_k = \sum_{n=0}^{N-1} x_n e^{-i \frac{2\pi}{N} kn} $      | 離散信号を周波数領域に変換         |
| 逆離散フーリエ変換（IDFT） | $ x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k e^{i \frac{2\pi}{N} kn} $ | 周波数領域から時間領域に信号を復元 |

# 3. FFT（高速フーリエ変換）とは

## FFTのアルゴリズム

高速フーリエ変換（FFT）は、離散フーリエ変換（DFT）を高速に計算するためのアルゴリズムです。通常のDFTの計算量は $O(N^2)$ ですが、FFTではこの計算量を $O(N \log N)$ に減少させることができます。これにより、大量のデータを迅速に処理することが可能です。

FFTは、特に信号のサンプル数が2のべき乗である場合に効率的に動作し、分割統治法を利用して計算を最適化します。主なアルゴリズムとしては、コーリー・トゥキー（Cooley-Tukey）アルゴリズムが一般的に用いられています。

## FFTとDFTの違い

FFTとDFTは基本的に同じ数学的概念に基づいていますが、計算効率が異なります。FFTは、DFTの計算を最適化するためのアルゴリズムであり、特に大規模なデータセットに対して優れた性能を発揮します。

- **DFT**: 計算量が $O(N^2)$ であるため、サンプル数が多いと計算時間が大幅に増加します。
- **FFT**: 計算量が $O(N \log N)$ であり、非常に効率的です。



![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/208980/214332fc-8227-18c8-04b7-1af51dc2430a.png)


https://zenn.dev/masswork/articles/fft-understanding-01



## FFTの計算効率

FFTは、大規模なデータ解析やリアルタイム処理において不可欠です。その計算効率は、以下の理由から重要です。

1. **大規模データの処理**: 大量のサンプルを含むデータセットを短時間で解析可能。
2. **リアルタイム処理**: 音声や映像のリアルタイムフィルタリングや解析に適用可能。
3. **低リソース環境での実行**: 限られたコンピューティングリソースを効率的に利用。

# まとめ

以下の表にFFTのアルゴリズムの特徴とその利点を整理します。

| 項目            | 説明                                         | 利点                                       |
| --------------- | -------------------------------------------- | ------------------------------------------ |
| FFTアルゴリズム | 分割統治法を用いたDFTの最適化アルゴリズム    | 計算量 $O(N \log N)$で高速に計算可能       |
| FFTとDFTの違い  | 基本的には同じ概念だが、計算効率が異なる     | FFTは大規模データ解析において効率的        |
| 計算効率の利点  | リアルタイム処理や大規模データ解析に適用可能 | リソース効率の向上、迅速なデータ処理が可能 |

# 関連資料

https://qiita.com/kotai2003/items/364cb155f25a0646af17

https://qiita.com/kotai2003/items/577c89b20909b989dbf7

https://qiita.com/kotai2003/items/f5528f70bffa51816c78