[發明專利]一種基于深度優先的分布式算術碼解碼方法

有效

• 申請號: 201710419222.0
• 申請日: 2017-06-06
• 公開（公告）號: CN107294656B
• 公開（公告）日: 2021-02-02
• 發明（設計）人: 方勇;崔華;王璇;關琦
• 申請（專利權）人: 長安大學
• 主分類號: H04L1/00
• 分類號: H04L1/00;H03M7/40
• 代理公司: 北京化育知識產權代理有限公司 11833
• 代理人: 秦麗

1.一種基于深度優先的分布式算術碼解碼方法，其特征在于，包括以下步驟：

1)數據結構和全局變量：實現深度優先算法，需要為DAC定義一個節點的數據結構，包括以下成員：

i:該節點的等級，即到該節點結束的路徑長度；

l,h和c:具有相同精度的三個整形變量；l和h分別是節點的上限和下限；c用來緩沖來自DAC比特流的比特量；

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

d：該節點結束處與邊信息之間路徑的漢明距離；

m：該節點結束處路徑的總體度量；

child0，child1和parent：這三個指針分別指向該節點的左分支節點、右分支節點和雙親節點；

DAC為分布式算術碼；

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

bst：指向葉子節點的最佳完整路徑；

spaths：其元素指向端節點的暫停路徑的指針數組；

nsp：在spaths中占用的元素數量；

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

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

2)深度優先解碼概要：最初，根節點根據u₀創建；然后解碼器重復調用一次單路徑搜索函數，compact_list函數，它從spaths中刪除不可能的暫停路徑的端節點，wakeup_path函數，從spaths選擇最佳暫停路徑來產生一條新的通路，直到最終滿足條件結束循環；最后，信源的最優估計通過追溯bst而獲得；

3)單路徑搜索：遍歷從一個等級為i的s節點開始；解碼器首先通過s.l，s.h和s.c計算u，然后通過u決定當前符號如果等于0或1，邊信息和在節點s的子結點結束的路徑之間的漢明距離將會是如果很明顯在子結點處結束路徑是有希望的，因此解碼器創建的s的子結點和重新指向s到它的的子節點；否則，解碼器調用prune_path函數來修剪在s節點結束的路徑并且終止通過；如果u落在重疊間隔內，這個問題將會變得復雜，所以branch函數被定義來描述在叉結點解碼器的行為；如果傳遞到達葉結點沒有被終止，它被稱為一個完整傳遞，這意味著在葉節點處結束的完整路徑必須是到現在為止的最佳全路徑，因此必須更新最小全路徑與邊信息之間的漢明距離d_min；

4)叉節點處的譯碼器行為：如果s是叉節點，除非這條通路被中止了，至少有一條s的子路徑是可行的，即如果s的左子路徑是不可行的，它的右子路徑必須可行，反之亦然；如果s的所有子路徑都是可行的，對應的子節點會更好，即為了更好的整體指標，子路徑將被挑選出來繼續這條通路，然而未被選擇的分支將被存儲到spaths數組中；

5)暫停路徑的節點壓縮列表：在每個完整路徑之后，解碼器用以bst結尾的完整路徑和邊信息之間漢明距離來更新d_min；然后利用新的d_min，解碼器通過去除指向無條件暫停路徑的末端節點的節點指針來壓縮該spaths數組：如果路徑和邊信息之間的漢明距離等于或大于d_min，則該路徑將被修剪并且其指向其末端節點的節點指針將從spaths數組中刪除；

6)在線內存釋放：壓縮列表和通過函數調用修剪路徑函數來部分釋放分配給無用路徑的內存，這通過向后迭代地刪除無條件路徑的末節點，直到末節點與其他路徑共享為止；

7)選擇最佳暫停路徑：調用壓縮列表函數后，spaths中的所有元素將指向可能的暫停路徑的結束節點；然后解碼器調用wave_path路徑函數，根據總體路徑度量從暫停列表中選擇最佳暫停路徑；一旦確定了最佳暫停路徑，將從其末端節點開始新的遍歷，同時指向其末端節點的節點指針將從spaths中移除；

8)終止條件：深度優先解碼器的終止條件取決于實際約束；如果解碼器不受復雜度約束，則終止條件可以是希望存儲的暫停路徑的數量：如果nsp＝0，即spaths是空的，則停止解碼，這意味著DAC樹已被完全搜索；如果解碼器受復雜度約束，則創建的節點的數量可以用作終止條件：如果創建的節點的數量超過閾值，則停止解碼。