數(shù)據(jù)表示與指令系統(tǒng)

1、2.1 數(shù)據(jù)表示數(shù)據(jù)表示2.2 浮點(diǎn)數(shù)據(jù)表示浮點(diǎn)數(shù)據(jù)表示2.3 高級(jí)數(shù)據(jù)表示高級(jí)數(shù)據(jù)表示2.4 指令系統(tǒng)的優(yōu)化設(shè)計(jì)指令系統(tǒng)的優(yōu)化設(shè)計(jì)2.5 指令系統(tǒng)設(shè)計(jì)的兩種風(fēng)格指令系統(tǒng)設(shè)計(jì)的兩種風(fēng)格 2.1.1 數(shù)據(jù)類型、數(shù)據(jù)表示與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型、數(shù)據(jù)表示與數(shù)據(jù)結(jié)構(gòu)整數(shù)、實(shí)數(shù)、布爾數(shù)、二進(jìn)制位、字符、串、圖、整數(shù)、實(shí)數(shù)、布爾數(shù)、二進(jìn)制位、字符、串、圖、表、樹、陣列、隊(duì)列、鏈表、棧、向量等。表、樹、陣列、隊(duì)列、鏈表、棧、向量等。數(shù)據(jù)類型數(shù)據(jù)類型定義了具有相同屬性一組值的集合，定義了具有相同屬性一組值的集合，還定義了這個(gè)集合上的操作集。還定義了這個(gè)集合上的操作集。數(shù)據(jù)數(shù)據(jù) 用戶定義的數(shù)據(jù)用戶定義的數(shù)據(jù) 用戶程

2、序中使用用戶程序中使用 系統(tǒng)數(shù)據(jù)系統(tǒng)數(shù)據(jù) 執(zhí)行程序時(shí)生成執(zhí)行程序時(shí)生成 指令指令 數(shù)據(jù)的復(fù)合數(shù)據(jù)的復(fù)合l 基本數(shù)據(jù)類型基本數(shù)據(jù)類型： 二進(jìn)制位、整數(shù)、十進(jìn)制數(shù)、浮點(diǎn)數(shù)、字符、二進(jìn)制位、整數(shù)、十進(jìn)制數(shù)、浮點(diǎn)數(shù)、字符、布爾數(shù)等。布爾數(shù)等。l結(jié)構(gòu)數(shù)據(jù)類型結(jié)構(gòu)數(shù)據(jù)類型：由一組相互有關(guān)的數(shù)據(jù)元素復(fù)合而由一組相互有關(guān)的數(shù)據(jù)元素復(fù)合而成的數(shù)據(jù)類型成的數(shù)據(jù)類型數(shù)組、字符串、向量、堆棧、隊(duì)列、記錄、樹等數(shù)組、字符串、向量、堆棧、隊(duì)列、記錄、樹等 計(jì)算機(jī)體系結(jié)構(gòu)所要研究的一個(gè)內(nèi)容是：計(jì)算機(jī)體系結(jié)構(gòu)所要研究的一個(gè)內(nèi)容是：在所在所有這些數(shù)據(jù)類型中，哪些用硬件實(shí)現(xiàn)，哪些用軟有這些數(shù)據(jù)類型中，哪些用硬件實(shí)現(xiàn)，哪些用軟件實(shí)

3、現(xiàn)，并研究它們的實(shí)現(xiàn)方法。件實(shí)現(xiàn)，并研究它們的實(shí)現(xiàn)方法。所有系統(tǒng)結(jié)構(gòu)都支持基本數(shù)據(jù)類型所有系統(tǒng)結(jié)構(gòu)都支持基本數(shù)據(jù)類型大多數(shù)系統(tǒng)結(jié)構(gòu)只能部分地支持結(jié)構(gòu)數(shù)據(jù)類型大多數(shù)系統(tǒng)結(jié)構(gòu)只能部分地支持結(jié)構(gòu)數(shù)據(jù)類型數(shù)據(jù)表示：數(shù)據(jù)表示：機(jī)器硬件能直接識(shí)別，并可以被指令調(diào)機(jī)器硬件能直接識(shí)別，并可以被指令調(diào)用的數(shù)據(jù)類型，用的數(shù)據(jù)類型，數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：結(jié)構(gòu)數(shù)據(jù)類型的組織方式。結(jié)構(gòu)數(shù)據(jù)類型的組織方式。 確定哪些數(shù)據(jù)類型用數(shù)據(jù)表示實(shí)現(xiàn)，哪些數(shù)據(jù)類確定哪些數(shù)據(jù)類型用數(shù)據(jù)表示實(shí)現(xiàn)，哪些數(shù)據(jù)類型用數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，是軟硬件的主要分界面之一，型用數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，是軟硬件的主要分界面之一，本質(zhì)上是一個(gè)軟硬取舍問題。本質(zhì)上是一個(gè)軟硬取舍

4、問題。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 基本數(shù)據(jù)類型基本數(shù)據(jù)類型映像存儲(chǔ)器存儲(chǔ)器縮短程序的運(yùn)行時(shí)間縮短程序的運(yùn)行時(shí)間占用存儲(chǔ)空間少占用存儲(chǔ)空間少減少減少CPU和主存的通信量和主存的通信量通用性和利用率通用性和利用率確定哪些數(shù)據(jù)類型用數(shù)據(jù)表示實(shí)現(xiàn)的原則：確定哪些數(shù)據(jù)類型用數(shù)據(jù)表示實(shí)現(xiàn)的原則：例：實(shí)現(xiàn)例：實(shí)現(xiàn)A=A+B，A和和B都是都是200200 的矩陣。的矩陣。標(biāo)量機(jī)：標(biāo)量機(jī)：6 6條指令條指令, , 其中其中4 4條循環(huán)指令要執(zhí)行條循環(huán)指令要執(zhí)行200200* *200200=40000=40000次；因此次；因此CPUCPU與主存之間的通信量為：與主存之間的通信量為：取指令取指令 2 24 4400004

5、0000條；條；讀或?qū)憯?shù)據(jù)讀或?qū)憯?shù)據(jù) 3 34000040000個(gè)；個(gè)；共要訪問主存共要訪問主存 7 74000040000次以上。次以上。通用性不好通用性不好向量機(jī)：向量機(jī)：向量指令：向量指令： 1 1條指令條指令, , 減少取指令操作減少取指令操作4 4* *40000=16000040000=160000次，程序執(zhí)行時(shí)間縮短了一半。次，程序執(zhí)行時(shí)間縮短了一半。對(duì)復(fù)雜的樹數(shù)據(jù)結(jié)構(gòu)的支持較好，高效；對(duì)復(fù)雜的樹數(shù)據(jù)結(jié)構(gòu)的支持較好，高效；但對(duì)向量、數(shù)組、鏈表等其他數(shù)據(jù)結(jié)構(gòu)支持不夠，但對(duì)向量、數(shù)組、鏈表等其他數(shù)據(jù)結(jié)構(gòu)支持不夠，低效。低效。舉例舉例1：引入樹型數(shù)據(jù)表示：引入樹型數(shù)據(jù)表示可高效地對(duì)向量

6、、數(shù)組、鏈表、樹等多種數(shù)據(jù)結(jié)可高效地對(duì)向量、數(shù)組、鏈表、樹等多種數(shù)據(jù)結(jié)構(gòu)提供支持。構(gòu)提供支持。舉例舉例2：引入指針數(shù)據(jù)表示：引入指針數(shù)據(jù)表示通用性好通用性好當(dāng)當(dāng)選擇產(chǎn)生沖突時(shí)，根據(jù)性能選擇產(chǎn)生沖突時(shí)，根據(jù)性能/ /價(jià)格衡量?jī)r(jià)格衡量 從減少?gòu)臏p少CPU和主存的通信量及縮短執(zhí)行時(shí)間兩方面和主存的通信量及縮短執(zhí)行時(shí)間兩方面看，對(duì)于處理矩陣運(yùn)算，向量數(shù)據(jù)表示優(yōu)越性要高。看，對(duì)于處理矩陣運(yùn)算，向量數(shù)據(jù)表示優(yōu)越性要高。實(shí)際系統(tǒng)設(shè)計(jì)實(shí)際系統(tǒng)設(shè)計(jì) 系統(tǒng)結(jié)構(gòu)設(shè)計(jì)的任務(wù)：系統(tǒng)結(jié)構(gòu)設(shè)計(jì)的任務(wù)：確定哪些數(shù)據(jù)類型用硬件確定哪些數(shù)據(jù)類型用硬件即數(shù)據(jù)表示實(shí)現(xiàn)，哪些數(shù)據(jù)類型用軟件實(shí)現(xiàn)，即數(shù)據(jù)表示實(shí)現(xiàn)，哪些數(shù)據(jù)類型用軟件實(shí)現(xiàn)，

7、即數(shù)據(jù)結(jié)構(gòu)，哪些數(shù)據(jù)類型由軟件和硬件共同即數(shù)據(jù)結(jié)構(gòu)，哪些數(shù)據(jù)類型由軟件和硬件共同來實(shí)現(xiàn)。來實(shí)現(xiàn)。復(fù)雜的數(shù)據(jù)類型一般通過數(shù)據(jù)結(jié)構(gòu)或通過軟硬件聯(lián)復(fù)雜的數(shù)據(jù)類型一般通過數(shù)據(jù)結(jié)構(gòu)或通過軟硬件聯(lián)合設(shè)計(jì)實(shí)現(xiàn)合設(shè)計(jì)實(shí)現(xiàn)(如如table、 graph、record、tree等等)簡(jiǎn)單的、常用的、通用的數(shù)據(jù)類型采用數(shù)據(jù)表示簡(jiǎn)單的、常用的、通用的數(shù)據(jù)類型采用數(shù)據(jù)表示(如如int、 float、stack等等)； 數(shù)據(jù)表示是數(shù)據(jù)結(jié)構(gòu)的一個(gè)子集，數(shù)據(jù)表示是數(shù)據(jù)結(jié)構(gòu)的一個(gè)子集，數(shù)據(jù)結(jié)構(gòu)通過數(shù)據(jù)結(jié)構(gòu)通過 一定的算法變成數(shù)據(jù)表示才能在系統(tǒng)中處理；一定的算法變成數(shù)據(jù)表示才能在系統(tǒng)中處理； 數(shù)據(jù)表示是軟、硬件界面的一部分；數(shù)據(jù)

