第六章：信道編碼

信道編碼本章節(jié)達到的目的理解信道編碼在通信系統(tǒng)中的作用了解信道編碼的的基本分類了解信道編碼性能評價的基本方法了解漢明碼的編譯碼原理了解信道容量/容量代價函數(shù)在信道編碼定理中的作用理解香農第二定理又稱有噪信道編碼定理的物理意義了解信道編碼理論與實際應用的差距本章研究內容信道編碼概述錯誤概率與譯碼準則、編碼方法信道編碼定理與聯(lián)合典型序列信道編碼的性能界限信道編碼舉例－漢明碼關于信道編碼理論的若干評注§6.1:信道編碼概述問題引出什么是信道編碼信道編碼的作用信道編碼的三種情形信道編碼的實質§6.1:信道編碼概述－問題引出互信息能告訴我們什么？隨機變量X,Y統(tǒng)計意義上的依存程度可以獲得的信息量不能：所得信息能否可靠地確定信道輸入？無噪信道編碼能告訴我們什么？無噪無損信道，只要對信源輸出進行適當編碼，總能以最大信息傳輸率，無差錯的傳輸信息。但是：一般信道總存在噪聲或干擾，信息傳輸會造成損失實際通信中人們對傳輸要求什么？傳輸信息量大傳輸可靠提出的與信道傳輸有關的問題：如何能使信息傳輸后發(fā)生的錯誤最少？錯誤概率與那些因素有關？有無辦法控制？能控制到什么程度？無誤傳輸可達的最大信息率是多少？§6.1:信道編碼概述－什么是信道編碼通信系統(tǒng)模型信道編碼：從消息到信道波形或矢量的映射

希望通信系統(tǒng)與信道統(tǒng)計特性相匹配的編碼§6.1:信道編碼概述－什么是信道編碼復接、代數(shù)編碼、調制、成形濾波、擴頻、上下變頻等等都屬于廣義的信道編碼范疇注意：信道譯碼可以不是離散信道譯碼。只有當解調為硬判決輸出時才是離散信道和離散信道譯碼§6.1:信道編碼概述－信道編碼的作用信道編碼的作用：在資源、可靠性和傳信量之間選擇一個好的工作點（有時還要考慮延時）。資源指的提供信息傳輸所付出的代價包括頻率、時間、空間、功率等等。但不包括實現(xiàn)復雜度一個好的編碼就是要充分利用資源，傳遞盡可能多的信息§6.1:信道編碼概述－三種情形：給定資源和可靠性要求，通過信道編碼盡量提高傳輸速率（例：多電平編碼）給定對信息傳輸?shù)乃俾屎涂煽啃砸?，通過信道編碼盡量減少資源開銷（例：擾亂編碼）給定資源和傳輸速率，通過編碼提高可靠性（例：檢、糾錯編碼）§6.1:信道編碼概述－編碼的實質

利用冗余降低差錯概率將所有可能的輸入信息（消息）映射到信道符號（波形）空間的點，而這個點的集合要小于（包含于）全信道空間中?！?.1:信道編碼概述－信道編碼的基本分類

按碼的結構分:線性碼線性分組碼（群碼）卷積碼（線性樹碼）非線性碼按抗干擾模式分抗隨機差錯碼抗突發(fā)差錯碼按編譯碼理論所用數(shù)學工具分代數(shù)碼幾何碼組合碼按對錯誤的處理方式分檢錯碼糾錯碼§6.2:錯誤概率與譯碼準則、編碼方法－1錯誤概率與譯碼規(guī)則錯誤概率Pe與什么有關信道的統(tǒng)計特性譯碼規(guī)則譯碼規(guī)則的選擇依據(jù)最大后驗概率準則－－理想最大似然準則－－實用編碼譯碼§6.2:錯誤概率與譯碼準則、編碼方法－2信道譯碼An1243w4w3w1w2xxxAn

是接收空間w1,w2,…

是發(fā)送的碼子圍繞每個碼子有一個譯碼域i如果接收的碼子在i中，就認為發(fā)送的是碼子

wi

發(fā)生錯誤一般,An中存在一些不屬于任何

i的區(qū)域

有時接收碼子會被映射到錯誤的i，進而被譯成錯誤的

wi

正確譯碼不知如何譯碼譯碼錯誤§6.2:錯誤概率與譯碼準則、編碼方法－3

問題：在輸入和信道特性給定的條件下，差錯概率將取決于接收矢量空間按什么樣的劃分準則進行劃分劃分接收矢量空間的準則－－譯碼器的譯碼準則§6.2:錯誤概率與譯碼準則、編碼方法－4

§6.2:錯誤概率與譯碼準則、編碼方法－5

準則一：平均錯誤概率最小譯碼準則計算平均錯誤概率：YX若碼字Xm經(jīng)傳輸后在接收端所得的接收矢量不落在Ym子集中，則譯碼發(fā)生錯誤其中：§6.2:錯誤概率與譯碼準則、編碼方法－6

