定数による除算

[] [] []


c個のデータの平均値を求めるときなど1/cといった定数による除算が必要になる。RTLでそのまま1/cと書いても合成できるみたいだが、FPGAには乗算器が備わっているので乗算に置き換えた方がよい。すなわち

 1/c m/2n

と近似すれば、定数cのわり算が定数mのかけ算とnビットの右シフトで実装できる

与えられたcに対してmnはどう決めればよいだろうか

Nビットの整数aを整数c (定数)でわり算して結果a/cを整数で求めることを考える。

乗数mnから次のように決まる。

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

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

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

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

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

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

εの寄与を最悪値ε0.5a2Nでチェックすると

   | a*ε/2n | | 2N *0.5/2n | 0.5  Nn

となるので、nN以上にする必要がある。

◇◇

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

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

n

2n

2n/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,nn=3,6,9,...3個とびであることに注意。

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

a

a/c

a*m/2n

整数部[a*m/2n]

-0.5≦δ<0.5

212-1

455

454.8889..

455

0

212-2

454.999..

454.7778..

455

-1/9

212-3

454.888..

454.6667..

455

-2/9

212-4

454.777..

454.5557..

455

-3/9

212-5

454.555..

454.4446..

454

+5/9

212-6

454.444..

454.3335..

454

+4/9

212-7

454.333..

454.2224..

454

+3/9

212-8

454.222..

454.1113..

454

+2/9

212-9

454.111..

454.0002..

454

+1/9

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

a

a/c

a*m/2n

整数部[a*m/2n]

-0.5≦δ<0.5

212-1

455

455.0139..

455

0

212-2

454.999..

454.9028..

455

-1/9

212-3

454.888..

454.7917..

455

-2/9

212-4

454.777..

454.6805..

455

-3/9

212-5

454.555..

454.5694..

455

-4/9

212-6

454.444..

454.4583..

454

+4/9

212-7

454.333..

454.3472..

454

+3/9

212-8

454.222..

454.2361..

454

+2/9

212-9

454.111..

454.125  

454

+1/9

◇◇◇

定数のわり算を、RTL1/cおよびm/2n (小数点以下は切り捨て)と書いた場合を、実際に合成して比べると次表のとおりになった。

1/cと書くよりもm/2nと書いた方が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が下回ってしまい不都合だからである。


[] [] []