算術運算的方法與電路

整數的表示法
整數的表示法決定運算方法
整數的長度決定可表示範圍
整數長度=算術邏輯運算單元的資料長度=word(字組)的長度

......................................................................................................................

complement(補數表示法)
1最適合加減法運算的整數表示法
2可表示正整數與負整數
3大多電子計算機採用complement表示整數

設b為基底,使用n個位數表示一整數,
則整數x的補數有以下兩種表示法:
1整數x的補數=b^n-x  (b的補數)
ex:b=10,n=4,整數x=3725
則x的補數=10^4-3725=6275
若0~4999為正,5000~9999為負,則6275表示-3725,而且整數範圍值=-5000~4999
且3275+6275=10000=整數的0
ex:b=16,n=4,整數x=3562
則x的補數=16^4-3562=CA9E
ex:b=8,n=4,整數x=3562
則x的補數=8^4-3562=4216
ex:b=2,n=4,整數x=1011
則x的補數=2^4-1011=0101

2整數x的補數=(b^n-1)-x  (b-1的補數)
ex:b=10,n=4,整數x=3725
則x的補數=(10^4-1)-3725=6274
若0~4999為正,5000~9999為負,則6274表示-3725,而且整數範圍值=-4999~4999
且3275+6274=9999=整數的0
ex:b=16,n=4,整數x=3562
則x的補數=(16^4-1)-3562=CA9D
ex:b=8,n=4,整數x=3562
則x的補數=(8^4-1)-3562=4216
ex:b=2,n=4,整數x=1011
則x的補數=(2^4-1)-1011=0100


則實數x的補數有以下兩種表示法:
1 實數x的補數=b^n-x  (b的補數)
ex:b=10,n=2,實數x=37.25
則x的補數=10^2-37.25=62.75,
若0~49.99為正,50~99.99為負,則62.75表示-37.25,而且實數範圍值=-50.00~49.99
ex:b=2,n=4,實數x=1011.101,
則x的補數=2^4-1011.101=0100.011

2 實數x的補數=(b^n-b^-m)-x  (b-1的補數)
ex:b=10,n=2,實數x=37.25,m=2位小數
則x的補數=(10^2-10^-2)-37.25=62.74,
若0~49.99為正,50~99.99為負,則62.74表示-37.25,而且實數範圍值=-50.00~49.99
ex:b=2,n=4,實數x=1011.101,m=3位小數
則x的補數=(2^4-2^-3)-1011.101=0100.010

......................................................................................................................

n位元2進位整數的表示法
無號數表示法
 適合加法運算與比較運算
 只能表示正整數而無法表示負整數
 n個位元整數值範圍=0 ~ 2^n-1
ex:10010110在無號數表示法=128+16+4+2=150
符號絕對值表示法
 將最左邊的位元當成符號位元,1為負數,0為正數
 適合相反數轉換,不適合加法運算與比較運算
 n個位元整數值範圍=-(2^(n-1)-1) ~ (2^(n-1)-1)
ex:10010110在符號絕對值表示法=-(16+4+2)=-22
ex:用符號絕對值表示法,69=01000101,-69=11000101

1's complement(1的補數表示法)
 適合加法運算與相反數轉換,不適合比較運算
 不需處理進位旗標
 n個位元整數值範圍=-(2^(n-1)-1) ~ (2^(n-1)-1)
 最左邊符號位元若為0表示正數,1表示負數
ex:設n=8,整數範圍=-127~127,負整數範圍=10000000~11111111,正整數範圍00000000~01111111
ex:10010110在1的補數表示法=-((2^8-1)-150)=11111111-10010110=01101001=-105
ex:10010110在1的補數表示法=10010110的相反=負的01101001=-105
ex:用1的補數表示法,69=01000101,-69=10111010

2's complement(2的補數表示法)
 適合加法運算與相反數轉換,不適合比較運算
 需處理進位旗標
 n個位元整數值範圍=-(2^(n-1)) ~ (2^(n-1)-1)
 最大正整數是(011111......1),最小負數是(10000......0)

 可直接使用binary adder(二進位加法器)來表示整數,一般電子計算機用
