LDPC 譯碼器的研究與設計

1、 山 東 科 技 大 學本科畢業(yè)設計（論文）題 目 LDPC 譯碼器的研究與設計 學 院 名 稱 電子通信與物理學院 專業(yè)班級 電子信息科學與技術2010-2班 學生姓名 唐彤彤 學 號 201001051023 指 導 教 師 張小軍 填表時間：二0一四年 月 日摘 要LDPC (Low Density Parity Check Codes)碼，又叫低密度奇偶校驗碼，是一種可以由校驗矩陣直接確定的編碼方式，該碼的碼長一般較長，但是卻仍能保持較高的譯碼性能。同時它具有接近香農極限的差錯控制性能，以及譯碼復雜度低、吞吐率高的優(yōu)點引起了人們的關注，成為繼Turbo 碼后信道編碼界的又一研究熱點。本

2、文實現了一種基于IEEE802.15.3c 標準的LDPC 碼譯碼器。該譯碼器采用歸一化最小和（Normalized Min Sum）算法，其歸一化因子取值為0.75，具有接近置信傳播（Belief Propagation）算法的性能。根據譯碼算法提出了一種基于伸縮因子的量化方案，該量化方案應用于歸一化最小和算法時的譯碼性能與浮點性能相比僅相差0.1dB。同時針對TDMP算法提出了雙閾值迭代終止算法，可以節(jié)約迭代的次數，降低硬件復雜度。本文提出的幾種算法，對LDPC碼譯碼器的研究有一定的參考價值。關鍵字：LDPC碼；IEEE802.15.3c 標準；歸一化最小和算法；TDMP；伸縮因子Abst

3、ractLDPC codes, also known as low density parity check codes, are a kind of channel coding, and they are directly determined by the parity check matrix. The length of the codes is generally longer, but they also show high decoding performance. Meanwhile LDPC codes have attracted much attention and b

4、ecome an another focus in channel coding filed after Turbo codes because of their error correction capability close to Shannon limit, and low decoding complexity and high decoding throughput. The paper implements a standard LDPC decoder based on IEEE802.15.3c.The decoder uses the normalized min sum

5、algorithm, the normalized factor is 0.75, with close to belief propagation Algorithm. According to the decoding algorithm, a quantization scheme based on the scaling factor, the decoding performance and floating point performance of the quantization scheme is applied to the normalized min sum algori

6、thm when compared to only a difference of 0.1dB.At the same time for the TDMP algorithm is proposed for termination algorithm double threshold iteration, iteration times can be saved, reducing hardware complexity.Several algorithms are proposed in this paper, research on the LDPC decoder has a certa

7、in reference value.Keywords: LDPC codes, IEEE802.15.3c standard, Normalized Min Sum,TDMP, extension factor目錄摘 要2第1章 緒論41.1 論文選題背景41.2 LDPC碼的提出、發(fā)展及現狀61.3 論文的研究意義71.4 論文結構及主要研究內容8第2章 低密度奇偶校驗碼92.2 LDPC碼的優(yōu)勢和性能分析132.3 LDPC碼的編碼構造142.4 LDPC碼校驗矩陣的構造152.5 本章小節(jié)16第3章 LDPC譯碼算法163.1 IEEE802.15.3c 標準定義的LDPC碼163.2

8、 LDPC碼的譯碼算法173.3 歸一化最小和算法243.4 本章小節(jié)25第4章 LDPC譯碼器的伸縮因子量化方案254.1 量化譯碼的研究264.2 提出的量化方案274.3 本章小節(jié)28第5章 LDPC譯碼器的迭代終止算法285.1 TDMP算法285.2 現有的迭代終止算法295.3 提出的雙閾值迭代終止算法295.4 本章小節(jié)31第6章 模塊設計與驗證316.1 置換網絡的設計316.2 仿真驗證結果33第7章 總結和展望367.1 總結377.2 展望37第1章 緒論 隨著數字通信技術的發(fā)展，現代社會對各種通信業(yè)務的需求增長迅猛，數字通信系統(tǒng)既要有高標準的傳輸質量，又要具備較大的傳輸

9、容量，這就對通信的可靠性和有效性提出了更高的要求。為保證通信傳輸的低差錯率，信道編碼已經成為通信系統(tǒng)中必不可少的關鍵技術。頻帶是通信系統(tǒng)寶貴而緊張的資源，在帶寬受限的環(huán)境下，通信的有效性顯得更加重要，優(yōu)良的信道譯碼不僅糾錯性能突出，而且傳輸碼率要高，以加強通信系統(tǒng)的可靠性和有效性。1.1 論文選題背景通信系統(tǒng)的基本目的在于將信息由信源高效、可靠，有時還需安全地傳送到信宿。有擾通信信道中的噪聲會不可避免地對傳輸信息產生不同程度的干擾，從而可能降低通信可靠性。所以通信系統(tǒng)設計的核心問題就是在存在隨機噪聲的信道中如何克服干擾，減小信息傳輸的差錯，同時又不降低信息傳輸的效率，即如何解決系統(tǒng)的有效性與可

10、靠性之間的矛盾。一般地，通信系統(tǒng)的可靠性用誤比特率（BER）來衡量，其有效性則用信息傳輸速率R比特/信道符號來衡量。早期的人們普遍認為1：通信系統(tǒng)的可靠性與有效性之間是一對不可調和的矛盾，一方的改善總是以犧牲另一方為代價，并指出當功率受限時，在有擾通信信道上實現任意小錯誤概率的信息傳輸的唯一途徑就是把信息傳輸速率降低至零。Shannon信息和編碼理論的奠基性論文“通信的數學理論”于 1948 年發(fā)表之后2，改變了這一觀點。根據Shannon的信息理論，數字通信系統(tǒng)的基本組成如圖1.1所示。信源信源編碼器信道編碼器數字調制器信道干擾信宿信源譯碼器信道譯碼器數字解調器 圖 1.1 數字通信系統(tǒng)的組