8、結(jié)構(gòu)是數(shù)據(jù)表示是軟、硬件界面的一部分；數(shù)據(jù)結(jié)構(gòu)是軟件和應(yīng)用的一部分。軟件和應(yīng)用的一部分。l 數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)表示的關(guān)系數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)表示的關(guān)系數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)表示數(shù)據(jù)表示軟硬件的界面軟硬件的界面數(shù)據(jù)表示的確定實(shí)質(zhì)上是軟硬件的取舍問題數(shù)據(jù)表示的確定實(shí)質(zhì)上是軟硬件的取舍問題l早期的計(jì)算機(jī)系統(tǒng)只有定點(diǎn)數(shù)據(jù)表示早期的計(jì)算機(jī)系統(tǒng)只有定點(diǎn)數(shù)據(jù)表示優(yōu)點(diǎn)：硬件結(jié)構(gòu)簡(jiǎn)單優(yōu)點(diǎn)：硬件結(jié)構(gòu)簡(jiǎn)單缺點(diǎn)：缺點(diǎn)：l編程困難：先確定小數(shù)點(diǎn)位置，小數(shù)點(diǎn)對(duì)編程困難：先確定小數(shù)點(diǎn)位置，小數(shù)點(diǎn)對(duì)齊再運(yùn)算齊再運(yùn)算l表示數(shù)的范圍?。喝绫硎緮?shù)的范圍?。喝?616位字長(zhǎng)表示的整數(shù)位字長(zhǎng)表示的整數(shù)范圍為：范圍為： -32768-3276832

9、76732767l數(shù)據(jù)存儲(chǔ)單元的利用率很低（數(shù)據(jù)存儲(chǔ)單元的利用率很低（大量的前置大量的前置0 0）2.1.2 浮點(diǎn)數(shù)據(jù)表示浮點(diǎn)數(shù)據(jù)表示l計(jì)算機(jī)中的浮點(diǎn)數(shù)來源于數(shù)學(xué)中的實(shí)數(shù)，但兩者有很多計(jì)算機(jī)中的浮點(diǎn)數(shù)來源于數(shù)學(xué)中的實(shí)數(shù)，但兩者有很多本質(zhì)的區(qū)別：本質(zhì)的區(qū)別： 實(shí)數(shù)：實(shí)數(shù)：表示范圍表示范圍無限，表示精度無限，表示精度連續(xù)。連續(xù)。 浮點(diǎn)數(shù)：浮點(diǎn)數(shù)：表示范圍表示范圍有限，表示精度有限，表示精度不連續(xù)。不連續(xù)。三大特點(diǎn)：表數(shù)范圍、表數(shù)精度和表數(shù)效率三大特點(diǎn)：表數(shù)范圍、表數(shù)精度和表數(shù)效率關(guān)鍵問題：在數(shù)據(jù)字長(zhǎng)確定的情況下，找到具有關(guān)鍵問題：在數(shù)據(jù)字長(zhǎng)確定的情況下，找到具有最最大表數(shù)范圍、最高表數(shù)精度和最大表

10、數(shù)效率大表數(shù)范圍、最高表數(shù)精度和最大表數(shù)效率的浮點(diǎn)的浮點(diǎn)數(shù)表示方式。數(shù)表示方式。-Nmin 0 -NmaxNminNmax可表示可表示的負(fù)數(shù)的負(fù)數(shù)可表示可表示的正數(shù)的正數(shù)負(fù)下負(fù)下溢區(qū)溢區(qū)負(fù)上負(fù)上溢區(qū)溢區(qū)正下正下溢區(qū)溢區(qū)正上正上溢區(qū)溢區(qū)l浮點(diǎn)數(shù)的一般格式：對(duì)任意浮點(diǎn)數(shù)浮點(diǎn)數(shù)的一般格式：對(duì)任意浮點(diǎn)數(shù)N，可表示為：，可表示為：emrmNqere m：尾數(shù)，多采用規(guī)格化小數(shù)表示：尾數(shù)，多采用規(guī)格化小數(shù)表示e： 階碼的值，一般采用整數(shù)、移碼表示階碼的值，一般采用整數(shù)、移碼表示rm ：尾數(shù)的基，一般采用二進(jìn)制、十六進(jìn)制：尾數(shù)的基，一般采用二進(jìn)制、十六進(jìn)制re ：階碼的基，一般采用二進(jìn)制：階碼的基，一般采用

