通信原理沈越泓、高媛媛、魏以民等編著機(jī)械工業(yè)出版社1第9章差錯(cuò)控制編碼9.1概述9.2信道編碼的基本概念9.3常用的簡(jiǎn)單編碼9.4線性分組碼9.5循環(huán)碼9.6卷積碼9.7m序列2§9-1信道編碼概述兩種編碼:信源編碼:提高有效性信道編碼:提高可靠性信源信源編碼信道編碼調(diào)制信道信宿信源譯碼信道譯碼解調(diào)典型的數(shù)字通信系統(tǒng)3編碼的原理：使不帶規(guī)律性或規(guī)律性不強(qiáng)的原始數(shù)字信 號(hào)變?yōu)閹弦?guī)律性或加強(qiáng)了規(guī)律性的數(shù)字信號(hào)， 利用這些規(guī)律性可以發(fā)現(xiàn)或糾正錯(cuò)誤。信道編碼原理編碼的本質(zhì)：增加冗余度，犧牲有效性以提高可靠性。編碼的方法：對(duì)原信息進(jìn)行變換，加入附加信息(即監(jiān)督碼)。例:(4,1)重復(fù)碼

0:0000 1:11114差錯(cuò)及信道分類(lèi)隨機(jī)錯(cuò)誤：零星分布的錯(cuò)誤突發(fā)錯(cuò)誤：集中出現(xiàn)的錯(cuò)誤突發(fā)信道：以突發(fā)錯(cuò)誤為主隨機(jī)信道：以隨機(jī)錯(cuò)誤為主混合信道：兩種錯(cuò)誤均較明顯對(duì)錯(cuò)誤的處理方式：檢錯(cuò)，糾錯(cuò)5差錯(cuò)控制的工作方式發(fā)端收端前向糾錯(cuò)FEC糾錯(cuò)碼發(fā)端收端重發(fā)檢錯(cuò)ARQ檢錯(cuò)碼判決信號(hào)發(fā)端收端信息反饋IF信息信號(hào)信息信號(hào)發(fā)端收端混合糾錯(cuò)HEC檢錯(cuò)和糾錯(cuò)碼判決信號(hào)6ARQ系統(tǒng)組成方框圖7分組碼舉例設(shè)：有一種由3個(gè)二進(jìn)制碼元構(gòu)成的編碼，它共有23=8種不同的可能碼組：

000–晴001–云010–陰011–雨

100–雪101–霜110–霧111–雹這時(shí)，若一個(gè)碼組中發(fā)生錯(cuò)碼，則將收到錯(cuò)誤信息。一、分組碼的概念§9-2信道編碼的基本概念8若在此8種碼組中僅允許使用4種來(lái)傳送天氣，例如：令

000–晴011–云101–陰110–雨 為許用碼組，其他4種不允許使用，稱(chēng)為禁用碼組。 這時(shí)，接收端有可能發(fā)現(xiàn)（檢測(cè)到）碼組中的一個(gè)錯(cuò)碼。

這種編碼只能檢測(cè)錯(cuò)碼，不能糾正錯(cuò)碼。若規(guī)定只許用兩個(gè)碼組：例如

000–晴111–雨就能檢測(cè)兩個(gè)以下錯(cuò)碼，或糾正一個(gè)錯(cuò)碼。9分組碼＝信息位＋監(jiān)督位分組碼符號(hào)：(n,k)

其中，n：碼組總長(zhǎng)度，

k：

信息碼元數(shù)目。

r=n–k

監(jiān)督碼元數(shù)目。

右表中的碼組為(3,2)碼。信息位監(jiān)督位晴000云011陰101雨11010分組碼的一般結(jié)構(gòu)11分組碼的參數(shù)

——碼長(zhǎng)、碼重、碼距、最小碼距、碼率

碼長(zhǎng)：碼組(碼字或碼矢)中碼元的數(shù)目稱(chēng)為碼組的長(zhǎng)度，簡(jiǎn)稱(chēng)碼長(zhǎng)。

碼重：碼組中非0位的數(shù)目稱(chēng)為碼組的重量，簡(jiǎn)稱(chēng)碼重。例如碼組11010，碼長(zhǎng)N=5，碼重w=3。12