11、成Shannon的信息理論從通信系統(tǒng)的整體最佳化來研究信息的傳輸和處理。比特是一種通用的信息表示形式，它本身并不依賴于信源或信道特征。這就允許我們分別設計圖1.1 所示的兩個階段的信息處理，即信源編碼和信道編碼。Shannon不失最佳性地證明了這種分離性。圖1.1中信道編譯碼部分是以特定的控制手段，引入適量冗余比特，以克服信息在傳輸過程中受到的噪聲和干擾影響。根據Shannon提出的信道編碼定理【2】，對任意一個平穩(wěn)離散無記憶有噪聲信源，都有一個固定的量，稱之為信道容量，記做C。從信道編碼定理可知，在信息傳輸速率R不大于信道容量C的情況下，從碼組長度趨于無窮大的碼集合中隨機的選取編碼碼字，并且

12、在接收端譯碼采用最大似然譯碼算法時，譯碼錯誤率可趨于零。這種無差錯傳輸必須滿足以下3個基本條件：1.采用隨機性編譯碼。2.編碼長度L，即分組的碼組長度無限。3.譯碼過程采用最佳的最大似然譯碼方案。雖然該定理僅僅是一個存在性定理，沒有給出具體實現差錯控制編碼的方法，但卻從理論上給出了糾錯碼的理論極限，同時也指明了糾錯碼研究的方向和目標。幾十年來，無數的學者嘗試著構造能達到Shannon限而譯碼復雜度又低的編碼方案。1962年Gallagher首次提出了低密度奇偶校驗（Low-density Parity-check）碼【2】，簡稱LDPC碼，其糾錯性能優(yōu)異，但受到當時研究手段的限制，并沒有引起重

