1、.通 信 原 理程琳 蘭州大學(xué)信息科學(xué)與技術(shù)學(xué)院電信系M.Pmail: chenglin or chenglinwttAddress：Department of Electronics & Information Science, School of Information Science&Engineering, Lanzhou University, Tianshui Southern Road 222#， Gansu Province，P.R.ChinaPrinciples of Communications*.2 第十三章 差錯(cuò)控制和信道編碼主要內(nèi)容

2、提要： 差錯(cuò)控制方式及信道編碼的基本概念 線性分組碼 循環(huán)碼 卷積碼 其它信道編碼簡(jiǎn)介*.3 本章的教學(xué)基本要求 本章要求掌握差錯(cuò)控制的基本方式、信道編碼的一些基本概念、線性分組碼特性及其設(shè)計(jì)、循環(huán)碼特性及其設(shè)計(jì)、卷積碼特性及其設(shè)計(jì)；其余的內(nèi)容可根據(jù)學(xué)時(shí)情況酌情加以了解即可。*.4 在實(shí)際信道上傳輸數(shù)字信號(hào)時(shí)，由于信道傳輸特性不理想以及加性噪聲的影響，接收端所收到的數(shù)字信號(hào)不可避免地會(huì)發(fā)生錯(cuò)誤。產(chǎn)生差錯(cuò)的原因信道的電氣特性引起信號(hào)幅度、頻率、相位的畸變；信號(hào)反射；串?dāng)_；閃電、大功率電機(jī)的啟停產(chǎn)生脈沖干擾等。 一般說來，線路傳輸差錯(cuò)是不可避免的，但要盡量減小其影響。1. 引言*.5 1. 引 言

3、信道差錯(cuò)的幾種模式隨機(jī)差錯(cuò)：差錯(cuò)的出現(xiàn)是隨機(jī)的，一般而言差錯(cuò)出現(xiàn)的位置是隨機(jī)分布的。這種情況一般是由信道的加性隨機(jī)噪聲引起的。一般將這種信道稱為隨機(jī)信道。突發(fā)差錯(cuò)：差錯(cuò)的出現(xiàn)是一連串出現(xiàn)的。這種情況如移動(dòng)通信中信號(hào)在某一段時(shí)間內(nèi)發(fā)生衰落，造成一串差錯(cuò)；光盤上的一條劃痕等等。這樣的信道我們稱之為突發(fā)信道?；旌喜铄e(cuò)：既有突發(fā)錯(cuò)誤又有隨機(jī)差錯(cuò)的情況。這種信道稱之為混合信道。*.6 1.引 言降低誤碼的技術(shù)措施：為了在已知信噪比情況下達(dá)到一定的誤比特率指標(biāo)，首先應(yīng)該合理設(shè)計(jì)基帶信號(hào)，選擇調(diào)制解調(diào)方式，采用時(shí)域/頻域均衡，使誤比特率盡可能降低。但若誤比特率仍不能滿足要求，則必須采用信道編碼（即差錯(cuò)控制編

4、碼），將誤比特率進(jìn)一步降低，以滿足系統(tǒng)指標(biāo)要求。隨著差錯(cuò)控制編碼理論的完善和數(shù)字電路技術(shù)的發(fā)展，信道編碼已經(jīng)成功地應(yīng)用于各種通信系統(tǒng)中，并且在計(jì)算機(jī)、磁記錄與存儲(chǔ)中也得到日益廣泛的應(yīng)用。*.7 1. 引 言我們研究的是編碼和譯碼，所以完全可以將調(diào)制、解調(diào)與信道合起來等效成一個(gè)等效信道編碼信道。 編碼信道根據(jù)調(diào)制解調(diào)的不同輸入和輸出具有不同的類型離散無記憶對(duì)稱二進(jìn)制輸入二進(jìn)制輸出信道（BSC）離散無記憶二進(jìn)制輸入多進(jìn)制輸出信道離散無記憶多進(jìn)制輸入多進(jìn)制輸出離散無記憶二進(jìn)制輸入連續(xù)輸出離散有記憶信道編碼信道信源編碼調(diào)制信道解調(diào)譯碼信宿*.8 1.引 言信道編碼的目的：改善數(shù)字通信系統(tǒng)的傳輸質(zhì)量信道

