信道編碼2023/2/82第6章信道編碼目的：了解信道編碼的作用與意義掌握幾種典型的信道編碼、譯碼方法對信道編碼的研究方法和成果有基本認識，為進一步研究打下基礎特點：基本概念、物理意義、基本方法為主2023/2/83主要內容基本概念和方法線性分組碼循環碼（實驗）BCH卷積碼2023/2/856.1用于可靠傳輸和存儲數據的編碼

——信道編碼的引入移動通信通信網小張小李2023/2/866.1用于可靠傳輸和存儲數據的編碼

——信道編碼的引入通信的目的在于傳輸信息通信系統主要質量指標是通信的有效性和可靠性在實際信道上傳輸信號時，由于信道傳輸特性不理想及噪聲的影響，接收端收到的信號不可避免地會發生錯誤發送端接收端干擾2023/2/876.1用于可靠傳輸和存儲數據的編碼

——信道編碼的引入隨著差錯控制編碼理論的完善和數字電路技術的發展，信道編碼不僅應用于各種通信系統中，在計算機存儲、運算系統以及超大規模集成電路的設計中也得到日益廣泛的應用。2023/2/896.1用于可靠傳輸和存儲數據的編碼

——信道編碼的基本思想通過對信息碼元序列作某種變換,即增加一定數量的多余碼元，使原來彼此相互獨立、沒有關聯的信息碼元,經過變換后,產生某種規律性或相關性,從而在接收端可根據這種規律性來檢查、糾正傳輸序列中的差錯。編碼的實質——利用冗余降低差錯概率。2023/2/8106.1用于可靠傳輸和存儲數據的編碼

——信道編碼的基本思想舉例：ASCII碼的偶校驗過程ASCII碼：7bit表示符號，例如“L”的ASCII是偶校驗：使得編碼后輸出的碼字中“1”的個數為偶數

0011001->00110011接收端驗證“1”的個數是否為偶數這一“規律”（關系）是否成立來檢驗錯誤是否發生啟示需要增加冗余碼元（8，7）監督碼元與信息碼元建立了一組關系接收端利用這組關系檢查和糾正錯誤2023/2/8116.1用于可靠傳輸和存儲數據的編碼

——編碼系統模型信源：輸出的是信息序列（信息碼元）信道：廣義信道，也稱編碼信道2023/2/8136.1用于可靠傳輸和存儲數據的編碼

——編碼系統模型三點說明：1.不可無限的增加冗余碼2.盡可能的重現m，即使m′盡量接近m3.編譯碼算法易實現，設備費用盡量低研究各種編碼和譯碼方法是信道編碼所要解決的問題。噪聲干擾2023/2/8146.2錯誤類型與信道模型噪聲干擾輸入輸出轉移概率2023/2/8156.2錯誤類型與信道模型隨機錯誤和隨機信道突發錯誤和突發信道混合錯誤和混合信道2023/2/817二進制對稱信道（BinarySymmetricChannel,BSC）P(1/0)=pP(0/1)=pP(1/1)=1-pP(0/0)=1-p輸入符號取值集合

X={0，1}輸出符號取值集合

Y={0，1}0101XYpp1-p1-p6.2錯誤類型與信道模型2023/2/8186.2錯誤類型與信道模型突發錯誤和突發信道突發錯誤：噪聲對各傳輸碼元的影響不是獨立的，從而導致差錯是一連串出現的。例如移動通信中信號在某一段時間內發生衰落，造成一串差錯；光盤上的一條劃痕等。存在突發錯誤的信道，稱之為有記憶信道/突發信道。2023/2/8196.2錯誤類型與信道模型混合錯誤和混合信道混合錯誤：既有突發錯誤又有隨機錯誤。突發錯誤和隨機錯誤并存的信道稱之為混合信道。2023/2/821例：發送序列C：（1111100000），收到的序列R：（1001010000），第二、三、五、六位產生了錯誤，因此錯誤圖樣e的二、三、五、六位取值為1，即e：(0110110000)對于突發信道，錯誤圖樣中，第一個“1”和最后一個“1”之間的碼元總個數稱為突發長度，其圖樣稱為突發圖樣。該例中，突發圖樣是（11011），突發長度為5。6.2錯誤類型與信道模型2023/2/8226.3差錯控制的基本方式反饋重傳方式前向糾錯方式混合方式2023/2/8236.3差錯控制的基本方式反饋重傳方式(AutomaticRepeatreQuest,ARQ)工作原理：發送端發送的是檢錯碼，通過信道傳輸到接收端，接收端譯碼器只需根據編碼規則判斷是否有錯誤，并把判決信號通過反饋信道送回發送端。發送端根據判決信號將收端認為有錯誤的重新發送，直到接收端檢查無誤為止。2023/2/8256.3差錯控制的基本方式前向糾錯方式(ForwardErrorCorrection,FEC)工作原理：發送端發送能糾正錯誤的碼字，在接收端根據接收到的碼字和編碼規則，能自動糾正傳輸中的錯誤。不需要反饋信道，實時性好。隨著糾錯能力的提高，編譯碼設備復雜。2023/2/8266.3差錯控制的基本方式混合方式(HybridErrorCorrection,HEC)工作原理：結合前向糾錯和ARQ的系統，在糾錯能力范圍內，自動糾正錯誤，超出糾錯范圍則要求發送端重新發送。——折衷方案。2023/2/8296.4信道編碼的分類按信息碼元在編碼后是否保持原來的形式：系統碼、非系統碼按糾正錯誤的類型：糾正隨機錯誤的碼、糾正突發錯誤的碼按每個碼元取值：二進制碼、多進制碼2023/2/8306.4信道編碼的分類2023/2/8316.5信道編碼定理香農信道編碼定理性能指標分組碼及相關基本概念2023/2/8326.5信道編碼定理香農信道編碼定理

