計(jì)算機(jī)算法和算法電路實(shí)現(xiàn)本章介紹計(jì)算機(jī)組成和系統(tǒng)結(jié)構(gòu)的重要基本概念，信息編碼、算法設(shè)計(jì)和運(yùn)算器設(shè)計(jì)等。3計(jì)算機(jī)算法和算法電路實(shí)現(xiàn)3.1各種數(shù)據(jù)類(lèi)型的二進(jìn)制表示3.2加減運(yùn)算和快速加法器設(shè)計(jì)3.3乘法和高速乘法算法及電路3.4除法和快速除法電路3.5開(kāi)方算法及電路實(shí)現(xiàn)處理機(jī)存儲(chǔ)器I/O接口顯示器打印機(jī)鍵盤(pán)網(wǎng)絡(luò)鼠標(biāo)I/O接口總線(xiàn)控制器圖1.4硬盤(pán)軟盤(pán)Cache信息編碼3.1各種數(shù)據(jù)類(lèi)型的二進(jìn)制表示信息編碼內(nèi)容信息編碼數(shù)據(jù)編碼命令編碼數(shù)值編碼字符編碼定點(diǎn)數(shù)值浮點(diǎn)數(shù)值邏輯數(shù)值西文中文（指令編碼）(I’llexplainitindetailinchapter4.)數(shù)據(jù)編碼數(shù)據(jù)編碼數(shù)值編碼字符編碼定點(diǎn)數(shù)值浮點(diǎn)數(shù)值邏輯數(shù)值西文中文定點(diǎn)整數(shù)定點(diǎn)小數(shù)數(shù)值編碼定點(diǎn)數(shù)值浮點(diǎn)數(shù)值邏輯數(shù)值定點(diǎn)整數(shù)定點(diǎn)小數(shù)數(shù)值編碼定點(diǎn)數(shù)值定點(diǎn)整數(shù)定點(diǎn)小數(shù)定點(diǎn)數(shù)值原碼表示補(bǔ)碼表示移碼表示原碼表示補(bǔ)碼表示定點(diǎn)整數(shù)格式…...0110n-1n-2n-33210.第n-1位為符號(hào)位。第n-1位=0，表示正整數(shù)；=1，表示負(fù)整數(shù)；例如：6，原碼表示是:1110例如：-6，原碼表示是:原碼表示:

n-2位—0位為數(shù)的絕對(duì)值。[x]原=x,x>=0;2n-1+|x|,x=<-1[x]原=[x]原=x=0110x=-0110數(shù)值表示范圍：正最小值：000…...0000n-1n-2n-33210..正最大值：011…...1111n-1n-2n-33210.+0+（2n-1-1）負(fù)最大值：100…...0000n-1n-2n-33210.負(fù)最小值：111…...1111n-1n-2n-33210.-0-（2n-1-1）真值機(jī)器數(shù)數(shù)值表示個(gè)數(shù)：0+（2n-1-1）-（2n-1-1）2n個(gè)數(shù)值表示范圍：+1-1變化的分辨率:1,并且是均允的.0+（2n-1-1）-（2n-1-1）+1-1定點(diǎn)整數(shù)格式…...0110n-1n-2n-33210.第n-1位為符號(hào)位。第n-1位=0，表示正整數(shù)；=1，表示負(fù)整數(shù)；例如：6，補(bǔ)碼表示是:1010例如：-6，補(bǔ)碼表示是:補(bǔ)碼表示:[x]補(bǔ)=x,x>=0;2n-|x|,x=<-1[x]補(bǔ)=[x]補(bǔ)=x=0110x=-011010000-0110=1010[x]補(bǔ)=x,x>=0;2n-|x|,x=<-1證明:2n-|x|=111…..11+1-|x|=111…..11-|x|+1=[x]反+1從n-1位到0位

[-9]補(bǔ)

10111取反加1的證明0100110111例如求-9的補(bǔ)碼:|-9|01001[9]反10110+110111100000數(shù)值表示范圍：正最小值：000…...0000n-1n-2n-33210.正最大值：011…...1111n-1n-2n-33210.0+（2n-1-1）負(fù)最大值：000…...0000n-1n-2n-33210.負(fù)最大值：111…...1111n-1n-2n-33210.0-1負(fù)最小值：100…...0000n-1n-2n-33210.-2n-1真值機(jī)器數(shù)數(shù)據(jù)表示個(gè)數(shù)：0+(2n-1-1)-2n-12n個(gè)數(shù)值表示范圍+1-1變化的分辨率:1,并且是均允的.0+(2n-1-1)-2n-1+1-1定點(diǎn)整數(shù)格式…...n-1n-2n-33210.移碼表示:[x]移=x+移碼值=x+(2n-1-1)X=[x]移-移碼值=[x]移-(2n-1-1)定點(diǎn)小數(shù)格式0110第0位為符號(hào)位0位=0，表示正整數(shù)；=1，表示負(fù)整數(shù)；例如：0.75，原碼表示是:1110例如：-0.75，原碼表示是:原碼表示:

