[發(fā)明專利]基于疊加度的系統(tǒng)LT碼編譯方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310216256.1
• 申請(qǐng)日: 2013-06-03
• 公開（公告）號(hào): CN103346858A
• 公開（公告）日: 2013-10-09
• 發(fā)明（設(shè)計(jì)）人: 張欽宇;焦健;顧術(shù)實(shí);李云鵬;吳紹華
• 申請(qǐng)（專利權(quán)）人: 哈爾濱工業(yè)大學(xué)深圳研究生院
• 主分類號(hào): H04L1/00
• 分類號(hào): H04L1/00
• 代理公司: 深圳市科吉華烽知識(shí)產(chǎn)權(quán)事務(wù)所(普通合伙) 44248
• 代理人: 肖偉;鄧揚(yáng)

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

本發(fā)明涉及一種系統(tǒng)LT碼編譯方法，尤其涉及一種基于疊加度的有限長(zhǎng)系統(tǒng)LT碼的編碼、譯碼方法。

背景技術(shù)

近年來，能夠以較低的編譯碼復(fù)雜度逼近刪除信道容限的噴泉碼，受到了相關(guān)研究者的極大關(guān)注。噴泉碼的無(wú)碼率特性，使得發(fā)送端能夠?qū)個(gè)信息分組產(chǎn)生無(wú)限的編碼分組，向接收端噴射；而接收端只需要成功接收到略多于k個(gè)編碼包，即可通過一種簡(jiǎn)單的消息傳遞(BeliefPropagation，BP)迭代譯碼算法恢復(fù)出原始信息。噴泉碼將傳統(tǒng)的信道糾錯(cuò)編碼拓展到了數(shù)據(jù)分組，提供了一種無(wú)需反饋鏈路的高效前向糾刪傳輸機(jī)制。尤其是碼長(zhǎng)10³數(shù)量級(jí)的短碼長(zhǎng)LT碼，適用于節(jié)點(diǎn)運(yùn)算能力受限的容遲網(wǎng)絡(luò)場(chǎng)景的信息分組糾刪(如物聯(lián)網(wǎng)、深空探測(cè)等)。在實(shí)際應(yīng)用中的編碼往往需要采用系統(tǒng)碼結(jié)構(gòu)，即由原始信息與冗余校驗(yàn)信息構(gòu)成傳輸碼字。在信道沒有發(fā)生刪除或刪除概率極低時(shí)，接收端可以直接恢復(fù)原始信息以避免譯碼開銷，能極大的降低處理時(shí)延。

但是，Luby設(shè)計(jì)的LT碼和Shokrollahi的Raptor碼采用的隨機(jī)編碼方式使其原有的編碼方案不易獲得系統(tǒng)碼字結(jié)構(gòu)。因此，Shokrollahi設(shè)計(jì)了相關(guān)專利技術(shù)，通過對(duì)級(jí)聯(lián)的WRSD分布(弱魯棒孤波分布)LT碼的生成矩陣進(jìn)行逆變換，獲得中間節(jié)點(diǎn)進(jìn)而構(gòu)造系統(tǒng)Raptor碼，但是生成矩陣的逆變換操作需要O(k²)的復(fù)雜度，在信息節(jié)點(diǎn)數(shù)k較大時(shí)編碼復(fù)雜度超出了硬件受限的通信節(jié)點(diǎn)能力。3GPP利用偽隨機(jī)序列構(gòu)造輸入節(jié)點(diǎn)與中間節(jié)點(diǎn)的生成矩陣，提出了一種冗余譯碼開銷極小的Raptor碼系統(tǒng)編碼方案，但接收端需要使用高斯消去(Gaussian?Elimination，GE)譯碼算法，此時(shí)譯碼端需要O(k²)的復(fù)雜度。以上兩種基于Raptor碼改進(jìn)的系統(tǒng)編碼方案復(fù)雜度較大，且需要預(yù)編碼結(jié)構(gòu)。而現(xiàn)有一種對(duì)中間節(jié)點(diǎn)進(jìn)行交織的準(zhǔn)系統(tǒng)摻雜LT碼(Quasi-Systematic?Doped?LT?Codes，QS-DLT)，省略了Raptor碼的預(yù)編碼結(jié)構(gòu)，并獲得了BP譯碼的漸近性能(即碼長(zhǎng)趨近于無(wú)窮時(shí))，但是其中間節(jié)點(diǎn)的交織需要較大的緩存開銷。