ex:1個byte的可表示範圍為10000000~01111111=-128~127
ex:10010110在2的補數表示法=-((2^8)-150)=-106
ex:10010110在2的補數表示法=10010110的相反+1=負的01101001+1=-106
ex:用2的補數表示法,69=01000101,-69=10111010+1=10111011
exess(超碼表示法)
 適合比較運算,不適合加法運算和相反數轉換
 n個位元整數值範圍=-(2^(n-1)) ~ (2^(n-1)-1)
ex:10010110在超碼表示法=(128+16+4+2)-128=22
ex:用超碼表示法,69=11000101,-69=00111011=(32+16+8+2+1)-128
ps:1的補數與2的補數表示法也稱為有號數表示法

ps:nibble表示4bit,a word=2bytes=16bit
n=4,表示法比較表:

無號數符號絕對1的補數2的補數超碼
0000
0001
0010
0011
0100
0101
0110
0111
0
1
2
3
4
5
6
7
+0
+1
+2
+3
+4
+5
+6
+7
+0
+1
+2
+3
+4
+5
+6
+7
+0
+1
+2
+3
+4
+5
+6
+7
-8
-7
-6
-5
-4
-3
-2
-1
1000
1001
1010
1011
1100
1101
1110
1111
8
9
10
11
12
13
14
15
-0
-1
-2
-3
-4
-5
-6
-7
-7
-6
-5
-4
-3
-2
-1
-0
-8
-7
-6
-5
-4
-3
-2
-1
+0
+1
+2
+3
+4
+5
+6
+7



......................................................................................................................

整數的加減運算

加法運算法則
做法:可用n-bit adder(n位元加法器)進行加法運算來產生n的合
若用1的補數表示法要設定進位旗標
ex:(5)+(-3)
1的補數表示法=(0101)+(1100)=1(0001)=(0001)+1=(0010)=2
2的補數表示法=(0101)+(1101)=1(0010)=2
產生的合若超出範圍則會出現arithmetic overflow(算術溢位)的中斷信號
判斷是否有arithmetic overflow方法:
 有號數
 無號數

減法運算法則
若用1的補數表示法要設定進位旗標
有號數
做法:先將減號轉成減號的補數,在使用n-bit adder進行加法運算來產生n的合
ex:使用1的補數,需考慮進位旗標
(5)-(-3)=(0101)-(1100)=(0101)+(0011)=(1000),overflow
(3)-(6)=(0011)-(0110)=(0011)+(1001)=(1100)=-3
ex:使用2的補數
(5)-(-3)=(0101)-(1101)=(0101)+(0011)=(1000),overflow
(3)-(6)=(0011)-(0110)=(0011)+(1010)=(1100)=-3
無號數
做法:先把兩個無號數視為有號數的正數,也就是最左邊多加1個符號位元並設為0,在採用有號數做法,並設定進位旗標
ex:無號數用4bit表示,使用2的補數法
(12)-(3)=(1100)-(0011)=12+3的補數=(1100)+(1101)=(1)(1001)=9
(3)-(12)=(0011)-(1100)=3+12的補數=(0011)+(0100)=(0)(0111),overflow


加減運算電路
half adder(半加器)
2個輸入變數,被加數x與加數y
2個輸出變數,carry(進位)與sum(和)
full adder(全加器)
3個輸入變數,被加數x與加數y和進位c
2個輸出變數,carry(進位)與sum(和)
parallel adder(平行加法器)/ripple adder(漣漪加法器)
使用n個全加器串連在一起
會有delay propagation(延遲累積)的問題
carry look-ahead adder(預先進位加法器)
無delay propagation的問題
使用carry generate signal(進位產生訊號)和carry propagate signal(進位傳遞訊號)
位元個數增加會導致複雜度大大增加

......................................................................................................................

整數的乘除運算

無號數的乘法運算法則
比有號數乘法運算簡單
硬體組織:n位元加法器電路,n位元暫存器*3,進位旗標,控制電路