13、視。1993年Cabarrus等人提出Turbo碼，震驚了整個編碼界。學者研究發(fā)現Turbo碼實質上是一類特殊的LDPC碼，其接近香農極限的性能引發(fā)了學術界的研究熱潮。兩者都是基于圖構造的低密度碼，譯碼算法具有等價性，從而使兩者在基于圖模型的編譯碼研究中得到了統(tǒng)一。 1.2 LDPC碼的提出、發(fā)展及現狀1962 年，Gallager在他的博士論文中提出了二元正則LDPC碼，也被稱做Gal lager碼。Gallager證明了這類碼具有很好的漢明距離特性，是滿足GV限的漸進好碼，在計算樹上進行Ilog(log( N)（N為碼長）次后驗概率迭代譯碼可以獲得依碼字長度指數降低的比特錯誤概率，但限于當

14、時的計算能力，LDPC碼被認為不是實用碼，在很長一段時間內沒有受到人們的重視。 1981 年，Tanner在他的一篇奠基性的文章中正式提出了用圖模型來描述碼字的概念，從而將LDPC碼的校驗矩陣對應到被稱為Tanner圖的雙向二部圖上。采用Tanner圖構造的LDPC碼，通過并行譯碼可以顯著地降低譯碼復雜度。Tanner還仔細分析了最小和算法（Min-Sum Algorithm）與和積算法（Sum-Product Algorithm）兩種信息傳遞算法，證明了基于有限無環(huán)Tanner圖的最小和譯碼算法與和積譯碼算法的最優(yōu)性。但Tanner圖在實際當中是采用隨機圖構造的，其中不可避免地存在小環(huán)路現象

15、，這些小的環(huán)路會造成譯碼信息的重復傳遞，使譯碼過程中的消息之間不滿足獨立性假設，影響了迭代譯碼算法的收斂性。 Turbo碼的發(fā)現重新引發(fā)了眾多學者對LDPC碼的研究興趣。MacKay和Neal利用隨機構造的Tanner圖研究了LDPC碼的性能，發(fā)現采用和積譯碼算法的正則LDPC碼具有和Turbo碼相似的譯碼性能，在長碼時甚至超過了Turbo碼，這一結果引起了信道編碼界的極大關注。此后，Davey和MacKay從減少Tanner圖上小環(huán)路的概念出發(fā)提出了基于GF ( q ), q 2的LDPC碼，進一步提高了LDPC碼的譯碼性能。 在MacKay和Neal重新發(fā)現LDPC碼優(yōu)異性能的同時，Spe

16、llman和Sipper提出了基于二部擴展圖的擴展碼。在對擴展碼的研究中，他們證明了一個隨機構造的Tanner圖以很大的概率為好的擴展圖，而由好的擴展圖構造的線性糾錯碼是漸進好碼，從而證明了采用隨機Tanner圖構造的LDPC碼以很大概率是漸進好碼。Lusby等人將采用非正則Tanner圖構造的擴展圖用于刪除信道，稱之為Tornado碼。由于采用了非正則的Tanner圖，Tornado碼具有更大的擴展性和更好的收斂性，糾刪性能更強。此后，采用優(yōu)化度序列設計的非正則Tanner圖被用于構造LDPC碼，稱為非正則LDPC碼，與正則LDPC碼相比，非正則LDPC碼的性能得到顯著的提高。同時，Weis

17、berg結合Turbo碼和網格圖的研究，將Tanner 圖推廣到包含隱含狀態(tài)變量的因子圖（Factor Graph），對Turbo碼和LDPC碼的研究在因子圖的基礎上得到統(tǒng)一。Weisberg對因子圖的研究發(fā)現，對任意給定系統(tǒng)，無環(huán)圖的狀態(tài)復雜度是最大的，有環(huán)圖的狀態(tài)復雜度則會大大降低，從而證明了基于有環(huán)Tanner圖的LDPC碼具有較低的譯碼復雜度。Weisberg同時還證明了最小和算法和和積算法在本質上的同一性，在格圖譯碼中，最小和算法退化為Vitoria譯碼算法，和積算法退化為BCJR譯碼算法。 近兩年，Richardson等人應用密度進化理論來測度LDPC碼的性能。Richardson

18、等人在對LDPC碼的研究中發(fā)現，譯碼信息的迭代傳遞過程中存在著譯碼閾值現象，即當信噪比大于譯碼閾值時，迭代譯碼可使誤碼率趨于零，反之無論采用多長的LDPC碼，經過多少次迭代譯碼，總存在一定的錯誤概率。應用中心極限定理，Richardson等人證明了有限隨機有環(huán)圖的譯碼閾值可以逼近無環(huán)圖的譯碼閾值。通過建立在無環(huán)圖上的密度進化理論，可以精確地計算無環(huán)圖上LDPC碼的譯碼閾值，分析其譯碼收斂條件，從而近似估算有環(huán)Tanner圖上LDPC碼的性能。研究表明，譯碼閾值的大小與LDPC碼的構造參數密切相關，采用優(yōu)化度序列設計的非正則LDPC碼可以有效地改善閾值，因此密度進化理論可以用于指導LDPC碼的優(yōu)

19、化設計。 Chung等通過對密度進化理論的研究，進一步提出了應用高斯逼近原理來簡化譯碼閾值計算和收斂性分析，從而使測度LDPC碼性能的模型由多參數動態(tài)系統(tǒng)的密度進化理論模型簡化為單一參數動態(tài)系統(tǒng)的高斯逼近模型。1.3 論文的研究意義在通信系統(tǒng)的分析和設計中,特別重要的是信息傳輸所通過物理信道的特征,信道的特征一般會影響通信系統(tǒng)基本組成部分的設計。無論是在有線信道、無線信道還是在光纖信道等物理媒質中傳輸,信號將不可避免地受到加性熱噪聲、人為噪聲以及大氣噪聲等干擾。因此信道譯碼器輸出序列的誤碼率是衡量編碼器-譯碼器組合性能的一個重要量度。而低密度校驗碼(LDPC，Low-Density Parit

20、y-Check Codes)是一種能逼近Shannon容量限的漸進好碼，其長碼性能甚至超過了Turbo碼。由于低密度校驗碼具有譯碼復雜度低、錯誤平層低等諸多優(yōu)點，它在信息可靠傳輸中的良好應用前景已經引起學術界和IT業(yè)界的高度重視，成為當今信道編碼領域最受矚目的研究熱點之一。LDPC碼的提出改變了人們構造好碼的傳統(tǒng)觀念，同時LDPC碼迭代的思想也為解決不同通信領域的問題提供了新的思路。因此，LDPC碼作為譯碼界的重大突破，其研究意義是不言而喻的。目前，在國外許多大學和研究機構都在進行LDPC碼的研究。美國JPL實驗室、紐約州立大學、瑞典的Charmer大學、Lund大學以及澳大利亞的南澳大利亞大

21、學等都在LDPC碼研究領域取得了一系列的成果。此外，在ICC等許多通信和電子類的國際會議上，LDPC碼都被作為一個獨立的專題來討論。LDPC碼的研究已經得到了廣泛重視。另外，LDPC碼在實際系統(tǒng)中的成功應用也是促使LDPC碼研究深入進行的一個重要因素。目前，LDPC碼已經在深空通信、(移動)衛(wèi)星通信以及多媒體通信等領域得到了廣泛應用。但對于LDPC碼來說，在地面無線通信系統(tǒng)中的應用研究最富有挑戰(zhàn)性。無線信道是功率受限(便攜式用戶終端的能量供給有限)和帶寬受限的(用戶對業(yè)務需求的不斷增加使得帶寬資源匾乏)，同時衰落、陰影和多徑效應使得無線信道異常復雜；而且系統(tǒng)的實時性要求也比較高，這些因素都使L

22、DPC碼的應用受到嚴重挑戰(zhàn)。因此，開展LDPC碼關鍵技術及LDPC原理的應用研究，具有理論和實踐兩方面的意義。1.4 論文結構及主要研究內容本文致力于實現LDPC碼譯碼器的設計，以現有譯碼算法為基礎，以提高譯碼性能和降低譯碼復雜度為目標，研究出適合硬件實現的譯碼算法，并對譯碼算法的性能進行仿真。本文具體內容安排如下：第一章為緒論部分，主要介紹了課題的研究背景和研究意義、國內外的研究現狀、及論文主要研究的內容。第二章從LDPC碼的基本概念入手，詳細介紹LDPC碼的定義、性能優(yōu)勢和校驗矩陣的構造，并簡單介紹了 LDPC碼的編碼構造方法。第三章主要對LDPC碼的各種硬判決和軟判決譯碼算法進行了分析，

23、詳細比較了各個譯碼算法的復雜度和性能的差別，LDPC碼譯碼器的硬件設計確定一種復雜度和性能折中的算法方案。第四章主要介紹了本文所提出的量化方案。第五章主要介紹了TDMP算法和提出的雙閾值迭代終止算法。第六章主要是對所涉及的置換網絡進行了介紹和仿真。第七章為結論與展望部分，對全文所做的工作進行總結，并明確了下一步的研究方向。第2章 低密度奇偶校驗碼LDPC碼是可以由稀疏校驗矩陣定義的線性分組碼，它具有特別優(yōu)異的糾錯性能。本章首要介紹LDPC碼的基本原理和基本概念，之后再分別介紹了隨機型和準循環(huán)型LDPC碼的特點，闡述了AA-LDPC碼的優(yōu)勢和特點，介紹了LDPC碼譯碼算法，深入分析影響LDPC碼

24、譯碼性能的因素。2.1 LDPC碼2.1.1 LDPC碼的定義LDPC(Low一Density Parity一Cheek Codes)碼9，即低密度奇偶校驗碼，是一類特殊的線性分組碼，它通過一個生成距陣G將信息序列映射成發(fā)送序列，也就是碼字序列。對于生成距陣G，完個等效的存在一個奇偶校驗矩陣H，所有的碼字c都應該滿足校驗方程，即H*cT=0。其校驗矩陣H中絕大多數元素為0，只有少部分為1，即H是稀疏矩陣，如圖2-1（a）中的H矩陣。相對于行與列的長度(m,n)，校驗矩陣H每行、列中非零元素的數目(稱作行重、列重)非常少，即這種碼的校驗矩陣中包含多數的0而僅有少數的1，這也是LDPC碼之所以稱為

25、低密度碼的原因。LDPC碼是一種逼近香農限1的線性分組碼，它也通過一個生成矩陣G進行表示。矩陣Gkn是一個(n,k)的線性碼的生成矩陣，它由k個線性獨立的行矢量組成，可表示為G=pkr,IKK，其中下標r=n-k。I是一個kxk單位矩陣，其中k=7，n=14，如式(2.1)所示。G714= （2.1）除了用校驗矩陣和生成矩陣表示LDPC碼以外，還可以用二分圖(bipartite)表示LDPC碼。其中最常見的一種是Tanner圖7，他有Tanner提出，用于研究可迭代譯碼的LDPC碼的結構。Tanner圖可用頂點和邊的集合進行表示。對維數為mn的校驗矩陣，校驗矩陣的列可映射n個頂點，這些頂點記為

26、v1，v2，v3，vn，稱之為變量節(jié)點；校驗矩陣的行可映射為m個頂點，記為c1，c2，c3，cm，稱之為校驗節(jié)點。任意兩個變量節(jié)點之間不相連，任意兩個校驗節(jié)點之間不相連，只有在變量節(jié)點和校驗節(jié)點之間存在相連的邊。如果校驗矩陣的第i行和第j列元素是非零的，則在Tanner圖中，節(jié)點ci與vj之間有一條邊相連。與節(jié)點相連的邊數目稱為節(jié)點的度(degree)。從某個節(jié)點出發(fā)又回到此節(jié)點的閉合路徑稱之為一個環(huán)(cycle)，所經過邊的數量稱之為環(huán)的長度(length)。其中最短環(huán)的長度稱之為圖G的周長(girth)。由于校驗矩陣H的稀疏性以及構造時所使用的不同規(guī)則，使得不同LDPC碼的Tanner圖具

27、有不同的閉合環(huán)路分布。而Tanner圖中閉合環(huán)路是影響LDPC碼性能的重要因素，它使得LDPC碼在類似BP算法的一類迭代譯碼算法下，表現出完全不同的譯碼性能。在Tanner圖中不能包含長度很短的環(huán)，短環(huán)的存在限制了譯碼性能。圖2.1(a)展示了一種碼率為1/2的(8,4)LDPC碼，它有4行8列。H矩陣映射為Tanner圖，如圖2.1(b)所示。校驗矩陣的行和列可被映射為校驗節(jié)點(Cheek Node Unit,CNU)和變量節(jié)點（Variable Node Unit,VNU)，校驗節(jié)點和變量節(jié)點之間的連線標識了它們之間的信息交互關系。H= 圖 2.1(a) 碼率為1/2的(8,4)LDPC碼