碼距：兩個(gè)等長(zhǎng)碼組之間對(duì)應(yīng)位不同的數(shù)目稱(chēng)為這兩個(gè)碼組的的漢明距離，簡(jiǎn)稱(chēng)碼距。兩個(gè)碼組的模二相加得到的新碼組的重量就是這兩個(gè)碼組之間的距離。最小碼距：某種編碼中，各個(gè)碼組間距離的最小值稱(chēng)為最小碼距。13

碼率：通常用R=k/n來(lái)表示碼元中信息元所占的比例,稱(chēng)為編碼效率,簡(jiǎn)稱(chēng)碼率,它是衡量編碼性能的一個(gè)重要參數(shù)。14糾(檢)錯(cuò)能力與最小碼距的關(guān)系(1)檢測(cè)e個(gè)隨機(jī)錯(cuò)誤，則要求的最小距離(2)糾正t個(gè)隨機(jī)錯(cuò)誤，則要求的最小距離(3)糾正t個(gè)同時(shí)檢測(cè)e(>t)個(gè)隨機(jī)錯(cuò)誤，則要求的最小距離15一種編碼的糾檢錯(cuò)能力：決定于最小碼距d0的值。為了能檢測(cè)e個(gè)錯(cuò)碼，要求最小碼距0123BA漢明距離ed0碼距等于3的兩個(gè)碼組16為了能糾正t個(gè)錯(cuò)碼，要求最小碼距BtA漢明距離012345td0碼距等于5的兩個(gè)碼組17為了能糾正t個(gè)錯(cuò)碼，同時(shí)檢測(cè)e個(gè)錯(cuò)碼，要求最小碼距AB1tt漢明距離e碼距等于(e+t+1)的兩個(gè)碼組糾檢結(jié)合工作方式18糾錯(cuò)編碼的效果舉例例設(shè)(7,3)分組碼，d0=3，信道誤碼率pe=1*10-4。試問(wèn)：采用FEC方式，最終的輸出誤字率？采用ARQ方式，最終的輸出誤字率？19糾錯(cuò)和檢錯(cuò)能力盡量強(qiáng)；編碼效率盡量高；碼長(zhǎng)盡量短；編碼規(guī)律盡量簡(jiǎn)單。對(duì)糾錯(cuò)編碼的基本要求20常用編碼分類(lèi)信道編碼分組碼卷積碼TCM漢明碼循環(huán)碼一些簡(jiǎn)單編碼21§9.3常用的簡(jiǎn)單編碼重復(fù)碼奇偶監(jiān)督碼恒比碼22重復(fù)碼例

(6,2)重復(fù)碼

00:0000

00 01:0101

01 10:1010

10 11:1111

1123 在n－1個(gè)信息元后面附加一個(gè)監(jiān)督元，使得長(zhǎng)n的碼字中1的個(gè)數(shù)保持為奇數(shù)或偶數(shù)的碼稱(chēng)為奇偶監(jiān)督碼。奇數(shù)個(gè)1:奇監(jiān)督碼偶數(shù)個(gè)1:偶監(jiān)督碼作用：檢測(cè)錯(cuò)誤奇偶監(jiān)督碼24例：碼長(zhǎng)為5的偶監(jiān)督碼序號(hào)碼字序號(hào)碼字信息碼元監(jiān)督元信息碼元監(jiān)督元00000081000110001191001020010110101003001101110111401001121100050101013110116011001411101701111151111025

110010100001000011010111100001100111000010101010100010111000111100例：5*10的(66,50)行列監(jiān)督碼二維奇偶監(jiān)督碼26適于監(jiān)測(cè)突發(fā)錯(cuò)誤：逐行傳輸時(shí)，能檢測(cè)長(zhǎng)度b

11的突發(fā)錯(cuò)誤;逐列傳輸時(shí),能檢測(cè)長(zhǎng)度b6的突發(fā)錯(cuò)誤；還能糾正單個(gè)錯(cuò)誤。行列監(jiān)督碼糾、檢錯(cuò)能力分析27恒比碼數(shù)字碼字012345678901101010111100110110110100011110101111000111010011又稱(chēng)等重碼或定1碼，這種碼字中1和0的位數(shù)保持恒定比例。3：2數(shù)字保護(hù)碼28§9.4線性分組碼教學(xué)內(nèi)容：線性分組碼；循環(huán)碼原理。；要求：了解線性分組碼的定義；掌握漢明碼的定義及特點(diǎn)；掌握循環(huán)碼的定義。29§9.4線性分組碼的幾個(gè)概念

