摘要 低密度校驗(yàn)碼以其低復(fù)雜度的迭代譯碼和可逼近香農(nóng)限而成為目前最佳的編碼技 術(shù)之一，越來越受到眾多編碼研究者的關(guān)注。 本文首先簡(jiǎn)述了通信系統(tǒng)以及信道編碼理論的基礎(chǔ)知識(shí)，并且對(duì)線性分組碼的基 本原理作了闡述。本文介紹了l d p c 碼的定義、最主要的編譯碼算法，重點(diǎn)介紹了 d v b s 2 標(biāo)準(zhǔn)中l(wèi) d p c 碼的特點(diǎn)及編碼方法，給出了通過仿真得到的非規(guī)則校驗(yàn)矩陣， 并對(duì)l d p c 碼編碼器進(jìn)行設(shè)計(jì)并進(jìn)行仿真。闡述了對(duì)數(shù)域置信傳播算法的幾種表達(dá)形 式，討論了幾種最小和算法的改進(jìn)算法。然后對(duì)修正因子和偏移因子的選擇進(jìn)行了探 討，并仿真證明簡(jiǎn)化譯碼算法在運(yùn)算復(fù)雜度大幅下降的情況下性能與標(biāo)準(zhǔn)譯碼算法相 近。 關(guān)鍵詞：d v b s 2 標(biāo)準(zhǔn)l d p c 碼b p 算法f p g a a b s t r a c t l o w d e n s i t yp a r i t y c h e c kc o d e sc o m et o b co n eo ft h eb e s tc o d i n gt e c h n o l o g i e s b e c a u s eo ft h e i rl o w - c o m p l i c i t yi t e r a t i v ed e c o d i n ga l g o r i t h ma n dc o p a c i t ya p p r o a c h i n g p e r f o r m a n c e a n dt h e ya t r a c km o r ea n dm o r er e s e a r c h e r se y e si nr e c e n ty e a r s i nt h i st h e s i s ，t h eb a s i so fc o m m u n i c a t i o na n dc h a n n e lc o d i n gt h e o r yi si n t r o d u c e d b r i e f l y a f t e rt h ed e f i n i t i o no fl d p cc o d e ，t h ee n c o d i n ga n dd e c o d i n ga l g o r i t h m s ，a l s ot h e p e r f o r m a n c ea n a l y s i so fd e c o d i n ga l g o r i t h m s ，a r es t u d i e d t h e n ，i ti n t r o d u c e s t h ec o d i n g s c h e m e su s e di nd v b s 2 a n dg e t st h ep a r i t yc h e c km a t r i xb ys i m u l a t i o n i tg i v e ss o m e s o l u t i o n sf o rd e s i g n i n gt h ee n c o d e r v a r i o u sl o g - - l i k e l i h o o d - r a t i o - b a s e db e l i e f - p r o p a g a t i o n d e c o d i n ga l g o r i t h m sa n dt h e i rr e d u c e d c o m p l e x i t yd e r i v a t i v e sf o rl d p cc o d e s u s e di n d v b - s 2a r ep r e s e n t e d f i n a l l y , i td i s c u s sh o wt og e tt h ec o r r e c t i o nf a c t o ra n do f f s e tf a c t o r u s i n gi nt h en o r m a l i z e db p b a s e dd e c o d i n ga n do f f s e tb p - b a s e dd e c o d i n g s i m u l a t i o n r e s u l t ss h o wt h a tt h e s er e d u c e d - c o m p l e x i t yd e c o d i n ga l g o r i t h m sf o rl d p cc o d e sa c h i e v ea p e r f o r m a n c ev e r yc l o s et ot h a to ft h eb pa l g o r i t h m k e y w o r d s ：d v b - s 2 l d p cb pa l g o r i t h mf p g a 長(zhǎng)春理工大學(xué)碩士學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的碩士學(xué)位論文，l d p c 碼在d v b s 2 標(biāo)準(zhǔn)中的應(yīng) 用研究是本人在指導(dǎo)教師的指導(dǎo)下，獨(dú)立進(jìn)行研究工作所取得的成果。除文中 已經(jīng)注明引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫過的 作品成果。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均己在文中以明確方式標(biāo) 明。本人完全意識(shí)到本聲明的法律結(jié)果由本人承擔(dān)。 作者簽名：曼月監(jiān)日 長(zhǎng)春理工大學(xué)學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者及指導(dǎo)教師完全了解“長(zhǎng)春理工大學(xué)碩士、博士學(xué)位論文版 權(quán)使用規(guī)定，同意長(zhǎng)春理工大學(xué)保留并向中國(guó)科學(xué)信息研究所、中國(guó)優(yōu)秀博碩 士學(xué)位論文全文數(shù)據(jù)庫(kù)和c n k i 系列數(shù)據(jù)庫(kù)及其它國(guó)家有關(guān)部門或機(jī)構(gòu)送交學(xué) 位論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)長(zhǎng)春理工大學(xué)可以 將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，也可采用影印、縮印 或掃描等復(fù)制手段保存和匯編學(xué)位論文。 儲(chǔ)簽名：縊豆望蝗翌2 年三月娌日 指導(dǎo)導(dǎo)師簽名： 筍日 第一章緒論弟一早硒記 本章介紹了論文的主要研究背景。首先對(duì)數(shù)字通信的基本模型和信道編碼理論發(fā) 展歷程進(jìn)行了楷述，然后介紹了逼近香農(nóng)限的信道編碼技術(shù)tl d p c 碼的提出和研究現(xiàn) 狀，最后給出全文的內(nèi)容安排。 1 1 引言 通信系統(tǒng)的目的就是實(shí)現(xiàn)發(fā)送端信息的無失真?zhèn)鬏?，在接收端接收到和發(fā)送端一 樣的信息，但是通信信道中普遍存在著信道噪聲，尤其是無線通信信道和衛(wèi)星通信信 道，為了使發(fā)送端的信息盡可能大的無失真?zhèn)魉偷浇邮斩?，人們提出了在通信系統(tǒng)的 發(fā)送端的信息，在發(fā)送時(shí)，添加一些冗余信息，通過冗余信息來恢復(fù)被信道噪聲干擾 而失真的信息，這就是信道編碼和信道譯碼。但這也造成了信道傳輸?shù)挠行院涂煽?性之間的矛盾，而且對(duì)于這些冗余信息能在多大程度上恢復(fù)失真的信息，和怎樣添加 冗余信息，都是沒有任何回答的。1 9 4 8 年，s h a n n o n n l 發(fā)表了名為“通信的數(shù)學(xué)理論 具有劃時(shí)代意義的學(xué)術(shù)論文。從而從數(shù)學(xué)的角度解釋了怎么添加冗余信息才能最大限 度的恢復(fù)失真的信源消息，同時(shí)也回答了冗余信息能在多大程度上恢復(fù)失真的信源信 息。他指出了在不可靠的信道下可以進(jìn)行可靠通信傳輸?shù)慕缦藓瓦_(dá)到這些界限的方法， 也就是回答了能在多大程度上恢復(fù)信源信息和怎樣添加冗余信息的問題。從而徹底改 變?cè)谥捌毡檎J(rèn)為的通信的可靠性和有效性是不可調(diào)和的矛盾的觀點(diǎn)。 一個(gè)數(shù)字通信信道可以定義由輸入符號(hào)x 和輸出符號(hào)y 以及在信道傳輸中受到干 擾后與之對(duì)應(yīng)的信道傳輸概率p ( x y ) 三元關(guān)系組成。對(duì)于一個(gè)有噪聲的通信信道， 總存在這樣一個(gè)參數(shù)c ，s h a n n o n 證明了當(dāng)信道傳輸數(shù)據(jù)的速率小于c 的情況下，總存 在一種編碼技術(shù)使得碼長(zhǎng)充分長(zhǎng)時(shí)，系統(tǒng)的錯(cuò)誤概率可以達(dá)到任意小。這就是香農(nóng)定 理。通信系統(tǒng)的系統(tǒng)模型如圖1 1 信源編碼信道編碼 信源i 信源編碼 i ；。l 信道編碼 ；r l 上 信道噪聲 上 銷卜 一信源譯碼 l l 信道鋸碼 i 圖1 1 數(shù)字通信系統(tǒng)模型 s h 鋤n o n 定理給我們提出了這樣的一種保證信息傳輸不失真的方法即信道編碼，信 道編碼器把將信息源添加一些冗余信息從而形成一個(gè)碼字，并把這些碼字發(fā)送出去。 這些經(jīng)過信道編碼的信息，受到信道噪聲的干擾，必定會(huì)產(chǎn)生失真，即從“0 ”到“1 ”和從 “1 ”到“0 ”的變化，在接收端，如果接收到的碼字序列，即“0 ”“1 ”交替序列和發(fā)送端相差 不是很大的情況下。接收端就可以根據(jù)事先的信道編碼規(guī)則，利用冗余的信息位，將 信道干擾的信號(hào)的失真去除掉。從s h a n n o n 定理我們可以知道，要想達(dá)到無誤傳輸?shù)膬?個(gè)條件是： ( 1 ) 構(gòu)造趨向于無窮長(zhǎng)的漸進(jìn)好碼或s h a i l n o n 碼； ( 2 ) 采用最佳的最大似然譯碼算法來譯碼。 幾十年來，人們對(duì)信道編碼做了大量的研究，戈雷碼、漢明碼、循環(huán)碼和b c h 碼 等優(yōu)秀的編碼相繼被發(fā)明。但是他們的性能都無法達(dá)到香農(nóng)碼的性能。9 0 年代，信道 編碼理論取得突飛猛進(jìn)的發(fā)展。9 3 年c b a y o u 等人提出的t u r b o 碼引，這種編碼在長(zhǎng)碼 時(shí)能夠逼近香農(nóng)限。t u r b o 碼在3 g 中被采用，取得了巨大的成功。人們由于t u r b o 碼的 出現(xiàn)和它取得的巨大成功的影響。對(duì)同樣采用迭代譯碼思想譯碼的早在1 9 6 2 年g a l l a g e r 發(fā)現(xiàn)的低密度校驗(yàn)碼( l d p c ，l o w d e n s i t yp a r i t y c h e c kc o d e s ) 9 j 重新重視起來，發(fā)現(xiàn) l d p c 在長(zhǎng)碼的條件下也是逼近香農(nóng)限的。并且在相比較于t u r b o 碼具有三大優(yōu)點(diǎn)：譯 碼的線性復(fù)雜度，抗突變的糾錯(cuò)能力，無交織器帶來的延時(shí)。 從s h a i l n o n 的噪聲信道編碼定理非構(gòu)造性證明中我們可以知道，任何噪聲信道都 存在好的分組碼，實(shí)際上所有的分組碼都是好的。隨著l d p c 碼編解碼理論的成熟， 越來越多的通信系統(tǒng)都開始采用l d p c 碼作為信道。 2 1 2 國(guó)內(nèi)外研究現(xiàn)狀 1 2 1l d p c 碼的發(fā)展歷程 早在1 9 6 3 年g a l l a g e r 在他的博士論文中就提出了l d p c 碼，并提出了隨機(jī)構(gòu)造的方 法構(gòu)造h 矩陣，并提出了迭代譯碼的算法，但由于當(dāng)時(shí)的理論水平和計(jì)算機(jī)硬件條件的 限制，一直沒有引起學(xué)術(shù)界的重視。l d p c 碼的重新發(fā)現(xiàn)和復(fù)興是始于人們對(duì)t u r b o 碼 迭代算法的深入研究的，同時(shí)也是編碼理論水平發(fā)展和計(jì)算機(jī)仿真能力的提高的影響。 同時(shí)，m a c k a y 和n e a l ，s i p s e r 和s p i e l m a n 以及w i b e r g 等人對(duì)它重新進(jìn)行了研究，發(fā)現(xiàn) l d p c 碼同樣具有逼近香農(nóng)限的優(yōu)異性能。從那時(shí)起該碼逐漸成為編碼領(lǐng)域的一個(gè)研究 熱點(diǎn)。l d p c 碼是一種特殊的線性分組碼，具有一個(gè)稀疏的校驗(yàn)矩陣。具有良好的線性 復(fù)雜度。學(xué)者們的研究取得了一定的成果。z y a b l o v _ j f l l p i n s k e r l l 6 j 證明了l d p c 碼是好碼 并給出了一種簡(jiǎn)單的“位翻轉(zhuǎn)”的譯碼算法。t a n n e r r 7 】提出利用二分圖來描述碼字的概 念，他將l d p c 碼的校驗(yàn)矩陣與后來稱為t a n n e r 圖的二分圖相對(duì)應(yīng)，在t a n n e r 圖上隨機(jī) 構(gòu)造的u ) p c 碼可以并行進(jìn)行譯碼降低了譯碼的復(fù)雜度，同時(shí)t a n n e r 還證明了在無環(huán) t a n n e r 圖上，最小和( m i n s u m ) 和與積( s u m p r o d u c t ) 譯碼算法是最優(yōu)的。 w i b e r g 毛e 重新研究t a n n e r 的研究成果的基礎(chǔ)上，將信息狀態(tài)引入至l j t a n n e r 圖中，并 且與t u r b o 碼和網(wǎng)格圖的研究相結(jié)合，t a n n e r 的研究成果推廣為含有狀態(tài)變量的w i b e r g 圖，這樣便得到了基于網(wǎng)格圖的消息傳遞算法。m a c k a y 和n e a l 1 8 兒1 1 j 發(fā)現(xiàn)了“m n ” ( m a c k e ya n dn e a l ) 碼，這實(shí)際也是一種低密度校驗(yàn)碼的重新發(fā)現(xiàn)，他們利用g a l l a g e r 在 他的博士論文中提到的隨機(jī)構(gòu)造法隨機(jī)構(gòu)造出的t a n n e r 圖研究l d p c 碼的性能，采用和 積譯碼算法的規(guī)則證明了l d p c 碼具有與t u r b o 碼具有相似的譯碼性能，在長(zhǎng)碼上甚至 超過t u r b o 碼。與此同時(shí)，s p i s e 和i s p i e m a n l l 9 j 研究了擴(kuò)展碼( e x p a n d e rg r a p h s ) ，證明了 基于t a n n e r 圖的l d p c 碼為漸進(jìn)好碼。l u b y l 2 0 j 等人將u ) p c 碼從規(guī)則的l d p c 碼拓展到非 規(guī)則的l d p c 碼，并證明了非規(guī)則u ) p c 碼比規(guī)則u ) p c 碼有更好的性能，當(dāng)選擇好的度 序列非規(guī)則碼的性能甚至要優(yōu)于t u r b o 碼。c h u n g 等人表明在二進(jìn)制輸夕, a w g n 信道下， 設(shè)計(jì)的碼率1 2 、碼長(zhǎng)1 0 7 的非規(guī)則碼在誤比特率為1 0 面時(shí)離s h a n n o n 艱：僅0 0 0 4 5 d b 。 r i c h a r d o n 和u r b a n k e 用稱為密度進(jìn)化理論( d e n s i t ye v o l u t i o nt h e o r y ) 的數(shù)值方法來跟蹤 計(jì)算在每次迭代譯碼中傳遞的信息的概率密度，并且分析了在碼長(zhǎng)足夠大和足夠的迭 代次數(shù)下，信道參數(shù)存在一個(gè)閥值現(xiàn)象，當(dāng)噪聲在小于這個(gè)閥值下，置信傳播算法才 能漸進(jìn)成功譯碼。他們還進(jìn)一步綜合分析研究了在漸進(jìn)大的的隨機(jī)二分圖的最佳分布 設(shè)計(jì)問題，并把密度進(jìn)化理論的分析法延展到更一般的信道中。k s c h i s c h a n g 等人在總 結(jié)t a n n e r 和w i b e r g 等的研究基礎(chǔ)上，建立一個(gè)統(tǒng)一的模型( 因子圖) 。在因子圖模型中， 置信傳播及l(fā) d p c 的迭代譯碼算法都可歸結(jié)為基于因子圖的和積算法。 3 1 2 2l d p c 碼的研究現(xiàn)狀 自l d p c 碼自重新受到重視以來，國(guó)內(nèi)外學(xué)者對(duì)低密度校驗(yàn)碼的研究熱點(diǎn)主要集中 在兩個(gè)方面，即碼本身性能的改進(jìn)和低密度校驗(yàn)碼在各種實(shí)際的通信標(biāo)準(zhǔn)中的應(yīng)用 【冽1 2 1 1 1 2 2 1 。 1 2 2 1l d p c 碼的構(gòu)造 低密度校驗(yàn)碼之所以能夠引起大家的關(guān)注，是因?yàn)樵诘兔芏刃ｒ?yàn)碼的校驗(yàn)矩陣是 一個(gè)低密度的校驗(yàn)矩陣，含有少量的“1 ”的結(jié)構(gòu)特性決定了低密度校驗(yàn)碼的性能，使它 具有線性復(fù)雜度，并且在由于校驗(yàn)矩陣中只含有少量的“1 ”因此，相距很遠(yuǎn)的信息比特 參與統(tǒng)一的校驗(yàn)，這就使得低密度校驗(yàn)碼自身就具有很好的抗突變性能。并且由于它 是一種線性分組碼，不需要交織器，避免了編碼過程中的延時(shí)問題。低密度校驗(yàn)碼的 一切優(yōu)異性能都是和它自身的校驗(yàn)矩陣結(jié)構(gòu)相關(guān)。因此如何構(gòu)造h 矩陣成為影響低密度 校驗(yàn)碼性能的關(guān)鍵。目前有關(guān)構(gòu)造l d p c 碼矩陣h 的方法很多，對(duì)于長(zhǎng)碼、中長(zhǎng)碼、短 碼具有不同的構(gòu)造方法，在這些構(gòu)造方法中，最主要的有兩類：g a l l a g e r 博士在他的博 士論文中最終提出的隨機(jī)構(gòu)造法和后來人們提出的結(jié)構(gòu)構(gòu)造法。隨機(jī)構(gòu)造法一般適合 于長(zhǎng)碼，其性能能夠接近香農(nóng)限，但是其復(fù)雜度過高，在實(shí)際應(yīng)用中限制太大。結(jié)構(gòu) 化構(gòu)造方法大體上可以分為代數(shù)構(gòu)造法和組合構(gòu)造法。代數(shù)方法一般是基于矩陣h 的數(shù) 學(xué)變化而來的，它的一般適合用于中，短長(zhǎng)度的碼。復(fù)雜度也較隨機(jī)構(gòu)造簡(jiǎn)單，但是 性能稍差。 1 2 2 2l d p c 碼的譯碼 一切編碼的好壞都要看解碼端，是否能簡(jiǎn)單準(zhǔn)確的譯碼出發(fā)送端送來的信息。這 是因?yàn)樵谝话銞l件下。發(fā)送端的條件大多可認(rèn)為控制，對(duì)設(shè)備的大型話，設(shè)備的大功 率化，我們都是可以滿足的。而對(duì)于特定條件下的接收端，對(duì)于譯碼的復(fù)雜度和譯碼 的準(zhǔn)確度都要同時(shí)滿足。低密度校驗(yàn)碼的結(jié)構(gòu)( 即校驗(yàn)矩陣h ) 定了之后，譯碼算法的好 壞便決定了編碼的性能。譯碼算法的復(fù)雜度決定了工程實(shí)現(xiàn)的可能性，而譯碼算法的 準(zhǔn)確性決定了工程實(shí)施的必要性。目前l(fā) d p c 碼的譯碼方法主要有兩類：一類是基于概 率的置信傳播，簡(jiǎn)稱b p 算法。這類算法的特點(diǎn)是譯碼性能好，但是譯碼復(fù)雜度高。對(duì) 接受端硬件要求較高。因此在保留高準(zhǔn)確性的同時(shí)，研究如何降低譯碼的復(fù)雜度是人 們一直研究的問題。因此，研究者提出了許多基于該算法的改進(jìn)算法。例如對(duì)數(shù)域b p 算法、最小和算法、歸一化最小和算法，偏移化最小和算法等。第二類是基于校驗(yàn)和 統(tǒng)計(jì)迭代的比特翻轉(zhuǎn)譯碼算法，簡(jiǎn)稱b f 算法。這類算法的特點(diǎn)是譯碼復(fù)雜度較低，但 同時(shí)譯碼準(zhǔn)確度較低，因此保留譯碼復(fù)雜度低，同時(shí)提高譯碼的準(zhǔn)確度成為廣大學(xué)者 研究的方向。但這一類譯碼算法研究較少。 1 2 2 3l d p c 碼的性能分析 隨著低密度校驗(yàn)碼研究的深入，出現(xiàn)了大量的新的理論，包括對(duì)低密度校驗(yàn)碼性 能分析的理論也出現(xiàn)了新的發(fā)展。( 1 ) 密度進(jìn)化，對(duì)于任何一種通信編碼來講，都有一 4 個(gè)判決門限，當(dāng)大于某個(gè)門限值時(shí)，得出正確的譯碼碼字。當(dāng)然對(duì)于一個(gè)通信信道編 碼的統(tǒng)計(jì)規(guī)律來看，當(dāng)信噪比大于某個(gè)值時(shí)，大量的信息比特被錯(cuò)誤的譯碼，最終造 成成誤碼率的增大。g a l l a g e r 博士在他的研究過程中發(fā)現(xiàn)，在信道噪聲水平低于某個(gè)閥 值( 門限) 時(shí)，隨著碼長(zhǎng)趨于無窮大時(shí)，碼的錯(cuò)誤概率可以任意逼近零，否則錯(cuò)誤概率將 大于一個(gè)正常數(shù)。r i c h a r d s o n 等人基于g a l l a g e r 的思想提出密度進(jìn)化理謝矧，提出在和 積譯碼算法的每次迭代信息傳遞中出現(xiàn)信息錯(cuò)誤是低密度校驗(yàn)編碼度分布序列和信道 參數(shù)的函數(shù)。( 2 ) 高斯近似，密度進(jìn)化理論的復(fù)雜度是相當(dāng)大的，特別對(duì)于信道相當(dāng)復(fù) 雜的來說，這就造成了密度進(jìn)化理論在實(shí)際應(yīng)用中的不可行性。為了在實(shí)際應(yīng)用中， 使密度進(jìn)化理論變得使用，通過比較少的運(yùn)算就能找到這個(gè)閥值( 門限) 時(shí)，提高密度進(jìn) 化算法的計(jì)算速度，學(xué)者們提出將多維問題轉(zhuǎn)化為高斯密度均值的一維問題，使多維 復(fù)雜信道變?yōu)楹?jiǎn)單的一維信道，大大簡(jiǎn)化了計(jì)算的復(fù)雜度，快速的用計(jì)算機(jī)線性規(guī)劃 尋找和優(yōu)化非規(guī)則的碼。 1 2 2 4l d p c 碼的應(yīng)用 由于低密度校驗(yàn)碼的優(yōu)異性能是最近才受到人們重視和熱點(diǎn)研究的。因此在，先 期的各種通信標(biāo)準(zhǔn)中，都采用的是同樣采用迭代譯碼算法的t u r b o 。比如在3 g 通信標(biāo) 準(zhǔn)中。但是l d p c 碼有其他任何碼都無法與相比較的優(yōu)勢(shì)：第一，l d p c 碼具有與碼長(zhǎng) 成線性關(guān)系的復(fù)雜度。第二，由于l d p c 碼迭代譯碼算法為并行算法，便于硬件實(shí)現(xiàn)。 第三，l d p c 碼的校驗(yàn)矩陣具有稀疏性，本身即有抗突發(fā)差錯(cuò)的特性，不需要引入交織 器，避免時(shí)延。這些優(yōu)點(diǎn)使得低密度校驗(yàn)碼的應(yīng)用前景廣闊。 1 3 論文的研究的主要內(nèi)容 第一章為緒論，闡述數(shù)字通信系統(tǒng)，回顧了信道編碼的發(fā)展歷程，概述了l d p c 碼 的分析方法和實(shí)際應(yīng)用情況。 第二章在回顧線性分組碼的基礎(chǔ)上，概述l d p c 碼的定義及表示方法，詳細(xì)闡述了 l d p c 碼的通用編譯碼方法，詳細(xì)闡述h 矩陣的構(gòu)造。 第三章在充分介紹了l d p c 碼的基礎(chǔ)知識(shí)上，詳細(xì)闡述了在d v b s 2 標(biāo)準(zhǔn)中采用的 l d p c 碼的特點(diǎn)及編碼方法，分析了其達(dá)到線性編碼復(fù)雜度的原因。最后，對(duì)符合 d v b s 2 標(biāo)準(zhǔn)的l d p c 碼編碼器設(shè)計(jì)進(jìn)行了初步設(shè)計(jì)。 第四章詳細(xì)闡述了l d p c 碼采用的譯碼算法及其簡(jiǎn)化算法的應(yīng)用研究。 第五章以符合d v b s 2 標(biāo)準(zhǔn)，碼長(zhǎng)為1 6 2 0 0 比特，碼率為1 4 的l d p c 碼為例，對(duì)前 面各個(gè)章節(jié)的理論進(jìn)行仿真驗(yàn)證。 5 第二章l d p c 碼的編譯碼原理 l d p c 碼是一種特殊的線性分組碼，可以用生成矩陣和校驗(yàn)矩陣來表征，其校驗(yàn)矩 陣具有低密度的特殊性；它又稱為稀疏圖碼，可以用與校驗(yàn)矩陣完全對(duì)應(yīng)的二分( t a n n c r ) 圖來表征。 2 1 線性分組碼概述 按照信息碼元和附加的監(jiān)督碼元之間的檢驗(yàn)關(guān)系可以分為線性和非線性碼，信息 碼元和監(jiān)督碼元之間的關(guān)系為線性關(guān)系，即監(jiān)督碼元是信息碼元的線性組合，則稱為 線性碼。反之，若兩者間不存在線性關(guān)系，則稱為非線性碼。我們有限域上討論線性 分組碼的構(gòu)造，具有口個(gè)元素的有限域用g f ( q ) 表示。g f ( q ) 上的n 維線性空間k 中的 一個(gè)k 維子空間k 。稱為( 以，七) 線性分組碼，編碼后總碼元數(shù)目為，l ，信息碼元數(shù)目為k ， 監(jiān)督碼元數(shù)目為，一n k 。編碼效率r = k n ，它是衡量糾錯(cuò)碼性能的一個(gè)重要指標(biāo)。 一般情況下，監(jiān)督位越多，檢糾錯(cuò)能力越強(qiáng)，但編碼效率也隨之降低。 對(duì)于二進(jìn)制( 以，七) 線性分組碼，信息數(shù)量為少個(gè)，可用編碼空間的點(diǎn)數(shù)為2 個(gè)，總 ，“、 共可能的編碼方案有i 。1 種。一個(gè)o ，七) 線性分組碼可以看作是由k 個(gè)線性無關(guān)的甩 2 維向量 g o ，g l , 既一。 作為基底的線性組合，寫成矩陣形式為： c 。m g( 2 1 ) g g o g l ： gk 一1 10 0 ；p o p o ，“1 風(fēng)一一l 0 1 o ；a p l j + 1 a ，l 一1 0 - - 1 ；仇一1 j 仇一1 + l 見一1 j l 一1 2 娃卅】 ( 2 2 ) m 為包含七個(gè)信息序列的分組 ，m k 一，) ；c 為編碼后的，l 維向量 c 0 ，c l ，q 一。) g 稱 為生成矩陣，為k x k 維單位矩陣，p 為n 0 一七) 維矩陣。這種形式的生成矩陣稱為 典型生成矩陣。g 中的每一行都是一個(gè)碼字，任意k 個(gè)線性無關(guān)的碼字都可以作為生 成矩陣。 將( 2 2 ) 式代入( 2 1 ) 式可得到： c = m g = m 【，p j 一 m o ，r ，l l ，m k - 1p o ，p l ，p 。一t l ( 2 3 ) ljt o vj 由典型生成矩陣得出的碼字c 中，信息位不變，監(jiān)督位附加于其后，這種碼稱為系統(tǒng)碼。 與生成矩陣g 對(duì)應(yīng)的校驗(yàn)矩陣h 由，行和n 列組成，每行代表一個(gè)線性監(jiān)督方程 的系數(shù)?？杀硎緸椋?6 h = 吃。?。?h 2 1h 2 2 h ，l 以2 k h 2 。 ： k ( 2 4 ) 與式( 2 2 ) 對(duì)應(yīng)的矩陣h 為：h ；卜，l j ，- u 是( 刀一七) 七維矩陣，它是p 矩陣 的轉(zhuǎn)置，”一”表示一，矩陣中的每一個(gè)元素是p 矩陣中對(duì)應(yīng)元素的逆元，在二進(jìn)制情況 下，仍是該元素本身。顯然，由此得到日滿足： 明r ；m h 。0 ( 2 5 ) l 1 一一七j 即g 與h 的行生成空間互為零空間。 任一矢量c 是許用碼字的充要條件為： h c r ；0 或胡r 一0 ( 2 6 ) 某一碼字中非零元素的個(gè)數(shù)稱為這個(gè)碼字的重量，簡(jiǎn)稱碼重。兩個(gè)碼字對(duì)應(yīng)位置 上不同元素的個(gè)數(shù)稱為碼組的距離，簡(jiǎn)稱碼距，又稱漢明( h 鋤m i n g ) 距離。各碼組間距 離的最小值稱為最小碼距，通常用d 。表示。d 。表明差錯(cuò)控帶i 。p - 力的下限，與信道編碼 的檢糾錯(cuò)能力密切相關(guān)，有以下三條結(jié)論： ( 1 ) 為檢測(cè)e 個(gè)誤碼，最小碼距應(yīng)滿足：d 。e + 1 ； ( 2 ) 為糾正t 個(gè)誤碼，最小碼距應(yīng)滿足：d 。之2 t + 1 ； ( 3 ) 為糾正f 個(gè)誤碼，同時(shí)能檢測(cè)e 個(gè)誤碼，最小碼距應(yīng)滿足：d 。e + f + 1 ( e f ) 。 如果用c 商。表示重量最小( d 耐。) 的碼字，根據(jù)( 2 6 ) 式可得到：c m i n h 丁一0 。由于線性 分組碼的最小重量等于最小碼距，故有監(jiān)督矩陣h 的d 。；。個(gè)列必然是線性相關(guān)的，也 就是日中線性無關(guān)的列最多不超過d 。；。一1 個(gè)。而h 的秩至多為以一k ，則必有 咒- k 苫d 。i 。- 1 ，因此d m i 。的上界為：d i i l i 。sn - k + 1 。 設(shè)發(fā)送碼字c 通過有擾信道傳輸，將發(fā)生錯(cuò)誤看成是模2 加入某種“錯(cuò)誤格式”e 的 結(jié)果，則接收碼字r = c + e 。每一碼字c 都必須滿足式( 2 6 ) 。因此，對(duì)接收到的碼字尺 進(jìn)行檢驗(yàn)： r i t r = ( c + e ) h r = c h r + e h r ；e h r( 2 7 ) 式( 2 7 ) 說明r h r 完全由錯(cuò)誤格式e 決定，而與發(fā)送的碼字無關(guān)，它充分反映了信 道的干擾情況。 令s = r h r = e h r ，稱為接收碼字尺的伴隨式( 或校正子) 。線性分組碼的伴隨式譯 碼可分為以下三步： ( 1 ) 由接收到的序列r ，計(jì)算伴隨式s = r h r ； ( 2 ) 若s = 0 ，r 為正確接收碼字：若s 不為零，尋找錯(cuò)誤格式； 7 ( 3 ) 由錯(cuò)誤格式解出碼字c = r e 。 若( 甩，七) 線性分組碼集合中的2 k 個(gè)碼字等概率發(fā)出，設(shè) c 為許用碼字集合，當(dāng)尺不 屬于 c 時(shí)，就判為錯(cuò)。然后將尺與 c 中所有碼字進(jìn)行漢明距離比較，選擇 c 中與尺 漢明距離最小的碼字作為發(fā)送碼字。這種通過選擇最小漢明距離來譯碼的方法，稱為 最大似然譯碼。 2 2l d p c 碼的定義及二分圖表示 l d p c 碼是一種特殊的線性分組碼，因而它可以用校驗(yàn)矩陣來定義。l d p c 碼的特 殊性在于其校驗(yàn)矩陣是“稀疏矩陣”：它的元素中，絕大多數(shù)元素是o ，只有很少一部分 元素是1 。根據(jù)稀疏矩陣中非零元素在行和列中的數(shù)目，可以將l d p c 碼分為規(guī)則l d p c 碼和非規(guī)則u ) p c 碼；而根據(jù)矩陣中組成元素，可以將l d p c 碼分為二元l d p c 碼和非二 元l d p c 碼，二元規(guī)則l d p c 碼是指其稀疏校驗(yàn)矩陣的元素在g f ( 2 ) _ l 取值，其每個(gè)碼元 參與j 個(gè)校驗(yàn)方程，而每個(gè)校驗(yàn)方程有k 個(gè)碼元參與，這樣定義的線性分組碼稱為二元規(guī) 則u ) p c 碼，記為( n ，j ，k ) 規(guī)則u ) p c 碼。圖2 1 為示例的規(guī)則( 1 2 ，3 ，6 ) l d p c 碼的校驗(yàn)矩陣。 h l d p c 碼除了可以用校驗(yàn)矩陣表示外，還可以用二部圖f 2 4 】表示， 部圖如圖2 1 所示： 8 ( 2 8 ) 上面的( 1 2 ，3 ，6 ) 規(guī)則二 o 0 1 0 1 1 0 1 0 0 1 1 1 0 0 0 1 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1 o 0 1 1 1 0 o 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 1 1 0 圖2 1 ( 1 2 ，3 ，6 ) 規(guī)則l d p c 碼二部圖表示 圖2 1 中的節(jié)點(diǎn)分為兩類：左邊的節(jié)點(diǎn)稱為變量節(jié)點(diǎn)，每個(gè)變量節(jié)點(diǎn)對(duì)應(yīng)l d p c 碼的 一個(gè)碼元，其個(gè)數(shù)等于碼長(zhǎng)n ，也等于校驗(yàn)矩陣的列數(shù)；右邊的節(jié)點(diǎn)稱為校驗(yàn)節(jié)點(diǎn)，與 校驗(yàn)方程對(duì)應(yīng)，其個(gè)數(shù)等于校驗(yàn)方程的個(gè)數(shù)，也等于校驗(yàn)矩陣的行數(shù)。如果第i 個(gè)碼元 參與了第j 個(gè)校驗(yàn)方程，就用一條邊將變量節(jié)點(diǎn)k 和校驗(yàn)節(jié)點(diǎn)c ，相連。與一個(gè)節(jié)點(diǎn)相連 的邊數(shù)稱為這個(gè)節(jié)點(diǎn)的度。 從二部圖的觀點(diǎn)來看，一個(gè)規(guī)則u ) p c 碼相同類型的節(jié)點(diǎn)( 變量節(jié)點(diǎn)或校驗(yàn)節(jié)點(diǎn)) 具 有相同的度，而對(duì)非規(guī)則l d p c 碼而言，變量節(jié)點(diǎn)( 或檢驗(yàn)節(jié)點(diǎn)) 的度不再是相同的，而 是服從某個(gè)度分布。從校驗(yàn)矩陣的觀點(diǎn)來看，一個(gè)規(guī)則的l d p c 碼具有相同的行重和相 同的列重，而對(duì)于非規(guī)則l d p c 碼來說，各行的行重是不相同的，各列的列重也是不相 同的。對(duì)于非規(guī)則l d p c 碼可以用兩類節(jié)點(diǎn)的度分布來表示。假設(shè)變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn) 的度分布函數(shù)分別為： d ， a ( x ) 一羅叫以 ( 2 9 ) 怒 以 p ( x ) ；羅p f 工 ( 2 1 0 ) 矩 其中 表示二部圖中，從度為i 的變量節(jié)點(diǎn)出發(fā)的邊在全部邊中所占比例，西，表示 變量節(jié)點(diǎn)的最大度；p ；表示二部圖中，從度為，的校驗(yàn)節(jié)點(diǎn)出發(fā)的邊在全部邊中所占 比例，d ，表示校驗(yàn)節(jié)點(diǎn)的最大度。 如果設(shè)n i 表示度數(shù)為i 變量節(jié)點(diǎn)的個(gè)數(shù)，m ，表示度數(shù)為f 的校驗(yàn)節(jié)點(diǎn)的個(gè)數(shù)，而e 表示二部圖中邊的總數(shù)，那么在給定l d p c 碼碼長(zhǎng)n 及度分布( a ( x ) ，p ( 工) ) 的條件下， 我們可以計(jì)算t z i ，m ；，e 如下： 9 q ； 岱 1 2 3 4 5 6 7 8 9 1 1 1 v v v v v v v v v v v v 驢蘇州蓋 億1 1 ) e 2 薈i v 。高耋 。兩n ( 2 1 2 ) 如果設(shè)m 為校驗(yàn)節(jié)點(diǎn)的總數(shù)，那么 m 蘇州茄 q 1 3 ) 同樣，我們可以計(jì)算得到 e 5 薈d 。兩m 薈d , 以2 兩m 所以有 m ；卑絲( 2 均 a ( x 渺 因而，對(duì)于度分布函數(shù)為( a ( z ) ，p ( z ) ) 的l d p c 碼，其設(shè)計(jì)碼率r 為： r ；下n - m = 1 _ 擎蘭 ( 2 1 6 ) j ：a ) d x 、 從上面的公式可以看出，u ) p c 碼的設(shè)計(jì)碼率是f h l d p c 碼度分布函數(shù)決定的。 二元l d p c 碼是由一個(gè)稀疏的0 1 矩陣定義的。一個(gè)碼字是合法的，當(dāng)且僅當(dāng)它與 校驗(yàn)矩陣的乘積在模2 加法和乘法下是一個(gè)全o 向量。d a v e y 和m a c k e y 將二元u ) p c 碼推 廣到了一般有限域g f ( q ) 上。g f ( q ) 上u ) p c 碼同樣由一個(gè)相似的“稀疏”校驗(yàn)矩陣定義， 只是校驗(yàn)矩陣中的元素是a k g f ( q ) i - _ i 玟值。一個(gè)碼字是合法的，當(dāng)且僅當(dāng)其與校驗(yàn)矩陣 的乘積在g f ( q ) 上的加法和乘法運(yùn)算下為全零向量。 從直觀上來看，非規(guī)則l d p c 碼的性能優(yōu)于規(guī)則l d p c 碼。這是因?yàn)樵谧兞抗?jié)點(diǎn)和 校驗(yàn)節(jié)點(diǎn)總數(shù)一定時(shí)，度數(shù)大的變量節(jié)點(diǎn)從校驗(yàn)節(jié)點(diǎn)得到的校驗(yàn)信息較多，因而能夠 更好的被正確譯碼，這些譯碼信息經(jīng)校驗(yàn)節(jié)點(diǎn)提供給度較小的變量節(jié)點(diǎn)，使度較小的 變量節(jié)點(diǎn)也能更好的被譯碼。理論分析和仿真結(jié)果證明了這一點(diǎn)。對(duì)g f ( q ) 上的l d p c 碼，已有結(jié)果證明其性能較二進(jìn)制碼為優(yōu)。在l d p c 碼的直接編碼方式中，構(gòu)造稀疏校 驗(yàn)矩陣h 是首要的問題。下面介紹幾種校驗(yàn)矩陣h 的生成算法。 2 3 校驗(yàn)矩陣h 的構(gòu)造 2 3 1 矩陣h 的半隨機(jī)( s e m i r a n d o m ) 構(gòu)造算法 1 0 矩陣h 的半隨機(jī)構(gòu)造算法可以概括為以下步驟： ( 1 ) 系統(tǒng)首先生成一個(gè)m 以維的全o 矩陣，然后隨機(jī)的往每列插入j 個(gè)1 ； ( 2 ) 調(diào)整行重，使行重盡量保持一致； ( 3 ) 調(diào)整列中1 的位置，使得相鄰兩列1 的位置在行上不重疊； ( 4 ) 消除矩陣中的短循環(huán)。 這種算法的運(yùn)算量比較大，有時(shí)會(huì)不收斂，需要更換隨機(jī)數(shù)種子。構(gòu)造出的矩陣 不一定是規(guī)則的，還需要進(jìn)一步處理使行重盡可能達(dá)到一致。l d p c 碼在短幀傳輸情況 下，出現(xiàn)長(zhǎng)度為4 的環(huán)( 記為4 環(huán)) 的概率比較大，所以必須反復(fù)地掃描h ，直到所有4 環(huán)都被消除。并且要避免與變量節(jié)點(diǎn)連接的校驗(yàn)節(jié)點(diǎn)過于集中。在消除短環(huán)過程中， 有兩種矩陣h 的生成方式： ( 1 ) 矩陣日的c v c n b o t h 生成方式 在這種生成方式中，要嚴(yán)格保持矩陣h 的列和行的重量分別為_ | 和k 。在消去短環(huán) 過程中，移動(dòng)矩陣日中某個(gè)1 后，相應(yīng)地該行或列的重量減一，而另一行或列的重量增 一。再?gòu)闹亓吭黾拥男谢蛄衅渌恢蒙系? 中選擇一個(gè)，調(diào)回到原有的行或列中，以使 每行和每列的重量保持一致。然后重新檢查此時(shí)的矩陣日是否出現(xiàn)新環(huán)，若有則重復(fù) 上述步驟。 ( 2 ) 矩陣h 的e v e n c o l 生成方式 在這種生成方式中，只保證列的重量固定不變，即每個(gè)變量節(jié)點(diǎn)受到的約束程度 是一樣的。允許一部分行的重量稍微大些或小些，平均行重量在k 附近即可。在消去短 環(huán)過程中，系統(tǒng)將某個(gè)1 在某列內(nèi)上下移動(dòng)，即迫使該變量節(jié)點(diǎn)從一個(gè)校驗(yàn)方程切換到 另一個(gè)校驗(yàn)方程。此變量節(jié)點(diǎn)參與的校驗(yàn)方程的個(gè)數(shù)并沒有改變，并沒有放松對(duì)該碼 字的約束。然后重新檢查此時(shí)的矩陣h 是否出現(xiàn)新環(huán)，若有則重復(fù)上述步驟。 在e v e n b o t h 方式下，強(qiáng)制每個(gè)校驗(yàn)方程監(jiān)督相同數(shù)量的比特；e v e n c o l 方式則允許一 部分校驗(yàn)方程的約束范圍稍大，一部分較小。對(duì)于這兩種生成方式，二分圖中邊的條 數(shù)是非常接近的。 2 3 2 矩陣h 的p e g ( p r o g r e s s i v ee d g e g r o w t h ) 算法 p e g 算法是一種構(gòu)造二分圖的簡(jiǎn)單有效方法，它以保持盡可能大的g i r t h 為目的，逐 個(gè)增加變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)的邊。具體操作可描述為：給定變量節(jié)點(diǎn)的數(shù)目n 、校驗(yàn)節(jié) 點(diǎn)的數(shù)目m 和變量節(jié)點(diǎn)的分布序列后，邊選擇程序開始放置新的邊，選擇新邊時(shí)保證 盡可能對(duì)g i r t h 影響較?。恍逻叿胖煤煤?，繼續(xù)搜索下一個(gè)邊，直到結(jié)束。 p e g 算法不但適用于規(guī)則u ) p c 碼的構(gòu)造，也可應(yīng)用于非規(guī)貝d j l d p c 碼的構(gòu)造。它 具有較好的實(shí)用性，能構(gòu)造g i r t h 為8 、( 1 0 0 8 ，3 ，6 ) 的l d p c 碼。p e g 算法構(gòu)造的中、短 長(zhǎng)度的l d p c 碼是當(dāng)前所知具有相同參數(shù)的最好的l d p c 碼之一。 2 3 3 矩陣h 的比特填充( b i t f i l l i n g ) 算法 比特填充算法能設(shè)計(jì)出二分圖中最小環(huán)長(zhǎng)較大的( 以，k ) 形式的l d p c 碼。在給定 校驗(yàn)矩陣h 的列重j 、行重七、g i r t h 為g 和正整數(shù)，l 。( n 。 r 1 ) 時(shí)，也可設(shè)計(jì)出校驗(yàn)節(jié)點(diǎn)數(shù) 目m 較小，即碼率較大的非規(guī)則l d p c 碼。比特填充算法可描述如下： ( 1 ) 假設(shè)己得到行重均小于等于k 的矩陣h ，再增加第n 。+ 1 列到矩陣日上； ( 2 ) 設(shè)第+ 1 列的列重為j ，并初始為空集合u ，它是以校驗(yàn)節(jié)點(diǎn)為元素的一個(gè) 集合，是 1 ，2 ，m 的一個(gè)子集； ( 3 ) 進(jìn)一步假設(shè)已經(jīng)增加了i 個(gè)校驗(yàn)節(jié)點(diǎn)到u 集合里( 1 f 6 ，則反轉(zhuǎn)比特乙 ( 3 ) 重復(fù)步驟1 和步驟2 直到s ；0 或達(dá)到最大迭代次數(shù)。 當(dāng)參與每一個(gè)校驗(yàn)方程的比特?cái)?shù)都很少且誤碼率不是很高時(shí)，比特反轉(zhuǎn)譯碼方法 是比較有效的。 2 5 2 軟判決譯碼算法b e l i e fp r o p a g a t i o n ( b p ) 置信傳播算法b p ( b e l i e fp r o p a g a t i o na l g o r i t h m ) 是一類較重要的消息傳播算法，算 法中各個(gè)節(jié)點(diǎn)之間傳遞的信息是概率或置信信息，如由變量節(jié)點(diǎn)m 傳遞給校驗(yàn)節(jié)點(diǎn)c ； 的信息是u 取某些值的概率信息，該信息的具體取值依賴于”的觀察值和其他所有與k 相連的校驗(yàn)節(jié)點(diǎn)( c ；除外) 在上一輪傳遞給k 的置信信息，同樣，由c ；傳遞給u 的信息也 是c ，取某些特定值的概率信息，該信息的取值依賴于c ，的觀察值和其他所有與c ；相連 的信息節(jié)點(diǎn)( k 除外) 在上一輪傳遞給c i 的置信信息。我們首先介紹兩個(gè)與b p 算法密切 相關(guān)的定理： 1 3 定理1 ：假設(shè)m 個(gè)獨(dú)立的二進(jìn)制數(shù)口一( a l , 口：，口。) 中p ( 吼一1 ) 一p k 。則序列口中有 偶數(shù)個(gè)1 的概率為：丟+ 三n ( 1 2 仇) ，有奇數(shù)個(gè)1 的概率為丟一三n ( 1 2 仇) 。 定理2 ：假設(shè)y i 一五+ ，其中n i 是滿足( o ，口2 ) 分布的高斯隨機(jī)變量，并且 p ( 毛2 1 ) 目o 5 ，p ( 2o ) = o 5 ，貝op ( 而。x i 咒) 5 i ：麗1 ( x 一1 ，1 ) ) 我們定義編碼后產(chǎn)生的碼字中第i 個(gè)比特弓的后驗(yàn)概率為： p ( 乞- l r ，s i ) ( 2 1 8 ) 式中】，是接收序列，s 表示事件：乙所參加的校驗(yàn)式都成立。由條件概率的定義和b a y e s 公式，我們可以得到乞的后驗(yàn)概率比為： 矧= 躺描；等舞警仁1 功可i 而可2 可諏j 可瓦f 兩2 瓦i 兩i u j ” 其中，p i ；p ( 毛- l l y ；) ；n p ( s , l z , 一o ，y ) 表示的是給定y 和乞一。的情況下，乙 參加的所有校驗(yàn)式均成立的概率，因此，也就相當(dāng)于每個(gè)校驗(yàn)式中除了毛，其他比特 為1 的個(gè)數(shù)為偶數(shù)的概率。由定理1 可知： p ( 北地y ) 2 日，p 覘v1 - 2 p v - ，) ( 2 2 0 ) 式中忍一p ( 五j 一1 k j ) ，弓，是碼字中與第j 個(gè)校驗(yàn)式的第f 個(gè)位置相對(duì)應(yīng)的比特。y i ， 是與z i j 相對(duì)應(yīng)的接收符號(hào)。同理： p ( 墨i z i = 1 , y ) 2 凰爭(zhēng)j 1 ；覡v ( 1 嘲講 ( 2 2 1 ) 將式( 2 2 0 ) 和式( 2 2 1 ) 代入式( 2 1 9 ) 中，我們得到： 垂三竺；隨2 ；垃 p ( 乞= 1j y ，s ) 只 熙卜職v ( 1 - 2 叫 ( 2 2 2 ) 直接計(jì)算式( 2 1 9 ) 比較困難，g a l l a g e r 給出了一種迭代算法求解式( 2 1 9 ) 。 定義兩個(gè)變量：q i ，( b ) 和，( b ) 。q i ，( b ) 是從變量節(jié)點(diǎn)u 傳遞個(gè)校驗(yàn)節(jié)點(diǎn)c 的軟信 息，表示的是給定y i ，并且除了第，個(gè)校驗(yàn)式以外的所有校驗(yàn)式都滿足的條件下，乞= 6 的概率。( 6 ) 是從校驗(yàn)節(jié)點(diǎn)傳遞c j 給變量節(jié)點(diǎn)u 的軟信息，表示的是在弓= 6 、參加 第，個(gè)校驗(yàn)式的其他比特滿足概率級(jí)，( 6 ) ( i i ) 的條件下，該校驗(yàn)式成立的概率。通過 1 4 上面的定義我們可以很容易的得到q i ，( b ) 和j ( b ) 的計(jì)算公式： 吒印) 2 五1 + 三；夙( 1 嘞舢) ) ( 2 2 3 ) 刑4 j 1 一云1 ；目v ( 1 一刺) ( 2 2 4 于是式( 2 1 9 ) 改寫為： 矧；鬻 仁2 5 ， 碉2 了廝礦 弘z 吼加) 2 ( 1 一剛，取，) ( 2 2 6 ) 吼，( 1 ) - - k i j p l “1 ) ( 2 2 7 ) 常數(shù)是用來保證仍，( o ) + 呸j ( 1 ) ；1 。根據(jù)上面對(duì)概率域上的b p 算法每一個(gè)變量 ( 1 ) 初始化：由定理2 得到，呸。( o ) 。p r 1 l m ) 2 i i 磊1 萬，呸，。( o ) = 1 一吼，。( 1 ) 初 ( 2 ) 根據(jù)式( 2 2 3 ) 和式( 2 2 4 ) 計(jì)算出從校驗(yàn)節(jié)點(diǎn)傳遞給變量節(jié)點(diǎn)的軟信息0 ；。 ( 3 ) 根據(jù)式( 2 2 6 ) 和式( 2 2 7 ) 計(jì)算出從變量節(jié)點(diǎn)傳遞給校驗(yàn)節(jié)點(diǎn)的軟信息劬 ( 4 ) 我們根據(jù)式( 2 2 5 ) 計(jì)算乙的后驗(yàn)概率：q j ( o ) tk ( 1 一a ) n 、o ( o ) q ：f ( 1 ) = k b - 互( 1 ) ，常數(shù)t 保證q ( o ) +目1arji q i ( 1 ) 5 對(duì)q c 1 ，進(jìn)行硬判決，產(chǎn)生譯碼結(jié)果三；一仁璽曷二慧將得到的譯碼 結(jié)果序列2 左乘校驗(yàn)矩陣，獲得各個(gè)校驗(yàn)式的校驗(yàn)結(jié)果：s ；( ，0 ，) 。 g a l l a g e r 證明，如果校驗(yàn)矩陣h 中沒有閉合環(huán)路，當(dāng)?shù)螖?shù)趨向無窮大時(shí)，q ( 1 ) 1 5 第三章d v b s 2 中l(wèi) d p c 碼線性時(shí)間編碼 l d p c 碼譯碼性能優(yōu)良，算法簡(jiǎn)單。但面臨的一個(gè)主要問題就是其較高的編碼復(fù)雜 度和編碼時(shí)延。若按照常規(guī)線性分組碼的編碼方法，通過先得到生成矩陣來編碼，涉 及到求解奇偶校驗(yàn)方程組的復(fù)雜問題，而且對(duì)于生成矩陣g 并不能保證它是稀疏矩陣， 通過這樣的方法來編碼，算法復(fù)雜度是碼長(zhǎng)的指數(shù)關(guān)系。這嚴(yán)重制約了l d p c 碼的應(yīng)用， 然而學(xué)者t j r i c h a r d s o n 和r l u r b a n k e 在陋l 文獻(xiàn)中指出，對(duì)l d p c 碼的校驗(yàn)矩陣h 進(jìn)行一 定的預(yù)處理后，l d p c 碼編碼器的計(jì)算復(fù)雜度與分組碼長(zhǎng)度成線性關(guān)系。實(shí)際上，有效 的l d p c 碼編碼器的設(shè)計(jì)是可行的，編碼器算法復(fù)雜度比譯碼器算法復(fù)雜度還要小。 3 1l d p c 碼的線性時(shí)間編碼 3 1 1 基于準(zhǔn)下三角校驗(yàn)矩陣的l d p c 線性編碼 在l d p c 碼的校驗(yàn)矩陣h 中，在h 中非零元素的個(gè)數(shù)是碼長(zhǎng)的幾倍到幾十倍，它 們之間是線性關(guān)系。如果能很好的利用校驗(yàn)矩陣的稀疏性，那么運(yùn)算復(fù)雜度只和矩陣h 中非零元素的個(gè)數(shù)有關(guān)，就可以實(shí)現(xiàn)線性時(shí)間編碼。根據(jù)這種思路，我們采用了 r i c h a r d s o n 等提出的利用準(zhǔn)下三角校驗(yàn)矩陣實(shí)現(xiàn)線性時(shí)間內(nèi)編碼的方法。 為了保持校驗(yàn)矩陣h 的稀疏性，僅對(duì)矩陣h 執(zhí)行行列置換，得到圖3 1 所示 圖3 1 具相卜二用彤瓦網(wǎng)枚驗(yàn)矩陣 更確切地將矩陣表示成如下形式： h ，佇b nt f l ( 3 1 ) 4 icdej ( 3 j 其中a 為( 所一g ) ( 萬一所) 維，b 為( ，t g ) x g 維，t 為( 聊- g ) x ( m g ) 維，c 為g ( 忍一所) 維，d 為gx g 維，e y - - j gx ( m - g ) 維，這些矩陣都是稀疏的，t 是左上至右下對(duì)角線上 為1 的下三角矩陣。用