【正文】 0xx 4種 1xx 0xx 16種 1xx 1xx 0xx 64種 41664平均碼長 =*4*3+*15*6+*55*9=； 例 4：指令系統(tǒng)共有 78種指令，前 10種使用頻率平均為 ，中間 18種使用頻率平均為 ，最后 50種使用頻率平均為 。 例 3：指令系統(tǒng)共有 74種指令，前 4種使用頻率平均為 ，中間 15種使用頻率平均為 ，最后 55種使用頻率平均為 。如何編碼？ 0000 ： 15種 1110 1111 0000 ： ： 15種 1111 1110 1111 1111 0000 ： ： ： 15種 1111 1111 1110 解：因頻率分布有三種，故碼長可有三種； 因每段指令數(shù)基本相同，故可采用 等長擴展 (4812位)， 保留特征碼的每段指令數(shù)相同 (151515)方法。 例如： 4812等長編碼， 151515每種長度指令數(shù)為15，共可編碼 45種 平均每條指令位數(shù) =(4＋ 8＋ 12) 15/45=8 ? 采用保留標(biāo)志位方法編碼較為復(fù)雜，但表示的指令總數(shù)多。 ?等長擴展 —— 每次擴展相同的位數(shù) 如 4812等長擴展方法（ 每次擴展 4位 ） ?不等長擴展 —— 每次擴展不同的位數(shù) 如 4610不等長擴展方法 (美國的 B1700) 擴展標(biāo)志： 保留 碼點標(biāo)志 —— 一組編碼作為擴展標(biāo)志 保留 標(biāo)志位 —— 一個標(biāo)志位作為擴展標(biāo)志 擴展編碼中選擇某些特征位用于擴展。 實現(xiàn)目標(biāo)：平均碼長接近全哈夫曼碼的碼長， 同時又保持了 定長碼的規(guī)整性。 ? (1)將事件的使用頻度值作為葉結(jié)點并按出現(xiàn)頻率次序排列； （排序） (2)將出現(xiàn)頻率最小的兩個事件合并（頻率相加）形成一個新結(jié)點； （合并） (3)在新組成的葉結(jié)點序列中繼續(xù)做 (2)，直至到根結(jié)點（頻率＝ 1，構(gòu)成一棵樹 )； (4)從樹根起沿左和右子樹分別分配其值為 1和 0，直至葉結(jié)點； （分配值 ） (5)事件的使用頻度值葉結(jié)點編碼為從根結(jié)點到葉結(jié)點的編碼組合。 – 動態(tài)再定位 ：在執(zhí)行每條指令時才形成訪存物理地址的方法。因此，映射實際上是壓縮。 堆棧訪存次數(shù)過多 支持子程序嵌套 、 遞歸調(diào)用 程序占用空間小 尋址方式與指令格式的優(yōu)化設(shè)計 ?尋址方式分析 ?程序定位技術(shù) ?指令格式的優(yōu)化設(shè)計 ? 尋址方式： 是指令按什么方式尋找（訪問）到所 需的操作數(shù)或信息。 ?有很豐富的堆棧操作類指令且功能很強，直接可對堆棧中的數(shù)據(jù)進行各種運算和處理 ?有力地支持高級語言程序的編譯；逆波蘭表達(dá)式 – 如： F=A*B+C/(DE) – 逆波蘭表達(dá)式： AB*CDE/+ ?堆棧指令程序 ?有力地支持子程序的嵌套和遞歸調(diào)用 qrsti+1 i+2 i+3irsti+1i i iq嵌套調(diào)用間接遞歸 直接遞歸i+1子程序現(xiàn)場信息返回地址r局部性參數(shù)i子程序現(xiàn)場信息返回地址q局部性參數(shù)......全局參數(shù)i+1子程序i子程序用堆棧實現(xiàn)子程序的嵌套和遞歸調(diào)用數(shù)據(jù)表示小結(jié)： －分類： 基本數(shù)據(jù)表示 高級數(shù)據(jù)表示 標(biāo)志符 描述符 自定義數(shù)據(jù)表示 向量數(shù)據(jù)表示 堆棧數(shù)據(jù)表示 引入數(shù)據(jù)表示的原則： （ 1）系統(tǒng)效率高 （ 2）通用性和利用率高 數(shù)據(jù)表示和數(shù)據(jù)結(jié)構(gòu)的關(guān)系 數(shù)據(jù)表示是數(shù)據(jù)結(jié)構(gòu)的一個子集，面向硬件； 數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織方式，面向軟件和應(yīng)用由算法和軟件實現(xiàn)兩者的映射。 堆棧機器： 具有堆棧數(shù)據(jù)表示的機器 ,以堆棧尋址方式指令為主。 高級語言機器：高級語言和機器語言合二為一，高級語言不用編譯，直接由機器硬件解釋執(zhí)行。 ?在向量數(shù)據(jù)表示的機器中，有豐富的向量運算指令，有大量的向量寄存器和并行、高速流水運算部件的支持，可以實現(xiàn)向量運算的高速執(zhí)行。 i++) ? c[i]=a[i]+b[i]。 向量數(shù)據(jù)表示 ? 向量表示 – 向量通常是指由標(biāo)量的一組有序集合表示的量，類似于一維數(shù)組 – 標(biāo)量通常只是一個整數(shù)或?qū)崝?shù) – 數(shù)組 A=(a0,a1,a2,…,a n1)可看成向量 A a0 a1 a11 ? 向量在主存儲器中的存放原則： 規(guī)律性、地址計算簡單、訪存沖突小 – 元素相鄰存放 – 元素等間距存放 ?向量計算機 處理向量數(shù)據(jù)的計算機 ? 舉例：計算 ci=ai+bi, I=10,11,…,1000 – 無向量數(shù)據(jù)表示 (C語言 )： ?for(i=10。 101 3101 4101 4101 4000 (a11)000 (a12)000 (a13)000 (a14)000 (a21)000 (a22)000 (a23)000 (a24)000 (a31)000 (a32)000 (a33)000 (a34)陣列描述符三元素向量3*4 二維陣列Aa11 a12 a13 a14a21 a22 a23 a24a31 a32 a33 a343*4 二維陣列用描述符描述二維陣列 ? 標(biāo)志符是和每一個數(shù)據(jù)相連的，合存在一個存儲單元中，描述單個數(shù)據(jù)的類型特征。 – 減小高級語言和機器語言的語義差距 – 通用機中不使用，專用機（支持動態(tài)數(shù)據(jù)類型如 LISP和 PROLOG）中使用 ? 目的：描述復(fù)雜和多維的結(jié)構(gòu)類型，進一步減少標(biāo)志符所占的存貯空間。 – 實現(xiàn)時間是否減少？ ?取出數(shù)據(jù)后轉(zhuǎn)換，必須推遲到運行時間進行 ?專門的指令用于標(biāo)志符初始化，增加了輔助開銷 ?指令執(zhí)行過程中，對每個標(biāo)志符進行逐個解釋，并判斷數(shù)據(jù)是否相容，因此單條指令的執(zhí)行速度降低，但宏觀執(zhí)行時間減少 – 宏觀時間 =設(shè)計時間 +編譯時間 +調(diào)試時間 通用性和利用率 這是一種理想的數(shù)據(jù)表示模式，通用性較好； 只用一種存儲器，利用率不高，采用指令和數(shù)據(jù)存儲器后，利用率不會降低。 ? （ 1）分別計算程序在處理機 A和 B上占用的存儲空間大小。 類型標(biāo)志 數(shù)據(jù) ? 優(yōu)點： – 簡化指令系統(tǒng)和程序設(shè)計 – 簡化了系統(tǒng)程序和編譯程序的設(shè)計 – 便于一致性校驗 – 能由硬件自動完成數(shù)據(jù)類型的變換 – 支持?jǐn)?shù)據(jù)庫系統(tǒng)的實現(xiàn)與數(shù)據(jù)類型無關(guān)的要求 – 為軟件調(diào)試和應(yīng)用軟件開發(fā)提供支持 ? 缺點： – 硬件設(shè)計的復(fù)雜度增加（數(shù)據(jù)類型轉(zhuǎn)換、一致性檢驗等） – 降低指令的執(zhí)行速度 – 必須用專門的指令完成標(biāo)志符的初始化 ? 引入可行性分析 – 存儲空間是否減少？ B A 數(shù)據(jù) 指令 總數(shù)少 總數(shù)多 通常有面積 B面積 A 采用標(biāo)志符后 數(shù)據(jù)字增長 不采用標(biāo)志符 采用標(biāo)志符后 指令字縮短 ? 例 設(shè)處理機 A的數(shù)據(jù)不帶標(biāo)志符，指令字長和數(shù)據(jù)字長都是 32位，設(shè)處理機 B的數(shù)據(jù)帶 3位標(biāo)志符，使數(shù)據(jù)字長增至 35位，但可使指令字長減少至 30位。格式如下： 類型標(biāo)志主要用于指明數(shù)據(jù)類型（如二進制整數(shù)、十進制整數(shù)等，也可用于指明機器內(nèi)部所用信息的各種類型）。 注意點： 新數(shù)據(jù)表示引入的可行性（原則）； 新數(shù)據(jù)表示的必要條件（指令系統(tǒng)和硬件器件）； 新數(shù)據(jù)表示的存取方法（如稀疏向量表示） 。 高級數(shù)據(jù)表示 ? 自定義數(shù)據(jù)表示（ Selfdefining） – 帶標(biāo)志符的數(shù)據(jù)表示 – 數(shù)據(jù)描述符 ? 向量數(shù)據(jù)表示 ? 堆棧數(shù)據(jù)表示 內(nèi)容： 堆棧、向量、數(shù)組（隊列）、記錄、自定義等。 （ 4） ROM或 PLA法 。被截尾數(shù)無論是 0是 1，恒置 1。被截尾數(shù)為 1進 1，運算中最大誤差小于一半。在整數(shù)運算中最大會接近于 1；誤差大都是負(fù)誤差。也稱為不舍入法。 應(yīng)用情況： ? 浮點數(shù)加法中的對階、規(guī)格化右移操作以及乘法中結(jié)果取單倍長度會把有效位移掉或截掉從而造成精度損失。 （ 4）浮點數(shù)尾數(shù)基值的選擇 rm ＝ 2，表數(shù)效率只有 50%，為了提高表數(shù)效率，許多計算機采用了隱藏位表示法，此時表數(shù)效率100%； 當(dāng)浮點數(shù)字長確定后， rm取 2，具有最大的表數(shù)范圍、表數(shù)效率和最高的表數(shù)精度。 rm ＝ 16，正規(guī)格化尾數(shù)的個數(shù) 15個，最大正數(shù)為 （ 1－ 16－ 1） 162，一個數(shù)量單位 =(1/16)162＝ 16 尾數(shù)基值 rm＝ 2與 rm＝ 16相比，顯然基值越大浮點數(shù)的表數(shù)效率高。 規(guī)格化浮點數(shù)的表數(shù)精度主要與尾數(shù)基值和尾數(shù)長度有關(guān)，一般認(rèn)為尾數(shù)最后 1位值的一半定義為表數(shù)精度 )2(21 ?? mpm rr )16(21 39。 （ 2） 浮點數(shù)的表數(shù)精度 表數(shù)精度也稱為表數(shù)誤差，浮點數(shù)存在表數(shù)精度的根本原因是由于浮點數(shù)的不連續(xù)性造成的。但 rm大時，在數(shù)軸上的分布較稀疏。 解：此浮點數(shù)共有 16位，格式如下： 1＝ 21 1: 0 1000001 , 10000000 1最小數(shù)： 0 1000001 , 10000001 規(guī)格化表示的最小尾數(shù) 15 14 9 8 0 數(shù)符 尾數(shù) 階碼 最小正尾數(shù)為： 可表示的正規(guī)格化浮點數(shù)的個數(shù)為 可表示的負(fù)階、正尾規(guī)格化數(shù)的個數(shù)為 40232 2162 ??41232 21622 ???可表示的正、負(fù)規(guī)格化浮點數(shù)的個數(shù)為 4241 222 ?? 從上面的分析可以看到，規(guī)格化浮點數(shù)的表數(shù)范圍主要與階碼的長度 q和 rm尾數(shù)基值有關(guān)，這時，能表示的絕對值最大的浮點數(shù)可近似為： 表數(shù)范圍 隨著 q和 rm的增大而擴大。 尾數(shù)用原碼表示，階碼采用移碼。 rm =2, 20(~) , 21(~) rm =16, 160(~) , 161(） 1/2 1 2 ? 【 例 1】 某計算機的浮點數(shù)采用 1位符號位、 6位階碼和 9位尾數(shù)，基數(shù)為 16，求規(guī)格化時它能表示數(shù)值的個數(shù)。如上例中 rm ＝ 2時，規(guī)格化后， 其尾數(shù)個數(shù)只為原來的 1/2；二是因為在同長度階碼時， rm不同，每次小數(shù)點移動位置不同，如上例中 rm ＝ 2時， 1個階碼值移動小數(shù)點 1bit，而 rm ＝ 16時，則 移動 4bits。例如在數(shù)軸1/22之間，當(dāng) rm ＝ 2時，有數(shù) 15個；而當(dāng) rm ＝ 16時，有數(shù) 8個。 可表示的最大正浮點數(shù)為 3 8 4 016)161()1( 31)12(1 ?????? ??? qmm rr而 rm=2時，其最大數(shù)是 15/2。一般使用 2， 8， 16三種。 可表示的最大正浮點數(shù)為 可表示規(guī)格化的最小正浮點數(shù)為 可表示的正階、正尾規(guī)格化數(shù)的個數(shù)為 2/1516/1582)21( 34 ???? ?2/122 01 ???322/122 24 ???16/15211 44 ???? ??mr最大尾數(shù)為 最小階碼為 最大階碼為 012 0 ??312 2 ??)3,2,1,0(42 2 ?階碼的個數(shù)為 最小尾數(shù)為 2/12 11 ?? ??mr尾數(shù)的個數(shù)為 162 4 ?在 尾數(shù)基值 rm ＝ 16（十六進制） q＝ 2, p=4(尾數(shù)bit3~bit0， 4位二進制組成一個十六進制數(shù)） ,做規(guī)格化表示（即此時 bit3~bit0 中必須有 1位為“ 1”，不許出現(xiàn)全“ 0”， bit3~bit0 為 0001～ 1111）的正階、正尾的數(shù)的范圍： 最小尾數(shù)為 16116 11 ?? ??mr1615161 1 ?? ?最大尾數(shù)為 最小階碼為 最大階碼為 012 0 ??31212 2 ????q422 2 ??q階碼的個數(shù)為 可表示的最小正浮點數(shù)為 16121612 001 ?????mr1512 ??p尾數(shù)的個數(shù)為 可表示的正階、正尾規(guī)格化數(shù)的個數(shù)為 60152 2 ??從上述例子，可得到下列兩個結(jié)論： （ 1）當(dāng)有相同階碼與尾數(shù)位數(shù)時， rm大，則表示數(shù)的范圍也大，表示數(shù)的個數(shù)增多。 現(xiàn)以階碼為 q=2，尾數(shù) p=4，正階、正尾數(shù)為例，比較 rm=2和 rm=16時