對于一個給定的有擾信道，若信道的容量為C，只要發送端以低于C的速率發送信息，則一定存在一種編碼方法，使譯碼錯誤概率P隨著碼長n的增加，按指數下降到任意小的值，表示為 這里E(R)稱為可靠性函數。2023/2/8336.5信道編碼定理定理告訴我們：當信息速率小于信道容量時，總存在一種編碼方式使差錯率低于任一給定值ε；為減小差錯概率，可增大碼長n或增大E(R)

增大E(R)可：可以增大信道容量；（增大帶寬、增大功率、降低噪聲）減小碼率；2023/2/8346.6線性分組碼分組碼及參數分組碼：將信息序列分成k位一組，按照一定的校驗關系增加r位校驗位，構成n(n=k+r)位碼分組，稱為碼字（Codewords)，所有可能碼字構成的集合稱為一個分組碼，記為(n,k)分組碼分組碼的校驗關系僅限于一個碼分組之內2023/2/8356.6線性分組碼分組碼及參數主要參數：信息分組：m=(mk-1mk-2

…m1m0)碼字：C=(cn-1cn-2

…c1c0)碼長n，信息位個數k，校驗位個數r=n-k碼字個數(二進制)：2k編碼效率：R=k/n2023/2/8366.6線性分組碼許用碼組、禁用碼組（n，k）碼中有2k個n重碼字。但是nbit的二進制序列具有2n種不同的組合序列；分組碼的編碼規則就是從2n種不同序列中選擇2k個碼字，建立信息序列與碼字的對應關系；這2k個碼字組成的集合稱為許用碼組，剩余的2n-2k個n重向量組成的集合稱為禁用碼組。2023/2/8376.6分組碼基本概念碼重、碼距碼重：碼字中非0碼元的個數，又稱漢明重量。例如碼字x=(11000)，則碼重w(x)=2

碼距：碼字x與碼字y對應位取值不同的個數，又稱為漢明距離。例如：x=(10111101)，y=(01110101)2023/2/8386.6分組碼的基本概念最小碼距（最小漢明距離）最小碼距：（n，k）分組碼中，任何兩個碼字之間距離的最小值，稱為該分組碼的最小漢明距離，簡稱最小距離，用d表示。最小碼距描述分組碼特性的重要參量，決定了碼的糾錯、檢錯性能。(n,k)分組碼通常也記為(n,k,d)分組碼。2023/2/8396.6分組碼的基本概念最小碼距（最小漢明距離）[例]：

(2,1)重復碼，{00,11}d=？

(3,1)重復碼，{000,111} d=？

(4,1)重復碼，{0000,1111} d=？2023/2/8406.6分組碼的基本概念最小漢明距離譯碼準則：在許用碼組中，判斷與接收序列r“最近”的碼字為發送碼字2023/2/841分組碼的檢糾錯能力分組碼的檢糾錯能力碼的最小距離為d0=

e+1，其檢錯能力為e。2023/2/842分組碼的檢糾錯能力分組碼的檢糾錯能力糾錯能力：一個(n,k)分組碼，如果能糾正碼字內的所有小于或等于t個(位)錯誤，則稱該碼的糾錯能力為t2023/2/843分組碼的檢糾錯能力碼的最小距離為d0=

