四川師范大學(xué)本科畢業(yè)設(shè)計

1、四川師范大學(xué)本科畢業(yè)設(shè)計卷積碼編碼與viterbi譯碼的設(shè)計與實現(xiàn)學(xué)生姓名院系名稱物理與電子工程學(xué)院專業(yè)名稱電子信息工程班級2007 級4班學(xué)號20070704指導(dǎo)教師陳萬川完成時間2011年 5月 11日卷積碼編碼與viterbi譯碼的設(shè)計與實現(xiàn)設(shè)計學(xué)生姓名：指導(dǎo)老師：陳萬川內(nèi)容摘要：介紹了數(shù)字通信系統(tǒng)中一種卷積碼為特比譯碼的軟件實現(xiàn)算法 , 在 C 環(huán)境實現(xiàn)了卷積碼 Viterbi 譯碼功能 , 在程序?qū)崿F(xiàn)中充分利用了卷積碼的特性 , 運用網(wǎng)格圖和回溯以得到譯碼輸出。為了在實際中更好地利用卷積碼的優(yōu)異性能, 文章從應(yīng)用角度出發(fā), 對卷積碼的譯碼方法進行了分析 , 給出了在不同的情況下 ,

2、如何利用各種譯碼方法 , 得到理論性能和實際應(yīng)用的最佳結(jié)合。 (2,1,3) 卷積碼搭建了簡單的系統(tǒng)來進行糾錯展示 , 可以實現(xiàn)從編碼 , 加入錯誤 , 譯碼 , 輸入輸出碼字對比等基本功能 , 另外加入了交互模塊 , 用戶可以自己設(shè)定錯誤比特的數(shù)目和位置 , 使糾錯功能顯而易見。關(guān)鍵詞： 卷積編碼；維特比譯碼；卷積碼編碼器; 信道編碼 ; 信息論 ;Design OfDecoding Methods of Convolutional CodesAbstract:Describes a digital communication system, convolutional code is Vi

3、terbi decoding algorithm of the software.In the C environment to achieve the convolutional code Viterbi decoding functions . In the program to achieve full useof the characteristics of convolutional codes, using the grid map and to get the decoder output .In order to practically utilize the excellen

4、t performance of convolutional codes ,several decoding methods of convolutional codes are analyzed in the paper from the application angle . (2,1,3) Convolutional Codes built a simple system for correcting display can be realized from coding, joined errors, decoding, the input and output code contra

5、st basic functions, adding to its interactive modules, Users can set their own errors and the number of bits, so that error-correcting functions obvious.Key words :convolution code ; viterbi decoding； convolutional coder ;channelcoding ;information t heory.目錄1 概述.11.1課題背景及意義 .11.1.1數(shù)字通信系統(tǒng) .11.1.2信道編

6、解碼 .21.2卷積碼編碼與維特比譯碼的發(fā)展應(yīng)用. 31.3設(shè)計要求 .42 信道編解碼理論介紹 .42.1糾錯碼基本理論 .42.1.1糾錯碼概念 .42.1.2基本原理和性能參數(shù) .42.1.3實現(xiàn) .42.2信道編碼定理 .52.3幾種常用的糾錯碼 .62.4卷積碼編碼原理及算法 .72.4.1卷積碼基本原理 .72.4.2卷積碼糾錯性能 .82.5卷積碼表示方法 .82.6卷積碼譯碼方法 .102.7 viterbi 譯碼原理及算法 .11Viterbi譯碼原理簡述 . 112.7.2 Viterbi 譯碼算法描述. 122.8維特比譯碼算法性能 .123 卷積碼編碼與維特比譯碼的設(shè)計

7、 .133.1卷積碼編碼設(shè)計 .133.1.1卷積碼編碼器原理 .133.1.2卷積碼編碼過程 .133.2 viterbi 譯碼設(shè)計 .153.2.1維特比譯碼器原理 .153.2.2維特比譯碼過程 .163.3對譯碼算法及實現(xiàn)的優(yōu)化 .183.3.1留存路徑更新算法優(yōu)化. 183.3.2考慮數(shù)據(jù)溢出問題 .193.3.3優(yōu)化判決輸出 .193.4 交互模塊 .194卷積碼編碼譯碼器的實現(xiàn) .195總結(jié) .20致謝 .20參考文獻 .20附錄 . 21卷積碼編碼與viterbi譯碼的設(shè)計與實現(xiàn)1 概述1.1課題背景及意義數(shù)字通信系統(tǒng)數(shù)字通信系統(tǒng)是傳遞信息所需的一切技術(shù)設(shè)備的總和， 包括信息源