28、 圖 2.1（b）（8,4）線性分組碼H矩陣的Tanner圖2.1.2 校驗矩陣的環(huán)在Tanner圖中，一個長為的環(huán)是一個能夠回到起點的包含個分支的閉合路徑。在圖2-1(b)中，粗實線表示的是一個長為4的環(huán)。圖的最小環(huán)長稱為圖的圍長(girth)。顯然，二分圖中可能的最短的環(huán)長為4，對應到H矩陣中就是H矩陣的一個子陣，其四個角都是1，如圖2.2所示。環(huán)(特別是短環(huán))會對譯碼性能產生負面影響。因為LDPC碼的譯碼采用迭代譯碼，其算法的推導是基于假設在節(jié)點間傳遞的信息統(tǒng)計獨立，當有環(huán)存在時，某一節(jié)點發(fā)出的信息經過一個環(huán)長的傳遞會被傳回本身，從而造成自身信息的疊加，破壞了獨立的假設，影響譯碼的準確性

29、。設計校驗矩陣時，應盡量減少短環(huán)對碼的性能影響。 圖 2.2 二分圖的最短環(huán)2.1.3 LDPC碼的分類 根據列重和行重的不同，LDPC碼主要分為兩類，即規(guī)則碼和非規(guī)則碼。所謂的規(guī)則碼是指所有行的行重都是相同，同時所有列的列重也相同。如圖2.3所表示的規(guī)則碼，其行重都為4，列重都為2。反之，則是非規(guī)則碼，如圖2.1中的LDPC碼。非規(guī)則碼在譯碼性能方面優(yōu)于規(guī)則碼。H1=圖2.3 規(guī)則碼的H1矩陣根據校驗矩陣的結構特點，可把LDPC碼分為隨機型和準循環(huán)型兩種。所謂隨機型就是指校驗矩陣中非零元素1的分布比較隨機，沒有規(guī)律性。隨機型的碼字一般通過計算搜索獲得，同時在搜索時限制條件，非常長的隨機型LD