2t+1，其糾錯能力為t。且當d*=2t+1或d*=2t+2時，都不能糾正t+1個錯誤。2023/2/844分組碼的檢糾錯能力分組碼的檢糾錯能力同時糾檢錯能力：一(n,k)分組碼，如果能糾正碼字內的所有小于或等于t個(位)錯誤，同時又能檢出所有小于或等于e(e>t)個(位)錯誤，則稱該碼的同時糾檢錯能力為糾t個錯同時檢e個錯。

2023/2/845分組碼的檢糾錯能力碼最小碼距d0=e+t+1，其中e>t，該碼能夠糾正t個錯誤，同時檢測e個錯誤。2023/2/8466.7幾種常用的編碼方式奇偶校驗(監督)碼水平一致監督碼水平垂直一致監督碼群計數碼恒比碼（等重碼）2023/2/8476.7幾種常用的編碼方式奇偶校驗碼是(n,n-1)碼。假設奇偶校驗碼的碼字表示為偶校驗碼：加入監督位后，碼字中“1”的個數為偶數個，即所有位的模二和為0。（即偶數個1）2023/2/8486.7幾種常用的編碼方式奇偶監督（校驗）碼奇校驗碼：加入監督位后碼字中“1”的個數為奇數個，即所有位的模二和為1。（即奇數個1）可以檢測任意奇數個錯誤；構造簡單，易于實現，在計算機內部數據傳送和輸入輸出設備中經常使用。2023/2/8496.7幾種常用的編碼方式水平一致監督碼將原信息序列以適當長度排成一行，如每k位信息為一行，設共有m行。對每行進行偶（奇）校驗經，構成(m(k+1),mk)分組碼傳輸時按列傳輸；譯碼時排成表，檢驗每行的校驗關系2023/2/8506.7幾種常用的編碼方式水平一致監督碼可以發現所有長度b≤m的單個突發錯誤2023/2/8516.7幾種常用的編碼方式水平垂直一致監督碼經奇偶校驗后的若干碼字排列成矩陣，每個碼字排成一行，然后再按列的方向增加垂直校驗位，就構成了二維奇偶校驗碼((m(k+1)+k,mk)傳輸時可以按行傳輸，也可以按列傳輸。2023/2/8526.7幾種常用的編碼方式水平垂直一致監督碼2023/2/8536.7幾種常用的編碼方式水平垂直一致監督碼糾檢錯能力強：可檢測每一行中奇數個錯和每一列中奇數個錯；二維奇偶碼適用于檢測突發錯誤。如果采用按照列的順序傳輸，可以發現長度t≤m+2的突發錯；如果按照行的順序傳輸，可以發現t≤k+2。應用于穿孔紙帶、磁帶記錄系統中。2023/2/8546.7幾種常用的編碼方式群計數碼將碼字中“1”的計數值作為監督碼元例如，信息組為01011，共3個1，用011表示，得到(8,5)碼。群計數碼的碼字為01011011檢錯能力很強，除了0錯成1和1錯成0成對發生的情況外，其它形式的錯誤都能發現。為了降低發送碼元中的冗余度，有時只傳送計數碼元中最后幾位。特別的只傳輸最后1位監督元，則群計數碼變成奇偶校驗碼2023/2/8556.7幾種常用的編碼方式恒比碼碼字中“1”和“0”的個數保持相同的比例，即每個碼字中1的個數相同。恒比碼的譯碼可以采用查表方法，檢錯時查1或0的個數。恒比碼是一種檢錯碼。恒比碼一般用在電報。2023/2/8566.7幾種常用的編碼方式恒比碼例：發漢字電報時，每個漢字用4位阿拉伯數字表示，每個阿拉伯數字用5個比特的碼字表示。由于阿拉伯數字只有10個，因此從32中可能的碼字中挑出=10個1的個數為3的碼字作為阿拉伯數字的編碼方式。阿拉伯數字編碼阿拉伯數字編碼1010116101012110017111003101108011104110109100115001110011012023/2/8576.8信道編碼理論的發展歷史1948年香農（Shannon）在其論文《通信中的數學理論》中提出有擾信道編碼定理——奠定了信道編碼的基石。50年代至60年代初，信道編碼從無到有得到了迅速的發展：奠定了線性分組碼的理論基礎；提出了著名的BCH碼編譯碼方法以及卷積碼的序列譯碼。2023/2/8586.8信道編碼理論的發展歷史60年代至70年代初，信道編碼發展最為活躍的時期：提出了門限譯碼、迭代譯碼、軟判決譯碼和維特比譯碼等有效的譯碼方法，并注重糾錯碼的實用化；在此期間以代數方法特別以有限域理論為基礎的線性分組碼理論趨于成熟。2023/2/85970年代至80年代，理論上，戈帕（Goppa）為首的一