8、、 發(fā)送設(shè)各、傳輸介質(zhì)、信息接收者和接收設(shè)備。 數(shù)字通信系統(tǒng)傳輸?shù)臄?shù)據(jù)是數(shù)字化了的信息。單向數(shù)字通信系統(tǒng)的結(jié)構(gòu)，如圖 1 所示信息編碼調(diào)制源傳輸介質(zhì)噪聲擾接收譯碼解制者圖 1 數(shù)字通信系統(tǒng)信息源中，模擬信息源（如模擬式電話機、電視攝像機）輸出的是幅度連續(xù)變化的信號，離散信息源（如計算機）輸出的是離散的符號序列或文字。通過采樣和量化可以將模擬信息變換為離散信息。 發(fā)送設(shè)各的基本功能是使不同種類和速率的信息源與傳輸媒介相匹配， 通常是將信息源產(chǎn)生的信息經(jīng)過編碼， 并變換為便于傳送的信號形式，送往傳輸介質(zhì)。編碼包括信源編碼與信道編碼兩部分。信源編碼把連續(xù)消息變換為數(shù)字信號，信道編碼則使數(shù)字信號與傳輸

9、介質(zhì)匹配， 提高傳輸?shù)目煽啃院陀行浴?調(diào)制是多種變換方式中最常見的一種。 發(fā)送設(shè)各還包括為達到某些特殊要求所進行的各種處理，如多路復(fù)用、保密處理、糾錯編碼處理等。傳輸介質(zhì)是發(fā)送設(shè)備到接收設(shè)備之間信號傳遞所經(jīng)過的媒介， 例如：電磁波、紅外線等無線傳輸介質(zhì)，各種電纜、光纜、雙絞線等有線傳輸介質(zhì)。傳輸過程中必然會引入熱噪聲、 衰減、脈沖等干擾。 介質(zhì)的固有特性和干擾特性直接關(guān)系到編碼方式的選取。接收設(shè)備的基本功能是完成對發(fā)送的反變換（解調(diào)、譯碼、解密等），從帶有干擾的信號中恢復(fù)出正確的原始信息， 對于多路復(fù)用信號還包括解除多路復(fù)用和實現(xiàn)正確分路（或稱輸出掃描）。雙向通信要求通信雙方都有發(fā)送設(shè)備和接

10、收設(shè)備， 如果兩個方向共用一個傳輸媒介，則必須采用分頻或分時的辦法。 信息的傳輸系統(tǒng)和交換系統(tǒng)組成完整的通信系統(tǒng)，直至構(gòu)成復(fù)雜的通信網(wǎng)絡(luò)。信道編解碼數(shù)字信號在傳輸中往往由于各種原因， 使得在傳送的數(shù)據(jù)流中產(chǎn)生誤碼， 從而使接收端產(chǎn)生圖象跳躍、 不連續(xù)、出現(xiàn)馬賽克等現(xiàn)象。 所以通過信道編碼這一環(huán)節(jié)，對數(shù)碼流進行相應(yīng)的處理， 使系統(tǒng)具有一定的糾錯能力和抗干擾能力， 可極大地避免碼流傳送中誤碼的發(fā)生。 誤碼的處理技術(shù)有糾錯、 交織、線性內(nèi)插等。提高數(shù)據(jù)傳輸效率， 降低誤碼率是信道編碼的任務(wù)。 信道編碼的本質(zhì)是增加通信的可靠性。 但信道編碼會使有用的信息數(shù)據(jù)傳輸減少， 信道編碼的過程是在源數(shù)據(jù)碼流中加

11、插一些碼元， 從而達到在接收端進行判錯和糾錯的目的， 這就是我們常常說的開銷。 這就好象我們運送一批玻璃杯一樣， 為了保證運送途中不出現(xiàn)打爛玻璃杯的情況， 我們通常都用一些泡沫或海棉等物將玻璃杯包裝起來， 這種包裝使玻璃杯所占的容積變大，原來一部車能裝 5000 各玻璃杯的，包裝后就只能裝 4000 個了，顯然包裝的代價使運送玻璃杯的有效個數(shù)減少了。同樣，在帶寬固定的信道中， 總的傳送碼率也是固定的， 由于信道編碼增加了數(shù)據(jù)量， 其結(jié)果只能是以降低傳送有用信息碼率為代價了。 將有用比特數(shù)除以總比特數(shù)就等于編碼效率了，不同的編碼方式，其編碼效率有所不同。數(shù)字電視中常用的糾錯編碼，通常采用兩次附加

12、糾錯碼的前向糾錯（ FEC）編碼。RS編碼屬于第一個 FEC，188 字節(jié)后附加 16 字節(jié) RS碼，構(gòu)成（204，188）RS碼，這也可以稱為外編碼。第二個附加糾錯碼的 FEC一般采用卷積編碼，又稱為內(nèi)編碼。 外編碼和內(nèi)編碼結(jié)合一起， 稱之為級聯(lián)編碼。 級聯(lián)編碼后得到的數(shù)據(jù)流再按規(guī)定的調(diào)制方式對載頻進行調(diào)制。前向糾錯碼（ FEC）的碼字是具有一定糾錯能力的碼型， 它在接收端解碼后，不僅可以發(fā)現(xiàn)錯誤， 而且能夠判斷錯誤碼元所在的位置， 并自動糾錯。 這種糾錯碼信息不需要儲存， 不需要反饋， 實時性好。所以在單向傳輸系統(tǒng)都采用這種信道編碼方式。信道編碼又稱糾錯編碼， 它與信源編碼是信息傳輸?shù)膬蓚€

