數(shù)字通信第41章糾錯碼

2023/1/101第4章差錯控制編碼2023/1/102內(nèi)容4.1引言4.2糾錯編碼的基本原理4.3常用的簡單編碼4.4線性分組碼4.5卷積碼4.6Turbo碼和LDPC碼4.7編碼調(diào)制2023/1/1034.1引言信道分類：從差錯控制角度看隨機信道：錯碼的出現(xiàn)是隨機的，噪聲引起突發(fā)信道：錯碼成串集中出現(xiàn)，干擾、快衰落引起混合信道：既存在隨機錯碼又存在突發(fā)錯碼差錯控制技術(shù)的種類反饋校驗前向糾錯檢錯重發(fā)檢錯刪除2023/1/104差錯控制技術(shù)1.反饋檢驗法需要雙向信道，和前向信道有相同的通信容量。引入較大的延時可以糾正任何錯誤BA2023/1/1052.前向糾錯（FEC）不需要雙向信道實時性好靠糾錯編碼2023/1/106

3.檢錯重發(fā)法（ARQ）自動請求重發(fā)需要反向信道，但容量降低，會引入停頓BA2023/1/107三種自動請求重發(fā)(ARQ)系統(tǒng)停止等待ARQ系統(tǒng)系統(tǒng)工作在半雙工狀態(tài)，時間沒有得到充分利用，傳輸效率較低。接收碼組ACKACKNAKACKACKNAKACKt1233455發(fā)送碼組12334556t有錯碼組有錯碼組AB2023/1/108拉后ARQ系統(tǒng)需要對發(fā)送的數(shù)據(jù)組和答復(fù)進行編號，以便識別。系統(tǒng)需要雙工信道接收數(shù)據(jù)有錯碼組有錯碼組91011101112214365798576ACK1NAK5NAK9ACK5發(fā)送數(shù)據(jù)57695214367981011101112重發(fā)碼組重發(fā)碼組2023/1/109選擇重發(fā)ARQ系統(tǒng)它只重發(fā)出錯的數(shù)據(jù)組，因此進一步提高了傳輸效率。接收數(shù)據(jù)有錯碼組有錯碼組921436575981011131412發(fā)送數(shù)據(jù)995852143671011131412重發(fā)碼組重發(fā)碼組NAK9ACK1NAK5ACK5ACK92023/1/1010ARQ的主要優(yōu)點：和前向糾錯方法相比監(jiān)督碼元較少(碼率較高)能使誤碼率降到很低；檢錯的計算復(fù)雜度較低；檢錯用的編碼方法和加性噪聲的統(tǒng)計特性基本無關(guān)，能適應(yīng)不同特性的信道。ARQ技術(shù)的優(yōu)缺點2023/1/1011ARQ的主要缺點：重發(fā)而使ARQ系統(tǒng)的傳輸效率降低。在要求實時通信的場合，例如電話通信，往往不允許使用ARQ法。信道干擾嚴重時，可能發(fā)生因不斷重發(fā)造成事實上的通信中斷。需要雙向信道來重發(fā)，不能用于單向信道，也不能用于一點到多點的通信系統(tǒng)。ARQ技術(shù)的優(yōu)缺點2023/1/10124.2差錯控制編碼的基本原理如用三位二進制編碼來代表八個字母 000 A 100 E 001 B 101 F 010 C 110 G 011 D 111 H不管哪一位發(fā)生錯誤，都會使傳輸字母錯誤如用三位二進制編碼傳四個字母 000 A 011 B 101 C 110 D發(fā)生一位錯誤，許用碼字將變成禁用碼字，接收端就能知道出錯，但是不能糾錯。2023/1/1013如用三位二進制編碼傳二個字母 000 A 111 B

