一種基于CS的LDPC碼的抗誤碼方法

馬文萱，謝正光，張 輝，徐 偉

(南通大學(xué)電子信息學(xué)院，江蘇南通 226019)

隨著多媒體技術(shù)的迅猛發(fā)展，視頻應(yīng)用的范圍越來越廣泛。龐大的數(shù)字化視頻數(shù)據(jù)需要進(jìn)行高效壓縮，壓縮后的碼流對信道誤碼十分敏感。現(xiàn)有的視頻編碼標(biāo)準(zhǔn)(H.264/AVC)［1］大多以預(yù)測編碼為基礎(chǔ)，一旦某幀在傳輸過程中發(fā)生錯(cuò)誤，就會(huì)導(dǎo)致其后續(xù)幀的錯(cuò)誤累積。

傳統(tǒng)抗誤碼方法可分為3種［2］。一種是在編碼端使用冗余容錯(cuò)的方法，如冗余片、靈活宏塊調(diào)整、幀內(nèi)刷新、可伸縮性編碼［3］以及多重描述編碼［4］，然而這些方法增加了冗余數(shù)據(jù)，使得信道的利用率下降。另一種是在解碼端使用錯(cuò)誤隱藏、數(shù)據(jù)恢復(fù)［5－6］的方法，但這些方法只是盡可能地彌補(bǔ)誤碼所帶來的圖像視覺損傷，并不能真正地抑制差錯(cuò)飄移。第3種在視頻傳輸?shù)倪^程中使用某種糾錯(cuò)方法:比如前向糾錯(cuò)，該方法的不足之處是當(dāng)錯(cuò)誤率超出了信道編碼預(yù)設(shè)的糾錯(cuò)能力時(shí)，所重建的視頻質(zhì)量就會(huì)迅速下降，呈現(xiàn)所謂的“懸崖效應(yīng)”。上述表明傳統(tǒng)抗誤碼方法存在諸多不足。

壓縮感知理論［7］可以從很少采樣數(shù)據(jù)中高準(zhǔn)確率重構(gòu)出原來信號的特性，受到了人們的重視。本文對壓縮感知線性規(guī)劃解碼和信道碼線性規(guī)劃解碼進(jìn)行了研究，利用它們之間的聯(lián)系，提出了一種基于壓縮感知的LDPC碼的抗誤方法。相對于傳統(tǒng)誤碼，它在高誤碼率時(shí)表現(xiàn)出良好的性能。

1 壓縮感知線性規(guī)劃解碼

1.1 壓縮感知

壓縮感知理論首先由 Candes、Romberg［8］、Tao［9］和Donoho［10］等人在2004年提出文獻(xiàn)直到2006年才發(fā)表。Candes證明了只要信號在某一個(gè)正交空間具有稀疏性，就能以較低的頻率(M?N)采樣信號，而且能以高概率重構(gòu)該信號。壓縮感知理論指出，設(shè)長度為N的信號X在某組正交基或緊框架ψ上的變換系數(shù)是稀疏的，如果用一個(gè)與變換基ψ不相關(guān)的觀測基φM×N(M?N)對系數(shù)向量進(jìn)行線性變換，并得到觀測集合M×1。那么就可以利用優(yōu)化求解方法從觀測集合中精確或低概率地重構(gòu)原始信號X。壓縮感知理論是一種新的在采樣的同時(shí)實(shí)現(xiàn)壓縮目的的理論框架，其框架如圖1所示。

圖1 壓縮感知理論框架

首先，如果信號X∈Rn在某個(gè)正交基或緊框架ψ上是可壓縮的，求出變換系數(shù)Θ=ΨTX，Θ是Ψ的等價(jià)或逼近的稀疏表示;第二步，設(shè)計(jì)一個(gè)平穩(wěn)，與變換基Ψ不相關(guān)的M×N維觀測矩陣Ψ，對Θ進(jìn)行觀測得到觀測集合Y=ΦΘ=ΦΨTX，該過程也可以表示為信號X通過矩陣ACS進(jìn)行非自適應(yīng)觀測:Y=ACSX(其中ACS=ΦΨT)，ACS稱為CS信息算子［11］;最后，利用0－范數(shù)意義下的優(yōu)化問題求解X的精確或近似逼近，見式(1)，稀疏信號e，對于合適的HCS，CS－OPT產(chǎn)生的估計(jì)值等于e，見式(2)。