13、方面。 它們之間存在對偶的關(guān)系。應(yīng)用信道譯碼直接對一些自然信息進行處理，可以去掉剩余度，以達到壓縮數(shù)據(jù)的目的。為了使一種碼具有檢錯或糾錯能力， 必須對原碼字增加多余的碼元， 以擴大碼字之間的差別， 使一個碼字在一定數(shù)目內(nèi)的碼元上發(fā)生錯誤時， 不致錯成另一個碼字。準(zhǔn)確地說， 即把原碼字按某種規(guī)則變成有一定剩余度的碼字， 并使每個碼字的碼元間有一定的關(guān)系。 關(guān)系的建立稱為編碼。 碼字到達收端后， 用編碼時所用的規(guī)則去檢驗。如果沒有錯誤，則原規(guī)則一定滿足，否則就不滿足。由此可以根據(jù)編碼規(guī)則是否滿足以判定有無錯誤。 當(dāng)不能滿足時， 在可糾能力之內(nèi)按一定的規(guī)則確定錯誤所在的位置， 并予以糾正。糾錯并恢復(fù)

14、原碼字的過程稱為譯碼；碼元間的關(guān)系為線性時， 稱為線性碼； 否則稱為非線性碼。 檢錯碼與其他手段結(jié)合使用，可以糾錯。檢錯反饋重發(fā)系統(tǒng)（ARQ系統(tǒng)）就是一例。在構(gòu)造糾錯碼時，將輸入信息分成k 位一組以進行編碼。若編出的校驗位僅與本組的信息位有關(guān)，則稱這樣的碼為分組碼。若不僅與本組的k 個信息位有關(guān)，而且與前若干組的信息位有關(guān)，則稱為格碼。這種碼之所以稱為格碼，是因為用圖形分析時它象籬笆或格架。線性格碼在運算時為卷積運算，所以叫卷積碼。卷積碼是深度空間通信系統(tǒng)和無線通信系統(tǒng)中常用的一種差錯控制編碼。 在編碼過程中 , 卷積碼充分利用了各碼字間的相關(guān)性。在與分組碼同樣的碼率和設(shè)備復(fù)雜性的條件下 ,

15、無論從理論上還是從實踐上都證明 , 卷積碼的性能都比分組碼具有優(yōu)勢。而且卷積碼在實現(xiàn)最佳譯碼方面也較分組碼容易。 因此卷積碼廣泛應(yīng)用于衛(wèi)星通信， CDMA數(shù)字移動通信等通信系統(tǒng)，是很有前途的一種編碼方式。對其進行研究有很大的現(xiàn)實意義。1.2 卷積碼編碼與維特比譯碼的發(fā)展應(yīng)用在現(xiàn)代通信系統(tǒng)中 , 前向糾錯編碼 (FEC)得到了廣泛的應(yīng)用。其中 , 卷積編碼是應(yīng)用最廣泛的一種。 C.E. 仙農(nóng)在 1948 年發(fā)表在通信的數(shù)學(xué)理論一文中的信道編碼定理指出： 只要采用適當(dāng)?shù)募m錯碼， 就可在多類信道上傳輸消息， 其誤碼率 pe 可以任意小。可惜的是這一定理僅僅指出理論上可以達到的目標(biāo)，而未能給出構(gòu)造性的

16、實現(xiàn)方法。 自仙農(nóng)的論文發(fā)表以來， 人們經(jīng)過持續(xù)不懈的努力已找到多種好碼，可以滿足許多實用要求。 但在理論上，仍存在一些問題未能解決。R.W.漢明于 1950 年首先給出可以糾正一個獨立錯誤的線性分組碼漢明碼。差不多與此同時 E. 戈雷給出一種可以糾正三個錯誤的完備碼。完備碼雖然十分罕見，但有較大實用意義。1954 年 D.E. 莫勒提出一種能糾正多個錯誤的碼； I.S. 里德則立即給出它的譯碼方法，用的是擇多判決法，這種碼常稱為 RM碼。1957 年，E. 普勒齊引入了循環(huán)碼的概念。 19591960 年出現(xiàn)了 BCH碼, 引進有限域 的概念，解決了循環(huán)碼的構(gòu)造和性能估計等基本問題。后來成為

17、線性分組碼中最重要的一類碼。 它能糾正多個錯誤， 且在實用范圍內(nèi)接近信道編碼定理所指出的誤碼率值。 但當(dāng) n 增大時，其誤碼率不能呈指數(shù)下降。 BCH碼的譯碼問題是 W.W.彼得森解決的 ; 錢天聞則提供了一種系統(tǒng)地搜索根的方法。1967 年， E.R. 伯利坎普提出一種迭代算法，大大簡化了譯碼，使糾錯碼趨于實用。1970 年 . . 戈帕提出一種線性分組碼的構(gòu)造方法，原則上它可以達到吉爾伯特限，實現(xiàn)了理論上預(yù)期的目標(biāo)。 但至今仍未解決如何具體構(gòu)造這種碼的問題。卷積碼最早由 P. 伊萊亞斯于 1955 年提出。它的糾錯能力較強，設(shè)備復(fù)雜程度與分組碼大體相當(dāng)。首先獲得成功的譯碼方法是序列譯碼。