30、PC碼的性能優(yōu)于有限幾何LDPC碼。圖2-1中H矩陣所表示的LDPC碼屬于隨機構造。雖然隨機構造的LDPC碼就有很好的譯碼性能，但由于其奇偶校驗矩陣缺乏結構性，對于較大的校驗矩陣的存取、數據的編碼和碼字性能的分析都造成了較大的困難。而當校驗矩陣具有結構化時可解決這些問題。準循環(huán)LDPC碼作為一類結構化的LDPC碼，可取得與隨機構造的LDPC碼相似的性能。根據準循環(huán)的特性，編碼器可通過移位寄存器實現。校驗矩陣的規(guī)則性有利于降低硬件復雜度并可實現高性能的譯碼器。圖2.4描述了一種QC-LDPC的H矩陣11。 圖 2.4 準循環(huán)碼的H矩陣2.2 LDPC碼的優(yōu)勢和性能分析2.2.1 LDPC碼的優(yōu)勢

31、LDPC碼的最大特點是性能接近著一名的Shannon信道編碼定理1中所指出信道容量(即香農限)，其糾錯性能具至超過了3G中應用的Turbo碼319。與Turbo碼相比，LDPC具有以下優(yōu)點：可以達到很高的碼率。LDPC碼可以達到0.7、0.8甚至0.9的碼率，而目前使用的Turbo碼的碼率大都是1/3。譯碼速率快。LDPC碼具備全并行譯碼結構，可以達到很高的譯碼速度。不可檢測錯誤少。由于LDPC碼碼字之間的碼距較大，使得它譯碼過程中出現不可檢測錯誤的概率很小。發(fā)生“地板效應”(error-floor)20的概率低。隨著信噪比的增加，Turbo碼誤碼率的下降趨勢將趨于平緩，即出現所謂的“地板效應

32、”。但是LDPC碼發(fā)生這種現象的概率低得多，這使得LDPC碼在深空通信或光纖通信中更具優(yōu)勢。LDPC碼可以采用基于硬判決的迭代算法，雖然性能比軟判決差，但實現復雜度很低。Turbo碼譯碼在迭代時必須傳遞軟信息，因此無法使用硬判決算法。由于校驗式的存在，使得LDPC碼的譯碼過程中能夠確定碼字是否正確，這樣不僅可以省掉CRC編碼，而且可以采用動態(tài)終止算法來減少迭代次數。2.2.2 LDPC碼的性能分析 LDPC碼譯碼性能的分析主要包括密度進化（Density Evolution）理論、高斯近似（Gaussian Approximation）和EXIT圖。Richardson等人基于Gallaghe

33、r的思想提出密度進化理論2，定義了BP算法的LDPC碼的容量，系統(tǒng)的建立了無環(huán)圖的BP譯碼的密度進化理論，分析LDPC碼的漸進性能，設計優(yōu)化碼的度數分布。密度進化不僅可應用于二進制差錯（BEC）信道21和加性高斯白噪聲信道（AWGN），還可擴展到碼間干擾（ISI）信道，并由分析二進制LDPC碼擴展到多進制LDPC碼。為提高密度進化的計算速度，Chung等人采用高斯近似方法17將迭代的多維問題轉化為一維問題，降低了計算復雜度?；诨バ畔⒂嬎愕耐庑畔⑥D移圖（EXIT圖）由Brink提出，用于分析并行迭代譯碼算法的收斂性，又可應用于LDPC碼編碼調制方案設計和譯碼算法的分析。并且基于EXIT圖方法分

34、析比密度進化法計算量小得多。2.3 LDPC碼的編碼構造從前面對LDPC碼基本原理的介紹，可以看出校驗矩陣H不僅決定了LDPC的編碼，而且在譯碼過程中也起著至關重要的作用。在同樣碼參數的LDPC碼集合中，不同結構的LDPC碼的性能有很大的不同，同時編譯碼的復雜度也有很大的區(qū)別，所以如何構造性能優(yōu)異、編譯碼簡便的LDPC碼一直是研究的一個熱點問題。目前根據構造方式的不同，校驗矩陣主要分為兩大類：隨機校驗矩陣和結構化校驗矩陣。Gallager、Mackay等都是用隨機方法構造LDPC碼的稀疏校驗矩陣4。用隨機法構造的LDPC碼22的碼字參數選擇靈活，但對于高碼率、中短長度的LDPC碼用隨機法進行構

35、造，要避免Tanner圖中的四線循環(huán)是很困難的，其沒有一定的碼結構，編碼復雜度高，并且Gallager和Mackay等定義的稀疏校驗矩陣5不是系統(tǒng)形式的，也不是循環(huán)形式的，因此編碼器非常復雜，不具有實用性。而結構化校驗矩陣一般可以通過代數幾何、組合24,25,30,31等方式生成，可以克服短循環(huán)的產生，具有確定的結構生成的LDPC碼是循環(huán)碼或準循環(huán)碼，可以實現線性時間編碼和簡單譯碼，硬件實現起來比隨機結構的碼容易，而且可以設計girth較大的碼，糾錯性能達到隨機校驗矩陣生成的碼。由于LDPC碼的編碼構造不是本文討論的重點，因此有關LDPC碼校驗矩陣具體的構造方法方面的內容這里就不多作描述，感興