假設(shè)輸入信號為x，輸出信號為y，并且這個(gè)信息符號在塊長度為n、維度為k=n－rank(Hcs)的實(shí)值碼CCS的幫助下編碼，過程如下:

1)CCS碼滿足 CCS∈{x∈Rn∣ HCS·x=0}。

2)假設(shè)一個(gè)生成矩陣GCS∈Rn×k滿足CCS∈{GCS·u∣u∈Rk}，通過這個(gè)生成矩陣進(jìn)行x=GCS·u運(yùn)算，信息向量u∈Rk被編碼成碼字x∈Rn。

3)設(shè)y∈ynCS為接收到的向量。對于一個(gè)合適的定義向量e∈Rn，稱作錯(cuò)誤向量，可以寫成y=x+e。假設(shè)這個(gè)e是稀疏的，也就是說非零項(xiàng)個(gè)數(shù)被一些正整數(shù)k限制。

4)首先接收端計(jì)算

式中:

然后通過解決CS－OPT來獲得對e的估計(jì)，通過=y－求得，又因?yàn)槭蔷€性碼即可得到。求解CSOPT問題的計(jì)算極不穩(wěn)定而且是NP難問題［12］。Chen，Donoho和Saunders［11］指出求解一個(gè)更加簡單的L1優(yōu)化問題會(huì)產(chǎn)生同等的解，即

1.2 CS－LPD與CS－OPT等同的條件

探究CS－LPD與CS－OPT結(jié)果等同的條件，就是探究在何種條件下CS－LPD可以準(zhǔn)確求解出原來的信號，也就是探究何種測量矩陣的LP松弛是緊的。文獻(xiàn)［12］已經(jīng)指出一個(gè)測量矩陣的行數(shù)m滿足m=Θ(klog(n/k))，則可以通過CS－LPD恢復(fù)出k稀疏信號，表示為k=Θ(n)，但是它最適宜的量度要求構(gòu)造的矩陣的測量值數(shù)量線性于信號的維度n。一個(gè)證明測量矩陣是“好的”的充分條件是文獻(xiàn)［13－14］指出的有限等距性質(zhì)(Restricted Isometry Property，RIP)，如果測量矩陣滿足RIP，則它的LP松弛對于K稀疏向量e是緊的，并且重構(gòu)可以達(dá)到近似稀疏［13］。眾所周知，RIP不是一個(gè)“好的”測量矩陣的LP松弛的完整特性，而零空間性質(zhì)［15－16］是一個(gè)對于“好的”測量矩陣的必須且充分的條件。

定義1:假設(shè)，C∈R≥0。如果C·‖vs‖1≤‖v‖1對于所有v∈nullspaceR(HCS)成立就說明HCS具有零空間性質(zhì)NSPR≤(S，C)，寫成HCS∈NSPR≤(S，C)。如果C·‖vs‖1＜‖v‖1對于所有v∈nullspaceR(HCS)［17］成立就可以說明HCS具有嚴(yán)格的零空間性質(zhì)NSPR＜(S，C)，寫成 HCS∈NSPR＜(S，C)。

定義2:假設(shè)k∈Z≥0，C∈R≥0。如果 HCS∈NSPR≤(S，C)對于所有S?I(HCS)成立并且S≤k，則認(rèn)為HCS具有零空間性質(zhì)NSPR≤(k，C)寫成HCS∈NSPR≤(k，C)。如果HCS∈NSPR＜(S，C)對于所有S?I(HCS)并且S≤k，則認(rèn)為HCS具有嚴(yán)格的零空間性質(zhì)NSPR≤ (k，C)，寫成 HCS∈NSPR＜(k，C)。