分組碼：將信息分組之后進(jìn)行編碼；

線性分組碼：碼的規(guī)律性可用線性方程組表述的分組碼。

系統(tǒng)碼：編碼后能將信息元和監(jiān)督元區(qū)分開(kāi)的碼編碼器信息元碼字A={an-1,an-2,…,an-k,an-k-1,…,a1,a0}信息元監(jiān)督元30本節(jié)將以漢明（Hamming）碼為例引入線性分組碼的一般原理。漢明碼的特點(diǎn)是d0＝3，碼長(zhǎng)n與監(jiān)督元個(gè)數(shù)r滿足關(guān)系式：n=2r

–

1所以漢明碼有(7,4)、(15,11)、(31,26)等。漢明碼是一種能夠糾正一位錯(cuò)碼且編碼效率較高的線性分組碼。31漢明碼的引入前面學(xué)過(guò)的偶監(jiān)督碼，在接收端是計(jì)算若S=0，就認(rèn)為無(wú)錯(cuò)；若S=1，就認(rèn)為有錯(cuò)。上式稱(chēng)為監(jiān)督關(guān)系式，S稱(chēng)為校正子。一個(gè)校正子只能指示有無(wú)錯(cuò)2個(gè)校正子可以表示四種情況，00表示無(wú)錯(cuò)，其他三種指示三個(gè)單個(gè)錯(cuò)的位置。對(duì)于碼長(zhǎng)n的分組碼，使用r個(gè)校正子，為了指示n個(gè)單個(gè)錯(cuò)，則32對(duì)于(7,4)漢明碼，校正子S1S2S3指示23–1=7個(gè)錯(cuò)碼的位置。若規(guī)定校正子和錯(cuò)碼位置的關(guān)系如下表則僅當(dāng)在a6a5a4a2位置上有錯(cuò)碼時(shí)，校正子S1的值才等于1；否則S1的值為零。這就意味著：同理，有S1S2S3錯(cuò)碼位置S1S2S3錯(cuò)碼位置001a0101a4010a1110a5100a2111a6011a3000無(wú)錯(cuò)碼（7，4）漢明碼的引入33針對(duì)無(wú)錯(cuò)的情況，校正子應(yīng)該等于0，即有給定信息位后，為了計(jì)算監(jiān)督位，上式可以改寫(xiě)為34信息位a6a5a4a3監(jiān)督位a2a1a0信息位a6a5a4a3監(jiān)督位a2a1a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111135在接收端解碼時(shí)，對(duì)于每個(gè)接收碼組，先按式計(jì)算出校正子S1，S2和S3，然后按照表判斷錯(cuò)碼的位置S1S2S3錯(cuò)碼位置S1S2S3錯(cuò)碼位置001a0101a4010a1110a5100a2111a6011a3000無(wú)錯(cuò)碼例：若接收碼組為0000011，則按上三式計(jì)算得到：S1=0，S2=1，S3=1。24561aaaaS???=36上例中的漢明碼是(7,4)碼，其最小碼距d0=3。由式可知，此碼能夠檢測(cè)2個(gè)錯(cuò)碼，或糾正1個(gè)錯(cuò)碼。漢明碼的碼率：

當(dāng)r(或n)很大時(shí)，上式趨近于1。所以漢明碼是一種高效編碼。37練習(xí)題1碼長(zhǎng)n＝15的漢明碼，監(jiān)督位r應(yīng)為多少？編碼效率為多少？試寫(xiě)出監(jiān)督碼元與信息碼元之間的關(guān)系s0s1s2s3錯(cuò)碼位置s0s1s2s3錯(cuò)碼位置0001a01001a80010a11010a90011a91011a100100a31100a110101a41101a120110a51110a130111a61111a141000a70000無(wú)錯(cuò)38令s0s1s2s3=0000，可得監(jiān)督碼元和信息碼元之間的關(guān)系：39線性分組碼的監(jiān)督位和信息位的關(guān)系可以改寫(xiě)為