5、編碼(差錯(cuò)控制編碼)的基本思路：在發(fā)送端將被傳輸?shù)男畔⒏缴弦恍┍O(jiān)督碼元，這些冗余的碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)（約束）。接收端按照既定的規(guī)則校驗(yàn)信息碼元與監(jiān)督碼元之間的關(guān)系，一旦傳輸發(fā)生差錯(cuò)，則信息碼元與監(jiān)督碼元的關(guān)系就受到破壞，從而接收端可以發(fā)現(xiàn)錯(cuò)誤乃至糾正錯(cuò)誤。信道編碼的任務(wù)：構(gòu)造出以最小多余度（冗余度）代價(jià)換取最大抗干擾性能的“好碼”。研究各種編碼和譯碼方法是信道編碼所要解決的主要問題。 *.9 信道編碼與信源編碼的區(qū)別信源編碼盡量減少信源的冗余度。即盡可能用最少的信息比特來表示信源。如話音壓縮編碼、圖象壓縮編碼。信道編碼在待傳輸信息中加入冗余信息，以此達(dá)到差錯(cuò)控制的目的，

6、從而提高通信系統(tǒng)的可靠性。如糾錯(cuò)編碼、檢錯(cuò)重發(fā)編碼等*.10 2. 差錯(cuò)控制方式及信道編碼的基本概念一、差錯(cuò)控制的三種方式：檢錯(cuò)重發(fā)（ARQ： Automatic Repeat Request ）在接收端根據(jù)編碼規(guī)則進(jìn)行檢查，如果發(fā)現(xiàn)規(guī)則被破壞，則通過反向信道要求發(fā)送端重新發(fā)送，直到接收端檢查無誤為止。ARQ系統(tǒng)需要反饋信道，效率較低，但是能達(dá)到很好的性能。 前向糾錯(cuò)（FEC： Forward Error Correction ） 發(fā)送端發(fā)送能糾正錯(cuò)誤的編碼，在接收端根據(jù)接收到的碼和編碼規(guī)則，能自動(dòng)糾正傳輸中的錯(cuò)誤。不需要反饋信道，實(shí)時(shí)性好，但是隨著糾錯(cuò)能力的提高，編譯碼設(shè)備復(fù)雜。 混合方式（

7、HEC：Hybrid Error Correction ）結(jié)合前向糾錯(cuò)FEC和ARQ的系統(tǒng)，在糾錯(cuò)能力范圍內(nèi)，自動(dòng)糾正錯(cuò)誤，超出糾錯(cuò)范圍則要求發(fā)送端重新發(fā)送。它是一種折中的方案。*.11 差錯(cuò)控制的三種方式檢錯(cuò)重發(fā)（ARQ： Automatic Repeat Request ）前向糾錯(cuò)（FEC： Forward Error Correction ） 混合方式（HEC：Hybrid Error Correction ）發(fā)送接收可檢錯(cuò)的碼序列應(yīng)答信號(hào)發(fā)送接收可檢錯(cuò)和糾錯(cuò)的碼序列發(fā)送接收可檢錯(cuò)和糾錯(cuò)的碼序列應(yīng)答信號(hào)*.12 差錯(cuò)控制的三種方式 之 ARQ檢錯(cuò)重發(fā) ARQ系統(tǒng)具有各種不同的重發(fā)機(jī)制停等

8、 ARQ發(fā)送方每發(fā)完一幀必須等接收方確認(rèn)后才能發(fā)下一幀。Go-back-N ARQ(回退N)發(fā)送方可連續(xù)發(fā)送多幀。若前面某幀出錯(cuò)，從該幀以后的各幀都需重發(fā)。（一般與流控結(jié)合使用）選擇性重傳 SARQ發(fā)送方可連續(xù)發(fā)送多幀。若前面某幀出錯(cuò)，只需重發(fā)該出錯(cuò)的幀。發(fā)送方需要緩存前面所有未被確認(rèn)的幀。其它不常用的差錯(cuò)控制方式： 信息反饋方式（IRQ）*.13 差錯(cuò)控制的三種方式 之 ARQ停等ARQ回退N選擇性重傳碼組1ACKNAK碼組2ACK重發(fā)碼組2碼組3無錯(cuò)無錯(cuò)有錯(cuò)發(fā)送接收1234563456712345634567發(fā)現(xiàn)錯(cuò)誤NAK重發(fā)12345637891234563789發(fā)現(xiàn)錯(cuò)誤NAK重發(fā)*.1

9、4 二、 信道編碼的分類 1、按功能劃分為：檢錯(cuò)碼、糾錯(cuò)碼、糾刪碼（兼檢錯(cuò)、糾錯(cuò)）2、按信息位和校驗(yàn)位的約束關(guān)系分為：線性碼、非線性碼3、按信息碼元和監(jiān)督碼元的約束關(guān)系分為：分組碼：監(jiān)督碼僅與本碼組信息碼有關(guān)卷積碼：監(jiān)督碼不僅與本碼組信息碼有關(guān)，而且與前面碼組的信息碼有關(guān)。4、按編碼后信息碼結(jié)構(gòu)是否發(fā)生變化分為：系統(tǒng)碼：編碼前后信息碼結(jié)構(gòu)不變非系統(tǒng)碼：編碼前后信息碼結(jié)構(gòu)發(fā)生改變5、按碼元的進(jìn)制進(jìn)行劃分：二進(jìn)制碼、多進(jìn)制碼：*.15 三、信道編碼的基本概念分組碼：將k比特信息編成n比特一組的碼字（碼組），記為（n，k）分組碼。K位碼元，作為信息碼元r=n-k位碼元，稱作冗余碼、監(jiān)督碼許用碼組：禁