檢二個錯誤，糾正一個錯誤。具有檢錯或糾錯的碼組，其所用的比特數(shù)必須大于信息碼組原來的比特數(shù)－>引入冗余度。結(jié)論2023/1/1014分組碼的符號：(n,k)n－碼組的總位數(shù)，又稱為碼組的長度（碼長），k－碼組中信息碼元的數(shù)目，n–k＝r－碼組中的監(jiān)督碼元數(shù)目，或稱監(jiān)督位數(shù)目。將信息碼分組，為每組信息碼附加若干監(jiān)督碼的編碼稱為分組碼。分組碼的結(jié)構(gòu)

2023/1/1015監(jiān)督碼元：在發(fā)送端需要在信息碼元序列中增加一些差錯控制碼元，它們稱為監(jiān)督碼元。在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。信息位和監(jiān)督位的關(guān)系：舉例如下信息位監(jiān)督位晴000云011陰101雨1102023/1/1016碼率編碼效率(碼率)：設(shè)編碼序列中信息碼元數(shù)量為k，總碼元數(shù)量為n，則比值k/n就是碼率。冗余度：指增加的監(jiān)督碼元多少。例如，若編碼序列中平均每兩個信息碼元就添加一個監(jiān)督碼元，則這種編碼的多余度為1/3。理論上，差錯控制以降低信息傳輸速率為代價換取提高傳輸可靠性。2023/1/1017碼重、碼距碼重(weight)一個碼字中“1”的數(shù)目碼距(distance)兩個碼字之間對應(yīng)位置上1、0不同的個數(shù)，又叫漢明(Hamming)距。 10110碼重：3 01100碼重：2最小碼距：把某種編碼中各個碼組之間距離的最小值稱為最小碼距(d0)。例如，上面的編碼的最小碼距d0=2。碼距：32023/1/1018圖9-1碼距的幾何意義(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a12023/1/1019為檢測e個錯碼，要求最小碼距d0e+1

0123BA漢明距離ed0最小漢明距與檢錯、糾錯能力2023/1/1020為了糾正t個錯碼，要求最小碼距d02t+1BtA漢明距離012345td02023/1/1021為糾正t個錯碼，同時檢測e個錯碼，要求最小碼距先分析下圖所示例子。按照檢錯能力公式，最多能檢測4個錯碼，按照糾錯能力公式糾錯時，能糾正2個錯碼。但是，不能同時作到兩者，因為當(dāng)錯碼位數(shù)超過糾錯能力時，該碼組進入另一碼組的圓內(nèi)而被錯誤地“糾正”了。BtA漢明距離012345td02023/1/1022 所以，為了在可以糾正t個錯碼的同時，能夠檢測e個錯碼，就需要像下圖那樣，使某一碼組（A）發(fā)生e個錯誤之后所處的位置，與其他碼組（B）的糾錯圓圈至少距離等于1，不然將落在該糾錯圓上從而發(fā)生錯誤地“糾正”。因此，要求最小碼距

這種糾錯和檢錯結(jié)合的工作方式簡稱糾檢結(jié)合。ABe1tt漢明距離2023/1/1023 這種工作方式是自動在糾錯和檢錯之間轉(zhuǎn)換的。當(dāng)錯碼數(shù)量少時，系統(tǒng)按前向糾錯方式工作，以提高傳輸效率；當(dāng)錯碼數(shù)量多時，系統(tǒng)按反饋重發(fā)方式糾錯，以降低系統(tǒng)的總誤碼率。它適用于大多數(shù)時間中錯碼數(shù)量很少，少數(shù)時間中錯碼數(shù)量多的情況。2023/1/1024漢明距與檢錯、糾錯能力為檢查出e個錯誤，要求最小碼距為為糾正t個錯誤，要求最小碼距為為糾正t個錯誤，同時檢查出e個錯誤，要求最小碼距為2023/1/1025香農(nóng)信道編碼理論香農(nóng)信道編碼定理存在噪聲干擾的信道，若離散信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息，則一定存在一種編碼方式，使譯碼的錯誤概率隨著碼長N的增加將按指數(shù)下降到任意小的值，即E[R]為正實函數(shù)，稱為誤差指數(shù)，與R、C的關(guān)系如圖：RC1C2C1>C2E(R)2023/1/1026香農(nóng)信道編碼理論結(jié)論在有擾信道中，只要信息傳輸速率(碼率)小于信道容量，采用信道編碼有可能實現(xiàn)任意可靠的信息傳輸。存在性證明。如碼長及信息速率一定，可以通過增大信道容量，使Pe減小。如信道容量及信息速率一定，可以通過增加碼長，使錯誤概率下降。2023/1/1027系統(tǒng)帶寬和信噪比的矛盾：為了糾錯需要在發(fā)送信息碼元序列中加入監(jiān)督碼元。這樣使發(fā)送序列增長，冗余度增大。若仍須保持發(fā)送信息碼元速率不變，則傳輸速率必須增大，因而增大了系統(tǒng)帶寬。系統(tǒng)帶寬的增大將引起系統(tǒng)中噪聲功率增大，使信噪比下降。信噪比的下降反而又使系統(tǒng)接收碼元序列中的錯碼增多。一般說來，采用糾錯編碼后，誤碼率總是能夠得到很大改善的。改善的程度和所用的編碼有關(guān)。糾錯碼的作用2023/1/1028未采用糾錯編碼時， 若接收信噪比等于 7dB，編碼前誤碼率 約為810-4，圖中A 點，在采用糾錯編碼 后，誤碼率降至約4 10-5，圖中B點。 不增大發(fā)送功率就能 降低誤碼率約一個半 數(shù)量級。10-610-510-410-310-210-1編碼后PeCDEAB信噪比(dB)編碼性能舉例2023/1/1029若保持誤碼率在10-5， 圖中C點，未采用編 碼時，約需要信噪比 Eb/n0=9.5dB。在 采用這種編碼時，約 需要信噪比7.5dB，圖 中D點?？梢怨?jié)省功率 2dB。通常稱這2dB為 編碼增益。上面兩種情況付出的代 價是帶寬增大。10-610-510-410-310-210-1編碼后PeCDEAB信噪比(dB)2023/1/1030傳輸速率和Eb/n0的關(guān)系 對于給定的傳輸系統(tǒng) 若希望提高傳輸速率， 由上式看出必使信 噪比下降，誤碼率增 大。假設(shè)系統(tǒng)原來工作 在圖中C點，提高速率后 由C點升到E點。但加用糾錯編碼后，仍可將誤碼率降到D點。這時付出的代價仍是帶寬增大。10-610-510-410-310-210-1編碼后PeCDEAB信噪比(dB)2023/1/10314.3常用的簡單編碼奇偶校驗碼二維奇偶校驗碼恒比碼正反碼2023/1/1032奇偶校驗碼特點：偶校驗奇校驗編碼檢錯能力：如果以上關(guān)系被破壞，則出現(xiàn)錯誤，因此能檢查出奇數(shù)個錯誤，但不能檢測偶數(shù)個錯誤。 討論：這種碼檢錯能力不高(最小碼距為dmin=2)，采用什么方法提高呢？2023/1/1033二維奇偶校驗碼特點：檢碼字按行排成方陣，不僅對行進行奇偶校驗，而且也對列進行奇偶校驗。編碼：檢錯能力：有可能檢測偶數(shù)個錯誤，但對構(gòu)成矩形的4個錯碼檢測不出；適于檢測突發(fā)錯誤。列監(jiān)督位，行監(jiān)督位，/0/1/0/1對稱出現(xiàn)4個錯碼也檢不出來2023/1/1034等比碼編碼規(guī)則：電傳機傳輸十位阿拉伯?dāng)?shù)字時，用5位代碼表示，每個碼組的長度為5，其中恒有3個“1”，稱為“5中取3”恒比碼。共有種許用碼組。檢錯能力：能夠檢測碼組中所有奇數(shù)個錯誤和部分偶數(shù)個錯誤，但不能檢測碼組中1變?yōu)?與0變?yōu)?的錯碼數(shù)目相同的那些偶數(shù)個錯誤。2023/1/1035正反碼編碼規(guī)則：信息位段有奇數(shù)個1：1100111001（監(jiān)督位與信息位重復(fù)）信息位段有偶數(shù)個1：1000101110（監(jiān)督位是信息位反碼）。檢錯能力：能夠糾正一位錯碼，并能檢測全部兩位以下的錯碼和大部分兩位以上的錯碼。信息位監(jiān)督位信息位監(jiān)督位2023/1/1036正反碼的解碼在上例中，先將接收碼組中信息位和監(jiān)督位按模2相加，得到一個5位的合成碼組。然后，由此合成碼組產(chǎn)生一個校驗碼組。若接收碼組的信息位中有奇數(shù)個“1”，則合成碼組就是校驗碼組；若接收碼組的信息位中有偶數(shù)個“1”，則取合成碼組的反碼作為校驗碼組。最后，觀察校驗碼組中“1”的個數(shù)，按下表進行判決及糾正可能發(fā)現(xiàn)的錯碼。2023/1/1037校驗碼組和錯碼的關(guān)系

