[發(fā)明專利]一種Raptor碼的解碼方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201010191845.5
• 申請(qǐng)日: 2010-06-04
• 公開(kāi)（公告）號(hào): CN101882972A
• 公開(kāi)（公告）日: 2010-11-10
• 發(fā)明（設(shè)計(jì)）人: 石東新;徐偉掌;張遠(yuǎn);楊占昕;楊爽
• 申請(qǐng)（專利權(quán)）人: 中國(guó)傳媒大學(xué)
• 主分類號(hào): H04L1/00
• 分類號(hào): H04L1/00;H03M13/00
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

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

本申請(qǐng)涉及一種Raptor解碼方法，該方法可廣泛用于數(shù)字通信、數(shù)據(jù)存儲(chǔ)、數(shù)據(jù)壓縮等技術(shù)領(lǐng)域。

背景技術(shù)

為有效利用移動(dòng)網(wǎng)絡(luò)資源，3GPP提出了多媒體廣播多播業(yè)務(wù)(MBMS)，在移動(dòng)網(wǎng)絡(luò)中提供一個(gè)數(shù)據(jù)源向多個(gè)用戶發(fā)送數(shù)據(jù)的點(diǎn)到多點(diǎn)業(yè)務(wù)。3GPP?MBMS采用Raptor系統(tǒng)碼(一種實(shí)用的噴泉碼)作為前向糾錯(cuò)的編碼方案。噴泉碼可以由K個(gè)原始分組生成任意數(shù)量的編碼分組，只要收到其中任意K(1+ε)(ε＞0)個(gè)編碼分組，就能解碼恢復(fù)K個(gè)原始分組。LT碼是Luby提出噴泉碼的概念后給出的首個(gè)可以實(shí)用的編碼方案。隨后Shokrollahi提出了Raptor碼，其主要思路是在LT編碼前加入傳統(tǒng)的糾錯(cuò)編碼，構(gòu)成串聯(lián)碼，糾錯(cuò)碼作為外碼，LT作為內(nèi)碼，并可進(jìn)行多層外碼編碼。由于Raptor碼采用了糾錯(cuò)編碼，因此可比LT碼接收更少的碼字，就能通過(guò)自身的糾錯(cuò)機(jī)制實(shí)現(xiàn)解碼，從而克服LT碼所需ε偏大的問(wèn)題，并具有線性編解碼時(shí)間的性質(zhì)。

3GPP?MBMS給出的Raptor系統(tǒng)碼是一種高效的編解碼方案。但是該方案給出的解碼算法一般需要接收大于K個(gè)符號(hào)，這是因?yàn)槿我饨邮盏腒個(gè)符號(hào)不一定剛好滿足解碼矩陣A_L×L滿秩，這樣解碼就不能一次性成功。即使N大于K，也不能100％保證一次性解碼成功，僅僅是解碼成功的概率增大，即N越大，解碼成功的概率越大。但是一旦解碼失敗，此時(shí)的解碼結(jié)果無(wú)法再用，必須在接收新的符號(hào)基礎(chǔ)上，重啟解碼過(guò)程，造成解碼時(shí)間比較長(zhǎng)。

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

本發(fā)明可以解決現(xiàn)有技術(shù)方案存在的以上問(wèn)題。解碼失敗后，在接收新符號(hào)后，利用當(dāng)前解碼失敗的結(jié)果繼續(xù)完成解碼，大大縮短解碼時(shí)間并保證解碼的成功率是100％。

一種Raptor碼的解碼方法，其特征在于，包括以下步驟：

步驟1：首先，至少接收K個(gè)符號(hào)，構(gòu)造矩陣

其中，I_S×S和I_H×H分別是S階和H階的單位陣，O_S×H為S×H階的零矩陣，(G_LDPC)_S×K和(H_Half)_H×(S+K)分別是LDPC校驗(yàn)矩陣和Half校驗(yàn)矩陣，(G_LT)_K×L是LT編碼矩陣，L＝S+H+K；

步驟2：對(duì)矩陣A_L×L進(jìn)行高斯變換，變換為的模式，其中I為i×i的單位陣，O為零矩陣，U矩陣有L行u列元素；

步驟3：在對(duì)矩陣A_L×L進(jìn)行高斯消元法變換時(shí)，記錄所有發(fā)生的列交換位置信息，如矩陣A的j列與j′列交換，則記錄j和j′的值；

步驟4：將矩陣U劃分為i行子矩陣U_upper和L-i行子矩陣U_lower；對(duì)U_lower用無(wú)列交換的高斯消元法進(jìn)行變換，如果U_lower的秩是u，則可以將其變換成u×u的單位陣I_u，轉(zhuǎn)向步驟6；否則如果U_lower的秩u′＜u，只能將U_lower轉(zhuǎn)化為I_u′，A矩陣末行會(huì)有零行出現(xiàn)，轉(zhuǎn)向步驟5；

步驟5：接收一個(gè)新的符號(hào)E[x_k+i]，其序號(hào)是x_k+i，每接收一個(gè)新符號(hào)，i按1，2...n遞增，新符號(hào)存入D[d[L-1+i]]，其中d[L-1+i]＝L-1+i；將序號(hào)x_k+i按LT編碼算法得到一串長(zhǎng)度為L(zhǎng)的數(shù)據(jù)串，可看做一個(gè)1×L的矩陣；按照步驟3記錄的對(duì)矩陣A_L×L進(jìn)行的所有列交換位置信息，對(duì)該1×L的矩陣按列進(jìn)行列變換；然后將變換后的1×L矩陣加入到步驟4得到的矩陣A_L×L的L+i行，將該行與矩陣A_L×L第一行的0行交換，得到新的矩陣A_L×L′，回到步驟4對(duì)矩陣A_L×L′重新操作；

步驟6：如果由步驟4直接轉(zhuǎn)到該步驟，則U_lower將被變換成u×u的單位陣I_u；如果經(jīng)歷過(guò)步驟5，則刪除矩陣A_L×L′的全部0行；此時(shí)再用單位陣I_u將子矩陣U_upper中的1全部消去，原矩陣A_L×L轉(zhuǎn)化為單位陣，實(shí)現(xiàn)矩陣求逆，則中間符號(hào)C[c[0]]，C[c[1]]，...，C[c[L-1]]＝D[d[0]]，D[d[1]]，...，D[d[L-1]]；