[發(fā)明專利]咬尾碼的最大似然譯碼算法

在審

• 申請?zhí)枺?/td>: 201210310583.9
• 申請日: 2012-08-28
• 公開（公告）號: CN103634015A
• 公開（公告）日: 2014-03-12
• 發(fā)明（設(shè)計）人: 王曉濤;錢驊;徐景;楊旸
• 申請（專利權(quán)）人: 上海無線通信研究中心
• 主分類號: H03M13/23
• 分類號: H03M13/23
• 代理公司: 上海光華專利事務(wù)所 31219
• 代理人: 李儀萍

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

本發(fā)明無線通信的信道譯碼領(lǐng)域，涉及一種譯碼算法，特別是涉及一種咬尾碼的最大似然譯碼算法。

背景技術(shù)

卷積碼根據(jù)其編碼器初始化方式的不同，可分為傳統(tǒng)卷積碼和咬尾卷積碼(Tail-Biting?Convolutional?Codes,TBCC)。有些分組碼可以用咬尾格形圖來表示，所以稱這樣的分組碼和咬尾卷積碼為咬尾碼。傳統(tǒng)卷積碼的編碼器采用已知比特（一般是全0比特）初始化，并在編碼結(jié)束的時候使其結(jié)束于某個已知狀態(tài)；TBCC的編碼器采用信息序列的最后v'位來初始化，其中v'≤v,v是編碼器中的寄存器長度。根據(jù)v'和v的關(guān)系，TBCC可分為全咬尾卷積碼(v'=v)和部分咬尾卷積碼(v'<v)。

采用咬尾方式編碼可以消除用已知比特初始化編碼器所導致的碼率損失，因此，咬尾卷積碼被廣泛應用在增強型數(shù)據(jù)GSM環(huán)境（enhanced?data?GSM?environment，EDGE），微波存取全球互通（worldwide?interoperability?for?microwave?access，WiMAX）和3GPP長期演進（long?term?evolution，LTE）中作為控制信道和廣播信道的編碼方式。

對咬尾碼來說，目前已有的最大似然（maximum?likelihood，ML）譯碼算法有：兩階段最大似然譯碼算法（two-phase?ML?decoder，TP-ML?decoder）和雙向樹搜索算法（bidirectional?efficient?algorithm?for?searching?code?trees，BEAST），這些算法在實際應用中存在諸多問題。對于TP-ML譯碼器來說，它的兩個階段采用不同的搜索方式使得對于實現(xiàn)來說過于復雜，且在第二階段的搜索過程中所采用的啟發(fā)式搜索需要消耗大量存儲器。BEAST算法在譯碼之前要先構(gòu)造咬尾碼的傳統(tǒng)格形圖，然后才能譯碼；且BEAST算法在咬尾格形圖上的譯碼效率過低，幾乎和理論最大似然譯碼算法復雜度相當，這些缺點導致現(xiàn)有最大似然譯碼算法無法在實際中使用。

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

鑒于以上所述現(xiàn)有技術(shù)的缺點，本發(fā)明的目的在于提供一種咬尾碼的最大似然譯碼算法，用于解決現(xiàn)有技術(shù)中咬尾碼譯碼算法計算復雜度高、存儲器消耗大、以及算法不收斂的問題。

為實現(xiàn)上述目的及其他相關(guān)目的，本發(fā)明提供一種咬尾碼的最大似然譯碼算法，所述咬尾碼的最大似然譯碼算法包括：

S1，初始化幸存狀態(tài)集合、起始于幸存狀態(tài)集合中任一幸存狀態(tài)的路徑累計度量值、結(jié)束于各個幸存狀態(tài)的咬尾路徑度量值的下界值、以及最優(yōu)咬尾路徑度量值；

S2，進行i次迭代，得到第i+1次迭代的幸存狀態(tài)集合，為第i+1次迭代做準備；其中，i≥1；

S3，停止譯碼并輸出和最優(yōu)最大似然咬尾路徑相關(guān)的碼字。

優(yōu)選地，于所述步驟S1還包括：將幸存狀態(tài)集合初始化為幸存起始狀態(tài)集合，將起始于幸存狀態(tài)集合中任一幸存狀態(tài)的路徑累積度量值初始化為0；將結(jié)束于各個幸存狀態(tài)的咬尾路徑度量值的下界值初始化為0，將最優(yōu)咬尾路徑度量值初始化為無窮大。

優(yōu)選地，于所述步驟S2還包括：

S21，以幸存狀態(tài)集合中的狀態(tài)為起始點，執(zhí)行以最優(yōu)咬尾路徑凈增量為界的維特比譯碼搜索；

S22，若發(fā)現(xiàn)第i次迭代中得到的最大似然咬尾路徑比前i-1次迭代中得到的最優(yōu)咬尾路徑度量值小，則更新最優(yōu)最大似然咬尾路徑及最優(yōu)咬尾路徑度量值；

S23，對幸存狀態(tài)集合中的所有狀態(tài)，更新結(jié)束于各個幸存狀態(tài)的咬尾路徑度量值的下界值為前i次迭代中獲得的最大的一個值，從幸存狀態(tài)集合中刪除結(jié)束于各個幸存狀態(tài)的咬尾路徑度量值的下界不小于最優(yōu)咬尾路徑度量值的狀態(tài)，得到第i+1次迭代的幸存狀態(tài)集合；

S24，若發(fā)現(xiàn)第i+1次迭代的幸存狀態(tài)集合為空集時，執(zhí)行步驟S3；若發(fā)現(xiàn)第i次迭代的幸存狀態(tài)集合與第i+1次迭代的幸存狀態(tài)集合相同，則從第i次迭代中得到的最大似然路徑的起始狀態(tài)開始執(zhí)行有界維特比譯碼搜索，得到咬尾路徑，若該咬尾路徑凈增量小于最優(yōu)咬尾路徑度量值，則更新最優(yōu)最大似然咬尾路徑及最優(yōu)咬尾路徑度量值，并從第i+1次迭代的幸存狀態(tài)集合中刪除起始狀態(tài)；

S25，為第i+1次迭代做初始化，將結(jié)束于幸存狀態(tài)集合中任一幸存狀態(tài)的路徑的累積度量值賦值給下一次迭代開始時從所述幸存狀態(tài)集合中任一幸存狀態(tài)起始的路徑的初始路徑度量值，返回步驟S2，執(zhí)行第i+1次迭代。