11、二進(jìn)制p：尾數(shù)長(zhǎng)度（不包括符號(hào)位），當(dāng)：尾數(shù)長(zhǎng)度（不包括符號(hào)位），當(dāng)rm 16時(shí)，時(shí)，每四個(gè)二進(jìn)制位表示一位尾數(shù)每四個(gè)二進(jìn)制位表示一位尾數(shù)q：階碼長(zhǎng)度：階碼長(zhǎng)度(不包括階碼的符號(hào)）不包括階碼的符號(hào)）浮點(diǎn)數(shù)的表示需要六個(gè)基本參數(shù)：尾數(shù)浮點(diǎn)數(shù)的表示需要六個(gè)基本參數(shù)：尾數(shù)m m、階碼、階碼e e的的值；尾數(shù)的基值；尾數(shù)的基r rm m、階碼的基、階碼的基r re e、尾數(shù)長(zhǎng)度、尾數(shù)長(zhǎng)度p(p(不包括不包括符號(hào)位符號(hào)位) )、階碼長(zhǎng)度、階碼長(zhǎng)度q (q (不包括符號(hào)位不包括符號(hào)位) )mf ef e m 1 1 q p 在浮點(diǎn)表示方式中尾數(shù)采用規(guī)格化小數(shù)的目的在浮點(diǎn)表示方式中尾數(shù)采用規(guī)格化小數(shù)的目的是

12、為了在尾數(shù)中表示最多的有效數(shù)據(jù)位及數(shù)據(jù)表是為了在尾數(shù)中表示最多的有效數(shù)據(jù)位及數(shù)據(jù)表示的惟一性。示的惟一性。0.00345 0.34510-2尾數(shù)規(guī)格化尾數(shù)規(guī)格化數(shù)符階符l （1 1）表數(shù)范圍：）表數(shù)范圍：在尾數(shù)采用原碼在尾數(shù)采用原碼p p位、純小數(shù)，階碼位、純小數(shù)，階碼q q位采用移碼的位采用移碼的浮點(diǎn)數(shù)表示方式中，規(guī)格化浮點(diǎn)數(shù)浮點(diǎn)數(shù)表示方式中，規(guī)格化浮點(diǎn)數(shù)N的表數(shù)范圍如下：的表數(shù)范圍如下：11)1 (|qeqermpmrmmrrNrr最大正數(shù)：最大正數(shù)：最小正數(shù)：最小正數(shù)：最大負(fù)數(shù)：最大負(fù)數(shù)： 最小負(fù)數(shù)：最小負(fù)數(shù)：表數(shù)范圍：表數(shù)范圍：1)1(qermpmrrqermmrr1qermmrr11

13、)1 (qermpmrr例如：尾數(shù)用原碼，純小數(shù)表示，階碼用移碼整數(shù)例如：尾數(shù)用原碼，純小數(shù)表示，階碼用移碼整數(shù)表示，當(dāng)表示，當(dāng)p=23，q=7， rm = re=2時(shí)，規(guī)格化數(shù)時(shí)，規(guī)格化數(shù)N在在正數(shù)區(qū)間的表數(shù)范圍是：正數(shù)區(qū)間的表數(shù)范圍是：127231282)21 (2)2/1 (N128127232)2/1 (2)21 (N在負(fù)數(shù)區(qū)間的表數(shù)范圍是：在負(fù)數(shù)區(qū)間的表數(shù)范圍是：表示數(shù)的個(gè)數(shù)是：表示數(shù)的個(gè)數(shù)是：1511282422/122 規(guī)格化浮點(diǎn)數(shù)的個(gè)數(shù)應(yīng)是可表示的階碼的個(gè)數(shù)規(guī)格化浮點(diǎn)數(shù)的個(gè)數(shù)應(yīng)是可表示的階碼的個(gè)數(shù)與可表示的尾數(shù)的個(gè)數(shù)的乘積。與可表示的尾數(shù)的個(gè)數(shù)的乘積?，F(xiàn)以階碼為現(xiàn)以階碼為q=2

14、，尾數(shù)，尾數(shù)p=4，正階、正尾數(shù)為例，正階、正尾數(shù)為例，比較比較rm=2和和rm=16時(shí)的不同情況。時(shí)的不同情況。 7 6 5 4 3 2 1 0階符階符00尾符尾符在在尾數(shù)基值尾數(shù)基值rm 2（二進(jìn)制）（二進(jìn)制） ，p=4(即尾數(shù)即尾數(shù)bit3bit0，共，共4位）、做規(guī)格化表示（即此時(shí)位）、做規(guī)格化表示（即此時(shí)bit3=1）的正階、正尾的數(shù)的范圍：）的正階、正尾的數(shù)的范圍：在階碼相同的前提下，尾數(shù)采用不同基值時(shí)，表在階碼相同的前提下，尾數(shù)采用不同基值時(shí)，表示的浮點(diǎn)數(shù)大小及個(gè)數(shù)均不相同。示的浮點(diǎn)數(shù)大小及個(gè)數(shù)均不相同。 可表示的最大正浮點(diǎn)數(shù)為可表示的最大正浮點(diǎn)數(shù)為可表示規(guī)格化的最小正浮點(diǎn)數(shù)為可

15、表示規(guī)格化的最小正浮點(diǎn)數(shù)為可表示的正階、正尾規(guī)格化數(shù)的個(gè)數(shù)為可表示的正階、正尾規(guī)格化數(shù)的個(gè)數(shù)為2/1516/1582)21(342/12201322/1222416/1521144mr最大尾數(shù)為最大尾數(shù)為 最小階碼為最小階碼為 最大階碼為最大階碼為01203122)3 , 2 , 1 , 0(422階碼的個(gè)數(shù)為階碼的個(gè)數(shù)為最小尾數(shù)為最小尾數(shù)為2/1211mr尾數(shù)的個(gè)數(shù)為尾數(shù)的個(gè)數(shù)為1624在在尾數(shù)基值尾數(shù)基值rm 16（十六進(jìn)制）（十六進(jìn)制） q2, p=4(尾數(shù)尾數(shù)bit3bit0，4位二進(jìn)制組成一個(gè)十六進(jìn)制數(shù)）位二進(jìn)制組成一個(gè)十六進(jìn)制數(shù)）,做規(guī)做規(guī)格化表示（即此時(shí)格化表示（即此時(shí)bit3b

16、it0 中必須有中必須有1位為位為“1”，不許出現(xiàn)全不許出現(xiàn)全“0”， bit3bit0 為為00011111）的正）的正階、正尾的數(shù)的范圍：階、正尾的數(shù)的范圍：最小尾數(shù)為最小尾數(shù)為1611611mr16151611最大尾數(shù)為最大尾數(shù)為最小階碼為最小階碼為 最大階碼為最大階碼為0120312122q4222q階碼的個(gè)數(shù)為階碼的個(gè)數(shù)為可表示的最小正浮點(diǎn)數(shù)為可表示的最小正浮點(diǎn)數(shù)為16121612001mr1512p尾數(shù)的個(gè)數(shù)為尾數(shù)的個(gè)數(shù)為可表示的正階、正尾規(guī)格化數(shù)的個(gè)數(shù)為可表示的正階、正尾規(guī)格化數(shù)的個(gè)數(shù)為601522從上述例子，可得到下列兩個(gè)結(jié)論：從上述例子，可得到下列兩個(gè)結(jié)論：（1）當(dāng)有相同階碼

17、與尾數(shù)位數(shù)時(shí)，）當(dāng)有相同階碼與尾數(shù)位數(shù)時(shí)， rm大，則表示大，則表示數(shù)的范圍也大，表示數(shù)的個(gè)數(shù)增多。數(shù)的范圍也大，表示數(shù)的個(gè)數(shù)增多。 rm只能取只能取2，4，8，16，。一般使用。一般使用2，8，16三種。三種。rm=2時(shí)，其個(gè)數(shù)是時(shí)，其個(gè)數(shù)是32?？杀硎镜淖畲笳↑c(diǎn)數(shù)為可表示的最大正浮點(diǎn)數(shù)為384016)161()1(31)12(1qmmrr而而rm=2時(shí)，其最大數(shù)是時(shí)，其最大數(shù)是15/2。（2） rm大時(shí)，雖然表示數(shù)的范圍大，表示數(shù)的大時(shí)，雖然表示數(shù)的范圍大，表示數(shù)的個(gè)數(shù)增加，但在數(shù)值的分布較稀疏。例如在數(shù)軸個(gè)數(shù)增加，但在數(shù)值的分布較稀疏。例如在數(shù)軸1/2-2之間，當(dāng)之間，當(dāng)rm 2時(shí)，有

18、數(shù)時(shí)，有數(shù)15個(gè)；而當(dāng)個(gè)；而當(dāng)rm 16時(shí)，有數(shù)時(shí)，有數(shù)8個(gè)。個(gè)。原因有兩點(diǎn)：一是因?yàn)椴捎靡?guī)格化表示的緣故。如上例中原因有兩點(diǎn)：一是因?yàn)椴捎靡?guī)格化表示的緣故。如上例中rm 2時(shí)，規(guī)格化后，時(shí)，規(guī)格化后，其尾數(shù)個(gè)數(shù)只為原來的其尾數(shù)個(gè)數(shù)只為原來的1/2；二是因?yàn)樵?；二是因?yàn)樵谕L(zhǎng)度階碼時(shí)，同長(zhǎng)度階碼時(shí)， rm不同，每次小數(shù)點(diǎn)移動(dòng)位置不同，如上例不同，每次小數(shù)點(diǎn)移動(dòng)位置不同，如上例中中rm 2時(shí)，時(shí)，1個(gè)階碼值移動(dòng)小數(shù)點(diǎn)個(gè)階碼值移動(dòng)小數(shù)點(diǎn)1bit，而，而rm 16時(shí)，則時(shí)，則移移動(dòng)動(dòng)4bits。故：。故：rm 增大，則表示數(shù)的個(gè)數(shù)增加，數(shù)值上分布稀增大，則表示數(shù)的個(gè)數(shù)增加，數(shù)值上分布稀疏，從而計(jì)算誤

19、差增加。疏，從而計(jì)算誤差增加。rm =2, 20(0.10010.1111) , 21(0.10.1111)rm =16, 160(0.10010.1111) , 161(0.0001） 1/2 1 2l【例【例1】某計(jì)算機(jī)的浮點(diǎn)數(shù)采用】某計(jì)算機(jī)的浮點(diǎn)數(shù)采用1位符號(hào)位、位符號(hào)位、6位階位階碼和碼和9位尾數(shù)，基數(shù)為位尾數(shù)，基數(shù)為16，求規(guī)格化時(shí)它能表示數(shù)，求規(guī)格化時(shí)它能表示數(shù)值的個(gè)數(shù)。值的個(gè)數(shù)。解：此浮點(diǎn)數(shù)共有解：此浮點(diǎn)數(shù)共有16位位階碼為階碼為q=5，尾數(shù)位數(shù)，尾數(shù)位數(shù)p=9，re =2和和rm =16。尾數(shù)用原碼表示，階碼采用移碼。尾數(shù)用原碼表示，階碼采用移碼。可表示的正階、正尾規(guī)格化數(shù)的個(gè)

20、數(shù)為可表示的正階、正尾規(guī)格化數(shù)的個(gè)數(shù)為)162(2213339最大階碼為最大階碼為3112125q32225q階碼的個(gè)數(shù)為階碼的個(gè)數(shù)為最大尾數(shù)為最大尾數(shù)為 (0.1FF)402322162l【例【例1】某計(jì)算機(jī)的浮點(diǎn)數(shù)采用】某計(jì)算機(jī)的浮點(diǎn)數(shù)采用1位符號(hào)位、位符號(hào)位、7位階位階碼（移碼）和碼（移碼）和8位尾數(shù)（原碼規(guī)格化），基數(shù)為位尾數(shù)（原碼規(guī)格化），基數(shù)為2，數(shù)據(jù)數(shù)據(jù)1在這種浮點(diǎn)格式中的表示為在這種浮點(diǎn)格式中的表示為 ，這種，這種浮點(diǎn)表示的大于浮點(diǎn)表示的大于1的最小數(shù)是的最小數(shù)是 。解：此浮點(diǎn)數(shù)共有解：此浮點(diǎn)數(shù)共有16位，格式如下：位，格式如下： 10.1211: 0 1000001 , 10

21、0000001最小數(shù)：最小數(shù)： 0 1000001 , 10000001規(guī)格化表示的最小尾數(shù) 15 14 9 8 0數(shù)符數(shù)符尾數(shù)尾數(shù)階碼階碼最小正尾數(shù)為：最小正尾數(shù)為：0.100000000可表示的正規(guī)格化浮點(diǎn)數(shù)的個(gè)數(shù)為可表示的正規(guī)格化浮點(diǎn)數(shù)的個(gè)數(shù)為可表示的負(fù)階、正尾規(guī)格化數(shù)的個(gè)數(shù)為可表示的負(fù)階、正尾規(guī)格化數(shù)的個(gè)數(shù)為4023221624123221622可表示的正、負(fù)規(guī)格化浮點(diǎn)數(shù)的個(gè)數(shù)為可表示的正、負(fù)規(guī)格化浮點(diǎn)數(shù)的個(gè)數(shù)為4241222 從上面的分析可以看到，規(guī)格化浮點(diǎn)數(shù)的表數(shù)范從上面的分析可以看到，規(guī)格化浮點(diǎn)數(shù)的表數(shù)范圍主要與階碼的長(zhǎng)度圍主要與階碼的長(zhǎng)度q和和rm尾數(shù)基值有關(guān)，這時(shí)，尾數(shù)基值有

22、關(guān)，這時(shí)，能表示的絕對(duì)值最大的浮點(diǎn)數(shù)可近似為：能表示的絕對(duì)值最大的浮點(diǎn)數(shù)可近似為：qermrNmax 表數(shù)范圍表數(shù)范圍隨著隨著q和和rm的增大而擴(kuò)大。當(dāng)有相同階碼的增大而擴(kuò)大。當(dāng)有相同階碼與尾數(shù)位數(shù)時(shí)，與尾數(shù)位數(shù)時(shí)， rm大，則表示數(shù)的范圍大。但大，則表示數(shù)的范圍大。但rm大大時(shí)，在數(shù)軸上的分布較稀疏。時(shí)，在數(shù)軸上的分布較稀疏。 當(dāng)浮點(diǎn)數(shù)的尾數(shù)長(zhǎng)度相同時(shí)，尾基為當(dāng)浮點(diǎn)數(shù)的尾數(shù)長(zhǎng)度相同時(shí)，尾基為2 2時(shí)具有時(shí)具有最高的表數(shù)精度。最高的表數(shù)精度。 表數(shù)精度也稱為表數(shù)誤差，浮點(diǎn)數(shù)存在表數(shù)精表數(shù)精度也稱為表數(shù)誤差，浮點(diǎn)數(shù)存在表數(shù)精度的根本原因是由于浮點(diǎn)數(shù)的不連續(xù)性造成的。度的根本原因是由于浮點(diǎn)數(shù)的不連

23、續(xù)性造成的。浮點(diǎn)數(shù)表示的僅僅是實(shí)數(shù)的一個(gè)子集。浮點(diǎn)數(shù)表示的僅僅是實(shí)數(shù)的一個(gè)子集。規(guī)格化浮點(diǎn)數(shù)的表數(shù)精度主要與尾數(shù)基值和尾規(guī)格化浮點(diǎn)數(shù)的表數(shù)精度主要與尾數(shù)基值和尾數(shù)長(zhǎng)度有關(guān)，一般認(rèn)為尾數(shù)最后數(shù)長(zhǎng)度有關(guān)，一般認(rèn)為尾數(shù)最后1位值的一半定位值的一半定義為表數(shù)精度義為表數(shù)精度)2(21mpmrr)16(21mpmrr在在尾數(shù)基值尾數(shù)基值rm 16（十六進(jìn)制）（十六進(jìn)制） re 2, 尾數(shù)尾數(shù)4位位（4位二進(jìn)制組成一個(gè)十六進(jìn)制數(shù)）、位二進(jìn)制組成一個(gè)十六進(jìn)制數(shù)）、q=2時(shí)做規(guī)時(shí)做規(guī)格化表示的最大正數(shù)、正規(guī)格化數(shù)的個(gè)數(shù)及一個(gè)格化表示的最大正數(shù)、正規(guī)格化數(shù)的個(gè)數(shù)及一個(gè)數(shù)量單位的大?。簲?shù)量單位的大?。簉m 2，正

