?一、LDPC碼簡介

低密度校驗碼（LDPC碼）是一種前向糾錯碼，LDPC碼最早在20世紀60年代由Gallager在他的博士論文中提出，但限于當時的技術(shù)條件，缺乏可行的譯碼算法，此后的35年間基本上被人們忽略，其間由Tanner在1981年推廣了LDPC碼并給出了LDPC碼的圖表示，即后來所稱的Tanner圖。1993年Berrou等人發(fā)現(xiàn)了Turbo碼，在此基礎(chǔ)上，1995年前后MacKay和Neal等人對LDPC碼重新進行了研究，提出了可行的譯碼算法，從而進一步發(fā)現(xiàn)了LDPC碼所具有的良好性能，迅速引起強烈反響和極大關(guān)注。經(jīng)過十幾年來的研究和發(fā)展，研究人員在各方面都取得了突破性的進展，LDPC碼的相關(guān)技術(shù)也日趨成熟，甚至已經(jīng)開始有了商業(yè)化的應用成果，并進入了無線通信等相關(guān)領(lǐng)域的標準。

1.1.1 LDPC碼的特點

LDPC碼是一種分組碼，其校驗矩陣只含有很少量非零元素。正是校驗矩陣的這種稀疏性，保證了譯碼復雜度和最小碼距都只隨碼長呈現(xiàn)線性增加。除了校驗矩陣是稀疏矩陣外，碼本身與任何其它的分組碼并無二致。其實如果現(xiàn)有的分組碼可以被稀疏矩陣所表達，那么用于碼的迭代譯碼算法也可以成功的移植到它身上。然而，一般來說，為現(xiàn)有的分組碼找到一個稀疏矩陣并不實際。不同的是，碼的設(shè)計是以構(gòu)造一個校驗矩陣開始的，然后才通過它確定一個生成矩陣進行后續(xù)編碼。而LDPC的編碼就是本文所要討論的主體內(nèi)容。

譯碼方法是LDPC碼與經(jīng)典的分組碼之間的最大區(qū)別。經(jīng)典的分組碼一般是用ML類的譯碼算法進行譯碼的，所以它們一般碼長較小，并通過代數(shù)設(shè)計以減低譯碼工作的復雜度。但是LDPC碼碼長較長，并通過其校驗矩陣H的圖像表達而進行迭代譯碼，所以它的設(shè)計以校驗矩陣的特性為核心考慮之一。

1.1.2 LDPC碼的構(gòu)造

構(gòu)造二進制LDPC碼實際上就是要找到一個稀疏矩陣H作為碼的校驗矩陣，基本方法是將一個全零矩陣的一小部分元素替換成1，使得替換后的矩陣各行和各列具有所要求的數(shù)目的非零元素。如果要使構(gòu)造出的碼可用，則必須滿足幾個條件，分別是無短環(huán)，無低碼重碼字，碼間最小距離要盡可能大。

1.1.3 Tanner圖

LDPC碼常常通過圖來表示，而Tanner圖所表示的其實是LDPC碼的校驗矩陣。Tanner圖包含兩類頂點:n個碼字比特頂點(稱為比特節(jié)點)，分別與校驗矩陣的各列相對應和m個校驗方程頂點(稱為校驗節(jié)點)，分別與校驗矩陣的各行對應。校驗矩陣的每行代表一個校驗方程，每列代表一個碼字比特。所以，如果一個碼字比特包含在相應的校驗方程中，那么就用一條連線將所涉及的比特節(jié)點和校驗節(jié)點連起來，所以Tanner圖中的連線數(shù)與校驗矩陣中的1的個數(shù)相同。以下圖是矩陣

的Tanner圖，其中比特節(jié)點用圓形節(jié)點表示，校驗節(jié)點用方形節(jié)點表示，加黑線顯示的是一個6循環(huán)：

