離散フーリエ変換をちゃんと理解する

はじめに

以前こんな記事を書きました。
https://zenn.dev/torataro/articles/2023-02-26-fourier_transform
これはがっつり数学の話でプログラミングという観点では実用的ではないです。今回はコンピュータ内でフーリエ変換を実現する離散フーリエ変換について紹介していきます。上記記事の内容は本記事でもフォローしていくつもりですので、上記記事を読む必要はありません。

対象読者
・フーリエ解析または信号処理を少なからずとも学んだことがある。
定義
・$ii$は虚数単位$i=−1i=\sqrt{-1}$とする。
・整数全体を$Z\mathbb{Z}$、0以上の整数全体を$Z≥0\mathbb{Z}_{\geq 0}$と置く。
・$nn$が整数や0以上の整数であることを$n∈Z,n∈Z≥0n\in\mathbb{Z},n\in\mathbb{Z}_{\geq 0}$と書く
・$a⊤\mathbf{a}^{\top}$をベクトル$a\mathbf{a}$の転置とする。表示上の問題で転置を多用します。

離散フーリエ変換って？

初めに次のデータ列を考えてみます。

$$f=(f0 f1 ⋯ fN−2 fN−1)⊤ \mathbf{f}=(f_{0}\;f_{1}\;\cdots\;f_{N-2}\;f_{N-1})^{\top}$$

これはベクトル$f\mathbf{f}$の定義で、その要素として$fn,n∈Z≥0f_{n},n\in\mathbb{Z}_{\geq 0}$が格納されています。全要素数は$NN$です。要素$fnf_{n}$自体が$nn$のみに依存する関数なので、このベクトルは一次元の信号と呼ばれ^[1]、例として音声信号や株価情報などが挙げられます。このベクトルの要素に対する次の処理が離散フーリエ変換になります。

$$Fm=∑n=0N−1fnexp⁡(−i2πnmN)fn=1N∑m=0N−1Fmexp⁡(i2πnmN) \begin{align*} F_{m}&=\sum_{n=0}^{N-1}f_{n}\exp\left(-i2\pi\frac{nm}{N}\right)\\ f_{n}&=\frac{1}{N}\sum_{m=0}^{N-1}F_{m}\exp\left(i2\pi\frac{nm}{N}\right) \end{align*}$$

前者が離散フーリエ変換、後者はその逆変換で逆離散フーリエ変換と呼びます。当然、変換＆逆変換と読んでいるくらいなので行ったり来たりできる関係にありますが、なぜ可能なのでしょうか？線形代数の知識を使って説明します。

離散フーリエ変換の原理

内積と一次結合

次のベクトル$a,b\bm{a},\bm{b}$について

$$a=(a0 a1 a2)⊤, b=(b0 b1 b2)⊤ \bm{a}=(a_{0}\;a_{1}\;a_{2})^{\top},\;\bm{b}=(b_{0}\;b_{1}\;b_{2})^{\top}$$

ベクトル$a,b\bm{a},\bm{b}$の要素は複素数であるとします。ここで標準基底

$$e0=(1 0 0)⊤, e1=(0 1 0)⊤, e2=(0 0 1)⊤ \bm{e}_{0}=(1\;0\;0)^{\top},\;\bm{e}_{1}=(0\;1\;0)^{\top},\;\bm{e}_{2}=(0\;0\;1)^{\top}$$

を使うと$a\bm{a}$は、

$$a=a0e0+a1e1+a2e2 \bm{a}=a_{0}\bm{e}_{0}+a_{1}\bm{e}_{1}+a_{2}\bm{e}_{2}$$

と書けます。このような足し合わせを一次結合といいます^[2]。このとき内積$⟨a,b⟩\langle \bm{a},\bm{b}\rangle$は次で定義されます。

$$⟨a,b⟩=∑n=03−1anbn∗ \langle \bm{a},\bm{b}\rangle=\sum_{n=0}^{3-1}a_{n}b_{n}^{*}$$

特徴的なのは$b\bm{b}$の要素に複素共役がかかっていることです。そうすれば$⟨a,a⟩\langle \bm{a},\bm{a}\rangle$と同じベクトル同士の内積を計算したときベクトルの大きさが得られます。もし$a,b\bm{a},\bm{b}$が$NN$個を要素に持つベクトルならば、その内積は

