數(shù)字通信基礎 差錯控制編碼

差錯控制編碼1概述2常用的幾種簡單分組碼3線性分組碼4循環(huán)碼5卷積碼2005-2-151通信工程教研室差錯控制編碼一概述1.1信道編碼

在數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼和信道編碼。信源編碼是為了提高數(shù)字信號的有效性以及為了使模擬信號數(shù)字化而采取的編碼。信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。數(shù)字信號在傳輸過程中，加性噪聲、碼間串擾等都會產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射功率，降低接收設備本身的噪聲，以及合理選擇調(diào)制、解調(diào)方法等。此外，還可以采用信道編碼技術。2005-2-152通信工程教研室1.2差錯控制方式圖1差錯控制方式2005-2-153通信工程教研室

1.檢錯重發(fā)方式

檢錯重發(fā)又稱自動請求重傳方式，記作ARQ(AutomaticRepeatRequest)。由發(fā)端送出能夠發(fā)現(xiàn)錯誤的碼，由收端判決傳輸中無錯誤產(chǎn)生，如果發(fā)現(xiàn)錯誤，則通過反向信道把這一判決結(jié)果反饋給發(fā)端，然后，發(fā)端把收端認為錯誤的信息再次重發(fā)，從而達到正確傳輸?shù)哪康?。其特點是需要反饋信道，譯碼設備簡單，對突發(fā)錯誤和信道干擾較嚴重時有效，但實時性差，主要在計算機數(shù)據(jù)通信中得到應用。2005-2-154通信工程教研室

2.前向糾錯方式前向糾錯方式記作FEC(ForwordErrorCorrection)。發(fā)端發(fā)送能夠糾正錯誤的碼，收端收到信碼后自動地糾正傳輸中的錯誤。其特點是單向傳輸，實時性好，但譯碼設備較復雜。2005-2-155通信工程教研室

3.混合糾錯方式混合糾錯方式記作HEC(HybridErrorCorrection)是FEC和ARQ方式的結(jié)合。發(fā)端發(fā)送具有自動糾錯同時又具有檢錯能力的碼。收端收到碼后，檢查差錯情況，如果錯誤在碼的糾錯能力范圍以內(nèi)，則自動糾錯，如果超過了碼的糾錯能力，但能檢測出來，則經(jīng)過反饋信道請求發(fā)端重發(fā)。這種方式具有自動糾錯和檢錯重發(fā)的優(yōu)點，可達到較低的誤碼率，因此，近年來得到廣泛應用。2005-2-156通信工程教研室另外，按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨機信道、突發(fā)信道和混合信道。恒參高斯白噪聲信道是典型的隨機信道，其中差錯的出現(xiàn)是隨機的，而且錯誤之間是統(tǒng)計獨立的。具有脈沖干擾的信道是典型的突發(fā)信道，錯誤是成串成群出現(xiàn)的，即在短時間內(nèi)出現(xiàn)大量錯誤。短波信道和對流層散射信道是混合信道的典型例子，隨機錯誤和成串錯誤都占有相當比例。對于不同類型的信道，應采用不同的差錯控制方式。2005-2-157通信工程教研室1.3糾錯碼的分類

(1)根據(jù)糾錯碼各碼組信息元和監(jiān)督元的函數(shù)關系，可分為線性碼和非線性碼。如果函數(shù)關系是線性的，即滿足一組線性方程式，則稱為線性碼，否則為非線性碼。

(2)根據(jù)上述關系涉及的范圍，可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關；卷積碼中的碼元不僅與本組的信息元有關，而且還與前面若干組的信息元有關。

(3)根據(jù)碼的用途，可分為檢錯碼和糾錯碼。檢錯碼以檢錯為目的，不一定能糾錯；而糾錯碼以糾錯為目的，一定能檢錯。2005-2-158通信工程教研室1.4糾錯編碼的基本原理

1.分組碼