Tanner圖中的循環(huán)是由圖中的一群相互連接在一起的頂點所組成的，循環(huán)以這群頂點中的一個同時作為起點和終點，且只經(jīng)過每個頂點一次。循環(huán)的長度定義為它所包含的連線的數(shù)量，而圖形的圍長，也可叫做圖形的尺寸，定義為圖中最小的循環(huán)長度。如上圖中，圖形的尺寸，即圍長為6，如加黑線所示。

1.2 LDPC編碼

方法一：設(shè)H=[A | B]，對H進行高斯消元可得到H=[I| P]，設(shè)編碼完成的碼字為u=[c| s]，其中c為監(jiān)督位，s為信息位。因為H*u' = u*H' = 0，可以得到I*c' + P*s' = 0 即 I*c' = P*s' (在GF(2)上)，從而可求 c' = P*s'。如果高斯消元過程中進行了列交換，則只需記錄列交換，并以相反次序?qū)幋a后的碼字同樣進行列交換即可。解碼時先求出u，再進行列交換得到u1=[c| s]，后面部分即是想要的信息。

方法一示例：

方法二：首先推導出根據(jù)校驗矩陣直接編碼的等式。將尺寸為m*n校驗矩陣H寫成如下形式：H=[H1 | H2]，其中H1矩陣的大小為m*k，H2的大小為m*m，設(shè)編碼完成的碼字為u=[s | p]，s為信息位，p為監(jiān)督位。因為H*u' =u*H' = 0求得p*H2'=s*H1'，最后得p=s* H1'* (H2')-

上述兩種方法可以不通過生成矩陣而直接由校驗矩陣進行編碼的等式,一切只依賴校驗矩陣的編碼都是通過這兩個式子實現(xiàn)的。但方法二要考慮H2是否滿秩（可逆）。

1.3 LDPC碼H矩陣的構(gòu)造

規(guī)則的LDPC碼和非規(guī)則的LDPC碼

如果校驗矩陣中各行非零元素的個數(shù)相同，各列中非零元素的個數(shù)也相同，這樣的LDPC碼稱為規(guī)則碼，與規(guī)則碼對照，如果校驗矩陣的各行中非零元素的個數(shù)不同或各列中非零元素個數(shù)不同，此時的LDPC碼稱為非規(guī)則的LDPC碼。

1.3.1 非規(guī)則的LDPC碼

構(gòu)造方法：碼率R=M/N=0.5，構(gòu)造的H矩陣列重固定，而行重是隨機的。下面通過一個大小為6*12，列重為2的H矩陣來說明。因為列重固定為2，所以其列坐標集合為[1,1,2,2,3,3,4,4…….12,12]，而行坐標可以隨機構(gòu)造。

1.???????先構(gòu)造一個6*12，每一列為1到6隨機排列的矩陣onesInCol。

2.???????選取onesInCol的前2行（和列重一致），如上圖所示。

3.??????? 將所選取的矩陣按列依次排列如下

?

4.???????構(gòu)造矩陣tmp

5.???????矩陣tmp重排成c1

6.???????full 把稀疏矩陣轉(zhuǎn)換為滿陣顯示， sparse 創(chuàng)建稀疏矩陣生成M*N階稀疏矩陣H在以向量r1和c1為坐標的位置上的對應元素值為向量1的對應值。

1.3.2 規(guī)則的LDPC 碼

對于碼率R=0.5的規(guī)則的LDPC碼其行重與列重有關(guān)，行重是列重的2倍。以6*12的H矩陣為例，假設(shè)其列重為2，每列1的個數(shù)為2，總的1的個數(shù)為2*12=24，H矩陣有6行，行重相同則每行1的個數(shù)為24/6=4，即行重為4。假設(shè)其列重為3，其行重為6。

構(gòu)造方法：與構(gòu)造行重類似，行重列重固定之后，其在矩陣中的位置坐標集合固定，如列重為2，行重為4，列坐標集合為[1，1，2，2，3，3，…..]，行坐標集合為[1,1,1,1,2,2,2,2,3,3,3,3,……]，下面考慮的就是如何將行列坐標組合起來而不重復。這里采用的是保持行坐標集合不變，列坐標集合打亂重排。以構(gòu)造大小5*10，列重為2，行重為4的H矩陣為例說明。