36、趣的讀者可以參考相關文獻。2.4 LDPC碼校驗矩陣的構造碼的結構決定了LDPC碼的性能。不同結構的LDPC碼性能有很大不同，同時編譯碼復雜度也有很大區(qū)別，所以，如何構造出性能優(yōu)異、編譯碼簡便的LDPC碼一直是研究的一個熱點10。關于LDPC碼的構造方法很多，主要分為兩大類：隨機構造法和結構化構造法。LDPC碼校驗矩陣的隨機化構造方法包括：Gallager構造法、Mackay構造法、Davey構造法、比特填充及擴展的比特填充法、Girth 分布構造法、PEG方法等。結構化構造方法分為代數構造法和組合方法，代數結構法包括基于有限幾何和基于循環(huán)置換矩陣的方法。隨機構造的矩陣沒有確定的結構，糾錯性能

37、雖好，編碼復雜度大，譯碼存儲時復雜度高，不易于硬件實現。結構化校驗矩陣可以克服短循環(huán)的產生，具有特定的結構，生成的LDPC碼是循環(huán)碼或類循環(huán)碼11，編譯碼實現簡單，硬件實現起來也比隨機構造的碼容易，推動了LDPC碼的實用化。但是代數構造法對碼率和碼長的選擇不夠靈活，只能根據自身設計規(guī)則構造H矩陣，這種算法導致標準兼容問題，因此，如何結合隨機方法和代數方法構造結構更好并且實用高效的H矩陣仍是當前研究的重點。 其中QC-LDPC碼中使用比較廣泛的一種是AA-LDPC34。AA-LDPC碼可通過H矩陣分解并限制子校驗矩陣行和列“1”的個數與位置而生成,這種方法產生的LDPC碼可以獲得與隨機構造的LD

38、PC有相似的誤碼率。AA-LDPC碼校驗矩陣Hmxn可分解為M個子行(bloke rows)或者超碼(super code),每個子行又可分為N個子矩陣，分解后變?yōu)镸xN個S1X S2子校驗矩陣，其中MxS1=m，NxS2=n，S1和S2是碼字相互獨立的參數。這些分解后的子矩陣稱之為偽置換矩陣(pseudo permutation matrices)，這些偽置換矩陣滿足以下兩個條件：所有的行重不大于1；所有的列重不大于1；AA-LDPC碼的校驗矩陣如圖2-5中HAA所示。整個校驗矩陣被分解為3個，每個子行又可分為5個子矩陣，每個子矩陣的維數為S1=S2=5，這些子矩陣為零矩陣或者循環(huán)轉置單位矩

39、陣。AA-LDPC碼構造時，可首先構造基矩陣(Hbase)，然后再擴展基矩陣。為了簡化硬件實現，一般S1=S2=5，S為擴展因子，基矩陣中的零元素擴展為零矩陣,非零元素擴展為循環(huán)轉置單位矩陣。2.5 本章小節(jié)本章首先對LDPC碼的概念進行了詳細的介紹，并且說明了LDPC碼優(yōu)異的糾錯能力。在此基礎上，對LDPC碼的優(yōu)勢和性能做了較好的分析，還介紹了比較重的校驗矩陣的環(huán)的概念，同時還分析比較了LDPC碼的常用的幾種構造方法的優(yōu)缺點，分析了本文所用的AA-LDPC碼的特點。重要的是，為后面對基于IEEE802.15.3c標準定義232425的矩陣中LDPC碼的譯碼算法的研究奠定基礎。第3章 LDPC

40、譯碼算法3.1 IEEE802.15.3c 標準定義的LDPC碼IEEE802.15.3C 標準1314中定義的LDPC碼是一種結構化構造的非正則準循環(huán)碼。不規(guī)則的LDPC碼作為高性能的糾錯碼，它所支持的FEC碼率、信息塊的長度及代碼塊的長度見表1。在IEEE802.15.3C標準中，校驗矩陣H的定義如圖3.1所示：其中Pij，代表一個zz的標準置換矩陣或全零矩陣，z為大于或等于1的整數，滿足：n=znb，m=zmb，nb固定為21。Hb為一個nbmb的二進制基矩陣，其中，基距陣中的元素l表示一個zz的標準置換矩陣，元素0則表示一個zz的全零矩陣。將基矩陣Hb中的元素l用其表示的標準置換矩陣循

41、環(huán)移位的次數來代替，元素0用空白或一個符號(“-”)來代替，便得到一個與Hb大小相同的基本模型矩陣Hmb。由Hmb便可直接擴展得到一個mn的校驗矩陣H。本文所使用是IEEE802.15.3C 標準中碼長為672的三種碼率的矩陣，三種碼率分別為1/2、3/4、7/8的基本校驗矩陣，其中碼率為3/4的矩陣如表3.2所示。表3.2中基本模型矩陣中的“0”表示零矩陣，“1”表示單位陣，其它元素表示單位距陣循環(huán)左移的次數；其中每一個子矩陣為2121。 表3.1 碼率為3/4的矩陣 本論文所用的三種碼率LDPC的統(tǒng)計信息如下表3.3所示。 表3.2 LDPC碼的三種碼率 3.2 LDPC碼的譯碼算法信道編