1位—n-1位為數(shù)的絕對(duì)值。[x]原=x,0<=x<1;1+|x|,-1<x<=0[x]原=[x]原=…...0123n-1.n-3n-2數(shù)值表示范圍：正最小值：正最大值：負(fù)最大值：負(fù)最小值：真值機(jī)器數(shù)000…...00000123n-1.n-3n-2011…...11110123n-1.n-3n-200…...0000123n-1.n-3n-2111…...11110123n-1.n-3n-21+0-01-2-（n-1）-(1-2-（n-1）)1.00000…00.0000…010.11111…1正最大值：011…...11110123n-1.n-3n-21-2-（n-1）1-2-（n-1）公式說(shuō)明1-2-（n-1）數(shù)據(jù)表示個(gè)數(shù)：02n個(gè)數(shù)值表示范圍：變化的分辨率:,2-（n-1）

并且是均允的.01-2-（n-1）1-2-（n-1）-(1-2-（n-1）)-(1-2-（n-1）)定點(diǎn)小數(shù)格式0110第0位為符號(hào)位0位=0，表示正整數(shù)；=1，表示負(fù)整數(shù)；例如：0.75，原碼表示是:1010例如：-0.75，原碼表示是:補(bǔ)碼表示:[x]補(bǔ)=x,0<=x<1;2-|x|,-1<=x<0[x]補(bǔ)=[x]補(bǔ)=…...0123n-1.n-3n-2[x]補(bǔ)=x,

0=<x<1;2

-|x|,-1=<x<0從0位到n-1位

[-0.5625]補(bǔ)取反加“1”的證明例如求-0.5625的補(bǔ)碼:|-0.5625|01001[0.5625]反10110+1101112-|x|=1.111….1+2-（n-1）-|x|=1.111….1-|x|+2-（n-1）=[x]反+“1”1000000100110111數(shù)值表示范圍：正最小值：正最大值：負(fù)最大值：負(fù)最小值：真值機(jī)器數(shù)000…...00000123n-1.n-3n-2011…...11110123n-1.n-3n-200…...0000123n-1.n-3n-2111…...11110123n-1.n-3n-210-11-2-（n-1）-2-（n-1）數(shù)據(jù)表示個(gè)數(shù)：02n個(gè)數(shù)值表示范圍：變化的分辨率:,2-（n-1）

并且是均允的.01-2-（n-1）1-2-（n-1）-1-14位二進(jìn)制數(shù)在各種不同表示方法下的所能表示的數(shù)值100111001111001110011110011100111內(nèi)存中哪些是數(shù)據(jù),哪些是指令PC:11001100AR:11101110指令數(shù)據(jù)由指令決定數(shù)據(jù)類(lèi)型!浮點(diǎn)數(shù)值的表示法浮點(diǎn)數(shù)是指小數(shù)點(diǎn)位置可浮動(dòng)的數(shù)據(jù)，通常以下式表示：N=M?RE其中，N為浮點(diǎn)數(shù)，M(mantissa)為尾數(shù)，E(exponent)為階碼，R(radix)稱(chēng)為階的基數(shù)，也叫底。R是一個(gè)常數(shù)，一般是2、8或16。sEMseffractionIEEE754浮點(diǎn)數(shù)值的表示法sef031302322sef063625251IEEE(InstituteofElectricalandElectronicEngineers)745標(biāo)準(zhǔn)的單精度和雙精度浮點(diǎn)格式。s(sign)、e(exponent)f(fraction)單精度雙精度IEEE754浮點(diǎn)數(shù)值的表示法符號(hào)位

s=0,+

1,-階碼e采用移碼，尾數(shù)f采用原碼純小數(shù)。機(jī)器數(shù)與真值的關(guān)系：V=(-1)s?2e-127?

1.f23.34*1022.334*103規(guī)格化的非規(guī)格化的11.0111*22規(guī)格化的非規(guī)格化的1.10111*23f隱藏位01000000111011000000000000000000舉例說(shuō)明：V=(-1)s?2e-127?

1.f=(-1)0

?2129-127?

1.fV=22?