1.???????先構(gòu)造一個5*10，每一列為1到5隨機排列的矩陣onesInCol。

2.???????選取onesInCol的前2行（和列重一致）構(gòu)成1*20的矩陣

3.???????將r按升序排列得到

4.???????記錄下排列前的位置索引

5.???????因為列坐標集合為[1,1,2,2,3,3,4,4,……9,9,10,10]，將列坐標集合根據(jù)上面的位置索引重新排列，得到c

?

6.???????行坐標集合如下，與列坐標一一對應，確定矩陣H中1的位置。

7.???????最后結(jié)果

1.3.3 LDPC碼的環(huán)

在 LDPC 碼的 Tanner 圖中，從一個頂點出發(fā)，經(jīng)過不同頂點后回到同一個頂點的一些“邊”組成的回路稱為“環(huán)”。經(jīng)過的邊的個數(shù)稱為環(huán)的長度。所有環(huán)中周長最小的環(huán)稱為 LDPC碼的圍長(girth) ?。

Tanner 圖中的環(huán)不可避免的會對譯碼結(jié)果造成非常大的干擾。由于迭代概率譯碼會使信息在節(jié)點間交互傳遞，若存在環(huán)，從環(huán)的某一個節(jié)點出發(fā)的信息會沿著環(huán)上的節(jié)點不斷傳遞并最終重新回到這個節(jié)點本身，從而使得節(jié)點自身信息不斷累加，進而使得譯碼的最終結(jié)果失敗的概率變大。顯然，環(huán)長越小，信息傳遞回本身所需走的路徑就越短，譯碼失敗的概率就變得越高。Tanner 圖形成一個環(huán)至少需要 4 個節(jié)點組成4 條相連的邊，即環(huán)長最小為4，這類短環(huán)對碼字的譯碼結(jié)果干擾最大。定義 LDPC碼的行列(RC)約束為：兩行或兩列中不存在元素 1 的位置有 1 個以上相同的情況。顯然，滿足 RC 約束的 LDPC 碼最低就是 6 環(huán)，去除了4 環(huán)的干擾。由于4環(huán)的檢測以及避免最為簡單并且必要，因此絕大部分構(gòu)造方法都會滿足 RC 約束。而構(gòu)造大圈長的碼字則需要精確的設(shè)計。

1.4 LDPC譯碼

Gallager 在描述 LDPC 碼的時候，分別提出了硬判決譯碼算法和軟判決譯碼算法兩種。經(jīng)過不斷發(fā)展，如今的硬判決算法已在 Gallager 算法基礎(chǔ)上進展很多，包含許多種加權(quán)比特翻轉(zhuǎn)譯碼算法及其改進形式。硬判決和軟判決各有優(yōu)劣，可以適用于不同的應用場合。

1.4.1 比特翻轉(zhuǎn)算法（BF）

硬判決譯碼算法最早是 Gallager 在提出 LDPC 碼軟判決算法時的一種補充。硬判決譯碼的基本假設(shè)是當校驗方程不成立時，說明此時必定有比特位發(fā)生了錯誤，而所有可能發(fā)生錯誤的比特中不滿足校驗方程個數(shù)最多的比特發(fā)生錯誤的概率最大。在每次迭代時均翻轉(zhuǎn)發(fā)生錯誤概率最大的比特并用更新之后的碼字重新進行譯碼。具體步驟如下：

1.???????設(shè)置初始迭代次數(shù) k1及其上限kmax 。對獲得的碼字y=（y1，y2…yn）按照下式展開二元硬判決得到接收碼字的硬判決序列Zn 。

2.???????若k1=kmax ，則譯碼結(jié)束。不然，計算伴隨式s=(s0,s1,…sm-1)，sm表示第m個校驗方程的值。若伴隨式的值均為 0，說明碼字正確，譯碼成功。否則說明有比特位錯誤。繼續(xù)進行步驟3。