文獻(xiàn)［16］分別給出了如上定義。定義2中的零空間條件對于K稀疏信號的“好的”測量矩陣是必須并且充分的，也就是說對于這些矩陣CS－LPD的估計(jì)值等同于CS－OPT的估計(jì)值。“好的”測量矩陣的零空間性質(zhì)是將CS－LPD和CC－LPD聯(lián)系起來的重要關(guān)鍵點(diǎn)之一。可以得出以下理論:設(shè)HCS是一個(gè)測量矩陣，并且假設(shè)s=HCS·e，而且 e最多有k個(gè)非零元素，可以表示為‖e‖0≤k。如果HCS∈NSPR＜(k，C=1)，則由CSLPD產(chǎn)生的估計(jì)值e等同于CS－OPT產(chǎn)生的估計(jì)值e。

2 信道碼線性規(guī)劃解碼(CC－LPD)

2.1 信道碼線性規(guī)劃解碼框架

設(shè)輸入 xCC? {0，1}，輸出 yCC，信道規(guī)則為PY︱X(y︱x)。這個(gè)編碼方案是以一個(gè)塊長度為n、維度為k的二元線性碼CCC為基礎(chǔ)的，n≥k。下面來定義XCC:

1)設(shè) GCC∈為對于CCC的生成矩陣。因此，GCC秩為k，并且信息向量u∈通過x=GCC·u(mod 2)被編碼成x∈，也就是CCC={GCC·u︱u∈}。

2)設(shè) HCC∈是一個(gè)對于CCC的校驗(yàn)矩陣。因此，HCC的秩n－k≤m，并且對于任x∈，當(dāng)且僅當(dāng)x∈CCC時(shí)滿足HCC·x=0(mod 2)，也就是說CCC={x∈︱HCC·x=0(mod 2)}。3)y∈ ynCC為接收到的向量，定義每個(gè)i∈I(HCC)(I(HCC)代表H的行集合)，對數(shù)似然比為

4)令yCC是二元的，可以寫成y=x+e(mod 2)，e∈為錯(cuò)誤向量，s=H·y(mod 2)，s=H·y=H·

CCCCCC(x+e)=HCC·x+HCC·e=HCC·e(mod 2)。最大似然解碼(MLD)規(guī)則為

式中:

表示形式如式(4)，即

因?yàn)榇鷥r(jià)函數(shù)是線性的，并且一個(gè)線性函數(shù)達(dá)到它的凸集的最小極值點(diǎn)，本質(zhì)上等于CC－MLD2如式(6):

雖然只是一個(gè)線性規(guī)劃問題，但是因?yàn)樗拿枋鰪?fù)雜性高，所以通常不可以有效解決。

C 可以被寫成 CCC=CCC，1∩ … ∩ CCC，m，所以conv(CCC)=conv(CCC，1∩ … ∩ CCC，m)?conv(CCC，1)∩ … ∩conv(CCC，m)=P(HCC)。在文獻(xiàn)［18－19］中如下結(jié)論被證實(shí):松弛具有一個(gè)重要的性質(zhì)即所有conv(CCC)的頂點(diǎn)都是P(HCC)的頂點(diǎn)。所以CC－MLD問題轉(zhuǎn)換為CC－LPD問題表示為式(7)，即

2.2 CC－LPD與CC－MLD等同的條件

在二元對稱信道中，設(shè)HCC為碼CCC的一個(gè)校驗(yàn)矩陣，設(shè)S?I(HCC)。如果HCC滿足‖ωS‖1＜‖ω‖1，對于所有ω∈k(HCC){0}，則CC－LPD的結(jié)果等于這個(gè)發(fā)送的結(jié)果。其中，

3 CC－LPD與CS－LPD之間的聯(lián)系

由以上分析可知，要知道CC－LPD和CS－LPD之間的聯(lián)系，就需要理解在零空間里的哪些點(diǎn)可以與在基本多面體空間里的點(diǎn)產(chǎn)生聯(lián)系。文獻(xiàn)［20］中指出如下定理:設(shè)HCS是一個(gè)0－1測量矩陣，則v∈Nullsp(HCS)?|v|∈K(HCS)。即表示在HCS的R零空間的每個(gè)點(diǎn)可以聯(lián)系到HCS的基本錐空間上的一個(gè)點(diǎn)。因此，一個(gè)對于R零空間的問題點(diǎn)，將會(huì)轉(zhuǎn)化成在多面錐上的一個(gè)問題點(diǎn)，導(dǎo)致CC－LPD具有糟糕的性能。簡單來說，如果一個(gè)校驗(yàn)矩陣HCS在多面錐空間里有不低的偽碼重量點(diǎn)，則在HCS的R零空間域中沒有問題點(diǎn)。在文獻(xiàn)［19］中給出了不同信道下的最低偽碼重量。