例如，若發(fā)送碼組為1100111001，接收碼組中無錯碼，則合成碼組應(yīng)為1100111001=00000。由于接收碼組信息位中有奇數(shù)個“1”，所以校驗碼組就是00000。按上表判決，結(jié)論是無錯碼。校驗碼組的組成錯碼情況1全為“0”無錯碼2有4個“1”和1個“0”信息碼中有1位錯碼，其位置對應(yīng)校驗碼組中“0”的位置3有4個“0”和1個“1”監(jiān)督碼中有1位錯碼，其位置對應(yīng)校驗碼組中“1”的位置4其他組成錯碼多于1個2023/1/10384.4線性分組碼內(nèi)容：一、分組碼基本概念二、漢明碼的構(gòu)造三、線性分組碼的編碼及譯碼2023/1/1039差錯控制編碼分類按功能分檢錯碼糾錯碼糾刪碼（發(fā)現(xiàn)不可糾正的錯誤時，可發(fā)出指示或刪除）按信息碼元和監(jiān)督碼元之間的校驗關(guān)系分線性碼非線性碼按信息碼元和監(jiān)督碼元之間的約束方式分分組碼卷積碼2023/1/1040代數(shù)碼：建立在代數(shù)學(xué)基礎(chǔ)上的編碼。線性碼：按照一組線性方程構(gòu)成的代數(shù)碼。在線性碼中信息位和監(jiān)督位是由一些線性代數(shù)方程聯(lián)系著的。線性分組碼：按照一組線性方程構(gòu)成的分組碼。本節(jié)將以漢明碼為例引入線性分組碼的一般原理?；靖拍?023/1/1041定義：可用線性方程組（代數(shù)關(guān)系）表述碼的規(guī)律性的分組碼稱為線性分組碼。例如偶校驗碼的編程原理利用了代數(shù)關(guān)系：稱奇偶校驗碼為線性分組碼。碼參數(shù)：分組碼一般用表示，其中：n是碼長，k/n是編碼效率2023/1/1042圖9-3分組碼結(jié)構(gòu)2023/1/1043漢明碼（Hamming）提出：為了糾正一位錯誤碼，在分組碼中最少要幾位監(jiān)督碼位？編碼效率能否提高？從這種思想出發(fā)，便導(dǎo)致了漢明碼的誕生。特點：漢明碼是能夠糾正一位錯碼且編碼效率較高的一種線性分組碼。2023/1/1044漢明碼的構(gòu)造下面介紹漢明碼的構(gòu)造原理。內(nèi)容：校正子（伴隨式）個數(shù)與糾錯能力的關(guān)系舉例：（7，4）漢明碼校驗方程編譯碼方法2023/1/1045校正子的個數(shù)與糾錯能力的關(guān)系一位校正子的情況先回顧偶校驗碼,在接收端實際上計算監(jiān)督關(guān)系式：，若，認為碼字無錯，有錯由于s（校正子）只有兩種形式“0”或“1”，只能代表有錯或無錯，因而不找出錯碼的位置。2023/1/1046校正子的個數(shù)與糾錯能力的關(guān)系二位校正子的情況兩個監(jiān)督式就有兩個校正子，其可能值有4種組合：00，01，10，11，這4種組合代表不同信息。若用1種組合表示無錯，其余3種組合就可以用來表示一位錯碼的3種不同位置。2023/1/1047校正子的個數(shù)與糾錯能力的關(guān)系位校正子的情況個監(jiān)督式能指示一位錯碼的個可能位置。一般來說，若，則監(jiān)督位，一般線性碼要糾正一位以上的錯誤應(yīng)滿足：漢明碼滿足：2023/1/10482.舉例：（7，4）漢明碼如何構(gòu)造這些監(jiān)督關(guān)系式（校驗方程）：設(shè)碼字（7，4）～校正子（3個監(jiān)督關(guān)系式中的校正子），可建立三個互為獨立的監(jiān)督關(guān)系式。校驗位信息位2023/1/1049校驗方程的推導(dǎo)的值與錯碼位置的對應(yīng)關(guān)系可以規(guī)定如下表：錯碼位置錯碼位置001101010110100111011000無錯2023/1/1050可寫成偶監(jiān)督關(guān)系式：

