1クロックで対数を計算する演算回路

昨日、BLANCAで作ったハードウェア・フーリエ変換機では、FFTの演算をした後、その結果を画面に表示するために、パワースペクトラムの計算をおこなっています。

その計算は、すなわち、log₁₀ √(x²+y²)の計算を行うわけですが、これをハードウェアで計算しなければなりません。
そこで、次のように回路を工夫しました。

まずx²+y²の計算です。xとyというのはある周波数での実部と虚部ですが、これはSpartan3のハードウェア乗算器を使って計算しているので、簡単に実装できます。

平方根をハードウェアで計算するのは難しいのですが、log₁₀ √P、という演算であればそれほど難しくはありません。対数の性質により、平行根の部分をlogの外に出すことができるからです。つまり、
log₁₀ √P = 1/2 log₁₀ P
だからです。

よって、この計算の中心は、logを求めることになります。

さて、ハードウェアでlogを求めるにはどうしたらよいでしょう。
二乗の和の平方根を取るような場合、元の数が16ビットなら32ビットくらいの精度で数字を扱わなければなりません。したがって、32bitの入力のlogの表を全部をテーブルに入れてしまうのは得策ではありません。
また、テーラー展開やニュートン法は大変なので採用したくありません。

そこで、私は次のように考えました。

我々が普段使っている常用対数というのは、10進数で考えた場合の(桁数-1)を表しているものです。
例えば、log₁₀ 10 = 1、log₁₀ 100 = 2、log₁₀ 1000000=6です。
1と0が並ぶ数でない場合は端数が出ます。
例えば、

それと同じように、2進数で考えた場合は、対数は2進数の桁数として計算することができます。
例えば、log₂ 10 = 1、log₂ 100 = 2、log₂ 1000000=6です。
左端以外のビットに1がつく場合は端数が出ます。

というわけで、2進数で対数を計算するには、その数字の桁数を数えればよいことになります。
つまり、
00010010101010010100101011100101
という32ビットの数字があった場合、左から数えて最初に'1'が出るビットの位置が対数をとった時の整数部となります。
上の例では、bit28がはじめに'1'になっているので、
log₂00010010101010010100101011100101 = 28.何とか
という数になります。
(左端をbit31、右端をbit0として数える)

では、「何とか」と書いた小数部はどうやって求めるかというと、その最初に'1'になったビットの右側の何ビットかを使って求めます。
つまり、8ビットの精度で
00010010101010010100101011100101
の部分と、最初に'1'になったビットを使って
1.00101010という固定小数点の数字に見立てて、対数を求めることになります。
これは10進数で言って1～2の間に必ず収まる数ですから、テーブルを使うことができます。

式で考えると、Pという数の対数を取りたい場合、

(ただし、Nは整数、1≦M<2とする)
とし、

このlogMは次のようなグラフになります。

直線で近似してしまってもいいかもしれないくらいな関数です。

つまるところ、2進数での桁数と、最初に出た'1'に続く数ビットの対数を取れば十分な精度で求められることがわかります。

今回のスペアナでは、画面のサイズが640×480ですから、対数を取った後の数字は8ビットあれば十分です。
32ビットの2進数の対数を取るわけなので、桁数で5ビットの精度があります。
よって、端数のlog₂Mの部分は3ビットあれば十分ということになります。

BLANCAに実装したハードウェア・フーリエ変換器では、次のような回路を使って、3クロックでlog₁₀ √(x²+y²)を求めることができました。

二乗の和の部分に2クロック、平方根と対数演算の部分で1クロックです。
タイミングレポートによれば、これが70MHzくらいの速さで動きます。
バレルシフタの後にもう一つフリップフロップをいれてやれば、100MHzは簡単に超えられるでしょうが、1クロックでの対数計算にこだわったので、こうなりました。

また、精度を上げたければ、対数表の部分をより精密にすることで容易に実現できます。
今回は5ビット入力3ビット出力の対数表にしたので、直接when～else文で記述してしまいましたが、Spartan3のブロックRAMに対数表をいれておけば、11ビット入力9ビット出力の対数表が作れます。整数部(桁数)は5ビットで出てくるので、最大14ビットの精度で対数が計算できるはずです。

このアルゴリズムが常識かどうかは調べていないのでわかりませんが、こんな簡単な回路で実用上十分な計算ができるのを確認できました。