4 實(shí)驗(yàn)仿真

4.1 實(shí)驗(yàn)步驟

由以上的結(jié)論可知，如果一個(gè)校驗(yàn)矩陣可以糾正CC－LPD中的k個(gè)比特翻轉(zhuǎn)錯(cuò)誤，則這個(gè)校驗(yàn)矩陣可以作為CS－LPD中的測量矩陣來恢復(fù)k稀疏的錯(cuò)誤信號。因此可以采用IEEE802.16e標(biāo)準(zhǔn)中的校驗(yàn)矩陣作為解碼端壓縮感知重構(gòu)的測量矩陣，實(shí)驗(yàn)步驟圖見圖2。

圖2 實(shí)驗(yàn)步驟圖

步驟如下:

1)對YUV文件進(jìn)行編碼:通過264編碼器編碼為標(biāo)準(zhǔn)視頻文件264文件，對264文件的每個(gè)NAL的長度進(jìn)行限制。

2)對264文件進(jìn)行處理:將264文件按NAL為單位分別存儲，轉(zhuǎn)換為二進(jìn)制數(shù)據(jù)。IEEE802.16e標(biāo)準(zhǔn)中的碼長從 576～2 304不等，碼率有 1/2，2/3A，2/3B，3/4A，3/4B，5/6共6種。此次仿真中選取碼長為2 304、碼率為3/4A進(jìn)行仿真。對不足2 304長度的NAL進(jìn)行補(bǔ)0處理。

3)編碼:對每一個(gè)NAL數(shù)據(jù)進(jìn)行基于IEEE802.16e的LDPC編碼。

4)信道仿真:分別加入信噪比為－1～+1.8 dB(步長0.2 dB)與1.9～3.5 dB(步長0.1 dB)的噪聲。

5)LDPC解碼:運(yùn)用LLR－BP算法進(jìn)行解碼。

6)CS重構(gòu)解碼:設(shè)IEEE 802.16e中的校驗(yàn)矩陣為H，經(jīng)過LDPC編碼和信道仿真的信號為y∈F2，其中y=x+e。x∈F2為經(jīng)過LDPC編碼得到的信號，e∈F2為錯(cuò)誤信號。將式子兩邊同時(shí)乘以H得到

因?yàn)镠為x的生成矩陣，且x為線性碼，所以H·x(mod 2)為0，所以

通過求解式(15)得到e，通過回代即可得到y(tǒng)。

4.2 實(shí)驗(yàn)結(jié)果

在對 clip_cif.yuv，akiyo_cif.yuv，news_cif.yuv 進(jìn)行 2種編解碼方法得到的264文件解碼，發(fā)現(xiàn)2種方法能夠正確解碼的最大誤碼相差不大，但是解碼正確率有很大差異。圖3、圖4、圖5為3個(gè)不同文件的解碼正確率實(shí)驗(yàn)結(jié)果圖。

圖4 兩種方法的解碼成功率對比圖

由圖可以看出當(dāng)信噪比大于2 dB時(shí)兩種解碼方法都可以正確解碼，驗(yàn)證了“如果一個(gè)校驗(yàn)矩陣可以糾正CCLPD中的k個(gè)比特翻轉(zhuǎn)錯(cuò)誤，則這個(gè)校驗(yàn)矩陣可以作為CS－LPD中的測量矩陣來恢復(fù)k稀疏的錯(cuò)誤信號”的結(jié)論。并且由圖可以看出使用CS解碼正確率明顯高于傳統(tǒng)LDPC解碼方法。

圖5 兩種方法的解碼成功率對比圖

5 結(jié)束語