另一方面，現(xiàn)有的度分布往往是基于漸近最優(yōu)設(shè)計(jì)的，對(duì)于有限長(zhǎng)度的信息分組往往難以獲得理想的復(fù)雜度與譯碼性能的折衷。現(xiàn)有技術(shù)中可通過引入修正的期望可譯集，對(duì)實(shí)用碼長(zhǎng)LT碼的度分布進(jìn)行離散密度進(jìn)化，但優(yōu)化的度分布只能保證恢復(fù)出盡量多的原始數(shù)據(jù)包而不是恢復(fù)原始文件。現(xiàn)有技術(shù)中還可利用多狀態(tài)馬爾科夫鏈推導(dǎo)了極短碼長(zhǎng)條件下(＜100)LT碼的度分布最優(yōu)解，但是該優(yōu)化算法的高復(fù)雜度使其無(wú)法對(duì)實(shí)用長(zhǎng)度的最優(yōu)度分布求解。現(xiàn)有技術(shù)中還提出了一種度分布優(yōu)化算法，該算法給出了中短碼長(zhǎng)的次優(yōu)LT碼度分布。上述對(duì)于噴泉碼的度分布優(yōu)化設(shè)計(jì)主要是針對(duì)RSD進(jìn)行優(yōu)化，無(wú)法保證編譯碼過程的線性復(fù)雜度。更進(jìn)一步的，采用RSD的LT碼在譯碼端需要接收到絕大多數(shù)碼字才能進(jìn)入BP譯碼的瀑布區(qū)，即接收端需要額外的等待時(shí)延才能開始恢復(fù)傳輸過程中被刪除的碼字。因此，利用已接收的部分編碼包盡快恢復(fù)原始信息成為近年的熱點(diǎn)研究問題。但是上述研究都是面向非系統(tǒng)結(jié)構(gòu)的LT碼。

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

為了克服上述現(xiàn)有技術(shù)的不足，本發(fā)明提供一種基于疊加度的系統(tǒng)LT碼編譯方法。

相較于現(xiàn)有技術(shù)，本發(fā)明針對(duì)實(shí)際應(yīng)用的需求，設(shè)計(jì)了一種短碼長(zhǎng)的系統(tǒng)LT碼編碼方案。與現(xiàn)有方案不同，為降低編碼端的預(yù)編碼計(jì)算復(fù)雜度或交織帶來緩存開銷，針對(duì)系統(tǒng)編碼的中間節(jié)點(diǎn)設(shè)計(jì)并優(yōu)化了一種SPDD度分布，通過在WRSD度分布的基礎(chǔ)上疊加了一個(gè)DD摻雜度分量，有效的保證對(duì)信息節(jié)點(diǎn)的全選覆蓋概率，同時(shí)具有保證線性的編譯碼復(fù)雜度和中間節(jié)點(diǎn)的部分恢復(fù)特性，并理論證明了SPDD的漸近性能。然后基于實(shí)用化參數(shù)的考慮，在有限碼長(zhǎng)的條件下根據(jù)碼長(zhǎng)、信道刪除概率以及譯碼冗余開銷等參數(shù)優(yōu)化了SPDD度分布的疊加比例。仿真驗(yàn)證了本發(fā)明提出的系統(tǒng)LT碼在有限碼長(zhǎng)下相對(duì)于現(xiàn)有的系統(tǒng)噴泉碼方案，具有更低的譯碼失敗概率。未來將從理論分析角度深入研究SPDD中疊加比例p與其他參數(shù)的定量關(guān)系，以拓展系統(tǒng)LT碼面對(duì)不同信道條件的適用性，并進(jìn)一步構(gòu)造通用的系統(tǒng)LT碼。

附圖說明

圖1是本發(fā)明的基于疊加度的系統(tǒng)LT碼編譯方法的編碼方案示意圖。

圖2是本發(fā)明中β值在短碼長(zhǎng)條件下受δ影響的最佳取值示意圖。

圖3是本發(fā)明中不同疊加比例p的SPDD度分布示意圖。

圖4是本發(fā)明中SPDD和WRSD的全選覆蓋性能示意圖。

圖5是本發(fā)明中三種系統(tǒng)碼的BP譯碼失敗概率示意圖