10、用碼組：碼重W：碼字中1的個(gè)數(shù)。如W(11000)=2; W(010)=1 碼距d （漢明距離Hamming） ：兩碼組中對(duì)應(yīng)位不同的比特（bit）數(shù)。如C1:11000，C2:11101,則d(C1，C2)=2*.16 信道編碼的基本概念最小碼距：分組碼(n,k)中任何兩個(gè)碼字Ci、Cj之間的碼距的最小值，用dmin表示。最小碼距是衡量碼的一種內(nèi)在屬性 最小碼距決定了碼的糾錯(cuò)、檢錯(cuò)性能若要發(fā)現(xiàn)e個(gè)獨(dú)立隨機(jī)錯(cuò)誤，要求dmine+1若要糾正t個(gè)獨(dú)立隨機(jī)錯(cuò)誤，要求dmin2t+1若要發(fā)現(xiàn)e個(gè)同時(shí)又糾正t(et)個(gè)獨(dú)立隨機(jī)錯(cuò)誤，要求dmine+t+1e+1ee2t+1tte+t+1et*.17 四、

11、常用簡(jiǎn)單檢錯(cuò)碼1.奇偶監(jiān)督碼（奇偶校驗(yàn)碼）最簡(jiǎn)單的檢錯(cuò)碼(1bit校驗(yàn))，在計(jì)算機(jī)數(shù)據(jù)傳輸中得到廣泛應(yīng)用 傳送信息分組(an-1,a1,)+監(jiān)督位(a0) = 一個(gè)傳輸碼組(an-1,a1, a0)偶校驗(yàn)：an-1+an-2 + +a1+a0=0 (mod 2) （即偶數(shù)個(gè)1）奇校驗(yàn)：an-1+an-2 + +a1+a0=1 (mod 2) （即奇數(shù)個(gè)1） 可見這種碼的最小碼距為2，只能檢出1個(gè)獨(dú)立隨機(jī)差錯(cuò)。*.18 簡(jiǎn)單的檢錯(cuò)碼2.二維奇偶監(jiān)督碼（行列監(jiān)督碼）可檢測(cè)出任一行或任一列上所有奇數(shù)個(gè)錯(cuò)碼信息碼元水平監(jiān)督碼010110110010101010010000110000110垂直監(jiān)督碼0

12、0111111011*.19 簡(jiǎn)單的檢錯(cuò)碼3.恒比碼 每個(gè)碼組中的1的個(gè)數(shù)都是一樣的。典型應(yīng)用：一般用在電傳、電報(bào)。例如，我國(guó)電傳機(jī)傳輸漢字時(shí)每個(gè)漢字用4位阿拉伯?dāng)?shù)字表示，每個(gè)阿拉伯?dāng)?shù)字用5個(gè)比特的碼字表示 ，即從32種組合選取10個(gè)為阿拉伯?dāng)?shù)字編碼阿拉伯?dāng)?shù)字編碼阿拉伯?dāng)?shù)字編碼101011610101211001711100310110801110411010910011500111001101恒比碼的編譯碼可以采用查表的方法，檢錯(cuò)時(shí)檢查1的個(gè)數(shù)是否為3*.20 簡(jiǎn)單的檢錯(cuò)碼4.ISBN國(guó)際統(tǒng)一圖書編號(hào)（例一）在國(guó)際圖書的發(fā)行中，經(jīng)常用編碼的方式來防止書號(hào)在通信過程中發(fā)生錯(cuò)誤，舉例如下所述。如

13、通信原理的書號(hào)是ISBN 7-5635-0525-3其中第一位數(shù)字“7”表示“中國(guó)”，“5635”表示出版社，“0525”表示書名編號(hào)，最后一位“3”表示校驗(yàn)位。這里所采用的校驗(yàn)方式如下所示：7 5 6 3 5 0 5 2 5 37 12 18 21 26 26 31 33 38 417 19 37 58 84 110 141 174 212 253(模11) 0若通信過程中統(tǒng)一書號(hào)發(fā)生了錯(cuò)誤，則上述累計(jì)和就不能被11整除，從而可以校驗(yàn)出來。*.21 簡(jiǎn)單的檢錯(cuò)碼4.ISBN國(guó)際統(tǒng)一圖書編號(hào)（例二）如通信原理的書號(hào)是ISBN 7-118-0429-X其中第一位數(shù)字“7”表示“中國(guó)”，“118”

