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

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

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

隨著多媒體技術的迅猛發展，視頻應用的范圍越來越廣泛。龐大的數字化視頻數據需要進行高效壓縮，壓縮后的碼流對信道誤碼十分敏感。現有的視頻編碼標準(H.264/AVC)［1］大多以預測編碼為基礎，一旦某幀在傳輸過程中發生錯誤，就會導致其后續幀的錯誤累積。

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

壓縮感知理論［7］可以從很少采樣數據中高準確率重構出原來信號的特性，受到了人們的重視。本文對壓縮感知線性規劃解碼和信道碼線性規劃解碼進行了研究，利用它們之間的聯系，提出了一種基于壓縮感知的LDPC碼的抗誤方法。相對于傳統誤碼，它在高誤碼率時表現出良好的性能。

1 壓縮感知線性規劃解碼

1.1 壓縮感知

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

圖1 壓縮感知理論框架

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

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

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

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

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

4)首先接收端計算

式中:

然后通過解決CS－OPT來獲得對e的估計，通過=y－求得，又因為是線性碼即可得到。求解CSOPT問題的計算極不穩定而且是NP難問題［12］。Chen，Donoho和Saunders［11］指出求解一個更加簡單的L1優化問題會產生同等的解，即

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

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

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

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

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

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

2.1 信道碼線性規劃解碼框架

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

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

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

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

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

式中:

表示形式如式(4)，即

因為代價函數是線性的，并且一個線性函數達到它的凸集的最小極值點，本質上等于CC－MLD2如式(6):

雖然只是一個線性規劃問題，但是因為它的描述復雜性高，所以通常不可以有效解決。

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

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

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

3 CC－LPD與CS－LPD之間的聯系

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

4 實驗仿真

4.1 實驗步驟

由以上的結論可知，如果一個校驗矩陣可以糾正CC－LPD中的k個比特翻轉錯誤，則這個校驗矩陣可以作為CS－LPD中的測量矩陣來恢復k稀疏的錯誤信號。因此可以采用IEEE802.16e標準中的校驗矩陣作為解碼端壓縮感知重構的測量矩陣，實驗步驟圖見圖2。

圖2 實驗步驟圖

步驟如下:

1)對YUV文件進行編碼:通過264編碼器編碼為標準視頻文件264文件，對264文件的每個NAL的長度進行限制。

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

3)編碼:對每一個NAL數據進行基于IEEE802.16e的LDPC編碼。

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

5)LDPC解碼:運用LLR－BP算法進行解碼。

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

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

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

4.2 實驗結果

在對 clip_cif.yuv，akiyo_cif.yuv，news_cif.yuv 進行 2種編解碼方法得到的264文件解碼，發現2種方法能夠正確解碼的最大誤碼相差不大，但是解碼正確率有很大差異。圖3、圖4、圖5為3個不同文件的解碼正確率實驗結果圖。

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

由圖可以看出當信噪比大于2 dB時兩種解碼方法都可以正確解碼，驗證了“如果一個校驗矩陣可以糾正CCLPD中的k個比特翻轉錯誤，則這個校驗矩陣可以作為CS－LPD中的測量矩陣來恢復k稀疏的錯誤信號”的結論。并且由圖可以看出使用CS解碼正確率明顯高于傳統LDPC解碼方法。

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

5 結束語

本文利用CC－LPD和CS－LPD之間的聯系將壓縮感知的重構方法運用在LDPC解碼上。實驗結果表明本文所提出的基于CS的LDPC抗誤方法的解碼正確率明顯高于傳統LDPC解碼方法，提高了抗誤效果，提高了數據重構的精確性，為后續研究提供了保證，為視頻抗誤碼傳輸提供了新的思路。

:

［1］王嵩.H.264視頻編碼新標準及其性能分析［J］.電視技術，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.