Chip123 科技應用創新平台

標題: FPGA數值運算問題解答收集 [打印本頁]
作者: walltsou    時間: 2008-1-19 08:56 PM
標題: FPGA數值運算問題解答收集
在使用FPGA後教了別人數次定點數小數表示法，發現一些狀況。但自己並不是走這一行的，所以一些比較深入的問題也無法回答。所以希望經由各位高手將其應用經驗以或是提供相關資料參考。5 q+ K: o8 Z) u' O, r: [
能得到一些常用於FPGA的數值運算，如小數表示、乘除法、開根及平方、三角函數、亂數以及其他常用數值方法。, L2 g8 w) i/ _& Y
此篇文章屬拋磚引玉性質，可能對一些人來說這些知識是"幼稚班"等級，但對於像我這種由韌體兼職FPGA工程師是有很大的幫助。
1 K! ]+ Q8 \  A/ R& R) v格式大概為下列所列，各作者可以自行調整。
" L6 ?1 {% P5 N主題：可以讓人了解的題目$ H+ L( W& w/ E. L4 b
使用資源：計算時間、使用Gate count數目等. a" l) j' g/ r- Y" ~
適用及限定範圍：說明常用及不合適的地方
( {- o8 z" ~9 R$ M9 _7 U參考資料來源：出處或參考書本
- ]$ Z2 t# |) r1 T0 i原理說明及例子：就是文章開始的地方
作者: walltsou    時間: 2008-1-19 08:57 PM
主題：定點數小數表示法3 x8 C. L$ u( P: M# E' M! C7 R+ Z& T
使用範圍：使用整數運算系統下之小數運算* ~4 j% b  U6 i8 C
參考資料：嵌入式系統構件 Jean J. Labrosse原著 黃文增譯 全華科技圖書出版5 }, n& F9 J3 I8 Y( C
原理說明：. p! T+ I0 r# p5 G* D
先復習一下計算機概論，有許多人都還給老師了。"^"表示次方運算
# D' |: m9 j2 N( m  C$ u101.101b=2^3+2^0+2^-1+2^-3=5.625( V$ t0 b* B* ?
現在是如何運用到FPGA上了。其實這個問題在之前的定點數DSP就遇過了，只是後來應用變少了。現在的FPGA又要用，捲土重來。
3 A  \3 b9 D6 ?8 K* \1 E+ Z$ q我們知道FPGA對於整數系統的加減法是可以，但是遇到小數有些人就不知該如何。其實不難，只要在整數運算系統上加上小數點就行了。$ q& w2 t5 O$ U. I
例如101.1b+101.1b=1011.0b，可以發現去掉小數點就和整數運算沒有兩樣。意指，只要將小數點那個位數對齊就可以了，使用移位對FPGA是很容易的。
( n' m. m) S2 [# Y. A但是整數運算使用為小數要標示小數位置，所以引入類似科學記號表示法。我們知道科學表示法為<尾數>E<指數>，例:3E3=3*10^3=3000，E表示10的次方。
8 S' N$ \# Q1 ^/ z. f定點數的表示法符號為S，表示法為<尾數>S<指數>，S表示為2的次方。舉例2.5S3=2.5*2^3=2.5*8=20。
3 t: H; ~# Z. z7 H. T在基本數學運算下的處理為：$ t- T# [0 l% _1 ]5 l
1.加減法; v& N3 [; E! B( N
處理方式是將小數位數對齊再做運算。例:2S3+3S2=20S2+3S2=23S2' d  H4 R8 b+ C; F
2.乘除法
8 O& M$ d# F' ~  E. I乘法時要將指數相加，尾數相乘。例:2S3*3S2=6S5- G: A3 ?! E5 X& I+ T9 Z8 F/ a, N
除法時要將指數相減，尾數相除。例:2S3/3S2=0.66S1
# x- T: Y* w: u" x2 A4 _+ u3.開根3 ^; M0 x2 B3 e: ?4 n/ {* G* @
主要是推導數學運算對指數的影響。3 O: m" @, X1 h5 B% ?8 Y9 X/ O& O
sqrt(aSb)=sqrt(a)*sqrt(2^b)=sqrt(a)*2^(b/2)
/ D2 ?, I. d% l可以發現在開根時指數是除2，尾數直接開根。5 K9 f& P; C- F, T1 u
4.小數精度的選用
- R! e0 y! i- ~8 M6 V$ ^為了符合精度，要如何選用指數範圍。我們使用定點數其精度取決於二進位小數取多少位。
- Z" W. M# b" A+ d, y7 o( }1 W例如若是使用S-4為其指數，每二數之間最小距離為2^-4=0.0625。此為S-4下的精度。
. J$ g7 m  l( H9 W9 u" u7 c. w7 o對應十進位精度可以使用log(精度)/log(2)去計算要使用的指數。
0 n, [& H* V; _+ W! Q! M7 ?6 |3 X使用精度0.1則S取用為log(0.1)/log(2)=-3.32，則使用S-4為其數值格式，就夠用了。
. j$ {. p; G1 v1 I  v. P8 X/ t& u5.數值範圍- s$ Z  U+ P; c. x5 ?6 M
因為定點數是有限的位元組成，也是有限的數字集合及有限的可使用範圍，一但超過範圍的數也無法表示。也就是在運算上有可能會產生縊位問題，而造成非預期結果。* t6 E: \4 V& z5 U/ _
所以只可以使用在變動不大的運算上。所以要考量使用的數值範圍及使用精度，這方面是定點數在使用前要考量好的。
" O! _' `+ a9 ?: Y; A, U定點數應用例：
9 Y8 B0 c5 w! N. }& C* V已知機器運算只能使用整數的狀況下，要使用小數，則是使用負的S指數，將尾數變成整數。尾數送入機器去運算；指數則是人工管理。- x/ G0 e: ]2 }) c
例：r=10.1求圓面積area，假設輸出入需求精度為0.1/ ?; d+ n/ W& r2 a" {
解答：精度為0.1則，log(0.1)/log(2)=-3.32，故選用的S指數要到S-4可以達成。. C! F; {0 z: w0 a8 t1 {
pi=3.1416=50S-4(四捨五入)
, f+ e  |6 _3 {2 P# w, A8 q7 X# Pr=10.1=162S-4(四捨五入)8 a, D# r( a/ G, S
area=pi*r*r=50S-4*162S-4*162S-4=1312200S-12=5126S-4(四捨五入): ?/ g1 B5 k( p
換算為320.375* _( k. N6 W/ V+ g! O; G8 n# x. _4 v
實際為320.473866592694808255574251528344 I/ @) u: N3 h& `# y& S
只有精準到整數，是因為所有數值精確度只有到0.1，誤差是0.05，運算來源有三個，故最大誤差為0.15，所以符合誤差範圍。7 @: O9 r/ ]9 O% W# o- g
由算式可以得知機器只計算50*162*162，解讀結果需右移8位元含四捨五入，輸出結果為S-4格式。
" G' ^. P7 q5 G6 S9 ]" x6 ]小技巧：7 b, l, Q$ |" f
定點數之計算可以使用小算盤來算。將小算盤設定為工程型。使用二進位顯示就可以將十進位轉成二進位。  U6 f% \8 j9 t; n
因二進位只能使用整數，所以要先轉成整數才可以顯示。
" X7 r, K5 b& X( h例如：pi的取用。  @/ ]* Y$ H4 p. z; T
pi取S-4結果為何?先取出pi=3.1415926535897932384626433832795$ `7 {: J; _" H& M/ A( L/ C3 r$ ?
若我們使用精度為Qword則有64位元可以用，可以先乘上2^32，取用4相關的指數，可以在顯示時容易找到小數點位置。- e, k4 m4 V. a% @1 l# ]
結果為13493037704.522018958598982648896
' {3 c! u9 P% k* J! K直接按二進位，結果為11 0010 0100 0011 1111 0110 1010 1000 1000) R1 I; L. n/ r
找到小數點位置後可以發現是110010bS-4
6 X- a; n6 R1 r- V. h3 {/ [/ A輸入110010按十進位可得50，我們可知pi=50S-4
: K# U6 |9 E3 ~# `( c另外pi常有人用201/64來表示，其實是使用S-6的格式，可以看上面的值找出pi=11001001bS-6=201S-6
9 E& S4 |* S% B: y+ f" w/ Z另外四捨五入在二進位很容易做，只要看取需要取用的小數精度下一位是否為1，若是則結果加一，不是則捨棄。
4 a- L; y5 y, B  p6 I但會引發另一問題，剛好尾數LSB為多個1連續，則會進位。
* q2 T3 B$ R. v( h" C' n1 j. j以pi為例取S-10至S-15四捨五入後表示的數皆相同，都會和S-10完全一樣，精度沒有增加，pi皆為3217S-10，就算是寫成不同的S值，如12868S-12，仍等於3217S-10。
作者: walltsou    時間: 2008-1-19 08:57 PM
主題：使用加法做開根及平方計算
( y2 p# }1 B1 v. R( S- V- w使用範圍：整數計算開根及平方，計算慢，gate count少' a3 y- j& l/ P5 F- Q
參考資料：MATH toolkit for Real-Time Programming by Jack W. Crenshaw CMP Books% F: I5 x: {+ F) g, i
原理說明：
5 h+ o+ ]) B+ Q$ t) W0 ~這是我們常用的公式(n+1)^2=n^2+2*n+1$ a: Q; Z' L2 v1 l' e
改寫為(n+1)^2=n^2+n+(n+1)，其中n^2在上次計算可得到，所以只剩n及(n+1)且只使用加法就可以進行。
4 H, i2 @+ P; D7 d, ?' T4 ]* u設計演算法為5 A0 G% ^& R! R  z* O
a=Count" E& D( B+ o2 I. w. A& L9 v
b=Last Sum= Sum
$ |- N& g8 c2 @/ w/ j2 jc=Sum=Last Sum+Count
; b" T* k" X( {7 v8 A3 L' c  md=Squart=Sum+Last Sum
, ?8 p) \2 K2 K排表為* g3 [  g, r2 Q0 y  M1 f
ａ　ｂ　ｃ　ｄ, n2 R4 A0 H8 l* ?5 O/ v1 k$ C! [
0　 0   0　 0; \4 E) A% U. a9 P4 x2 u  e
1　 0   1　 1% T) B# P9 E: z/ n& [% a) c7 q
2　 1   3　 4
. {5 u4 q) b$ [" P* Q+ a 3　 3   6　 9
6 ^/ j& n$ X2 @  w 4　 6  10　16
) F8 ]- G& W* i$ ] 5　10  15　25$ @2 ?& ?$ L. X9 W- }; {
若要取得平方，就將輸入做為計算的次數。計算停下來時，取出d就是答案。3 p7 D" f* G, ]6 W2 `
要做開方，就將輸入和輸出比較，超過時停下來，取出a就是答案。
7 b1 u" E8 d/ a6 w( T5 x1 l若要使用到小數，則使用定點數方式可以得到。
作者: 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