摘要第I頁(yè)高吞吐量LDPC碼編碼構(gòu)造及其FPGA實(shí)現(xiàn)摘要低密度校驗(yàn)碼（LDPC，LOWDENSITYPARITYCHECKCODE）是一種性能接近香農(nóng)極限的信道編碼，已被廣泛地采用到各種無(wú)線通信領(lǐng)域標(biāo)準(zhǔn)中，包括我國(guó)的數(shù)字電視地面?zhèn)鬏敇?biāo)準(zhǔn)、歐洲第二代衛(wèi)星數(shù)字視頻廣播標(biāo)準(zhǔn)（DVBS2,DIGITALVIDEOBROADCASTINGSATELLITE2）、IEEE80211N、IEEE80216E等。它是3G乃至將來(lái)4G通信系統(tǒng)中的核心技術(shù)之一。當(dāng)今LDPC碼構(gòu)造的主流方向有兩個(gè)，分別是結(jié)合準(zhǔn)循環(huán)（QC,QUASICYCLIC）移位結(jié)構(gòu)的單次擴(kuò)展構(gòu)造和類似重復(fù)累積（RA,REPEATACCUMULATE）碼構(gòu)造。相應(yīng)地，主要的LDPC碼編碼算法有基于生成矩陣的算法和基于迭代譯碼的算法?；谏删仃嚨木幋a算法吞吐量高，但是需要較多的寄存器和ROM資源；基于迭代譯碼的編碼算法實(shí)現(xiàn)簡(jiǎn)單，但是吞吐量不高，且不容易構(gòu)造高性能的好碼。本文在研究了上述幾種碼構(gòu)造和編碼算法之后，結(jié)合編譯碼器綜合實(shí)現(xiàn)的復(fù)雜度考慮，提出了一種切實(shí)可行的基于二次擴(kuò)展（DEX,DUPLEXEXPANSION）的QCLDPC碼構(gòu)造方法，以實(shí)現(xiàn)高吞吐量的LDPC碼收發(fā)端；并且充分利用該類碼校驗(yàn)矩陣準(zhǔn)循環(huán)移位結(jié)構(gòu)的特點(diǎn)，結(jié)合RU算法，提出了一種新編碼器的設(shè)計(jì)方案?；诙螖U(kuò)展的QCLDPC碼構(gòu)造方法，是通過(guò)對(duì)母矩陣先后進(jìn)行亂序擴(kuò)展（PEX，PERMUTATIONEXPANSION）和循環(huán)移位擴(kuò)展（CSEX，CYCLICSHIFTEXPANSION）實(shí)現(xiàn)的。在此基礎(chǔ)上，為了實(shí)現(xiàn)可變碼長(zhǎng)、可變碼率，一般編譯碼器需同時(shí)支持多個(gè)亂序擴(kuò)展和循環(huán)移位擴(kuò)展的擴(kuò)展因子。本文所述二次擴(kuò)展構(gòu)造方法的特點(diǎn)在于，固定循環(huán)移位擴(kuò)展的擴(kuò)展因子大小不變，支持多個(gè)亂序擴(kuò)展的擴(kuò)展因子，使得譯碼器結(jié)構(gòu)得以精簡(jiǎn)；構(gòu)造得到的碼字具有近似規(guī)則碼的結(jié)構(gòu)，便于硬件實(shí)現(xiàn)；（偽）隨機(jī)生成的循環(huán)移位系數(shù)能夠提高碼字的誤碼性能，是對(duì)硬件實(shí)現(xiàn)和誤碼性能的一種折中。摘要第II頁(yè)新編碼器在很大程度上考慮了資源的復(fù)用，使得實(shí)現(xiàn)復(fù)雜度近似與碼長(zhǎng)成正比?？紤]到吞吐量的要求，新編碼器結(jié)構(gòu)完全拋棄了RU算法中串行的前向替換（FS,FORWARDSUBSTITUTION）模塊，同時(shí)簡(jiǎn)化了流水線結(jié)構(gòu)，由原先RU算法的6級(jí)降低為4級(jí)；為了縮短編碼延時(shí)，設(shè)計(jì)時(shí)安排每一級(jí)流水線計(jì)算所需的時(shí)鐘數(shù)大致相同。這種碼字構(gòu)造和編碼聯(lián)合設(shè)計(jì)方案具有以下優(yōu)勢(shì)相比RU算法，新方案對(duì)可變碼長(zhǎng)、可變碼率的支持更靈活，吞吐量也更大；相比基于生成矩陣的編碼算法，新方案節(jié)省了50以上的寄存器和ROM資源，單位資源下的吞吐量更大；相比類似重復(fù)累積碼結(jié)構(gòu)的基于迭代譯碼的編碼算法，新方案使高性能LDPC碼的構(gòu)造更為方便。以上結(jié)果都在XILINXVIRTEXIIPRO70FPGA上得到驗(yàn)證。通過(guò)在實(shí)驗(yàn)板上實(shí)測(cè)表明，上述基于二次擴(kuò)展的QCLDPC碼構(gòu)造和相應(yīng)的編碼方案能夠?qū)崿F(xiàn)高吞吐量LDPC碼收發(fā)端，在實(shí)際應(yīng)用中具有很高的價(jià)值。目前，LDPC碼正向著非規(guī)則、自適應(yīng)、信源信道及調(diào)制聯(lián)合編碼方向發(fā)展?？鐚勇?lián)合編碼的構(gòu)造方法，及其對(duì)應(yīng)的編碼算法，也必將成為信道編碼理論未來(lái)的研究重點(diǎn)。關(guān)鍵詞低密度校驗(yàn)碼，重復(fù)累積碼，編碼器，現(xiàn)場(chǎng)可編程門(mén)陣列ABSTRACT第III頁(yè)CODECONSTRUCTIONANDENCODERIMPLEMENTATIONOFHIGHPAYLOADLOWDENSITYPARITYCHECKCODEABSTRACTLDPCCODESPERFORMCLOSETOTHESHANNONLIMITITHASBEENWIDELYADOPTEDBYSTANDARDSINTHEFIELDOFWIRELESSCOMMUNICATION,INCLUDINGDVBTH,DVBS2,IEEE80211NANDIEEE80216ELDPCCODESHAVEBECOMEONEOFTHEKEYTECHNOLOGIESIN3GANDEVENTHENEXTGENERATIONCOMMUNICATIONNETWORKTODAY,THEREARETWOPOPULARWAYSOFCONSTRUCTINGLDPCCODES,NAMELYSINGLEEXPANSIONCODECONSTRUCTIONANDREPEATACCUMULATELIKECODECONSTRUCTION,BOTHOFWHICHTAKEADVANTAGEOFTHEQUASICYCLICSTRUCTURECORRESPONDINGTOTHETWOKINDSOFLDPCCODES,TWOPOPULARENCODINGALGORITHMSAPPLY,NAMELYALGORITHMBASEDONGENERATIONMATRIXANDALGORITHMBASEDONITERATIVEDECODINGTHEALGORITHMBASEDONGENERATIONMATRIXCANACHIEVEAHIGHPAYLOAD,WHILEITCONSUMESLOTSOFREGISTERSANDROMTHEALGORITHMBASEDONITERATIVEDECODINGCANBEEASILYIMPLEMENTED,WHILELDPCCODESWITHRELATIVELYHIGHPERFORMANCEAREHARDTOCONSTRUCTAFTERADETAILANALYSISOFTHEABOVECONSTRUCTIONMETHODSANDENCODINGALGORITHMS,WITHCONSIDERATIONTOTHECODECCOMPLEXITY,AFLEXIBLECONSTRUCTIONMETHODCALLEDDUPLEXEXPANSIONISPROPOSEDTOACHIEVEAHIGHPAYLOADTAKINGADVANTAGEOFTHEQUASICYCLICSTRUCTUREOFTHESPARSEHMATRIX,ANEWENCODERALGORITHMISALSOPRESENTEDDUPLEXEXPANSIONCODECONSTRUCTIONISUSUALLYREALIZEDTHROUGHAABSTRACT第IV頁(yè)P(yáng)ERMULATIONEXPANSIONONMOTHERMATRIXFOLLOWEDBYACYCLICSHIFTEXPANSIONONBASEMATRIXFORFLEXIBLECODERATEANDCODELENGTH,MULTIPLEPERMULATIONEXPANSIONFACTORSPEXANDCYCLICSHIFTEXPANSIONFACTORSCSEXSHALLBESUPPORTEDBYCODECTHEFEATURESOFDUPLEXEXPANSIONCODECONSTRUCTIONILLUSTRATEDINTHISARTICLELIEINFIXEDCSEXFACTORANDFLEXIBLEPEXFACTORS,FACILITATINGDECODERIMPLEMENTATIONAPPROXIMATEREGULARLDPCCODE,MAKINGCODECCOMPLEXITYLOWPSEUDORANDOMCHOSENPEXFACTORS,IMPROVINGPERFORMANCETHUS,THISSPECIFICDUPLEXEXPANSIONCODECONSTRUCTIONACHIEVESAGOODTRADEOFFBETWEENHARDWARECOMPLEXITYANDPERFORMANCETHENEWENCODINGALGORITHMHASENABLEDRESOURCESHARINGWHEREVERPOSSIBLE,WHICHMAKESTHEENCODERCOMPLEXITYINLINEARPROPORTIONTOTHECODELENGTHFULLYCONSIDERINGAHIGHPAYLOAD,THEFORWARDSUBSTITUTIONINRUALGORITHMISREMOVEDMEANWHILE,THENUMBEROFPIPELINESTAGESHASBEENREDUCEDFROM6TO4INORDERTOREDUCETHEENCODINGLATENCY,ALLPIPELINESAREDESIGNEDTOCONSUMEAPPROXIMATELYTHESAMENUMBEROFCLOCKSCOMPAREDTORUALGORITHM,THISPROPOSEDSCHEMEISMOREFLEXIBLETOSUPPORTMULTIPLECODERATESANDCODELENGTHSWITHMUCHHIGHERPAYLOADCOMPAREDTOTHEALGORITHMBASEDONGENERATIONMATRIX,ITCONSUMESMUCHLOWERREGISTERANDROMRESOURCES,THUSACHIEVESAHIGHERPAYLOADPERUNITRESOURCECOMPAREDTOTHEALGORITHMBASEDONREPEATACCUMULATESTRUCTUREANDITERATIVEDECODINGALGORITHM,ITISMUCHEASIERTOCONSTRUCTTHECODESWITHHIGHPERFORMANCEALLTHERESULTSHAVEBEENPROVENBYXILINXVERTEXIIPRO70FPGAUPONBOARDLEVELTESTING,RESULTSSHOWTHATTHEABOVEDUPLEXEXPANSIONCODECONSTRUCTIONANDENCODERDESIGNOFLDPCCODECANACHIEVEAHIGHPAYLOADWITHRATHERLOWRESOURCESITENJOYSAFAIRLYHIGHMERITINPRACTICALAPPLICATIONNOWADAYS,IRREGULAR,FLEXIBLEANDJOINTSOURCECHANNELMODULATIONLDPCCODEDESIGNHASBECOMETHEFOCUSOFFUTURERESEARCHANDTHECONSTRUCTIONMETHODOFJOINTSOURCECHANNELMODULATIONCODEANDITSCORRESPONDINGENCODINGALGORITHMWILLCONTINUETOBESTUDIEDINDETAILKEYWORDSLDPC,REPEATACCUMULATE,ENCODER,FPGA上海交通大學(xué)學(xué)位論文原創(chuàng)性聲明本人鄭重聲明所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下，獨(dú)立進(jìn)行研究工作所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫(xiě)過(guò)的作品成果。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本人完全意識(shí)到本聲明的法律結(jié)果由本人承擔(dān)。學(xué)位論文作者簽名日期年月日上海交通大學(xué)學(xué)位論文版權(quán)使用授權(quán)書(shū)本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國(guó)家有關(guān)部門(mén)或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)上海交通大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。保密，在年解密后適用本授權(quán)書(shū)。本學(xué)位論文屬于不保密。（請(qǐng)?jiān)谝陨戏娇騼?nèi)打“”）學(xué)位論文作者簽名指導(dǎo)教師簽名日期年月日日期年月日第一章緒論第1頁(yè)第一章緒論伴隨著集成電路的飛速發(fā)展，以及摩爾定律的延續(xù)，上世紀(jì)90年代初，信道編碼迭代譯碼的方法再一次受到人們廣泛的關(guān)注。隨著TURBO碼12、TURBO乘積碼3（TPC,TURBOPRODUCTCODE）的橫空出世，以及LDPC碼的重新發(fā)現(xiàn)，香農(nóng)極限不再是遙不可及的，人們把信道編碼向著極限推進(jìn)了一大步。本章將從信道編碼基本理論開(kāi)始，簡(jiǎn)述信道編碼的概念，從而引出本文的重點(diǎn)LDPC碼，并對(duì)其基本概念、發(fā)展情況以及應(yīng)用前景作簡(jiǎn)要介紹。11信道編碼基本理論現(xiàn)實(shí)生活中，信息的傳遞難免受到信道的干擾，特別是無(wú)線通信系統(tǒng)中，信道的不確定性導(dǎo)致了接收端接收信號(hào)質(zhì)量的下降，信道編碼存在的目的就是盡量減少接收端錯(cuò)誤接收的信息比例，從而做到信息的可靠傳輸。信道編碼的容錯(cuò)能力，是通過(guò)在傳輸碼字中增加冗余實(shí)現(xiàn)的。冗余的作用是加大有效碼字之間的距離，這樣接收端就能把有效碼字和無(wú)效碼字區(qū)分開(kāi)來(lái)。最佳的接收方法是最大似然的譯碼方法，在收到當(dāng)前碼字后，通過(guò)統(tǒng)計(jì)所有有效碼字發(fā)送的可能性，將可能性最大的那個(gè)有效碼字判為接收到的正確信息。一般認(rèn)為，有效碼字集合中任意兩個(gè)碼的距離越大，則這個(gè)碼的性能越好。在幾種特殊類型的碼中間，這種距離是可以衡量的。例如線形分組碼就能用最小碼距DMIN來(lái)衡量其優(yōu)劣，同樣地，卷積碼的優(yōu)劣就能用自由距離DFREE來(lái)衡量。然而，最大似然的譯碼方法，在實(shí)際中卻是難以實(shí)現(xiàn)的。它的求取一般涉及遍歷整個(gè)有效碼字空間的操作，現(xiàn)實(shí)中僅可能對(duì)短碼長(zhǎng)的碼采用，其余情況下采用的都是一些次最優(yōu)的，計(jì)算較為簡(jiǎn)單的算法，以降低譯碼復(fù)雜度，然而這樣會(huì)犧牲一定的誤碼性能。這些簡(jiǎn)化的譯碼算法，并非很多時(shí)候都和最大似然算法保持著相當(dāng)?shù)男阅懿罹?，迭代譯碼方法的出現(xiàn)使得人們找到了一種次最優(yōu)的譯碼算法，隨著硬件技術(shù)的發(fā)展，這一算法在今天終于成為了現(xiàn)實(shí)，而它最成功的應(yīng)用當(dāng)屬LDPC碼。第一章緒論第2頁(yè)12LDPC碼簡(jiǎn)介L(zhǎng)DPC碼是低密度校驗(yàn)碼（LOWDENSITYPARITYCHECKCODE）的簡(jiǎn)稱，最早由RGGALLAGER45在1962年提出，當(dāng)時(shí)由于硬件技術(shù)的限制，其重要性沒(méi)有為人們所廣泛認(rèn)識(shí)。直到上世紀(jì)90年代前，學(xué)術(shù)界只有為數(shù)不多的學(xué)者發(fā)表了相關(guān)的論文，這些人包括MARGULIS6、TANNER7以及ZYABLOV和PINSKE8等。隨著迭代譯碼方法在TURBO碼上的成功應(yīng)用，MACKAY910、NEAL10和WIBERG11又分別重新發(fā)現(xiàn)了LDPC碼。LDPC碼是一種線性分組碼，顧名思義，校驗(yàn)矩陣的稀疏性是它的特點(diǎn)所在。LDPC碼最先使用了循環(huán)迭代的方法進(jìn)行譯碼，使現(xiàn)實(shí)可行的譯碼算法在性能上迅速逼近最佳算法，使信道編碼技術(shù)向香農(nóng)極限又邁進(jìn)了一步。根據(jù)校驗(yàn)矩陣的某些特征，可以對(duì)LDPC碼進(jìn)行分類。如果校驗(yàn)矩陣是由一系列循環(huán)移位方陣拼接而成的，則稱之為準(zhǔn)循環(huán)移位LDPC（QCLDPC）碼；如果校驗(yàn)矩陣右邊的方陣僅有主對(duì)角線和一條次對(duì)角線上的元素非零，則稱之為重復(fù)累積（RA）碼；如果校驗(yàn)矩陣所有的行重和列重相同，則稱之為規(guī)則碼，反之，則稱之為非規(guī)則碼。規(guī)則碼有其相應(yīng)的表示方法，一般記作N,DV,DC，其中N表示碼長(zhǎng)，DC表示行重，DV表示列重。這里給出了一個(gè)12,3,6規(guī)則LDPC碼的校驗(yàn)矩陣，如圖11所示。011101000011110101010100101010001011110010111000000100111110001011100101H圖11一個(gè)12,3,6規(guī)則LDPC碼的校驗(yàn)矩陣FIG11ANHMATRIXEXAMPLEOFA12,3,6REGULARLDPCCODE13LDPC碼的發(fā)展概況自從上世紀(jì)90年代LDPC碼被重新發(fā)現(xiàn)以來(lái)，學(xué)術(shù)界對(duì)它的研究就遍地開(kāi)花，一直如火如荼的進(jìn)行著。在誤碼性能方面，SHOKROLLARI、SPIELMAN、LUBY、MITZENMACHER和STEMANN等人研究了二進(jìn)制擦除信道（BEC,BINARYERASURECHANNEL）和二進(jìn)制對(duì)稱信道（BSC,BINARYSYMMETRICCHANNEL）下LDPC碼的誤碼性能，并證明了在BEC信道下，隨著碼長(zhǎng)的增第一章緒論第3頁(yè)長(zhǎng)，利用置信傳播算法（BPA,BELIEFPROPORGATIONALGORITHM）1213譯碼的LDPC碼的性能將逼近香農(nóng)極限。URBANKE和RICHARDSON等人用密度演化（DE,DENSITYEVOLUTION）的方法研究了LDPC碼結(jié)合置信傳播譯碼算法在其它信道下的誤碼性能，指出LDPC碼在其它很多信道中的傳輸速率都能趨近于信道容量。文獻(xiàn)14對(duì)瑞利衰落信道中的LDPC碼進(jìn)行了性能分析，并且提出了相應(yīng)的構(gòu)造方法，得到了一種誤碼性能優(yōu)于TURBO碼的LDPC碼。文獻(xiàn)1516結(jié)合了LDPC碼與OFDM兩種先進(jìn)技術(shù)，提出了一種在MPSK調(diào)制下的OFDM系統(tǒng)中LDPC碼的譯碼算法，并給出了性能分析。在碼字構(gòu)造方面，人們從LDPC碼的最小碼距著手，通過(guò)有限幾何的方法得到了一些性能相當(dāng)接近香農(nóng)極限的LDPC碼17181920，文獻(xiàn)21從譯碼角度出發(fā)，結(jié)合譯碼器硬件結(jié)構(gòu)，提出了一種碼構(gòu)造的方法。為了編碼器實(shí)現(xiàn)方便，HUIJIN，DIVSALAR以及MCELIECE等人提出了RA22碼，這種碼的特點(diǎn)在于編碼直接，非常適合低傳輸速率場(chǎng)合。伴隨著RA碼的出現(xiàn)，一系列類RA碼23迅速涌現(xiàn)，它們無(wú)不有著編碼器設(shè)計(jì)簡(jiǎn)單的優(yōu)點(diǎn)，為L(zhǎng)DPC碼構(gòu)造的發(fā)展提供了另一個(gè)方向。在編碼方面，RICHARDSON和URBANKE最先提出了將校驗(yàn)矩陣下三角化的想法24，以使編碼復(fù)雜度降低到與碼長(zhǎng)近似成正比的程度。沿著這個(gè)角度出發(fā)，文獻(xiàn)25在構(gòu)造時(shí)就將校驗(yàn)矩陣設(shè)計(jì)成下三角形式，但是這樣做減少了校驗(yàn)矩陣的隨機(jī)性，勢(shì)必會(huì)影響誤碼性能的提升。之后HUIJIN，DIVSALAR等人從碼字構(gòu)造方面開(kāi)創(chuàng)了簡(jiǎn)單編碼器的架構(gòu)22，為人們實(shí)際尋找更簡(jiǎn)單的編碼方法開(kāi)辟了蹊徑。隨著準(zhǔn)循環(huán)移位結(jié)構(gòu)日漸成為L(zhǎng)DPC碼的主流，ZONGWANG,LI和SHU，LIN等人提出了基于生成矩陣的編碼算法26，作為QCLDPC碼編碼的普適算法有著舉足輕重的地位。最近SHAQFEH和GOERTZ又提出了基于迭代譯碼的編碼算法27，對(duì)于某些特殊的校驗(yàn)矩陣而言，編碼算法可以變得和RA碼一樣簡(jiǎn)單。在譯碼方面，置信傳播算法一直占據(jù)著主流的地位。但是由于其復(fù)雜度仍然較高，因此一系列簡(jiǎn)化算法應(yīng)運(yùn)而出，其中包括最小和算法、改進(jìn)的最小和算法和分層的改進(jìn)最小和算法等。結(jié)合不同信道和調(diào)制方式，一些更簡(jiǎn)單的迭代算法也有著應(yīng)用空間，比如一些硬判決、軟判決相結(jié)合的譯碼算法2829。隨著分層迭代譯碼思想的出現(xiàn)，LDPC碼譯碼器的吞吐量得以提升。文獻(xiàn)30實(shí)現(xiàn)了最大凈吞吐量1GBPS的譯碼器，當(dāng)然它是建立在硬件全并行的基礎(chǔ)上的，H矩陣的每一行和每一列都被固定成一個(gè)硬件處理單元，將置信傳播算法直接映射到了硬件上。文獻(xiàn)31對(duì)TURBO碼和LDPC碼的譯碼復(fù)雜度進(jìn)行了比較，指出LDPC碼譯碼器實(shí)現(xiàn)起來(lái)更簡(jiǎn)單。文獻(xiàn)32對(duì)LDPC碼譯碼器的定點(diǎn)化進(jìn)行了討論。第一章緒論第4頁(yè)14LDPC碼的應(yīng)用前景LDPC碼的最大亮點(diǎn)是其接近香農(nóng)極限的誤碼性能，這在當(dāng)今強(qiáng)調(diào)低輻射、低功耗的時(shí)代背景下顯得尤其重要。對(duì)于無(wú)線通信而言，終端設(shè)備一般具有體積小、攜帶方便、能耗低的特點(diǎn)。無(wú)線設(shè)備的續(xù)航能力正日益為人們所重視，因此如何降低上行通信中的發(fā)射功率和下行通信中的接收功率就成了人們當(dāng)務(wù)之急，降低發(fā)射功率帶來(lái)的必然結(jié)果是降低接收機(jī)的信噪比，使得接收變得異常困難，而因?yàn)長(zhǎng)DPC能在接近于香農(nóng)極限的性噪比條件下正常工作，因此它能夠得到廣泛的認(rèn)可。國(guó)際上，LDPC碼已經(jīng)被列入IEEE80211N、IEEE80216E等標(biāo)準(zhǔn)；在歐洲，LDPC碼已被用于第二代衛(wèi)星數(shù)字視頻廣播標(biāo)準(zhǔn)（DVBS2）；在我國(guó)，數(shù)字電視地面?zhèn)鞑?biāo)準(zhǔn)已經(jīng)正式頒布并于今年8月強(qiáng)制執(zhí)行，這標(biāo)志著LDPC碼已經(jīng)正式走入國(guó)人的生活。當(dāng)然，我們也不能忽視了LDPC碼在其他電子領(lǐng)域的應(yīng)用。例如采用LDPC碼進(jìn)行壓縮和加密數(shù)據(jù)。在現(xiàn)今TB級(jí)的大容量硬盤(pán)中，為了延長(zhǎng)硬盤(pán)使用壽命、降低硬盤(pán)功耗，需要降低硬盤(pán)中的信噪比，這樣就會(huì)對(duì)編碼和糾錯(cuò)算法提出很高的要求，LDPC碼有望解決這個(gè)難題。如今在信道編碼這一領(lǐng)域，LDPC碼面臨的潛在競(jìng)爭(zhēng)來(lái)自于TURBO碼以及TURBO乘積碼等幾種同樣基于迭代譯碼的信道編碼。拿TURBO碼作對(duì)比，LDPC碼的優(yōu)勢(shì)在于譯碼的并行性，而TURBO碼的譯碼難以并行實(shí)現(xiàn)。另外，LDPC碼的譯碼要比TURBO碼方便，結(jié)構(gòu)也更簡(jiǎn)單。然而，除了RA碼和一些類似RA結(jié)構(gòu)的碼以外，其余LDPC碼的編碼復(fù)雜度仍然比較高，這可能是制約LDPC碼發(fā)展的一個(gè)重要瓶頸。15本章小結(jié)本章首先簡(jiǎn)要介紹了信道編碼的基本理論，進(jìn)而引出了LDPC碼，給出了其基本原理、發(fā)展概況和應(yīng)用前景。一般情況下，信道編碼的最佳譯碼方法是最大似然算法，在接收到一個(gè)碼字時(shí)，它通過(guò)計(jì)算所有有效碼字的發(fā)送概率并取最大的那個(gè)碼字來(lái)實(shí)現(xiàn)最佳譯碼，然而這樣的復(fù)雜度一般來(lái)說(shuō)是不能接受的。迭代譯碼的引入為人們找到了一種次最優(yōu)的譯碼方法，由于硬件實(shí)現(xiàn)復(fù)雜度的關(guān)系直到上世紀(jì)90年代才為人們所關(guān)注。LDPC碼由于其校驗(yàn)矩陣是稀疏的，因此在一次迭代中信息傳遞的次數(shù)不會(huì)很多，從而非常適合迭代譯碼，代表著信道編碼技術(shù)新的發(fā)展方向。第一章緒論第5頁(yè)截止目前，LDPC碼已經(jīng)被我國(guó)采用到數(shù)字電視地面?zhèn)鞑?biāo)準(zhǔn)中，并且IEEE80216E（WIMAX）、IEEE80211N以及DVBS2也已率先采用了這一編碼技術(shù)，可見(jiàn)其有著廣闊的發(fā)展前景。LDPC碼比起TURBO碼有著天然的并行優(yōu)勢(shì)，因此它將是下一代無(wú)線通信系統(tǒng)中最具有競(jìng)爭(zhēng)力的信道編碼方案。第二章LDPC碼譯碼算法第6頁(yè)第二章LDPC碼譯碼算法簡(jiǎn)介迭代譯碼方法的可行性長(zhǎng)久以來(lái)一直是LDPC碼沒(méi)能得到重視的主要原因，人們?cè)噲D從硬件和算法兩方面改變這樣的情況。自從摩爾定律提出之日起，至今一直是有效的，當(dāng)半導(dǎo)體技術(shù)順利攻克45納米后，在未來(lái)10年內(nèi)，摩爾定律仍然是可以依賴的，這也就為迭代譯碼算法提供了硬件上的保障。與此同時(shí)，人們也盡可能地降低迭代譯碼算法的復(fù)雜度，由于算法復(fù)雜度與性能之間總保持著一種折中關(guān)系，因此如何在性能不損失很多的前提下找到簡(jiǎn)化的譯碼算法也就成了人們努力的方向。本章將首先介紹基于TANNER圖的LDPC表示方式，然后給出經(jīng)典的信息傳遞譯碼算法（MPA,MESSAGEPASSINGALGORITHM），其中將簡(jiǎn)要介紹置信傳播算法及其幾種比較常用的簡(jiǎn)化算法。21LDPC碼的TANNER圖表示線性分組碼既可以用它的生成矩陣G來(lái)表示，也可以用校驗(yàn)矩陣H來(lái)表示，對(duì)于LDPC碼來(lái)說(shuō)，由于校驗(yàn)矩陣是稀疏的，因此更容易用來(lái)表示，我們從以下漢明碼的校驗(yàn)矩陣看起1010101H0110011000111121把H矩陣的每一列看作一個(gè)重復(fù)碼，對(duì)應(yīng)一個(gè)比特節(jié)點(diǎn)XI；把H矩陣的每一行看作一個(gè)類奇偶校驗(yàn)碼，對(duì)應(yīng)一個(gè)校驗(yàn)節(jié)點(diǎn)FI；把H矩陣中J行I列的非零元素看作連接上述比特節(jié)點(diǎn)XI和校驗(yàn)節(jié)點(diǎn)FJ的一條邊。于是，對(duì)應(yīng)式21，可以得到圖21所示的TANNER圖7。圖中用等號(hào)表示一個(gè)比特節(jié)點(diǎn)，用加號(hào)表示一個(gè)校驗(yàn)節(jié)點(diǎn)。第二章LDPC碼譯碼算法第7頁(yè)F1F2F3X1X2X3X4X5X6X7圖21TANNER圖示例FIG21ANEXAMPLEOFTANNERGRAPH顯然，迭代譯碼時(shí)信息的傳遞是以TANNER圖中的邊為介質(zhì)的，而LDPC碼以其稀疏的校驗(yàn)矩陣大大降低了TANNER圖中邊的數(shù)量，進(jìn)而降低了迭代譯碼的復(fù)雜度，因此LDPC碼的出現(xiàn)使得基于TANNER圖的迭代譯碼算法得以真正有效地應(yīng)用。那稀疏的結(jié)構(gòu)會(huì)不會(huì)影響LDPC碼的誤碼性能呢LDPC碼所引入的稀疏矩陣對(duì)于迭代譯碼性能的損失是很小的。假設(shè)實(shí)際傳輸需要達(dá)到信道容量的1倍（這里是某個(gè)趨近于零的正常數(shù)），可以證明當(dāng)趨向于零的時(shí)候，校驗(yàn)矩陣H中“1”的個(gè)數(shù)只需要有NLN1/的數(shù)量級(jí)，基于TANNER圖的迭代譯碼質(zhì)量就不會(huì)明顯下降，這里N是LDPC碼碼長(zhǎng)。稀疏的校驗(yàn)矩陣帶來(lái)的好處是，在趨向于零的情況下，每比特譯碼迭代總復(fù)雜度的數(shù)量級(jí)為1/LN1/；而在最大似然譯碼算法中，當(dāng)傳輸速率趨近信道容量時(shí)，這個(gè)復(fù)雜度函數(shù)是1/的指數(shù)函數(shù)。因此，LDPC碼迭代譯碼的理論基礎(chǔ)是非常充實(shí)的。22信息傳遞算法信息傳遞算法是一種常用的LDPC譯碼算法，其中置信傳播算法（BPA，BELIEFPROPAGATIONALGORITHM）是目前已知誤碼性能最好的LDPC譯碼算法。首先我們看一下比特節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)分別是如何工作的。第二章LDPC碼譯碼算法第8頁(yè)A1A2E3A4A5E6圖22信息在比特節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的計(jì)算示意圖FIG22ILLUSTRATIONOFINFORMATIONPROCESSINGATBITNODE圖22給出了信息在比特節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的計(jì)算示意圖。其中比特節(jié)點(diǎn)的外信息E3由式22決定，校驗(yàn)節(jié)點(diǎn)的外信息E6由式23決定123121211AAEAAAA226343411EAAAA23圖中比特節(jié)點(diǎn)接收除了目標(biāo)校驗(yàn)節(jié)點(diǎn)外其余所有校驗(yàn)節(jié)點(diǎn)傳遞的外信息以及信道信息，計(jì)算后將互信息傳遞給目標(biāo)校驗(yàn)節(jié)點(diǎn)。校驗(yàn)節(jié)點(diǎn)接收除了目標(biāo)比特節(jié)點(diǎn)外其余所有比特節(jié)點(diǎn)傳遞的外信息，計(jì)算后將互信息傳遞給目標(biāo)比特節(jié)點(diǎn)。這里，式22和23只是作示例用，實(shí)際情況下比特節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的輸入可能遠(yuǎn)遠(yuǎn)大于兩路，本章稍后部分將會(huì)作詳細(xì)介紹。在所有的信息傳遞算法中，置信傳播算法是最常用的，對(duì)它稍作修正還能得到許多簡(jiǎn)化算法。221置信傳播算法如式22、23所指出的那樣，置信傳播算法在TANNER圖的邊上傳遞的并不是硬值，而是概率值，它是一種軟值，相對(duì)硬值保留了更多的信息，相應(yīng)地使譯碼性能得到很大提高，所犧牲的復(fù)雜度也還是可以接受的。為了說(shuō)明置信傳播算法，首先給出一些符號(hào)定義，并假定發(fā)送碼字C的每一個(gè)比特具有獨(dú)立的分布1JJIRIH，表示H矩陣第J行中非零元素列位置的集合；第二章LDPC碼譯碼算法第9頁(yè)1JJIRIIHI，表示H矩陣第J行中，除了第I列外非零元素列位置的集合；1IJICJH，表示H矩陣第I列中非零元素行位置的集合；1IJICJJHJ，表示H矩陣第I列中，除了第J行之外非零元素行位置的集合；PR1/IIIPCY，表示在信道接收信息YI前提下，信息節(jié)點(diǎn)I取1的概率；IJQB表示在已知除第I個(gè)校驗(yàn)方程外其他所有校驗(yàn)方程以及信道的信息時(shí)，發(fā)送碼字ICB的概率；JIRB表示當(dāng)ICB時(shí)，第J個(gè)校驗(yàn)方程被滿足的概率。2211概率域上的置信傳播算法初始化對(duì)于每一對(duì)滿足HIJ1的I,J，令22/101PR1|1IIJIIIYQPXYE2422/11PR1|1IIJIIIYQPXYE25第一步對(duì)每一個(gè)校驗(yàn)方程J以及相應(yīng)的每一個(gè)RJ中的I，計(jì)算以下兩個(gè)概率度量11012122JJIIJIRIRQ26110JIJIRR27第二步利用上一步計(jì)算所得的0JIR和1JIR更新概率值0IJQ和1IJQ，對(duì)于每一個(gè)J進(jìn)行以下計(jì)算010IIJIJIJIJCJQKPR2811IIJIJIJIJCJQKPR29第二章LDPC碼譯碼算法第10頁(yè)其中，常數(shù)IJK是歸一化系數(shù)，使得011IJIJQQ；0IJIJCJR表示信息比特取值為0時(shí)所有的校驗(yàn)方程得到滿足的概率；1IJIJCJR表示信息比特取值為1時(shí)所有的校驗(yàn)方程得到滿足的概率。第三步對(duì)于每一個(gè)I，計(jì)算比特I取值為0和1的后驗(yàn)概率0IQ和1IQ010IIIIJJCQKPR21011IIIIJJCQKPR211其中，常數(shù)IK是歸一化系數(shù)，使得011IIQQ。硬判輸出對(duì)于每一個(gè)I，進(jìn)行如下判決11050IIIFQCELSE212如果此時(shí)0TCH，則譯碼成功并停止迭代；否則判定此次譯碼失敗，若此時(shí)的迭代次數(shù)少于最大預(yù)設(shè)迭代次數(shù)，則回到第一步；若達(dá)到最大迭代次數(shù)仍未成功，則宣告譯碼失敗。實(shí)際應(yīng)用中，由于概率域上的置信傳播算法涉及的大多是乘法操作，因此不利于硬件實(shí)現(xiàn)，一個(gè)自然的想法是利用取對(duì)數(shù)的方法將乘法轉(zhuǎn)化為加法，因此就得到了下述對(duì)數(shù)域上的置信傳播算法。2212對(duì)數(shù)域上的置信傳播算法在進(jìn)一步研究對(duì)數(shù)域上置信傳播算法前，需要在已有定義的基礎(chǔ)上，增加對(duì)數(shù)域上相應(yīng)概念的定義。來(lái)自信道的信息定義為PR1|LOGPR1|IIIIIXYLCXY；在比特節(jié)點(diǎn)上，定義0LOG1IJIJIJQLQQ，IJIJSIGNLQ表示輸出互信息的符號(hào)位，IJIJLQ表示輸出互信息幅度的絕對(duì)值；第二章LDPC碼譯碼算法第11頁(yè)在校驗(yàn)節(jié)點(diǎn)上，定義0LOG1JIJIJIRLRR；譯碼器輸出定義為0LOG1IIIQLQQ；這些都是概率比的對(duì)數(shù)值，稱它們?yōu)閷?duì)數(shù)似然比（LLR，LOGLIKELIHOODRATIO）。此外，定義函數(shù)11LOGTANHLOG21XXEXXENULL，當(dāng)X0時(shí)，容易證明1XX213以下過(guò)程描述對(duì)數(shù)域置信傳播算法初始化對(duì)于每一對(duì)滿足HIJ1的I,J，令22/IJIILQLCY214第一步對(duì)每一個(gè)校驗(yàn)方程J以及相應(yīng)的每一個(gè)RJ中的I，計(jì)算以下對(duì)數(shù)域度量JJIJIJIJIRIIRILR215第二步對(duì)于每一個(gè)J，利用第一步的計(jì)算結(jié)果，計(jì)算以下對(duì)數(shù)域度量IIJIJIJCJLQLCLR216第三步對(duì)于每一個(gè)I，計(jì)算IIIJIJCLQLCLR217硬判輸出對(duì)于每個(gè)I，進(jìn)行如下判決100IIIFLQCELSE218如果此時(shí)0TCH，則譯碼成功并停止迭代；否則判定此次譯碼失敗，若此時(shí)的迭代次數(shù)少于最大預(yù)設(shè)迭代次數(shù)，則回到第一步；若達(dá)到最大迭代次數(shù)仍未成功，則宣告譯碼失敗。從上述算法過(guò)程中可見(jiàn)，對(duì)數(shù)域上的置信傳播算法只涉及加減法和查表操作，比較適合硬件實(shí)現(xiàn)。然而，由于式215的查表復(fù)雜度直接決定了對(duì)數(shù)域上置信傳播算法的實(shí)現(xiàn)復(fù)雜度，因此對(duì)該式的簡(jiǎn)化將有助于譯碼算法復(fù)雜度的大幅降低。第二章LDPC碼譯碼算法第12頁(yè)222最小和算法由于置信傳播譯碼算法的復(fù)雜度集中在215式的計(jì)算上，因此尋找一種簡(jiǎn)單函數(shù)來(lái)逼近式215的結(jié)果會(huì)是比較理想的。根據(jù)函數(shù)X的特性，JIJIRI的值可以用最小的IJ所對(duì)應(yīng)的IJ的值來(lái)近似，于是MINMINJJJJJJIJIJIJIJIJIJIJIRIIRIIRIIRIIRIIRILRII219這就是“最小和”的原意。然而，對(duì)置信傳播算法的簡(jiǎn)化必然會(huì)帶來(lái)算法性能上的損失，包括收斂速度和誤碼性能，為了最大程度上彌補(bǔ)這些損失，人們又在最小和算法的基礎(chǔ)上提出了一些改進(jìn)算法。223各種基于最小和算法的改進(jìn)算法由函數(shù)X的性質(zhì)可知，最小和算法會(huì)得到比真實(shí)JIJIRI值更大的結(jié)果，因此人為加入加性或者乘性因子可以修正這種誤差，從而改善譯碼的性能，這一類算法統(tǒng)稱為改進(jìn)的最小和算法（MMSA,MODIFIEDMINIMUMSUMALGORITHM）。仿真證明改進(jìn)的最小和算法能夠小幅提高譯碼器的誤碼性能。由于改進(jìn)的最小和算法的收斂速度和置信傳播算法幾乎一樣，因此在某些需要高速譯碼的領(lǐng)域，人們又引入了分層的改進(jìn)的最小和算法（LMMSA,LAYEREDMODIFIEDMINIMUMSUMALGORITHM）。分層的概念就是把原先的一次迭代分解為現(xiàn)在的幾次小迭代，雖然幾次小迭代所需要的總的時(shí)鐘數(shù)和原先一次迭代的時(shí)鐘數(shù)相同，但是這幾次小迭代之間是有信息互通的，雖然這樣做會(huì)少量增加譯碼器的硬件資源，但是由于LMMSA算法可以使收斂速度增加一倍，即置信傳播算法20次迭代等價(jià)于LMMSA算法的10次迭代，因此從吞吐量的角度上來(lái)看仍然有著非常大的改善。鑒于置信傳播譯碼算法的變體還有很多種，在此不再一一列舉。23本章小結(jié)本章從LDPC的TANNER圖表示開(kāi)始，介紹了最常用的LDPC碼迭代譯碼算法第二章LDPC碼譯碼算法第13頁(yè)信息傳遞算法。其中一類置信傳播算法目前廣泛地應(yīng)用于各類LDPC碼譯碼器中。221給出了置信傳播算法在概率域及對(duì)數(shù)域上計(jì)算的具體步驟，由于它傳遞的是軟信息，因此比一般傳遞硬值的譯碼算法需要更多的量化資源，但是由于軟信息得到了保留，因此誤碼性能有大幅的提高。由于傳統(tǒng)的置信傳播算法復(fù)雜度仍然較高，因此在硬件實(shí)現(xiàn)上一般采用最小和算法代替。為了補(bǔ)償最小和算法帶來(lái)的性能損失，又引入了加性或乘性因子，使最小和算法性能非常接近對(duì)數(shù)域的置信傳播算法。由于改進(jìn)的最小和算法收斂速度不夠快，在要求高吞吐量的領(lǐng)域一般采用分層的改進(jìn)最小和譯碼算法，雖然這樣做會(huì)增加硬件資源，但是單位吞吐量所需的資源消耗仍然是下降的。迭代譯碼的出現(xiàn)使得LDPC碼在實(shí)際應(yīng)用中具有了接近香農(nóng)極限的誤碼性能，這也促使LDPC碼躋身各大通訊標(biāo)準(zhǔn)中。在介紹完LDPC碼基本譯碼算法后，下一章起將介紹本文的重點(diǎn)高吞吐量LDPC碼編碼構(gòu)造及其編碼器實(shí)現(xiàn)方法。第三章主流LDPC碼構(gòu)造方法與編碼算法第14頁(yè)第三章主流LDPC碼構(gòu)造方法與編碼算法比起TURBO碼而言，LDPC碼在譯碼方面有著并行和簡(jiǎn)單的結(jié)構(gòu)，然而較復(fù)雜的編碼結(jié)構(gòu)始終是擺在LDPC碼構(gòu)造者面前的難題。盡管有普遍適用的LDPC編碼算法存在，但是由于其較高的復(fù)雜度，以及很少考慮資源的復(fù)用，一般在實(shí)際中不能直接采用，因此簡(jiǎn)單的編碼算法仍然需要基于特殊的碼字構(gòu)造。本章將簡(jiǎn)要介紹當(dāng)今主流的碼字構(gòu)造及其相應(yīng)得編碼算法，這也是第四章提出的一種高吞吐量LDPC碼構(gòu)造和編碼的基礎(chǔ)。RU算法作為最先提出的普適的LDPC碼編碼算法，為后來(lái)很多編碼算法奠定了基礎(chǔ)，許多碼構(gòu)造和編碼算法是通過(guò)在RU算法上作改進(jìn)實(shí)現(xiàn)的。RU算法也是本文提出的編碼算法的基礎(chǔ)，31將會(huì)簡(jiǎn)要介紹RU算法。現(xiàn)在的LDPC碼構(gòu)造，一般都是建立在循環(huán)移位結(jié)構(gòu)的基礎(chǔ)上的。這樣的構(gòu)造需要對(duì)基矩陣作單次擴(kuò)展，其中基矩陣一般根據(jù)理論優(yōu)化得到的度分布對(duì)確定校驗(yàn)矩陣的行重和列重，所作的單次擴(kuò)展則確定校驗(yàn)矩陣的細(xì)節(jié)，一般會(huì)盡量使校驗(yàn)矩陣滿秩。優(yōu)化校驗(yàn)矩陣環(huán)長(zhǎng)的過(guò)程同時(shí)存在于確定基矩陣和單次擴(kuò)展之中。然而即使本質(zhì)上都采用基于循環(huán)移位結(jié)構(gòu)的單次擴(kuò)展方法，目前各大標(biāo)準(zhǔn)中所使用的構(gòu)造仍然可以明顯地分為兩個(gè)方向第一種方法根據(jù)優(yōu)化理論得到的度分布對(duì)，或者某些優(yōu)化環(huán)長(zhǎng)的算法，例如邊增長(zhǎng)（PEG,PROGRESSIVEEDGEGROWTH）算法確定基矩陣。我國(guó)數(shù)字電視地面?zhèn)鬏敇?biāo)準(zhǔn)中使用的就是這種碼構(gòu)造方法。32將對(duì)這種構(gòu)造方法作相應(yīng)的介紹，并且給出一種基于生成矩陣的編碼算法，這種算法可以解決幾乎所有該類碼構(gòu)造的編碼問(wèn)題。第二種方法對(duì)基矩陣的非零元素位置作了一定的規(guī)定，如要求最右邊的方陣非零元素占滿主對(duì)角線和一條次對(duì)角線等。這種方法是受到RA碼結(jié)構(gòu)的啟發(fā)，它的編碼復(fù)雜度和RA碼相近，但是其吞吐量比傳統(tǒng)RA碼要高很多，原因在于引入了并行的累加結(jié)構(gòu)，并且它的譯碼器也比傳統(tǒng)RA碼容易實(shí)現(xiàn)。由于基于生成矩陣的編碼算法對(duì)于寄存器和ROM資源需求很大，并且和碼長(zhǎng)的平方成正比，在碼長(zhǎng)很長(zhǎng)時(shí)就不適用了，因此類似RA碼的構(gòu)造算法非常適合長(zhǎng)碼長(zhǎng)情況。IEEE80211N、IEEE80216E以及歐洲的DVBS2標(biāo)準(zhǔn)中使用的就是這種碼構(gòu)造方法。33將對(duì)這種構(gòu)造方法作簡(jiǎn)要介紹，并且給出相應(yīng)的基于迭代譯碼的編碼算法。第三章主流LDPC碼構(gòu)造方法與編碼算法第15頁(yè)31RU算法作為一種線形分組碼，LDPC碼可以使用信息比特S與生成矩陣G相乘的方法得到編碼后的碼字C，即CSG。這樣做的缺點(diǎn)是很明顯的，由于G矩陣是通過(guò)對(duì)H矩陣進(jìn)行某些非線性操作得到的，因而一般是一個(gè)非稀疏的矩陣，而且很難保證有什么規(guī)律，因此這種做法沒(méi)有利用到H矩陣的任何特性，包括最明顯的稀疏特性，是很不經(jīng)濟(jì)的。既然從上述生成矩陣的方程式出發(fā)不能得到一種簡(jiǎn)單的編碼算法，一個(gè)很自然的想法就是從校驗(yàn)方程式HCT0T出發(fā)進(jìn)行編碼。RICHARDSON和URBANKE在文獻(xiàn)24中回答了這個(gè)問(wèn)題。他們指出，針對(duì)任何一個(gè)普通的校驗(yàn)矩陣H，只需要對(duì)其進(jìn)行一次軟件上的簡(jiǎn)單預(yù)處理，使它變成一種類似下三角陣的結(jié)構(gòu)，就能進(jìn)行簡(jiǎn)單編碼了。并且這種編碼算法的復(fù)雜度在大多數(shù)情況下近似與碼長(zhǎng)成正比，因此它是一種具有普適意義的簡(jiǎn)單LDPC碼編碼算法。311RU算法RU算法主要分為三個(gè)階段預(yù)處理階段、編碼階段和碼字交換階段。假設(shè)H矩陣是MN維的，預(yù)處理通過(guò)對(duì)校驗(yàn)矩陣H作行交換和列交換，目的是把H矩陣變?yōu)槿鐖D31所示的類似下三角的矩陣，其中矩陣A的大小為MGNM，矩陣B的大小為MGG，下三角矩陣T的大小為MGMG，矩陣C的大小為GNM，矩陣D的大小為GG，矩陣E的大小為GMG。同時(shí)需要保證由DBET1所定義的矩陣是可逆的，如果本次預(yù)處理時(shí)不可逆，則可以將矩陣B、D所在的某些列進(jìn)行內(nèi)部交換或者與矩陣A、C的某些列互換，并進(jìn)行下一次試探，直到滿秩為止。由于預(yù)處理涉及的矩陣操作只涉及初等變換中的行交換和列交換，因此，經(jīng)過(guò)預(yù)處理后的矩陣H矩陣仍然是稀疏的。第三章主流LDPC碼構(gòu)造方法與編碼算法第16頁(yè)ABCDETMNGNMMGGMG圖31經(jīng)行交換、列交換后的類似下三角校驗(yàn)矩陣HFIG31THEREFORMEDPARITYCHECKMATRIXHINAPPROXIMATELYLOWTRIANGLEFORM經(jīng)過(guò)處理后的矩陣H也是MN維的，由圖31可知，矩陣H可以表示成如下形式EDCTBAH31為了推導(dǎo)簡(jiǎn)單，以下將H記作H，事實(shí)上從校驗(yàn)方程式的角度上看，使用H和H的區(qū)別只是在于是否需要對(duì)C進(jìn)行一次列交換，由于在RU編碼的第三階段碼字交換階段會(huì)對(duì)C進(jìn)行從H到H的逆向列交換過(guò)程，因此這兩次列交換過(guò)程在計(jì)算推導(dǎo)時(shí)完全可以認(rèn)為是透明的。在式31兩邊同時(shí)左乘下三角矩陣1IOETI，得到ODBETCAETTBAHIETOI11132由校驗(yàn)方程式可知，編碼后碼字C滿足HCT0T。在此對(duì)C進(jìn)行分割，令CS,P1,P2，其中S表示信息位，P1和P2聯(lián)合表示校驗(yàn)位，實(shí)際中分別對(duì)應(yīng)矩陣B、D和T、E所在的列，則校驗(yàn)位的P1長(zhǎng)度為G，P2長(zhǎng)為MG。由校驗(yàn)方程式，可將32式作如下分解120TTTASBPTP331110ETACSETBDP34定義矩陣DBET1，于是得到校驗(yàn)位P1和P2的表示式第三章主流LDPC碼構(gòu)造方法與編碼算法第17頁(yè)111TTPETACS35121TTTPTASBP36至此完成了RU算法的編碼計(jì)算過(guò)程，以下我們簡(jiǎn)單分析RU算法的編碼復(fù)雜度。在式35中，由于1是大小為GG的非稀疏矩陣，因此35式的計(jì)算復(fù)雜度與G2成正比。同樣地，在式36中，T1是大小為MGMG的非稀疏矩陣，但是由于T本身是下三角的，因此T1也是下三角的，于是其與向量的乘法可以使用文獻(xiàn)24提出的前向替換的方法來(lái)簡(jiǎn)化。這樣，RU算法的編碼復(fù)雜度就可以減少到ONG2，所以在編碼預(yù)處理階段，要求G盡可能的小，也就要求下三角陣T的維數(shù)盡量大。RU算法的編碼流程如圖32所示，除去輸入輸出級(jí)的話，一共需要6級(jí)流水線。被A乘被C乘被T1乘被E乘被B乘被1乘被T1乘信息比特S流水線分級(jí)異或異或校驗(yàn)比特P2校驗(yàn)比特P1圖32RU編碼算法流程圖FIG32FLOWCHARTOFRUENCODINGALGORITHM第三章主流LDPC碼構(gòu)造方法與編碼算法第18頁(yè)312RU算法的優(yōu)缺點(diǎn)RU算法從校驗(yàn)方程式出發(fā)，繞開(kāi)了非稀疏的生成矩陣對(duì)LDPC碼進(jìn)行編碼，充分利用了校驗(yàn)矩陣稀疏的特點(diǎn)，是LDPC碼第一種比較理想的編碼方式。不僅如此，它通過(guò)有限的兩種初等變換求得一個(gè)維數(shù)較大的下三角方陣，利用其逆矩陣也是下三角的特點(diǎn)，應(yīng)用前向替換將非稀疏矩陣與向量的乘法簡(jiǎn)化，使得整體計(jì)算復(fù)雜度從ON2降低到了ONG2。但是，RU算法的缺點(diǎn)也是比較明顯的。首先，RU算法的流水級(jí)安排不合理，這里指的是每一級(jí)流水線所消耗的時(shí)鐘數(shù)相差比較大。拿碼長(zhǎng)為1536的LDPC碼來(lái)說(shuō)，算上輸入、輸出兩個(gè)緩存級(jí)，流水級(jí)所需的時(shí)鐘數(shù)從1095到3906不等，這就會(huì)導(dǎo)致某些流水級(jí)長(zhǎng)時(shí)間不在工作狀態(tài)，降低了硬件的利用效率。其次，在1沒(méi)有被強(qiáng)制設(shè)計(jì)為某些特殊簡(jiǎn)單矩陣的情況下，它與向量的乘法沒(méi)有辦法做任何簡(jiǎn)化，這會(huì)使RU算法在支持自適應(yīng)編碼時(shí)顯得力不從心。最后，前向替換方法是一把雙刃劍，在解決了下三角非稀疏矩陣與向量乘法的同時(shí)，也引入了串行的計(jì)算結(jié)構(gòu)，使得目標(biāo)向量中下一個(gè)分量的求解依賴于該向量之前求得的所有分量，因此前向替換必須一位一位進(jìn)行，大大限制了吞吐量的提升，這一點(diǎn)和33所介紹的一種傳統(tǒng)RA碼的累加結(jié)構(gòu)是類似的。綜上所述，在硬件資源有限的前提下，RU算法只適合應(yīng)用在吞吐量要求不太高、碼長(zhǎng)不太長(zhǎng)、不要求自適應(yīng)編碼的場(chǎng)合。然而在結(jié)合了準(zhǔn)循環(huán)移位結(jié)構(gòu)后，對(duì)其算法作一些改進(jìn)能得到一些非常實(shí)用的算法，因此RU算法的理論指導(dǎo)意義很大。32基于生成矩陣的編碼算法RU算法的普適性使得它能夠解決一般LDPC碼的編碼問(wèn)題，從31的介紹中我們可以看到，RU算法考慮的只是校驗(yàn)矩陣的稀疏性，它不對(duì)校驗(yàn)矩陣作任何其它假定，于是當(dāng)校驗(yàn)矩陣仍存在某種其他規(guī)律時(shí)，RU算法顯然是不能預(yù)計(jì)的。正是由于RU方法存在的這一不足，使得它與實(shí)際理想LDPC的編碼算法仍有一定距離，這也促使人們往校驗(yàn)矩陣上施加更多的約束，以達(dá)到簡(jiǎn)化編碼算法的目的。隨著準(zhǔn)循環(huán)移位結(jié)構(gòu)的流行，人們開(kāi)始重新審視基于生成矩陣的編碼方法。此時(shí)的生成矩陣已經(jīng)不再是那種沒(méi)有規(guī)律的非稀疏陣，在某些條件下，生成矩陣也具有了準(zhǔn)循環(huán)移位結(jié)構(gòu)的特點(diǎn)。這種構(gòu)造及編碼方法的典型應(yīng)用在于我國(guó)的數(shù)字電視地面?zhèn)鬏敇?biāo)準(zhǔn)。本節(jié)將會(huì)簡(jiǎn)單介紹基于單次擴(kuò)展的QCLDPC碼以及針對(duì)這一類碼的基于生成矩陣的第三章主流LDPC碼構(gòu)造方法與編碼算法第19頁(yè)編碼算法。321基于單次擴(kuò)展的QCLDPC碼首先給出一些關(guān)于QCLDPC碼的基本定義。若一個(gè)方陣可由單位矩陣經(jīng)循環(huán)右移N位后得到，那么這個(gè)矩陣稱為循環(huán)移位單位陣（CSI,CYCLICSHIFTIDENTITY）；一般地，若一個(gè)方陣除去第一行后的每一行都可由該方陣上一行經(jīng)循環(huán)右移一位后得到，并且第一行是最后一行經(jīng)循環(huán)右移一位后得到，那么這個(gè)方陣稱為循環(huán)移位陣（CSM,CYCLICSHIFTMATRIX）。進(jìn)一步，如果將ZPEX個(gè)大小相同的循環(huán)移位單位陣和ZPEXZPEX1個(gè)相同大小的零陣拼接得到方陣，并且該方陣的行重、列重均為1，那么這個(gè)方陣稱為準(zhǔn)循環(huán)移位單位陣（QCI,QUASICYCLICIDENTITY）；一般地，如果將ZPEXZPEX個(gè)大小相同的循環(huán)移位陣或者零陣拼接得到方陣，那么這個(gè)方陣稱為準(zhǔn)循環(huán)移位陣（QCM,QUASICYCLICMATRIX）。顯然，準(zhǔn)循環(huán)移位單位陣是一種特殊的準(zhǔn)循環(huán)移位陣。文獻(xiàn)26證明了準(zhǔn)循環(huán)移位陣的加、減、乘、求逆運(yùn)算（如果存在）所得仍是準(zhǔn)循環(huán)移位陣。如果一個(gè)LDPC碼的校驗(yàn)矩陣由且僅由大小相同的循環(huán)移位陣或零陣拼接而成，那么此LDPC碼稱為QCLDPC碼。假設(shè)H矩陣的基矩陣大小是MN的，一般MN。圖33給出了QCLDPC碼校驗(yàn)矩陣的模型，其中HI,J1IMJN,1為大小相同的循環(huán)移位陣或者零陣。H1,NH2,NH2,1H1,1HM,NHM,1H2,2H1,2HM,2H1,N1H2,N1HM,N1圖33QCLDPC碼校驗(yàn)矩陣FIG33PARITYCHECKMATRIXOFQCLDPCCODE第三章主流LDPC碼構(gòu)造方法與編碼算法第20頁(yè)322基于生成矩陣的編碼算法基于生成矩陣的編碼算法前提是構(gòu)造出具有類似于圖33的具有循環(huán)移位結(jié)構(gòu)的生成矩陣，即使在絕大多數(shù)情況下，該矩陣不是稀疏的。假設(shè)上述HI,J的大小是ZCSEXZCSEX的，即循環(huán)移位擴(kuò)展的擴(kuò)展因子是ZCSEX。文獻(xiàn)26分別