42、碼的譯碼算法是決定其性能和應用前景的一個重要因素。線性分組碼的譯碼復雜度與碼長成指數關系，當碼長增大到一定程度后，復雜度的增加將是不可控制的。但LDPC碼由于其校驗矩陣的稀疏性，使得譯碼算法的復雜度和碼長成線性關系，克服了分組碼在碼長較長時所面臨的計算復雜度問題。Gallagher2在提出LDPC碼的同時給出了兩種迭代譯碼算法：硬判決和軟判決算法。前者計算復雜度很低，只需要模二和運算，但其譯碼性能不理想，后者雖然性能更好，但復雜度較大。對于硬判決算法，由于其譯碼性能不能滿足課題研究的需要，本章只做原理性介紹。軟判決譯碼算法本質是基于Tanner圖的消息傳遞MP(Message Passing)

43、算法26。1996年，Mackay和Neal提出了Bp(Belief propagation)算法13，也稱為Sum一Product算法，其譯碼性能比硬判決算法好的多，但譯碼復雜度較高。Log-BP算法8是BP算法的對數域形式，在一定程度上降低了譯碼復雜度。Fostoria對BP算法作了進一步研究，提出了BP-Based算法，降低了BP算法的復雜度，但造成了議碼性能的損失。為了改善BP-Based算法因為校驗節(jié)點上的簡化處理而造成的性能損失，J. chem.進一步提出改進算法：采用歸一化的近似最佳BP-Based算法(亦稱為歸一化最小和算法)27。本章將主要研究上面提到的幾種軟判決譯碼算法。3

44、.2.1 LDPC碼硬判決譯碼算法考慮二元輸入無記憶信道，令yi0，1為對應于第i個變量節(jié)點的接收值。硬判決譯碼的主要思想是翻轉最少的yi0，1使所有n-k個校驗方程滿足。當H是低密度時，這一過程最為簡單。因為每個校驗方程只涉及很少的比特，而每個比特也只涉及很少的校驗方程。LDPC碼最簡單的譯碼方法是比特翻轉法(Bit FliPPing)，它是一種硬判決算法。其譯碼的主要原理是：如果發(fā)生錯誤，校驗方程不滿足，根據接收信息的有關規(guī)則，改變一些比特的值(0/1)，然后判斷是否滿足校驗方程，如果滿足校驗方程，則譯碼輸出，否則繼續(xù)迭代，或者已達到最大迭代次數則被迫停止譯碼，給出譯碼輸出21。BF譯碼操

45、作簡單，硬件很容易實現，但性能要差于軟判決的概率譯碼。BF譯碼算法的流程如3.4圖所示。 初始化，迭代次數i=1對做yn硬判決得到V0i是否大于max輸出碼子Vi-1Ck=H* (Vi-1)T結束譯碼翻轉en最大部分的變量節(jié)點得到碼子ViH* (Vi-1)T=0?輸出碼子Vi-1i=i+1結束譯碼否是否是 圖3.4 BF譯碼算法的流程這種算法只有模二和運算和比較大小的運算，因此譯碼速度較快。并且具有迭代結構，硬件實現比較簡單。但是譯碼性能較差，因為每次迭代譯碼選擇en最大的變量節(jié)點翻轉，若同時有好幾個這種節(jié)點，就可能使迭代進入一個循環(huán)，不能正確譯碼。3.2.2 LDPC碼軟判決譯碼算法LDPC

46、碼的軟判決譯碼算法具有逼近Shannon限的性能1，同時具有可以并行實現的特性。利用Tanner圖可以形象地說明LDPC碼的軟判決譯碼算法，如圖3.4所示。 圖3.5 LDPC碼的軟判決譯碼算法的Tanner圖LDPC譯碼算法是一個循環(huán)迭代過程，在迭代過程中，變量節(jié)點和校驗節(jié)點進行相互的信息交換，隨著迭代次數的增加，誤碼率越來越低。為表述方便,定義以下變量，其中b0,1。R(i)C,V(b) 表示在第i次迭代中校驗節(jié)點c向變量節(jié)點v傳遞的信息；L(i)C,V 表示在對數域內,在第i次迭代中校驗節(jié)點c向變量節(jié)點v傳遞的信息；q(i)v,c(b) 表示在第i次迭代中變量節(jié)點v向校驗節(jié)點c傳遞的信息

47、；Lq(i)v,c 表示在對數域內,在第i次迭代中變量節(jié)點v向校驗節(jié)點c傳遞的信息；q(i)v 表示在第i次迭代后變量節(jié)點v的后驗概率；Lq(i)v 表示在對數域內,在第i次迭代后變量節(jié)點v的后驗概率；S(i)c,v 表示在第i次迭代中校驗節(jié)點c向變量節(jié)點v傳遞的信息的符號位；Lq(i)v,c 表示在第i次迭代中變量節(jié)點v傳遞到校驗節(jié)點c的信息；M(v) 表示與變量節(jié)點v連接的所有校驗節(jié)點集合；M(v)c 表示與變量節(jié)點v連接的所有校驗節(jié)點中除了校驗節(jié)點c的集合；N(c ) 表示與校驗節(jié)點c連接的所有變量節(jié)點集合；N(c)v 表示與校驗節(jié)點c連接的所有變量節(jié)點中除了變量節(jié)點V的集合；3.2.2

48、.1置信傳播算法(BP) BP算法由Gallagher1提出，他在其博士論文中證明了：一組相互獨立的二進制序列“u=u0，u1，un-1，uj0,1，令pj=pr（uj=1）表示uj=1的概率，則此序列中“1”的個數為偶數的概率為： +此序列中“1”的個數為奇數的概率為： + BP譯碼算法的流程如3.6所示： 初始化，對q(0)v,c進行賦值迭代次數i=1i是否為最大值更新校驗節(jié)點計算R(i)C,V計算q(i)v更新校驗節(jié)點計算q(i)v,c根據q(i)v進行硬判決得到碼子ViH* (Vk-1)T=0?輸出碼子Vi-1i=i+1譯碼結束輸出碼子Vi-1譯碼結束是否是否 圖 3.6 BP算法的流