上式中，已經(jīng)將“”簡(jiǎn)寫(xiě)成“+”。40

上式可以寫(xiě)成矩陣形式：

（模2）

將上式簡(jiǎn)寫(xiě)為

HAT=0T

或AHT=0

A=[a6

a5

a4

a3

a2

a1

a0]

0=[000]監(jiān)督矩陣41監(jiān)督矩陣的性質(zhì)監(jiān)督矩陣H確定碼組中的信息位和監(jiān)督位的關(guān)系。

H可以分成兩部分，例如

典型監(jiān)督矩陣

式中，P為r

k階矩陣，Ir為r

r階單位方陣。H矩陣的各行應(yīng)該是線性無(wú)關(guān)的42 可以寫(xiě)為 上式兩端分別轉(zhuǎn)置后，可以變成式中，Q為k

r階矩陣，是P的轉(zhuǎn)置，即 Q=PT43將Q的左邊加上一個(gè)k階單位方陣，稱(chēng)為生成矩陣：

G稱(chēng)為生成矩陣，因?yàn)榭梢杂盟a(chǎn)生整個(gè)碼組A，即有生成矩陣44生成矩陣的性質(zhì)具有[IkQ]形式的生成矩陣稱(chēng)為典型生成矩陣。矩陣G的各行也必須是線性無(wú)關(guān)的。45錯(cuò)誤圖樣 設(shè)：發(fā)送碼組A是一個(gè)n列的行矩陣： 接收碼組是一個(gè)n列的行矩陣B： 令接收碼組和發(fā)送碼組之差為

E就是錯(cuò)碼的行矩陣 稱(chēng)為錯(cuò)誤圖樣

式中，

(i=0,1,…,n-1)

若ei

=0，表示該碼元未錯(cuò)；若ei=1，表示該碼元為錯(cuò)碼。B–A=E(模2)46校正子計(jì)算B–A=E可以改寫(xiě)成B=A+E上式表示發(fā)送碼組A與錯(cuò)碼矩陣E之和等于接收碼組B。

例如，若發(fā)送碼組A=[1000111]， 錯(cuò)碼矩陣E=[0000100]，則,接收碼組B=[1000011]。

在接收端解碼時(shí)，將接收碼組B和HT相乘S=BHT

47若接收碼組中無(wú)錯(cuò)碼，則B=A。代入后，該式仍成立，即有

BHT=0將B=A+E代入上式，得到: S=(A+E)HT=AHT+EHT

上式右端第一項(xiàng)等于0，所以

S=EHTS和E有一一對(duì)應(yīng)關(guān)系，則S能代表錯(cuò)碼位置。48E：錯(cuò)誤位置校正子S

無(wú)錯(cuò)49線性分組碼的性質(zhì)任意兩個(gè)許用碼組相加后（按位模2相加）仍為一個(gè)許用碼組，即滿足封閉性；最小碼距等于除全零碼組以外碼的最小重量。50練習(xí)題2前述(7,4)漢明碼編碼，若接收端收到B=[0001101]。

有沒(méi)有錯(cuò)誤？ 如果有，如何糾正？51練習(xí)題3已知（7，3）分組碼的監(jiān)督關(guān)系式為求其監(jiān)督矩陣、生產(chǎn)矩陣、全部碼字及糾錯(cuò)能力。52循環(huán)碼：一種特殊的線性分組碼，它的任一碼組循環(huán)移位所得的序列仍在該碼組集中。§9-5循環(huán)碼信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0碼組編號(hào)

12340000010100110000011111101001碼組編號(hào)

5678信息位監(jiān)督位1001011101111011110001010010(7,3)循環(huán)碼舉例一、循環(huán)碼原理53 常用代數(shù)多項(xiàng)式(碼多項(xiàng)式)來(lái)表示碼字，（n,k）線性分組碼的碼多項(xiàng)式為碼多項(xiàng)式 例：[0111010]54多項(xiàng)式的按模除法運(yùn)算例：55生成多項(xiàng)式、監(jiān)督多項(xiàng)式(n,k)循環(huán)碼：對(duì)(xn+1)分解因式：xn+1=g(x)h(x)其中：g(x)=xr