14、表示出版社，“01429”表示書名編號(hào)，最后一位“X”表示校驗(yàn)位（它是羅馬數(shù)字10的表示）。這里所采用的校驗(yàn)方式如下所示：7 1 1 8 0 4 2 9 X=107 8 9 17 17 21 23 32 427 15 24 41 58 79 102 134 176 176(模11)=0。 又譬如：ISBN 7030144562，大家可自行分析。*.22 3. 線性分組碼 近世代數(shù)學(xué)有限域的概念：有限個(gè)元素的集合，按規(guī)定可以進(jìn)行的代數(shù)四則運(yùn)算，其運(yùn)算結(jié)果仍屬于該集合中有限的元素。最簡(jiǎn)單的有限域 0，1Galois域1+1=0、 1+0=1、 0+1=1、 0+0=0 1x1=1、 1x 0=0、

15、 0 x0 =0、 0 x1 =0定義線性分組碼的加法為模2加，乘法為二進(jìn)制乘法。且碼字與碼字的運(yùn)算是各個(gè)相應(yīng)比特位上的上述二進(jìn)制運(yùn)算規(guī)則。*.23 3. 線性分組碼基本概念碼組中監(jiān)督碼與信息碼之間滿足線性方程；任意兩個(gè)可用碼組之和(逐位模2加)仍為一個(gè)可用碼組奇偶監(jiān)督碼最簡(jiǎn)單的線性分組碼偶校驗(yàn)時(shí) 奇校驗(yàn)時(shí)不滿足線性分組碼的第二個(gè)性質(zhì)。定義校正子（校驗(yàn)子伴隨式）接收時(shí)進(jìn)行校驗(yàn)計(jì)算： S=0無錯(cuò)； S=1有錯(cuò)（奇數(shù)個(gè)） *.24 3. 線性分組碼一般情況下：如果碼組中有2個(gè)監(jiān)督碼，校正子為S=s1,s2可以檢測(cè)到三種誤碼狀態(tài)*.25 3. 線性分組碼如果碼組中有r個(gè)監(jiān)督碼，假設(shè)碼組中有K個(gè)信息碼

16、，則線性分組碼的長(zhǎng)度應(yīng)該為n=K+r。碼的結(jié)構(gòu)線性分組碼（n，k）的性質(zhì)封閉性：任意兩個(gè)碼組的和還是許用的碼組碼的最小距離等于非零碼的最小碼重K位信息位r位監(jiān)督位n位碼組*.26 3. 線性分組碼檢錯(cuò)能力：有r個(gè)校正子方程可以指示（2r-1）個(gè)錯(cuò)誤糾錯(cuò)能力：對(duì)1位錯(cuò)碼，可以指示（2r-1）個(gè)錯(cuò)誤位置若2r-1n，可以糾正1bit或以上的錯(cuò)碼， 即2r-1r+k， 2r-1- rk設(shè)k=4，能糾正1位誤碼的最小r=3，則n=7 （7，4）線性分組碼，碼組C=c6c5c4c3c2c1c0， 其中c6c5c4c3為信息碼，c2c1c0為監(jiān)督碼*.27 3. 線性分組碼一般分析，對(duì)于線性分組碼（n,k

17、）,若可記為：（Cn-1 Cn-2 Cn-3 Cn-K Cr-1 Cr-2 Cr-3C1 C0） 現(xiàn)令信息碼元與監(jiān)督碼元的約束關(guān)系為：*.28 3. 線性分組碼據(jù)此可得如下結(jié)果：由上式可得一致監(jiān)督關(guān)系為：*.29 3. 線性分組碼其中的H為：*.30 3. 線性分組碼同樣可知：*.31 3. 線性分組碼若令下述關(guān)系成立：對(duì)比H和G，可見：*.32 3. 線性分組碼所以可得如下結(jié)果： 這里稱H為一致監(jiān)督矩陣；G則是生成矩陣。下面研究一個(gè)實(shí)際例子。*.33 3. 線性分組碼現(xiàn)以一個(gè)(7,3)線性分組碼為例n=7,k=3,r=n-k=4編碼效率為：R=k/n=3/7 c0=u0 c3=u0 + u2

18、 信息位 c1=u1 監(jiān)督位 c4=u0 + u1 + u2 c2=u2 c5=u0 + u1 c6=u1 + u2 則C=（c0c1c2c3c4c5c6）=（u0,u1,u2,u0 + u2,u0 + u1 + u2, u0 + u1, u1 + u2 ）*.34 3. 線性分組碼n位的碼組，由k個(gè)信息位的輸入消息u通過一個(gè)線性變換矩陣kn階G來產(chǎn)生，稱G生成矩陣G= ，I為k階單位方陣典型生成矩陣生成矩陣G*.35 3. 線性分組碼將監(jiān)督位線性方程組寫為即 可見上述監(jiān)督關(guān)系的線性方程組完全由矩陣H所決定。故將此r n的H矩陣稱為監(jiān)督矩陣H= , I為(n-kr)維（階）單位方陣 典型監(jiān)督矩