2023/1/1051校驗方程校驗方程2023/1/1052編碼方法上面的校驗方程可寫成監(jiān)督碼元在左邊的形式：信息位確定后，可直接按上式計算出監(jiān)督位。2023/1/1053信息位a6a5a4a3監(jiān)督位a2a1a0信息位a6a5a4a3監(jiān)督位a2a1a000000001000111000101110011000010101101001000111101011001010011011000010101101110101001100111110100011100011111112023/1/1054譯碼方法譯碼：接收端收到每個碼字后，先計算出，再按表判斷錯碼情況。如果不全零，可判出在哪一位出錯。2023/1/1055按照上述方法構(gòu)造的碼稱為漢明碼。表中所列的(7,4)漢明碼的最小碼距d0=3。因此，這種碼能夠糾正1個錯碼或檢測2個錯碼。由于碼率k/n=(n-r)/n=1–r/n，故當(dāng)n很大和r很小時，碼率接近1?？梢?，漢明碼是一種高效碼。2023/1/1056三、線性分組碼的一般原理內(nèi)容：(1)校驗矩陣和生成矩陣(2)校正子S（伴隨式）譯碼2023/1/1057校驗矩陣（7，4）漢明碼的監(jiān)督方程矩陣形式上式還可以簡記為HAT=0T或AHT=0 2023/1/1058校驗矩陣校驗矩陣H矩陣稱為典型形式，各行一定是線性無關(guān)的。而一個非典型形式的經(jīng)過運算可以化成典型形式，通過校驗矩陣可以知道監(jiān)督碼和信息碼的監(jiān)督關(guān)系。2023/1/1059生成矩陣若把監(jiān)督關(guān)系式改寫為：2023/1/1060生成矩陣改寫為矩陣形式：即：其中：2023/1/1061生成矩陣和編碼生成矩陣

，通過校驗矩陣可以得到生成碼組。編碼：如果輸入碼組為00112023/1/1062生成矩陣和編碼由這種方式得到的生成矩陣稱為典型生成矩陣，由它產(chǎn)生的分組碼必定為系統(tǒng)碼，也就是信息碼字保持不變，監(jiān)督位附加其后，每行一定是線性無關(guān)的，每行都是一個生成碼組。2023/1/1063伴隨式譯碼原理發(fā)送碼組