+gr-1xr-1+gr-2xr-2+…+g1x+1h(x)=xk

+hk-1xk-1+hk-2xk-2+…+h1x+1生成多項(xiàng)式監(jiān)督多項(xiàng)式例：x7+1=(x+1)(x3+x2+1)(x3+x+1)(7,4)循環(huán)碼:(7,3)循環(huán)碼:56生成矩陣、監(jiān)督矩陣?yán)?7,4)循環(huán)碼，g(x)=x3+x2+1。GH有了生成矩陣式和監(jiān)督矩陣，我們?cè)瓌t上已經(jīng)可以進(jìn)行編譯碼了，但是針對(duì)循環(huán)碼，我們可以得到簡(jiǎn)單的編譯碼方法。57信息元：M=[mk-1,mk-2,…,m1,m0]碼多項(xiàng)式：T(x)=MG(x)T(x)是循環(huán)碼碼多項(xiàng)式T(x)能被g(x)整除

二、循環(huán)碼編碼、譯碼方法58循環(huán)碼的產(chǎn)生方法思路：尋找能被g(x)整除的、次數(shù)小于n的多項(xiàng)式。為簡(jiǎn)單，考慮系統(tǒng)碼：前k個(gè)碼元為信息元A(x)=xr(mk-1

xk-1+mk-2

xk-2+…+m1

x+m0)+r(x)關(guān)鍵[A(x)],g(x)=0(循環(huán)碼性質(zhì))[xr(mk-1xk-1+mk-2xk-2+…+m1x+m0)+r(x)],g(x)=0[xr(mk-1xk-1+mk-2xk-2+…+m1x+m0)],g(x)=[r(x)],g(x)=r(x)r(x)=[xr(mk-1xk-1+mk-2xk-2+…+m1x+m0)],g(x)59循環(huán)碼的編碼（1）用xn－k乘m(x)，左移r位。

（2）用g(x)除xn－km(x)

，得到余式r(x)（3）編出的碼組T(x)為

60第i個(gè)反饋抽頭：gi=1:接通gi=0:斷開(kāi)多項(xiàng)式除法的實(shí)現(xiàn)除以g(x):D0D1Dr-2Dr-1g1g2gr-1碼元輸入移位寄存器模2加法器“商”輸出當(dāng)最后一個(gè)碼元移入D0時(shí)，D0~Dr-1中的狀態(tài)即“余”例：[1100101]/[10111]61循環(huán)碼編碼器方案系統(tǒng)碼:g(x)=x4+x2+x+1前k拍接通，計(jì)算余式后r拍斷開(kāi)，前k拍向下，輸出信息位后r拍向上，輸出監(jiān)督位前述除法電路的改進(jìn)型62輸入移存器反饋輸出mabcdef000000011011101001101011100000101001000010000010163循環(huán)碼的譯碼原理原則上糾錯(cuò)可按下述步驟進(jìn)行：（1）用生成多項(xiàng)式g(x)除接收碼組R(x)＝T(x)+E(x)得r(x)，如r(x)為0則無(wú)錯(cuò)，否則有錯(cuò)；（2）按余式r(x)用查表的方法或通過(guò)某種運(yùn)算得到錯(cuò)誤圖樣E(x)，就可確定錯(cuò)碼位置；（3）從R(x)中減去E(x)，便得到已糾正錯(cuò)誤的原發(fā)送碼組T(x)。64循環(huán)碼譯碼器方案65三、縮短循環(huán)碼采用縮短循環(huán)碼的原因：在系統(tǒng)設(shè)計(jì)中，碼長(zhǎng)n、信息位數(shù)k和糾錯(cuò)能力常常是預(yù)先給定的。并不是所有長(zhǎng)度n和k上都能找到相應(yīng)的滿足某糾錯(cuò)能力的循環(huán)碼。這時(shí)若將循環(huán)碼縮短，即可滿足n、k和糾錯(cuò)碼能力的要求，且擁有循環(huán)碼編譯碼簡(jiǎn)單的特點(diǎn)。66信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0碼組編號(hào)

12340000010100110000011111101001碼組編號(hào)

