（通信與信息系統(tǒng)專業(yè)論文）低密度校驗碼的性能分析及其量化譯碼.pdf

摘要 低密度校驗碼是一種能逼近s h 咖o n 容量限的漸進(jìn)好碼 在長碼時其性能甚 至超過了t u r b o 碼 它的譯碼采用的是基于置信傳播的軟輸出迭代譯碼算法 復(fù)雜 度很低 是一種次優(yōu)的譯碼算法 由于低密度校驗碼具有諸多優(yōu)點 它在信息可 靠傳輸中的良好應(yīng)用前景已經(jīng)引起學(xué)術(shù)界和i t 業(yè)界的高度重視 成為當(dāng)今信道編 碼領(lǐng)域最受矚目的研究熱點之一 低密度校驗碼的應(yīng)用也已經(jīng)被提到日程上 作者在理解u p c 碼基本編譯碼理論的基礎(chǔ)之上 深入分析了影響l i p c 碼 性能的因素 并研究了采用最小和算法u p c 碼的量化譯碼方案 本文主要完成的工作有以下幾個方面 1 基于因子圖模型 介紹了u p c 碼的表示和構(gòu)造 詳細(xì)介紹了u p c 碼基 于多種測度的軟判決迭代譯碼 和積算法和最小和算法 2 概括了影響u p c 碼性能的主要因素 分析了度序列對長碼性能的影響 介紹了結(jié)合密度進(jìn)化 高斯逼近 和差分進(jìn)化優(yōu)化高斯信道下度序列的方法 分 析了環(huán)對中 短碼性能的影響 介紹了p e o 構(gòu)造方法 最后分析了u p c 碼錯誤 平層產(chǎn)生的原因 介紹并仿真了能有效的降低l d p c 碼錯誤平層的a c e 算法 3 研究了u p c 碼的量化譯碼 提出了一種基于密度進(jìn)化理論優(yōu)化設(shè)計低密 度校驗碼最小和量化譯碼器的算法 該算法能夠大大降低譯碼復(fù)雜度 同時譯碼 性能損失很小 u p c 碼的實用化還要走較長的一段路 雖然u p c 碼的性能優(yōu)越 但是編碼 問題一直很難解決 因此 u p c 碼的編碼方面還需要進(jìn)一步研究 如碼的構(gòu)造及 線性編碼問題 量化譯碼也是l d p c 碼實用化過程中的關(guān)鍵問題 本文僅對u p c 碼量化譯碼做了粗淺的研究 如何設(shè)計一個復(fù)雜度低但性能好的量化譯碼器是值 得研究的 關(guān)鍵詞 低密度校驗碼性能分析量化譯碼 a b s t r a c t l o w d e n s i t yp a f i t y c h e c k u p c c o d e sa r eac l a s so fc a p a c i t ya p p r o a c l l i n g e n d r c o e c t i n gc o d e s b yu s i n g l o wc o m p i e x i t y a 1 9 0 r i t h m sb a s e d o nb e l i e f p r o p a 鯽i o n l d p c d e sc 柚g e tn e a rs h a i l n o nl i m i td e c o d i n gp e r f o m a n c e f o rl o n g c o d e1 朋g t b s l p cc o d e s c a ne v e no u 啦面瑚n r b oc o d e s d u ef o 齜a d v a n a g c so f u p cc o d e s t h e i ra p p l i c a t j o n si nr e l i a b l ec o m m u n i c a t i o n sh a v er e c e i v e dg r e a t i n t e r e s t s a n dh a v eb e c o m eo n eo fm o s ta t t r a d i v ef i e l di nc h a n n e lc o d i l l gc o m m u n i t y n o w t h e a p p l i c a t i o no fl r d p ch a sb e e np u to nt h ea g e n d a t 1 l i st h e s i s i n v e s t i g a t e ss o m ea s p e c t s o fl d p cc o d e sw i t h e m p h a s i s o n p e r f o r m 卸c ea n a l y s i sa n dq u 柚t j z a t i o nd e d i n gs c h e m e so fu p cc o d e s t h em a i n i e s u l t sa n dc o n t e n t sa r ea sf o n o w s 1 b a s e do nf a c t o r 胂p h t h er e p f e s e n t a t i o na n dc o n s t n l c t i o no fu p cc o d e sa r e a d d r c s s e d a i l dt h es o f td e c o d i n ga l g o r i t h mf o ru d p cc o d e s i e s u m p r o d u c ta 1 9 0 椰h m a n dm i n i m u m s u ma i g o r i t h m a r ed i s c u s s e d 2 確em a j o rf a c t o r sw h i c hi m p a dl d p cc o d e s p e 渤鋤a n c ca r es u 蛐a r i z e d a m a l y z i l l g h ej m p a c to fd e g r e ed i s 砸b u t j o n o nt h el 冊爭l e n g t hu p c0 0 d e s 鋤d i n t r o d u c i n gt h eo p t i l l l i z e dd e 辨ed i s t 抽u t i o na l g o r i t h mu n d e rt h ea w g n c h 蛐n e lb 弱e d o nd e n s i t ye v o l u t i o no rg a u s s i 鋤a p p m x i m a t i 伽a l l dd i f f e r c n t i a le v o l u t i o n t 1 l ei m p a c t o fc y d e so nt h es h o n l e n 垂hu p co o d e si s 柚a l y z e d 柚dt h cp e ga l g o r i t h mi s i n t m d u c c d t h ea c ea l g o 血h mw h i c hc a i ld e g m d et h ee o rf i re f f i d e n n yi s i n t r o d u c e d 3 q u a n t i z a t i o n d e c o d i n g o fm p cc o d e si ss t u d i e d a j le 衢c i e n t q u a n t i z a l i o n d e c o d i n gs c h e m ci sp r o p o s e dw h i c hc a ng f c a t l yr e d u c et h ed e c o d i n g m p l e x n y w i t hal i t t l ep e r f 佃咀柚c el o s s a l t b o u g hl o n gl d p c c o d e sa r eg o o d t h ee n c o d i n gp m b l e mj sh a f dt os o i v e s o t h es t u d yo fe n c o d i n ga n dq u a n t i z a t i o nd e c o d i n ga l g o r i t h mi se s s e n t i a lt ot h ep r a c t i c a l u s e k e y w o r d s l o w d e n s 咿p a r i 姆一c h e c k l d p c c o d e sp e r f b m a n a n a l y s i s q u a n z a 廿o nd e c o d i n g 創(chuàng)新性聲明 本人聲明所呈交的論文是我個人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究 成果 盡我所知 除了文中特別加以標(biāo)注和致謝中所羅列的內(nèi)容以外 論文中不 包含其他人已經(jīng)發(fā)表或撰寫過的研究成果 也不包含為獲得西安電子科技大學(xué)或 其它教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料 與我一同工作的同志對本研究所做 的任何貢獻(xiàn)均已在論文中做了明確的說明并表示了謝意 申請學(xué)位論文與資料若有不實之處 本人承擔(dān)一切相關(guān)責(zé)任 本人簽名 l 瓣 日期 關(guān)于論文使用授權(quán)的說明 砷 6 耳l 冉 本人完全了解西安電子科技大學(xué)有關(guān)保留和使用學(xué)位論文的規(guī)定 即 研究生在校攻讀學(xué)位期間論文工作的知識產(chǎn)權(quán)單位屬西安電子科技大學(xué) 本 人保證畢業(yè)離校后 發(fā)表論文和使用論文工作成果時署名單位仍然為西安電 子科技大學(xué) 學(xué)校有權(quán)保留送交論文的復(fù)印件 允許查閱和借閱論文 學(xué)校 可以公布論文的全部或部分內(nèi)容 可以允許采用影印 縮印或其它復(fù)印手段 保存論文 保密的論文在解密后遵循此規(guī)定 本人簽名 導(dǎo)師簽名 日期型1 6 量lb 日期趟笸 f 壟 一 笙二里墮笙 第一章緒論 本章簡要介紹了數(shù)字通信與信道編碼的關(guān)系 回顧了信道編碼理論與技術(shù)的 發(fā)展歷程 給出了常見的幾種信道模型及其容量計算 結(jié)合圖模型的發(fā)展歷程概 述了l i p e 碼的歷史和現(xiàn)狀 最后總結(jié)了作者在攻讀碩士期間所做的主要工作并給 出了本文內(nèi)容安排 1 1 數(shù)字通信與信道編碼 通信系統(tǒng)旨在將信息由信源高效 可靠 有時還需安全地傳送到信宿 有擾 通信信道的噪聲會對傳輸信息產(chǎn)生干擾 從而可能降低通信可靠性 所以 通信 系統(tǒng)設(shè)計的中心問題是在隨機(jī)噪聲干擾下如何有效而可靠地傳輸信息 一般地 通信系統(tǒng)的可靠性用錯誤比特率 b e r 衡量 有效性用傳輸速率r 比特 信道符號衡 量 早期的人們普遍認(rèn)為 通信系統(tǒng)的可靠性與有效性是一對不可調(diào)和的矛盾 在有擾通信信遴上實現(xiàn)任意小錯誤概率的信息傳輸?shù)奈ㄒ煌緩骄褪前褌鬏斔俾式?低至零吲 s h 柚n o n 信息和編碼理論的奠基性論文 通信的數(shù)學(xué)理論 1 于1 9 4 8 年發(fā) 表之后 改變了這一觀念 他首次闡明了在有擾信道中實現(xiàn)可靠通信的方法 指 出實現(xiàn)有效而可靠地傳輸信息的途徑是編碼 在這篇論文中s h 枷咖證明了數(shù)據(jù)壓 縮和傳輸?shù)幕径蓮亩於?信息理論的基石 s h a 蚰o n 也因此被稱為 信息論 之父 根據(jù)s h 卸n o n 的信息理論 數(shù)字通信系統(tǒng)的基本組成如圖1 1 所示 3 j 一 聃l 亟刊刪信進(jìn) 編碼信道 圖1 1 數(shù)字通信系統(tǒng)的模型 一般的通信系統(tǒng)均可以用圖1 1 來表示 如果將存儲介質(zhì)看成信道的話 存儲 系統(tǒng)也可以用上述模型表示 這時數(shù)字調(diào)制 解調(diào)器分別對應(yīng)于寫入 寫出單元 堡重堡墮鱉旦塑垡堂坌塑墾苧壁垡堡塑 如上圖所示 發(fā)送端包含四個模塊 信源 信源編碼 信道編碼和數(shù)字調(diào)制器 信源編碼就是用二進(jìn)制 或多進(jìn)制 序列束表示信源輸出的過程 其目的是除去 信源的冗余以減少通信負(fù)擔(dān) 因而也稱為數(shù)據(jù)壓縮 任何信源都有一個被稱為信 源熵的量 它表征了信源的平均不確定程度 信源編碼定理 4 指出信源熵是數(shù)據(jù)壓 縮的下界 信道編碼與信源編碼正相反 它通過在信息序列中引入冗余來實現(xiàn)通 信的可靠性 任何信道都存在一個被稱為信道容量的值 它表征了信道的傳輸能 力 數(shù)字調(diào)制就是將信息序列映射成適合信道傳輸?shù)男盘柕倪^程 對應(yīng)地在接收 端也有相應(yīng)的四個模塊用于實現(xiàn)相反的過程 由于噪聲是影響通信可靠性的關(guān)鍵因素 一個自然的想法是構(gòu)建可靠的信道 以減少噪聲 但是這種想法在很多情況下是無法實現(xiàn)的 而且也沒有必要 r e b l a h u t 曾指出 與其花費大量的金錢去建造一條好的通信信道不如采用信道編 碼 因此 從通信系統(tǒng)的經(jīng)濟(jì)性角度考慮信道編碼也是必不可少的 綜上所述 信道編碼是解決通信有效性和可靠性這對矛盾的關(guān)鍵 也是實現(xiàn) 通信系統(tǒng)經(jīng)濟(jì)性所必需的 但是 s b a l l n o n 在 1 中關(guān)于信道編碼定理的證明是存在 性的 因而如何在實際系統(tǒng)中實現(xiàn)信道編碼仍然是一個難題 定理1 1 信道編碼定理 5 l 任意離教輸入無記憶平穩(wěn)有噪信道都有一個被稱為信道容量的值c 它標(biāo)志 著信道傳輸能力的上限 只要信息傳輸速率r c 就存在一種編碼方式 當(dāng)平均 碼長足夠大時 譯碼錯誤概率可以做到任意小 反之 則無論采用何種編碼方式 也不可能保證錯誤概率任意小 信道編碼定理和信源編碼定理 率失真理論一起構(gòu)成了s h a i l n o n 三大編碼定 理 s h a i l n o n 在證明上述信道編碼定理時采用了三種技術(shù) 1 編碼采用了隨機(jī)編碼思想 2 1 讓碼長趨于無窮 3 1 譯碼采用了最大似然譯碼 1 2 使得碼本身具有卓越的糾錯性能 而3 中的最大似然譯碼使得碼的糾錯 性能得以從分發(fā)揮 但是 采用隨機(jī)編碼 使碼長趨于無窮大并且采用最大似然 譯碼將會使系統(tǒng)的復(fù)雜度和延時變得太大 因而無法在實際中使用 在半個多世 紀(jì)的編碼發(fā)展歷程中 從h 撇m i n g 碼 b c h 碼 r s 碼 r m 碼 卷積碼 級聯(lián)碼 代數(shù)幾何碼到逼近容量限的1 l r b o 碼和u p c 碼 數(shù)學(xué)家和信息理論專家們?yōu)榱诉_(dá) 到s h a n n o n 容量限作了不懈的努力 在編碼理論的最初階段 人們一直傾向于用代 數(shù)方法來實現(xiàn)差錯控制編碼 有限域 數(shù)論和有限幾何等數(shù)學(xué)理論成了編碼理論 的主要工具 然而有趣的是 最終能夠逼近s h a n n o n 容量限的t u r b o 碼和u p c 碼都 部分地引入了隨機(jī)編碼的思想 t u r b 0 碼的交織器和l d p c 碼的稀疏校驗矩陣 并 第一章緒論 且它們的碼長都較長 譯碼均采用了近似最大后驗概率譯碼 當(dāng)輸入等概時 最 大后驗概率譯碼等價于最大似然譯碼 的迭代譯碼算法 換句話說 s h a n n o n 在證 明信道編碼定理的三種技術(shù)在最終逼近容量限的t u f b o 碼和u p c 碼中都有所體 現(xiàn) 1 2 信道模型和信道容量 信道就是信息傳輸?shù)拿劫|(zhì) 如圖1 1 所示 按照功能不同 信道可以分為調(diào)制 信道和編碼信道1 6 j 這里只考慮編碼信道 假定平穩(wěn)無記憶信道的輸入取自m 元符號集合 信道的輸出取自q 元符號集 合 在數(shù)字通信的接收端 解調(diào)器對接收波形進(jìn)行處理 將受擾波形轉(zhuǎn)換成一個 標(biāo)量或向量作為對傳輸數(shù)據(jù)的估計值 并將它送入判決器進(jìn)行判決 判決輸出q 元 符號 實際上 可以將判決過程看成是 種量化過程 而判決器輸出所采用符號 集的大小對應(yīng)為量化級數(shù) 當(dāng)量化級數(shù)q 一 f 時 稱判決器作了一次硬判決 當(dāng) 量化級數(shù)q m 時 我們稱判決器作了一次軟判決i 引 判決器的輸出將作為譯碼器 的輸入 1 2 1 幾種常見的信道模型 1 2 1 1 二進(jìn)制對稱信道 m n a f ys y 秈e 倒cc h a n n e i b s c 考察一個二元輸入加性噪聲信道 令判決器作硬判決 如果信道噪聲造成的 錯誤是統(tǒng)計獨立的 平均錯誤概率為p 那么可以用如下的轉(zhuǎn)移概率來描述這個 信道的統(tǒng)計特性 囂 收茹囂嘗 昌 p m p y 1 l x t l p 一0 l x o t 1 一p 7 我們稱這種信道為二進(jìn)制對稱信道 其信道模型可以用圖1 2 表示 0 1 圖1 2 二進(jìn)制對稱信道 0 1 1 2 1 2 離散輸入連續(xù)輸出信道 假定信道編碼器的輸出符號取自x 一 而 而 而 譯碼器輸入為連續(xù)值 低密度校驗碼的性能分析及其帶化澤碼 y 月 我們稱這類信道為離散輸入連續(xù)輸出信道 典型的有二元輸入高斯白噪聲 信道 b 陵w g n 和二元拉普拉斯 i 五p l a c e 信道f 1 二元輸入高斯白噪聲信道的輸出可以用下式表示 y z 1 2 其中 為加性高斯自噪聲 其均值為零 方差為口2 給定一個輸入x 置 七一0 1 口一1 則 是均值為孔 方差為盯2 的高斯變量 p o i x 孔 矗 7 j e x p 一 y 一坼 2 盯2 1 3 q 踴u 如果信道是無記憶的 則滿足 p y 一 y i x 一 工 一 一n p 只l 墨一 1 4 1 2 2 信道容量 信道容量定義為信道輸入與信道輸出的互信息 它表征了信道可靠傳輸?shù)淖?大速率 最常見的信道容量計算式就是帶寬 功率受限下的加性高斯白噪聲 a w g n 信道容量計算式 設(shè)a w g n 信道帶寬受限于卜緲 1 噪聲雙邊功率譜 密度為 2 信號功率為p 則 p 川 9 1 1 南jp 圳5 式 1 5 這個容量僅在輸入服從高斯分布的情況下可以達(dá)到 如果輸入信號調(diào)制受限 那么容量將會小于上面這個值 下面我們考察其他幾種典型信道的容量計算 1 2 2 1 離散無記憶信道側(cè)s c t em e m o r y i 船sc h a n n d d m c 的容量 考慮一個離散無記憶信道 它的輸入符號集為x f h 而 一 輸出符號 集為l y o 1 i 一 y 一t 并且轉(zhuǎn)移概率為p y tl 如 假定傳輸符號為 接收到 符號為y 則事件xt x 和事件y y i 的互信息是1 0 9 p y i l x p 鋤 其中 p 弘 p m 寶p 五妒 弘i 鼻 1 6 o 因此 輸入集 和輸出集 之間的平均互信息為f 5 l 髑班驀蓍盹冊 l o g 馬紫 1 7 0 f lr l v l 由上式可知 y 的值取決于輸入符號集的概率分布 p x 和信道的特 性 即轉(zhuǎn)移概率 p y i z m 令 俾 y 在所有輸入分布 p 中取得最大值 則 這個最大值只與信道的特性 p 鋤i 工腳有關(guān) 它標(biāo)志著信道的傳輸能力 稱為信道 第一章緒論 容量 c a p a c i t y 配為c 這樣我們就得到了離散無記憶信道的容量計算式 c m a x j x y p 5 嘴薹 腆 魄幫 a 墻 對轉(zhuǎn)移概率為p 的二進(jìn)制對稱信道而言 當(dāng)輸入等概時 互信息取得最大值 信道容量為 c 昌1 p l 0 9 2 p 1 一p l 0 9 2 1 一p 一1 一f p 1 9 其中 日 p 是二元熵函數(shù) 1 2 2 2 離散輸入連續(xù)輸出信道 d i s c r e t e i n p u t c o n t i n u 叫s 咖t p l i tc h 柚n e i 的容 量 對于離散輸入連續(xù)輸出信道 記輸入符號集為z 一 而 一 輸出符號 集為y 一 一 m 在式 1 8 中 將對輸出符號的求和換成積分 相應(yīng)的概率 p y i x j 換成概率密度p y l 葺 這樣就得到了離散輸入連續(xù)輸出信道的容量計 算式 3 l c 黼霪e 曲 馴 昭z 篇凈 m 囂 慧葷 m 拉p 仆厄 l o g z 警 共中也 刀母付虧雕煎 若對二元輸入高斯信道的輸出作硬判決 則信道等效為一個b s c 其轉(zhuǎn)移概率 為 p f 壽e 噼啪 彘e x 卅嶧 一 去唧 一垃皇粵盥刪瓜 1 2 t 嘉去e x p 爭 令州y 厄 而 6 低密度校驗碼的性能分析及其肇化澤碼 其惻小f 擊唧 出 將式 1 1 2 的轉(zhuǎn)移概率代入式 1 9 就可以計算得出硬判決時的信道容量e 圖1 3 給出了b n w g n 信遵的軟判決容量 硬判決容量與出氓一磊 0 的關(guān)系 圖1 4 給出 了a i g n 信道的b p s k 容量限和調(diào)制不受限的s h a n n o n 容量限 c p c 時 h u ss n r m b 哪v g h d 帥 c 哪 n u e m 日眥nc h a n n h l 2 怒 i f 一 j f s n r e w 卿 圖1 3b i a w g n 信道的軟判決與硬判決容量 圖1 4b p s k 容鼉限與s h a n n o n 容量限 由圖1 3 可知調(diào)制器采用軟輸出比硬輸出有2 d b 左右的附加增益 這也就解釋了 為什么軟判決譯碼一般要優(yōu)于硬判決譯碼 由圖1 4 可以看出隨著碼率的增加b p s k 容量限離s h 鋤n o n 容量限越來越遠(yuǎn) 而當(dāng)碼率較小時b p s k 容量限基本與s h 鋤o n 容 量限一致 因此b p s k 調(diào)制下 系統(tǒng)一般工作在中低噪比 同時碼率也較小 小于等 于1 偽 若系統(tǒng)工作在高信噪比 則可以選擇更高維的調(diào)制以提高容量 由圖1 4 可得常見碼率的s h a l l n o n 容量限 例如1 2 碼率時s h 如n o n 容量限為 o d b 相應(yīng)的b p s k 容量限約為o 2 d b 1 3 碼率時s h a i i n o n 容量限約為 0 5 5 d b 相應(yīng) 的b p s k 容量限約為 0 5 d b 1 2 2 3 誤比特率仇與單位比特信噪比e o 給定信道容量c 由信道編碼定理可知 只要傳輸碼率尺低于c 就可以獲 得任意小的誤比特率p b 但是如果允許所大于零 那么可獲得更大的編碼增益 即 昂 0 可以進(jìn)一步減小 由信道編碼逆定理1 5 i 見l o g m 一1 h 既 日 u 一工c 1 1 3 c 其中 f 為信源字母表的大小 h u 為信源熵 信源每l 秒產(chǎn)生一個字母 信道容量為c 每t 秒產(chǎn)生一個信道符號 則碼率r t t 對b p s k 調(diào)制信號有 m 2 h u z 1 式 1 1 3 化為 c r 1 一日 肪 1 1 4 第一章緒論 上式也可以從另外一個角度得到 通常 為了考察特定碼的性能 可以通過仿 真砸出其誤比特率和信噪比的關(guān)系曲線圖 再與相同條件下的其它碼作比較從而 判斷碼的性能 下面討論給定碼率條件下誤比特率和信噪比的理論最佳曲線的作 法 接收端譯碼后誤比特率為鞏的情形等效于發(fā)送端對信源作誤比特率為風(fēng)的編 碼而接收端譯碼無誤的情形 由率失真理論可知 對二元輸出信源作誤比特率為以 的編碼所需的信源編碼速率為1 一日 以 令信道編碼速率為r 則實際需要的 b i a w g n 信道容量為r 1 一片 鞏 由信道編碼定理即可得式 1 1 4 圖1 5 為 b 拾w g n 信道下碼率為l 2 時 誤比特率與單位比特信嗓比的藍(lán)線圖 00 2040 60 b 1 2 圖1 5b i a w g n f 毒馨 障比特率和信噪比 的理論最佳曲線圖 碼率 1 2 1 3 低密度校驗碼的歷史和發(fā)展現(xiàn)狀 早在1 9 6 2 年g a l l a g c r 已經(jīng)提出正則低密度校驗碼 r e g u l a fl o wd e n s i t yp 盯i t y c h e c kc o d c s 和迭代譯碼 i t e r a 伽ed e c o d i n 曲的概念 然而直到上世紀(jì)9 0 年代中期 u p c 碼被s p i e l m 粕 m a c k a y 和n e a l 等學(xué)者m o 重新發(fā)現(xiàn)后 它才重新引起人們的 廣泛關(guān)注 為什么性能如此杰出的碼會沉寂幾十年才被人們認(rèn)識呢 g a l l a g e 增說 過這是因為在u p c 碼提出不久 f o m e y 提出了級聯(lián)碼的思想 而當(dāng)時大多數(shù)人都 認(rèn)為級聯(lián)碼更有可能取得好的性能 當(dāng)然 還有一個原因就是當(dāng)時的硬件水平尚 未成熟 實現(xiàn)那么長的u p c 碼 u p c 碼的短 中碼的碼長已經(jīng)達(dá)到幾百 幾千的 量級 非常困難 致使u p c 碼幾十年來一直無人問津 只有寥寥幾篇文章 其中有 一篇是1 9 8 1 年t a 珈e f 發(fā)表的獲獎文章 ar e c l l r s i v ea p p r o a c ht ol o wc o m p l e x i t yc o d e s 1 1 當(dāng)然這篇文章獲獎已經(jīng)是低密度校驗碼重新被人們認(rèn)識后的事了 通過這篇 文章 t 卸n e r 為基于圖模型的碼奠定了基石 文中引入了u p c 碼的二部圖模型 d 口 曠 曠 盯 低密度校驗碼的性能分析及其鼙化譯碼 b i p a r t i t eg r a p h i c a l m o d e l 現(xiàn)在稱為t a n n e r 圖 圖1 6 給出了一股l d p c 碼的t a n n e r 圖表示 圖1 6 中黑色圓圈表示碼字中的符號 方框表示局部約束關(guān)系 t a n e r 將 u p c 碼中的局部約束關(guān)系推廣到一般的線性碼中 并發(fā)現(xiàn)上述模型包含了乘積碼 以及由簡單碼遞歸構(gòu)造的碼類 同時 t a n n e r 還提出了現(xiàn)在所說的 最小和 算法 或 者稱為 最大積 算法 t a n n e r 對基于圖模型碼類的貢獻(xiàn)使我們認(rèn)識到 如果對相 對簡單的碼進(jìn)行迭代譯碼 那么譯碼器可以采用并行結(jié)構(gòu) 符合當(dāng)今大規(guī)模集成 電路技術(shù)的要求 因為譯碼器可以有效地使用軟判決信息 并且采用了并行結(jié)構(gòu) 此外譯碼復(fù)雜度也很低 所以即使對長碼進(jìn)行譯碼 速度也很快 蠢 曼基霪 菱 o j 夕汀 7 毒 i 一二 一y i 7 一 一一 札 p 一 圖1 6u p c 碼的t 如n e r 圖 圖1 7 因子圖 u p c 碼的復(fù)興和t u r b o 碼的出現(xiàn)緊密相關(guān) 1 9 9 3 年 c b e r i 伽 a g l a v i e u x a n d p n i t i m a j s h i m a 提出令人震驚的t u r b o 碼 1 2 l 離b i a w g n 信道s h a i l n o n 容量限只有 o 5 d b t u r b 0 碼成為繼u n g e r b o e d 提出t c m 1 3 之后信道編碼的又一里程碑 t u r b o 碼給人們帶來了一個重要啟示 迭代譯碼可以獲得接近最大似然譯碼的性能 于 是 迭代譯碼思想成為信道編碼理論界的研究熱點 也被用在通信的各個方面 如信道均衡 經(jīng)過j h a g c n a u e f 等人的總結(jié) 迭代譯碼思想上升為現(xiàn)在我們所熟知 的t u f b 0 原理 t u r b op r j n c i p l e 與此同時 各種1 n l i b o l 岫碼也紛紛涌現(xiàn) b e n e d e t t o 的串行級聯(lián)t u r b o 碼 s j p s e r 和s p i l m a l l 的擴(kuò)展碼 t o m a d o 碼 重復(fù)累積 r a 碼和李 坪的c t 碼等等 當(dāng)然這其中也有同樣采用迭代譯碼的低密度校驗碼 所有的 t u r b o 1 i k e 碼都由結(jié)構(gòu)簡單 譯碼復(fù)雜度低的分量碼和偽隨機(jī)置換矩陣組成 并且 1 l d o 1 i k e 碼有兩個共同點 可以采用圖模型表示 構(gòu)造 采用迭代譯碼思想 u p c 碼研究的興起 除了t u r b o 碼的研究熱潮為它提供了契機(jī) 還有兩方面 原因1 1 4 l 一方面是由于s p i e l m a l l m a c k a y 等幾位學(xué)者獨立研究了低密度校驗碼 發(fā)現(xiàn)u p c 碼有杰出的糾錯能力 而另一方面是由于w i b 盯g 在他的關(guān)于基于圖模型 碼的論文中作了拓荒性的研究工作1 1 5 l s p i e l m a l l 在他的論文中基于擴(kuò)展圖 e x p a n d e rg r a p h s 基于l i p c 碼設(shè)計了一種具有漸進(jìn)好糾錯性能的碼類 稱為擴(kuò) 展碼 9 1 這種碼可以線性時間編 譯碼 此后不久 a l o n 和i j l b y 把這些結(jié)果應(yīng)用到 i n t e m e t 丟包的問題中 設(shè)計了t o m a d o 碼舊 t o l a d o 碼是第一個商用化的u p c 碼 在刪除信道中 線性碼的譯碼問題等價于解線性線性方程組 通常求解一般線性 方程組的時間復(fù)雜度不是線性的 但是如果方程組中的每個方程都只有一個未知 第一章緒論 數(shù) 或者通過迭代等效于每個方程只有一個來知數(shù) 的話 那么譯碼將變得非常 簡單 此后 l u b y 研兔發(fā)現(xiàn)使用非規(guī)則圖并優(yōu)化度分布序列可以使碼的性能逼近 刪除信道的容量限 即當(dāng)傳輸速率接近1 一p 時 p 為刪除概率 可以取得非常小 的誤比特率 n 攤t p n t y b i 拈 d h b i 協(xié) 峪tnl融 圖1 81 l r b o 碼的岡子圖模型 s e c 帥d p a 一姆 b j t s 一 僅當(dāng) i l l 時 節(jié)點z 和z 之間由一 條邊連接 節(jié)點善 和五互稱相鄰節(jié)點 其間連接邊稱為這兩個節(jié)點的相鄰邊 因 子圖上每個變量節(jié)點具有d 條入射邊 即度數(shù)為d 每個校驗節(jié)點具有d 條入射 邊 即度數(shù)為d 共有e t 刪 一刪 條邊 令集合m p j i l 一1 表示變量工 的受限范圍 令 o 一 幾 1 表示校驗z 的約束范圍 圖2 1 a 是一個 8 2 4 短碼的校驗矩陣及校驗方程組 圖2 1 q 是相應(yīng)的因子 圖表示 該圖表示了校驗約束結(jié)構(gòu)碼的全局函數(shù) 工1 l 叫 也稱碼特征函數(shù) 每 個校驗節(jié)點z 表示一個局部約束函數(shù)正 扛 o 全局函數(shù)因式分解為 1 x 8 j l o l z 3 x 5 z 7 2 0 i 工4 x 6 z 8 0 2 x 3 6 z 7 4 q 2 耳4 x 5 z 8 2 1 定義指示函數(shù)為一個把布爾邏輯命題p 映射到g f 2 上的二值函數(shù) 2 9 j 叫 惡 陋萄 式 2 1 中的各個函數(shù)均為指示函數(shù) 其中全局函數(shù)的邏輯命題為 工是一個碼 字 每個局部函數(shù)的邏輯命題為圖2 1 a 中的校驗方程 式 2 1 又寫作為 z c 一k l x 3 x 5 x 7 0 恤1 x 4 x 6 z 8 墨0 1 b 2 上3 善6 x 7 駕o h 工2 工4 工5 x 8 墨o 2 3 第 一 章低密度校驗碼基丁圈模型的編譯碼原理 1 5 圖2 1 b 的因予圖實際上是一個有環(huán)t a n n e r 圖 注意到矩陣的第三列和第七列 中 1 出現(xiàn)在第一行和第三行兩個兩行位置上 對應(yīng)在因子圖中 依照無向邊連接 關(guān)系 存在一個長度為4 的循環(huán)路徑純 z z z 0 z 毛 屯 類似地 圖中還存在另一個長度為4 的循環(huán)路徑o z z 砘 o z 0 z 采用 迭代置信傳播算法譯碼時 這種短環(huán)路將極大地影響碼性能 碼的最小漢明 h a m m j n 曲距離及距離譜直接取決于環(huán)路的分布 青況 因此構(gòu)造碼時 應(yīng)該盡量消 除短環(huán)路 8 3 0 6 7 1 u p c 碼的因子圖表示中 e 條邊對校驗節(jié)點的入射關(guān)系和對變量節(jié)點的入射 關(guān)系可以看作是相互置換 所以一個特定的碼集合實際是滿足特定條件的隨機(jī)囂 換函數(shù)集合 如果不限制變量節(jié)點和校驗節(jié)點度數(shù) 那么隨機(jī)置換函數(shù)有可能導(dǎo) 致變量節(jié)點和校驗節(jié)點各自的度數(shù)不再恒定 這時入射邊分布表示為一對度數(shù)分 布序列a 一 a 1 一 九 和p p 1 一 j d d 1 1 9 3 1 1 其中a 和n 分別表示度數(shù) 變量節(jié) 點的入射邊比例和度數(shù)髓曼驗節(jié)點的入射邊比例 哦和d 分別是最大變量節(jié)點度數(shù) 和最大校驗節(jié)點度數(shù) 或用多項式a o 一 扎a h 和p o 一 幺a 工 1 表示 這 時設(shè)計碼率風(fēng) a p 一l 一 p o 出 f a o 出 1 一 生zn za j 當(dāng)度數(shù)分布多項式退化為a 一 1 和p 0 工 1 時 變量節(jié)點和校驗節(jié)點的 度數(shù)分別恒定為 和k 相應(yīng)的碼就稱為 l j 規(guī)則 f c g i l l a r i d p c 碼 反之稱 為非規(guī)則 i r i e g u l a r i d p c 碼 規(guī)則u p c 碼通常也稱為g a l l a g e f 碼 具有優(yōu)化度數(shù)分 布a 0 和j d 的非規(guī)則l d p c 碼一般要好于規(guī)則u p c 碼 1 8 而且優(yōu)化的非規(guī)則 u p c 長碼的性能已經(jīng)超過了最好的t u 曲碼 2 0 3 2 l 2 l 2 后驗概率分布表示 考慮時間離散信道上的一個分組碼c 設(shè)傳輸碼字為善一 屯 工 接收 碼字為 y y 根據(jù)全概率公式 信道輸入和輸出向量的聯(lián)合概率 密 度 函數(shù) 善 y 尸o o i 其中p 善 是發(fā)送碼字j 的先驗概率 j l x 是發(fā) 送碼字工時接收y 的條件概率 密度 函數(shù)或似然函數(shù) 基于給定的信道觀察y 對 碼字集合c 的后驗概率 a p p 測度p 臼l y 與聯(lián)合概率函數(shù) 善 了 成比例 即渺1 p 善iy 工 j y o c x y 2 4 對于時間離散的平穩(wěn)無記憶信道 似然函數(shù)具有如下的乘積形式 m i j m t 粉一曲階 m y 小 2 5 其中 y i x j 一1 是平穩(wěn)信道的標(biāo)量轉(zhuǎn)移概率密度函數(shù) 低密度校驗碼的性能分折及其鬣化譯碼 碼字j 允許服從任何分布 1 5 如果假定所有碼字被等概選取 即先驗概率p q 為一個常數(shù) 結(jié)合形如式 2 1 的碼特征函數(shù) 可以表示為 i 盹 h 2 高地 2 6 圖2 2u p c 碼的后驗概率測度因子圖 因此 聯(lián)合概率函數(shù) o 可以比例表示為 并z m 出 y w 珥 j 2 o 珂 y i 工小 2 7 代入式 2 4 得到后驗概率測度 即給定信道觀察y 時 j c 的后驗概率為 p x 協(xié)a l j 2 l l y 小 2 8 其中a 是使羅 p 冀 i y t l 的歸一化因子 在表示u p c 碼校驗約束的因子圖上 增加接收變量節(jié)點 及信道轉(zhuǎn)移函數(shù) 節(jié)點 y l 工 得到如圖2 2 所示的表示碼字后驗概率分布p 工l 的因子圖a 圖 中 黑圓點表示局部校驗函數(shù) 等同于圖2 1 中的校驗節(jié)點 黑方塊表示轉(zhuǎn)移函數(shù) 節(jié)點 圓圈表示發(fā)送變量和接收變量節(jié)點 2 2l d p c 碼的構(gòu)造 2 2 1 正則低密度校驗碼的構(gòu)造 校驗矩陣可以唯一確定一個線性分組碼 因此構(gòu)造正則低密度校驗碼只需要 構(gòu)造它的校驗矩陣 g a l l a g c r 在文獻(xiàn) 4 8 中采用0 l 七 來表示一個正則低密度校驗 碼 其中 l 表示碼長 j 表示校驗矩陣中每列所含1 的個數(shù) 而七則表示校驗矩陣中每 行所含1 的個數(shù) g a l l a g e 朗 用隨機(jī)置換的方法來構(gòu)造校驗矩陣 方法如下 第一二章低密度校驗碼基1 二圖模州的編譯碼原理 1 7 g a l l a g e r 構(gòu)造正則低密度校驗碼的方法 1 將校驗矩陣日分成f 個子矩陣h 1 仃2 凹 每個子 矩陣有0 一七 行 并且每個子矩陣的每列有且只有一個1 2 子矩陣日1 中的1 呈下降的階梯狀排列 即第f 行的七個1 從 第 f 一啦 1 位排到第蹈位 3 其余的子矩陣通過對日1 進(jìn)行隨機(jī)列置換得到 所有置換是 等概出現(xiàn)的 若一個伽 砷正則低密度校驗碼的校驗矩陣是滿秩的 設(shè)校驗矩陣有小行 根 據(jù)校驗矩陣中l(wèi) 的總數(shù)是固定的 有 m 七 可辛竺 2 9 撐芹 因此 這個機(jī)工n 正則低密度校驗碼的碼率可以簡單計算如下 r 竿一1 一竺a 1 一吾 2 1 0 九月抒 從上面的構(gòu)造方法不難知道 由g 棚a g e r 的方法構(gòu)造的校驗矩陣并不是滿秩 的 因此 由g a l l a g e r 的方法構(gòu)造的低密度校驗碼的碼率要略大于式 2 1 0 所計算 盼碼率 g a l l a g e r 曾給出了一個 2 0 3 4 低密度校驗碼的校驗矩陣 如圖2 3 所示 這里 我們稱由上述方法可以構(gòu)造的低密度校驗碼類 e n s 咖b l e 為6 枷a g c r 碼 類 g a l l a g e r 證明了關(guān)于g a i l a g e r 碼類的兩個結(jié)果 第一個是關(guān)于最小距離的 g a l l a 鼬r 碼類中 碼的最小距離是一個隨機(jī)變量 這個隨機(jī)變量的分布函數(shù)可以用 圖2 4 所示曲線作為上界 對j 苫3 和七 f 的g a l l a g c r 碼類而言 當(dāng)碼長趨于無窮時 圖2 4 中的曲線逼近階躍函數(shù) 躍變點處的坐標(biāo)值與碼長的比值是一個固定值 記為 6 m 因此 當(dāng)碼長n 足夠長時 實際上g a l l a g e r 碼類中的所有碼的最小距離至少 為硒m 第二個結(jié)果是關(guān)于誤比特率的 g a l l a g e r 證明 對于g a l l a g e r 碼類 在對稱 無記憶信道中 采用最大似然譯碼時 其誤比特率隨著碼長的增加呈指數(shù)形式下 降 這兩個結(jié)果說明g a n a g 盯碼類是相當(dāng)好的碼類 m a c k a y 和d a v e y 曾指出對任何 碼長和碼率 當(dāng)平均列重 一3 時 隨機(jī)構(gòu)造的g a l l a g c r 碼離現(xiàn)在所知最好的碼在零 點幾個d b 之內(nèi)p 低密度校驗碼的性能分析及其域化譯碼 1 11l0 o0 0 0 o o 0 o 00 0 000o 0 o0 o1 1110 0 0 o00o o 0 0 0 o 0000 o 0 0 0 1l11o00 o o 0 0 0 000oo0oo0o o o 1111o o o o 0 0oo 0 o 0 o00o 0 0 0 001 111 10001o o 010o01 0oo0 000 010001 o 0o1o 0 0 o 0 o10 0 0 001o00 1o 0 00oo1o 001 00 o 0 0lo ooo00lo001o0 o1o 0 0 0 o o o010 0010o0 lo0o1 1o0o010 0 000 1o o0 0o100 010000 1o 0o10 0 0 o10 o 0 0 0010 0 0 0 lo o0o10 00o 01o 0 0 0lo o o o10oo01o 0l0 o0 0 0 o o1o 0 0o1000o10o 0 01 圖2 3 2 0 3 4 低密度校驗碼的校驗矩陣 廣 p 聆6 膻 圖2 4 最小距離分布函數(shù)簡圖 2 2 2 非正則低密度校驗碼的構(gòu)造 理論上 正則低密度校驗的性能能夠逼近s h a 仰o n 容量限1 3 4 1 但是這是當(dāng)碼長 趨于無窮并采用最優(yōu)譯碼器的情況下取得的 然而 當(dāng)碼長無窮時 最優(yōu)譯碼的 復(fù)雜度太高 無法在實際應(yīng)用中實現(xiàn) 實際上 對于低密度校驗碼 一般碼長不 可能太大而譯碼采用逼近最大后驗概率譯碼的和積譯碼算法 因此 正則低密度 校驗碼的性能是否能完全被挖掘出來還要看具體的譯碼算法 g a l l a g e r 最初構(gòu)造的低密度校驗碼是正則低密度較碼 它的校驗矩陣的列重是 個常數(shù) 另一種可選方案是允許校驗矩陣的列重可以取幾種不同的值 這樣構(gòu)造 的碼稱為非正則低密度校驗碼 l u by m i t z e n m a c h e r s h o k r o l l a h i 和s p i e l m a n 證明了 精心選擇非正則碼的列重可以使它的性能超過相同參數(shù)的正則碼p o 非正則低密度校驗碼和正則碼一樣也可以通過它的圖模型來描述 記度為珀q 第二章低密度校驗碼基 幽模型的編譯碼原理 變量節(jié)點的個數(shù)為 度為 的校驗節(jié)點的個數(shù)為p 若非正則碼的碼長為h 碼率為尺 則有 叫 n 一 a t p n 1 一r 2 1 1 類似式 2 9 根據(jù)t a n n e r 圖中按校驗節(jié)點所連邊的數(shù)目等于按變量節(jié)點所連邊 的數(shù)目 有 魄 j p 2 1 2 由變量節(jié)點度分布序列 a i 和校驗節(jié)點度分布序列 p 定義多項式 x a 和p x 一 p 聲 2 1 3 由式 2 一1 1 有a 1 一肛 p 1 一n 1 一r 碼率為r 一1 一 1 p 1 對a x 和p x 求導(dǎo)可得 嘶 一等壁 叭一 2 1 4 甜 一 咐一掣 芝 刪 p 1 5 積 一 令x 1 有 人 1 p 1 總邊數(shù) 2 1 6 從邊的角度考慮 定義度分布序列 凡 和 n 其中 為與度為f 的變量節(jié)點 連接的邊的數(shù)目占總邊數(shù)的比例 磯為與度為j 的校驗節(jié)點的邊的數(shù)目占總邊數(shù) 的比例 類似地定義多項式 a 工 1 2 1 7 p x 一 p 卜1 2 一1 8 由式 2 1 4 2 1 8 有 簫及刖 器 2 2 3快速編碼l d p c 碼的構(gòu)造 近年來 信道編碼的研究者們都以解決以下問題作為最終目標(biāo) 對一個給定 的信道 找到一種碼宇同時具備兩種性質(zhì) 1 存在線性時間編碼算法 2 對任意 逼近信道容量的編碼速率可以可靠線性時間譯碼 但是對一般的l p d c 碼來說 若 按傳統(tǒng)的編碼方法編碼 復(fù)雜度是0 h 2 n 為碼長 這是無法用硬件實現(xiàn)的 編碼問題可以從兩方面著手去解決 一是研究編碼算法 試圖提出一種低復(fù)雜度 的編碼算法 如r i c h a r d s o n 等人提出的快速編碼算法 矧 或者是從研究碼的結(jié)構(gòu)入 墊 堡奎堡竺竺坐盟些壁坌塹墨基曼些堡塑 手 尋找能快速編碼的特殊結(jié)構(gòu) 4 5 4 蚋 如z i g z a g 型的l n p c 碼 2 2 l 即使用傳統(tǒng)方法編 碼 復(fù)雜度也低很多 由矩陣循環(huán)移位構(gòu)造的u p c 碼 4 7 1 的編碼和u p c 分組和卷 積編碼f 4 5 j 礎(chǔ)都可用移位寄存器實現(xiàn) 具有線性復(fù)雜度 2 3 置信傳播算法 因子圖中 函數(shù)節(jié)點對每一個相鄰變量節(jié)點根據(jù)其它相鄰變量節(jié)點傳遞的消 息并行求和計算邊界消息 變量節(jié)點對每一個相鄰函數(shù)節(jié)點根據(jù)其它相鄰函數(shù)節(jié) 點傳遞的邊界消息并行求積計算 乘積消息又將調(diào)整對應(yīng)函數(shù)節(jié)點的邊界計算 經(jīng)過若干次迭代 最終準(zhǔn)確地或漸近準(zhǔn)確地完成因式分解 對這個過程引入半環(huán) r 0 o 其中r 表示消息空間 o 和 o 分別表示定義在空間r 上的 和 積 運算 不同半環(huán)的引入 和積算法將演化為涉及人工智能 信號處理和數(shù) 字通信等不同領(lǐng)域的特定算法 它們包括貝葉斯網(wǎng)絡(luò)的p e a r l 置信傳播算法 快速 傅立葉變換算法 b c j r 前向 后向算法 算法 l d p c 碼的迭代大數(shù)判決譯碼算 法 也包括最小和算法 在糾錯碼的譯碼算法中 無論引入何種半環(huán) 事實上都 是依據(jù)概率澳9 度進(jìn)行的 所以 和積算法應(yīng)用于糾錯碼的譯碼時 統(tǒng)稱為概率傳 播算法 我們在本文中繼續(xù)統(tǒng)稱置信傳播 b p 算法 2 3 1 信號檢測與凋度 設(shè)隨機(jī)變量j x 和y y 分別表示信道的輸入和輸出字符 其中x 和y 分別表 示相應(yīng)的字符集 對于二元輸入倍道 信道編碼器輸出比特序列經(jīng)雙極映射后進(jìn) 入信道 假設(shè)比特h 0 l 雙極映射為x 一1 2 l 則x 一 1 一1 雙極映射后 g f 2 1 上的 和 運算轉(zhuǎn)化為實數(shù)域上的 積 運算 在這個意義上 g f 2 和 l u 是一對同構(gòu)空間 y 既可以為離散集也可以為連續(xù)集 比如 對于二元對稱信道 b s c y x 對于二元純刪除信道 b e c y 1 0 一1 對于a w g n 半連續(xù)信 道 y 等于實數(shù)域r 軟判決譯碼器將基于觀察y y 產(chǎn)生一個關(guān)于x 的測度 m e a s u i e 肛o 其值域 令a 表示 這種測度一般等價于x 的一個概率分布 產(chǎn)生測度最常用的兩種方法是 最大似然法 m l 和最大后驗法 m a p 即 一p y 卜 p y p o 弘 x 一p x y 一p r p y 硬判決譯碼器則產(chǎn)生兩個極端取值的測度 l 由隨機(jī)變量r 表示 稱為硬判決測度 這時a o 1 傳輸信道被模型化為一個二 元輸入二元輸出離散倍道 對測度p x 可以引入不同的量度 m e 試c 以適應(yīng)不同的計算需要 最常用的 對