Chip123 科技應用創新平台
標題:
FPGA數值運算問題解答收集
[打印本頁]
作者:
walltsou
時間:
2008-1-19 08:56 PM
標題:
FPGA數值運算問題解答收集
在使用FPGA後教了別人數次定點數小數表示法，發現一些狀況。但自己並不是走這一行的，所以一些比較深入的問題也無法回答。所以希望經由各位高手將其應用經驗以或是提供相關資料參考。
% z6 u2 W0 _) h6 }) }6 n
能得到一些常用於FPGA的數值運算，如小數表示、乘除法、開根及平方、三角函數、亂數以及其他常用數值方法。
8 E1 p5 w8 ~8 O5 }
此篇文章屬拋磚引玉性質，可能對一些人來說這些知識是"幼稚班"等級，但對於像我這種由韌體兼職FPGA工程師是有很大的幫助。
' Q3 ^8 _! C& e* y$ S3 L9 \
格式大概為下列所列，各作者可以自行調整。
1 K. K9 d1 e) g. S* e
主題：可以讓人了解的題目
6 C/ p! q9 z# M2 Q
使用資源：計算時間、使用Gate count數目等
' D6 c, p! k9 g# {. N, G
適用及限定範圍：說明常用及不合適的地方
1 ]$ r$ r' p+ y9 E/ d3 E
參考資料來源：出處或參考書本
, i$ S1 d' Y: R! C5 H+ m
原理說明及例子：就是文章開始的地方
作者:
walltsou
時間:
2008-1-19 08:57 PM
主題：定點數小數表示法
* h' `* S5 G! c- R8 x, p' p
使用範圍：使用整數運算系統下之小數運算
8 w2 Q+ H1 _6 |
參考資料：嵌入式系統構件 Jean J. Labrosse原著 黃文增譯 全華科技圖書出版
; J% R% o- F4 b& b! U
原理說明：
" }1 d0 y) d* P; j. G
先復習一下計算機概論，有許多人都還給老師了。"^"表示次方運算
8 G* {4 z3 P' n3 w$ `0 B8 Z
101.101b=2^3+2^0+2^-1+2^-3=5.625
7 m; t+ w8 v3 T- W0 x; k
現在是如何運用到FPGA上了。其實這個問題在之前的定點數DSP就遇過了，只是後來應用變少了。現在的FPGA又要用，捲土重來。
: e( |, R# E% U6 @7 \2 V$ Y: ~1 M5 y
我們知道FPGA對於整數系統的加減法是可以，但是遇到小數有些人就不知該如何。其實不難，只要在整數運算系統上加上小數點就行了。
" ?; w; j; r$ _5 e
例如101.1b+101.1b=1011.0b，可以發現去掉小數點就和整數運算沒有兩樣。意指，只要將小數點那個位數對齊就可以了，使用移位對FPGA是很容易的。
& _3 c9 Z; P) x
但是整數運算使用為小數要標示小數位置，所以引入類似科學記號表示法。我們知道科學表示法為<尾數>E<指數>，例:3E3=3*10^3=3000，E表示10的次方。
) C7 J" C7 b3 g8 A$ W i3 p+ W
定點數的表示法符號為S，表示法為<尾數>S<指數>，S表示為2的次方。舉例2.5S3=2.5*2^3=2.5*8=20。
8 Y3 @5 U' D( d7 ]( b9 V/ I
在基本數學運算下的處理為：
6 {* }2 ]8 I3 N/ k4 u0 g
1.加減法
: F) O2 I+ F8 e2 g2 r
處理方式是將小數位數對齊再做運算。例:2S3+3S2=20S2+3S2=23S2
6 s) l2 g- F' V8 u+ S6 H- y% |! |# B
2.乘除法
1 q& f& j! M# H N; Z' V
乘法時要將指數相加，尾數相乘。例:2S3*3S2=6S5
" g+ O4 C G E- @: c1 x
除法時要將指數相減，尾數相除。例:2S3/3S2=0.66S1
. Q+ J, V. [6 c8 N0 p5 x3 U3 E
3.開根
& `* J {5 r8 g, w
主要是推導數學運算對指數的影響。
' B' W3 X3 J$ v/ f1 \
sqrt(aSb)=sqrt(a)*sqrt(2^b)=sqrt(a)*2^(b/2)
* ^2 y5 z. E7 E$ H
可以發現在開根時指數是除2，尾數直接開根。
' ~. S0 N5 b3 b3 v" P/ W
4.小數精度的選用
. @, c2 }0 g5 i8 p3 D4 g# |
為了符合精度，要如何選用指數範圍。我們使用定點數其精度取決於二進位小數取多少位。
2 P% T; c& ^. ]- V
例如若是使用S-4為其指數，每二數之間最小距離為2^-4=0.0625。此為S-4下的精度。
2 e2 I8 Z7 y6 D. p* Y6 I( h
對應十進位精度可以使用log(精度)/log(2)去計算要使用的指數。
1 U% A2 g& d) X& ]; n; `
使用精度0.1則S取用為log(0.1)/log(2)=-3.32，則使用S-4為其數值格式，就夠用了。
1 V0 }- L! f* R6 ^
5.數值範圍
/ U; c* K4 n: n1 K: H$ A
因為定點數是有限的位元組成，也是有限的數字集合及有限的可使用範圍，一但超過範圍的數也無法表示。也就是在運算上有可能會產生縊位問題，而造成非預期結果。
1 ` q8 s" p+ F( \# a& ^' U$ B
所以只可以使用在變動不大的運算上。所以要考量使用的數值範圍及使用精度，這方面是定點數在使用前要考量好的。
' M. d2 s" x) g$ D/ i4 e2 e9 N. H
定點數應用例：
0 R4 p4 K0 q: d; E
已知機器運算只能使用整數的狀況下，要使用小數，則是使用負的S指數，將尾數變成整數。尾數送入機器去運算；指數則是人工管理。
0 t3 u' u' W; G
例：r=10.1求圓面積area，假設輸出入需求精度為0.1
3 o* Z# j6 c4 N. Z
解答：精度為0.1則，log(0.1)/log(2)=-3.32，故選用的S指數要到S-4可以達成。
* q9 ~1 W- G. ^
pi=3.1416=50S-4(四捨五入)
9 T. j, ^( l9 D1 r
r=10.1=162S-4(四捨五入)
1 ~; e/ z) y4 i5 ?- p$ @7 T
area=pi*r*r=50S-4*162S-4*162S-4=1312200S-12=5126S-4(四捨五入)
5 H( M* I7 l. z5 A3 s3 K* u4 Z3 S
換算為320.375
7 x: o8 ` w" {+ T$ F3 ]
實際為320.47386659269480825557425152834
" z+ k$ J0 S6 q+ I1 ~% ]
只有精準到整數，是因為所有數值精確度只有到0.1，誤差是0.05，運算來源有三個，故最大誤差為0.15，所以符合誤差範圍。
* O7 a. N" D+ ?7 W0 W+ w! ^' H6 ]8 ~
由算式可以得知機器只計算50*162*162，解讀結果需右移8位元含四捨五入，輸出結果為S-4格式。
$ A: I) i; J: s# i7 Q0 W
小技巧：
; j T7 c! Q+ n* J
定點數之計算可以使用小算盤來算。將小算盤設定為工程型。使用二進位顯示就可以將十進位轉成二進位。
! ~0 o8 ]) K4 H# Y$ i( b
因二進位只能使用整數，所以要先轉成整數才可以顯示。
1 K, q9 U: i& X- i0 w; D9 H& I
例如：pi的取用。
' J. t2 s) y) J
pi取S-4結果為何?先取出pi=3.1415926535897932384626433832795
, R) t7 Y, Q9 x% N6 r6 ]
若我們使用精度為Qword則有64位元可以用，可以先乘上2^32，取用4相關的指數，可以在顯示時容易找到小數點位置。
) Y' b( ^2 N* {# X- I
結果為13493037704.522018958598982648896
& R* a: G- A6 z) y+ N! h9 R
直接按二進位，結果為11 0010 0100 0011 1111 0110 1010 1000 1000
! D/ T+ S- Z3 t5 U
找到小數點位置後可以發現是110010bS-4
} g9 s' P o
輸入110010按十進位可得50，我們可知pi=50S-4
" w9 j. d; Q4 A b
另外pi常有人用201/64來表示，其實是使用S-6的格式，可以看上面的值找出pi=11001001bS-6=201S-6
6 w! d1 j! v5 N c/ y
另外四捨五入在二進位很容易做，只要看取需要取用的小數精度下一位是否為1，若是則結果加一，不是則捨棄。
9 P. c& L6 F R% D# J5 S
但會引發另一問題，剛好尾數LSB為多個1連續，則會進位。
# U, [" U8 f h& [& I
以pi為例取S-10至S-15四捨五入後表示的數皆相同，都會和S-10完全一樣，精度沒有增加，pi皆為3217S-10，就算是寫成不同的S值，如12868S-12，仍等於3217S-10。
作者:
walltsou
時間:
2008-1-19 08:57 PM
主題：使用加法做開根及平方計算
" |, ^/ }: b& u; b0 W$ x I
使用範圍：整數計算開根及平方，計算慢，gate count少
2 p7 `. J* ~& f$ g K
參考資料：MATH toolkit for Real-Time Programming by Jack W. Crenshaw CMP Books
/ Y1 ?& f( p1 r! [7 y; R
原理說明：
$ y/ a0 n, w- l6 E
這是我們常用的公式(n+1)^2=n^2+2*n+1
+ j4 ~& A# f4 I! n5 L8 w
改寫為(n+1)^2=n^2+n+(n+1)，其中n^2在上次計算可得到，所以只剩n及(n+1)且只使用加法就可以進行。
3 f9 [. \' B2 s( l2 E% }
設計演算法為
; Y s7 m8 U& h# k8 q9 T
a=Count
$ L. t) h6 B4 t7 g* @2 a/ H) a! N# A3 g
b=Last Sum= Sum
& E' s U" H+ g8 Z
c=Sum=Last Sum+Count
; i1 @* s5 i1 X
d=Squart=Sum+Last Sum
8 Q, o% \9 O* L9 c- t
排表為
/ g4 u6 }* A5 `6 c' X
ａ ｂ ｃ ｄ
+ S1 B) f, O# e$ H) V1 Y/ s% d
0 0 0 0
3 x( z; o* j3 Q2 o6 `2 d4 b
1 0 1 1
6 {8 A2 u4 L9 Y$ @
2 1 3 4
5 {8 s$ f4 V/ }+ _& t
3 3 6 9
2 J l8 h- N' W+ t# T& F, M
4 6 10 16
. a& J7 `. Q, j. K/ U) ^& |
5 10 15 25
4 \) P, L9 ?6 w) s! y& q3 t* ~7 M5 A+ ]
若要取得平方，就將輸入做為計算的次數。計算停下來時，取出d就是答案。
( h# j! b( {: Q T
要做開方，就將輸入和輸出比較，超過時停下來，取出a就是答案。
) a- R% X2 `: s5 U2 t
若要使用到小數，則使用定點數方式可以得到。
作者:
t8810012
時間:
2008-3-20 10:04 AM
It is good topic for me. thanks your sharing.
歡迎光臨 Chip123 科技應用創新平台 (http://free.vireal.world/chip123_website/innoingbbs/)
Powered by Discuz! X3.2