18、1967 年 A.J. 維特比提出的譯碼算法，能較好地按最大似然準(zhǔn)則譯碼，且在許多領(lǐng)域中均可應(yīng)用。卷積碼是深度空間通信系統(tǒng)和無線通信系統(tǒng)中常用的一種差錯控制編碼。 在編碼過程中 , 卷積碼充分利用了各碼字間的相關(guān)性。在與分組碼同樣的碼率和設(shè)備復(fù)雜性的條件下 , 無論從理論上還是從實踐上都證明 , 卷積碼的性能都比分組碼具有優(yōu)勢。在卷積碼譯碼過程中，不僅從此時刻收到的碼組中提取譯碼信息，而且還要利用以前或以后各時刻收到的碼組中提取有關(guān)信息。而且卷積碼的糾錯能力隨約束長度的增加而增強，差錯率則隨著約束長度增加而呈指數(shù)下降 。卷積碼 (n,k,m) 主要用來糾隨機錯誤， 它的碼元與前后碼元有一定的約

19、束關(guān)系而且卷積碼在實現(xiàn)最佳譯碼方面也較分組碼容易。因此卷積碼廣泛應(yīng)用于衛(wèi)星通信，CDMA數(shù)字移動通信等通信系統(tǒng)，是很有前途的一種編碼方式。對其進行研究有很大的現(xiàn)實意義。1.3 設(shè)計要求本題目的基本任務(wù)就是根據(jù)編碼理論中所學(xué)習(xí)的卷積碼編碼方法和viterbi 譯碼方法，運用 C或 C+來設(shè)計開發(fā)一個編譯碼軟件，實現(xiàn)對信息的編碼和譯碼。要求所設(shè)計實現(xiàn)的編譯碼軟件操作簡便、快捷。本題目的實現(xiàn)主要涉及到編碼理論、 C程序設(shè)計（或面向?qū)ο蟪绦蛟O(shè)計）等課程的相關(guān)內(nèi)容，必須對相關(guān)知識熟練掌握。2 信道編解碼理論介紹2.1 糾錯碼基本理論糾錯碼概念糾錯碼 (error correcting code) ，在傳

20、輸過程中發(fā)生錯誤后能在收端自行發(fā)現(xiàn)或糾正的碼。 僅用來發(fā)現(xiàn)錯誤的碼一般常稱為檢錯碼。 為使一種碼具有檢錯或糾錯能力，須對原碼字增加多余的碼元，以擴大碼字之間的差別 ，即把原碼字按某種規(guī)則變成有一定剩余度 （見信源編碼） 的碼字，并使每個碼字的碼之間有一定的關(guān)系。 關(guān)系的建立稱為編碼。 碼字到達收端后， 可以根據(jù)編碼規(guī)則是否滿足以判定有無錯誤。當(dāng)不能滿足時，按一定規(guī)則確定錯誤所在位置并予以糾正。糾錯并恢復(fù)原碼字的過程稱為譯碼。檢錯碼與其他手段結(jié)合使用，可以糾錯?；驹砗托阅軈?shù)糾錯碼能夠檢錯或糾錯， 主要是靠碼字之間有較大的差別。 這可用碼字之間的漢明距離 d(x ，y) 來衡量。它的定義為碼

21、字 x 與 y 之間的對應(yīng)位取不同值的碼元個數(shù)。一種糾錯碼的最小距離 d 定義為該種碼中任兩個碼字之間的距離的最小值。一種碼要能發(fā)現(xiàn) e 個錯誤 , 它的最小距離 d 應(yīng)不小于 e+1。若要能糾正 t 個錯誤，則 d 應(yīng)不小于 2t+1 。一個碼字中非零碼元的個數(shù)，稱為此碼字的漢明重量。一種碼中非零碼字的重量的最小值， 稱為該碼的最小重量。 對線性碼來說，一種碼的最小重量與其最小距離在數(shù)值上是相等的。在構(gòu)造線性碼時， 數(shù)字上是從 n 維空間中選一 k 維子空間，且使此子空間內(nèi)各非零碼字的重量盡可能大。當(dāng)構(gòu)造循環(huán)碼時 , 可進一步將每一碼字看成一多項式 , 將整個碼看成是多項式環(huán)中的理想 , 這

22、一理想是主理想 , 故可由生成多項式?jīng)Q定；而多項式完全可由它的根規(guī)定。 這樣 , 就容易對碼進行構(gòu)造和分析。 這是 BCH 碼等循環(huán)碼構(gòu)造的出發(fā)點。 一般地說，構(gòu)造一種碼時， 均設(shè)法將它與某種代數(shù)結(jié)構(gòu)相聯(lián)系，以便對它進行描述， 進而推導(dǎo)它的性質(zhì)， 估計它的性能和給出它的譯碼方法。若一種碼的碼長為 n，碼字?jǐn)?shù)為 M,或信息位為 h, 以及最小距離為 d，則可把此碼記作【 n,M,d 】碼。若此碼為線性碼，常簡記作 (n ，k) 或(n,k,d) 碼。人們還常用 R=log2M/n 表示碼的信息率或簡稱碼率 , 單位為比特 / 碼元。 R越大 , 則每個碼元所攜帶的信息量越大，編碼效率越高。實現(xiàn)糾