3.???????對每個比特，統(tǒng)計其不符合校驗方程的數(shù)量fn （1<=n<=N）

4.???????將最大fn所對應的比特進行翻轉(zhuǎn)，然后k=k+1，返回步驟2。

BF 算法的理論假設(shè)是若某個比特不滿足校驗方程的個數(shù)最多，則此比特是最有可能出錯的比特，因此，選擇這個比特進行翻轉(zhuǎn)。BF 算法舍棄了每個比特位的可靠度信息，單純的對碼字進行硬判決，理論最為簡單，實現(xiàn)起來最容易，但是性能也最差。當連續(xù)兩次迭代翻轉(zhuǎn)函數(shù)判斷同一個比特位為最易出錯的比特時，BF 算法會陷入死循環(huán)，大大降低了譯碼性能。

二、DCT變換

DCT變換的全稱是離散余弦變換(Discrete Cosine Transform)，離散余弦變換相當于一個長度大概是它兩倍的離散傅里葉變換，這個離散傅里葉變換是對一個實偶函數(shù)進行的。通過數(shù)字信號處理的學習我們知道實函數(shù)的傅立葉變換獲得的頻譜大多是復數(shù)，而偶函數(shù)的傅立葉變換結(jié)果是實函數(shù)。以此為基礎(chǔ)，使信號函數(shù)成為偶函數(shù)，去掉頻譜函數(shù)的虛部，是余弦變換的特點之一。它可以將將一組光強數(shù)據(jù)轉(zhuǎn)換成頻率數(shù)據(jù)，以便得知強度變化的情形。若對高頻的數(shù)據(jù)做些修飾，再轉(zhuǎn)回原來形式的數(shù)據(jù)時，顯然與原始數(shù)據(jù)有些差異，但是人類的眼睛卻是不容易辨認出來。壓縮時，將原始圖像數(shù)據(jù)分成8*8數(shù)據(jù)單元矩陣，例如亮度值的第一個矩陣內(nèi)。

2.DCT產(chǎn)生的工程背景：

視頻信號的頻譜線在0-6MHz范圍內(nèi)，而且1幅視頻圖像內(nèi)包含的大多數(shù)為低頻頻譜線，只在占圖像區(qū)域比例很低的圖像邊緣的視頻信號中才含有高頻的譜線。因此，在視頻信號數(shù)字處理時，可根據(jù)頻譜因素分配比特數(shù)：對包含信息量大的低頻譜區(qū)域分配較多的比特數(shù)，對包含信息量低的高頻?譜區(qū)域分配較少的比特數(shù)，而圖像質(zhì)量并沒有可察覺的損傷，達到碼率壓縮的目的。然而，這一切要在低熵(Entropy)值的情況下，才能達到有效的編碼。能否對一串數(shù)據(jù)進行有效的編碼，取決于每個數(shù)據(jù)出現(xiàn)的概率。每個數(shù)據(jù)出現(xiàn)的概率差別大，就表明熵值低，?可以對該串數(shù)據(jù)進行高效編碼。反之，出現(xiàn)的概率差別小，熵值高，則不能進行高效編碼。視頻信號的數(shù)字化是在規(guī)定的取樣頻率下由A/D轉(zhuǎn)換器對視頻電平轉(zhuǎn)換而來的，每個像素的視頻信號幅度隨著每層的時間而周期性地變化。每個像素的平均信息量的總和為總平均信息量，即熵值。由于每個視頻電平發(fā)生幾乎具有相等的概率，所以視頻信號的熵值很高。?熵值是一個定義碼率壓縮率的參數(shù)，視頻圖像的壓縮率依賴于視頻信號的熵值，在多數(shù)情況下視頻信號為高熵值，要進行高效編碼，就要將高熵值變?yōu)榈挽刂怠Ｔ鯓幼兂傻挽刂的?？這就需要分析視頻頻譜的特點。大多數(shù)情況下，視頻頻譜的幅度隨著頻率的升高而降低。其中?低頻頻譜在幾乎相等的概率下獲得0到最高的電平。與此相對照，高頻頻譜通常得到的是低電平及稀少的高電平。顯然，低頻頻譜具有較高的熵值，高頻頻譜具有較低的熵值。據(jù)此，可對視頻的低頻分量和高頻分量分別處理，獲得高頻的壓縮值。

