[發明專利]一種靜態哈夫曼并行全編碼實現方法

有效

• 申請號: 201710690814.6
• 申請日: 2017-08-14
• 公開（公告）號: CN107565974B
• 公開（公告）日: 2020-06-12
• 發明（設計）人: 萬國春;陳怡;夏子為;唐令怡
• 申請（專利權）人: 同濟大學
• 主分類號: H03M7/40
• 分類號: H03M7/40
• 代理公司: 上海科律專利代理事務所(特殊普通合伙) 31290
• 代理人: 葉鳳

1.一種靜態哈夫曼并行全編碼實現方法，其特征在于，

首先進行優化的并行全比較，算法為：一個時鐘周期內能得到所有權值的比較值，其中比較值為‘0’或者為‘1’，假如權值A比權值B大，那么A比B的比較值為‘1’，B比A的比較值根據A比B的比較值取反得到，即為‘0’，不需要多增加一個比較器就能得到B比A的比較值，這樣只使用一半的大于等于比較器就能夠得出所有的比較結果，根據此優化的并行全比較算法，不僅減少FPGA硬件資源的使用率，而且提高時鐘頻率；

然后半累加值，算法為：把每個權值與其他所有權值的比較值相加，得到一個相應的累加值，考慮到一旦需要比較的權值比較多，為了提高時序，每個權值的所有比較值分兩次相加，用兩個寄存器變量存放50％比較值的相加結果；

然后全累加值，算法為：下一個時鐘周期再把這兩個累加值相加得到一個完整的累加值，根據優化的并行全比較算法，每個權值的累加值各不相同，累加值的大小就代表該權值的大小；

然后根據最小的兩個累加值選出相應的兩個最小權值，把它們的權值相加得到一個新的權值，同時對這兩個最小權值進行編碼，兩者之中最小的那個權值編碼0，次最小權值編碼1；

接著繼續下一次的并行全比較、半累加值相加、全累加值相加、得到每個權值的排序結果、兩個最小權值相加為一個新的權值，如此循環下去，直到循環第N-1次，整個過程結束；

此外，在進行兩個最小權值相加為一個新的權值的時候，利用FPGA的并行處理功能，同時，對所有數據進行靜態Huffman的編碼，最后伴隨著循環結束，所有數據的靜態Huffman編碼也隨之結束；

最后采用流水線技術，流水輸出每個數據對應的Huffman編碼值。

2.如權利要求1所述的靜態哈夫曼并行全編碼實現方法，其特征在于，采用流水線的輸出方式，此流水線分為三級，第一級為讀取需要輸出編碼值的數據，第二級為取出該數據對應的靜態Huffman編碼值和碼長，第三級為輸出編碼，該流水線能夠保證在數據碼長不固定的情況下，不斷流輸出編碼值。