23、錯碼實現(xiàn)中最復(fù)雜的部分是譯碼。 它是糾錯碼能否應(yīng)用的關(guān)鍵。 根據(jù)式 (1), 采用的碼長 n 越大 , 則誤碼率越小。 但 n 越大，編譯碼設(shè)備也越復(fù)雜 , 且延遲也越大。人們希望找到的譯碼方法是 : 誤碼率隨碼長 n 的增加按指數(shù)規(guī)律下降 ; 譯碼的復(fù)雜程度隨碼長 n 的增加接近線性地增加； 譯碼的計算量則與碼長 n 基本無關(guān)。可惜，已經(jīng)找到的碼能滿足這樣要求的很少。不過由于大規(guī)模集成電路的發(fā)展，既使應(yīng)用比較復(fù)雜的但性能良好的碼， 成本也并不太高。 因此，糾錯碼的應(yīng)用越來越廣泛。糾錯碼傳輸?shù)亩际菙?shù)字信號。 這既可用硬件實現(xiàn)， 也可用軟件實現(xiàn)。 前者主要用各種數(shù)字電路， 主要是采用大規(guī)模集成電

24、路。 軟件實現(xiàn)特別適合計算機通信網(wǎng)等場合。因為這時可以直接利用網(wǎng)中的計算機進行編碼和譯碼， 不需要另加專用設(shè)備。硬件實現(xiàn)的速度較高，比軟件可快幾個數(shù)量級。在傳信率一定的情況下， 如果采用糾錯碼提高可靠性， 要求信道的傳輸率增加，帶寬加大。因此，糾錯碼主要用于功率受限制而帶寬較大的信道，如衛(wèi)星、散射等系統(tǒng)中。糾錯碼還用在一些可靠性要求較高， 但設(shè)備或器件的可靠性較差，而余量較大的場合，如磁帶、磁盤和半導(dǎo)體存儲器等。在分組碼的研究中， 譜分析的方法受到人們的重視。 糾同步錯誤碼、算術(shù)碼、不對稱碼、不等錯誤糾正碼等，也得到較多的研究。2.2 信道編碼定理C.E. 仙農(nóng)在 1948 年發(fā)表在通信的數(shù)學(xué)

25、理論 一文中的信道編碼定理指出：只要采用適當(dāng)?shù)募m錯碼，就可在多類信道上傳輸消息，其誤碼率pe 可以任意小PeeNE(R)（1）(1) 式中 N 為碼長； Er(R) 為信息率 R 的函數(shù) , 與信道有關(guān)。當(dāng) R 小于信道容量 C 時,Er(R) 為正值?？上У氖沁@一定理僅僅指出理論上可以達到的目標(biāo)， 而未能給出構(gòu)造性的實現(xiàn)方法。 自仙農(nóng)的論文發(fā)表以來， 人們經(jīng)過持續(xù)不懈的努力已找到多種好碼，可以滿足許多實用要求。 但在理論上，仍存在一些問題未能解決。R.W.漢明于 1950 年首先給出可以糾正一個獨立錯誤的線性分組碼漢明碼。差不多與此同時 E. 戈雷給出一種可以糾正三個錯誤的完備碼。完備碼雖然

26、十分罕見，但有較大實用意義。 1954 年 D.E. 莫勒提出一種能糾正多個錯誤的碼；I.S. 里德則立即給出它的譯碼方法，用的是擇多判決法，這種碼常稱為 RM碼。 1957 年，E. 普勒齊引入了循環(huán)碼的概念。 1959 1960 年出現(xiàn)了 BCH碼 , 引進有限域的概念，解決了循環(huán)碼的構(gòu)造和性能估計等基本問題。 后來成為線性分組碼中最重要的一類碼。 它能糾正多個錯誤， 且在實用范圍內(nèi)接近信道編碼定理所指出的誤碼率值。但當(dāng) n 增大時，其誤碼率不能呈指數(shù)下降。 BCH碼的譯碼問題是W.W.彼得森解決的 ; 錢天聞則提供了一種系統(tǒng)地搜索根的方法。1967 年， E.R. 伯利坎普提出一種迭代算

27、法，大大簡化了譯碼，使糾錯碼趨于實用。 1970 年 . . 戈帕提出一種線性分組碼的構(gòu)造方法，原則上它可以達到吉爾伯特限， 實現(xiàn)了理論上預(yù)期的目標(biāo)。 但至今仍未解決如何具體構(gòu)造這種碼的問題。卷積碼最早由 P. 伊萊亞斯于 1955 年提出。它的糾錯能力較強，設(shè)備復(fù)雜程度與分組碼大體相當(dāng)。首先獲得成功的譯碼方法是序列譯碼。 1967 年 A.J. 維特比提出的譯碼算法，能較好地按最大似然準(zhǔn)則譯碼，且在許多領(lǐng)域中均可應(yīng)用。卷積碼還可用代數(shù)方法譯碼。 它的設(shè)備雖較簡單， 但性能較差。 卷積碼在理論上不如分組碼成熟，所用的工具也比較多樣，尚缺乏系統(tǒng)的、統(tǒng)一的方法處理。分組碼和卷積碼不但可以用來糾正獨

