[發(fā)明專利]一種基于深度優(yōu)先的分布式算術(shù)碼解碼方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710419222.0
• 申請(qǐng)日: 2017-06-06
• 公開（公告）號(hào): CN107294656B
• 公開（公告）日: 2021-02-02
• 發(fā)明（設(shè)計(jì)）人: 方勇;崔華;王璇;關(guān)琦
• 申請(qǐng)（專利權(quán)）人: 長(zhǎng)安大學(xué)
• 主分類號(hào): H04L1/00
• 分類號(hào): H04L1/00;H03M7/40
• 代理公司: 北京化育知識(shí)產(chǎn)權(quán)代理有限公司 11833
• 代理人: 秦麗

本發(fā)明公開了一種基于深度優(yōu)先的分布式算術(shù)碼解碼方法，該方法包括以下步驟：數(shù)據(jù)結(jié)構(gòu)和全局變量；深度優(yōu)先解碼概要；單路徑搜索；叉節(jié)點(diǎn)處的譯碼器行為；壓縮端節(jié)點(diǎn)暫停路徑列表；在線內(nèi)存釋放；選擇最佳暫停路徑；終止條件。將深度優(yōu)先解碼與現(xiàn)有的廣度優(yōu)先解碼進(jìn)行比較，深度優(yōu)先解碼對(duì)短碼執(zhí)行得更好。

技術(shù)領(lǐng)域

本發(fā)明涉及一種深度優(yōu)先解碼方法，具體地說，涉及一種基于深度優(yōu)先的分布式算術(shù)碼解碼方法。

背景技術(shù)

分布式信源編碼以Slepian-Wolf理論和Wyner-Ziv理論為基礎(chǔ)，是編碼領(lǐng)域的熱點(diǎn)研究方向之一。分布式算術(shù)碼(Distributed Arithmetic Coding,DAC)是以分布式信源編碼的基本理論為基礎(chǔ)，通過引入算術(shù)碼作為編解碼核心產(chǎn)生的一種編碼方案，由于在處理小數(shù)據(jù)塊時(shí)展現(xiàn)出接近壓縮極限的性能，而得到廣泛的認(rèn)可和應(yīng)用。分布式算術(shù)碼由于存在疊區(qū)，隨著解碼的進(jìn)行將形成一棵不完全二叉解碼樹。傳統(tǒng)的分布式算術(shù)碼解碼方案是基于廣度優(yōu)先搜索實(shí)現(xiàn)的，在到達(dá)葉節(jié)點(diǎn)之前最小全路徑與邊信息之間的漢明距離是未知的，因此需要訪問大量的節(jié)點(diǎn)來實(shí)現(xiàn)解碼樹的全搜索。同時(shí)，為了防止溢出，解碼器需要為所有路徑的端節(jié)點(diǎn)分配空間，在解碼結(jié)束后才能釋放內(nèi)存，造成了資源的浪費(fèi)。本發(fā)明針對(duì)這一問題，提出了深度優(yōu)先解碼器，彌補(bǔ)了傳統(tǒng)解碼器中的不足。

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

本發(fā)明的目的在于提供一種基于深度優(yōu)先的分布式算術(shù)碼解碼方法。

其具體技術(shù)方案為：

一種基于深度優(yōu)先的分布式算術(shù)碼解碼方法，包括以下步驟：

1)數(shù)據(jù)結(jié)構(gòu)和全局變量：實(shí)現(xiàn)深度優(yōu)先算法，需要為DAC定義一個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，包括以下成員：

i:該節(jié)點(diǎn)的等級(jí)，即到該節(jié)點(diǎn)結(jié)束的路徑長(zhǎng)度。

l,h和c:具有相同精度的三個(gè)整形變量。l和h分別是節(jié)點(diǎn)的上限和下限。c用來緩沖來自DAC比特流的比特量。

p:將DAC比特流讀入c的下一位的位置。

d：該節(jié)點(diǎn)結(jié)束處與邊信息之間路徑的漢明距離。

m：該節(jié)點(diǎn)結(jié)束處路徑的總體度量。

child0，child1和parent：這三個(gè)指針分別指向該節(jié)點(diǎn)的左分支節(jié)點(diǎn)、右分支節(jié)點(diǎn)和雙親節(jié)點(diǎn)。

此外，需要以下全局變量：

bst：指向葉子節(jié)點(diǎn)的最佳完整路徑。

spaths：其元素指向端節(jié)點(diǎn)的暫停路徑的指針數(shù)組。

nsp：在spaths中占用的元素?cái)?shù)量。

d_min：最小完整路徑與邊信息之間的漢明距離。

如果一條路徑和邊信息之間的漢明距離等于或大于d_min，說明這個(gè)路徑是不可能的；否則我們說這條路是可能的。

2)深度優(yōu)先解碼概要：最初，根節(jié)點(diǎn)根據(jù)u₀創(chuàng)建。然后解碼器重復(fù)調(diào)用一次單路徑搜索函數(shù)，compact_list函數(shù)，它從spaths中刪除不可能的暫停路徑的端節(jié)點(diǎn)，wakeup_path函數(shù)，從spaths選擇最佳暫停路徑來產(chǎn)生一條新的通路，直到最終滿足條件結(jié)束循環(huán)。最后，信源的最優(yōu)估計(jì)通過追溯bst而獲得。