$$⟨a,b⟩=∑n=0N−1anbn∗ \langle \bm{a},\bm{b}\rangle=\sum_{n=0}^{N-1}a_{n}b_{n}^{*}$$

とそのまま拡張した形になります。話を戻します。ベクトル$a\bm{a}$と標準基底$e0\bm{e}_{0}$との内積を取ると、

$$⟨a,e0⟩=a0⋅1+a1⋅0+a2⋅0=a0 \langle \bm{a},\bm{e}_{0}\rangle=a_{0}\cdot 1 + a_{1}\cdot 0 + a_{2}\cdot 0 = a_{0}$$

基底の係数$a0a_{0}$が抽出できます。つまり標準基底は自身の係数を抽出する抽出特性を有しているということです。なぜ抽出できるかというと、基底同士の内積を次のように計算したとき

$$⟨en,em⟩={1n=m0n≠m \langle \bm{e}_{n},\bm{e}_{m}\rangle= \left\{ \begin{array}{ll} 1 & n=m \\ 0 & n\ne m \end{array} \right.$$

同じ基底ならば$11$を、異なる基底ならば$00$を取るからです。これを直交性といいます。直交性について同じ基底のとき、内積の計算結果が必ずしも$11$を取る必要はなく、$00$以外の数値であればよいです。ただ異なる基底で必ず$00$を取る必要があります。$00$以外の数値を取るならば、異なる基底の係数も抽出されてしまいます。

最後に、さきほどの内積の結果を使えば次の一次結合でベクトル$a\bm{a}$が再度表現できます。

$$a=⟨a,e0⟩e0+⟨a,e1⟩e1+⟨a,e2⟩e2 \bm{a}=\langle \bm{a},\bm{e}_{0}\rangle\bm{e}_{0} +\langle \bm{a},\bm{e}_{1}\rangle\bm{e}_{1} +\langle \bm{a},\bm{e}_{2}\rangle\bm{e}_{2}$$

とにかく重要なのは抽出特性と内積による線形結合です。この二つの性質が離散フーリエ変換と逆変換を成り立たせています。それを次に紹介します。

逆離散フーリエ変換と新たな基底

先ほど標準基底が直交性を有することによる抽出特性と、標準基底との内積で元のベクトルが再構築できたのを確認しました。このような基底はほかにもあり、その例として次のベクトルを紹介します。

$$em=(exp⁡(i2π0⋅mN) exp⁡(i2π1⋅mN) ⋯ exp⁡(i2π(N−1)⋅mN))⊤ \mathbf{e}_{m}=\left( \exp\left(i2\pi\frac{0\cdot m}{N}\right)\; \exp\left(i2\pi\frac{1\cdot m}{N}\right)\; \cdots\; \exp\left(i2\pi\frac{(N-1)\cdot m}{N}\right) \right)^{\top}$$

ここで$m∈Z≥0m\in\mathbb{Z}_{\geq 0}$です。このベクトルに対して次のような線形結合を考えます。

$$f=1N∑m=0N−1Fmem \mathbf{f}=\frac{1}{N}\sum_{m=0}^{N-1}F_{m}\mathbf{e}_{m}$$

このベクトル$f\mathbf{f}$のとある要素$fnf_{n}$を参照すると、

$$fn=1N∑m=0N−1Fmexp⁡(i2πnmN) f_{n}=\frac{1}{N}\sum_{m=0}^{N-1}F_{m}\exp\left(i2\pi\frac{nm}{N}\right)$$

まぎれもなく逆離散フーリエ変換になります。これが逆変換の正体です。そして標準基底の係数が抽出できたのと同じように各基底の係数$FmF_{m}$をこの基底でも抽出できるでしょうか？それを次に示します。

抽出特性と離散フーリエ変換

基底が抽出特性を満たすには直交性を持っていなければなりませんでした。それを確認するために、内積$⟨em,em′⟩\langle \mathbf{e}_{m},\mathbf{e}_{m'}\rangle$を計算します。ここで$m′∈Z≥0m'\in\mathbb{Z}_{\geq 0}$です。

• $m=m′m=m'$のとき

$$⟨em,em′⟩=∑n=0N−1exp⁡(i2πnmN)exp⁡(−i2πnm′N)=∑n=0N−1exp⁡(i2πn(m−m′)N) \langle \mathbf{e}_{m},\mathbf{e}_{m'}\rangle= \sum_{n=0}^{N-1}\exp\left(i2\pi\frac{nm}{N}\right)\exp\left(-i2\pi\frac{nm'}{N}\right) =\sum_{n=0}^{N-1}\exp\left(i2\pi\frac{n(m-m')}{N}\right)$$

より$m−m′=0m-m'=0$から

$$exp⁡(i2πn(m−m′)N)=1 \exp\left(i2\pi \frac{n(m-m')}{N}\right)=1$$

なので、

$$⟨em,em′⟩=∑n=0N−11=N \langle \mathbf{e}_{m},\mathbf{e}_{m'}\rangle=\sum_{n=0}^{N-1}1=N$$

です。

• $m≠m′m\neq m'$のとき

$$⟨em,em′⟩=∑n=0N−1exp⁡(i2πnmN)exp⁡(−i2πnm′N)=∑n=0N−1exp⁡(i2πn(m−m′)N) \langle \mathbf{e}_{m},\mathbf{e}_{m'}\rangle= \sum_{n=0}^{N-1}\exp\left(i2\pi\frac{nm}{N}\right)\exp\left(-i2\pi\frac{nm'}{N}\right) =\sum_{n=0}^{N-1}\exp\left(i2\pi\frac{n(m-m')}{N}\right)$$

この式展開までは同じ。ここで$k=m−m′k=m-m'$と置いてしまいましょう。そうすると、

$$⟨em,em′⟩=∑n=0N−1exp⁡(i2πnkN)=∑n=0N−1exp⁡(i2πkN)n \langle \mathbf{e}_{m},\mathbf{e}_{m'}\rangle =\sum_{n=0}^{N-1}\exp\left(i2\pi\frac{nk}{N}\right) =\sum_{n=0}^{N-1}\exp\left(i2\pi\frac{k}{N}\right)^{n}$$

という公比$exp⁡(i2πk/N)\exp\left(i2\pi k/N\right)$の総和になるので、等比数列の和の公式から、

$$⟨em,em′⟩=exp⁡(i2πk)−1exp⁡(i2πkN)−1 \langle \mathbf{e}_{m},\mathbf{e}_{m'}\rangle=\frac{\displaystyle\exp\left(i2\pi k\right)-1}{\exp\left(\displaystyle i2\pi \frac{k}{N}\right)-1}$$

となります。ここで$m,m′∈Z≥0m,m'\in\mathbb{Z}_{\geq 0}$であることを思い出すと、$k=m−m′∈Zk=m-m'\in\mathbb{Z}$なので、

$$exp⁡(i2πk)=1 \exp\left(i2\pi k\right)=1$$

より、

$$⟨em,em′⟩=0 \langle \mathbf{e}_{m},\mathbf{e}_{m'}\rangle=0$$

です。

• まとめ

これらの結果をまとめると、次のように直交性を記述できます。

$$⟨em,em′⟩={Nn=m0n≠m \langle \mathbf{e}_{m},\mathbf{e}_{m'}\rangle= \left\{ \begin{array}{ll} N & n=m \\ 0 & n\ne m \end{array} \right.$$

よって次の内積

$$⟨f,em′⟩=∑n=0N−1fnexp⁡(−i2πnmN)=Fm \langle \mathbf{f},\mathbf{e}_{m'}\rangle=\sum_{n=0}^{N-1}f_{n}\exp\left(-i2\pi\frac{nm}{N}\right)=F_{m}$$

は係数$FmF_{m}$を抽出します。これが離散フーリエ変換です。

信号処理の観点から

フーリエ級数展開が教えてくれるのは、任意の信号$f(t)f(t)$がいろんな周波数の正弦波の足し合わせで表されるということです。式で記述すると信号$f(t)f(t)$は次のようになります^[3]。

$$f(t)=∑n=−∞∞Ancos⁡(2πνnt+θn) f(t)=\sum_{n=-\infty}^{\infty}A_{n}\cos(2\pi\nu_{n}t + \theta_{n})$$

正弦波として$sin⁡\sin$を思い浮かべる人もいると思いますが、$sin⁡\sin$も$cos⁡\cos$も区別せずに両方とも正弦波と呼びます。それよりも$AnA_{n}$を解析することで信号$f(t)f(t)$が周波数$νn\nu_{n}$の正弦波をどれだけ含む^[4]かが分かること、$θn\theta_{n}$を解析することで正弦波がどれだけずれているか分かることのほうがが重要です。それを知るための手段がフーリエ変換です。

フーリエ変換と逆フーリエ変換

フーリエ変換と逆フーリエ変換は次の定義です。

$$F(ν)=∫−∞∞f(t)exp⁡(−i2πνt)dtf(t)=∫−∞∞F(ν)exp⁡(i2πνt)dν \begin{align*} F(\nu)&=\int_{-\infty}^{\infty} f(t)\exp(-i2\pi \nu t)dt\\ f(t)&=\int_{-\infty}^{\infty} F(\nu)\exp(i2\pi \nu t)d\nu \end{align*}$$

前者がフーリエ変換、後者が逆フーリエ変換です。特に$f(t),F(ν)f(t),F(\nu)$のフーリエ変換、逆変換は

$$F[f(t)]=F(ν), F−1[F(ν)]=f(t), \mathcal{F}[f(t)]=F(\nu),\;\mathcal{F}^{-1}[F(\nu)]=f(t),$$

と書かれることが多いです。フーリエ変換を使えば、時間領域$tt$に存在する$f(t)f(t)$を周波数領域$ν\nu$にマッピングし、時間とは異なる観点から情報を捉えられるようになります。この$F(ν)F(\nu)$を調べることで次の情報が得られます。$Arg\text{Arg}$は複素数の偏角です。

$∣F(ν)∣\lvert F(\nu)\rvert$	$Arg(F(ν))\text{Arg}(F(\nu))$
正弦波の振幅を反映。信号$f(t)f(t)$が周波数$ν\nu$の正弦波をどれだけ含んでいるか分かる。	正弦波の初期位相を反映。周波数$ν\nu$の正弦波の山の位置が分かる。

振幅、初期位相は次の正弦波の$A,θ0A,\theta_{0}$に該当します。

$$Acos⁡(2πνt+θ0) A\cos(2\pi\nu t + \theta_{0})$$

ここで逆フーリエ変換の積分対象である$F(ν)exp⁡(i2πνt)F(\nu)\exp(i2\pi \nu t)$は、$θ(ν)=Arg(F(ν))\theta(\nu)=\text{Arg}(F(\nu))$と置けば、

$$F(ν)exp⁡(i2πνt)=∣F(ν)∣eiθ(ν)exp⁡(i2πνt)=∣F(ν)∣exp⁡[i(2πνt+θ(ν))] F(\nu)\exp(i2\pi \nu t)=\lvert F(\nu)\rvert e^{i\theta(\nu)}\exp(i2\pi \nu t)=\lvert F(\nu)\rvert\exp\left[i(2\pi \nu t + \theta(\nu))\right]$$

$exp⁡\exp$の中身が$cos⁡\cos$に一致することが分かります。実際$exp⁡(i2πνt)\exp(i2\pi \nu t)$は複素正弦波と呼ばれ、逆フーリエ変換自体も信号$f(t)f(t)$の(複素)正弦波の足し合わせを表しているのです。厳密な比較ではありませんが、上記から$∣F(ν)∣\lvert F(\nu)\rvert$は$AA$、$Arg(F(ν))\text{Arg}(F(\nu))$は$θ0\theta_{0}$に対応していることが感じ取れるはずです。

離散フーリエ変換では時間領域の信号は$fnf_{n}$、それを周波数領域にマッピングした結果は$FmF_{m}$になります。フーリエ変換を離散化することでそれぞれを比較しましょう。

デルタ関数と標本化

先にデルタ関数を紹介します。デルタ関数$δ(t)\delta(t)$は次の定義です。

$$∫−∞∞f(t)δ(t−t′)dt=∫−∞∞f(t)δ(t′−t)dt=f(t′)∫−∞∞δ(t)dt=1 \begin{align*} \int_{-\infty}^{\infty} f(t)\delta(t-t')dt&=\int_{-\infty}^{\infty} f(t)\delta(t'-t)dt=f(t') \\ &\int_{-\infty}^{\infty} \delta(t)dt=1 \end{align*}$$

デルタ関数は何か実態があるわけでなくこの二式で定義されます。前者がデルタ関数の抽出特性を表しています。とある時間$t=t′t=t'$での関数$ff$の値$f(t′)f(t')$を抽出しています。後者の式はデルタ関数が$11$で正規化されることを表しています。ただこの定義だとイメージが湧きにくいので次のように書かれることもあります。

$$δ(t)={∞t=00t≠0 \delta(t)= \left\{ \begin{array}{ll} \infty & t=0 \\ 0 & t\ne 0 \end{array} \right.$$

これはインパルス信号と呼ばれるもので、もし図化するならば次のようになります。

続いて標本化です。音などを考えると信号は連続であることが多いです。そしてこの信号をメモリに格納することを考えれば、この連続な信号から値を選ぶ必要がでてきます。その操作が標本化です。サンプリングとも言われます。標本化として次の図のような方法が一般的でしょう。

この標本化では、とある間隔$Δt\Delta t$で信号を選んでいます。選ばれた信号は次のようにベクトルで格納することができます。

$$f=(⋯ f(−2Δt) f(−Δt) f(0) f(Δt) f(2Δt) ⋯ )⊤ \mathbf{f}=(\cdots\;f(-2\Delta t)\;f(-\Delta t)\;f(0)\;f(\Delta t)\;f(2\Delta t)\;\cdots)^{\top}$$

この選ばれた信号に対して後々積分ができるように次の列を考えます。

$$sΔt(t)=∑n=−∞∞δ(t−nΔt) s_{\Delta t}(t)=\sum_{n=-\infty}^{\infty}\delta(t-n\Delta t)$$

これを図化すると次のようになります。

選んだ場所でデルタ関数の角が立っていることが確認できます。これはくし型関数と呼ばれるものです。くし型関数使えば

$$fs(t)=f(t)sΔt(t)=∑n=−∞∞f(nΔt)δ(t−nΔt) f_{s}(t)=f(t)s_{\Delta t}(t)=\sum_{n=-\infty}^{\infty}f(n\Delta t)\delta(t-n\Delta t)$$

のように標本化したものを積分できるようになります。そしてこのくし型関数ですが$Δt\Delta t$を一周期とする周期関数なので複素フーリエ級数展開（Appendix参照）を使って次の様に記述することもできます。

$$sΔt(t)=1Δt∑n=−∞∞exp⁡(i2πntΔt) s_{\Delta t}(t)=\frac{1}{\Delta t}\sum_{n=-\infty}^{\infty}\exp\left(i2\pi\frac{nt}{\Delta t}\right)$$

この式は後で使います。

フーリエ変換の離散化

$f(t)f(t)$のフーリエ変換が$F(ν)F(\nu)$であるならば、標本化後のフーリエ変換はどうなるでしょうか？$fs(t)f_{s}(t)$をフーリエ変換することで調べましょう。その前に畳み込み積分と積のフーリエ変換の公式を紹介します。畳み込み積分は二つの関数$f=f(t),g=g(t)f=f(t),g=g(t)$を用いて次式で定義されます。

$$(f∗g)(t)=∫−∞∞f(τ)g(t−τ)dτ (f*g)(t)=\int_{-\infty}^{\infty}f(\tau)g(t-\tau)d\tau$$

ここで$∗*$は畳み込み積分を示す演算子として定義します。また関数の積$f(t)g(t)f(t)g(t)$のフーリエ変換は$f(t),g(t)f(t),g(t)$のフーリエ変換を$F=F(ν),G=G(ν)F=F(\nu),G=G(\nu)$と置けば、

$$F[f(t)g(t)]=(F∗G)(ν)=∫−∞∞F(ν′)G(ν−ν′)dν′ \mathcal{F}[f(t)g(t)]=(F*G)(\nu)=\int_{-\infty}^{\infty}F(\nu')G(\nu-\nu')d\nu'$$

と変換結果の畳み込み積分で表されます（証明はAppendix参照）。$fs(t)=f(t)sΔt(t)f_{s}(t)=f(t)s_{\Delta t}(t)$のフーリエ変換を$Fs(ν)F_{s}(\nu)$と置き、上記結果を使えば、

$$Fs(ν)=(F∗SΔt)(ν)=∫−∞∞F(ν′)SΔt(ν−ν′)dν′ F_{s}(\nu)=(F*S_{\Delta t})(\nu)=\int_{-\infty}^{\infty}F(\nu')S_{\Delta t}(\nu-\nu')d\nu'$$

となります。$SΔt=SΔt(ν)S_{\Delta t}=S_{\Delta t}(\nu)$はくし型関数$sΔt(t)s_{\Delta t}(t)$のフーリエ変換で次のような形になります。

$$SΔt(ν)=F[sΔt(t)]=∫−∞∞∑n=−∞∞δ(t−nΔt)exp⁡(−i2πνt)dt=∑n=−∞∞∫−∞∞δ(t−nΔt)exp⁡(−i2πνt)dt=∑n=−∞∞exp⁡(−i2πνnΔt) \begin{align*} S_{\Delta t}(\nu)=\mathcal{F}[s_{\Delta t}(t)]&=\int_{-\infty}^{\infty}\sum_{n=-\infty}^{\infty}\delta(t-n\Delta t)\exp(-i2\pi \nu t)dt \\ &=\sum_{n=-\infty}^{\infty}\int_{-\infty}^{\infty}\delta(t-n\Delta t)\exp(-i2\pi \nu t)dt\\ &=\sum_{n=-\infty}^{\infty}\exp(-i2\pi \nu n\Delta t) \end{align*}$$

ここで上から三行目のイコールの時点でデルタ関数の抽出特性を使いました。この結果とくし型関数の複素フーリエ級数展開の結果を比較すると、

$$SΔt(ν)=1Δts1Δt(ν)=1Δt∑n=−∞∞δ(ν−nΔt) S_{\Delta t}(\nu)=\frac{1}{\Delta t}s_{\frac{1}{\Delta t}}(\nu)=\frac{1}{\Delta t}\sum_{n=-\infty}^{\infty}\delta\left(\nu-\frac{n}{\Delta t}\right)$$

と最終的にくし型関数になることが分かります^[5]。この結果からデルタ関数の抽出特性を使えば

$$Fs(ν)=∫−∞∞F(ν′)1Δt∑n=−∞∞δ(ν−ν′−nΔt)dν′=1Δt∑n=−∞∞∫−∞∞F(ν′)δ((ν−nΔt)−ν′)dν′=1Δt∑n=−∞∞F(ν−nΔt) \begin{align*} F_{s}(\nu)&=\int_{-\infty}^{\infty}F(\nu')\frac{1}{\Delta t}\sum_{n=-\infty}^{\infty}\delta\left(\nu-\nu'-\frac{n}{\Delta t}\right)d\nu'\\ &=\frac{1}{\Delta t}\sum_{n=-\infty}^{\infty}\int_{-\infty}^{\infty}F(\nu')\delta\left(\left(\nu-\frac{n}{\Delta t}\right)-\nu'\right)d\nu'\\ &=\frac{1}{\Delta t}\sum_{n=-\infty}^{\infty}F\left(\nu-\frac{n}{\Delta t}\right) \end{align*}$$

となります。数式をもとに$Fs(ν)F_{s}(\nu)$を描くと次のようなイメージです。

$F(ν)F(\nu)$が一つの山を成し、$νs=1/Δt\nu_{s}=1/\Delta t$の周期で山の頂点が現れることが確認できます。$νs\nu_{s}$はサンプリング周波数といい、1秒間に何回サンプリングするか決めるものです。当然沢山サンプリングすると山と山の間隔は離れます。この話は次の標本化定理の紹介で行います。

離散フーリエ変換の話に戻りましょう。実際$Δt\Delta t$で標本化したならば、コンピュータ上で格納できる最大周波数は$νs\nu_{s}$になります。また離散フーリエ変換した結果$FmF_{m}$は、変換対象のデータ数と同じ$NN$個得られるので、フーリエ変換後の結果を離散化するならば次の方法になります。

つまり周波数領域で離散化するというのは、山の頂点から次の山の頂点の間で$NN$個値を取ってくることに他ならないわけです。この離散化の間隔を$Δν\Delta \nu$と置けば次の式が成り立ちます。

$$ΔtΔν=1N \Delta t\Delta \nu = \frac{1}{N}$$

量子力学の不確定性原理のような数式ですね。この式から$Δt\Delta t$と$Δν\Delta \nu$の大きさはトレードオフの関係にあることが分かります。周波数領域でも一定の精度を担保したいならばデータを増やすしかないということです。

標本化定理とエイリアシング

標本化後の信号のフーリエ変換$Fs(ν)F_{s}(\nu)$より、本来得たい信号の結果$F(ν)F(\nu)$が繰り返し現れることが確認できました。そうすると懸念されるのは$F(ν)F(\nu)$同士が重ね合わさるところです。図示すると灰色の個所になります。

この重ね合わさった部分の周波数領域は$F(ν)F(\nu)$が取る本来の値とは異なるため、そのまま逆フーリエ変換をすると正しい信号$f(t)f(t)$を再現できなくなります。これをエイリアシングといいます。

もし信号$f(t)f(t)$が最大周波数$νmax\nu_{\text{max}}$までの正弦波の重ね合わせで構成されているならば、逆フーリエ変換で信号$f(t)f(t)$を回復するために次式を満たしている必要があります。

$$νs≥2νmax \nu_{s}\geq 2\nu_\text{max}$$

これは標本化定理と呼ばれるもので、$F(ν)F(\nu)$が重ね合わさらない条件になります。信号処理論で最も重要な式といってもよいかもしれません。標本化定理を満たしているとき次のようなイメージになります。

エイリアシングを起こさない条件が明確になりましたが、エイリアシングってどんな状態を表すのでしょうか？$νmax\nu_{\text{max}}$の周波数を持つ正弦波でもって説明します。まず正弦波の中から青点で沢山サンプリングします。

上図が正弦波をサンプリングした結果です。当然、この時サンプリングした点と点同士をつなぐとしっかりとオレンジの正弦波に追随していることが分かります。この点を極限まで減らした時、それでも正弦波を再現できるサンプリング数はいくつでしょうか？結論次の図の通りです。

このとき正弦波の山の頂上と谷の底でサンプリングを行いました。これらの点と点をつなぐと正弦波というよりは三角波になりますが、それでも正弦波の振動を表現することができています。実際、標本化定理は最大周波数を持つ正弦波の一回の振動で二回以上サンプリングすれば、元の信号を復元することができると主張しています。二回でのサンプリング結果が上の図です。

ではエイリアシングの場合どうなるでしょうか？それが次の図です。

エイリアシングは正弦波の振動をとらえきれない（サンプリング数が足りていない）ことで発生する現象になります。このとき点と点をつなぐと$νs−νmax\nu_{s}-\nu_{\text{max}}$の低周波数に折り返した正弦波が出現します。ゆえにエイリアシングは折り返し雑音とも呼ばれます。

最後に

離散フーリエ変換は初めにも紹介した通り、コンピュータ上で計算できるフーリエ変換になります。ただ離散フーリエ変換がフーリエ変換から導かれるというよりは、離散フーリエ変換が本来のフーリエ変換と共通する性質（推移則など）を持っているため、コンピュータ上での周波数領域へのマッピング方法として離散フーリエ変換が採用されていると捉えるほうがよいでしょう。

離散フーリエ変換を行列化すると、ユニタリ行列が現れたりともっと面白い性質があるのですが、長くなりそうなのでここらで終わりにします。最後まで読んでいただきありがとうございました！

Appendix

複素フーリエ級数展開

複素フーリエ級数展開の定義は次の通りである。

$$f(t)=∑n=−∞∞cnexp⁡(i2πntT)cn=1T∫−T/2T/2f(t)exp⁡(−i2πntT)dt \begin{align*} f(t)&=\sum_{n=-\infty}^{\infty}c_{n}\exp\left(i2\pi\frac{nt}{T}\right)\\ c_{n}&=\frac{1}{T}\int_{-T / 2}^{T / 2}f(t)\exp\left(-i2\pi\frac{nt}{T}\right)dt \end{align*}$$

ただし複素フーリエ級数展開を満たすものは$f(t)=f(t+T)f(t)=f(t+T)$の周期関数である。くし型関数の時$T=ΔtT=\Delta t$であり、$cn=1/Δtc_{n}=1/\Delta t$となる。

$F[f(t)g(t)]=(F∗G)(ν)\mathcal{F}[f(t)g(t)]=(F*G)(\nu)$の証明

$(F∗G)(ν)(F*G)(\nu)$の逆フーリエ変換が$f(t)g(t)f(t)g(t)$になることを証明する。

$$F−1[(F∗G)(ν)]=∫−∞∞(∫−∞∞F(ν′)G(ν−ν′)dν′)exp⁡(i2πνt)dν=∫−∞∞F(ν′)(∫−∞∞G(ν−ν′)exp⁡(i2πνt)dν)dν′ \begin{align*} \mathcal{F}^{-1}[(F*G)(\nu)]&=\int_{-\infty}^{\infty}\left(\int_{-\infty}^{\infty}F(\nu')G(\nu-\nu')d\nu'\right)\exp\left(i2\pi\nu t\right)d\nu\\ &=\int_{-\infty}^{\infty}F(\nu')\left(\int_{-\infty}^{\infty}G(\nu-\nu')\exp\left(i2\pi\nu t\right)d\nu\right)d\nu'\\ \end{align*}$$

ここで$s=ν−ν′s=\nu-\nu'$と置けば、$ν=s+ν′\nu=s+\nu'$なので

$$F−1[(F∗G)(ν)]=∫−∞∞F(ν′)(∫−∞∞G(s)exp⁡(i2π(s+ν′)t)ds)dν′=(∫−∞∞F(ν′)exp⁡(i2πν′t)dν′)(∫−∞∞G(s)exp⁡(i2πst)ds)=F−1[F(ν′)]F−1[G(s)]=f(t)g(t) \begin{align*} \mathcal{F}^{-1}[(F*G)(\nu)]&=\int_{-\infty}^{\infty}F(\nu')\left(\int_{-\infty}^{\infty}G(s)\exp\left(i2\pi(s+\nu') t\right)ds\right)d\nu'\\ &=\left(\int_{-\infty}^{\infty}F(\nu')\exp\left(i2\pi \nu' t\right)d\nu'\right) \left(\int_{-\infty}^{\infty}G(s)\exp\left(i2\pi s t\right)ds\right)\\ &=\mathcal{F}^{-1}[F(\nu')]\mathcal{F}^{-1}[G(s)]=f(t)g(t) \end{align*}$$

よって

$$F[f(t)g(t)]=(F∗G)(ν) \mathcal{F}[f(t)g(t)]=(F*G)(\nu)$$

である。■

余談であるが

$$F[(f∗g)(t)]=F(ν)G(ν) \mathcal{F}[(f*g)(t)]=F(\nu)G(\nu)$$

も成り立つ。証明の仕方は変わらない。(むしろこっちのほうがよく取り上げられる。)

参考文献

和田 成夫（著）「よくわかる信号処理」森北出版株式会社

脚注

1. もちろんベクトル的には$NN$次元の空間を張ることができますが、信号処理では次元の意味合いが異なることに注意してください。

2. 一次結合ではなく線形結合と呼ばれることもあります。

3. これはフーリエ級数展開の一つの表現方法です。周波数$νn\nu_{n}$はとびとびの値を取りますが、周波数も連続にし、複素数まで拡張すると逆フーリエ変換になります。

4. $2cos⁡θ2\cos\theta$の正弦波を含んでいるというのは$cos⁡θ+cos⁡θ\cos\theta + \cos\theta$で二つの正弦波$cos⁡θ\cos\theta$を含んでいるという意味になります。$0.1cos⁡θ0.1\cos\theta$の正弦波を二十個ととらえても問題ないです。いずれにしても「振幅が大きい」＝「信号$f(t)f(t)$は正弦波を多く含んでいる」と捉えます。

5. この比較では$∑n=−∞∞exp⁡(−i2πnθ)=∑n′=−∞∞exp⁡(i2πn′θ)\sum_{n=-\infty}^{\infty}\exp(-i2\pi n\theta)=\sum_{n'=-\infty}^{\infty}\exp(i2\pi n'\theta)$を使っています。