28、立錯誤， 而且可以用來恢復(fù)刪除錯誤和糾正突發(fā)錯誤。 如分組碼中有里德 - 索洛蒙碼 , 法爾碼等；卷積碼中有巖垂碼及擴散卷積碼等。為了實現(xiàn)低的誤碼率，根據(jù)式(1) ，要求碼長 n 較大。但已知的大多數(shù)碼，當(dāng) n 變大時不是性能欠佳或者難以構(gòu)造，就是譯碼過分復(fù)雜，不容易實現(xiàn)。但是，可以利用好的碼進行級連，以得到性能更好的碼。級連碼的內(nèi)碼和外碼，用分組碼和卷積碼都可以。這在深空通信中應(yīng)用較多。2.3 幾種常用的糾錯碼（1）RS編碼RS碼即里德 - 所羅門碼，它是能夠糾正多個錯誤的糾錯碼， RS碼為（204，188，t=8 ），其中 t 是可抗長度字節(jié)數(shù)，對應(yīng)的 188 符號，監(jiān)督段為 16 字節(jié)

29、( 開銷字節(jié)段）。實際中實施（ 255，239，t=8 ）的 RS編碼，即在 204 字節(jié)（包括同步字節(jié)）前添加 51 個全“ 0”字節(jié)， 產(chǎn)生 RS碼后丟棄前面 51 個空字節(jié)， 形成截短的（ 204， 188）RS碼。 RS的編碼效率是： 188/204 。（2）卷積碼卷積碼非常適用于糾正隨機錯誤， 但是，解碼算法本身的特性卻是： 如果在解碼過程中發(fā)生錯誤， 解碼器可能會導(dǎo)致突發(fā)性錯誤。 為此在卷積碼的上部采用RS碼塊， RS 碼適用于檢測和校正那些由解碼器產(chǎn)生的突發(fā)性錯誤。 所以卷積碼和 RS碼結(jié)合在一起可以起到相互補償?shù)淖饔?。卷積碼分為兩種：基本卷積碼 :基本卷積碼編碼效率為，1/2,

30、編碼效率較低 , 優(yōu)點是糾錯能力強。收縮卷積碼 :如果傳輸信道質(zhì)量較好， 為提高編碼效率， 可以采樣收縮截短卷積碼。 有編碼效率為： 1/2 、2/3 、3/4 、 5/6 、7/8 這幾種編碼效率的收縮卷積碼。編碼效率高，一定帶寬內(nèi)可傳輸?shù)挠行П忍芈试龃?, 但糾錯能力越減弱。（3）Turbo 碼1993 年誕生的 Turbo 碼，單片 Turbo 碼的編碼 / 解碼器，運行速率達40Mb/s。該芯片集成了一個 32×32 交織器，其性能和傳統(tǒng)的 RS 外碼和卷積內(nèi)碼的級聯(lián)一樣好。 所以 Turbo 碼是一種先進的信道編碼技術(shù)， 由于其不需要進行兩次編碼，所以其編碼效率比傳統(tǒng)的 R

31、S+卷積碼要好。（4）交織在實際應(yīng)用中， 比特差錯經(jīng)常成串發(fā)生， 這是由于持續(xù)時間較長的衰落谷點會影響到幾個連續(xù)的比特， 而信道編碼僅在檢測和校正單個差錯和不太長的差錯串時才最有效（如 RS只能糾正 8 個字節(jié)的錯誤）。為了糾正這些成串發(fā)生的比特差錯及一些突發(fā)錯誤， 可以運用交織技術(shù)來分散這些誤差， 使長串的比特差錯變成短串差錯，從而可以用前向碼對其糾錯， 例如：在 DVB-C系統(tǒng)中，RS(204,188)的糾錯能力是 8 個字節(jié)，交織深度為 12，那么糾可抗長度為 8× 12 96 個字節(jié)的突發(fā)錯誤。實現(xiàn)交織和解交織一般使用卷積方式。交織技術(shù)對已編碼的信號按一定規(guī)則重新排列， 解交

32、織后突發(fā)性錯誤在時間上被分散，使其類似于獨立發(fā)生的隨機錯誤， 從而前向糾錯編碼可以有效的進行糾錯，前向糾錯碼加交積的作用可以理解為擴展了前向糾錯的可抗長度字節(jié)。 糾錯能力強的編碼一般要求的交織深度相對較低。 糾錯能力弱的則要求更深的交織深度。一般來說，對數(shù)據(jù)進行傳輸時， 在發(fā)端先對數(shù)據(jù)進行 FEC編碼，然后再進行交積處理。在收端次序和發(fā)端相反， 先做去交積處理完成誤差分散， 再 FEC解碼實現(xiàn)數(shù)據(jù)糾錯。交積不會增加信道的數(shù)據(jù)碼元。（5）偽隨機序列擾碼進行基帶信號傳輸?shù)娜秉c是其頻譜會因數(shù)據(jù)出現(xiàn)連“ 1”和連“ 0”而包含大的低頻成分，不適應(yīng)信道的傳輸特性 , 也不利于從中提取出時鐘信息。解決辦法

