[發明專利]一種基于分布式算術編碼的隱馬爾科夫相關信源編碼方法

有效

• 申請號: 201310130164.1
• 申請日: 2013-04-16
• 公開（公告）號: CN103326731B
• 公開（公告）日: 2017-03-29
• 發明（設計）人: 方勇;陳亮;劉亞允
• 申請（專利權）人: 西北農林科技大學
• 主分類號: H03M7/40
• 分類號: H03M7/40
• 代理公司: 北京方圓嘉禾知識產權代理有限公司11385
• 代理人: 董芙蓉

1.一種基于分布式算術編碼的隱馬爾科夫相關信源編碼方法，其特征在于，所述基于分布式算術編碼的隱馬爾科夫相關信源編碼方法包括以下步驟：

產生信源；

對隱馬爾科夫相關信源編碼；

利用前向算法進行的解碼。

2.如權利要求1所述的基于分布式算術編碼的隱馬爾科夫相關信源編碼方法，其特征在于，所述產生信源的步驟為：

讀取HMM文件，確定隱馬爾科夫模型；

應用隱馬爾科夫模型計算觀察值序列O；

根據偏差概率p，生成信源X；

將信源X與觀察值序列O進行異或運算，生成邊信息Y。

3.如權利要求1所述的基于分布式算術編碼的隱馬爾科夫相關信源編碼方法，其特征在于，所述對隱馬爾科夫相關信源編碼步驟為：

設p是二元信源X的偏差概率，即p＝P(x_t＝1)，在經典的算術編碼中，信源符號x_t被迭代的映射到[0，1)的子區間中，這個子區間的長度與(1-p)和p成比例，在分布式算術編碼中，分配的子區間會有重疊，即符號x_t＝0和x_t＝1分別對應于區間[0，(1-p)^γ)和[1-p^γ，1)，定義low和high表示編碼區間，range表示整個區間長度，half_range表示區間的一半，first_quarter表示整個區間的四分之一大小，third_quarter表示整個區間的四分之三大小。

4.如權利要求3所述的基于分布式算術編碼的隱馬爾科夫相關信源編碼方法，其特征在于，所述對隱馬爾科夫相關信源編碼還包括具體的區間放大操作

當high＜half_range時，這時子區間完全處在上半區，該區間的上下端點的最高有效位都是0，輸出相同的最高有效位0，然后將區間的上界和下界分別擴大2倍，即：low＝2*low，high＝2*high；

當low＞half_range時，這時子區間完全處在下半區，該區間的上下端點的最高有效位都是1，此時輸出相同的最高有效位1，然后將區間的上界和下界分別擴大，即：low＝2*(low-half_range)，high＝2*(high-half_range)；

當first_quarter≤low≤high≤third_quarter，如果還是按照上述的方法對low和high進行更新，由于子區間不斷縮小，所以子區間總是會處在first_quarter≤low≤high≤third_quarter這個區間里，而始終沒有相同的最高比特位可以輸出，所以在這種情況下就用新的方法進行子區間更新：low＝2*(low-first_quarter)，high＝2*(high-first_quarter)+1。

5.如權利要求1所述的基于分布式算術編碼的隱馬爾科夫相關信源編碼方法，其特征在于，所述利用前向算法進行的解碼步驟為：

定義一個結構體node，結構體包括low，high，用來表示概率區間，metric用來表示每個分支的重要程度即分支中各個結點度量的總和，alpha用來記錄局部概率α_t(i)，path用來保存解碼出的字符，另外定義數組scale[2]，其中scale[0]表示當前解碼符號為0或1時，邊信息對應位置符號為0的總概率，scale[0]＝alpha[0][0]+alpha[0][1]；scale[1]表示當前解碼符號為0或1時，邊信息對應位置符號為1的總概率，scale[1]＝alpha[1][0]+alpha[1][1]；

步驟一、根據原始信源X的長度N，分配解碼所需的結點空間，并初始化分布式算術碼的解碼緩沖區；

步驟二、在第i次解碼過程中(0＜i≤N)，讀取邊信息當前位置的字符s_i，

步驟三、使用前向算法，對每個結點，計算第i次解碼時，產生0分支和1分支的概率，當i＝1即在狀態處于初始時刻時，局部概率用公式α₁(i)＝π_ib_i(z₁)來計算并用alpha數組記錄，當i＞1時，局部概率用公式計算，公式中變量α_t-1(j)由結構體node內取得，每次計算后，得到本次迭代的alpha[0]，alpha[1]，scale[0]和scale[1]，scale[0]表示當前解碼符號為0或1時，邊信息對應位置符號為0的總概率，scale[0]＝alpha[0][0]+alpha[0][1]；scale[1]表示當前解碼符號為0或1時，邊信息對應位置符號為1的總概率，scale[1]＝alpha[1][0]+alpha[1][1]；

步驟四、計算第i次解碼的符號c_i，如果碼字沒有落在重疊區域內，則把當前的符號寫入node.path，并將解碼符號c_i和邊信息s_i進行異或運算，當前點的度量就用到達該點的所有路徑的概率之和來表示，也就是scale[0]或者scale[1]，如果邊信息和當前解碼符號相同，當前點的度量就用scale[0]表示，如果邊信息和當前解碼符號不同，就用scale[1]表示，并將結點中的局部alpha更新為更新整條分支的重要性，對于第k條分支，如果碼字落在重疊區域內，則產生兩個分支m和n，這時候node[m].metric表示的是與邊信息相同的分支的度量，即當邊信息為1時，node[m].metric表示1分支的度量，當邊信息為0時，node[m].metric表示0分支的度量，而node[n].metric則相反，表示與邊信息相反的分支的度量，對于m分支，其存儲的符號與邊信息相同，此時所以m分支的整體重要性就用node[m].metric+＝log(scale[0])表示，即m分支上當前所有點的scale值的乘積，而n分支的整體重要性就用node[n].metric+＝log(scale[1])表示，即n分支上當前所有點的scale值的乘積，并用新的概率alpha[0]更新原node點中node[m].alpha，用新的alpha[1]更新原node點中的node[n].alpha；

步驟五、由于解碼一次就會產生新的解碼區間，所以計算完分支的度量并更新了局部概率后，要更新概率區間和相關的信息；

步驟六、對所有分支按照metric值從大到小進行排序，如果分支數大于我們所設定的閾值M，則將多余的分支剪掉，如果i＜N，則返回步驟二；否則，解碼結束，將分支排序后的第一條分支中path保存的數據作為解碼輸出。