自從Ahmed和Rao于1974年給出了離散余弦變換（DCT）的定義以來，離散余弦變換（DCT）與改進型離散余弦變換（MDCT）就成為廣泛應用于信號處理和圖像處理特別是用于圖像壓縮和語音壓縮編解碼的重要工具和技術(shù)，一直是國際學術(shù)界和高科技產(chǎn)業(yè)界的研究熱點?，F(xiàn)在的很多圖像和視頻編碼標準（如MPEG-1 ， MEPG-2 ，MEPG-4中的第二部分）都要求實現(xiàn)整數(shù)的8×8 的DCT和IDCT，而MDCT 和IMDCT 則主要被應用于音頻信號的編解碼中（如MPEG-1 ，MEPG-2 和AC-]等標準的音頻編碼部分）。正是由于這類變換被廣泛采用，對于這類變換的快速算法的研究才顯得尤為重要。特別是針對特定的應用條件下的快速算法的研究對于提高整個系統(tǒng)的性能表現(xiàn)有很大幫助。
??? 由上面的引用可見，碼率壓縮基于變換編碼和熵值編碼兩種算法。前者用于降低熵值，后者將數(shù)據(jù)變?yōu)榭山档捅忍財?shù)的有效編碼方式。在MPEG標準中，變換編碼采用的是DCT，變換過程本身雖然并不產(chǎn)生碼率壓縮作用，但是變換后的頻率系數(shù)卻非常有利于碼率壓縮。?實際上壓縮數(shù)字視頻信號的整個過程分為塊取樣、DCT、量化、編碼4個主要過程進行-----首先在時間域?qū)⒃紙D像分成N(水平)×N（垂直）取樣塊，根據(jù)需要可選擇4×4、4×8、8×8、8×16、16×16等塊，這些取樣的像素塊代表了原圖像幀各像素的灰度值，其范圍在139-163之間，并依序送入DCT編碼器，以便將取樣塊由時間域轉(zhuǎn)換為頻率域的DCT系數(shù)塊。DCT系統(tǒng)的轉(zhuǎn)換分別在每個取樣塊中進行，這些塊中每個取樣是數(shù)字化后的值，表示一場中對應像素的視頻信號幅度值

3.離散余弦變換的實現(xiàn)：

實現(xiàn)DCT的方法很多，最直接的是根據(jù)DCT的定義來計算。以二維8xSDCT為例，需要作4096次乘法和3584次加法。這種算法的實現(xiàn)需要巨大的計算量，不具有實用價值。在應用中，需要尋找快速而又精確的算法。較為常用的方法是利用DCT的可拆分特性，同樣以二維8xSDCT為例，先進行8行一維DCT需要64xＳ次乘法和56xS次加法，再進行8列一維DCT要64xS次乘法和56xS次加法，共需要64x8xZ=1024次乘法和56x8xZ=896次加法，計算量大為減少。

除此之外，DCT還有很多公開的快速算法?？焖偎惴ㄖ饕峭ㄟ^減少運算次數(shù)而減少運算時間，這對于設(shè)計快速的硬件系統(tǒng)非常有效。二維DCT的快速算法則一般采用行列分離DCT算法，即轉(zhuǎn)換為兩次一維變換，其間通過轉(zhuǎn)置矩陣連接。最為經(jīng)典和常用的快速算法是由Arai等人于1988年提出的AAN算法以及Loeffier等人于1989年提出的LLM算法。但是，由于行列分離DCT算法能夠重復使用一維變換結(jié)構(gòu)，因此在實際實現(xiàn)上，尤其在硬件上比二維直接計算算法更有優(yōu)勢。

?