33、之一是采用擾碼技術(shù) , 使信號受到隨機化處理，變?yōu)閭坞S機序列，又稱為“數(shù)據(jù)隨機化”和“能量擴散”處理。 擾碼不但能改善位定時的恢復(fù)質(zhì)量， 還可以使信號頻譜平滑，使幀同步和自適應(yīng)同步和自適應(yīng)時域均衡等系統(tǒng)的性能得到改善。擾碼雖然“擾亂”了原有數(shù)據(jù)的本來規(guī)律， 但因為是人為的“擾亂”， 在接收端很容易去加擾，恢復(fù)成原數(shù)據(jù)流。實現(xiàn)加擾和解碼， 需要產(chǎn)生偽隨機二進制序列 （PRBS）再與輸入數(shù)據(jù)逐個比特作運算。PRBS也稱為 m序列，這種 m序列與 TS 的數(shù)據(jù)碼流進行模 2 加運算后，數(shù)據(jù)流中的“ 1”和“ 0”的連續(xù)游程都很短，且出現(xiàn)的概率基本相同。利用偽隨機序列進行擾碼也是實現(xiàn)數(shù)字信號高保密性傳

34、輸?shù)闹匾侄沃?。一般將信源產(chǎn)生的二進制數(shù)字信息和一個周期很長的偽隨即序列模 2 相加，就可將原信息變成不可理解的另一序列。這種信號在信道中傳輸自然具有高度保密性。在接收端將接收信號再加上（模 2 和）同樣的偽隨機序列，就恢復(fù)為原來發(fā)送的信息。2.4 卷積碼編碼原理及算法卷積碼基本原理卷積碼是 1955 年由 Elias 等人提出的，是一種非常有前途的編碼方法。我們在一些資料上可以找到關(guān)于分組碼的一些介紹， 分組碼的實現(xiàn)是將編碼信息分組單獨進行編碼，因此無論是在編碼還是譯碼的過程中不同碼組之間的碼元無關(guān)。卷積碼和分組碼的根本區(qū)別在于， 它不是把信息序列分組后再進行單獨編碼，而是由連續(xù)輸入的信息

35、序列得到連續(xù)輸出的已編碼序列。 即進行分組編碼時， 其本組中的 n-k 個校驗員僅與本組的 k 個信息元有關(guān)， 而與其它各組信息無關(guān)； 但在卷積碼中，其編碼器將 k 個信息碼元編為 n 個碼元時，這 n 個碼元不僅與當(dāng)前段的 k 個信息有關(guān)，而且與前面的（ m 1）段信 息有關(guān)（ m為編碼的約束長度） 。同樣，在卷積碼譯碼過程中， 不僅從此時刻收到的碼組中提取譯碼信息， 而且還要利用以前或以后各時刻收到的碼組中提取有關(guān)信息。 而且卷積碼的糾錯能力隨約束長度的增加而增強，差錯率則隨著約束長度增加而呈指數(shù)下降 。卷積碼 (n,k,m) 主要用來糾隨機錯誤， 它的碼元與前后碼元有一定的約束關(guān)系， 編

36、碼復(fù)雜度可用編碼約束長度 m*n 來表示。一般地，最小距離 d 表明了卷積碼在連續(xù)m段以內(nèi)的距離特性，該碼可以在 m個連續(xù)碼流內(nèi)糾正 (d-1)/2 個錯誤。卷積碼的糾錯能力不僅與約束長度有關(guān)，還與采用的譯碼方式有關(guān)?？傊?，由于 n， k 較小，且利用了各組之間的相關(guān)性， 在同樣的碼率和設(shè)備的復(fù)雜性條件下， 無論理論上還是實踐上都證明：卷積碼的性能至少不比分組碼差。以二元碼為例。輸入信息序列為 u (u0 ，u1， ) ，其多項式表示為 u(x) u0+u1x ulxl 。編碼器的連接可用多項式表示為 g(1,1)(x) 1+x+x2 和 g(1,2)(x) 1+x2，稱為碼的子生成多項式。它

37、們的系數(shù)矢量 g(1,1)=(111)和 g(1,2)=(101) 稱作碼的子生成元。以子生成多項式為陣元構(gòu)成的多項式矩陣G(x) g(1,1)(x),g(1,2)(x) ，稱為碼的生成多項式矩陣。由生成元構(gòu)成的半無限矩陣 稱為碼的生成矩陣。 其中 (11,10,11) 是由 g(1,1) 和 g(1,2) 交叉連接構(gòu)成。編碼器輸出序列為 cu·G，稱為碼序列，其多項式表示為 c(x) ，它可看作是兩個子碼序列 c(1)(x) 和 c(2)(x) 經(jīng)過合路開關(guān) S 合成的，其中 c(1)(x) u(x)g(1,1)(x)和 c(2)(x)u(x)g(1,2)(x),它們分別是信息序列

