ＦＭ音源プログラム (10) -- オペレータ (3)

今回は、「表の分割」と「補間」についての話です。
基本となるのは三角関数の加法公式です。
$\qquad \sin(\alpha+\beta) = \sin(\alpha)\cdot\cos(\beta)+\cos(\alpha)\cdot\sin(\beta)$
前回述べた、テーブルは１周期の 1/4 あれば十分というのを、加法定理を使って再び示すと、
$\sin(\frac{\pi}{2}+x)=\sin(\frac{\pi}{2})\cdot\cos(x) + \cos(\frac{\pi}{2})\cdot \sin(x) = \cos(x) = \sin(\frac{\pi}{2}-x)$
$\sin(\frac{2\pi}{2}+x)=\sin(\pi)\cdot\cos(x) + \cos(\pi)\cdot \sin(x) = -\sin(x)$
$\sin(\frac{3\pi}{2}+x)=\sin(\frac{3\pi}{2})\cdot\cos(x) + \cos(\frac{3\pi}{2})\cdot \sin(x) = -\cos(x) = -\sin(\frac{\pi}{2}-x)$
となります。
いま、サイン波テーブルのインデクスが $N$ ビット、つまり、表のエントリ数が $2^{\small N}$ として、インデクスを下位の $M$ ビットと、上位の $N-M$ ビットに分けることを考えます。
具体的には、インデクスを $k$ として、 $k$ を $2^{\small M}$ で割った商 $q$ と余り $r$ に分けます。
$\qquad k = q \cdot 2^{\small M} + r$
ここで、 $0 \le q < 2^{\small N-M}$ 、 $0 \le r < 2^{\small M}$ です。
これを、もとの三角関数での表現に直すと、
$\qquad \sin \left ( \frac{2\pi\cdot(q\cdot 2^{M} + r)}{2^{N}} \right ) =\sin(2\pi \cdot 2^{\small M-N}\cdot q + 2\pi \cdot 2^{\small -N}\cdot r )$
となります。　これに加法定理を適用すると、
$\begin{eqnarray*}\qquad\sin(2\pi \cdot 2^{\small M-N}\cdot q + 2\pi \cdot 2^{\small -N}\cdot r ) &=& \sin(2\pi \cdot 2^{\small M-N}\cdot q)\cdot \cos(2\pi \cdot 2^{\small -N}\cdot r )\\ &+&\cos(2\pi \cdot 2^{\small M-N}\cdot q)\cdot \sin(2\pi \cdot 2^{\small -N}\cdot r )\end{eqnarray*}$
となります。
$\sin(2\pi \cdot 2^{\small M-N}\cdot q)$ をテーブルで表現すると、 $N-M$ ビット幅のインデクスを持つ $2^{\small N-M}$ エントリのテーブルになります。
同様に、 $\sin(2\pi \cdot 2^{\small -N}\cdot r )$ は $M$ ビット幅のインデクスを持つ $2^{\small M}$ エントリのテーブルになります。
したがって、この加法定理の式の右辺の計算では、使用するテーブルは小さなサイズのテーブルに分割され、そのテーブルのエントリ数の合計は、サイン波テーブルと、コサイン波テーブルを共用した場合、
$\qquad 2^{\small N-M} + 2^{\small M}$
になります。 sin / cos テーブルを別に持つ場合は、この倍になります。
このエントリ数の合計を $M$ について微分してゼロと置き、最小値となる $M$ を求めると、
$\qquad M = N / \, 2$
となります。
$N$ が偶数の場合は、エントリ数 $2^{\small N/2}$ の、同じ大きさのテーブルが２個で構成される時が最小で、総エントリ数は $2^{\small (N/2)+1}$ になります。
いま、 $N = 16$ とすると、元の式、つまり、ひとつのテーブルを使う場合のテーブルサイズが 64 K エントリなのに対し、加法定理を利用した計算では、 $2^{16/2} = 2^8 = 256$ エントリの表ふたつで済むことになります。
ただし、テーブルひとつの方法ではテーブル・ルックアップ 1 回で済むのに、この方式では、

テーブル・ルックアップ 4 回
乗算 2 回
加算 1 回

の計算コストがかかることになります。
もちろん、 $N$ が奇数の場合は、２種の表は同じ大きさにはならず、 $2^{(N+1)/2}$ エントリの表と $2^{(N-1)/2}$ エントリの表で構成されることになります。
ここまでは、表を分割してサイズを小さくする方法の話でしたが、今度は、 $M$ が小さい場合について考えてみます。
$M$ が小さければ $2\pi \cdot 2^{\small -N}\cdot r$ も小さく、
$\qquad \sin(2\pi \cdot 2^{\small -N}\cdot r ) = 2\pi \cdot 2^{\small -N}\cdot r$
$\qquad \cos(2\pi \cdot 2^{\small -N}\cdot r ) = 1$
と見なせますから、 $M$ 側の表が不要になり、計算量は、

テーブル・ルックアップ 2 回
乗算 1 回
加算 1 回

になります。　 $M$ が 2 ビットとか 3 ビットとかの小さい値の場合は、本格的な乗算でなくても、ビット・シフトおよび加算で実現できます。
つまり、この場合、加法定理の式をテーブルサイズ削減のためではなく、「補間」のために使うことになります。
さらに、三角関数の場合、「性質の良い」関数なので、表の隣のエントリとの間の単純な直線補間でも誤差はあまり大きくなりません。
ＦＭ音源プログラムの場合、実行時間が増えるのを嫌って、表の分割も補間もしていません。