1.11011000000000000000000=111.011000000000000000000=7.375例一，機(jī)器數(shù)真值例二，真值機(jī)器數(shù)V=3.125=11.001=1.1001?21s=0,e=1+127=128,f=1001000000000000000000001000000010010000000000000000000IEEE754單精度浮點(diǎn)數(shù)數(shù)的范圍01111111100000000000000000000000e=255,f=0：+無(wú)窮大00000000000000000000000000000000e=0,f=0：零00000000100000000000000000000000e=00000001,f=0：+最小值

=2-12601111111011111111111111111111111e=11111110,f=1111：+最大值

=2127（2-2-23）02-1262127（2-2-23）2e-127=20-127=2-127數(shù)表示的精度2e-30101000=1.000=100.0=4001=1.001=100.1=4.5010=1.010=101.0=5011=1.011=101.1=5.51001011101112e-3=25-3=22000001010011100101110111maxminfhas8patternsperavalue.數(shù)表示的精度邏輯數(shù)值True2false當(dāng)事物只有二個(gè)狀態(tài)時(shí)可用邏輯值表示!字符編碼西文編碼：漢字編碼：西文編碼：ASCII（AmericanStandardCodeforInformationInterchange):規(guī)定8個(gè)二進(jìn)制位的最高一位為0，余下的7位可以給出128個(gè)編碼，表示128個(gè)不同的字符。EBCDIC(ExtendedBinaryCodedDecimalInterchangeCode):擴(kuò)充的二十進(jìn)制交換碼，這種編碼使用8位二進(jìn)制數(shù)?？梢越o出256個(gè)編碼，表示256個(gè)不同的字符。漢字編碼：輸入程序1輸入程序2輸入程序n...內(nèi)碼字庫(kù)1字庫(kù)2字庫(kù)m...宋體楷體隸體...全拼碼ABC碼五筆字型碼...漢字輸入編碼：為了能直接使用西文標(biāo)準(zhǔn)鍵盤(pán)把漢字輸入到計(jì)算機(jī)。漢字內(nèi)碼：漢字內(nèi)碼是用于漢字信息的存儲(chǔ)、交換、檢索等操作的機(jī)內(nèi)代碼。字模碼是用點(diǎn)陣表示的漢字字形代碼，它是漢字的輸出形式。國(guó)標(biāo)碼不等于機(jī)內(nèi)碼！國(guó)標(biāo)碼是我國(guó)1981年公布的《通信用漢字字符集（基本集）及其交換碼標(biāo)準(zhǔn)》GB2312--80方案。00第一字節(jié)第二字節(jié)0011000000010010國(guó)標(biāo)碼如，“啊”：11第一字節(jié)第二字節(jié)1011000010010010機(jī)內(nèi)碼如，“啊”：區(qū)別ASCII漢字字型?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????0150153.2加減運(yùn)算和快速加法器設(shè)計(jì)3.2.1補(bǔ)碼的加減運(yùn)算3.2.2快速加法運(yùn)算3.2.1補(bǔ)碼的加減運(yùn)算[x]補(bǔ)[y]補(bǔ)[x+/-y]補(bǔ)

+ADD/SUB溢出？補(bǔ)碼加減運(yùn)算規(guī)則[x+y]補(bǔ)=[x]補(bǔ)+[y]補(bǔ)

[x-y]補(bǔ)=[x+[-y]]補(bǔ)=[x]補(bǔ)+[-y]補(bǔ)[-y]補(bǔ)=[y]補(bǔ)+“1”補(bǔ)碼加減運(yùn)算器判別溢出方法AsBsSsAsBsSs溢出AsBsSs補(bǔ)碼加減運(yùn)算0011(+3)0010(+2)0101(+5)+1100(-4)1101(-3)1001(-7)+1100(-4)0010(+2)1110(-2)+0011(+3)0111(+7)1010(-6)+1101(-3)1001(-7)0110(+6)+上溢！上溢！3.2.2快速加法運(yùn)算全加器設(shè)計(jì)全加器真值表輸入輸出abci

ci+1s0000000101010010111010001101101101011111邏輯表達(dá)式：s=a?b?ci

+a?b?ci

+a?b?ci

+a? b?ci+1=a?b+a?ci+b?ciabci+ci+1s=abci邏輯圖：sabcici+1邏輯表達(dá)式：s=a?b?ci

+a?b?ci

+a?b?ci

+a? b?ci

ci+1=a?b+a?ci+b?ci=ab+(a+b)ci=g+pci=abci邏輯圖：sabcici+1abscicoaddc0b0a0s0c1g:進(jìn)位產(chǎn)生函數(shù)p:進(jìn)位傳遞函數(shù)n位串聯(lián)加法器abscicoaddabscicoaddabscicoaddabscicoaddc0b0b1a0an-2an-1a1bn-2bn-1s0s1sn-2sn-1c1cncn-1cn-2c2分析：