49、程圖3.2.2.2LLR BP算法 概率BP譯碼算法的缺點是譯碼過程中存在大量的乘法運算，具有較高的復雜度。如果將這些大量的乘法運算變?yōu)榧臃ㄟ\算，那么，運算的時間就會大大減少，這種方法可以通過將譯碼算法轉化到對數域中進行來實現，這就是對數似然比BP算法，也就是LLR BP譯碼算法。在對數域中進行的譯碼有兩個好處：首先，它通過將概率域中的乘法運算轉化為對數域中的加法運算，可以減少運算的時間；其次，它去掉了系數歸一化這一步，增強了計算的穩(wěn)定性。 LLR BP算法可以總結為如下幾步：1.初始化 在初始化步驟中，首先計算信道傳給變量節(jié)點的初始概率似然比信息Lr(i)v，其中，i=0，1，2，n。令從變

50、量節(jié)點傳向校驗節(jié)點的初始消息用下式表示：Lq(0)v,c = Lr(0)v 2.迭代處理 LLR BP算法的迭代處理主要包括校驗節(jié)點信息的處理、變量節(jié)點信息的處理以及譯碼判決。 校驗節(jié)點信息處理 在第1次迭代時，從變量節(jié)點v傳給通過邊與其相連的校驗節(jié)點c的信息可以用式（3.38）計算 q(i)v = Lv + 變量節(jié)點消息處理 在第1次迭代時，進行完校驗節(jié)點的更新后，校驗節(jié)點c就會把更新后的信息通過邊傳給與其相連的變量v，計算式為 Lq(i)v,c = 譯碼判決 當進行完兩種節(jié)點的更新后，就可以對變量節(jié)點進行硬判決，判決式為： 如果Lr(i)v0，那么cv=0；否則cv=1。 3.譯碼停止 當

51、HcT=0或者已經達到最大迭代次數時，就停止迭代；否則的話，就從步驟繼續(xù)迭代，直到正確譯碼。3.2.2.3 Min-Sum BP-Based 算法 至此，我們可以看到，通過對數域的換算，我們將大量的實數乘法運算轉化為加法，大大降低了譯碼算法的復雜度和硬件實現的難度。M. P. C. Fostoria等將Weinberg11的最小和算法應用于LDPC碼，形成了最小和算法。由于最小和算法中只有比較運算和加法運算，沒有乘法運算，硬件復雜度顯著降低。在譯碼過程中，變量節(jié)點初始化為信道信息，校驗節(jié)點初始化為零。如式所示： 最小和譯碼算法的迭代過程包括兩部分： 校驗節(jié)點的更新信息： 變量節(jié)點的更新信息：

52、3.3 歸一化最小和算法 在上述的介紹中，可以看出 Min-Sum BP-Based 算法15相對于 BP 算法和 LLR BP 算法復雜度最低。但是在該算法計算過程中，對變量節(jié)點信息進行了估計，相對于 LLR BP 算法在數值上采用了近似處理。即在輸入相同校驗信息的條件下，兩種算法輸出相同的信息符號，但 Min-Sum BP-Based 算法得出的信息符號幅度要大于 LLR BP 算法譯碼輸出的信號幅度。因此在算法過程中，為了進一步提高算法的性能，需要對于 Min-Sum BP-Based 算法進行修正，使其性能更接近 LLR BP 算法。其中 Jing hu Chen 等212213提出了

53、基于 Min-Sum BP-Based 的兩種改進算法，分別為歸一化最小和算法（Normalized Min-Sum）算法和偏移量最小和算法（Offset Min-Sum）算法。 Normalized Min-Sum 算法對 Min-Sum BP-Based 算法的改進之處在于在公式(3-27)的基礎上乘上了一個小于 1 的縮小因子以來修正幅度的偏移。具體公式如下： 結合以上各種算法比較，可以看出不同算法各有優(yōu)缺點。但是對于更適合硬件實現來說，后面的 Min-Sum 算法及其改進算法更合適。即在譯碼性能上沒有多少的損失，又在算法的實現上降低了復雜度，更合適與并行執(zhí)行，提高了譯碼速度和效率。因此

54、本文采用了Normalized Min-Sum 譯碼算法。在C中進行算法及參數仿真，確定實現中需要的參數值。 3.4 本章小節(jié) 本章首先對基于IEEE802.15.3c標準13定義的LDPC碼進行了詳細的介紹，這一標準是本文的核心。然后對譯碼算法中的硬判決算法和軟判決算法分別進行了介紹，并對其性能進行了分析。同時，詳細介紹了LDPC碼譯碼算法的原理，對常用的譯碼算法進行對比研究。并且對這幾種譯碼算法的計算復雜度做了定量分析，從譯碼性能和硬件實現復雜度兩方面考慮，確定采用歸一化最小和算法實現LDPC碼的譯碼設計。第4章 LDPC譯碼器的伸縮因子量化方案本章根據歸一化最小和譯碼算法的特點，通過計算機仿真及理論分析研究了量化范圍、量化級數、量化方式對譯碼性能產生的影響，并確定適合硬件實現的量化方案。4.1 量化譯碼的研究量化是在數字系統(tǒng)中必須的一個環(huán)節(jié)40。在LDPC譯碼器所處的通信系統(tǒng)中，噪聲值是連續(xù)的，來自信道的譯碼信息是連續(xù)值，而譯碼器完全由數字系統(tǒng)構成,，為了實現數字系統(tǒng)高效性、準確性、可預見性等特點