Chip123 科技應用創新平台
標題:
FPGA數值運算問題解答收集
[打印本頁]
作者:
walltsou
時間:
2008-1-19 08:56 PM
標題:
FPGA數值運算問題解答收集
在使用FPGA後教了別人數次定點數小數表示法，發現一些狀況。但自己並不是走這一行的，所以一些比較深入的問題也無法回答。所以希望經由各位高手將其應用經驗以或是提供相關資料參考。
6 c2 } I0 l9 z2 v" K
能得到一些常用於FPGA的數值運算，如小數表示、乘除法、開根及平方、三角函數、亂數以及其他常用數值方法。
6 a5 d- O) \4 `7 d" E
此篇文章屬拋磚引玉性質，可能對一些人來說這些知識是"幼稚班"等級，但對於像我這種由韌體兼職FPGA工程師是有很大的幫助。
2 q6 l2 z; `% C$ r+ e7 l
格式大概為下列所列，各作者可以自行調整。
: \+ J% `% R, @& i5 @- [0 H4 m
主題：可以讓人了解的題目
- Y& J/ @8 ^0 t9 {! H" p, e5 D1 l
使用資源：計算時間、使用Gate count數目等
. j- {* c, u: H ^2 ^6 G( x5 a
適用及限定範圍：說明常用及不合適的地方
8 e5 C) b" U8 D1 c. b. ?
參考資料來源：出處或參考書本
7 H o6 z9 [/ w2 F, e8 m6 \
原理說明及例子：就是文章開始的地方
作者:
walltsou
時間:
2008-1-19 08:57 PM
主題：定點數小數表示法
0 Z) I! ^1 K0 i d9 @/ J! j, S6 V
使用範圍：使用整數運算系統下之小數運算
& M6 ]( T. [: e2 ?7 j% E6 W
參考資料：嵌入式系統構件 Jean J. Labrosse原著 黃文增譯 全華科技圖書出版
9 H+ d0 m5 P9 j _8 Z. \8 l
原理說明：
; i) C4 R1 U1 a* p: j$ O1 w
先復習一下計算機概論，有許多人都還給老師了。"^"表示次方運算
# y7 }$ R% [( M9 |
101.101b=2^3+2^0+2^-1+2^-3=5.625
3 [. C7 I( P; ]$ D" G" r
現在是如何運用到FPGA上了。其實這個問題在之前的定點數DSP就遇過了，只是後來應用變少了。現在的FPGA又要用，捲土重來。
; m R) q- }- G
我們知道FPGA對於整數系統的加減法是可以，但是遇到小數有些人就不知該如何。其實不難，只要在整數運算系統上加上小數點就行了。
$ | [$ a4 x. F% z
例如101.1b+101.1b=1011.0b，可以發現去掉小數點就和整數運算沒有兩樣。意指，只要將小數點那個位數對齊就可以了，使用移位對FPGA是很容易的。
# E- k0 s) o: U1 D$ K
但是整數運算使用為小數要標示小數位置，所以引入類似科學記號表示法。我們知道科學表示法為<尾數>E<指數>，例:3E3=3*10^3=3000，E表示10的次方。
5 E6 z0 x2 a1 e
定點數的表示法符號為S，表示法為<尾數>S<指數>，S表示為2的次方。舉例2.5S3=2.5*2^3=2.5*8=20。
9 W& a1 ?+ j P5 C. Y6 @8 h
在基本數學運算下的處理為：
- x, B0 [ h: C0 C3 T/ ?- X$ G
1.加減法
4 t$ v: k! ^4 S3 F) u
處理方式是將小數位數對齊再做運算。例:2S3+3S2=20S2+3S2=23S2
7 ]# V2 t" ~6 T9 a' ^/ Z/ W
2.乘除法
0 ~5 F3 ?, L( n2 e2 k
乘法時要將指數相加，尾數相乘。例:2S3*3S2=6S5
& [ f. Q# J& X
除法時要將指數相減，尾數相除。例:2S3/3S2=0.66S1
+ Y& T7 _+ g7 P) r/ H; m; _
3.開根
' c1 ]6 t% c S4 a7 H# `
主要是推導數學運算對指數的影響。
- W1 K/ N. w. t3 A
sqrt(aSb)=sqrt(a)*sqrt(2^b)=sqrt(a)*2^(b/2)
- h4 z" H4 }3 S. O( _1 O
可以發現在開根時指數是除2，尾數直接開根。
5 Q% T/ n. Q# m, j( w
4.小數精度的選用
7 t7 S2 u0 n- V2 {4 O8 t8 j( z/ @
為了符合精度，要如何選用指數範圍。我們使用定點數其精度取決於二進位小數取多少位。
# m) m% H$ j$ T9 c$ R
例如若是使用S-4為其指數，每二數之間最小距離為2^-4=0.0625。此為S-4下的精度。
( T) `2 _$ x' q3 Y# L
對應十進位精度可以使用log(精度)/log(2)去計算要使用的指數。
7 k1 t1 }2 x5 b# F6 W% g( X
使用精度0.1則S取用為log(0.1)/log(2)=-3.32，則使用S-4為其數值格式，就夠用了。
; f+ v5 j7 P* L2 A8 O& ~
5.數值範圍
x% p x1 F& d4 r- ]7 t
因為定點數是有限的位元組成，也是有限的數字集合及有限的可使用範圍，一但超過範圍的數也無法表示。也就是在運算上有可能會產生縊位問題，而造成非預期結果。
# l {5 m0 f/ ~- V2 _9 a" l) E. @
所以只可以使用在變動不大的運算上。所以要考量使用的數值範圍及使用精度，這方面是定點數在使用前要考量好的。
1 `& j7 ~) D. o6 e. r
定點數應用例：
8 a y; W. r: j/ N7 S- z$ ] w# S
已知機器運算只能使用整數的狀況下，要使用小數，則是使用負的S指數，將尾數變成整數。尾數送入機器去運算；指數則是人工管理。
2 b/ p( h# a w" f q/ J# k
例：r=10.1求圓面積area，假設輸出入需求精度為0.1
8 g1 a' |4 p% k& j1 x0 k* h7 [7 {
解答：精度為0.1則，log(0.1)/log(2)=-3.32，故選用的S指數要到S-4可以達成。
5 s4 j$ G' d0 v
pi=3.1416=50S-4(四捨五入)
4 x3 d; @" \, o6 k1 y+ |
r=10.1=162S-4(四捨五入)
# f9 `2 @+ a* [, x% J
area=pi*r*r=50S-4*162S-4*162S-4=1312200S-12=5126S-4(四捨五入)
' @$ b: f9 O1 z( S# x1 v4 f
換算為320.375
" ~* J# o3 w7 Z: I
實際為320.47386659269480825557425152834
[/ R* F+ W( y+ u% X5 o7 l# a
只有精準到整數，是因為所有數值精確度只有到0.1，誤差是0.05，運算來源有三個，故最大誤差為0.15，所以符合誤差範圍。
2 J4 \4 V( G6 S+ _/ K, I* J
由算式可以得知機器只計算50*162*162，解讀結果需右移8位元含四捨五入，輸出結果為S-4格式。
8 `8 D$ U% E. t7 X$ }
小技巧：
" u! `" P% k# `- r
定點數之計算可以使用小算盤來算。將小算盤設定為工程型。使用二進位顯示就可以將十進位轉成二進位。
+ i. C# \# l' ], z: |
因二進位只能使用整數，所以要先轉成整數才可以顯示。
5 ^ H& e- v j; m4 `
例如：pi的取用。
R0 o: s) e0 |5 R# N
pi取S-4結果為何?先取出pi=3.1415926535897932384626433832795
/ _( M& _( D, D. e. z. A
若我們使用精度為Qword則有64位元可以用，可以先乘上2^32，取用4相關的指數，可以在顯示時容易找到小數點位置。
% [8 Z# N8 @; j$ W a
結果為13493037704.522018958598982648896
* U5 {# H% j7 k3 _
直接按二進位，結果為11 0010 0100 0011 1111 0110 1010 1000 1000
. f: f6 T" ]7 ^" i! @
找到小數點位置後可以發現是110010bS-4
( K3 N. j# P% i* q
輸入110010按十進位可得50，我們可知pi=50S-4
* u4 i) `1 X9 g) U+ A: e
另外pi常有人用201/64來表示，其實是使用S-6的格式，可以看上面的值找出pi=11001001bS-6=201S-6
) a0 J/ H) [# \. Q5 @" s2 m
另外四捨五入在二進位很容易做，只要看取需要取用的小數精度下一位是否為1，若是則結果加一，不是則捨棄。
' y; U1 i7 n$ S! H/ A2 T
但會引發另一問題，剛好尾數LSB為多個1連續，則會進位。
5 L" d" S; G& u& W" s0 x
以pi為例取S-10至S-15四捨五入後表示的數皆相同，都會和S-10完全一樣，精度沒有增加，pi皆為3217S-10，就算是寫成不同的S值，如12868S-12，仍等於3217S-10。
作者:
walltsou
時間:
2008-1-19 08:57 PM
主題：使用加法做開根及平方計算
* c& _# M* T4 }9 g2 b3 M1 @
使用範圍：整數計算開根及平方，計算慢，gate count少
0 W" C+ r9 Z; M5 l% S1 a
參考資料：MATH toolkit for Real-Time Programming by Jack W. Crenshaw CMP Books
Z! c$ j1 p/ Q" M6 ~# j2 R
原理說明：
$ P/ D S+ K+ k# u7 H
這是我們常用的公式(n+1)^2=n^2+2*n+1
5 r0 z, _2 k$ b% _( s/ t
改寫為(n+1)^2=n^2+n+(n+1)，其中n^2在上次計算可得到，所以只剩n及(n+1)且只使用加法就可以進行。
5 O! j/ E4 H. d' c
設計演算法為
5 ~# |" o' A, A. ]5 |! t
a=Count
' D2 Y0 }5 ~7 m7 e4 x
b=Last Sum= Sum
: s0 |0 F) i* t; D
c=Sum=Last Sum+Count
. [. F/ u8 q- w. o
d=Squart=Sum+Last Sum
! e- m% @3 |! N A1 r
排表為
4 ]1 d( ^0 R" A( l; B# @' X ?
ａ ｂ ｃ ｄ
' n9 R+ F- E* O, }) b8 v
0 0 0 0
" q% I3 s# {% u2 U- M4 h# b
1 0 1 1
! b$ R4 Z2 \5 y" [: U7 i* N
2 1 3 4
0 d! c2 \& P( Y
3 3 6 9
5 i! S! p7 F6 m2 U# F$ u2 f
4 6 10 16
& q( a1 }/ `/ R8 ?5 W) I1 ^: q7 R
5 10 15 25
+ X5 F* Q$ c% R1 n- h
若要取得平方，就將輸入做為計算的次數。計算停下來時，取出d就是答案。
' s3 L+ J" p, q) @1 k
要做開方，就將輸入和輸出比較，超過時停下來，取出a就是答案。
) q- ]- _% |* b5 _( n; K0 Q
若要使用到小數，則使用定點數方式可以得到。
作者:
t8810012
時間:
2008-3-20 10:04 AM
It is good topic for me. thanks your sharing.
歡迎光臨 Chip123 科技應用創新平台 (http://chip123.com/)
Powered by Discuz! X3.2