§6.2:錯誤概率與譯碼準則、編碼方法－7理想的譯碼器應使平均譯碼差錯概率最小是譯碼正確的概率，則譯碼發(fā)生錯誤的概率為：譯碼器平均的譯碼差錯概率為：§6.2:錯誤概率與譯碼準則、編碼方法－8最小錯誤概率準則（最大后驗概率準則）：特點：優(yōu)點：理想缺點：1、后驗概率不易得到2、后驗概率依賴于輸入分布§6.2:錯誤概率與譯碼準則、編碼方法－9準則二：最大似然譯碼準則此時譯碼差錯概率為：平均的譯碼差錯概率為：§6.2:錯誤概率與譯碼準則、編碼方法－10最大后驗概率譯碼準則&最大似然譯碼準則輸入等概時－－二者是一致的此時：§6.2:錯誤概率與譯碼準則、編碼方法－11錯誤概率與編碼如何在信息傳輸率一定的前提下使Pe0實際經(jīng)驗：重復發(fā)送可以使Pe減小重復次數(shù)N很大時，可以使Pe0但：信息傳輸率降低信道編碼定理：R一定時，可以找到一種編碼方法使Pe相當?shù)鸵敫拍睿捍a字距離§6.2:錯誤概率與譯碼準則、編碼方法－12碼字距離－漢明距離長度為n的兩個符號序列(碼字)αi和βj之間的距離是指αi和βj之間對應位置上不同碼元的個數(shù)，用符號D(αi,βj)表示。這種碼字距離通常稱為漢明距離。例如：兩個二元序列αi=101111βj=111100則得D(αi,βj)=3又例如：兩個四元序列αi=1320120βj=1220310則得D(αi，βj)＝３?！?.2:錯誤概率與譯碼準則、編碼方法－13對于二元信道，即對于二元碼，漢明距離可表達成下述關系式：若令αi＝（ａi1ａi２…ａin）ａik∈｛0,1｝βj＝（bj1bj2…bjn）βjk∈｛0,1｝則αi和βj的漢明距離為D(αi，βj)＝在某一碼書C中，任意兩個碼字的漢明距離的最小值稱為該碼C的最小距離，即dmin＝min｛D(Ci,Cj)｝Ci≠CjCi,Cj∈C在任一碼書中，碼的最小距離dmin與該碼的譯碼錯誤概率有關?！?.2:錯誤概率與譯碼準則、編碼方法－14與碼字距離有關的結論最小距離譯碼準則在二進制對稱信道中：最小距離譯碼準則＝最大似然譯碼準則§6.3:信道編碼定理與聯(lián)合典型序列-1信道編碼定理引出問題：在有噪信道中，使平均誤碼率Pe盡可能小的情況下，可達到的信息傳輸率是多少？答案：信道容量C信道編碼定理信道編碼定理的證明證明思路隨機編碼方法聯(lián)合典型序列§6.3:信道編碼定理與聯(lián)合典型序列-2信道編碼定理：設R是信息傳輸?shù)乃俾?，C是離散無記憶信道的信道容量，ε>0是任意小的數(shù)，則只要R<C就總存在碼字長為N，碼字數(shù)為M=2NR的分組碼使譯碼的平均差錯概率Pe<ε?！?.3:信道編碼定理與聯(lián)合典型序列-3信道編碼定理的證明思路：通常思路：先構造一個理想的好碼，并定義一種譯碼準則，計算該好碼經(jīng)過譯碼后的誤碼率問題：構建極其復雜且無具體方法N值很大時，誤碼率計算困難香農采取的方法:用隨機編碼方法得到所有可能碼的集合在其中隨機選擇一個碼作為信道碼利用大數(shù)定理計算在集合平均意義上的該碼性能利用聯(lián)合典型序列譯碼香農采取的方法評價：不很嚴格，不是最優(yōu)，但便于理論分析隨機編碼方法在后來嚴格的證明中一直被采用§6.3:信道編碼定理與聯(lián)合典型序列-4隨機編碼方法：對每一個消息m,(m=0,1,…M-1),編碼為xm=(xm1xm2…xmn)其中：xmi(i=1,2,…n)是按照輸入字母的概率隨機選取，從而得到全部M=2NR個碼字，組成碼集C＝（x1x2….xM-1)隨機編碼方法產(chǎn)生某一特定碼字的概率P(Xm)是：§6.3:信道編碼定理與聯(lián)合典型序列-5聯(lián)合ε典型序列ε典型序列：信源輸出的隨機序列－奠定了信源編碼的基礎聯(lián)合ε典型序列：兩個隨機變量的自然擴展，是信道編碼的基礎

聯(lián)合ε典型序列定義：聯(lián)合AEP定理定理解釋：