分組碼一般可用(n,k)表示。其中，k是每組二進制信息碼元的數(shù)目，n是編碼碼組的碼元總位數(shù)，又稱為碼組長度，簡稱碼長。n-k=r為每個碼組中的監(jiān)督碼元數(shù)目。簡單地說，分組碼是對每段k位長的信息組以一定的規(guī)則增加r個監(jiān)督元，組成長為n的碼字。在二進制情況下，共有2k個不同的信息組，相應地可得到2k個不同的碼字，稱為許用碼組。其余2n-2k個碼字未被選用，稱為禁用碼組。2005-2-159通信工程教研室在分組碼中，非零碼元的數(shù)目稱為碼字的漢明重量，簡稱碼重。例如，碼字10110，碼重w=3。兩個等長碼組之間相應位取值不同的數(shù)目稱為這兩個碼組的漢明(Hamming)距離，簡稱碼距。例如11000與10011之間的距離d=3。碼組集中任意兩個碼字之間距離的最小值稱為碼的最小距離，用d0表示。最小碼距是碼的一個重要參數(shù)，它是衡量碼檢錯、糾錯能力的依據(jù)。2005-2-1510通信工程教研室2.檢錯和糾錯能力若分組碼碼字中的監(jiān)督元在信息元之后，而且是信息元的簡單重復，則稱該分組碼為重復碼。它是一種簡單實用的檢錯碼，并有一定的糾錯能力。例如(2,1)重復碼，兩個許用碼組是00與11，d0=2，收端譯碼，出現(xiàn)01、10禁用碼組時，可以發(fā)現(xiàn)傳輸中的一位錯誤。如果是(3,1)重復碼，兩個許用碼組是000與111,d0=3;當收端出現(xiàn)兩個或三個1時，判為1，否則判為0。此時，可以糾正單個錯誤，或者該碼可以檢出兩個錯誤。2005-2-1511通信工程教研室碼的最小距離d0直接關系著碼的檢錯和糾錯能力；任一(n,k)分組碼，若要在碼字內(nèi):(1)檢測e個隨機錯誤，則要求碼的最小距離d0≥e+1;(2)糾正t個隨機錯誤，則要求碼的最小距離d0≥2t+1;(3)糾正t個同時檢測e(>t)個隨機錯誤，則要求碼的最小距離d0≥t+e+1。2005-2-1512通信工程教研室

3.編碼效率用差錯控制編碼提高通信系統(tǒng)的可靠性，是以降低有效性為代價換來的。我們定義編碼效率R來衡量有效性:R=k/n

其中,k是信息元的個數(shù)，n為碼長。對糾錯碼的基本要求是:檢錯和糾錯能力盡量強；編碼效率盡量高；編碼規(guī)律盡量簡單。實際中要根據(jù)具體指標要求，保證有一定糾、檢錯能力和編碼效率，并且易于實現(xiàn)。2005-2-1513通信工程教研室二常用的幾種簡單分組碼2.1奇偶監(jiān)督碼奇偶監(jiān)督碼是在原信息碼后面附加一個監(jiān)督元，使得碼組中“1”的個數(shù)是奇數(shù)或偶數(shù)。或者說，它是含一個監(jiān)督元，碼重為奇數(shù)或偶數(shù)的(n,n-1)系統(tǒng)分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。2005-2-1514通信工程教研室設碼字A=［an-1,an-2,…,a1,a0］，對偶監(jiān)督碼有奇監(jiān)督碼情況相似，只是碼組中“1”的數(shù)目為奇數(shù)，即滿足條件而檢錯能力與偶監(jiān)督碼相同。奇偶監(jiān)督碼的編碼效率R為檢錯能力為能夠檢測出奇數(shù)位錯。

2005-2-1515通信工程教研室2.2行列監(jiān)督碼圖2(66,50)行列監(jiān)督碼特殊情況下（一行一列）具有糾錯能力，同行（列）有偶數(shù)錯無法糾錯，方陣四個頂角有錯時無法檢測出來。

2005-2-1516通信工程教研室2005-2-1517通信工程教研室2.3恒比碼碼字中1的數(shù)目與0的數(shù)目保持恒定比例的碼稱為恒比碼。由于恒比碼中，每個碼組均含有相同數(shù)目的1和0，因此恒比碼又稱等重碼，定1碼。這種碼在檢測時，只要計算接收碼元中1的數(shù)目是否正確，就知道有無錯誤。

目前我國電傳通信中普遍采用3∶2碼，又稱“5中取3”的恒比碼，即每個碼組的長度為5，其中3個“1”。這時可能編成的不同碼組數(shù)目等于從5中取3的組合數(shù)10，這10個許用碼組恰好可表示10個阿拉伯數(shù)字，如表9-1所示。而每個漢字又是以四位十進制數(shù)來代表的。實踐證明，采用這種碼后，我國漢字電報的差錯率大為降低。2005-2-1518通信工程教研室表13∶2恒比碼2005-2-1519通信工程教研室三線性分組碼