19、陣*.36 3. 線性分組碼根據(jù)前面所得可推導(dǎo)： G與H生成的空間互為零空間，且G與H可以互相轉(zhuǎn)換。 （即P、Q互為轉(zhuǎn)置矩陣）*.37 3. 線性分組碼校正子（碼組伴隨式）發(fā)送碼組C經(jīng)過傳輸系統(tǒng)到達(dá)接收端時(shí)，假設(shè)收到的碼組為B，B=bn-1bn-2b0差錯(cuò)關(guān)系為 B-C=E ， BE=CE =en-1en-2e0，E又稱為錯(cuò)誤圖樣。 其中接收時(shí)計(jì)算校正子為 *.38 3. 線性分組碼編碼器若以c0c1c2為信息碼,由監(jiān)督碼的生成關(guān)系可得c3=1c0 + 0c1 + 1c2 c4=1c0 + 1c1 +1 c2 c5=1c0 + 1c1 +0c2 c6= 0c0 + 1c1 + 1c2 C0C1

20、C2+u0u1u2C4C5C6C3*.39 3. 線性分組碼譯碼器由校正子關(guān)系可得*.40 3. 線性分組碼譯碼器b0b1b2b3b4b5b6+b0s1s2s3s4s1s2s3s4與+r0c0b1與+r1c1b2與+r2c2b3與+r3c3b4與+r4c4b5與+r5c5b6與+r6c6伴隨式計(jì)算電路錯(cuò)誤圖樣檢測(cè)電路*.41 3. 線性分組碼漢明（海明）碼（Hamming）能糾正單個(gè)隨機(jī)錯(cuò)誤的線性分組碼碼長(zhǎng) n=2m-1信息位 k=2m-1-m監(jiān)督位 n-k=m，且 m3最小距離 dmin=d0=3漢明碼是一類高效率的糾錯(cuò)碼編碼效率 R=k/n=(n-m)/n=1-m/nn很大時(shí)，R1*.42

21、 4. 循環(huán)碼基本概念線性分組碼的一個(gè)子類，比較成熟任何一個(gè)可用碼組經(jīng)過循環(huán)移位后所得到的碼組仍為一個(gè)可用碼組原碼組 C=cn-1 cn-2 c1 c0左移一位 C1=cn-2 cn-3 c0 cn-1右移一位 C2=c1 cn-1 c3 c2移i位 Ci=cn-i-1 cn-i-2 cn-i循環(huán)碼組 C=cn-1 cn-2 c1 c0 可表示為多項(xiàng)式 C(x)= cn-1 xn-1 + cn-2 xn-2 + c1 x+ c0式中x的冪次表示：碼元的位置；碼的移位次數(shù)*.43 4. 循環(huán)碼基本概念如多項(xiàng)式C(x)= x6 + x4 +x+1C=1010011c6x6可以看作c6從最低位c0左

22、移6次的結(jié)果C(x)左移一位記作 C(1)(x)C(1)(x)=cn-2 xn-1 + cn-3 xn-2 + c0 x+ cn-1C(x)左移i位后為C(i)(x)=cn-i-1 xn-1 + cn-i-2 xn-2 + cn-i+1 x+ cn-i*.44 4. 循環(huán)碼循環(huán)碼多項(xiàng)式的運(yùn)算特性碼長(zhǎng)為n的循環(huán)碼，其碼多項(xiàng)式C(x)，則xiC(x)=Q(x) (xn+1)+C(i)(x) 即例如：某循環(huán)碼組為C=(1100101)，碼長(zhǎng)n=7，對(duì)應(yīng)的碼多項(xiàng)式為C(x)=x6 +x5 + x2 + 1左移一位后xC(x)=x7 +x6 + x3 + x因?yàn)镃(1)(x) xC(x) (mod（x7

23、+1）)=x6 +x3 + x + 1 （1001011）*.45 4. 循環(huán)碼左移2位時(shí)x2C(x)=x8 +x7 + x4 + x2 x+1 x7 +1 ) x8 +x7 + x4 + x2 x8 +x x7 + x4 + x2 +x x7 +1 x4 + x2 +x +1C(2)(x)=x4 + x2 +x +1(0010111)*.46 4. 循環(huán)碼生成多項(xiàng)式g(x)對(duì)于(n,k)循環(huán)碼來說，生成多項(xiàng)式g(x)是一個(gè)能除盡xn+1的（n-k）階多項(xiàng)式。階數(shù)低于n并能被g(x)除盡的一組多項(xiàng)式就構(gòu)成一個(gè)(n,k)循環(huán)碼階數(shù)小于等于(n-1)并能被g(x)除盡的每個(gè)多項(xiàng)式都是循環(huán)碼的可用碼