§6.3:信道編碼定理與聯(lián)合典型序列-6聯(lián)合ε典型序列定義：設（X,Y）是長為N的隨機序列對，則在這些隨機序列對中滿足下列條件的序列對被稱為聯(lián)合典型序列式中δ是任意小的數(shù)，聯(lián)合典型序列的全體構成聯(lián)合典型序列集，記做G§6.3:信道編碼定理與聯(lián)合典型序列-7聯(lián)合AEP定理：設隨機序列對（X,Y)的，則對任意小的數(shù)δ>0，我們總能找到足夠大的N使全體序列對的集合能被分成滿足下述條件的集合G及其補集Gc：（1）（2）（3）設（X’，Y’）是相互獨立的隨機序列對，但它與（X,Y）有相同的邊緣分布，即：則：§6.3:信道編碼定理與聯(lián)合典型序列-8聯(lián)合AEP定理的解釋：兩個隨機變量情況下，序列Xn,Yn及其聯(lián)合序列XnYn都具有AEP特性聯(lián)合典型序列對是高概率序列對聯(lián)合典型序列對出現(xiàn)概率接近相等，且其和接近于1聯(lián)合典型序列對是一些密切關聯(lián)的序列對一般與X對應的Y可能是Y空間的任一個，該定理說明：隨N的增大，對應X的Y只能是（X,Y)典型序列對的Y，取其他Y的概率0聯(lián)合典型序列數(shù)目為2NH(XY)，典型x,典型Y隨機組合的空間為2N[H(X)+H(Y)]，聯(lián)合典型序列占其中約1/2NI(X;Y)，只是很小的一部分故：當X的數(shù)目<2NI(X;Y)時，，可使Pe0給出一種譯碼方法：譯碼時，取與接收矢量聯(lián)合典型的碼字作為輸出，這種譯碼方法可以保證得到很低的誤碼率。InputsequenceOutputsequence………………ywiwi+12nH(XY)

sequencesthatcanmaptoy

M=2nR

codewords§6.3:信道編碼定理與聯(lián)合典型序列-9信道編碼定理證明的幾點說明香農只是證明了碼的存在性，未給出構造方法隨機編碼所得的碼集很大，通過搜索得到好碼的方法實際上很難實現(xiàn)；而且即使找到，碼字也是毫無結構的，只能采用查表譯碼方法，當N很大時，碼表的存儲量也很難接受§6.4:信道編碼的性能界限－1理論性能極限－－存在性香農信道編碼定理作用：理論極限、漸進性能工程實現(xiàn)上的界限－－構造性最小距離界限作用：構造新碼、估計新碼性能時，說明新碼與最好性能的碼接近的程度香農理論極限：R<C；存在編譯碼方法使Pe0給定Pe；存在編譯碼方法使RC

－1.59dB§6.4:信道編碼的性能界限－2實際信道編碼理論研究內容：最佳碼性能有多好？如何設計好碼？如何譯碼？最小距離限在碼長和最小距離給定時，具有最大可能的碼字數(shù)A(n,dmin)的碼為好碼。完備碼A(n,dmin)的上下限近半個世紀以來，上限不斷改進，并逐步向下限靠近，但下限保持不變未證明的看法：上下限會逐步會合成為一條限?！?.5:信道編碼舉例－漢明碼－1漢明碼的編碼漢明碼的譯碼§6.5:信道編碼舉例－漢明碼－2漢明碼第一個具有系統(tǒng)的編譯碼方法的信道碼（7，4）漢明碼碼長n=7,信息元k=4，檢驗元r=n-k=3。長為3的二元序列共有23＝８個。我們將其中7個非全零序列按列排成如下矩陣H矩陣稱為：一致監(jiān)督矩陣。§6.5:信道編碼舉例－漢明碼－3設碼字C=（c6c5c4c3c2c1c0),有：H×CT=0T其中：0＝（000），0T是0矢量的轉置，即滿足：c3+c2+c1+c0=0c5+c4+c1+c0=0c6+c4+c2+c0=00000000010010110000111100110000111101010101001100110100100101100110011101010111100000011001011110010110101111111§6.5:信道編碼舉例－漢明碼－4給出生成矩陣滿足：§6.5:信道編碼舉例－漢明碼－5（7，4）漢明碼特點：16個碼字是所有碼長為7的二元序列中的一個封閉子集。碼的最小距離等于非零碼字的最小重量＝3能檢2個錯，糾一個錯。d>=s+1（檢錯時）d>=2s+1（糾錯時）§6.5:信道編碼舉例－漢明碼－6漢明碼譯碼：伴隨式譯碼錯誤圖樣ER=C+E伴隨式S伴隨式錯誤圖樣假設接收到碼矢y=(0010010)有7個可能的錯誤位置,如Z矩陣所示伴隨式是