3.1現(xiàn)以(7,4)分組碼為例來說明線性分組碼的特點。設其碼字為A=［a6

a5

a4

a3

a2

a1

a0］，其中前4位是信息元，后3位是監(jiān)督元，可用下列線性方程組來描述該分組碼，產(chǎn)生監(jiān)督元。2005-2-1520通信工程教研室表2(7,4)碼的碼字表碼字序號序號碼字信息元監(jiān)督元信息元監(jiān)督元000000008100011110001011910011002001010110101001030011110111011001401001101211000015010110113110101060110011141110100701110001511111112005-2-1521通信工程教研室3.2監(jiān)督矩陣H和生成矩陣G（7，4）碼的3個監(jiān)督方程式為線性方程可用矩陣形式表示為2005-2-1522通信工程教研室并簡記為其中，AT是A的轉(zhuǎn)置，OT是O=[000]的轉(zhuǎn)置，HT是H的轉(zhuǎn)置。H稱為監(jiān)督矩陣，一旦H給定，信息位和監(jiān)督位之間的關系也就確定，簡稱H矩陣，H矩陣每行之間是彼此線性無關的。式（9—7）所示的H矩陣可以表示為2005-2-1523通信工程教研室其中,P為r×k階矩陣，Ir為r×r階單位矩陣?？梢詫懗蒆=［PIr］形式的矩陣稱為典型監(jiān)督矩陣。

HAT=0T，說明H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來作為判斷接收碼字A是否出錯的依據(jù)。若把監(jiān)督方程補充為下列方程2005-2-1524通信工程教研室可改寫為矩陣形式2005-2-1525通信工程教研室2005-2-1526通信工程教研室3.3伴隨式(校正子)S

設發(fā)送碼組A=［an-1,an-2,…,a1,a0］，在傳輸過程中可能發(fā)生誤碼，設接收碼組B=［bn-1,bn-2,…,b1,b0］，則收發(fā)碼組之差定義為錯誤圖樣E，也稱為誤差矢量，即其中E=［en-1,en-2,…,e1,e0］，且當bi=ai

當bi≠ai

(9-15)2005-2-1527通信工程教研室式(9-15)也可寫作令S=BHT，稱為伴隨式或校正子。因為2005-2-1528通信工程教研室表3(7,4)碼S與E的對應關系2005-2-1529通信工程教研室線性分組碼具有封閉性：在一組線性碼中，任意兩個碼組之和仍為該種碼中的一個碼組。碼的最小距離也是碼的最小重量。由于線性碼具有封閉性，當E=A時，S=0，認為無錯碼，即不能檢測錯碼，需要計算出不能檢錯的概率。設（n,k）線性分組碼最大能檢錯位數(shù)為D，發(fā)送“0”、“1”等概，信道誤碼率為Pe，則不能檢錯的概率為其中Wi為重量為i的許用碼組數(shù)。2005-2-1530通信工程教研室4循環(huán)碼表4(7,3)循環(huán)碼2005-2-1531通信工程教研室在代數(shù)理論中，為了便于計算，常用碼多項式表示碼字。(n,k)循環(huán)碼的碼字，其碼多項式(以降冪順序排列)為其中冪的次數(shù)對應2進制數(shù)的權重位，乘x表示左移一位。2005-2-1532通信工程教研室4.1生成多項式及生成矩陣如果一種碼的所有碼多項式都是多項式g(x)的倍式，則稱g(x)為該碼的生成多項式。在(n,k)循環(huán)碼中任意碼多項式A(x)都是最低次碼多項式的倍式。如表9-4的(7,3)循環(huán)碼中，2005-2-1533通信工程教研室其它碼多項式都是g(x)的倍式，即2005-2-1534通信工程教研室循環(huán)碼的生成矩陣常用多項式的形式來表示2005-2-1535通信工程教研室例如(7,3)循環(huán)碼，n=7,k=3,r=4,其生成多項式及生成矩陣分別為2005-2-1536通信工程教研室生成多項式轉(zhuǎn)換成的生成矩陣，還要利用初等行變換轉(zhuǎn)換成典型生成矩陣G=[IkQ]形式，才能按線性分組碼的方法計算編碼結(jié)果和計算校正子進行檢錯與糾錯。2005-2-1537通信工程教研室4.2監(jiān)督多項式及監(jiān)督矩陣