本文利用CC－LPD和CS－LPD之間的聯(lián)系將壓縮感知的重構(gòu)方法運(yùn)用在LDPC解碼上。實(shí)驗(yàn)結(jié)果表明本文所提出的基于CS的LDPC抗誤方法的解碼正確率明顯高于傳統(tǒng)LDPC解碼方法，提高了抗誤效果，提高了數(shù)據(jù)重構(gòu)的精確性，為后續(xù)研究提供了保證，為視頻抗誤碼傳輸提供了新的思路。

:

［1］王嵩.H.264視頻編碼新標(biāo)準(zhǔn)及其性能分析［J］.電視技術(shù)，2003，27(6):25－27.

［2］WANG Y，STEPBUN W，WEN J T，et al.Error resilient video coding techniques［J］.Signal Processing Magazine，2000，17(4):61－82.

［3］WANG Guijin，ZHANG Qian.Channel－adaptive error protection for scalable video over channels with bit errors and packet erasures［C］//Proc.IEEE International Symposium on Circuits and Systems.［S.l.］:IEEE Press，2002:712－715.

［4］MIGUEL A C，MOHR A E，RISKIN E A.SPIHT for generalized multiple description coding［C］//Proc.International Conference on Image Processing.Kobe:IEEE Press，1999:842－846.

［5］KANG K，KIM T.Improved error control for real－time video broadcasting over CDMA 2000 networks［J］.IEEE Trans.Vehicular Technology，2009，58(1):188－197.

［6］BO Y，GHARAVI H.A hybrid frame concealment algorithm for H.264 AVC［J］.IEEE Trans.Image Processing，2010，19(1):98－107.

［7］DONOHO D L.Compressed sensing［J］.IEEE Trans.Information Theory，2006，52(4):1289－1306.

［8］CANDES E，ROMBERG J.Quantitative robust uncertainty principles and optimally sprase decompositions［J］.Foundations of Comput.Math.，2006，6(2):227－254.

［9］CANDES E J，TAO T.Near optimal signal recovery from random projections:Universal encoding strategies［J］.IEEE Trans.Information Theory，2006，52(12):5406－5425.

［10］DONOHO D L，TANNER J.Neighborliness of randomly projected simplices in high dimensions［J］.Academy of Sciences of USA，2005，102(27):9452－9457.

［11］BARANIUK R G.A lecture on compressive sensing［J］.Signal Processing Magazine，2007，24(4):118－121.

［12］CHEN S S，DONOHO D L，SAUNDERS M A.Atomic decomposition by basis pursuit［J］.SIAM Journal on Scientific Computing，1998，20(1):33－61.

［13］CANDES E J，ROMBERG J，TAO T.Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information［J］.IEEE Trans.Information Theory，2006，52(2):489－509.

［14］CANDES E.The restricted isometry property and its implications for compressed sensing［J］.ScienceDirect，2006，346(9):589－592.

［15］XU W Y，HASSIBI B.Compressed sensing over the grassmann manifold:a unified analytical framework［C］//Proc.2008 46th Annual Allerton Conference on Communication，Control and Computing.［S.l.］:IEEE Press，2008:562－567.

［16］STOJNIC M，XU W Y，HASSIBI B.Compressed sensing－probabilistic analysis of a null－space characterization［C］//Proc.IEEE International Conference on Acoustics Speech and Signal Processing.［S.l.］:IEEE Press，2008:3377－3380.

［17］MONAJEMI H，JAFARPOUR S，GAVISH M，et al.Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices［EB/OL］.［2013－12－25］.http://www.pnas.org/content/110/4/1181.short.

［18］JON F.Decoding error－correcting codes via linear programming［EB/OL］.［2013－12－25］.http://hdl.handle.net/1721.1/42831.

［19］FELDMAN J.Using linear programming to decode binary linear codes［J］.IEEE Trans.Information Theory，2005，51(3):945－972.

［20］SMARANDACHE R，VONTOBEL P O.Absdet－pseudo－codewords and perm－pseudo－codewords:definitions and properties［C］//Proc.IEEE International Symposium on Information Theory.［S.l.］:IEEE Press，2009:229－233.