24、組多項(xiàng)式。 所以，循環(huán)碼完全由其碼組長(zhǎng)度n和生成多項(xiàng)式g(x)所決定。*.47 4. 循環(huán)碼生成多項(xiàng)式g(x)設(shè)構(gòu)成循環(huán)碼的信息碼多項(xiàng)式為u(x)，其階數(shù)不大于(k-1)，則有循環(huán)碼組為C(x)=u(x) g(x)例如，n=7，g(x)=x4+x3+x2+1是x7+1的一個(gè)因式；g(x)最高冪次為4=n-k；則k=3，r=4（即信息碼3bit，監(jiān)督碼4bit）?？捎么a組如下：*.48 4. 循環(huán)碼生成多項(xiàng)式g(x)以上是一個(gè)（7，3）循環(huán)碼，最小碼距dmin=4，其信息碼多項(xiàng)式如下：*.49 4. 循環(huán)碼生成多項(xiàng)式g(x)為了得到g(x)，需對(duì)xn+1進(jìn)行因式分解對(duì)于大部分n值， xn+1僅有

25、很少的幾個(gè)因式；只有很少的幾個(gè)n值， xn+1才有較多因式設(shè)g(x) h(x)= xn+1 或g(x) h(x) 0 mod(xn+1) 以（7，3）循環(huán)碼為例，n=7 x7+1=(x+1)(x3+x2+1)(x3+x+1)*.50 4. 循環(huán)碼生成多項(xiàng)式g(x)n=7， x7+1=(x+1)(x3+x2+1)(x3+x+1)循環(huán)碼dming(x)h(x)(7,6)2x+1(x3+x2+1)(x3+x+1)(7,4)3x3+x2+1(x+1)(x3+x+1)x3+x+1(x+1)(x3+x2+1)(7,3)4(x+1)(x3+x+1)x3+x2+1(x+1)(x3+x2+1)x3+x+1(7,

26、1)7(x3+x2+1)(x3+x+1)x+1顯然，(7，3)、(7，4)循環(huán)碼互為對(duì)偶碼.*.51 4. 循環(huán)碼生成矩陣GC(x)=u(x) g(x) =(uk-1xk-1+uk-2xk-1+u1x+u0) g(x) = uk-1xk-1 g(x) +uk-2xk-2 g(x) +u0 g(x) =uG根據(jù)u的不同取值可求得(n,k)循環(huán)碼的所有2k個(gè)碼字，但這樣所得到的碼并非系統(tǒng)碼。*.52 4. 循環(huán)碼生成矩陣G為了進(jìn)一步得到系統(tǒng)碼，可作如下運(yùn)算：xn-ku(x)=Q(x)g(x)+r(x)C(x)= xn-ku(x)+r(x)= Q(x)g(x)+r(x)+r(x) = Q(x)g(x

27、)構(gòu)造系統(tǒng)循環(huán)碼：只需將信息碼多項(xiàng)式升(n-k)階，然后以g(x)為模求余，所得余式即為監(jiān)督碼多項(xiàng)式“除法求余”過程*.53 4. 循環(huán)碼例如：已知(7,4)系統(tǒng)碼的生成多項(xiàng)式為g(x)=x3+x2+1，求其生成矩陣。 解：由 先求出*.54 4. 循環(huán)碼監(jiān)督矩陣H由于 xn+1=g(x) h(x)生成多項(xiàng)式g(x)=gn-kxn-k+g1x+g0監(jiān)督多項(xiàng)式h(x)=hkxk+h1x+h0*.55 4. 循環(huán)碼例如，已知(7,3)系統(tǒng)循環(huán)碼的生成多項(xiàng)式g(x)=x4+x3+x2+1，求生成矩陣G及監(jiān)督矩陣H。解：由g(x) h(x)=x7+1的關(guān)系可得： h(x)=x3+x2+1=h3x3+h

28、2x2+h1x+h0根據(jù)前例方法先計(jì)算 rn-i (x)xn-imod g(x)可得*.56 4. 循環(huán)碼編碼器循環(huán)碼的特點(diǎn)一：可以采用反饋線性移位寄存器實(shí)現(xiàn)編碼和伴隨式計(jì)算以g(x)=x3+x+1的（7，4）循環(huán)編碼器為例D0D1D2+門輸入u(x) xn-k12碼字輸出*.57 4. 循環(huán)碼編碼器以g(x)=x3+x+1的（7，4）循環(huán)編碼器為例節(jié)拍信息組輸入依存狀態(tài)輸出碼字D0(x0)D1(x1)D2(x2)0000111101200110301110410111500116000170000初態(tài)為000門開四次移位后信息1001全部輸出，關(guān)門，輸出開關(guān)倒向2又循環(huán)回到初始狀態(tài)信息位監(jiān)督

