Chip123 科技應用創新平台
標題:
FPGA數值運算問題解答收集
[打印本頁]
作者:
walltsou
時間:
2008-1-19 08:56 PM
標題:
FPGA數值運算問題解答收集
在使用FPGA後教了別人數次定點數小數表示法，發現一些狀況。但自己並不是走這一行的，所以一些比較深入的問題也無法回答。所以希望經由各位高手將其應用經驗以或是提供相關資料參考。
9 j1 W: a5 n7 F$ u
能得到一些常用於FPGA的數值運算，如小數表示、乘除法、開根及平方、三角函數、亂數以及其他常用數值方法。
+ J) `$ R2 i7 y* M- L" E
此篇文章屬拋磚引玉性質，可能對一些人來說這些知識是"幼稚班"等級，但對於像我這種由韌體兼職FPGA工程師是有很大的幫助。
! ?8 H! t* c" W- \& H7 T/ F9 I
格式大概為下列所列，各作者可以自行調整。
: b7 F$ T) o2 @7 J2 D$ {. X5 I" n
主題：可以讓人了解的題目
0 }+ c& e" B' X* s e& U
使用資源：計算時間、使用Gate count數目等
4 _" i w, \1 K
適用及限定範圍：說明常用及不合適的地方
1 \. n/ S# s9 g) F
參考資料來源：出處或參考書本
' K+ X2 E$ W3 b4 W8 i- O) c$ u
原理說明及例子：就是文章開始的地方
作者:
walltsou
時間:
2008-1-19 08:57 PM
主題：定點數小數表示法
# P% C3 x# K" u: |
使用範圍：使用整數運算系統下之小數運算
( W2 ]8 o! E7 _/ A7 W# P# {* Q
參考資料：嵌入式系統構件 Jean J. Labrosse原著 黃文增譯 全華科技圖書出版
7 D" _( J( S. t K% l" T) C
原理說明：
4 x# [- n0 L7 b$ H6 Z* J
先復習一下計算機概論，有許多人都還給老師了。"^"表示次方運算
: \3 x6 r; J% S% G: V. j5 D+ K
101.101b=2^3+2^0+2^-1+2^-3=5.625
9 c+ a7 B3 K9 T; `8 v
現在是如何運用到FPGA上了。其實這個問題在之前的定點數DSP就遇過了，只是後來應用變少了。現在的FPGA又要用，捲土重來。
7 K& I1 ?9 u# V) G6 [7 G# k2 U" p
我們知道FPGA對於整數系統的加減法是可以，但是遇到小數有些人就不知該如何。其實不難，只要在整數運算系統上加上小數點就行了。
0 V( q+ ^# y! h: `' s W
例如101.1b+101.1b=1011.0b，可以發現去掉小數點就和整數運算沒有兩樣。意指，只要將小數點那個位數對齊就可以了，使用移位對FPGA是很容易的。
! _' B O* r9 p. \# }& ^0 X9 G
但是整數運算使用為小數要標示小數位置，所以引入類似科學記號表示法。我們知道科學表示法為<尾數>E<指數>，例:3E3=3*10^3=3000，E表示10的次方。
: T: z" U9 E/ o3 u S
定點數的表示法符號為S，表示法為<尾數>S<指數>，S表示為2的次方。舉例2.5S3=2.5*2^3=2.5*8=20。
; D4 `+ C6 b. i4 U
在基本數學運算下的處理為：
3 ?$ p1 n. U0 n8 c- S( @
1.加減法
- w9 f: L/ a1 j
處理方式是將小數位數對齊再做運算。例:2S3+3S2=20S2+3S2=23S2
5 [5 C* {1 l: b& S, N. L
2.乘除法
$ ]; j( K* H6 p& V6 b' N& f
乘法時要將指數相加，尾數相乘。例:2S3*3S2=6S5
. X7 C/ O, X+ p
除法時要將指數相減，尾數相除。例:2S3/3S2=0.66S1
$ c; A" N9 @6 P D9 r* i
3.開根
# m0 D( W& Q" O( `1 w
主要是推導數學運算對指數的影響。
' P* w3 O& z% v( J& Y2 }+ s
sqrt(aSb)=sqrt(a)*sqrt(2^b)=sqrt(a)*2^(b/2)
[; r% G' K/ S7 h4 \
可以發現在開根時指數是除2，尾數直接開根。
E/ x; k0 l* n! w8 p# [
4.小數精度的選用
6 [' d r" H( i9 o" K% X! i
為了符合精度，要如何選用指數範圍。我們使用定點數其精度取決於二進位小數取多少位。
' g2 w5 i) ]4 I4 L0 P
例如若是使用S-4為其指數，每二數之間最小距離為2^-4=0.0625。此為S-4下的精度。
. C% u: J' |% k- `2 {
對應十進位精度可以使用log(精度)/log(2)去計算要使用的指數。
7 y" D3 W" U( @
使用精度0.1則S取用為log(0.1)/log(2)=-3.32，則使用S-4為其數值格式，就夠用了。
7 t- {( h4 x, D k x
5.數值範圍
3 l5 V5 |/ i, m& a, z- `
因為定點數是有限的位元組成，也是有限的數字集合及有限的可使用範圍，一但超過範圍的數也無法表示。也就是在運算上有可能會產生縊位問題，而造成非預期結果。
+ ]; H! R0 G1 |5 S" G! W' A
所以只可以使用在變動不大的運算上。所以要考量使用的數值範圍及使用精度，這方面是定點數在使用前要考量好的。
$ l' d/ Z7 A* p+ E, k
定點數應用例：
# T+ ~2 l _4 ?) b( W6 e7 J2 }; M
已知機器運算只能使用整數的狀況下，要使用小數，則是使用負的S指數，將尾數變成整數。尾數送入機器去運算；指數則是人工管理。
- U. b- n8 f1 Q+ a1 u0 x+ k2 N
例：r=10.1求圓面積area，假設輸出入需求精度為0.1
5 Q7 D/ x- ?3 V
解答：精度為0.1則，log(0.1)/log(2)=-3.32，故選用的S指數要到S-4可以達成。
. e" |2 j3 a9 _! m6 N
pi=3.1416=50S-4(四捨五入)
7 y+ o- G8 ]8 q% F
r=10.1=162S-4(四捨五入)
: [4 v: |$ e- e$ s, c
area=pi*r*r=50S-4*162S-4*162S-4=1312200S-12=5126S-4(四捨五入)
3 c' W9 `# W/ |8 h7 o. w9 |
換算為320.375
4 M: D& t8 s, Q! t
實際為320.47386659269480825557425152834
& _8 U. x; n. Y& \
只有精準到整數，是因為所有數值精確度只有到0.1，誤差是0.05，運算來源有三個，故最大誤差為0.15，所以符合誤差範圍。
2 k9 _& I2 _' s8 ]
由算式可以得知機器只計算50*162*162，解讀結果需右移8位元含四捨五入，輸出結果為S-4格式。
: L+ o) O b F2 Y8 [3 b+ L
小技巧：
& }, p y; w. x3 w5 q! [* G
定點數之計算可以使用小算盤來算。將小算盤設定為工程型。使用二進位顯示就可以將十進位轉成二進位。
0 j* z, b t7 M5 }( u" o
因二進位只能使用整數，所以要先轉成整數才可以顯示。
}" } g6 h, X- M
例如：pi的取用。
0 G2 j+ H" ]6 f( F
pi取S-4結果為何?先取出pi=3.1415926535897932384626433832795
) i4 n/ Q6 v# B' e% {
若我們使用精度為Qword則有64位元可以用，可以先乘上2^32，取用4相關的指數，可以在顯示時容易找到小數點位置。
o- q7 O6 [5 I0 O
結果為13493037704.522018958598982648896
' R0 {: Q" \+ t7 N
直接按二進位，結果為11 0010 0100 0011 1111 0110 1010 1000 1000
! q8 i3 q$ w8 h' c: |
找到小數點位置後可以發現是110010bS-4
2 ^" b1 r- d+ ]
輸入110010按十進位可得50，我們可知pi=50S-4
7 a8 _# U/ Z/ C6 M( N
另外pi常有人用201/64來表示，其實是使用S-6的格式，可以看上面的值找出pi=11001001bS-6=201S-6
: _' k/ P! {8 v* k3 ?
另外四捨五入在二進位很容易做，只要看取需要取用的小數精度下一位是否為1，若是則結果加一，不是則捨棄。
% I" J& y! ~6 O; K, W
但會引發另一問題，剛好尾數LSB為多個1連續，則會進位。
' ?3 e# C9 M& f2 p3 `, r
以pi為例取S-10至S-15四捨五入後表示的數皆相同，都會和S-10完全一樣，精度沒有增加，pi皆為3217S-10，就算是寫成不同的S值，如12868S-12，仍等於3217S-10。
作者:
walltsou
時間:
2008-1-19 08:57 PM
主題：使用加法做開根及平方計算
( g" p. k D' h) t, M; a1 O
使用範圍：整數計算開根及平方，計算慢，gate count少
0 }" Y1 i0 E0 u: x6 ^1 I" N
參考資料：MATH toolkit for Real-Time Programming by Jack W. Crenshaw CMP Books
+ ^$ k% N. N" o+ B+ }( y
原理說明：
: r' a @8 B0 f3 U9 h( ~
這是我們常用的公式(n+1)^2=n^2+2*n+1
! ~$ |4 o3 t7 J# u& @! k5 z
改寫為(n+1)^2=n^2+n+(n+1)，其中n^2在上次計算可得到，所以只剩n及(n+1)且只使用加法就可以進行。
+ u4 r- Z5 X/ D1 Z0 c
設計演算法為
2 P! r- L2 @& }" Q. z4 P |
a=Count
, N/ k2 N6 y7 ]" @! x- z
b=Last Sum= Sum
% b; I& o; P# j; d; Q5 z
c=Sum=Last Sum+Count
: T4 U7 y. t T7 ?. ^$ t
d=Squart=Sum+Last Sum
1 r2 Z3 m7 m2 w! N
排表為
( W$ D% _% }: Y$ d- \6 Y& e
ａ ｂ ｃ ｄ
- x9 y0 ]- R) z+ s1 \% Y4 s0 v
0 0 0 0
5 L; |1 i; k7 ?8 e
1 0 1 1
7 Z& \- e# O! j3 q9 G8 p$ N# d( r
2 1 3 4
+ p3 W* T) P2 c
3 3 6 9
3 n1 f' L4 X' x5 C0 g+ e- h5 w; p
4 6 10 16
* q/ |& O+ U! t: O6 `" g
5 10 15 25
4 z" b1 o. K- p9 u
若要取得平方，就將輸入做為計算的次數。計算停下來時，取出d就是答案。
9 {( u9 x8 V% @1 s8 o
要做開方，就將輸入和輸出比較，超過時停下來，取出a就是答案。
9 l/ {* y/ S: S: L M! l
若要使用到小數，則使用定點數方式可以得到。
作者:
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
