FPGA數值運算問題解答收集

walltsou

在使用FPGA後教了別人數次定點數小數表示法，發現一些狀況。但自己並不是走這一行的，所以一些比較深入的問題也無法回答。所以希望經由各位高手將其應用經驗以或是提供相關資料參考。
能得到一些常用於FPGA的數值運算，如小數表示、乘除法、開根及平方、三角函數、亂數以及其他常用數值方法。
) Z4 L; ?) B  X+ Y, T此篇文章屬拋磚引玉性質，可能對一些人來說這些知識是"幼稚班"等級，但對於像我這種由韌體兼職FPGA工程師是有很大的幫助。
格式大概為下列所列，各作者可以自行調整。
主題：可以讓人了解的題目
' [8 ]" z$ I4 E3 |# ^# w使用資源：計算時間、使用Gate count數目等
適用及限定範圍：說明常用及不合適的地方
參考資料來源：出處或參考書本
+ o  e, L% P& o4 ^& y3 \! o. g3 H5 P原理說明及例子：就是文章開始的地方

walltsou

主題：定點數小數表示法
使用範圍：使用整數運算系統下之小數運算
參考資料：嵌入式系統構件 Jean J. Labrosse原著 黃文增譯 全華科技圖書出版
; Y* P0 \: ~# H5 G8 w原理說明：
先復習一下計算機概論，有許多人都還給老師了。"^"表示次方運算
101.101b=2^3+2^0+2^-1+2^-3=5.625
: d# C1 l3 Z5 F6 q1 j現在是如何運用到FPGA上了。其實這個問題在之前的定點數DSP就遇過了，只是後來應用變少了。現在的FPGA又要用，捲土重來。
我們知道FPGA對於整數系統的加減法是可以，但是遇到小數有些人就不知該如何。其實不難，只要在整數運算系統上加上小數點就行了。
9 l, o, K& ~' m% z  Q3 ~8 d' H4 V# a% G例如101.1b+101.1b=1011.0b，可以發現去掉小數點就和整數運算沒有兩樣。意指，只要將小數點那個位數對齊就可以了，使用移位對FPGA是很容易的。
但是整數運算使用為小數要標示小數位置，所以引入類似科學記號表示法。我們知道科學表示法為<尾數>E<指數>，例:3E3=3*10^3=3000，E表示10的次方。
定點數的表示法符號為S，表示法為<尾數>S<指數>，S表示為2的次方。舉例2.5S3=2.5*2^3=2.5*8=20。
在基本數學運算下的處理為：
% X, m! h+ G% p7 K# F5 N1.加減法
+ [/ p  C  i( O7 Z& _處理方式是將小數位數對齊再做運算。例:2S3+3S2=20S2+3S2=23S2
/ T4 Q5 o  s" k% z" K3 q" @# B; O2.乘除法
乘法時要將指數相加，尾數相乘。例:2S3*3S2=6S5
  A/ X+ K& j9 A: B( J. }$ v除法時要將指數相減，尾數相除。例:2S3/3S2=0.66S1
7 a7 W6 H* X+ G( j+ _: T3.開根
主要是推導數學運算對指數的影響。
sqrt(aSb)=sqrt(a)*sqrt(2^b)=sqrt(a)*2^(b/2)
( L3 I& g3 Y7 w. J可以發現在開根時指數是除2，尾數直接開根。
4.小數精度的選用
8 S/ a- t3 F2 E8 E2 ?6 Y% P- F為了符合精度，要如何選用指數範圍。我們使用定點數其精度取決於二進位小數取多少位。
* s( q3 B/ w9 Q9 K/ e- l4 v例如若是使用S-4為其指數，每二數之間最小距離為2^-4=0.0625。此為S-4下的精度。
" ^1 S2 y! [5 s( [) B對應十進位精度可以使用log(精度)/log(2)去計算要使用的指數。
使用精度0.1則S取用為log(0.1)/log(2)=-3.32，則使用S-4為其數值格式，就夠用了。
6 A( W, K  Q$ e- G, J1 c$ V5.數值範圍
$ _  @  z. K6 o  e, ]因為定點數是有限的位元組成，也是有限的數字集合及有限的可使用範圍，一但超過範圍的數也無法表示。也就是在運算上有可能會產生縊位問題，而造成非預期結果。
) x4 ^( [: o" B5 a: x9 j所以只可以使用在變動不大的運算上。所以要考量使用的數值範圍及使用精度，這方面是定點數在使用前要考量好的。
5 h' W* c# x( a( s( M2 r  M0 _, z定點數應用例：
8 u) p) ?& D' l) O已知機器運算只能使用整數的狀況下，要使用小數，則是使用負的S指數，將尾數變成整數。尾數送入機器去運算；指數則是人工管理。
! @3 k5 {8 i0 E2 Y7 q, x. T例：r=10.1求圓面積area，假設輸出入需求精度為0.1
; S8 e1 U3 M3 r8 j- b3 @; W- _解答：精度為0.1則，log(0.1)/log(2)=-3.32，故選用的S指數要到S-4可以達成。
6 A3 ^% ~. y! o( u$ H4 b# Cpi=3.1416=50S-4(四捨五入)
r=10.1=162S-4(四捨五入)
area=pi*r*r=50S-4*162S-4*162S-4=1312200S-12=5126S-4(四捨五入)
換算為320.375
8 {1 W) a: u+ E' ^% s# I實際為320.47386659269480825557425152834
0 n$ b, M# v2 ]* k. u只有精準到整數，是因為所有數值精確度只有到0.1，誤差是0.05，運算來源有三個，故最大誤差為0.15，所以符合誤差範圍。
/ ~. O* H& R9 c, q5 k由算式可以得知機器只計算50*162*162，解讀結果需右移8位元含四捨五入，輸出結果為S-4格式。
# R& {- X' C* c! W, w- v小技巧：
/ a, u8 A8 f9 w1 l1 L, ~/ e定點數之計算可以使用小算盤來算。將小算盤設定為工程型。使用二進位顯示就可以將十進位轉成二進位。
因二進位只能使用整數，所以要先轉成整數才可以顯示。
/ \3 Y' A% T# W+ ?8 f例如：pi的取用。
pi取S-4結果為何?先取出pi=3.1415926535897932384626433832795
; E0 m, p/ O) B. m若我們使用精度為Qword則有64位元可以用，可以先乘上2^32，取用4相關的指數，可以在顯示時容易找到小數點位置。
結果為13493037704.522018958598982648896
. H2 R3 I1 d8 e% L直接按二進位，結果為11 0010 0100 0011 1111 0110 1010 1000 1000
) ]3 H/ b+ S: Y. ?; ]; }: e; K找到小數點位置後可以發現是110010bS-4
* d+ F6 w; E- R1 x輸入110010按十進位可得50，我們可知pi=50S-4
0 A! B8 E+ o% y, v( I另外pi常有人用201/64來表示，其實是使用S-6的格式，可以看上面的值找出pi=11001001bS-6=201S-6
& L3 M/ v3 h7 i) C2 a" V另外四捨五入在二進位很容易做，只要看取需要取用的小數精度下一位是否為1，若是則結果加一，不是則捨棄。
( c' [. k4 ^- ^! H1 `8 ?, b6 N+ }但會引發另一問題，剛好尾數LSB為多個1連續，則會進位。
% G, {# g3 o6 M- R以pi為例取S-10至S-15四捨五入後表示的數皆相同，都會和S-10完全一樣，精度沒有增加，pi皆為3217S-10，就算是寫成不同的S值，如12868S-12，仍等於3217S-10。

walltsou

主題：使用加法做開根及平方計算
8 P4 \# `0 n- y4 l) E3 D% M: S使用範圍：整數計算開根及平方，計算慢，gate count少
2 V  r5 A. k' j' J+ v參考資料：MATH toolkit for Real-Time Programming by Jack W. Crenshaw CMP Books
原理說明：
這是我們常用的公式(n+1)^2=n^2+2*n+1
改寫為(n+1)^2=n^2+n+(n+1)，其中n^2在上次計算可得到，所以只剩n及(n+1)且只使用加法就可以進行。
0 f! }( G6 I2 M! |設計演算法為
a=Count
b=Last Sum= Sum
9 f; R4 k, Z6 F4 ?2 o# c9 }- M" J( ~: xc=Sum=Last Sum+Count
d=Squart=Sum+Last Sum
排表為
ａ　ｂ　ｃ　ｄ
1 g/ V- ?: T/ k' J 0　 0   0　 0
1　 0   1　 1
! s; M7 ^8 T. L" r6 ^9 Z 2　 1   3　 4
2 h& e( B+ ^0 t, ?4 N 3　 3   6　 9
6 O6 Z( p" c2 D# N 4　 6  10　16
5　10  15　25
5 A7 |- X: Q! t3 q$ z# X若要取得平方，就將輸入做為計算的次數。計算停下來時，取出d就是答案。
* m9 ]( X: u+ u, O要做開方，就將輸入和輸出比較，超過時停下來，取出a就是答案。
- J- p% x& F) E' B4 m* L! A2 @/ o若要使用到小數，則使用定點數方式可以得到。

t8810012

It is good topic for me. thanks your sharing.