為了便于對循環(huán)碼編譯碼，通常還定義監(jiān)督多項式，令

其中g(x)是常數(shù)項為1的r次多項式，是生成多項式；h(x)是常數(shù)項為1的k次多項式，稱為監(jiān)督多項式。同理，可得監(jiān)督矩陣H

2005-2-1538通信工程教研室是h(x)的逆多項式。例如(7，3)循環(huán)碼，g(x)=x4+x3+x2+1，則其中2005-2-1539通信工程教研室2005-2-1540通信工程教研室利用初等行變換轉(zhuǎn)換成典型生成矩陣H=[PIr]形式2005-2-1541通信工程教研室4.3編碼方法和電路在編碼時，首先要根據(jù)給定的(n,k)值選定生成多項式g(x)，即應在xn+1的因式中選一r=n-k次多項式作為g(x)。設編碼前的信息多項式m(x)為循環(huán)碼（系統(tǒng)碼）的碼多項式可表示為編碼時將m(x)左移r位（到最左側(cè)），被生成多項式除，余式就是r(x)，放在m(x)之后。2005-2-1542通信工程教研室圖9-3(7,3)循環(huán)碼編碼電路2005-2-1543通信工程教研室表9-5(7,3)循環(huán)碼的編碼過程2005-2-1544通信工程教研室9.4.4譯碼方法和電路圖4(7,3)循環(huán)碼譯碼電路譯碼時B(x)被生成多項式g(x)除，余式就是r(x)，計算或查表得到S(x)不為0則檢測出錯誤，能與E(x)對應則可糾錯。+2005-2-1545通信工程教研室2005-2-1546通信工程教研室卷積碼(n,k,N)表示碼組長度為n，信息元為k位，與N個信息段（包括當前信息段）的信息元有關。圖5卷積碼(2,1,3)編碼器5.1基本概念五

卷積碼2005-2-1547通信工程教研室起始狀態(tài)，各級移位寄存器清零，即S1S2S3為000。S1等于當前輸入數(shù)據(jù)，而移位寄存器狀態(tài)S2S3存儲以前的數(shù)據(jù)，輸出碼字C由下式確定表6(2,1,3)編碼器的工作過程2005-2-1548通信工程教研室5.2卷積碼的描述1.樹圖圖6(2,1,2)碼的樹圖S3S2為狀態(tài)標記

S1只能為0、1

2005-2-1549通信工程教研室2.狀態(tài)圖圖7(2,1,3)碼的狀態(tài)圖2005-2-1550通信工程教研室3.格圖圖8(2,1,3)碼的格圖2005-2-1551通信工程教研室5.3卷積碼的譯碼卷積碼的譯碼分為兩大類：大邏輯數(shù)譯碼，又稱門限譯碼；概率譯碼，如維特比譯碼、序列譯碼。1.大邏輯數(shù)譯碼設(2,1,6)卷積碼編碼規(guī)則：b為信息元，

c為卷積碼的監(jiān)督元。譯碼時，將b移位寄存并再編碼得c’，與c比較得誤差e，列出校正子約束方程。根據(jù)正交于e11錯誤元的一致校驗和式Si表達式可知，連續(xù)12位中如錯誤樣圖E中錯誤位數(shù)不多于2位，且其中一位發(fā)生在e11，則ΣSi

≥

3；如果E中錯誤位數(shù)不多于2位，且e11位上未發(fā)生錯誤，則ΣSi≤2。因此進行大數(shù)判決，決定是否對e11進行糾正。2005-2-1552通信工程教研室將最大似然算法加以簡化，得到維特比譯碼。其方法為：所已接收到的碼序列與所有可能的發(fā)送序列做比較，選擇其中碼距最小的序列作為判決（發(fā)送）序列。設發(fā)送為L組k位的序列，則共有2kL種排列方法，將這些序列存儲并與接收序列進行比較，找到碼距最小的序列作為判決序列，即最大似然解碼。維特比譯碼對此做了簡化，即分段比較選擇，最終達到整個序列是一個最大似然序列，成為實用算法。2.維特比譯碼2005-2-1553通信工程教研室圖9維特比譯碼格圖·

·

·

·

·

·

·

·

·

·

·

·

上下支路均保留，封閉時再去掉。

·

·

2005-2-1554通信工程教研室

3.序列譯碼

當m很大時，可以采用序列譯碼法。其過程如