29、位*.58 4. 循環(huán)碼譯碼器仍以g(x)=x3+x+1生成的（7，4）循環(huán)碼譯碼為例復(fù)用器+門1門2+門2Y(x)s0s1s2錯(cuò)誤圖樣檢測(cè)電路只有1套，其譯碼電路比一般的(7,4)線性分組碼大大簡(jiǎn)化*.59 4. 循環(huán)碼(7，4)循環(huán)碼d=3g(x)=(x3+x+1)(8,4)非循環(huán)碼d=4(7，3)循環(huán)碼d=4g(x)=(x3+x+1)(x+1)刪減增擴(kuò)收縮加長(zhǎng)縮短擴(kuò)展*.60 4. 循環(huán)碼循環(huán)碼檢錯(cuò)CRC (Cyclic Redundancy Check, 循環(huán)冗余校驗(yàn))一般能檢測(cè)的錯(cuò)誤：突發(fā)長(zhǎng)度n-k+1的錯(cuò)誤，其中不可檢出錯(cuò)誤僅占2-(n-k)所有與許用碼組碼距dmin-1的錯(cuò)誤所有

30、奇數(shù)個(gè)錯(cuò)誤CRC碼在數(shù)據(jù)通信及移動(dòng)通信中得到廣泛應(yīng)用*.61 4. 循環(huán)碼循環(huán)碼檢錯(cuò)：CRC (Cyclic Redundancy Check, 循環(huán)冗余校驗(yàn))常用的CRC碼國(guó)際標(biāo)準(zhǔn)CRC-12：g(x)=x12+x11+x3+x2+x+1CRC-16: g(x)=x16+x15+x2+1CRC-CCITT: g(x)=x16+x12+x5+1CRC-32: g(x)=x32+x26+x23+x22+x16+x12+x11 +x10+x8+x7+x5+x4+x2+x+1CRC-12用于字符長(zhǎng)度為6bit情況，后三種用于8bit字符。*.62 CRC 校驗(yàn)示例待校驗(yàn)數(shù)據(jù)：1101,0110,11

31、 g(x) = x4+x+1 , 即10011 1 1 0 1 0 1 1 0 1 1 0 0 0 01 0 0 1 1 1 1 0 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 0 1 1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 1 1 1 1 1 0余數(shù)傳送序列 T(x)=1101,0110,11 11,10待發(fā)送的原數(shù)據(jù)校驗(yàn)碼*.63 CRC接收端的處理過程假設(shè)收到序列R(X)=1101,1110,1111,10T(x) (出錯(cuò)) 仍然用g(x) = x4+x+1 , 即10011 做除數(shù)1 1 0 1 1 1

32、 1 0 1 1 1 1 1 01 0 0 1 1 1 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0 1 1 1 1 0 1 11 0 0 1 11 0 0 0 1 1 0 0 1 11 0 1 0非0余數(shù)表示有錯(cuò)*.64 接收端的處理過程（續(xù)）假設(shè)收到序列無誤，則有 R(X)=T(X)=1101,0110,1111,10 仍然用 g(x) = x4+x+1 , 即10011 做除數(shù)1 1 0 1 0 1 1 0 1 1 1 1 1 01 0 0 1 1 1 1 0 0 0 0 1 0 1 0 1 0 0 1 1

33、 1 0 0 1 1 1 0 0 1 1 0 0 1 0 1 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0余數(shù)為0表示正確接收*.65 5. 卷積碼卷積碼是非分組碼的典型代表，亦稱連環(huán)碼。 它是1955年由埃里亞斯（Elias ）最早提出。與分組碼的主要差異：卷積碼編碼器有記憶，在任意給定的時(shí)段，編碼器的n個(gè)輸出不僅與此時(shí)段的k個(gè)輸入有關(guān)，而且與前m個(gè)輸入有關(guān)卷積碼記為（n，k，m）n為輸出碼元數(shù)k為輸入碼元數(shù)m為編碼器的存儲(chǔ)器數(shù)*.66 5. 卷積碼卷積碼編碼串并轉(zhuǎn)換.有限狀態(tài)的有記憶系統(tǒng)（最大延遲為m）.并串轉(zhuǎn)換輸出碼字序列C輸入信息序列uuc