5678信息位監(jiān)督位1001011101111011110001010010(7,3)循環(huán)碼縮短循環(huán)碼的構(gòu)成取首位信息碼為0的碼組去掉固定為0的首位信息碼(6,2)縮短循環(huán)碼67交錯(cuò)碼又稱(chēng)交織碼，是一種能糾正突發(fā)錯(cuò)誤的碼，它是以交錯(cuò)的方法來(lái)構(gòu)造碼的。把糾隨機(jī)錯(cuò)誤的（n，k）線性分組碼的m個(gè)碼字，排成m行的一個(gè)碼陣，該碼陣稱(chēng)為交錯(cuò)碼陣。 碼陣在傳輸時(shí)按列的次序進(jìn)行，這樣可以將突發(fā)錯(cuò)誤變?yōu)殡S機(jī)錯(cuò)誤加以糾正。四、交錯(cuò)碼68交錯(cuò)碼糾突發(fā)錯(cuò)的原理例：(7,4)漢明碼，4行，按列傳輸。a16a15a14a13a12a11a10a26a25a24a23a22a21a20a36a35a34a33a32a31a30a46a45a44a43a42a41a4069§9-6卷積碼卷積碼又稱(chēng)連環(huán)碼，和分組碼有明顯的區(qū)別。（n,k）線性分組碼中，r=n－k個(gè)監(jiān)督元僅與本組k個(gè)信息元有關(guān)。卷積碼則不同，每個(gè)（n,k）碼段（也稱(chēng)子碼）不僅與該碼段內(nèi)的信息元有關(guān)，而且與前面m段的信息元有關(guān)。

通常稱(chēng)m為編碼存儲(chǔ)。卷積碼常用符號(hào)（n，k，m）表示。m+1個(gè)碼段具有內(nèi)在的約束聯(lián)系，故稱(chēng)m+1為編碼約束度

70(2,1,2)卷積碼S111010000S3S20001111001100000C1C21101010010110000狀態(tài)abdcbcaa71狀態(tài)圖樹(shù)圖格圖(2,1,2)碼的狀態(tài)圖卷積碼的表示方法0172(2,1,2)卷積碼的樹(shù)圖01730100a:00000000000011b:01c:10d:1111111111111111111010101010110101010101010101010000000010101010(2,1,2)卷積碼的格狀圖74卷積碼的譯碼卷積碼譯碼可分為：代數(shù)譯碼。代數(shù)譯碼是利用生成矩陣和監(jiān)督矩陣來(lái)譯碼，最主要的方法是大數(shù)邏輯譯碼。概率譯碼。概率譯碼比較實(shí)用的有兩種：維特比譯碼和序列譯碼。維特比譯碼思路：把接收碼字與所有可能的碼字比較，選擇一種碼距最小的碼字作為解碼輸出。75收碼：0101

01101001…0100a:00000000000011b:01c:10d:111111111111111111101010101011010101010101010101000000001010101011223133424413維特比譯碼(1)76維特比譯碼(2)77§9-7m序列確知序列：有規(guī)律、可控、可復(fù)現(xiàn)序列隨機(jī)序列：無(wú)規(guī)律、不可控、不可復(fù)現(xiàn)序列偽隨機(jī)序列：具有隨機(jī)特性的確知序列m序列

------由線性反饋移位寄存器產(chǎn)生的周期最長(zhǎng)的碼序列。它具有偽隨機(jī)特性，是目前廣泛應(yīng)用的一種偽隨機(jī)碼。78線性反饋移位寄存器抽頭位置：由特征多項(xiàng)式f(x)決定初始狀態(tài)：非全079m序列對(duì)特征多項(xiàng)式的要求：本原多項(xiàng)式n次多項(xiàng)式f(x)是本原多項(xiàng)式，則：f(x)是既約多項(xiàng)式(不可再分解因式)f(x)可以整除(xp+1)，p=2n-1f(x)不可整除(xq+1)，q<p本原多項(xiàng)式通?？梢圆楸淼玫健次特征多項(xiàng)式可以得到周期為2n－1的m序列80任意給定的非全0初態(tài)m序列產(chǎn)生器例：f(x)=x4+x+181M序列的性質(zhì)1.均衡特性（平衡性）

m序列每一周期P(P=2