[問題] 有人huffman 編/解碼的vhdl code..嗎

看板Programming作者iahon (嘻)時間19年前 (2006/07/09 15:56)推噓8(8推 0噓 0→)

留言8則, 6人參與討論串1/1

有人huffman 編/解碼的vhdl code..嗎 huffman壓縮的演算法大意如下：假設一篇文章共出現五種符號：a、b、c、d、e、f 其出現次數各為：a：23次、b：5次、c：8次、d：13次、e：103次、f：25次原本其各為8-bit的input，如：a=>00000000、f=>00000110 需將其使用huffman演算法壓縮，過程如下：每步驟將兩兩最小的兩個數相加，以此法建huffman tree，一：(b+c)、d、a、f、e 13 / \ b c d a f e (5) (8) (13) (23) (25) (103) 二：((b+c)+d)、a、f、e 26 / \ 13 d / \ (13) b c a f e (5) (8) (23) (25) (103) 三：((b+c)+d)、(a+f)、e 26 / \ 13 d 48 / \ (13) / \ b c a f e (5) (8) (23) (25) (103) 四：(((b+c)+d)+(a+f))、e 74 / \ 26 48 / \ / \ 13 d a f / \ (13)(23) (25) b c e (5) (8) (103) 五：((((b+c)+d)+(a+f))+e) 177 / \ 74 e / \ (103) 26 48 / \ / \ 13 d a f / \ (13)(23) (25) b c (5) (8) 以root為起點，向樹葉節點前進，每向左前進值填0，向右填1 所以壓縮後的編號為：a=>010、b=>0000、c=>0001、d=>001、e=>1、f=>011 與壓縮前的8-bit明顯少很多，此為huffman大致的用意。不需要做的太好，只要能達到要求既可，大致的設計如下：我們只設定這huffman程式能對64種符號解碼，所以之前先定死這64個符號給其特定的8-bit的address a~z => 00000000~00011001 A~Z => 00011010~00110011 0~9 => 00110100~00111101 逗號 => 00111110 空白鍵 => 00111111 第一階段：存值讀檔 ----> 將與其相對應的address給存在ROM裡面 ----> 將在ROM裡的address值一一output出來 ----> 第二階段：計算各符號出現次數設64個變數counter計算每個符號出現的次數counter初始值為0 ----> 若該符號出現則其相對應的counter <= counter +1 ----> 當檔案內的所有符號都讀完且計算完出現的counter後將64個變數output出來 ----> 第三階段：建huffman tree 寫一個if判斷式，將值大於0的counter拿出來做sort排序大小 ----> 將每次sort完最小的前兩個值相加後存至一變數，此變數再回去和剩下的counter再sort ----> 建好後的tree找出其相對應的編碼值 ----> 第四階段：將編碼後的值output出來將各符號編碼後的值output出來 ----> -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.137.92.27