24、規(guī)格化尾數(shù)的個(gè)數(shù)，正規(guī)格化尾數(shù)的個(gè)數(shù)8個(gè)，最大正數(shù)為個(gè)，最大正數(shù)為 (124) 22 ，一個(gè)數(shù)量單位，一個(gè)數(shù)量單位=(24)221/4當(dāng)表示的浮點(diǎn)數(shù)有相同的位數(shù)、尾數(shù)時(shí)，當(dāng)表示的浮點(diǎn)數(shù)有相同的位數(shù)、尾數(shù)時(shí)，rm=2，有最，有最大的表數(shù)精度。大的表數(shù)精度。rm 16，正規(guī)格化尾數(shù)的個(gè)數(shù)，正規(guī)格化尾數(shù)的個(gè)數(shù)15個(gè)，最大正數(shù)為個(gè)，最大正數(shù)為 （1161）162，一個(gè)數(shù)量單位，一個(gè)數(shù)量單位=(1/16)16216 尾數(shù)基值尾數(shù)基值rm2與與rm16相比，顯然基值越大相比，顯然基值越大浮點(diǎn)數(shù)的表數(shù)效率高。浮點(diǎn)數(shù)的表數(shù)效率高。mmqepmqepmmrrrrrrr12212)1(21全部浮點(diǎn)數(shù)個(gè)數(shù)可表示的規(guī)

25、格化浮點(diǎn)數(shù)浮點(diǎn)數(shù)的表數(shù)效率定義為浮點(diǎn)數(shù)的表數(shù)效率定義為l浮點(diǎn)數(shù)的表數(shù)范圍、表數(shù)精度和表數(shù)效率三個(gè)主浮點(diǎn)數(shù)的表數(shù)范圍、表數(shù)精度和表數(shù)效率三個(gè)主要特征都與尾數(shù)基值要特征都與尾數(shù)基值rm有關(guān)。有關(guān)。（4 4）浮點(diǎn)數(shù)尾數(shù)基值的選擇）浮點(diǎn)數(shù)尾數(shù)基值的選擇rm 2 2，表數(shù)效率只有，表數(shù)效率只有50%50%，為了提高表數(shù)效率，為了提高表數(shù)效率，許多計(jì)算機(jī)采用了隱藏位表示法，此時(shí)表數(shù)效率許多計(jì)算機(jī)采用了隱藏位表示法，此時(shí)表數(shù)效率100%100%； 當(dāng)浮點(diǎn)數(shù)字長(zhǎng)確定后，當(dāng)浮點(diǎn)數(shù)字長(zhǎng)確定后，rm取取2 2，具有最大的表，具有最大的表數(shù)范圍、表數(shù)效率和最高的表數(shù)精度。數(shù)范圍、表數(shù)效率和最高的表數(shù)精度。但但rm 4

26、時(shí)，就不能采用隱藏位表數(shù)法，因?yàn)槲矓?shù)時(shí)，就不能采用隱藏位表數(shù)法，因?yàn)槲矓?shù)可以從可以從00、01、10、11中取值，中取值，IBM370系列機(jī)、系列機(jī)、IBM4300系列機(jī)等浮點(diǎn)數(shù)的尾系列機(jī)等浮點(diǎn)數(shù)的尾數(shù)是數(shù)是16；Burroughs公司的公司的B6700,B7700等大型計(jì)算機(jī)，等大型計(jì)算機(jī)，浮點(diǎn)數(shù)尾數(shù)的基值是浮點(diǎn)數(shù)尾數(shù)的基值是8；DEC公司的公司的VAX-11、CDC公司公司CDC6600等大型等大型機(jī)以及機(jī)以及Intel公司的公司的X86系列機(jī)等的浮點(diǎn)數(shù)均采用系列機(jī)等的浮點(diǎn)數(shù)均采用尾數(shù)基值為尾數(shù)基值為2。應(yīng)用情況：應(yīng)用情況：l浮點(diǎn)數(shù)加法中的對(duì)階、規(guī)格化右移操作以及乘浮點(diǎn)數(shù)加法中的對(duì)階、規(guī)格

27、化右移操作以及乘法中結(jié)果取單倍長(zhǎng)度會(huì)把有效位移掉或截掉從法中結(jié)果取單倍長(zhǎng)度會(huì)把有效位移掉或截掉從而造成精度損失。而造成精度損失。（5 5）浮點(diǎn)數(shù)的下溢處理）浮點(diǎn)數(shù)的下溢處理尾數(shù)下溢處理方式：尾數(shù)下溢處理方式：（1）截?cái)嘟財(cái)唷Ｒ卜Q為不舍入法。簡(jiǎn)單地將下溢部分截去。也稱為不舍入法。簡(jiǎn)單地將下溢部分截去。在整數(shù)運(yùn)算中最大會(huì)接近于在整數(shù)運(yùn)算中最大會(huì)接近于1；誤差大都是負(fù)誤差。；誤差大都是負(fù)誤差。（2）舍入法舍入法。被截尾數(shù)為。被截尾數(shù)為1進(jìn)進(jìn)1，運(yùn)算中最大誤差小于一半。，運(yùn)算中最大誤差小于一半。（3）恒置恒置1法法。被截尾數(shù)無論是。被截尾數(shù)無論是0是是1，恒置，恒置1。最大誤差比截。最大誤差比截?cái)喾ù?/p>

28、。斷法大。（4）ROM或或PLA法法。也稱查表舍入法，平均誤差接近于零。也稱查表舍入法，平均誤差接近于零。l自定義數(shù)據(jù)表示（自定義數(shù)據(jù)表示（Self-definingSelf-defining）帶標(biāo)志符的數(shù)據(jù)表示帶標(biāo)志符的數(shù)據(jù)表示數(shù)據(jù)描述符數(shù)據(jù)描述符l向量數(shù)據(jù)表示向量數(shù)據(jù)表示l堆棧數(shù)據(jù)表示堆棧數(shù)據(jù)表示 內(nèi)容：內(nèi)容：堆棧、向量、數(shù)組（隊(duì)列）、記錄、自堆棧、向量、數(shù)組（隊(duì)列）、記錄、自定義等。定義等。 目的：目的：支持?jǐn)?shù)據(jù)結(jié)構(gòu)，提高支持?jǐn)?shù)據(jù)結(jié)構(gòu)，提高系統(tǒng)效率和性能系統(tǒng)效率和性能/ /價(jià)價(jià)格比。格比。 注意點(diǎn)：注意點(diǎn)： 新數(shù)據(jù)表示引入的可行性（原則）；新數(shù)據(jù)表示引入的可行性（原則）； 新數(shù)據(jù)表示的必

