雑記：サンプリング定理の話

キャラクターは架空のものです。おかしい点がありましたらご指摘いただけますと幸いです。

参考文献

Nyquist–Shannon sampling theorem - Wikipedia

f:id:cookie-box:20190101155733p:plain:w60

Nyquist–Shannon sampling theorem - Wikipedia に以下のようにあります。

関数 $x(t)$ が $B$ ヘルツを超える周波数を含まないならば^※、 $x(t)$ は $1/(2B)$ ごとにサンプリングした値から完全に復元することができる。

※ ただし、ちょうど $B$ ヘルツの正弦波を含んではならない。「 $B$ ヘルツ以上の周波数を含まないならば」とされることも多い。

…サンプリングしたのに元の関数が「完全に復元できる」とは不思議ではありませんか？

あ、ちなみにこの定理、ウィキペディアの記事名は「ナイキスト‐シャノンのサンプリング定理」となっていますが、後にコテルニコフさんという方が先にこの定理を発表していたのが発見されたので、「ナイキスト‐シャノン‐コテルニコフのサンプリング定理」ともいうようですね。まるでカルーシュ‐クーン‐タッカー条件のようです。

f:id:cookie-box:20190101160814p:plain:w60

何にせよ $x(t)$ を完全に復元できるサンプリング周波数 $2B$ をナイキストレートというんだね。他方、実際のサンプリング周波数 $f_s$ の半分 $f_s/2$ をナイキスト周波数というのか…ややこしいな。サンプリング周波数 $f_s$ でサンプリングしたときは $f < f_s/2$ を満たす周波数成分は再構築されることが保証されると。だからなぜ保証されるかが知りたいんだけど…先にエイリアシングという節で次の式が出てくる。

$\displaystyle X_s(f) := \sum_{k=-\infty}^\infty X(f - k f_s) = \sum_{n=-\infty}^\infty \frac{1}{f_s} \cdot x \left( \frac{n}{f_s} \right) e^{- 2 \pi i n f / f_s}$ これは、「もし関数 $x(t)$ を $f_s$ ごとにサンプリングしたサンプル $x(n/f_s)$ が無限に手元にあったら、それに $e^{- 2 \pi i n f / f_s}$ をかけて足したものは、周波数の世界で間隔 $f_s$ ごとに元の関数のフーリエ変換 $X(f)$ を無限に重ねていったものと等しい」という式かな。これ自体はポアソンの和公式にサンプルたちを当てはめただけだ。中辺で表される周期関数から出発してフーリエ級数展開した係数を求めたらこうなったともいえる。

Poisson の和公式 - 記憶帳

えっと、だから何なんですか？私たちはいま、サンプル $x(n/f_s)$ たちから元の関数 $x(t)$ を復元できるのかに興味があると思うんですが。

だからだよ。最右辺をみたらこれは元の関数の「離散フーリエ変換」だ。上式の主張は、「ある関数を離散フーリエ変換すると、素直に周波数成分が出てきてくれるのではなく、周波数成分が無限に『かげぶんしん』したものが出てきてしまう」といっているに他ならない。ウィキペディアの下図のようにね。

AliasedSpectrum.png

私たちは「サンプルから元の関数が復元できるのか」に興味があるけど、これは現在の文脈でもっと正確にいうと「サンプルたちから元の関数の周波数成分の情報を得て、そこから元の関数が復元できるのか」だね。そして上図が示唆することは、「サンプリング周波数 $f_s$ の半分を超える周波数成分は復元できない」だ。なぜなら、周波数成分のグラフ（青色）の $f_s/2$ を超える部分は自身の「かげぶんしん」（黄緑色）と重なって一般的には識別できなくなってしまうからね。

ちなみに、画像や音声をデジタル化するときに高周波成分が低周波なノイズになってあらわれる現象を「エイリアシング」というみたいだね。これを防ぐために予め元の情報をローパスフィルタにかけるらしいよ。

折り返し雑音 - Wikipedia

