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

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

2、如何利用各種譯碼方法 , 得到理論性能和實(shí)際應(yīng)用的最佳結(jié)合。 (2,1,3) 卷積碼搭建了簡單的系統(tǒng)來進(jìn)行糾錯(cuò)展示 , 可以實(shí)現(xiàn)從編碼 , 加入錯(cuò)誤 , 譯碼 , 輸入輸出碼字對(duì)比等基本功能 , 另外加入了交互模塊 , 用戶可以自己設(shè)定錯(cuò)誤比特的數(shù)目和位置 , 使糾錯(cuò)功能顯而易見。關(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è)計(jì)要求 .42 信道編解碼理論介紹 .42.1糾錯(cuò)碼基本理論 .42.1.1糾錯(cuò)碼概念 .42.1.2基本原理和性能參數(shù) .42.1.3實(shí)現(xiàn) .42.2信道編碼定理 .52.3幾種常用的糾錯(cuò)碼 .62.4卷積碼編碼原理及算法 .72.4.1卷積碼基本原理 .72.4.2卷積碼糾錯(cuò)性能 .82.5卷積碼表示方法 .82.6卷積碼譯碼方法 .102.7 viterbi 譯碼原理及算法 .11Viterbi譯碼原理簡述 . 112.7.2 Viterbi 譯碼算法描述. 122.8維特比譯碼算法性能 .123 卷積碼編碼與維特比譯碼的設(shè)計(jì)

7、 .133.1卷積碼編碼設(shè)計(jì) .133.1.1卷積碼編碼器原理 .133.1.2卷積碼編碼過程 .133.2 viterbi 譯碼設(shè)計(jì) .153.2.1維特比譯碼器原理 .153.2.2維特比譯碼過程 .163.3對(duì)譯碼算法及實(shí)現(xiàn)的優(yōu)化 .183.3.1留存路徑更新算法優(yōu)化. 183.3.2考慮數(shù)據(jù)溢出問題 .193.3.3優(yōu)化判決輸出 .193.4 交互模塊 .194卷積碼編碼譯碼器的實(shí)現(xiàn) .195總結(jié) .20致謝 .20參考文獻(xiàn) .20附錄 . 21卷積碼編碼與viterbi譯碼的設(shè)計(jì)與實(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)信息源中，模擬信息源（如模擬式電話機(jī)、電視攝像機(jī)）輸出的是幅度連續(xù)變化的信號(hào)，離散信息源（如計(jì)算機(jī)）輸出的是離散的符號(hào)序列或文字。通過采樣和量化可以將模擬信息變換為離散信息。 發(fā)送設(shè)各的基本功能是使不同種類和速率的信息源與傳輸媒介相匹配， 通常是將信息源產(chǎn)生的信息經(jīng)過編碼， 并變換為便于傳送的信號(hào)形式，送往傳輸介質(zhì)。編碼包括信源編碼與信道編碼兩部分。信源編碼把連續(xù)消息變換為數(shù)字信號(hào)，信道編碼則使數(shù)字信號(hào)與傳輸

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

37、們的系數(shù)矢量 g(1,1)=(111)和 g(1,2)=(101) 稱作碼的子生成元。以子生成多項(xiàng)式為陣元構(gòu)成的多項(xiàng)式矩陣G(x) g(1,1)(x),g(1,2)(x) ，稱為碼的生成多項(xiàng)式矩陣。由生成元構(gòu)成的半無限矩陣 稱為碼的生成矩陣。 其中 (11,10,11) 是由 g(1,1) 和 g(1,2) 交叉連接構(gòu)成。編碼器輸出序列為 cu·G，稱為碼序列，其多項(xiàng)式表示為 c(x) ，它可看作是兩個(gè)子碼序列 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)過一個(gè)時(shí)分開關(guān)被分成k0 個(gè)子序列 , 分別以u(píng)(x) 表示 , 其中 i=1 ，2, k0，即 u(x) u(x),u(x)。編碼器的結(jié)構(gòu)由k0×n0階生成多項(xiàng)式矩陣給定。輸出碼序列由n0 個(gè)子序列組成，即c(x) c(x),c(x)， c(x) ，且 c(x)=u(x)·G(x) 。若 m是所有子生成多項(xiàng)式g(x)中最高次式的次數(shù)，稱這種碼為(n0 ，k0， m)卷積碼。卷積碼糾錯(cuò)性能卷積碼中編碼后的n 個(gè)碼元不僅與當(dāng)前段的k 個(gè)信息有關(guān)，而且也與前面（ N-1）段的信息有關(guān)，編碼過程中相互關(guān)聯(lián)的碼元為

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

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

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

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 來代替。編碼器在每一個(gè)時(shí)鐘沿打入一個(gè)輸入信息 x（n），因此圖示內(nèi)容就變?yōu)椋?x（n）， x（ n-1 ）即狀態(tài)發(fā)生了轉(zhuǎn)移，并同時(shí)輸出 G0（ n）、G1（n）。由此我們可以將編碼過程用圖所示的狀態(tài)圖表示。b110100a 0010 d10111101c圖 2 編碼狀態(tài)圖由圖所示，隨著信息序列不斷輸入， 編碼器就不斷從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)并同時(shí)輸出相應(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 輸出其對(duì)應(yīng)的編碼結(jié)果“”。(3) 網(wǎng)格圖狀態(tài)圖可以完整的描述編碼器的工作過程， 但是其只能顯示狀態(tài)轉(zhuǎn)移的過程而不