29、要條件（指令系統(tǒng)和硬件器件）；新數(shù)據(jù)表示的必要條件（指令系統(tǒng)和硬件器件）； 新數(shù)據(jù)表示的存取方法（如稀疏向量表示）新數(shù)據(jù)表示的存取方法（如稀疏向量表示）。l引入思想：引入思想：減小高級(jí)語(yǔ)言和機(jī)器語(yǔ)言的語(yǔ)義差距，減減小高級(jí)語(yǔ)言和機(jī)器語(yǔ)言的語(yǔ)義差距，減輕編譯軟件的工作量（減少指令種類）輕編譯軟件的工作量（減少指令種類）l分類分類帶標(biāo)志符數(shù)據(jù)表示帶標(biāo)志符數(shù)據(jù)表示數(shù)據(jù)描述符數(shù)據(jù)描述符l定義：用以定義：用以定義某個(gè)數(shù)據(jù)的數(shù)據(jù)類型和數(shù)值的定義某個(gè)數(shù)據(jù)的數(shù)據(jù)類型和數(shù)值的數(shù)據(jù)表示數(shù)據(jù)表示。格式如下：。格式如下： 類型標(biāo)志主要用于指明數(shù)據(jù)類型（如二進(jìn)制類型標(biāo)志主要用于指明數(shù)據(jù)類型（如二進(jìn)制整數(shù)、十進(jìn)制整數(shù)等，也

30、可用于指明機(jī)器內(nèi)部所整數(shù)、十進(jìn)制整數(shù)等，也可用于指明機(jī)器內(nèi)部所用信息的各種類型）。用信息的各種類型）。 標(biāo)志符由編譯程序建立，對(duì)高級(jí)語(yǔ)言程序員標(biāo)志符由編譯程序建立，對(duì)高級(jí)語(yǔ)言程序員來說是透明的。來說是透明的。類型標(biāo)志類型標(biāo)志 數(shù)據(jù)數(shù)據(jù)l優(yōu)點(diǎn)：優(yōu)點(diǎn)：簡(jiǎn)化指令系統(tǒng)和程序設(shè)計(jì)簡(jiǎn)化指令系統(tǒng)和程序設(shè)計(jì)簡(jiǎn)化了系統(tǒng)程序和編譯程序的設(shè)計(jì)簡(jiǎn)化了系統(tǒng)程序和編譯程序的設(shè)計(jì)便于一致性校驗(yàn)便于一致性校驗(yàn)?zāi)苡捎布詣?dòng)完成數(shù)據(jù)類型的變換能由硬件自動(dòng)完成數(shù)據(jù)類型的變換支持?jǐn)?shù)據(jù)庫(kù)系統(tǒng)的實(shí)現(xiàn)與數(shù)據(jù)類型無關(guān)的要求支持?jǐn)?shù)據(jù)庫(kù)系統(tǒng)的實(shí)現(xiàn)與數(shù)據(jù)類型無關(guān)的要求為軟件調(diào)試和應(yīng)用軟件開發(fā)提供支持為軟件調(diào)試和應(yīng)用軟件開發(fā)提供支持l缺點(diǎn)：缺點(diǎn)：硬

31、件設(shè)計(jì)的復(fù)雜度增加（數(shù)據(jù)類型轉(zhuǎn)換、一致性硬件設(shè)計(jì)的復(fù)雜度增加（數(shù)據(jù)類型轉(zhuǎn)換、一致性檢驗(yàn)等）檢驗(yàn)等）降低指令的執(zhí)行速度降低指令的執(zhí)行速度必須用專門的指令完成標(biāo)志符的初始化必須用專門的指令完成標(biāo)志符的初始化l引入可行性分析引入可行性分析存儲(chǔ)空間是否減少？存儲(chǔ)空間是否減少？ BA數(shù)據(jù)數(shù)據(jù)指令指令總數(shù)少總數(shù)少總數(shù)多總數(shù)多通常有面積通常有面積B面積面積A采用標(biāo)志符后采用標(biāo)志符后 數(shù)據(jù)字增長(zhǎng)數(shù)據(jù)字增長(zhǎng)不采用標(biāo)志符不采用標(biāo)志符采用標(biāo)志符后采用標(biāo)志符后 指令字縮短指令字縮短l例例2.2 設(shè)處理機(jī)設(shè)處理機(jī)A的數(shù)據(jù)不帶標(biāo)志符，指令字長(zhǎng)和的數(shù)據(jù)不帶標(biāo)志符，指令字長(zhǎng)和數(shù)據(jù)字長(zhǎng)都是數(shù)據(jù)字長(zhǎng)都是32位，設(shè)處理機(jī)位，設(shè)處理

32、機(jī)B的數(shù)據(jù)帶的數(shù)據(jù)帶3位標(biāo)志位標(biāo)志符，使數(shù)據(jù)字長(zhǎng)增至符，使數(shù)據(jù)字長(zhǎng)增至35位，但可使指令字長(zhǎng)減少位，但可使指令字長(zhǎng)減少至至30位?，F(xiàn)有位。現(xiàn)有1個(gè)程序正在處理機(jī)個(gè)程序正在處理機(jī)A和和B上運(yùn)行的上運(yùn)行的目標(biāo)程序都有目標(biāo)程序都有IC條指令，平均每條指令訪問條指令，平均每條指令訪問2個(gè)個(gè)操作數(shù)，每個(gè)操作數(shù)重復(fù)訪問操作數(shù)，每個(gè)操作數(shù)重復(fù)訪問R次。次。l（1）分別計(jì)算程序在處理機(jī)）分別計(jì)算程序在處理機(jī)A和和B上占用的存儲(chǔ)上占用的存儲(chǔ)空間大小?？臻g大小。l（2）在什么條件下，程序在處理機(jī)）在什么條件下，程序在處理機(jī)B上占用的存上占用的存儲(chǔ)空間才小于在處理機(jī)儲(chǔ)空間才小于在處理機(jī)A上占用的存儲(chǔ)空間？上占用的存

33、儲(chǔ)空間？RICICMA32232l解解 （1）程序在處理機(jī)）程序在處理機(jī)A上占用的存儲(chǔ)空間上占用的存儲(chǔ)空間RICICMB35230l程序在處理機(jī)程序在處理機(jī)B上占用的存儲(chǔ)空間上占用的存儲(chǔ)空間l（2）為實(shí)現(xiàn)）為實(shí)現(xiàn)MB3，即當(dāng)操作數(shù)平均重復(fù)訪問次數(shù)，即當(dāng)操作數(shù)平均重復(fù)訪問次數(shù)R3，在帶標(biāo)志符的數(shù)據(jù)表示的處理機(jī)上運(yùn)行的程序占用的在帶標(biāo)志符的數(shù)據(jù)表示的處理機(jī)上運(yùn)行的程序占用的存儲(chǔ)空間會(huì)減小。存儲(chǔ)空間會(huì)減小。實(shí)現(xiàn)時(shí)間是否減少？實(shí)現(xiàn)時(shí)間是否減少？l取出數(shù)據(jù)后轉(zhuǎn)換，必須推遲到運(yùn)行時(shí)間進(jìn)行取出數(shù)據(jù)后轉(zhuǎn)換，必須推遲到運(yùn)行時(shí)間進(jìn)行l(wèi)專門的指令用于標(biāo)志符初始化，增加了輔助專門的指令用于標(biāo)志符初始化，增加了輔助開銷

34、開銷l指令執(zhí)行過程中，對(duì)每個(gè)標(biāo)志符進(jìn)行逐個(gè)解指令執(zhí)行過程中，對(duì)每個(gè)標(biāo)志符進(jìn)行逐個(gè)解釋，并判斷數(shù)據(jù)是否相容，因此單條指令的釋，并判斷數(shù)據(jù)是否相容，因此單條指令的執(zhí)行速度降低，但宏觀執(zhí)行時(shí)間減少執(zhí)行速度降低，但宏觀執(zhí)行時(shí)間減少宏觀時(shí)間宏觀時(shí)間= =設(shè)計(jì)時(shí)間設(shè)計(jì)時(shí)間+ +編譯時(shí)間編譯時(shí)間+ +調(diào)試時(shí)間調(diào)試時(shí)間通用性和利用率通用性和利用率這是一種理想的數(shù)據(jù)表示模式，通用性較好；這是一種理想的數(shù)據(jù)表示模式，通用性較好；只用一種存儲(chǔ)器，利用率不高，采用指令和數(shù)只用一種存儲(chǔ)器，利用率不高，采用指令和數(shù)據(jù)存儲(chǔ)器后，利用率不會(huì)降低。據(jù)存儲(chǔ)器后，利用率不會(huì)降低。l結(jié)論結(jié)論運(yùn)行時(shí)間增加，存儲(chǔ)空間減少。運(yùn)行時(shí)間增加，

35、存儲(chǔ)空間減少。減小高級(jí)語(yǔ)言和機(jī)器語(yǔ)言的語(yǔ)義差距減小高級(jí)語(yǔ)言和機(jī)器語(yǔ)言的語(yǔ)義差距通用機(jī)中不使用，專用機(jī)（支持動(dòng)態(tài)數(shù)據(jù)通用機(jī)中不使用，專用機(jī)（支持動(dòng)態(tài)數(shù)據(jù)類型如類型如LISPLISP和和PROLOGPROLOG）中使用）中使用l目的：描述復(fù)雜和多維的結(jié)構(gòu)類型，進(jìn)一步減目的：描述復(fù)雜和多維的結(jié)構(gòu)類型，進(jìn)一步減少標(biāo)志符所占的存貯空間。少標(biāo)志符所占的存貯空間。舉例：現(xiàn)以美國(guó)現(xiàn)以美國(guó)BurroughsBurroughs公司的公司的B6500B6500，75007500為例為例進(jìn)行自定義數(shù)據(jù)表示的說明，格式如下：進(jìn)行自定義數(shù)據(jù)表示的說明，格式如下：描述符描述符標(biāo)志位標(biāo)志位特征標(biāo)記特征標(biāo)記數(shù)據(jù)塊長(zhǎng)度數(shù)據(jù)塊長(zhǎng)度

