定数による除算

[←]　[↑]　[→]

---

c個のデータの平均値を求めるときなど定数による除算1/cが必要になる。RTLでそのまま1/cと書いても合成できるみたいだが、FPGAには乗算器が備わっているので乗算に置き換えた方がよい。すなわち次式のように近似すれば、定数cのわり算が定数mのかけ算とnビットの右シフトで実装できる。

　1/c ≒ m/2ⁿ

◇

Nビットの整数aを整数c (定数)でわり算した結果a/cを整数で求めるとき、与えられたcに対してmとnはどう決めればよいだろうか。

乗数mはnから次のように決まる。

　　m = 整数部[2ⁿ/c] , ε= 2ⁿ/c - m , 四捨五入-0.5≦ε＜0.5 …(1)

シフト数nは大きいほど精度がよくなるが、大きすぎても無駄なので、除算結果の誤差が

　　δ= a/c - 整数部[a*m/2ⁿ] , 四捨五入-0.5≦δ＜0.5 …(2)

となるように選べばよい。ここで誤差δはa*m/2ⁿの丸め誤差とεの寄与と2つの要因がある。

　　δ= (a*m/2ⁿ - 整数部[a*m/2ⁿ]) + (a*ε/2ⁿ)

丸め誤差は約cで割った余りになるから隣接c個のaについてチェックすればよく、εの寄与はaに比例するのでaの最大値付近でチェックすればよい。結局(2)についてa=2^N-1 から2^N-cについてチェックすればよい。

εの寄与を最悪値ε＜0.5、a＜2^Nでチェックすると

　　 | a*ε/2ⁿ | ＜ | 2^N *0.5/2ⁿ | ＜0.5 　∴N＜n

となるので、nはN以上にする必要がある。

◇◇

例）8ビットデータ9個の平均値を8ビットで求める。和は12ビットだからN=12、除数はc=9。

まず乗数mの候補は(1)から次表のとおりになる。

n	2^n	2^n/c	m	ε
1	2	0.222..	0	+2/9
2	4	0.444..	0	+4/9
3	8	0.888..	1	-1/9
4	16	1.777..	2	-2/9
5	32	3.555..	4	-4/9
6	64	7.111..	7	+1/9
7	128	14.222..	14	+2/9
8	256	28.444..	28	+4/9
9	512	56.888..	57	-1/9
10	1024	113.777..	114	-2/9
11	2048	227.555..	228	-4/9
12	4096	455.111..	455	+1/9
13	8192	910.222..	910	+2/9
14	16384	1820.444..	1820	+4/9
15	32768	3640.889..	3641	-1/9

ここでε=2/9,4/9はε=1/9にちょうど2のべき乗をかけた値になっているので、ε=1/9のときと精度は同じになる。つまり意味のあるm,nはn=3,6,9,...と3個とびであることに注意。

次にnはN=12ビット以上必要なので、n=12(1/9≒455/4096)を選んで(2)を満たすか調べると、一箇所を除いて誤差δが範囲内に収まっており、n=12でもかなりいい精度が得られている。

a	a/c	a*m/2^n	整数部[a*m/2^n]	-0.5≦δ＜0.5
2^12-1	455	454.8889..	455	0
2^12-2	454.999..	454.7778..	455	-1/9
2^12-3	454.888..	454.6667..	455	-2/9
2^12-4	454.777..	454.5557..	455	-3/9
2^12-5	454.555..	454.4446..	454	+5/9
2^12-6	454.444..	454.3335..	454	+4/9
2^12-7	454.333..	454.2224..	454	+3/9
2^12-8	454.222..	454.1113..	454	+2/9
2^12-9	454.111..	454.0002..	454	+1/9

n=12の次のn=15(1/9≒3641/32768)を選んで(2)を満たすか調べると、すべての値に対して誤差δが範囲内に収まっている。

a	a/c	a*m/2^n	整数部[a*m/2^n]	-0.5≦δ＜0.5
2^12-1	455	455.0139..	455	0
2^12-2	454.999..	454.9028..	455	-1/9
2^12-3	454.888..	454.7917..	455	-2/9
2^12-4	454.777..	454.6805..	455	-3/9
2^12-5	454.555..	454.5694..	455	-4/9
2^12-6	454.444..	454.4583..	454	+4/9
2^12-7	454.333..	454.3472..	454	+3/9
2^12-8	454.222..	454.2361..	454	+2/9
2^12-9	454.111..	454.125	454	+1/9

◇◇◇

定数によるわり算を、RTLで1/cおよびm/2ⁿ (小数点以下は切り捨て)と書いた場合を、実際に合成して比べると次表のとおりになった。1/cと書くよりもm/2ⁿと書いた方がDSP 1個で済み、もしDSPでなくLUTで乗算回路を作っても回路規模は小さくなっている。

RTL	回路規模 Arria V	回路規模 7 series
assign q[7:0] = a[11:0]/9;	88 ALUT	64 LUT
assign p[19:0] = a[11:0]*9'd455; assign q[7:0] = p[19:12];	1 DSP or 49 ALUT	1 DSP or 29 LUT
assign p[22:0] = a[11:0]*12'd3641; assign q[7:0] = p[22:15];	1 DSP or 53 ALUT	1 DSP or 36 LUT

◇◇◇◇

上記(2)では四捨五入で丸めたが、もしa/cの切り捨て結果を求めようとしたら(1)のmは切り上げにする必要がある。なぜならmを真値より小さく選んでしまうと、a/cがちょうど割り切れるときもa*m/2nが下回ってしまい不都合だからである。

---

[←]　[↑]　[→]