cn=an-1bn-1+(an-1+bn-1)cn-1=gn-1+pn-1cn-1ci=ai-1bi-1+(ai-1+bi-1)ci-1=gi-1+pi-1ci-1c2=a1b1+(a1+b1)c1=g1+p1c1c1=a0b0+(a0+b0)c0=g0+p0c02級(jí)門(mén)延遲2級(jí)門(mén)延遲2級(jí)門(mén)延遲2級(jí)門(mén)延遲abscicoaddabscicoaddabscicoaddabscicoaddc0b0b1a0an-2an-1a1bn-2bn-1s0s1sn-2sn-1c1cncn-1cn-2c2解決辦法

先行進(jìn)位加法器abscicoaddabscicoaddabscicoaddabscicoaddc0b0b1a0an-2an-1a1bn-2bn-1s0s1sn-2sn-1c1cncn-1cn-2c2Ci=fi(A,B,c0)ABA=(an-1,

an-2,…,

a1,a0)B=(bn-1,

bn-2,…,

b1,b0)以8位先行進(jìn)位加法器為例：a0b0a1b1a2b2a3b3a4b4a5b5a6b6a7b7s0s1s2s3s4s5s6s7c0c1c2c3c4c5c6c7c8A=(a7,

a6,…,

a1,a0)B=(b7,

b6,…,

b1,b0)ABCi=fi(A,B,c0)以8位先行進(jìn)位加法器為例：c2=a1b1+(a1+b1)c1=g1+p1c1=g1+p1(g0+p0c0)=g1+p1g0+p1p0c0c1=a0b0+(a0+b0)c0=g0+p0c0c3=a2b2+(a2+b2)c2=g2+p2c2=g2+p2(g1+p1g0+p1p0c0)=g2+p2g1+p2p1g0+p2

p1p0c0

c4=a3b3+(a3+b3)c3=g3+p3c3=g3+p3(g2+p2g1+p2p1g0+p2

p1p0c0

)=g3+p3g2+p3p2g1+p3

p2

p1g0+p3

p2

p1p0c0

c5=a4b4+(a4+b4)c4=g4+p4c4=g4+p4(g3+p3g2+p3p2g1+p3

p2

p1g0+p3

p2

p1p0c0

)=g4+p4g3+p4p3g2+p4

p3p2g1+p4

p3

p2p1g0+p4p3

p2

p1p0c0

c6=a5b5+(a5+b5)c5=g5+p5c5=g5+p5(g4+p4g3+p4p3g2+p4

p3p2g1+p4

p3

p2p1g0+p4p3

p2

p1p0c0

)=g5+p5g4+p5p4g3+p5

p4p3g2+p5

p4

p3p2g1+p5p4

p3

p2p1g0+p5

p4p3

p2

p1p0c0

以8位先行進(jìn)位加法器為例：c7=a6b6+(a6+b6)c6=g6+p6c6=g6+p6(g5+p5g4+p5p4g3+p5

p4p3g2+p5

p4

p3p2g1+p5p4

p3

p2p1g0

+p5

p4p3

p2

p1p0c0)=g6+p6

g5+p6

p5g4+p6

p5p4g3+p6

p5

p4p3g2+p6

p5

p4

p3p2g1

+p6

p5p4

p3

p2p1g0+p6

p5

p4p3

p2

p1p0c0c8=a7b7+(a7+b7)c7=g7+p7c7=g7+p7(g6+p6

g5+p6

p5g4+p6

p5p4g3+p6

p5

p4p3g2+p6

p5

p4

p3p2g1+p6

p5p4

p3

p2p1g0+p6

p5

p4p3

p2

p1p0c0)=g7+p7

g6+p7

p6

g5+p7

p6

p5g4+p7

p6

p5p4g3+p7

p6

p5

p4p3g2+p7

p6

p5

p4

p3p2g1+p7

p6

p5p4

p3

p2p1g0+p7

p6

p5

p4p3

p2

p1p0c0

以8位先行進(jìn)位加法器為例：?jiǎn)栴}1：扇入太多c8=a7b7+(a7+b7)c7=g7+p7c7=g7+p7(g6+p6

g5+p6

p5g4+p6

p5p4g3+p6

p5

p4p3g2+p6

p5

p4

p3p2g1+p6

p5p4

p3

p2p1g0+p6

p5

p4p3

p2

p1p0c0)=g7+p7

g6+p7

p6

g5+p7

p6

p5g4+p7

p6

p5p4g3+p7

p6

p5

p4p3g2+p7