無號數的除法運算法則
硬體組織:n位元加法器電路,n位元暫存器*3,符號旗標,控制電路
運算步驟
  restoring division(恢復式除法)
  non-restoring division(非恢復式除法):效能較好

有號數的乘法運算法則
因為有符號位元所以要做sign extension(符號擴充)
硬體組織:
robertson algorithm(羅勃森運算法則)
 直接對有號數進行乘法運算,不需將負的乘數轉換成正的乘數
booth algorithm(布氏運算法則)
 對乘數進行skipping over 1s(跳過連續的1)的技巧編碼
 處理正負乘數的方式都一樣
 以加法或減法進行運算
 若有連續的0或1的乘數,則會有較少運算,因此可加速完成乘法
 平均效率至少與一般有號數乘法運算法則相同
 步驟:
1將乘數由右而左,並對2和3處理n次
2乘數若相鄰兩個位元是01,則將被乘數加入乘積之中
若相鄰兩位元是10,則將被乘數取2's補數再加入乘積之中
其餘階不運算
3將乘積部份往右移一位
bit-pair recoding method(位元對編碼方式)
  處理正負乘數的方式都一樣
  至多需要n/2次的加法運算

乘法電路硬體實作
微程式控制
  產生一連串的加減法運算及shift(移位運算)的控制信號合力完成
  電路簡單,但運算要極多計時週期
硬體線路控制
  高效能電算機用,效能佳

..................................................................................................................................
..................................................................................................................................

實數的表示法
fixed-point number(定點數表示法):小數點是固定的,可表示範圍有限
floating-point number(浮點數表示法):小數點是浮動的

floating-point number
1 浮點數欄位:[sign bit][exponent][mantissa]
 sign bit(符號位元):浮點數用符號絕對值表示法,因此最左邊的位元1表負數0表正數
 mantissa(假數)/fraction(小數):表示significant digit有效數字或precision精確度,最左邊需為非零的正規化格式
 exponent(指數):表示浮點數的可表示範圍,使用超碼表示法,因為較適合比較運算

   ex:若長度為8bit,基底為2,則範圍是2^-128 ~ 2^127
ps:正規化過程就是,將小數點往左移或往右移到小數點右邊第一個數字不可為零
  ex:0.00011就要小數點右移3位變成0.11
  ex:110001.11就要小數點左移6位變成0.11000111

2 用小數部份與指數部份表示實數
3 實數的值= (1-2*s)*(0.m)*2^(e-n)
ex:設指數欄位5bit,假數10bit,採二進制正規化,則浮點數
+49.75=+(110001.11)*2^0=+(0.11000111)*2^6=(1-2*0)*(0.11000111)*2^(22-16)=[正][22][11000111填0到滿]=[0][10110][1100011100]
-356.875=-(101100100.111)*2^0=-(0.101100100111)*2^9=(1-2*1)*(0.101100100111)*2^(25-16)=[負][25][只取101100100111前10個]=[1][11001][1011001001]
-0.09375=-(0.00011)*2^0=-(0.11)*2^-3=(1-2*1)*(0.11)*2^(13-16)=[負][13][11填0到滿]=[1][01101][1100000000]
ps:5bit,採超16碼表示法,範圍在-16 ~ 15
ex:設浮點數格式為[1bit][3bit][4bit],則
01101000=[0][110][1000]=+(0.1000)*2^2=(10.00)=2
100000010=[1][000][0010]=-(0.0010)*2^-4=(0.00000010)=-1/128


......................

IEEE754浮點數表示法
1 採用2進位正規化且小數點最左邊隱含一個1,使用rounding處理guard bit
2 若將指數欄位所有位元設為0,表示underflow欠位,也就表示實數值太小無法表示
3 若將指數欄位所有位元設為1,表示overflow溢位,也就表示實數值太大無法表示
有兩種格式,如下:
single precision單倍精密度:32位元 [sign(1)][exponent(8)][fractional mantissa(23)]
實數的值= (1-2*s)*(1.f)*2^(e-127)
ex:-129.625=-(10000001.101)*2^0=-(1.0000001101)*2^7=(1-2*1)*(1.0000001101)*2^(134-127)
=[負][134][0000001101後接0一直到欄位滿]=[1][10000110][0000001101000000000000]
ps:134=127+7
ex:-1.5=-(1.1)*2^0=(1-2*1)*(1.1)*2^(127-127)
=[負][127][1後接0一直到欄位滿]=[1][01111111][1000000000000000000000]

