Chip123 科技應用創新平台
標題:
FPGA數值運算問題解答收集
[打印本頁]
作者:
walltsou
時間:
2008-1-19 08:56 PM
標題:
FPGA數值運算問題解答收集
在使用FPGA後教了別人數次定點數小數表示法，發現一些狀況。但自己並不是走這一行的，所以一些比較深入的問題也無法回答。所以希望經由各位高手將其應用經驗以或是提供相關資料參考。
5 U, w' g# G" ]; }; e5 y
能得到一些常用於FPGA的數值運算，如小數表示、乘除法、開根及平方、三角函數、亂數以及其他常用數值方法。
; a& _" s# V' ~
此篇文章屬拋磚引玉性質，可能對一些人來說這些知識是"幼稚班"等級，但對於像我這種由韌體兼職FPGA工程師是有很大的幫助。
# O, O- v. g" }! e
格式大概為下列所列，各作者可以自行調整。
+ }: t' j1 k# _
主題：可以讓人了解的題目
6 J. @$ z. M1 r; Y r0 _5 N) C
使用資源：計算時間、使用Gate count數目等
! T: j& c/ q$ D7 z0 N4 L7 p1 U
適用及限定範圍：說明常用及不合適的地方
( p) P! `0 }9 z0 I6 W& p. r* _; O, T! p
參考資料來源：出處或參考書本
& E' X+ I$ b4 k P1 w
原理說明及例子：就是文章開始的地方
作者:
walltsou
時間:
2008-1-19 08:57 PM
主題：定點數小數表示法
0 c, G) ?+ Z9 ~8 a
使用範圍：使用整數運算系統下之小數運算
3 o' O% Y9 p% A- F ^; M. _! C" E# q @
參考資料：嵌入式系統構件 Jean J. Labrosse原著 黃文增譯 全華科技圖書出版
* \' r$ Q" J- y9 i
原理說明：
3 T$ p, W7 t: b) V( n
先復習一下計算機概論，有許多人都還給老師了。"^"表示次方運算
5 U F7 z8 R& l+ S) O3 y- @
101.101b=2^3+2^0+2^-1+2^-3=5.625
% [- Y7 h3 R" D% v
現在是如何運用到FPGA上了。其實這個問題在之前的定點數DSP就遇過了，只是後來應用變少了。現在的FPGA又要用，捲土重來。
1 A- V( ]" s% q0 G3 K4 m
我們知道FPGA對於整數系統的加減法是可以，但是遇到小數有些人就不知該如何。其實不難，只要在整數運算系統上加上小數點就行了。
) `* U& _2 {: {% V/ I! w2 ]9 g& E
例如101.1b+101.1b=1011.0b，可以發現去掉小數點就和整數運算沒有兩樣。意指，只要將小數點那個位數對齊就可以了，使用移位對FPGA是很容易的。
& `) n: y" y8 X. D0 A
但是整數運算使用為小數要標示小數位置，所以引入類似科學記號表示法。我們知道科學表示法為<尾數>E<指數>，例:3E3=3*10^3=3000，E表示10的次方。
7 b& b% B I, G6 s! g0 R5 n
定點數的表示法符號為S，表示法為<尾數>S<指數>，S表示為2的次方。舉例2.5S3=2.5*2^3=2.5*8=20。
P: a6 D/ d" P- r& ` c# u$ E
在基本數學運算下的處理為：
$ T# C3 `$ q% \
1.加減法
: h1 C: Q, t. ~1 z
處理方式是將小數位數對齊再做運算。例:2S3+3S2=20S2+3S2=23S2
- b9 w8 a: Z) u" G& }+ h: z) C
2.乘除法
- ~' m7 b" i( l
乘法時要將指數相加，尾數相乘。例:2S3*3S2=6S5
# t( u! t7 [4 N5 `
除法時要將指數相減，尾數相除。例:2S3/3S2=0.66S1
* E6 N; [/ r9 o0 k1 K5 S" B; v
3.開根
6 j$ O1 `$ J, g; T( B
主要是推導數學運算對指數的影響。
. ^& r& J9 X& e
sqrt(aSb)=sqrt(a)*sqrt(2^b)=sqrt(a)*2^(b/2)
7 B7 Z; J, Z* u: [& I$ r
可以發現在開根時指數是除2，尾數直接開根。
& c& y; _% ?: n0 S$ g# o5 i
4.小數精度的選用
; D0 y# N* n) n j) z/ G
為了符合精度，要如何選用指數範圍。我們使用定點數其精度取決於二進位小數取多少位。
/ @$ |7 `( n/ s. r8 A
例如若是使用S-4為其指數，每二數之間最小距離為2^-4=0.0625。此為S-4下的精度。
# i j& x8 O4 E) F
對應十進位精度可以使用log(精度)/log(2)去計算要使用的指數。
2 K/ o" j: d) w' Z
使用精度0.1則S取用為log(0.1)/log(2)=-3.32，則使用S-4為其數值格式，就夠用了。
$ A0 J1 F# n1 m! x5 Y
5.數值範圍
Y3 E7 j; v4 s" l
因為定點數是有限的位元組成，也是有限的數字集合及有限的可使用範圍，一但超過範圍的數也無法表示。也就是在運算上有可能會產生縊位問題，而造成非預期結果。
0 n3 X& X% E* u! g8 x5 H+ y0 d4 r
所以只可以使用在變動不大的運算上。所以要考量使用的數值範圍及使用精度，這方面是定點數在使用前要考量好的。
2 y" l G' U" l' |
定點數應用例：
5 }9 p+ H0 C, l" V* X( O+ `- r! }6 @
已知機器運算只能使用整數的狀況下，要使用小數，則是使用負的S指數，將尾數變成整數。尾數送入機器去運算；指數則是人工管理。
! W) e0 j& x0 W9 z q t \
例：r=10.1求圓面積area，假設輸出入需求精度為0.1
S# A# f* y3 e$ H
解答：精度為0.1則，log(0.1)/log(2)=-3.32，故選用的S指數要到S-4可以達成。
6 a) T) c" _! z* J, V. c2 ?2 D: Z, {
pi=3.1416=50S-4(四捨五入)
% r' h) v c& O1 I3 a# e& w: E
r=10.1=162S-4(四捨五入)
3 K6 G* k- q- @, }: l {
area=pi*r*r=50S-4*162S-4*162S-4=1312200S-12=5126S-4(四捨五入)
) Y" v# u* s/ c& n+ z2 Z! V
換算為320.375
/ w) ^2 H" m- X
實際為320.47386659269480825557425152834
! F* \' B9 M8 u1 j- [4 p6 r
只有精準到整數，是因為所有數值精確度只有到0.1，誤差是0.05，運算來源有三個，故最大誤差為0.15，所以符合誤差範圍。
# n1 x" ]6 F4 r" ]5 b6 H
由算式可以得知機器只計算50*162*162，解讀結果需右移8位元含四捨五入，輸出結果為S-4格式。
/ Q/ m3 b* J' ^
小技巧：
) y2 [, L& ~, f. s. b
定點數之計算可以使用小算盤來算。將小算盤設定為工程型。使用二進位顯示就可以將十進位轉成二進位。
% O* z8 `* q3 V9 n1 v( q$ T
因二進位只能使用整數，所以要先轉成整數才可以顯示。
E8 A5 s: {6 j& ]
例如：pi的取用。
7 \0 m1 N: P* k U
pi取S-4結果為何?先取出pi=3.1415926535897932384626433832795
; f$ o' R6 q. ~3 x7 f
若我們使用精度為Qword則有64位元可以用，可以先乘上2^32，取用4相關的指數，可以在顯示時容易找到小數點位置。
/ s" L8 S! i2 c% P3 S
結果為13493037704.522018958598982648896
. ~' ~% S' F* \2 P
直接按二進位，結果為11 0010 0100 0011 1111 0110 1010 1000 1000
& ^$ u+ f o$ A5 D
找到小數點位置後可以發現是110010bS-4
0 n6 {# E. ]/ N; K
輸入110010按十進位可得50，我們可知pi=50S-4
. C: z3 a, u9 _/ p0 M
另外pi常有人用201/64來表示，其實是使用S-6的格式，可以看上面的值找出pi=11001001bS-6=201S-6
6 M8 T+ D( j0 r" y. p$ K" n1 A
另外四捨五入在二進位很容易做，只要看取需要取用的小數精度下一位是否為1，若是則結果加一，不是則捨棄。
; \+ R) _/ f- ^2 M
但會引發另一問題，剛好尾數LSB為多個1連續，則會進位。
0 G' U$ c! |3 Z; }
以pi為例取S-10至S-15四捨五入後表示的數皆相同，都會和S-10完全一樣，精度沒有增加，pi皆為3217S-10，就算是寫成不同的S值，如12868S-12，仍等於3217S-10。
作者:
walltsou
時間:
2008-1-19 08:57 PM
主題：使用加法做開根及平方計算
5 X- K0 ]7 \4 M% q; W, y
使用範圍：整數計算開根及平方，計算慢，gate count少
. ?6 j4 A, ~5 s
參考資料：MATH toolkit for Real-Time Programming by Jack W. Crenshaw CMP Books
( p; O5 I: q7 J
原理說明：
7 |# X. e4 A5 S5 j
這是我們常用的公式(n+1)^2=n^2+2*n+1
( S, s+ [/ _0 @, I( N" z# H7 V! O
改寫為(n+1)^2=n^2+n+(n+1)，其中n^2在上次計算可得到，所以只剩n及(n+1)且只使用加法就可以進行。
# d+ i/ E G% U& k
設計演算法為
8 U- _+ K. O4 t2 f1 ^
a=Count
. y2 r% e* T. R* e
b=Last Sum= Sum
/ b. D. G4 }( ]( e4 _# n3 ~ t9 c. u/ D
c=Sum=Last Sum+Count
# I! q, N) d3 N- Z$ w/ l! H8 k
d=Squart=Sum+Last Sum
2 I2 J% t' w0 n& j4 S9 Q
排表為
5 B4 S9 e" c2 x4 @8 [
ａ ｂ ｃ ｄ
3 ~) `6 J4 i8 `/ w. E; s. w+ I1 U
0 0 0 0
& w i* Y; L* S% }. T& J' Q
1 0 1 1
6 { B) @: M" i. r3 F" p
2 1 3 4
+ |0 D. c/ W0 R$ P/ f( ~+ G
3 3 6 9
: Q3 z9 q1 h5 E8 V
4 6 10 16
% c* U% J3 _; P6 p
5 10 15 25
/ U& B. G8 }4 P) h* l& v, ]
若要取得平方，就將輸入做為計算的次數。計算停下來時，取出d就是答案。
8 H- L$ T! B, v" g7 J
要做開方，就將輸入和輸出比較，超過時停下來，取出a就是答案。
4 h( H# V: v2 [) H) m- k
若要使用到小數，則使用定點數方式可以得到。
作者:
t8810012
時間:
2008-3-20 10:04 AM
It is good topic for me. thanks your sharing.
歡迎光臨 Chip123 科技應用創新平台 (http://www.chip123.com/)
Powered by Discuz! X3.2