36、數(shù)據(jù)塊起始地址數(shù)據(jù)塊起始地址382020格式：格式：數(shù)據(jù)數(shù)據(jù)000數(shù)值數(shù)值描述符描述符101P CISRTD長(zhǎng)度長(zhǎng)度地址地址3111120220111：不連續(xù)數(shù)據(jù)：不連續(xù)數(shù)據(jù)0：連續(xù)數(shù)據(jù)：連續(xù)數(shù)據(jù)1：數(shù)據(jù)集中的一個(gè)：數(shù)據(jù)集中的一個(gè)0：數(shù)據(jù)集的全體：數(shù)據(jù)集的全體只準(zhǔn)讀出的數(shù)據(jù)只準(zhǔn)讀出的數(shù)據(jù)00：數(shù)據(jù)描述符：數(shù)據(jù)描述符寫其他描述符寫其他描述符0：不在主存中：不在主存中1：在主存中：在主存中0：?jiǎn)尉葦?shù)據(jù)：?jiǎn)尉葦?shù)據(jù)1：雙精度數(shù)據(jù)：雙精度數(shù)據(jù)l優(yōu)點(diǎn)優(yōu)點(diǎn): :實(shí)現(xiàn)陣列數(shù)據(jù)的索引比變址方法實(shí)現(xiàn)的好，實(shí)現(xiàn)陣列數(shù)據(jù)的索引比變址方法實(shí)現(xiàn)的好，而且能檢查程序設(shè)計(jì)中陣列越界錯(cuò)誤而且能檢查程序設(shè)計(jì)中陣列越界錯(cuò)誤為向

37、量、數(shù)組數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)提供一定的支為向量、數(shù)組數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)提供一定的支持，有利于簡(jiǎn)化編譯中的代碼生成持，有利于簡(jiǎn)化編譯中的代碼生成l引入可行性分析：同帶標(biāo)志符的數(shù)據(jù)表示引入可行性分析：同帶標(biāo)志符的數(shù)據(jù)表示l描述符的工作過程如下圖描述符的工作過程如下圖101000000101101101XY操作碼操作碼指令指令描述符描述符描述符描述符地址生成邏輯地址生成邏輯（數(shù)據(jù)）（數(shù)據(jù)）（數(shù)據(jù)）（數(shù)據(jù)）數(shù)據(jù)塊數(shù)據(jù)塊數(shù)據(jù)塊數(shù)據(jù)塊主存儲(chǔ)器主存儲(chǔ)器1013101410141014000(a11)000(a12)000(a13)000(a14)000(a21)000(a22)000(a23)000(a24)000(

38、a31)000(a32)000(a33)000(a34)陣列描述符三元素向量3*4 二維陣列Aa11 a12 a13 a14a21 a22 a23 a24a31 a32 a33 a343*4 二維陣列用描述符描述二維陣列l(wèi)標(biāo)志符是和每一個(gè)數(shù)據(jù)相連的，合存在一個(gè)標(biāo)志符是和每一個(gè)數(shù)據(jù)相連的，合存在一個(gè)存儲(chǔ)單元中，描述單個(gè)數(shù)據(jù)的類型特征。存儲(chǔ)單元中，描述單個(gè)數(shù)據(jù)的類型特征。l描述符是和數(shù)據(jù)分開存放的，專門用來描述描述符是和數(shù)據(jù)分開存放的，專門用來描述所要訪問的數(shù)據(jù)是整塊數(shù)據(jù)還是單塊數(shù)據(jù)，所要訪問的數(shù)據(jù)是整塊數(shù)據(jù)還是單塊數(shù)據(jù)，訪問該數(shù)據(jù)塊或數(shù)據(jù)元素所需要的地址以及訪問該數(shù)據(jù)塊或數(shù)據(jù)元素所需要的地址以及

39、其他特征信息等。其他特征信息等。l向量表示向量表示向量通常是指由標(biāo)量的一組有序集合表示的向量通常是指由標(biāo)量的一組有序集合表示的量，類似于一維數(shù)組量，類似于一維數(shù)組標(biāo)量通常只是一個(gè)整數(shù)或?qū)崝?shù)標(biāo)量通常只是一個(gè)整數(shù)或?qū)崝?shù)數(shù)組數(shù)組 A=(aA=(a0 0,a,a1 1,a,a2 2,a,an-1n-1) )可看成向量可看成向量Aa0a1a11l 向量在主存儲(chǔ)器中的存放原則：向量在主存儲(chǔ)器中的存放原則： 規(guī)律性、地址計(jì)算簡(jiǎn)單、訪存沖突小規(guī)律性、地址計(jì)算簡(jiǎn)單、訪存沖突小元素相鄰存放元素相鄰存放元素等間距存放元素等間距存放l向量計(jì)算機(jī)向量計(jì)算機(jī)- -處理向量數(shù)據(jù)的計(jì)算機(jī)處理向量數(shù)據(jù)的計(jì)算機(jī)l舉例：計(jì)算舉例：

40、計(jì)算 c ci i=a=ai i+b+bi i, I=10,11,1000, I=10,11,1000無向量數(shù)據(jù)表示無向量數(shù)據(jù)表示(C(C語(yǔ)言語(yǔ)言) )：lfor(i=10; i=1000; i+)for(i=10; i=1000; i+)l ci=ai+bi; ci=ai+bi;向量數(shù)據(jù)表示：向量數(shù)據(jù)表示：lC(10:1000)=A(10:1000)+B(10:1000)C(10:1000)=A(10:1000)+B(10:1000)向量加A向量參數(shù)B向量參數(shù)C向量參數(shù)向量加 X A Y B Z Cl向量指令及包含的參數(shù)向量指令及包含的參數(shù)基地址、位移量、向量長(zhǎng)度基地址、位移量、向量長(zhǎng)度格式

41、如下：格式如下：A,B,C:存放A,B,C的向量基址及長(zhǎng)度X,Y,Z:寄存器號(hào)，存放A,B,C的位移量向量長(zhǎng)度位移量基地址起始地址（基址+位移）向量的有效長(zhǎng)度向量編址所用的參數(shù)注：向量起始地址注：向量起始地址= =基址基址+ +位移量位移量 向量有效長(zhǎng)度向量有效長(zhǎng)度= =向量長(zhǎng)度向量長(zhǎng)度- -位移量位移量 向量的數(shù)據(jù)地址起始地址位移量向量的數(shù)據(jù)地址起始地址位移量a0an-1a10l舉例：計(jì)算舉例：計(jì)算C(4C(4：11)=A(411)=A(4：11)+B(-411)+B(-4：3)3)A0A3A2A1A11A10A9A8A7A6A5A4C0C3C2C1C11C10C9C8C7C6C5C4B3B

42、2B1B0B-1B-2B-3B-4源向量源向量A結(jié)果向量結(jié)果向量C源向量源向量B位移量位移量Ad=4基址基址Ab起始地址起始地址 As=4Ae=12-4=8Cd基址基址Cb起始地址起始地址 Cs=4Ce=12-4=8起始地址起始地址 Bs=4 Be=4 ( 4) =8位移量位移量 Bd=4基址基址Bb向量起始地址向量起始地址= =基址基址+ +位移量位移量向量有效長(zhǎng)度向量有效長(zhǎng)度= =向量長(zhǎng)度向量長(zhǎng)度- -位移量位移量l稀疏向量的壓縮稀疏向量的壓縮采用隱蔽位向量法（壓縮向量）采用隱蔽位向量法（壓縮向量）存取過程如圖示：存取過程如圖示：A0A3A4A5 (0)A6 (0)A7A1 (0)A2 (

43、0)012356471A00A10A20A61A31A41A70A5A0稀疏向量稀疏向量A3A4A7壓縮向量壓縮向量Z向量（有序位向量）向量（有序位向量）l在描述符數(shù)據(jù)表示的機(jī)器中，只能提供在描述符數(shù)據(jù)表示的機(jī)器中，只能提供描述符寄存器和簡(jiǎn)單的地址形成邏輯等描述符寄存器和簡(jiǎn)單的地址形成邏輯等硬件，雖能支持向量數(shù)據(jù)結(jié)構(gòu)的運(yùn)算，硬件，雖能支持向量數(shù)據(jù)結(jié)構(gòu)的運(yùn)算，但運(yùn)行速度較慢。但運(yùn)行速度較慢。l在向量數(shù)據(jù)表示的機(jī)器中，有豐富的向在向量數(shù)據(jù)表示的機(jī)器中，有豐富的向量運(yùn)算指令，有大量的向量寄存器和并量運(yùn)算指令，有大量的向量寄存器和并行、高速流水運(yùn)算部件的支持，可以實(shí)行、高速流水運(yùn)算部件的支持，可以實(shí)現(xiàn)

44、向量運(yùn)算的高速執(zhí)行現(xiàn)向量運(yùn)算的高速執(zhí)行。 通用寄存器型機(jī)器對(duì)堆棧數(shù)據(jù)結(jié)構(gòu)支持較差，表通用寄存器型機(jī)器對(duì)堆棧數(shù)據(jù)結(jié)構(gòu)支持較差，表現(xiàn)為：現(xiàn)為：- 堆棧指令少，功能單一；堆棧指令少，功能單一；- 堆棧置于存儲(chǔ)器內(nèi)，訪問堆棧速度慢堆棧置于存儲(chǔ)器內(nèi)，訪問堆棧速度慢以寄存器尋址方式指令為主以寄存器尋址方式指令為主通用寄存器型機(jī)器。通用寄存器型機(jī)器。高級(jí)語(yǔ)言機(jī)器：高級(jí)語(yǔ)言和機(jī)器語(yǔ)言合二為一，高級(jí)語(yǔ)言機(jī)器：高級(jí)語(yǔ)言和機(jī)器語(yǔ)言合二為一，高級(jí)語(yǔ)言不用編譯，直接由機(jī)器硬件解釋執(zhí)行。高級(jí)語(yǔ)言不用編譯，直接由機(jī)器硬件解釋執(zhí)行。如如LISP,PROLOG計(jì)算機(jī)等。計(jì)算機(jī)等。 堆棧機(jī)器：堆棧機(jī)器：具有堆棧數(shù)據(jù)表示的機(jī)器具有