38、和相應(yīng)子生成元的卷積，卷積碼由此得名。在一般情況下，輸入信息序列經(jīng)過一個時分開關(guān)被分成k0 個子序列 , 分別以u(x) 表示 , 其中 i=1 ，2, k0，即 u(x) u(x),u(x)。編碼器的結(jié)構(gòu)由k0×n0階生成多項式矩陣給定。輸出碼序列由n0 個子序列組成，即c(x) c(x),c(x)， c(x) ，且 c(x)=u(x)·G(x) 。若 m是所有子生成多項式g(x)中最高次式的次數(shù)，稱這種碼為(n0 ，k0， m)卷積碼。卷積碼糾錯性能卷積碼中編碼后的n 個碼元不僅與當(dāng)前段的k 個信息有關(guān)，而且也與前面（ N-1）段的信息有關(guān)，編碼過程中相互關(guān)聯(lián)的碼元為

39、nN個。因此，這 N時間內(nèi)的碼元數(shù)目 nN 通常被稱為這種碼的約束長度。卷積碼的糾錯能力隨著 N 的增加而增大，在編碼器復(fù)雜程度相同的情況下，卷段積碼的性能優(yōu)于分組碼。卷積碼也是分組的 , 但它的監(jiān)督元不僅與本組的信息元有關(guān) , 而且還與前若干組的信息元有關(guān)。卷積碼根據(jù)需要 , 有不同的結(jié)構(gòu)及相應(yīng)的糾錯能力 , 但都有類似的編碼規(guī)律。值得指出的是一種 ( 2, 1) 卷積碼 , 其碼率為 1 /2, 它的監(jiān)督位只有 1 位, 編碼效率較高 , 也比較簡單。如使用較長的約束長度 , 則既可以糾正突發(fā)差錯 , 也可以糾正隨機差錯。2.5 卷積碼表示方法描述卷積碼編碼器過程的方法有很多， 如矩陣法、

40、多項式、碼樹和網(wǎng)格圖等，這里我們主要介紹和卷積碼編碼器結(jié)構(gòu)密切相關(guān)的多項式法， 以及與卷積碼譯碼密切相關(guān)的網(wǎng)格圖法。(1) 多項式法以二元碼為例。輸入信息序列為 u (u0 ，u1， ) ，其多項式表示為 u(x) u0+u1x ulxl 。編碼器的連接可用多項式表示為 g(1,1)(x) 1+x+x2和 g(1,2)(x) 1+x2，稱為碼的子生成多項式。它們的系數(shù)矢量 g(1,1)=(111)和 g(1,2)=(101) 稱作碼的子生成元。以子生成多項式為陣元構(gòu)成的多項式矩陣G(x) g(1,1)(x),g(1,2)(x) ，稱為碼的生成多項式矩陣。由生成元構(gòu)成的半無限矩陣（ 2）稱為碼的

41、生成矩陣。 其中 (11,10,11) 是由 和輸出序列為 cu·G，稱為碼序列， 其多項式表示為c(x)交叉連接構(gòu)成。 編碼器，它可看作是兩個子碼序列 c(x) 和c(x) u(x)gc(x) (x),經(jīng)過合路開關(guān) S 合成的，其中 c (x) u(x)它們分別是信息序列和相應(yīng)子生成元的卷積，· (x) 和卷積碼由此得名。在一般情況下，輸入信息序列經(jīng)過一個時分開關(guān)被分成u(x) 表示 , 其中 i=1 ，2, k0，即 u(x) u(x), ,u由 k0×n0 階生成多項式矩陣k0 (x)個子序列 , 分別以。編碼器的結(jié)構(gòu)(3)給定。輸出碼序列由n0 個子序列組

42、成，即c(x) c(x),c(x) ， c(x) ，且 c(x)=u(x)·G(x) 。(2) 狀態(tài)圖將編碼器寄存器中的內(nèi)容組合（ x（n-1 ）、 x（n-2 ）定義為編碼器狀態(tài)。如以 (2 ，1，2) 為例，則該編碼器的狀態(tài)有四種： 00，10，01 和 11，下面分別用a，b，c，d 來代替。編碼器在每一個時鐘沿打入一個輸入信息 x（n），因此圖示內(nèi)容就變?yōu)椋?x（n）， x（ n-1 ）即狀態(tài)發(fā)生了轉(zhuǎn)移，并同時輸出 G0（ n）、G1（n）。由此我們可以將編碼過程用圖所示的狀態(tài)圖表示。b110100a 0010 d10111101c圖 2 編碼狀態(tài)圖由圖所示，隨著信息序列不斷輸入， 編碼器就不斷從一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)并同時輸出相應(yīng)的碼序列， 所以圖 2 所示狀態(tài)圖可以簡單直觀的描述編碼器的編碼過程。因此通過狀態(tài)圖很容易給出輸入信息序列的編碼結(jié)果， 假定輸入序列為 110100，首先從零狀態(tài)開始即圖示 a 狀態(tài)，由于輸入信息為“ 1”，所以下一狀態(tài)為 c 并輸出“ 11”，繼續(xù)輸入信息“ 1”，由圖知下一狀態(tài)為 d、輸出“01”其它輸入信息依次類推，按照狀態(tài)轉(zhuǎn)移路徑 a->c->d->b->c->b->a 輸出其對應(yīng)的編碼結(jié)果“”。(3) 網(wǎng)格圖狀態(tài)圖可以完整的描述編碼器的工作過程， 但是其只能顯示狀態(tài)轉(zhuǎn)移的過程而不