「サンプリング周波数 $f_s$ の半分を超える周波数成分は復元できない」ですか…想像するに、1秒光って1秒消えるような周期2秒の点滅を繰り返すランプがあったとして、これを1秒おきに観測するなら「1秒おきに光っていそうだ」とわかりそうですが、2秒おきに観測するならもう点滅しているかもわからなさそうですね…。他方、対象の関数 $x(t)$ の周波数成分がサンプリング周波数 $f_s$ の半分を超えない範囲に収まっていれば、 $X(f)$ が識別できるのでそれをフーリエ逆変換すればよいということなんですね。

そうなんだけど、元の関数を直接サンプルたちで表す式も続きにあるね。上で定義した「かげぶんしん付き」フーリエ変換 $X_s(f)$ からかげぶんしんを排除するため、矩形関数で $f < |f_s/2|$ の部分だけ切り取る。

$\displaystyle \begin{split} X(f) &= {\rm rect}\left( \frac{f}{f_s} \right) X_s(f) \\ & = {\rm rect}\left( \frac{f}{f_s} \right) \sum_{n=-\infty}^\infty \frac{1}{f_s} \cdot x \left( \frac{n}{f_s} \right) e^{- 2 \pi i n f / f_s} \\ & = \sum_{n=-\infty}^\infty x \left( \frac{n}{f_s} \right) \cdot \frac{1}{f_s} {\rm rect}\left( \frac{f}{f_s} \right) e^{- 2 \pi i n f / f_s} \end{split}$ 矩形関数はsinc関数のフーリエ変換だから、両辺をフーリエ逆変換することで以下を得る。 $\displaystyle x(t) = \sum_{n=-\infty}^{\infty} x \left( \frac{n}{f_s} \right) \cdot {\rm sinc}\left( f_s t - n\right)$ sinc関数や矩形関数の定義は（そもそもフーリエ変換の定義も）、冒頭の記事からもリンクがあるけど、以下に準拠するよ。

https://en.wikipedia.org/wiki/Fourier_transform#Square-integrable_functions,_one-dimensional

「矩形関数はsinc関数のフーリエ変換だから」で片付けられても…本当にそのsinc関数をフーリエ変換すると矩形関数になりますか？

$\displaystyle \begin{split} \mathcal{F}[{\rm sinc}(f_s t - n)](f) &= \int_{-\infty}^\infty {\rm sinc}\left( f_s t - n\right) e^{-2 \pi i t f}dt \\ &= \int_{-\infty}^\infty {\rm sinc}\left( f_s t' \right) e^{-2 \pi i t' f} e^{-2 \pi i n f / f_s} dt' \qquad (t' = t - n/f_s) \\ &= e^{-2 \pi i n f / f_s} \int_{-\infty}^\infty {\rm sinc} \left( f_s t' \right) e^{-2 \pi i t' f} dt' \\ &= e^{-2 \pi i n f / f_s} \frac{1}{f_s} \int_{-\infty}^\infty {\rm sinc} \left( t'' \right) e^{-2 \pi i t'' f / f_s } dt'' \qquad (t'' = f_s t') \\ &= e^{-2 \pi i n f / f_s} \frac{1}{f_s} \int_{-\infty}^\infty \frac{\sin (\pi t'')}{\pi t''} e^{-2 \pi i t'' f / f_s} dt'' \end{split}$ この積分が ${\rm rect}(f/f_s)$ になるはずですが…難しそうですね。逆に矩形関数をフーリエ逆変換しますか。 $\displaystyle \begin{split} \mathcal{F}^{-1}[{\rm rect}(f)](t) &= \int_{-\infty}^\infty {\rm rect}(f) \cdot e^{2 \pi i t f} df \\&= \int_{-1/2}^{1/2} e^{2 \pi i t f} df \\&= \left[ \frac{e^{2 \pi i t f}}{2 \pi i t} \right]_{f=-1/2}^{f=1/2}\\&=\frac{e^{\pi i t } - e^{-\pi i t}}{2 \pi i t} \\ &=\frac{\sin (\pi t)}{\pi t} = {\rm sinc}(t) \end{split}$ …確かに矩形関数のフーリエ逆変換がsinc関数なので、sinc関数のフーリエ変換は矩形関数ですね。