45、堆棧數(shù)據(jù)表示的機(jī)器,以堆棧尋以堆棧尋址方式指令為主。址方式指令為主。主存主存寄存器寄存器控制控制邏輯邏輯堆棧堆棧l 有若干高速寄存器組成的硬件堆棧，并附加控制有若干高速寄存器組成的硬件堆棧，并附加控制電路讓它與主存中的堆棧區(qū)在邏輯上組成一個(gè)整體，電路讓它與主存中的堆棧區(qū)在邏輯上組成一個(gè)整體，使堆棧的訪問速度是寄存器的，堆棧的容量是主存使堆棧的訪問速度是寄存器的，堆棧的容量是主存的。的。l有很豐富的堆棧操作類指令且功能很強(qiáng)，直接有很豐富的堆棧操作類指令且功能很強(qiáng)，直接可對(duì)堆棧中的數(shù)據(jù)進(jìn)行各種運(yùn)算和處理可對(duì)堆棧中的數(shù)據(jù)進(jìn)行各種運(yùn)算和處理l有力地支持高級(jí)語(yǔ)言程序的編譯；逆波蘭表達(dá)有力地支持高級(jí)語(yǔ)言程

46、序的編譯；逆波蘭表達(dá)式式如：如：F=AF=A* *B+C/(D-E)B+C/(D-E)逆波蘭表達(dá)式：逆波蘭表達(dá)式：ABAB* *CDE-/+ CDE-/+ 堆棧指令程序堆棧指令程序l有力地支持子程序的嵌套和遞歸調(diào)用有力地支持子程序的嵌套和遞歸調(diào)用qrsti+1i+2i+3irsti+1iiiq嵌套調(diào)用間接遞歸直接遞歸i+1子程序現(xiàn)場(chǎng)信息返回地址r局部性參數(shù)i子程序現(xiàn)場(chǎng)信息返回地址q局部性參數(shù).全局參數(shù)i+1子程序i子程序用堆棧實(shí)現(xiàn)子程序的嵌套和遞歸調(diào)用數(shù)據(jù)表示小結(jié)：數(shù)據(jù)表示小結(jié)：分類：分類： 基本數(shù)據(jù)表示基本數(shù)據(jù)表示 高級(jí)數(shù)據(jù)表示高級(jí)數(shù)據(jù)表示標(biāo)志符標(biāo)志符描述符描述符自定義數(shù)據(jù)表示自定義數(shù)據(jù)表示

47、向量數(shù)據(jù)表示向量數(shù)據(jù)表示堆棧數(shù)據(jù)表示堆棧數(shù)據(jù)表示引入數(shù)據(jù)表示的原則：引入數(shù)據(jù)表示的原則：（1）系統(tǒng)效率高）系統(tǒng)效率高（2）通用性和利用率高）通用性和利用率高數(shù)據(jù)表示和數(shù)據(jù)結(jié)構(gòu)的關(guān)系數(shù)據(jù)表示和數(shù)據(jù)結(jié)構(gòu)的關(guān)系數(shù)據(jù)表示是數(shù)據(jù)結(jié)構(gòu)的一個(gè)子集，面向硬件；數(shù)據(jù)表示是數(shù)據(jù)結(jié)構(gòu)的一個(gè)子集，面向硬件；數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織方式，面向軟件和應(yīng)用數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織方式，面向軟件和應(yīng)用由算法和軟件實(shí)現(xiàn)兩者的映射。由算法和軟件實(shí)現(xiàn)兩者的映射。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)表示軟硬件界面軟硬件界面數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)表示是軟硬件的界面數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)表示是軟硬件的界面結(jié)論：結(jié)論：數(shù)據(jù)結(jié)構(gòu)的發(fā)展總是優(yōu)于機(jī)器的數(shù)數(shù)據(jù)結(jié)構(gòu)的發(fā)展總是優(yōu)于機(jī)器的數(shù)據(jù)表示據(jù)

48、表示系統(tǒng)結(jié)構(gòu)設(shè)計(jì)者的任務(wù)：系統(tǒng)結(jié)構(gòu)設(shè)計(jì)者的任務(wù)：從優(yōu)化設(shè)計(jì)的角從優(yōu)化設(shè)計(jì)的角度，確定軟硬件的分界面，哪些數(shù)據(jù)類型度，確定軟硬件的分界面，哪些數(shù)據(jù)類型用數(shù)據(jù)表示來實(shí)現(xiàn)，哪些數(shù)據(jù)類型用數(shù)據(jù)用數(shù)據(jù)表示來實(shí)現(xiàn)，哪些數(shù)據(jù)類型用數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，應(yīng)能對(duì)新型的數(shù)據(jù)結(jié)構(gòu)提供結(jié)構(gòu)來實(shí)現(xiàn)，應(yīng)能對(duì)新型的數(shù)據(jù)結(jié)構(gòu)提供更多更好的支持。更多更好的支持。l尋址方式分析尋址方式分析l程序定位技術(shù)程序定位技術(shù)l指令格式的優(yōu)化設(shè)計(jì)指令格式的優(yōu)化設(shè)計(jì) 尋址方式：尋址方式：是指令按什么方式尋找（訪問）到所是指令按什么方式尋找（訪問）到所 需的操作數(shù)或信息。需的操作數(shù)或信息。 指令所訪問的數(shù)據(jù)指令所訪問的數(shù)據(jù) 主存主存、寄存器寄存器、堆

49、棧堆棧 尋址能力尋址能力的要求的要求 多樣性、靈活性、尋址空間范圍大小、地址變多樣性、靈活性、尋址空間范圍大小、地址變換速度換速度 目目標(biāo)標(biāo)：以最短的位描述給定的尋址方式以最短的位描述給定的尋址方式2.3.1 尋址方式分析1.1.設(shè)置尋址方式的目標(biāo)設(shè)置尋址方式的目標(biāo)l尋址方式在指令中的指明方式尋址方式在指令中的指明方式占用操作碼位：占用操作碼位：DJS200DJS200系列指令系統(tǒng)中系列指令系統(tǒng)中8 8位操作位操作碼最高兩位：間接（碼最高兩位：間接（1111）和直接（）和直接（0101）地址碼設(shè)置尋址方式字段：地址碼設(shè)置尋址方式字段：VAX-11VAX-11指令中源和指令中源和目的各有目的各有

50、4 4位尋址方式位字段位尋址方式位字段主存主存直接、間接、變址、基址、相對(duì)尋址直接、間接、變址、基址、相對(duì)尋址 直接尋址直接尋址使指令字變長(zhǎng)使指令字變長(zhǎng) 間接尋址間接尋址使指令執(zhí)行速度變慢使指令執(zhí)行速度變慢 相對(duì)尋址相對(duì)尋址用于條件轉(zhuǎn)移指令中定位轉(zhuǎn)向后代碼的位用于條件轉(zhuǎn)移指令中定位轉(zhuǎn)向后代碼的位置置 變址尋址變址尋址支持向量、數(shù)組，實(shí)現(xiàn)循環(huán)支持向量、數(shù)組，實(shí)現(xiàn)循環(huán)，用寄存器做，用寄存器做變址器，地址碼部分不會(huì)很長(zhǎng)，訪問數(shù)據(jù)速度相當(dāng)于變址器，地址碼部分不會(huì)很長(zhǎng)，訪問數(shù)據(jù)速度相當(dāng)于一次訪問內(nèi)存的速度一次訪問內(nèi)存的速度 基址尋址基址尋址支持邏輯地址到物理地址的變換，支持邏輯地址到物理地址的變換，用于

51、程用于程序的動(dòng)態(tài)再定位；序的動(dòng)態(tài)再定位；2.2.尋址方式尋址方式寄存器寄存器直接、間接尋址直接、間接尋址以寄存器尋址方式為主的計(jì)算機(jī)稱為通用寄存器型以寄存器尋址方式為主的計(jì)算機(jī)稱為通用寄存器型計(jì)算機(jī)計(jì)算機(jī)優(yōu)點(diǎn)：優(yōu)點(diǎn)： - -指令字長(zhǎng)短指令字長(zhǎng)短 - -執(zhí)行速度快執(zhí)行速度快 - -支持向量、矩陣運(yùn)算支持向量、矩陣運(yùn)算缺點(diǎn)：缺點(diǎn)： - -不利于編譯程序的設(shè)計(jì)不利于編譯程序的設(shè)計(jì) - -不利于中斷和子程序的遞歸調(diào)用不利于中斷和子程序的遞歸調(diào)用 - -增加了硬件的復(fù)雜度增加了硬件的復(fù)雜度l堆棧堆棧堆棧尋址（只對(duì)棧頂元素進(jìn)行操作）堆棧尋址（只對(duì)棧頂元素進(jìn)行操作）特點(diǎn)：特點(diǎn)： 程序所占主存空間小，指令長(zhǎng)度

