貴州人學2 0 0 8 屆碩! t ：研究生學位論文 t u r b o 碼譯碼算法的研究 摘要 自香農(nóng)( s h a n n o n ) 1 9 4 8 年發(fā)表了論文通信的數(shù)學的通信理論以來，信道 編碼的發(fā)展取得了很大成就。t u r b o 碼于1 9 9 3 年由法國學者c b e r r o u 等人提出， 以其接近香農(nóng)極限的良好性能，不僅在信噪比比較低的高噪聲環(huán)境下性能優(yōu)越， 而且具有很強的抗衰落、抗干擾能力，成為業(yè)界研究信道編碼的熱點，也是近年 來糾錯編碼領(lǐng)域研究的重大突破。t u r b o 碼的出現(xiàn)是糾錯編碼史上的一個重大突 破，t u r b o 碼的提出被稱為信道編碼的一個罩程碑，隨著理論基礎(chǔ)的r 益完善， t u r b o 碼開始進入實際應用領(lǐng)域。現(xiàn)在，它已經(jīng)被廣泛使用在c d m a 2 0 0 0 ， w c d m a ，3 g p p 等諸多的當代通信協(xié)議中。 t u r b o 碼譯碼運算較復雜，占用的存儲空間較大，不利于工程實現(xiàn)。本文首 先介紹了信道編碼理論與技術(shù)的發(fā)展，深入研究了t u r b o 碼編譯碼算法的基本理 論；簡述了t u r b o 碼的編碼原理、交織器原理、譯碼原理以及發(fā)展狀況。在深入 分析迭代譯碼算法的基礎(chǔ)上，主要研究了最大后驗概率算法( m a p 算法) 及其對 數(shù)域簡化的l o g - m a p 算法和m a x - l o g - m a p 算法，結(jié)果表明m a p 算法和 m a x l o g - m a p 算法的性能比較接近，而l o g - m a p 算法由于軟信息的損失較多 從而有部分的性能損失。在任一算法中，增加迭代次數(shù)都會提高譯碼器的性能， 但同時運算量也會增加。本文采用m a x l o g m a p 算法作為d s p 實現(xiàn)t u r b o 碼 的譯碼算法；探討了m a x l o g - m a p 譯碼算法的原理、推導過程以及計算步驟； 重點對算法進行優(yōu)化調(diào)整，簡化了譯碼器的結(jié)構(gòu)、減少了計算的復雜度與存儲量。 最后，研究了用定點d s p 芯片實現(xiàn)t u r b o 碼譯碼器時的相關(guān)問題。討論了譯 碼量化精度、溢出處理和變量存儲等問題。給出了防溢出處理方法，有效地防止 運算過程中的溢出。結(jié)合文中給出的譯碼過程中相關(guān)問題的處理方法，并用c 語言對其譯碼算法進行了驗證仿真，在t i 公司t m s 3 2 0 c 5 4 1 6d s p 芯片實現(xiàn)了 t u r b o 碼譯碼算法，經(jīng)測試其譯碼性能與浮點譯碼接近。試驗結(jié)果表明，設計實 現(xiàn)的t u r b o 譯碼器工作穩(wěn)定，具有良好的性能。 關(guān)鍵詞：t u r b o 碼迭代譯碼m a x - l o g - m a p 算法d s p 貴州大學2 0 0 8 屆碩十研究生學位論文 t h er e s e a r c ho ft u r b o d e c o d i n ga l g o r i t h m a b s t r a ct f r o mt h et h e s i s t h et h e o r i e so fm a t h e m a t i c si nc o m m u n i c a t i o n s ”a n n o u n c e db y s h a n n o ni n19 4 8 ，t h ec o d i n gi nc h a n n e lh a so b t a i n e dv e r yg r e a ta c h i e v e m e n t t u r b o c o d e sw e r ep u tf o r w a r db yf r e n c hs c h o l a rc b e r r o ue t ci n19 9 3 t u r b oc o d e sh a v e g o o dc a p a b i l i t yn e a rt ot h ee x t r e m el i m i ti ns h a n n o n i tn o to n l yh a se x i m i o u s p e r f o r m a n c ei nt h ec i r c u m s t a n c ei nl o ws n r ，b u ta l s oh a sas t r o n ga b i l i t yt ok e e p f r o md e c l i n ea n di n t e r f e r e n c e ，, s ot u r b oc o d e sb e c a m et h eh o t s p o ti nc o d i n gd o m a i n a n dt h eb r e a k t h r o u g hi nt h es c o p e so fc o r r e c t i n gr i g h tc o d e s t h ef i n d i n go ft h et u r b o c o d e si st h eb r e a k t h r o u g hi nt h es c o p e so fc o r r e c t i n gr i g h tc o d e si nr e c e n ty e a r s t h e e m e r g e n c eo ft h et u r b oc o d e si sg o n eb yt h en a m eo fm i l e s t o n ei nt h es c o p e so f c o r r e c t i n gr i g h tc o d e s a st h et h e o r e t i c a lp r i n c i p l eb e c o m e sp e r f e c t l yd a yb yd a y , t u r b oc o d ei su s e dt oa p p l i e dd o m a i n n o wi th a sa l r e a d yb e e ne x t e n s i v e l yu s e di n m a n yc o m m u n i c a t i o np r o t o c o l ss u c ha sc d m a 2 0 0 0 ，t h ew c d m a ，a n dt h e3g p p t h eo p e r a t i o ni nt u r b oc o d e si s v e r yc o m p l i c a t e d ，a n di tt a k e su pp h y s i c a l m e m o r ys p a c eb i g g e r , a n ds oi ti sd i f f i c u l t yi ne n g i n e e r i n ga c h i e v i n g t h i st h e s i s i n t r o d u c e dt h ed e v e l o p m e n to ft h e o r i e sa n dt e c h n i q u ei ns i g n a lc h a n n e lc o d i n gf i r s t a n di n t e n s i v es t u d i e dt h eb a s a lt h e o r i e so nc o d i n ga n de n c o d i n ga r i t h m e t i co ft u r b o c o d e s t h e ni tb r i e fe x p l a i n e dt h eb a s i ct h e o r i e si nc o d i n ga n di n t e r w e a v e ra n d e n c o d i n ga n ds t a t u sq u o i nt h eb a s i co fs t u d y i n gt h ea r i t h m e t i ci ne n c o d i n g ，t h i s t h e s i sp r i m a r i l ys t u d i e st h ea r i t h m e t i c “m a p a n dt h ea r i t h m e t i c l o g - m a p a n dt h e a r i t h m e t i c “m a x l o g m a p ”a c c o r d i n gt ot h ee x p e r i m e n t t h ea r i t h m e t i c “m a p i s n e a rt ot h ea r i t h m e t i c “l(fā) o g m a p ”a n db e c a u s et h ea r i t h m e t i c “m a x l o g - m a p h a sm a n yp l u si ni n f o r m a t i o n ，i ti sm u c hl o s si nc a p a b i l i t y b u ti ti se a s yt oh a r d w a r e e x p e r i m e n t a lr e s u l t s f i n a l l y ，i n v e s t i g a t i n gt h ei n t e r r e l a t e dp r o b l e mw h i c ha c h i e v e de n c o d e ro ft u r b o 2 貴州人學2 0 0 8 屆碩? i j 研究生學位論義 c o d e su s i n gf i x e dp o i n td s pc h i p d i s c u s s i n gm a n yp r o b l e m sa b o u tt h ep r e c i s i o no f q u a n t i f i c a t i o no fc o d i n g 、t h ed i s p o s a lo fo v e r f l o wa n dd e p o s i t e dv a r i a b l ea n ds oo n a n dd r a wac o n c l u s i o na b o u tt h em e t h o do fa v o i d e do v e r f l o w , w h i c he f f e c t i v e l y a v o i dt h eo v e r f l o wi nt h ep r o c e s so fo p e r a t i o n t h et h e s i su s e sc l a n g u a g et ov a l i d a t e t h ea r i t h m e t i c a n di nt h ed s pc h i pt m s 3 2 0 c 5 416i nt h ec o m p a n yt i i t sc a p a b i l i t y i sn e a rt ot h ec o d i n gi nf l o a t i n gp o i n tn u m b e r sb yt e s t i n g a c c o r d i n gt ot h ee x p e r i m e n t ， t h et u r b oe n c o d e rh a sag o o dc a p a b i l i t ya n di tw o r k sv e r ys t e a d y k e y w o r d s ：t u r b oc o d e se n c o d i n gm a x - l o g m a pd s p 3 貴州人學2 0 0 8 屆頌i ? 研究生學位論文 原創(chuàng)性聲明 本人鄭重聲明：所呈交的學位論文，是本人在導師的指導下， 獨立進行研究所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本 論文不包含任何其他個人或集體己經(jīng)發(fā)表或撰寫過的科研成果。 對本文的研究在做出重要貢獻的個人和集體，均已在文中以明確 方式標明。本人完全意識到本聲明的法律責任由本人承擔。 論文作者簽名：! 士整 日 關(guān)于學位論文使用授權(quán)的聲明 本人完全了解貴州大學有關(guān)保留、使用學位論文的規(guī)定，同 意學校保留或向國家有關(guān)部門或機構(gòu)送交論文的復印件和電子 版，允許論文被查閱和借閱；本人授權(quán)貴州大學可以將本學位論 文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢索，可以采用影印、 縮印或其他復制手段保存論文和匯編本學位論文。 ( 保密論文在解密后應遵守此規(guī)定) 論文作者簽名：日生導師簽名：垂塵孳k 日 貴州人學2 0 0 8 屆碩? t 研究生學位論文 第一章緒論 本章介紹數(shù)字了通信系統(tǒng)的基本結(jié)構(gòu)，在此基礎(chǔ)上重點介紹差錯控制編碼在 數(shù)字通信系統(tǒng)中的位置和作用；然后分析信道編碼的基本數(shù)學理論和一些基本容 量限；在分析信道編碼技術(shù)發(fā)展歷程之后，綜合歸納了t u r b o 碼的研究現(xiàn)狀，并 在此基礎(chǔ)上對t u r b o 碼的主要研究內(nèi)容進行概括。 1 1t u r b o 碼發(fā)展歷史 隨著現(xiàn)代通信技術(shù)和計算機技術(shù)的迅速發(fā)展，每天都在不斷涌現(xiàn)新的通信業(yè) 務和信息業(yè)務，同時用戶對通信質(zhì)量和數(shù)據(jù)傳輸速率的要求也在不斷提高。由于 通信信道固有的噪聲和衰落特性，信號在經(jīng)過信道傳輸?shù)竭_通信接收端的過程中 不可避免地會受到干擾而出現(xiàn)信號失真。通常需要采用差錯控制碼來檢測和糾正 由信道失真引起的信息傳輸錯誤。由于差錯控制碼主要用于實現(xiàn)傳送糾錯，因此 又稱為糾錯碼或信道碼。最早的差錯控制碼主要是用于深空通信和衛(wèi)星通信，隨 著數(shù)字蜂窩電話、數(shù)字電視以及高分辨率數(shù)字存儲設備的出現(xiàn)，編碼技術(shù)的應用 已經(jīng)不僅僅局限于科研和軍事領(lǐng)域，而是逐漸在各種實現(xiàn)信息交流和存儲的設備 中得到成功應用。 隨著對高效、高可靠性數(shù)字通信系統(tǒng)需求的迅猛增長，大規(guī)模高速寬帶網(wǎng)絡 的發(fā)展使語音、圖像和其他多媒體信息的傳輸成為可能。通信系統(tǒng)設計人員最關(guān) 心的是如何在數(shù)據(jù)源功率和傳輸帶寬有限，系統(tǒng)復雜性和設備造價盡可能小的條 件下實現(xiàn)盡可能準確的信息傳輸，即使信息傳輸?shù)恼`碼率最小化。信道編碼是消 除或降低信息傳輸錯誤概率的有效手段之一。 為更好地理解信道編碼在數(shù)字通信系統(tǒng)中的地位和作用，下面首先介紹通用 數(shù)字通信系統(tǒng)的基本組成結(jié)構(gòu)，如圖1 1 所示。 4 貴州人學2 0 0 8 屆碩1 ：研究生學位論義 圖1 1 通信系統(tǒng)的基本組成結(jié)構(gòu) 圖1 1 中，信源編碼器是把信源發(fā)出的消息如語言、圖像、文字等轉(zhuǎn)換成二 進制( 多進制) 形式的信息序列，同時去掉了一些與傳輸信息無關(guān)的多余度。為了 抗擊傳輸過程中的各種干擾，需要人為的增加多余度，使信號具有自動檢錯或糾 錯能力，這種功能由圖中的信道編碼器完成。調(diào)制器的功用是把糾錯碼送出的信 息序列通過調(diào)制其變換成適合于信道傳輸?shù)男盘枴?shù)字信號在傳輸過程中，總會 遇到各種干擾而使信號失真，這種失真信號傳輸?shù)浇邮斩说慕邮諜C，進行解調(diào)， 變成二進制( 多進制) 信息序列。經(jīng)過信道譯碼器，對傳輸中產(chǎn)生的錯誤進行糾j 下， 再通過信源譯碼器恢復成原來的消息送給用戶。 現(xiàn)代信息和編碼理論的奠基人c e s h a n n o n 于1 9 4 8 年發(fā)表的“通信的數(shù)學原 理”中，首次闡明了在有噪信道中實現(xiàn)可靠通信的方法，提出了著名的有噪信道 編碼定理。他在定理中指出：對于任何信道，只要信息傳輸速率r 小于信道容量 c 時，就一定存在這樣的編碼方法：在采用最大似然譯碼( m l d ) 時，其誤碼率可以 任意小。在定理中s h a n n o n 給出了在數(shù)字通信系統(tǒng)中實現(xiàn)可靠通信的方法以及在 特定信道上實現(xiàn)可靠通信的信息傳輸速率上限。同時，該定理還給出了有效差錯 控制編碼的存在性證明，從而促進了信道編碼領(lǐng)域研究的快速發(fā)展。 上世紀九十年代以前，在信道編碼定理的指引下，人們?yōu)榱藰?gòu)造好的長碼和 復雜度可接收的譯碼算法而提出了許多編碼方案。根據(jù)信息碼元和校驗碼元之問 的關(guān)系，信道編碼可以分為卷積碼和分組碼兩類。分組碼編碼碼字中的監(jiān)督碼元 只與本組的信息元有關(guān)，而與其它碼字中的信息元無關(guān)。在通信系統(tǒng)中應用最廣 泛的分組碼是漢明碼和循環(huán)碼。1 9 5 0 年，r h a m m i n g 提出了第一個差錯控制編 碼方案一漢明碼，它是可以糾f 單個錯誤的完備碼。1 9 5 9 年霍昆格姆 ( h o c g e n g h e m ) 和1 9 6 0 年博斯( b o s e ) 以及雷一查德胡里( r a y c h a u d h u r i ) 分別提出 貴州人學2 0 0 8 屆碩 ：研究生學位論文 了糾正多個隨機錯誤的循環(huán)碼b c h 碼；1 9 6 0 年p e t e r s o n 找到了二元b c h 碼的 第一個有效算法，從而將它由理論推向?qū)嵱谩? 9 6 0 年r e e d 和s o l o m o n 發(fā)現(xiàn)了 b c h 碼在基于素數(shù)的有限域中的一個子類r s 碼的構(gòu)造方法，從而將分組碼的理 論推到了一個高峰。 雖然分組碼在理論分析和數(shù)學描述方面己經(jīng)非常成熟，并且在實際的通信系 統(tǒng)中也己經(jīng)得到了廣泛應用，但分組碼的固有缺陷限制了它的進一步發(fā)展。首先， 由于分組碼是面向數(shù)據(jù)塊的，因此，在譯碼過程中必須等待整個碼字全部接收之 后才能開始進行譯碼。另外，大多數(shù)基于代數(shù)的分組碼譯碼算法都是硬判決算法， 而不是對解調(diào)器輸出未量化的信息的軟譯碼，從而造成一定的增益損失。1 9 5 5 年愛罩斯( e l i a s ) 提出的卷積碼克服了分組碼的固有缺點，由于它的編碼過程足連 續(xù)進行的，并且在編碼過程中充分利用了前后比特的相關(guān)性，因此性能優(yōu)于同等 編碼效率的分組碼，并且在同等碼率和相似的糾錯能力下，卷積碼的實現(xiàn)要比分 組碼簡單。1 9 6 7 年v i t e r b i 提出了卷積碼的一種最大似然譯碼算法，無論從理論 還是實際應用上都大力推動了卷積碼的發(fā)展。卷積碼在各種通信系統(tǒng)中都得到了 廣泛的應用。 近年來，在信道編碼定理的指引下，人們一直致力于尋找能滿足現(xiàn)代通信業(yè) 務要求、結(jié)構(gòu)簡單、性能優(yōu)越的好碼，并在分組碼、卷積碼等基本編碼方法，提 出了乘積碼、代數(shù)幾何碼、低密度校驗碼( l d p c ，l o wd e n s i t yp a r i t yc o d e ) 、分 組一卷積級聯(lián)碼等編碼方法。其中對糾錯編碼發(fā)展貢獻比較大的是級聯(lián)碼。它是 在1 9 6 6 年由f o m e y 首先提出的，利用兩個確定的短碼來構(gòu)造長碼的串行級聯(lián)結(jié) 構(gòu)，并且允許將最大似然譯碼分為幾個較簡單的譯碼步驟，這樣便得到一個次最 優(yōu)而實際可行的譯碼策略。但是，傳統(tǒng)通信系統(tǒng)的最佳接收機中解調(diào)器和澤碼器 是獨立的兩個部分。在處理接收信號的過程中，解調(diào)器首先對調(diào)制器輸入符號做 最佳判決，然后將硬判決結(jié)果送給譯碼器，譯碼器再對編碼器輸入信息做最佳判 決，糾j 下解調(diào)器可能發(fā)生的錯誤判決，這是硬判決的基本思想。事實上，經(jīng)過解 調(diào)器對符號的硬判決，丟失了很多有利的譯碼信息。為了提高通信系統(tǒng)的性能， 人們從信息論的角度對接收機中的解調(diào)器與信道譯碼器的功能劃分和接口重新 審視，提出了軟判決譯碼方法，即解調(diào)器對輸出不進行判決，送到譯碼器的是判 決符號可能的概率值或未量化輸出，而非硬判決值，即在一個高效的數(shù)字通信系 6 貴州人學2 0 0 8 屆碩i ：研究生學位論文 統(tǒng)中，實際的判決是譯碼器而不是解調(diào)器的任務。在部分文獻中分析出解調(diào)器采 用軟輸出可以得到比硬判決輸出高2 d b 左右的附加編碼增益。這種僅僅輸入是軟 信息的譯碼方法，在只是用一個糾錯碼的情況下是最好的解決方案。 但是，在像串行級聯(lián)碼這種組合多個碼的情況下，由于內(nèi)碼譯碼器的輸出為 硬判決結(jié)果，使得外碼譯碼器不能采用軟判決譯碼技術(shù)從而限制了系統(tǒng)性能的進 一步提高。為此人們又提出了軟輸出的譯碼的概念和方法。相應的，對于輸入輸 出均為軟判決的譯碼方法，稱為軟輸入軟輸出( s l s o ，s o f ti ns o f to u t ) 譯碼算法。 軟輸出譯碼實現(xiàn)了解調(diào)器、內(nèi)譯碼器和外譯碼器之間的軟信息轉(zhuǎn)移，使通信系統(tǒng) 的性能得到了很大的改進。但是，串行級聯(lián)碼與香農(nóng)極限總有相當一段差距。 實際上，香農(nóng)信息論的第一項隨機化思想，才是香農(nóng)信息論的精華，它在長 信道編碼中體現(xiàn)為所有碼字間的碼距盡可能的接近平均碼距。隨機化思想貫穿于 編碼的構(gòu)造和譯碼算法的選取原則之中。之所以串行級聯(lián)碼與香農(nóng)極限總有相當 一段差距，是因為其編碼按照級聯(lián)多個短碼構(gòu)成為一個長碼的思想來構(gòu)造，而譯 碼端卻對這些短碼分別獨立譯碼。在此情況下，即使內(nèi)、外碼問的交織器起到隨 機化構(gòu)造長碼的作用，在譯碼端也沒有利用這一整體隨機化思想，因此，這里的 交織器只起到在外碼譯碼器輸入端將突發(fā)錯誤離散化的作用。直到1 9 9 3 年 b e r r o u 等人在工程實踐中發(fā)現(xiàn)了t u r b o 碼，糾錯碼的設計才真f 應用了隨機化的 編、譯碼思想，從而獲得了接近香農(nóng)限的性能。文獻巧妙的將卷積碼和隨機交織 器結(jié)合在一起，實現(xiàn)了隨機編碼的思想，同時，采用軟輸出迭代譯碼算法來逼近 最大似然譯碼算法。文中的模擬結(jié)果表明，如果采用大小為6 5 5 3 5 的隨機交織器， 并且進行1 8 次迭代，則在e b e d 大于等于0 7 d b 時誤比特率達到1 0 - 0 ，與香農(nóng) 限僅差0 7 d b 。這一結(jié)果的公布立刻在編碼理論界引起轟動，掀起了研究t u r b o 碼的熱潮。由于t u r b o 碼接近隨機碼，有好的距離特性，而且在編碼中融入了交 織碼，因而有很強的糾錯能力和抗衰落能力。 1 2t u r b o 碼的研究狀況 在介紹t u r b o 碼的首篇論文罩，發(fā)明者b e r r o u 僅給出了t u r b o 碼的基本組成 和達代譯碼的原理，而沒有嚴格的理淪解釋和證明。因此，在t u r b o 碼提出之初， 其基本理論的研究就顯得尤為重要。j h a g e n a u e r 首先系統(tǒng)地闡明了迭代譯碼的 7 貴州大學2 0 0 8 屆碩一i ：研究生學位論文 原理，并推導了二進制分組碼與卷積碼的軟輸入軟輸出譯碼算法。由于t u r b o 碼 中交織器的出現(xiàn)，使其性能分析異常困難，因此s b e n e d e t t o 和g m o n t o r s i 等人 提出了均勻交織( u i ，u n i f o r mi n t e r w e a v e ) 的概念，并利用聯(lián)合界技術(shù)給出了t u r b o 碼的平均性能上界。d d i v s a l a r 等人也根據(jù)卷積碼的轉(zhuǎn)移函數(shù)，給出了t u r b o 碼 采用m l d 時的誤比特率上界。對于t u r b o 碼來說，標準聯(lián)合界在信噪比較小時 比較寬松，只有在信噪比較大時才能實現(xiàn)對t u r b o 碼性能的度量。 l c p e r e z 等人從距離譜的角度對t u r b o 碼的性能進行了分析，證明可以通過 增加交織長度或采用本原多項式增加分量碼的自由距離來提高t u r b o 碼的性能。 他們還證明了t u r b o 碼雖然自由距離比較小，但其小重量碼字的數(shù)目比較少，從 而解釋了低信噪比條件下t u r b o 碼性能優(yōu)異的原因。s d o l i n a r 的研究表明，t u r b o 碼的段最小距離碼字主要由重量為2 的輸入信息序列生成，是形成錯誤平層的主 要原因。 在實際的通信系統(tǒng)中，為提高系統(tǒng)帶寬效率，一種方法是通過刪減部分校驗 比特來提高編碼速率，稱為刪余。d d i v s a l a r 等人分別研究了高碼率和低碼率條 件下t u r b o 碼分量碼設計的一般性原則。這些研究為構(gòu)造優(yōu)秀的t u r b o 碼提供了 參考。 t u r b o 碼是低碼率碼，其優(yōu)異性能是以較高的帶寬為代價的。目前，對此的 解決方案是將t u r b o 碼與t c m ( t r e l l i sc o d em o d u l a t i o n ) 相結(jié)合來實現(xiàn)高增益高頻 譜效率的編碼調(diào)制方案( t - t c m ) 。 t u r b o 碼的譯碼算法主要分為兩大類。一類是基于最大后驗概率( m a p ， m a x i m u map o s t e f i o r i ) 的軟輸出算法，主要包括標準m a p 算法、對數(shù)域上的 l o g - m a p 算法和m a x l o g - m a p 算法、修正的m a p 算法( m m a p ) 、滑動窗 m a p ( s w - m a p ) 算法和只有前向遞推的m a p 算法。另一類t u r b o 碼譯碼算法是 基于( v i t e r b i ) 算法( v a ，v i t e r b ia l g o r i t h m ) 的軟輸出算法。主要包括s o v a 、雙向 軟輸出v i t e r b i 算法( b s o v a ) 矛hl i s t s o v a 等。在t u r b o 碼迭代譯碼器實現(xiàn)方面 的研究也是層出不窮。南澳大利亞大學s m a l lw o r l d 通信研究組最先開始開發(fā) t m 0 編譯碼器并推出了t u r b o 碼產(chǎn)品。a c h a s s 、d a r r e t t 和k k o o r a 等人也分 別在不同的數(shù)字芯片上設計實現(xiàn)了m a x l o g m a p 算法和s o v a 算法。 由于t u r b o 碼具有接近s h a n n o n 理論極限的性能，尤其是低信噪比下的優(yōu)異 貴州人學2 0 0 8 屆碩i j 研究生學位論文 性能使t u r b o 碼在許多通信系統(tǒng)中都有非常大的應用潛力。t u r b o 碼己被列入各 種通信規(guī)范?？諉枖?shù)據(jù)標準咨詢委員會( c o n s u l t a t i v ec o m m i t t e ef o rs p a c ed a t a s t a n d a r d ，c c s d s ) 己將1 6 狀態(tài)t u r b o 碼列為一個新標準，2 0 0 3 年后，美國國家 航空和宇宙航行局( n a s a ) 與歐洲空間局( e s a ) 支持該標準。在個人移動通信領(lǐng) 域，3 g p p 正式將t u r b o 碼作為i m t - 2 0 0 0 的高速數(shù)據(jù)通信的信道編碼標準之一。 其中被國際電聯(lián)采用的具有代表性的3 個3 g 標準( w c d m a 、c d m a 2 0 0 0 和 t d s c d m a ) 均在信道編碼中使用了t u r b o 碼，用以傳輸高速率、高質(zhì)量的通信 業(yè)務，如6 4 k b p s 的電路數(shù)據(jù)業(yè)務、1 4 4 k b p s 和3 8 4 k b p s 的分組數(shù)據(jù)業(yè)務。 t u r b o 碼的出現(xiàn)，不僅提供了一個性能優(yōu)異的編碼方法，同時迭代的思想也 為眾多通信問題提供了解決方案。利用t u r b o 碼的迭代譯碼特性，可以實現(xiàn)聯(lián)合 信道估計和譯碼。在移動通信系統(tǒng)中把迭代譯碼的思想應用于c d m a 中，便形 成了迭代多用戶檢測( 或干擾抵消) 技術(shù)。在通信系統(tǒng)中采用均衡技術(shù)來消除信號 傳輸過程中產(chǎn)生的i s i ，傳統(tǒng)的均衡方法由線性均衡、判決反饋均衡及自適應均 衡方法。通常均衡與譯碼是獨立的，但利用t u r b o 迭代思想來實現(xiàn)系統(tǒng)均衡模塊 與譯碼模塊之間信息的交換，幾乎完全可以消除i s i 的影響。此外，t u r b o 碼在 聯(lián)合信源一信道編碼以及實現(xiàn)a r q 技術(shù)上也有應用。 1 3 t u r b o 碼設計中的幾個關(guān)鍵問題 在t u r b o 碼中，有許多關(guān)鍵的環(huán)節(jié)至關(guān)重要。設計時，要將各個環(huán)節(jié)作為一 個整體進行考慮，才有可能達到性能上的最佳。本節(jié)對t u r b o 碼的關(guān)鍵技術(shù)系統(tǒng) 地進行分析和研究。 分量碼的選擇 分量碼是整個t u r b o 碼編碼器的核心，在目前已經(jīng)成熟的糾錯碼中有許多可 以選作分量碼，如分組碼和卷積碼，分量碼的個數(shù)可以是兩個以上，構(gòu)成多維 t u r b o 碼。在各種性能測試中，卷積碼的性能一般要好于分組碼，目前分量碼的 選擇基本上是卷積碼，對分量碼選擇分組碼的研究較少。在實踐中發(fā)現(xiàn)，遞歸系 統(tǒng)卷積碼( r s c ) 能更好地滿足各分量碼中的信息互相利用，總的碼重更集中于平 均碼葦附近，所以被大多數(shù)的設計方案選用。但分r p 碼類犁的選擇要根抓實際的 應用環(huán)境進行選擇，不排除在其它的方案中選用其它的分量碼。 9 貴州人學2 0 0 8 屆碩i ：研究生學位論文 交織器的設計、 信道編碼中交織器的作用一般是對抗突發(fā)錯誤，在t u r b o 碼中，交織器除了 以上的作用外，還起到一個更重要的作用，即改變碼的重量分布，將原始信息序 列置亂，使得交織前后的信息序列的相關(guān)性減弱。交織長度越長，相鄰反饋信號 拘相關(guān)性就越低，從而可以很好地實現(xiàn)迭代譯碼。交織器的設計直接影響到整個 瑪?shù)男阅?。t u r b o 碼中常用的交織器有分組交織器與隨機交織器兩大類，其基本 類型又可分為行列式分組交織、螺旋式分組交織、線性轉(zhuǎn)換式隨機交織和讀表式 9 直機交織等。交織器的設計要根據(jù)應用的場合合理設計，完全隨機的交織器并不 是最佳的選擇。要根據(jù)信息的特點進行設計，盡量滿足一些基本準則：如盡可能 地置亂原始數(shù)據(jù)的順序；避免與同一信息位直接相關(guān)的兩個分量編碼器中的校驗 直均被刪除；避免出現(xiàn)“尾效應”圖案；使碼字間的最小距離盡可能大，而重量 ， 為口m i a 的碼字數(shù)要盡可能少，克服所謂的地板效應；交織深度要綜合考慮系統(tǒng)的 對延要求以及數(shù)據(jù)幀的大小，這樣才可以優(yōu)化整個編碼器的性能。 譯碼算法 在t u r b o 碼的各種譯碼算法中，標準m a p ( m a x i m u ma p o s t e r i o r i ) 算法的性能 非常好，缺點是運算大，不易實現(xiàn)。目前最常用的簡化算法有幾種：一是基丁= 符 號的最大后驗概率譯碼的m a x l o g m a p 算法，即把標準m a p 算法中的參量 用它們的對數(shù)形式表示，把繁瑣的指數(shù)和乘除運算轉(zhuǎn)化為加減運算，降低復雜度； 二是基于序列的最大后驗概率軟輸出v i t e r b i 算法( s o v a ) ，m a x l o g m a p 算法 的性能比標準m a p 算法要損失大約o 3 0 5 d b 的增益，而s o v a 算法要比標準 m a p 算法損失大約1 0 d b 左右。在t u r b o 碼的各種譯碼算法中，m a x l o g m a p 算法通常用于硬件實現(xiàn)。目前研究較多的是m a p 算法及其改進形式。許多學者 對t u r b o 碼的譯碼算法進行了研究，提出了許多改進的算法?？梢愿鶕?jù)不同的應 用環(huán)境選擇不同的譯碼算法，軟件和硬件實現(xiàn)時譯碼算法的選擇也有所不同，硬 件實現(xiàn)時主要是硬件參數(shù)的限制。 歸零處理 卷積碼在一幀結(jié)束時，通常要加m ( m 為編碼存儲長度) 個比特的收尾序列， 使編碼器返回全零狀態(tài)。但在t u r b o 碼中，因為交織器的引入，m 個比特的收尾 序列很難使兩個編碼器都返回全零狀態(tài)。因此，t u r b o 碼未狀態(tài)的處理就有多種 l o 貴卅1 人學2 0 0 8 屆顧i ：研究生學位論文 方法，目前主要有以下四種：歸零第一個編碼器；歸零第二個編碼器；都不歸零； 都歸零。當編碼器不歸零時，若采用s o v a 算法譯碼，則只需選擇度量值最大的 路徑即可，若采用m a p 算法，通常將后項遞歸分a 初始化為前項遞歸分量第一 次迭代后的末狀態(tài)值。一般的做法都是用收尾比特使其中一個編碼器在一幀結(jié)束 時歸零，一般情況下，這種方案對t u r b o 碼性能的影響很小。 迭代終止技術(shù) t u r b o 碼的譯碼是迭代的，每次迭代都會更加接近性能極限，但也帶來計算 量的增加和澤碼時延。當譯碼接近給定t u r b o 碼的性能極限時，迭代次數(shù)的增加 帶來的性能改善非常有限，因此設計合適有效的停止判據(jù)終止譯碼器，減少不必 要的迭代和時延是非常重要的問題。目前大多的t u r b o 碼譯碼算法采用的是預設 迭代次數(shù)，這個值可以針對具體的信道條件通過大量的訓練測試取一個平均值。 此方法簡單實用，但不能自適應不同的數(shù)據(jù)流和信道條件，并不是一個最佳的停 止判據(jù)。此外就是構(gòu)造一個統(tǒng)計量，每次迭代完以后，檢測該統(tǒng)計量的值，達到 一定的條件后即可終止譯碼器。目前，好幾種主要的方法都是基于互嫡的概念構(gòu) 造的。雖然停止判據(jù)的種類有多種，應該根據(jù)具體的應用場合選擇。在數(shù)據(jù)流的 特征和信道條件相對穩(wěn)定的情況下，通過訓練確定一個預設的迭代次數(shù)也是可取 的。 另外，在理論上有關(guān)t u r b o 碼的許多問題還是懸而未決。這一點，引起了人 們的重視，人們試圖從各方面來解決這些疑問： 1 分量碼的不同對碼字性能的影響； 2 迭代算法的收斂性； 3 交織深度對性能的影響等 1 4 本文主要工作及篇章結(jié)構(gòu) 本文采用描述、討論、數(shù)學分析和計算機仿真相結(jié)合的方法，對t u r b o 碼設 計和應用中的幾個關(guān)鍵問題進行了探討研究，包括編碼器、交織器和譯碼器，同 時結(jié)合d s p 對t u r b o 碼的硬件實現(xiàn)進行了研究，本論文的主要內(nèi)容安排如下： 1 ) 第一一章簡要介紹了t u r b o 誣5 的產(chǎn)：塵7 亍景、國內(nèi)外研究現(xiàn)狀及本文的主要 工作。 貴州人學2 0 0 8 屆顧 ：研究生學位論文 2 ) 第二章給出了t u r b o 碼的基本原理：包括編碼器和譯碼器的結(jié)構(gòu)和原理； 從理論上對t u r b o 碼的性能進行分析：先通過計算機仿真分析各種系統(tǒng) 參數(shù)對t u r b o 碼糾錯能力的影響，為設計t u r b o 碼提供了參數(shù)選擇的基本 原則；接著，對t u r b o 譯碼實現(xiàn)過程中信息量化等問題進行分析；從而 指明了t u r b o 碼的設計方向。 3 ) 第三章研究比較了t u r b o 碼的各種譯碼算法，主要研究了m a p 算法、 l o g m a p 算法和m a x l o g m a p 算法，并討論了t u r b o 碼在a w g n 信 道上的算法，并且以( 1 3 ，1 5 ) 分量碼為例，給出了性能仿真比較結(jié)果。 4 ) 第四章在深入研究m a x l o g - m a p 譯碼算法的基礎(chǔ)上，對該算法進行了 合理優(yōu)化，并且在d s p 平臺上實現(xiàn)了該算法?；诖朔椒▽崿F(xiàn)的t u r b o 碼譯碼器具有較低的誤碼率和較小的譯碼時延，在語音通信和數(shù)據(jù)通信 中具有廣泛的應用前景。 5 ) 第五章對以上完成的工作進行總結(jié)并做出展望。 貴州人學2 0 0 8 屆碩1 ：研究生學位論文 第二章t u r b o 碼基本原理 t u r b o 碼的編譯碼基本原理 t u r b o 碼又稱并行級聯(lián)卷積碼( p c c c ) ，它將卷積碼與隨機交織器結(jié)合在一 起，巧妙地實現(xiàn)了隨機編碼的思想，同時采用軟輸出迭代譯碼來逼近最大似然譯 碼。模擬結(jié)果表明，采用大小為6 5 5 3 5 的隨機交織器，并進行1 8 次迭代，碼率 為l 2 的t u r b o 碼在a w g n 信道上當e b e d = 0 7 d b 時的誤比特率b e r 尋1 0 _ 6 ， 達到了近s h a n n o n 限的性能。j 下是由于t u r b o 碼超乎尋常的性能，它的出現(xiàn)立即 引起了編碼學界的極大轟動，圍繞t u r b o 碼的研究也成了通信系統(tǒng)中的一個熱 點。同時，t u r b o 碼的出現(xiàn)還對信道編碼理論及技術(shù)的研究產(chǎn)生了深遠的影響， 主要體現(xiàn)在以下幾個方面：結(jié)束了長期以來將信道截至速率作為實際容量限的歷 史；從早期的基于代數(shù)的構(gòu)造與譯碼方法到如今更傾向于基于概率的軟判決譯碼 方法；從以前的編碼方法之間比較過渡到均與香農(nóng)限進行比較。 t u r b o 碼的最大特點在于它通過在編譯碼器中交織器和解交織器的使用，有 效地實現(xiàn)了隨機性編譯碼的思想，通過短碼的有效結(jié)合實現(xiàn)長碼，達到了接近 s h a n n o n 理論極限的性能。 典型的二維t u r b o 碼編碼器山兩個r s c 編碼器、一個交織器、一個刪余矩陣 和一個復接器組成，編碼后的校驗位經(jīng)過刪余陣，從而產(chǎn)生不同碼率的碼字，編 碼結(jié)構(gòu)如圖2 1 所示： 圖2 1 二維t u r b o 碼編碼器結(jié)構(gòu) 信息序y , jd = 4 ，d z ，d ) 經(jīng)過一個隨機交織器，形成一個新序列 4 = 4 ，d z ，“) ( 長度與內(nèi)容沒有變，但是比特位置經(jīng)過重新排列) 。d 和4 分別傳送到兩個分量碼編碼器( r s c l 和r s c 2 ) ，編碼后生成的碼字包含原信息序 貴州人學2 0 0 8 屙順i ：研究生學位論文 列“以及兩個子編碼器生成的校驗序列“p 1 和“，即生成的碼子為以，“川，“p 2 ) ， 這種編碼方式即所謂的“并行級聯(lián) 。( p a r a l l e lc o n c a t e n a t i o n ) 。為了提高編碼的 碼率，經(jīng)過編碼之后產(chǎn)生的校驗序列可能會通過一個刪截矩陣進行刪截 ( p u n c t u r e ) ，用丟掉一部分的校驗比特的代價來增加碼速。如果沒有經(jīng)過刪截， 子碼編碼器生成的校驗序列u 川和u 雕都將保留，碼速( 即編碼效率) 達到最小值 1 3 。通常所使用的是均勻刪截，即交替地刪去校驗比特“川和u 雕這樣得到的碼 率為1 2 。 分量編碼器一般選擇為遞歸系統(tǒng)卷積碼( r s c ) ，當然也可以是分組碼( b c ) ，非 遞歸系統(tǒng)卷積碼( n s c ) 等，從后面的分析可以看出，分量碼的最佳選擇足r s c 碼。 t u r b o 交織器的作用是將信息序列中的比特順序重置，當信息序列經(jīng)過第一個分 量編碼器后輸出的碼字重量較低時，交織器可使交織后的信息序列經(jīng)過第二個分 量編碼器編碼后以很大概率輸出高重量碼字，從而提高碼字的漢明重量；同時好 的交織器還可以有效地降低校驗序列之間的相關(guān)性。 刪余矩陣的作用是提高編碼效率，其元素取自集合 1 ，0 ) ，矩陣中每一行分 別與兩個編碼器相對應，其中“0 ”表示相應位置上的校驗比特被刪除，而“1 則表示保留相應位置的校驗位。 對于二維t u r b o 碼，其碼率r 與兩個分量碼的碼率r 1 和r 2 之間滿足： ! ：上+ 上一l 一= 一+ 一一_ rrr 即： 尺： 墨魚 r j + 心一r l 足 由上式可見，通過提高分量碼的編碼效率可以得到高碼率的t u r b o 碼。 由于多維t u r b o 碼的維數(shù)越多硬件實現(xiàn)就越為復雜，且二維t u r b o 碼基本就 能滿足要求，所以在一般在系統(tǒng)中都采用了二維編碼方法。 本文采用生成多項式系數(shù)為( 1 3 ，1 5 ) 的遞歸系統(tǒng)卷積碼作為分量碼實現(xiàn)二維 t u r b o 碼的編碼和譯碼，其完整編碼框圖如圖所示。 1 4 貴州人學2 0 0 8 屆碩i j 研究生學位論文 d u u p l u p 2 圖2 - 2g = ( 13 ，15 ) t u r b o 碼編碼結(jié)構(gòu)( 3 g p p 標準) 信息流d 直接輸入給子編碼器c 1 ，產(chǎn)生檢驗比特數(shù)據(jù)“川。u 經(jīng)交織器( 圖中 i 表示) 交織以后再輸入給編碼器口進行編碼，相應地產(chǎn)生檢驗比特數(shù)據(jù)甜弘。編 碼后生成的碼字包含原信息序列u = d 以及兩個子編碼器生成的校驗序列“p 1 和 圖2 1 中的編碼器使用了2 個子碼進行級聯(lián)。同樣的，也可以使用3 個或者3 個以上的子碼進行級聯(lián)。多個子碼并聯(lián)的性能顯然要優(yōu)于2 個子碼級聯(lián)的編碼 器。但因為增加了冗余信息，勢必會加重解碼的負擔，使解碼過程變得更為復雜。 一般情況下，很少使用2 個以上的子碼進行級聯(lián)構(gòu)成t u r b o 碼。本文后面所提到 的編碼器，如果沒有特別的說明，都是默認采用2 個相同的子碼并聯(lián)而成。 2 2 遞歸系統(tǒng)子碼( r s c ) 從t u r b o 碼的編碼器結(jié)構(gòu)上來看，雖然t u r b o 碼的子碼是卷積碼，但是由于 交織器的存在，使得t u r b o 碼能夠以分組的方式來進行，分組長度就是交織器的 深度，因此從這個意義上說，t u r b o 碼是分組碼而不是卷積碼。 對于個碼速為1 2 的二進制卷積碼編碼器而言，如果假定它的約束長度為 k ( 即記憶深度為k 1 ) ，在時刻k 輸入的二進制比特為以，對應的輸出對為( u k ，咋) ， 那么蠔和屹的表達式可以寫成 一l 坼- - y g l 噥一i m o d 2g l = o ，1 貴州人學2 0 0 8 扁碩t ：t i j f 究生學位論文 眉一i 咋一9 2 d m o d 29 2 = o ，i 其中，g i2 蜀 和g 22 g z 是兩個輸出比特的生成多項式的參數(shù)?？梢钥吹剑?該編碼器具有有限沖擊響應( f i n i t ei m p u l s er e s p o n s e ，f i r ) ，具有f i r 特性的卷 積碼也被稱作非系統(tǒng)卷積碼( n o n s y s t e m a t i cc o d e ，n s c ) 。構(gòu)成t u r b o 的每一個 子編碼器就是這一類具有無限沖擊響應( i n f i n i t ei m p u l s er e s p o n s e ，i i r ) 的被稱為 遞歸系統(tǒng)碼r s c 。之所以稱之為“遞歸”，是由于輸出的編碼比特會反饋到編碼 器的輸入端。如果在n s c 結(jié)構(gòu)中引入反饋環(huán)路，同時將輸出對【蠔，v kj 中的任意 一個就設置成輸入比特璣，那么得到的就是相對應的r s c 編碼器結(jié)構(gòu)。圖2 3 是對應圖2 2 的r s c 編碼器結(jié)構(gòu)示意圖。其中： k i 吼= 畋+ g l a hm o d 2 u k v k 圖2 3 ：非系統(tǒng)卷積碼( n s c ) 結(jié)構(gòu)示意圖。 由于g i ： 1 1 1 ，所以2 d k + 畋一- + d k 一2 ；由于g 2 = 1 0 i ，所以咋2 d k +