ここまでの話を整理すると、

サンプリング周波数 $f_s$ で取ってきた関数の値のサンプルたちから、周波数成分の情報を得ることを経由して元の関数を復元したい。＝サンプルたちをフーリエ変換してから逆フーリエ変換することで元の関数を復元したい。
サンプルたちを素直に離散フーリエ変換すると $[-f_s/2, f_s/2]$ の範囲が延々と繰り返されたものになってしまうことがわかる。ので、元の関数の周波数成分がこの範囲に収まるようにサンプリング周波数 $f_s$ を大きくとり、かつ、サンプルたちの離散フーリエ変換に対して矩形関数で $[-f_s/2, f_s/2]$ の範囲を切り取ってから逆フーリエ変換する必要がある。
「サンプルたちの離散フーリエ変換に矩形関数をかけて逆フーリエ変換したもの」は、「サンプルたちにその位置でてっぺんになるsinc関数をかけて足したもの」に他ならない。

ということですか…ん、ちょうど $f_s/2$ の周波数成分はどうなるんです？ウィキペディアの Introduction のところに、「ちょうど $B$ ヘルツの正弦波を含んではならない」というようにありましたが、正弦波限定でだめなんですか？では余弦波は大丈夫だと？

…じゃあ部長に演習問題だ。以下の関数をサンプリング周波数 $f_s$ でサンプリングしてから復元してほしい。

$x(t) = \cos(\pi f_s t)$
$x(t) = \sin(\pi f_s t)$

ええ…1. は $x( n /f_s) = \cos(n \pi)$ なので、これは $n$ が偶数のとき $1$ 、 $n$ が奇数のとき $-1$ ですね。

$\displaystyle \begin{split} x(t) &=\sum_{n=-\infty}^\infty (-1)^n {\rm sinc}\left( f_s t - n\right)=\sum_{n=-\infty}^\infty (-1)^n \frac{\sin \bigl( \pi( f_s t - n) \bigr)}{\pi( f_s t - n)} \\&=\sum_{n=-\infty}^\infty (-1)^n \frac{\sin ( \pi f_s t) \cos(n \pi ) - \cos( \pi f_s t) \sin(n \pi ) }{\pi( f_s t - n)} = \sum_{n=-\infty}^\infty \frac{\sin ( \pi f_s t)}{\pi( f_s t - n)} \\&= \sin ( \pi f_s t) \sum_{n=-\infty}^\infty \frac{1}{\pi f_s t - n \pi} \\&= \sin ( \pi f_s t) \frac{\cos(\pi f_s t) }{\sin(\pi f_s t)} = \cos(\pi f_s t) \end{split}$ ここで最後の行への式変形は以下の記事の極展開によりました。

ミッタク＝レフラーの定理 - Wikipedia

$f_s t$ が整数に一致するような $t$ ではこの変形はできませんが、逆に $f_s t$ が整数に一致しているならば最初の行からただちに $x(t)=1$ （偶数に一致しているとき）または $x(t)=-1$ （奇数に一致しているとき）なので結局如何なる $t$ でも $x(t)=\cos(\pi f_s t)$ といえるのではないでしょうか。つまり、「サンプリング周波数の半分ぴったりの余弦波は完全に復元できる」といえそうです（自信はありませんが…）。

それでは 2. は、 $x( n /f_s) = \sin(n \pi)$ なので…え、これサンプルが全て $0$ ですね。だったら復元しても $x(t)=0$ にしかなりません…しかし、なぜ余弦波と正弦波でこのような違いが… 慢心、環境の違い…。

原点を起点にサンプリングしていくなら、正弦波は波のてっぺんの位置がちょうど悪くて（サンプリングするインターバルのちょうど中間にてっぺんがきてしまって、サンプリングする点ではいつも波が全くない）、余弦波は逆にちょうどいいってことだと思う。あと、余弦波と正弦波をフーリエ変換してみてもなんでこの違いが出るのかわかると思うよ。

つづくかも

f:id:cookie-box:20191231173321p:plain:w390