52、短程序所占主存空間小，指令長(zhǎng)度短 支持程序的嵌套和遞歸調(diào)用，支持中斷處理支持程序的嵌套和遞歸調(diào)用，支持中斷處理 支持高級(jí)語(yǔ)言編譯支持高級(jí)語(yǔ)言編譯l面向主存：主要訪問內(nèi)存，少量訪問寄存器面向主存：主要訪問內(nèi)存，少量訪問寄存器op m1 m2op m1 m2l面向通用寄存器：多數(shù)在寄存器，少量在內(nèi)存面向通用寄存器：多數(shù)在寄存器，少量在內(nèi)存op r m op r m 、op r1 r2op r1 r2l面向堆棧：主要在堆棧，可減輕編譯負(fù)擔(dān)面向堆棧：主要在堆棧，可減輕編譯負(fù)擔(dān)opop、 op m op m 、op rop r(2)(2)尋址方式分類尋址方式分類 大多數(shù)采用分類編址，有三類：大多數(shù)采用分

53、類編址，有三類： 存儲(chǔ)效率存儲(chǔ)效率：堆棧型堆棧型 通用寄存器型通用寄存器型 程序占用空間小程序占用空間小 利于減輕對(duì)高級(jí)語(yǔ)言編譯的負(fù)擔(dān)利于減輕對(duì)高級(jí)語(yǔ)言編譯的負(fù)擔(dān) 支持子程序嵌套、遞歸調(diào)用支持子程序嵌套、遞歸調(diào)用 省去大量地址碼字段，省空間省去大量地址碼字段，省空間 運(yùn)算速度運(yùn)算速度：堆棧型：堆棧型通用寄存器型通用寄存器型 堆棧訪存次數(shù)過多堆棧訪存次數(shù)過多 面向寄存器方式支持向量、矩陣面向寄存器方式支持向量、矩陣 一般在系統(tǒng)中三類尋址方式都應(yīng)當(dāng)采用一般在系統(tǒng)中三類尋址方式都應(yīng)當(dāng)采用3. 3. 比較：比較：l 尋址方式分析尋址方式分析多種尋址方式可以顯著減少程序的指令條數(shù)，多種尋址方式可以顯著減

54、少程序的指令條數(shù)，但這同時(shí)也可能增加實(shí)現(xiàn)的復(fù)雜度和使用這些但這同時(shí)也可能增加實(shí)現(xiàn)的復(fù)雜度和使用這些尋址方式的指令的執(zhí)行時(shí)鐘周期數(shù)尋址方式的指令的執(zhí)行時(shí)鐘周期數(shù)(CPI)(CPI)，故，故需對(duì)多種尋址方式進(jìn)行分析需對(duì)多種尋址方式進(jìn)行分析2.3.2 2.3.2 程序定位技術(shù)程序定位技術(shù)l邏輯地址：程序員編寫程序時(shí)使用的地址邏輯地址：程序員編寫程序時(shí)使用的地址l物理地址：程序在主存中的實(shí)際地址物理地址：程序在主存中的實(shí)際地址l一般來講，邏輯地址的空間大于物理地址的空一般來講，邏輯地址的空間大于物理地址的空間。因此，映射實(shí)際上是壓縮。間。因此，映射實(shí)際上是壓縮。l程序定位技術(shù)程序定位技術(shù)直接定位直接定

55、位：程序裝入前，編譯時(shí)就已確定了：程序裝入前，編譯時(shí)就已確定了程序中的指令和數(shù)據(jù)的主存物理地址程序中的指令和數(shù)據(jù)的主存物理地址靜態(tài)再定位靜態(tài)再定位：程序裝入時(shí)，由定位裝入程序：程序裝入時(shí)，由定位裝入程序把程序的邏輯地址變換成物理地址，而在程把程序的邏輯地址變換成物理地址，而在程序的執(zhí)行過程中，物理地址不再改變。序的執(zhí)行過程中，物理地址不再改變。動(dòng)態(tài)再定位動(dòng)態(tài)再定位：在執(zhí)行每條指令時(shí)才形成訪存：在執(zhí)行每條指令時(shí)才形成訪存物理地址的方法。通過基址尋址來實(shí)現(xiàn)物理地址的方法。通過基址尋址來實(shí)現(xiàn)基址寄存器內(nèi)存邏輯地址用戶程序優(yōu)點(diǎn)：優(yōu)點(diǎn)：l 提高了主存利用率提高了主存利用率l主存中的同一個(gè)程序段可為多個(gè)程

56、序共享主存中的同一個(gè)程序段可為多個(gè)程序共享l支持虛擬存儲(chǔ)器支持虛擬存儲(chǔ)器問題：?jiǎn)栴}：l需要硬件支持，虛擬存儲(chǔ)器的軟件管理算法也需要硬件支持，虛擬存儲(chǔ)器的軟件管理算法也較復(fù)雜較復(fù)雜2.3.3 指令格式的優(yōu)化設(shè)計(jì)l指令指令 = = 操作碼操作碼 + + 地址碼地址碼l指令格式的優(yōu)化：如何用最短的位數(shù)來表示指令指令格式的優(yōu)化：如何用最短的位數(shù)來表示指令的操作信息和地址信息，使程序中指令的平均字的操作信息和地址信息，使程序中指令的平均字長(zhǎng)最短長(zhǎng)最短l主要目標(biāo)主要目標(biāo)節(jié)省程序的存儲(chǔ)空間節(jié)省程序的存儲(chǔ)空間指令格式盡量規(guī)整，便于譯碼指令格式盡量規(guī)整，便于譯碼1. 操作碼的優(yōu)化設(shè)計(jì)l操作碼主要包括兩部分內(nèi)容操

57、作碼主要包括兩部分內(nèi)容操作種類：加減乘除、數(shù)據(jù)傳送、移位、轉(zhuǎn)移、操作種類：加減乘除、數(shù)據(jù)傳送、移位、轉(zhuǎn)移、I/OI/O操作數(shù)描述：操作數(shù)描述：l數(shù)據(jù)類型：定點(diǎn)、浮點(diǎn)、字符（串）、邏輯數(shù)、數(shù)據(jù)類型：定點(diǎn)、浮點(diǎn)、字符（串）、邏輯數(shù)、向量向量l進(jìn)位制：進(jìn)位制：2 2、1010、1616進(jìn)制進(jìn)制l數(shù)據(jù)字長(zhǎng)：字、半字、雙字、字節(jié)數(shù)據(jù)字長(zhǎng)：字、半字、雙字、字節(jié)l地址碼通常包括三部分內(nèi)容地址碼通常包括三部分內(nèi)容地址地址: : 直接、間接地址、立即數(shù)、寄存器編號(hào)、直接、間接地址、立即數(shù)、寄存器編號(hào)、變址寄存器編號(hào)變址寄存器編號(hào)地址的附加信息地址的附加信息: : 偏移量、塊長(zhǎng)度、間距偏移量、塊長(zhǎng)度、間距尋址方式

58、尋址方式: : 直接、間接、立即數(shù)、變址、相對(duì)寄直接、間接、立即數(shù)、變址、相對(duì)寄存器尋址存器尋址l操作碼的三種編碼方法操作碼的三種編碼方法固定長(zhǎng)度固定長(zhǎng)度: : 規(guī)整性好規(guī)整性好, , 解碼簡(jiǎn)單解碼簡(jiǎn)單, , 占用占用空間大空間大HuffmanHuffman編碼編碼: : 空間小空間小, , 規(guī)整性不好規(guī)整性不好, , 解碼復(fù)雜解碼復(fù)雜擴(kuò)展編碼擴(kuò)展編碼: : 折衷方案折衷方案l哈夫曼哈夫曼(Huffman)(Huffman)壓縮概念壓縮概念當(dāng)各種事件發(fā)生的概率不均等時(shí)當(dāng)各種事件發(fā)生的概率不均等時(shí), , 采用優(yōu)化技術(shù)采用優(yōu)化技術(shù)對(duì)發(fā)生對(duì)發(fā)生概率較高概率較高的事件用的事件用較短較短的位數(shù)的位數(shù)(

59、(時(shí)間時(shí)間) )來表來表示示( (處理處理), ), 而對(duì)出現(xiàn)概率較低的允許用較長(zhǎng)的位而對(duì)出現(xiàn)概率較低的允許用較長(zhǎng)的位數(shù)數(shù)( (時(shí)間時(shí)間) )來表示來表示( (處理處理), ), 以達(dá)到平均位數(shù)以達(dá)到平均位數(shù)最最少的少的目的目的用于代碼壓縮、程序壓縮、空間壓縮和時(shí)間壓縮用于代碼壓縮、程序壓縮、空間壓縮和時(shí)間壓縮l操作碼的優(yōu)化表示操作碼的優(yōu)化表示信息源熵信息源熵：信息源包含的平均信息量：信息源包含的平均信息量操作碼的優(yōu)化表示就是要使信息冗余量操作碼的優(yōu)化表示就是要使信息冗余量R最小最小niiippH12logH即為操作碼可以達(dá)到的最短平均碼長(zhǎng)即為操作碼可以達(dá)到的最短平均碼長(zhǎng)lHlHlR1信息冗余

60、量信息冗余量niiipll1實(shí)際編碼的操作碼碼長(zhǎng)為：實(shí)際編碼的操作碼碼長(zhǎng)為：例例1.1.七條指令，頻度如下七條指令，頻度如下 I1 I2 I3 I4 I5 I6 I7 I1 I2 I3 I4 I5 I6 I7 0.4 0.3 0.15 0.05 0.04 0.03 0.03 0.4 0.3 0.15 0.05 0.04 0.03 0.03信息源熵信息源熵 H=2.17=2.17信息冗余量信息冗余量R=(3-2.17)/3=0.28=28% （1 1）等長(zhǎng)編碼）等長(zhǎng)編碼 可用可用000000110110來分別表示來分別表示7 7種不同的指令種不同的指令 I1: 000I1: 000 I2: 00