[發(fā)明專(zhuān)利]基于霍夫曼編碼的編碼方法、譯碼方法及應(yīng)用

在審

• 申請(qǐng)?zhí)枺?/td>: 201810998614.1
• 申請(qǐng)日: 2018-08-29
• 公開(kāi)（公告）號(hào): CN109104199A
• 公開(kāi)（公告）日: 2018-12-28
• 發(fā)明（設(shè)計(jì)）人: 江正忠
• 申請(qǐng)（專(zhuān)利權(quán)）人: 重慶物奇科技有限公司;上海物麒科技有限公司
• 主分類(lèi)號(hào): H03M7/40
• 分類(lèi)號(hào): H03M7/40
• 代理公司: 重慶強(qiáng)大凱創(chuàng)專(zhuān)利代理事務(wù)所(普通合伙) 50217
• 代理人: 隋金艷

本發(fā)明公開(kāi)了一種基于霍夫曼編碼的編碼方法，包括了編碼步驟，對(duì)輸入序列以第一指定長(zhǎng)度為編碼單元進(jìn)行霍夫曼編碼；以及補(bǔ)長(zhǎng)步驟，用于從霍夫曼編碼模塊獲取由編碼值組成的霍夫曼編碼序列，并以第二指定長(zhǎng)度作為邊界，如果最后一個(gè)編碼值輸入無(wú)法被放入到W長(zhǎng)度的獨(dú)立序列以?xún)?nèi)，就將該編碼值放到下一個(gè)第二指定長(zhǎng)度的獨(dú)立序列內(nèi)，而在當(dāng)前獨(dú)立序列內(nèi)剩余的長(zhǎng)度全部補(bǔ)入不影響譯碼結(jié)果的占位碼，最終輸出由多個(gè)長(zhǎng)度為第二指定長(zhǎng)度的獨(dú)立序列順次連接而成的編碼序列。本發(fā)明還公開(kāi)了相應(yīng)的基于霍夫曼編碼的編碼裝置，以及一種壓縮解壓縮方法和卷積神經(jīng)網(wǎng)絡(luò)中的應(yīng)有，具有不必對(duì)邊界進(jìn)行搜尋，大大提高了譯碼效率的效果。

背景技術(shù)

霍夫曼(Huffman)編碼是一種無(wú)損的熵編碼，廣泛應(yīng)用于數(shù)字音視頻等信息壓縮。

霍夫曼編碼是對(duì)輸入序列按概率進(jìn)行分類(lèi)，較高概率用較少的bit來(lái)編碼，較低概率則用較多bit編碼。在譯碼時(shí)，需要一個(gè)編碼映射表格，將每個(gè)編碼值在表格中進(jìn)行搜索，以還原成原來(lái)的數(shù)據(jù)序列。這樣一種編碼方式在數(shù)據(jù)序列中有較多冗余時(shí)，能獲得較好的壓縮比。

以二值霍夫曼編碼為例，假定存儲(chǔ)序列存在較多相同值，我們可以利用霍夫曼編碼原則對(duì)將數(shù)據(jù)分為兩類(lèi)：一類(lèi)是常數(shù)值MFV(most frequently value)，一般是對(duì)存儲(chǔ)矩陣進(jìn)行搜索，找到最經(jīng)常出現(xiàn)的值，這類(lèi)值會(huì)映射為編碼值“0”，僅僅占用1bit；另一類(lèi)是非MFV值，該類(lèi)值會(huì)映射在其加一個(gè)前導(dǎo)的“1”，作為其分類(lèi)標(biāo)志。當(dāng)然也有使用相反編碼邏輯的情況，這只是使用習(xí)慣的區(qū)別。

將輸入序列每16bit為一編碼單位為例子，假定0x1010是最常出現(xiàn)的值，它映射為bit0，那么下面的序列映射關(guān)系是：

0x1010----1’b0

0x4567----{1’h1,16’h4567}

0x1010----1’b0

0x1234----{1’h1,16’h1234}

0x1010----1’b0

0x1010----1’b0

霍夫曼譯碼的實(shí)現(xiàn)則與此過(guò)程相反，對(duì)于每一個(gè)長(zhǎng)度為W的輸入序列，需要從第一個(gè)bit進(jìn)行搜索，將其與編碼映射表進(jìn)行匹配，獲得第一個(gè)輸出；同時(shí)更新輸入序列W，將已經(jīng)譯碼完的bit丟棄，進(jìn)行新的字搜索。

由此可見(jiàn)，由于是一種變長(zhǎng)度編碼，霍夫曼編碼的譯碼通常情況下是串行的，前后的譯碼值存在依賴(lài)，下一個(gè)字的搜索起點(diǎn)取決于上一個(gè)字的譯碼結(jié)果，因此并不適合并行譯碼，進(jìn)而不利于以很高的吞吐率進(jìn)行譯碼,也不利于硬件高效率實(shí)現(xiàn)。

現(xiàn)有技術(shù)中，提出了利用霍夫曼邊界碼將原始的霍夫曼編碼分割為多個(gè)互不依賴(lài)的數(shù)據(jù)序列，譯碼時(shí)通過(guò)搜尋該邊界碼來(lái)找到每一個(gè)數(shù)據(jù)序列并輸入到不同的譯碼器中，從而可以實(shí)現(xiàn)各個(gè)數(shù)據(jù)序列并行的進(jìn)行譯碼。

然而，高速傳輸和處理系統(tǒng)都是流水線實(shí)現(xiàn)，霍夫曼邊界碼速度再快，也很難跟上處理器或主設(shè)備(master)的速度。另外，當(dāng)一個(gè)霍夫曼譯碼器的譯碼層時(shí)機(jī)(decode layertiming)不滿(mǎn)足系統(tǒng)帶寬需求時(shí)，通常會(huì)引入流水線(pipeline)的設(shè)計(jì)，而由此引入的延遲(latency)會(huì)導(dǎo)致地址跳轉(zhuǎn)時(shí)流水線的清空及地址“回退”，而如果沒(méi)有可預(yù)測(cè)的邊界，地址回退或重計(jì)算幾乎不可能，現(xiàn)有技術(shù)中即便是使用了編譯碼，但由于霍夫曼編碼是變長(zhǎng)度的，所以每個(gè)互不依賴(lài)的數(shù)據(jù)序列的長(zhǎng)度也是不確定的，即便使用了邊界碼，也是通過(guò)搜選來(lái)進(jìn)行邊界確定，其邊界仍然是不可預(yù)測(cè)的。

發(fā)明內(nèi)容

本發(fā)明意在提供一種編碼方法，使得用于并行譯碼的霍夫曼編碼序列的邊界可以預(yù)測(cè)，進(jìn)而可在硬件中實(shí)現(xiàn)快速高效的并行譯碼。

一種基于霍夫曼編碼的編碼方法，包括以下內(nèi)容：

編碼步驟：對(duì)輸入序列以第一指定長(zhǎng)度為編碼單元進(jìn)行霍夫曼編碼；