34、uc描述時(shí)序網(wǎng)絡(luò)的方法解析表示法離散卷積法、生成矩陣法、碼多項(xiàng)式法圖形表示法狀態(tài)圖法、樹圖法、格圖法*.67 5. 卷積碼卷積碼編碼現(xiàn)以一個(gè)二元（2，1，3）卷積碼為例輸入信息序列u=(u0u1u2)+輸出碼字序列c= (c0 c0 c1 c1 c2 c2 ) g有限狀態(tài)的有記憶系統(tǒng)k=1，即一個(gè)輸入位n=2，即兩個(gè)輸出位m=3，即三級(jí)移位寄存器輸出c = u*g = (c0c1c2)輸出c = u*g = (c0 c1 c2 )g *.68 5. 卷積碼卷積碼編碼離散卷積法以一個(gè)二元（2，1，3）卷積碼為例由圖可知 g1(x)=1+x2+x3 g=(1011) g2(x)=1+x+x2+x3

35、 g=(1111)設(shè)u=(10111)，則有 c=(10111) *(1011)=(10000001) c=(10111) *(1111)=(11011101)最后輸出的碼字為 c=(1101000101010011)生成序列*.69 5. 卷積碼生成矩陣G生成矩陣法理論分析 g0g0 g1g1 g2g2 g3g3 0 0 0 g0g0 g1g1 g2g2 g3g3 0G = 0 0 g0g0 g1g1 g2g2 g3g3 生成矩陣G是一個(gè)半無限的矩陣編碼方程的矩陣形式：c=uG*.70 5. 卷積碼生成矩陣G已知 u=(10111),求得 g=(1011),g=(1111) 代入公式，可求得

36、 11 01 11 11 0 0 0 0 0 11 01 11 11 0 0 0 0 0 11 01 11 11 0 0 0 0 0 11 01 11 11 0 0 0 0 0 11 01 11 11 C = uG= (10111)= (11 01 00 01 01 01 00 11)*.71 5. 卷積碼碼多項(xiàng)式表達(dá)式 工程應(yīng)用u=(10111)=1+x2+x3+x4g=(1011)=1+x2+x3g=(1111)=1+x+x2+x3 則卷積碼輸出為：c= (1+x2+x3+x4)(1+x2+x3) =1+x7=(10000001)c= (1+x2+x3+x4)(1+x+x2+x3) =1+

37、x+x3+x4+x5+x7=(11011101)輸出序列為 C=(1101000101010011)*.72 5. 卷積碼狀態(tài)圖法描述現(xiàn)以（2，1，2）卷積碼為例： k=1，n=2，m=2總的可能狀態(tài)數(shù)為 2km=22=4種，即 00, 10, 01, 11每次可能的輸入有兩個(gè)即 2k=2每次可能的輸出狀態(tài)也只有兩個(gè)狀態(tài)圖的畫法圓圈中的數(shù)字狀態(tài)狀態(tài)之間的連線和箭頭轉(zhuǎn)移方向（分支）分支上的數(shù)字轉(zhuǎn)移時(shí)輸出的碼字括號(hào)中的數(shù)字轉(zhuǎn)移時(shí)輸入的信息數(shù)字*.73 5. 卷積碼狀態(tài)圖法（2，1，2）卷積碼為例：（2，1，2）卷積碼狀態(tài)轉(zhuǎn)移圖0011100111(1)01(1)01(0)11(0)10(0)00(

38、1)00(0)10(1)*.74 5. 卷積碼樹圖法按時(shí)間展開l=0l=1l=2l=3l=4l=5l=6l=7l節(jié)點(diǎn)級(jí)數(shù)樹根0分支1分支a00110000001111100111100110010011011011000110001110010011011000110011優(yōu)點(diǎn)：時(shí)序關(guān)系清晰對(duì)每一個(gè)信息輸入序列有且僅有一個(gè)不重復(fù)的樹枝結(jié)構(gòu)相對(duì)應(yīng)缺點(diǎn)：進(jìn)行到一定時(shí)序后，狀態(tài)重復(fù)且樹圖越來越復(fù)雜*.75 5. 卷積碼樹圖法l=0l=1l=2l=3l=4l=5l=6l=7l節(jié)點(diǎn)級(jí)數(shù)樹根0分支1分支a001100000011111001111001100100110110110001100011100

39、10011011010011100C=(11 10 00 01 10 01 11 00)輸入序列為 u=(10111000)*.76 5. 卷積碼格圖法（籬笆圖）二維狀態(tài)l=0l=1l=2l=3l=4l=5l=6l=7l節(jié)點(diǎn)級(jí)數(shù)a=00b=10c=01d=110000000000000011111111111110011001011010100111000110011011110110010000111100在l=3時(shí)狀態(tài)abcd呈現(xiàn)重復(fù)圖示說明：輸入為0所走的分支輸入為1所走的分支C=(11 10 00 01 10 01 11)所對(duì)應(yīng)的路徑*.77 5. 卷積碼卷積碼的譯碼代數(shù)譯碼（略）概率譯碼最大似然譯碼算法即維特比（Vit