第六章：信道編碼

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

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

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

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

是接收空間w1,w2,…

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

wi

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

i的區(qū)域

有時(shí)接收碼子會(huì)被映射到錯(cuò)誤的i，進(jìn)而被譯成錯(cuò)誤的

wi

正確譯碼不知如何譯碼譯碼錯(cuò)誤§6.2:錯(cuò)誤概率與譯碼準(zhǔn)則、編碼方法－3

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

§6.2:錯(cuò)誤概率與譯碼準(zhǔn)則、編碼方法－5

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

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

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

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

sequencesthatcanmaptoy

M=2nR

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

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