p6

p5

p4

p3p2g1+p7

p6

p5p4

p3

p2p1g0+p7

p6

p5

p4p3

p2

p1p0c0

c8以8位先行進(jìn)位加法器為例：?jiǎn)栴}2：扇出太多c8=a7b7+(a7+b7)c7=g7+p7c7=g7+p7(g6+p6

g5+p6

p5g4+p6

p5p4g3+p6

p5

p4p3g2+p6

p5

p4

p3p2g1+p6

p5p4

p3

p2p1g0+p6

p5

p4p3

p2

p1p0c0)=g7+p7

g6+p7

p6

g5+p7

p6

p5g4+p7

p6

p5p4g3+p7

p6

p5

p4p3g2+p7

p6

p5

p4

p3p2g1+p7

p6

p5p4

p3

p2p1g0+p7

p6

p5

p4p3

p2

p1p0c0

p7以8位先行進(jìn)位加法器為例：?jiǎn)栴}3：電路不規(guī)則，需要長(zhǎng)線(xiàn)驅(qū)動(dòng)c8=a7b7+(a7+b7)c7=g7+p7c7=g7+p7(g6+p6

g5+p6

p5g4+p6

p5p4g3+p6

p5

p4p3g2+p6

p5

p4

p3p2g1+p6

p5p4

p3

p2p1g0+p6

p5

p4p3

p2

p1p0c0)=g7+p7

g6+p7

p6

g5+p7

p6

p5g4+p7

p6

p5p4g3+p7

p6

p5

p4p3g2+p7

p6

p5

p4

p3p2g1+p7

p6

p5p4

p3

p2p1g0+p7

p6

p5

p4p3

p2

p1p0c0

解決辦法a0b0a1b1a2b2a3b3a4b4a5b5a6b6a7b7s0s1s2s3s4s5s6s7c0c1c2c3c4c5c6c7c8A3-0B3-0A7-4B7-4c4解決辦法a0b0a1b1a2b2a3b3a4b4a5b5a6b6a7b7s0s1s2s3s4s5s6s7c0c1c2c3c4c5c6c7c8C1=a0b0+(a0+b0)C0=g0+p0C0C1=g0+p0C0C2=g1+p1C1=g1+p1(g0+p0C0)=g1+p1g0+p1p0C0

=G1,0+P1,0C0C2=G1,0+P1,0C0C3=g2+p2C2C4=G3,2+P3,2C2C5=g4+p4C4C6=G5,4+P5,4C4C7=g6+p6C6C8=G7,6+P7,6C6G1,0=g1+p1g0;

P1,0=p1p0a1,0b1,0a3,2b3,2a5,4b5,4a7,6b7,6以8位先行進(jìn)位加法器為例：實(shí)用的a0b0s0a1b1s1a2b2s2a3b3s3a4b4s4a5b5s5a6b6s6a7b7s7c0p0g0c6p6g6c5p5g5c7p7g7c4p4g4c3p3g3c2p2g2c1p1g1G1,0c0G3,2G5,4G7,6c0c0P1,0P3,2P5,4P7,6c2c4c4c4G3,0P3,0G7,4P7,4G7,0P7,0C4=G3,2+P3,2C2=G3,2+P3,2G1,0+P3,2P1,0C0=G3,0+P3,0C0C2=G1,0+P1,0C0C1=a0b0+(a0+b0)C0=C2=g1+p1C1=g1+p1(g0+p0C0)=g1+p1g0+p1p0C0=g0+p0C0G1,0+P1,0C0C3==g2+p2C2C4=g3+p3C3=g3+p3(g2+p2C2)=g3+p3g2+p3p2C2=G3,2+P3,2C2=G3,2+P3,2(G1,0+P1,0C0)=G3,2+P3,2G1,0+P3,2

P1,0C0=C5=a4b4+(a4+b4)C4=g4+p4C4C6

=G5,4+P5,4C4C7==g6+p6C6G3,0+P3,0C0C8=G7,4+P7,4C4=G7,4+P7,4(G3,0+P3,0C0)=G7,4+P7,4G3,0+P7,4P3,0C0)=G7,0+P7,0C03.3乘法和高速乘法算法及電路3.3.1無(wú)符號(hào)整數(shù)乘法及電路一位二進(jìn)制的乘法運(yùn)算規(guī)則:0x0=0,0x1=0,1x0=0,1x1=1十進(jìn)制乘法二進(jìn)制乘法1234432112342468370249365332114被乘數(shù):乘數(shù):乘積:1001101000001001

00001001

1011010被乘數(shù):乘數(shù):乘積:二進(jìn)制乘法1001101000001001

00