double precision雙倍精密度:64位元 [sign(1)][exponent(11)][fractional mantissa(52)]
實數的值= (1-2*s)*(1.f)*2^(e-1023)

ps:浮點數的誤差有
round off error拾去誤差:儲存假數部份的長度有限而無法完全儲存而造成的誤差
truncation error截尾誤差:無法真正進行無窮多個運算而造成的誤差
ps:guard bit
說明:在浮點運算過程中,超過假數欄位長度的部份
最後表示結果時,處理這些位元以產生長度較短的進似值方法有:
chopping切斷:直接把guard bit捨棄,其餘位元完全不變,誤差:0 ~ 1
von neumann rounding范諾曼捨去:把guard bit去除,若其中一個位元為1,則把假數位元最右邊設為1,誤差:+1 ~ -1
rounding捨去:把guard bit去除,若guard bit最左邊位元為1,則把假數欄位最右邊位元設為1,誤差:+1/2 ~ -1/2

......................................................................................................................

實數的加減運算與電路
指數欄位的值需相同才可開始加減法運算,步驟為:
1比較指數大小:若是兩浮點數的指數相差n,則將指數較小者的假數右移n個位元
2設定指數:將最小者的指數欄位設成和最大者的指數欄位一樣
3假數相加(減) :對原先兩個浮點數中的假數部份進行加(減)法
4正規化:如果假數不符合正規化格式,就需要在做一次正規化

ex:[0][11011][1001110100]+[1][01101][1100000000]
1 指數欄位[01101]比[11011]小14bit,所以將最小者的假數右移14個位元,並將指數設為11011
2 [1][01101][1100000000]的設定後變為[1][11011][0000000000]
3 [0][11011][1001110100]+[1][11011][0000000000]=[1][11011][1001110100]
4 [1][11011][1001110100]己符合正規化要求

ps:如果兩點浮點數指數相差大,則指數小的浮點數必須先將假數欄位右移,若有效數字超出假數欄位則會形成誤差
ex:欄位格式為[1bit][3bit][4bit],5/2+1/8=5/2,因為
[0][110][1010]+[0][010][1000]=[0][110][1010]+[0][110][0000]=[0][110][1010]=5/2

適合管線作業成為arithmetic pipeline(算術導管),在處理大量浮點數相加運算時可大大提昇運算效率
ps:arithmetic pipeline只需處理data hazard(資料危機)
四階段導管設計的浮點數加法器:
 stage1 加法器(比較指數) 
 stage2 移位器與多工器(假數右移與設定指數)
 stage3 加法器(假數相加)
 stage4 加法器與移位器(正規化)

......................................................................................................................

實數的乘除運算與電路
乘除運算步驟:
1指數相加:得到的結果必須用超碼表示法表示,在轉成二進位
2假數相乘:得到的結果超過欄位,則只保留前面留在欄位的部份
3正規化:如果假數不符合正規化格式,就需要在做一次正規化

ex:[0][10100][1001100000]*[1][10010][1111000000]
1指數欄位[10100]+[10010]=100110,在超碼表示法裡表示22(因為38-16),所以得到[10110]
2假數欄位[1001100000]*[1111000000]=[1000111010]
3得到[1][10110][1000111010],己符合正規化

2009-10-26 10:54:36發表 0000-00-00 00:00:00修改   

數據分析
程式開發
計算機組織與結構

資料結構與演算法
Database and MySql
manage tool
windows
unix-like
linux service
network
network layer3
network layer2
network WAN
network service
作業系統
數位鑑識
資訊安全解決方案
資訊安全威脅
Cisco security
Cisco network
Cisco layer3
Cisco layer2



  登入      [牛的大腦] | [單字我朋友] Powered by systw.net