第二章指令系統(tǒng)-展示頁
2025-08-10 13:02本頁面
【正文】 知識，在 n種可能發(fā)生的事件集合中，報告第 i種事件發(fā)生的消息中包含的信息量為： iaiai PPI lo g)1(lo g ??? 其中 Pi是第 i種事件發(fā)生的先驗概率 ， a是編碼基值 。 ? 每個結點都有兩個分支，分別用一位代碼“ 0” 和“ 1”表示。 ? 在新結點集合中選取兩個概率最小的結點進行合并，如此繼續(xù)進行下去，直至全部結點合并完畢。 指令 I1 概率 I2 I3 I4 I5 I6 I7 Huffman樹生成步驟： ? 把所有指令按照操作碼在程序中出現的概率，自左向右從排列好。 上面所說的 頻度值 就是各事件實際出現次數的百分比，它是理論出現 概率 的近似值。 讀出從根結點到任一片樹葉的路徑上依次出現的代碼位就排成了這個事件 （ 即指令 ） 的完整編碼 。 頻度合并： 將全部 n個事件 （ 在此即為 n條指令 ） 的頻度值排序 ， 選取其中最小的 2個頻度合并 ， 然后將剩下的 n1個頻度再次排序 ， 再合并最小的 2個頻度 ， 如此重復 ， 直至剩下 1個頻度為止 。 指令 I1 概率 I2 I3 I4 I5 I6 I7 解： 由于 N=7 因此，指令操作碼固定長度為 [lbN]=[lb7]=3 指令序號 概率 編碼 操作碼長度 I1 000 3位 I2 001 3位 I3 010 3位 I4 011 3位 I5 100 3位 I6 101 3位 I7 110 3位 編碼結果： 二、 Huffman編碼法（ 最小概率合并法 ） Huffman壓縮概念 （ 最佳編碼定理 ） ： 當用 n個長度不等的代碼分別代表 n種發(fā)生概率不等的事件時 ， 按照短代碼給高概率事件 、 把長代碼給低概率事件的原則分配 ， 可使平均碼長達到最低 。 2) 信息冗余。 若指令系統(tǒng)共有 N種不同功能的指令，則指令系統(tǒng)中的所有指令的操作碼長度固定為 [lbN]位。 3) 擴展編碼法。 操作碼的優(yōu)化表示 操作碼的表示方法： 1) 固定長度操作碼。 指令格式的優(yōu)化設計目標： 1) 使程序中指令的平均字長最短，節(jié)省程序的存儲空間。 2) 地址附加信息。 2) 所用操作數數據類型。第二章 指令系統(tǒng) 指令格式的優(yōu)化設計 指令格式的優(yōu)化是指如何用最短的二進制位數表示指令的操作碼信息和地址碼信息，使指令的平均字長最短，同時便于譯碼。 指令的組成 操作碼 地址碼 1) 指令的操作種類。 1) 操作數地址。 3) 尋址方式。 2) 指令格式要規(guī)整，減少硬件譯碼的復雜程度。 2) Huffman編碼法。 一、 固定長度操作碼 采用等長操作碼。 特點： 1) 長度規(guī)整，有利于硬件設計，減少指令譯碼時間。 例： 假設一臺模型計算機共有 7種不同的操作碼，已知各種操作碼在程序中出現的概率如下表，利用固定長度編碼法進行操作碼編碼。 Huffman編碼方法 這種編碼方法由兩個過程組成 。 記錄所有的合并關系 ， 形成一棵二叉樹 ── Huffman樹 ， 所有原始頻度值充當樹葉 ， 而最后剩下的總頻度 1為樹根； 碼元分配： 從樹根開始 ， 對每個中間結點的左右 2個分支邊各賦予一位代碼 “ 0”和 “ 1”（ “ 0”在哪一側不限 ） 。由于頻度高的事件較晚被合并 ， 它的編碼位數也就較少 ， 符合 Huffman壓縮原則 。 例： 假設一臺模型計算機共有 7種不同的操作碼，已知各種操作碼在程序中出現的概率如下表，利用 Huffman編碼法進行操作碼編碼。 ? 選取兩個概率最小的結點合并成一個概率值是二者之和的新結點，并把這個新結點與其它還沒有合并的結點一起形成新結點集合。 ? 最后得到的根結點的概率值為 1。 注意： 對于同一個頻度分布，應用哈夫曼算法可能生成不同的哈夫曼樹，因此，得到的哈夫曼編碼并不唯一，但平均碼長唯一。 信息量的單位是表示位數 （ 最少所需位數 ） 。 熵 （ entropy） ── 平均信息量： 一個消息源對 n種事件發(fā)布的消息的信息量平均值 ， 記為： ? ??????????niiainiii PPIPH11)(l o g)(平均碼長： 各事件編碼長度的數學期望。 %100??? L HLR 從減少存儲與傳輸量的角度看 ， 編碼方法的平均碼長越短越好 。 如果短于熵就一定會丟失有用信息 （ 即混淆不同指令 ） ， 這是不允許的 。已知各種操作碼在程序中出現的概率如下表，計算采用 Huffman編碼法的操作碼平均長度，并計算固定長操作碼和 Huffman操作碼的信息冗余量。 Huffman操作碼的主要缺點： 1) 操作碼長度很不規(guī)整，硬件譯碼困難 2) 與地址碼共同組成固定長的指令比較困難 % ???R擴展編碼方法（等長擴展法） 由固定長操作碼與 Huffman編碼法相結合形成。等長擴展法如 4812法，每次加長 4位。 ? 碼點表示法： 例如 15/15/15法， 8/64/512法 – 15/15/15法，每一種碼長都有 4位可編碼位（前頭可以有相同的擴展標識前綴），可產生 16個碼點（即編碼組合），但是至多只能使用其中 15個來表示事件，留下 1個或多個碼點組合作為更長代碼的擴展標識前綴。這就是“非前綴原則”。各段剩下的可編碼位一起編碼，所產生的碼點用來對應被編碼事件。
范文總結相關推薦
鄂ICP備17016276號-1