《信息論基礎教程》第二版PPT課件

《信息論基礎教程》第二版PPT課件,信息論基礎教程,信息論,基礎教程,第二,PPT,課件 第六章：有噪信道編碼一、信道編碼的相關概念一、信道編碼的相關概念二、有噪信道編碼定理二、有噪信道編碼定理三、糾錯編碼三、糾錯編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼l信道編碼的目標目標：提高通信的可靠性。1.信道編碼概述l信道編碼信道編碼，就是按照一定的規(guī)則給信源編碼后的碼符號序列增加一些冗余信息，使其變成具有一定數學規(guī)律的碼符號序列。l信道譯碼信道譯碼，就是按與信道編碼器相同的數學規(guī)律去掉接收到的碼符號序列中的冗余符號。l通常來說，增加的冗余符號越多，檢錯和糾錯能力就越強。但是，增加的冗余符號越多，傳輸效率就越低。信道編碼的相關概念信道編碼的相關概念l信道編碼器：信道編碼器：將信源編碼后的符號加上冗余符號，提高傳輸的可靠性。將信源編碼后的符號加上冗余符號，提高傳輸的可靠性。第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼1.信道編碼概述（續(xù)1）信道編碼的相關概念信道編碼的相關概念第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼1.信道編碼概述（續(xù)2）信道編碼的相關概念信道編碼的相關概念圖1編碼信道模型信道編碼器信道譯碼器信道第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼2.譯碼規(guī)則對錯誤概率的影響例例1 1：二進制對稱信道二進制對稱信道0101信道編碼的相關概念信道編碼的相關概念第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼2.譯碼規(guī)則對錯誤概率的影響（續(xù)1）譯碼規(guī)則1：信道譯碼器收到符號“0”譯為“0”信道譯碼器收到符號“1”譯為“1”正確譯碼概率0.1，錯誤譯碼概率信道編碼的相關概念信道編碼的相關概念0101第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼2.譯碼規(guī)則對錯誤概率的影響（續(xù)2）譯碼規(guī)則2：信道譯碼器收到符號“0”譯為“1”信道譯碼器收到符號“1”譯為“0”信道編碼的相關概念信道編碼的相關概念正確譯碼概率0.9，錯誤譯碼概率第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼定義6.1設信道的輸入符號集為，輸出符號集為。若對每一個輸出符號都有一個確定的函數，使對應于唯一的一個輸入符號，則稱這樣的一個函數為譯碼規(guī)則譯碼規(guī)則，記為3.譯碼規(guī)則XYx1x2xry1y2ysp(yj|xi)信道編碼的相關概念信道編碼的相關概念第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼3.譯碼規(guī)則（續(xù)1）信道共有rs 種譯碼規(guī)則信道編碼的相關概念信道編碼的相關概念譯碼規(guī)則例：01013.譯碼規(guī)則（續(xù)2）第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼3.譯碼規(guī)則（續(xù)3）例2：設一個信道的信道矩陣為，根據此信道矩陣，設計譯碼規(guī)則。解：譯碼規(guī)則A譯碼規(guī)則B信道編碼的相關概念信道編碼的相關概念對于有r個輸入符號，s個輸出符號的信道，總共可以設計出種譯碼規(guī)則，到底哪一種譯碼規(guī)則最好哪一種譯碼規(guī)則最好？依據什么標準什么標準來選擇譯碼規(guī)則？問題：3.譯碼規(guī)則（續(xù)4）第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念4.錯誤譯碼概率l設譯碼規(guī)則為當輸入符號是xi時，譯碼正確當輸入符號為除xi以外的(r-1)種符號時，譯碼錯誤正確譯碼的概率：錯誤譯碼的概率：第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念4.錯誤譯碼概率（續(xù)1）l平均正確譯碼概率：l平均錯誤譯碼概率：第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念5.兩種重要的譯碼規(guī)則為提高規(guī)則通信的可靠性，所采用的譯碼應當使平均錯誤譯碼概率最小。-最大后驗概率譯碼規(guī)則最大后驗概率譯碼規(guī)則最常用的譯碼規(guī)則，包括：極大似然譯碼規(guī)則極大似然譯碼規(guī)則最大后驗概率譯碼規(guī)則最大后驗概率譯碼規(guī)則第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念5.兩種重要的譯碼規(guī)則（續(xù)1）(1 1)最大后驗概率譯碼規(guī)則最大后驗概率譯碼規(guī)則已知：當求和項中的每一項都達到最小值時，就最小。要最小。要最大。第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念定義6.2令，而應滿足條件5.兩種重要的譯碼規(guī)則（續(xù)2）稱滿足上述條件的譯碼函數對應的譯碼規(guī)則為最大后驗最大后驗概率譯碼規(guī)則概率譯碼規(guī)則。第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念5.兩種重要的譯碼規(guī)則（續(xù)3）第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念5.兩種重要的譯碼規(guī)則（續(xù)4）第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念5.兩種重要的譯碼規(guī)則（續(xù)5）問題：最大后驗概率通常是未知的，使用不方便。我們能否推導出更便于使用的譯碼規(guī)則?第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念5.兩種重要的譯碼規(guī)則（續(xù)6）當輸入符號等概分布時當輸入符號等概分布時(2 2)極大似然譯碼規(guī)則極大似然譯碼規(guī)則第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼5.兩種重要的譯碼規(guī)則（續(xù)7）1)當輸入符號等概分布時，采用極大似然譯碼準則等價于最大后驗概率準則。2)當輸入符號不等概分布或先驗概率未知時，采用極大似然譯碼準則不一定使 最小。l 關于極大似然譯碼準則極大似然譯碼準則：第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念5.兩種重要的譯碼規(guī)則（續(xù)8）當輸入符號等概分布時當輸入符號等概分布時第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念5.兩種重要的譯碼規(guī)則（續(xù)9）例3：設信道矩陣為，且輸入符號等概分布，即，求譯碼規(guī)則和平均錯誤譯碼概率。第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念5.兩種重要的譯碼規(guī)則（續(xù)10）解：因為輸入符號為等概分布，所以由最大似然譯碼規(guī)則可得譯碼規(guī)則第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念5.兩種重要的譯碼規(guī)則（續(xù)11）譯碼規(guī)則A譯碼規(guī)則B例6.3假設輸入等概，求以下兩種譯碼規(guī)則的平均錯誤譯碼概率。第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念5.兩種重要的譯碼規(guī)則（續(xù)12）第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念5.兩種重要的譯碼規(guī)則（續(xù)13）第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念5.兩種重要的譯碼規(guī)則（續(xù)14）第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念6.Fano不等式l定理定理6.1平均錯誤概率與信道疑義度H(X|Y)滿足不等式：第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念01017.簡單重復編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念7.簡單重復編碼（續(xù)1）二元對稱信道的三次擴展信道M=2第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念由最大似然譯碼規(guī)則，可得7.簡單重復編碼（續(xù)2）自動糾正一位錯第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念7.簡單重復編碼（續(xù)3）l在輸入符號集（M個符號）等概的條件下，每個符號平均攜帶的最大信息量是。l當用n個碼元符號來傳輸M個信源符號時，每個碼符號攜帶的平均信息量，即信道信息傳輸率為：l不重復編碼時(n=1)，l重復編碼時(n=3)，第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念n=1,R=1,n=3,R=1/3,n=5,R=1/5,n=7,R=1/7,n=9,R=1/9,n=11,R=1/11,增加重復次數n，可使減小很多，但信息傳輸率R也減少很多。7.簡單重復編碼（續(xù)4）第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念7.簡單重復編碼（續(xù)5）第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念l如果在擴展信源的如果在擴展信源的 個碼符號序列中任意選擇個碼符號序列中任意選擇M個序個序列作為列作為信道的輸入，以代表信道的輸入，以代表M個信源消息個信源消息。l 因此若選擇因此若選擇“000”000”和和“001”001”代表消息代表消息“0”0”和和“1”1”，則，則 7.簡單重復編碼（續(xù)6）第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念l有有沒沒有有一一種種很很簡簡便便的的方方法法，幫幫我我們們選選擇擇平平均均錯錯誤誤概概率最小的率最小的M個序列？個序列？7.簡單重復編碼（續(xù)7）第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念8.漢明距離1）漢明距離2）碼的最小距離3）漢明距離與極大似然譯碼準則第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念8.漢明距離（續(xù)1）定義6.4設和表示兩個長度為n的碼符號序列，定義稱為碼字和之間的漢明距離。1）漢明距離）漢明距離第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念8.漢明距離（續(xù)2）例4：求下面兩個碼字之間的漢明距離。解：第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念8.漢明距離（續(xù)3）定義6.5在二元碼C中，任意兩個碼字之間的漢明距離的最小值，被稱為碼C的最小距離：2）碼的最小距離）碼的最小距離第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念8.漢明距離（續(xù)4）例5：設有n=3的兩組碼，分別求它們的最小漢明距離。解：碼的最小漢明距離為碼的最小漢明距離為第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念碼1碼2碼3碼4碼5碼600011100000100001110111000000110001000000011011011111010000001010011100101110111第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念8.漢明距離（續(xù)5）碼1碼2碼3碼4碼5碼字00011100001110111000000110001000000011011011111010000001010011100101110111消 息 數M24448信 息 傳輸率R1/32/32/32/51碼的最小距離32131平均錯誤概率（最大似然譯碼）8.漢明距離（續(xù)7）結論：碼的最小距離越大，平均譯碼錯誤概率越小。第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念設和表示兩個長度為n的碼符號序列，為信道的輸入，為信道的輸出。和的漢明距離為D。8.漢明距離（續(xù)8）3)漢明距離與極大似然譯碼準則漢明距離與極大似然譯碼準則對于離散平穩(wěn)無記憶二元對稱信道，有第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念通常情況下，D越小，就越大。8.漢明距離（續(xù)9）根據極大似然譯碼準則，極大似然譯碼準則就等價于，當接收到一個長為n的碼符號序列時，在輸入碼字集中尋找一個，使第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼信道編碼的相關概念信道編碼的相關概念最小距離譯碼準則最小距離譯碼準則1.有噪信道編碼定理定理6.2（香農第二定理）設有一離散無記憶平穩(wěn)信道，其信道容量為C，只要待傳送的信息傳輸率RC，即，則無論碼長n 取多大，也不可能使譯碼錯誤概率任意小。第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼有噪信道編碼定理有噪信道編碼定理1.有噪信道編碼定理（續(xù)3）信道容量是在信道中可靠傳輸信息的最大信息傳信道容量是在信道中可靠傳輸信息的最大信息傳輸率。輸率。結論：結論：第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼有噪信道編碼定理有噪信道編碼定理2.錯誤概率的上界第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼第六章：有噪信道編碼有噪信道編碼定理有噪信道編碼定理糾錯編碼糾錯編碼1 1 糾錯碼的分類糾錯碼的分類2 2 糾錯碼的基本概念糾錯碼的基本概念 3 3 線性分組碼線性分組碼 4 4 漢明碼漢明碼 5 5 循環(huán)碼循環(huán)碼*6 6 卷積碼卷積碼概述概述l 香農第二定理證明，當香農第二定理證明，當 時時 的碼存在。的碼存在。l 證明過程采用的是隨機編碼的方法：證明過程采用的是隨機編碼的方法：隨機編碼所得的碼集很大，通過搜索得到好碼的方法在實隨機編碼所得的碼集很大，通過搜索得到好碼的方法在實際上很難實現；際上很難實現；即使找到了好碼，這種碼的碼字也沒有規(guī)律，不便于譯碼。即使找到了好碼，這種碼的碼字也沒有規(guī)律，不便于譯碼。l 真正實用的信道編碼方法還需要通過各種數學工具真正實用的信道編碼方法還需要通過各種數學工具來構造，使碼具有好的結構性以便于譯碼。來構造，使碼具有好的結構性以便于譯碼。l 近世代數是信道編碼理論用到的最重要的數學工具，近世代數是信道編碼理論用到的最重要的數學工具，它包括群論、環(huán)論、域論、格論、線性代數等許多分支。它包括群論、環(huán)論、域論、格論、線性代數等許多分支。l 廣義信道編碼廣義信道編碼包括：調制、成形濾波、擴頻、上下包括：調制、成形濾波、擴頻、上下變頻等。變頻等。l 糾錯編碼是提高傳輸可靠性的最主要的措施之一。糾錯編碼是提高傳輸可靠性的最主要的措施之一。概述概述l 糾錯編碼的糾錯編碼的基本思路基本思路：根據一定的規(guī)律在待發(fā)送的信息碼元中人為的加根據一定的規(guī)律在待發(fā)送的信息碼元中人為的加入一些冗余碼元，入一些冗余碼元，這些這些冗余冗余碼元與信息碼元之間以某碼元與信息碼元之間以某種確定的規(guī)則相互關聯（約束）。種確定的規(guī)則相互關聯（約束）。在接收端按照既定的規(guī)則檢驗信息碼元與監(jiān)督碼在接收端按照既定的規(guī)則檢驗信息碼元與監(jiān)督碼元之間的關系。如果傳輸過程出錯，則信息碼元與監(jiān)元之間的關系。如果傳輸過程出錯，則信息碼元與監(jiān)督碼元之間的關系將受到破壞，從而可以發(fā)現錯誤乃督碼元之間的關系將受到破壞，從而可以發(fā)現錯誤乃至糾正錯誤。至糾正錯誤。概述概述E概述概述mmsgCcodeRnoisycodenewmsg干擾一般分為兩種形式：干擾一般分為兩種形式：一是隨機噪聲，它主要來源于設備的熱噪聲和散彈一是隨機噪聲，它主要來源于設備的熱噪聲和散彈噪聲以及傳播媒介的熱噪聲，它是通信系統中的主噪聲以及傳播媒介的熱噪聲，它是通信系統中的主要噪聲；要噪聲；二是脈沖干擾和信道衰落，它的特點是突發(fā)出現，二是脈沖干擾和信道衰落，它的特點是突發(fā)出現，主要來源于雷電、通電開關、負荷突變或設備故障主要來源于雷電、通電開關、負荷突變或設備故障等。等。概述概述信道可分為三類：信道可分為三類：1.只只產產生生隨隨機機錯錯誤誤的的信信道道稱稱為為隨隨機機信信道道。比比如如衛(wèi)衛(wèi)星星信信道道、同軸電纜、光纜信道以及大多數微波中繼信道。同軸電纜、光纜信道以及大多數微波中繼信道。2.產產生生突突發(fā)發(fā)錯錯誤誤的的信信道道稱稱為為突突發(fā)發(fā)信信道道。實實際際的的短短波波信信道道、移移動動通通信信信信道道、由由于于擦擦傷傷造造成成成成串串差差錯錯的的光光盤盤和和磁磁盤盤，均均為這一類信道。為這一類信道。3.有些實際信道既有隨機錯誤又有突發(fā)錯誤，稱為混合有些實際信道既有隨機錯誤又有突發(fā)錯誤，稱為混合信道。信道。根據不同的信道類型設計的信道編碼分為糾隨機錯誤根據不同的信道類型設計的信道編碼分為糾隨機錯誤碼、糾突發(fā)錯誤碼和糾混合錯誤碼。碼、糾突發(fā)錯誤碼和糾混合錯誤碼。概述概述在通信系統中，糾檢錯的工作方式有：在通信系統中，糾檢錯的工作方式有：(1)反饋重傳反饋重傳(ARQ)(2)前向糾錯前向糾錯(FEC)(3)混合糾錯混合糾錯概述概述 發(fā)送端經編碼后發(fā)出能夠發(fā)現錯誤的碼，接收端收到后經發(fā)送端經編碼后發(fā)出能夠發(fā)現錯誤的碼，接收端收到后經檢驗，如果發(fā)現傳輸中有錯誤，則通過反饋系統把這一判斷結檢驗，如果發(fā)現傳輸中有錯誤，則通過反饋系統把這一判斷結果反饋回發(fā)端，然后發(fā)送端把前面發(fā)出的信息重新傳送一次，果反饋回發(fā)端，然后發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端認為正確地收到信息為止。直到接收端認為正確地收到信息為止。(1)反饋重傳反饋重傳(ARQ)檢錯檢錯編碼編碼信道信道檢錯檢錯譯碼譯碼反饋反饋概述概述(2)前向糾錯前向糾錯(FEC)糾錯糾錯編碼編碼信道信道糾錯糾錯譯碼譯碼 發(fā)送端發(fā)出的是具有糾錯能力的糾錯碼，接收端根據譯發(fā)送端發(fā)出的是具有糾錯能力的糾錯碼，接收端根據譯碼規(guī)則進行譯碼。當誤碼個數在碼的糾錯能力范圍內時，譯碼規(guī)則進行譯碼。當誤碼個數在碼的糾錯能力范圍內時，譯碼器可以自動糾正錯誤。碼器可以自動糾正錯誤。概述概述特點：特點：1 1）前向糾錯方式不需要反饋信道，特別適合于只能）前向糾錯方式不需要反饋信道，特別適合于只能 提供單向信道的場合。提供單向信道的場合。2 2）由于能自動糾錯，不要求檢錯重發(fā)，因而延時小，）由于能自動糾錯，不要求檢錯重發(fā)，因而延時小，實時性好。實時性好。3 3）隨著糾錯能力的增強，譯碼設備也變得復雜。）隨著糾錯能力的增強，譯碼設備也變得復雜。概述概述(3)混合糾錯混合糾錯 對發(fā)送端進行適當的編碼。當對發(fā)送端進行適當的編碼。當錯誤不嚴重錯誤不嚴重，在碼的，在碼的糾錯能力范圍之內時，采用自動糾錯；當產生的糾錯能力范圍之內時，采用自動糾錯；當產生的差錯超差錯超出碼的糾錯能力范圍出碼的糾錯能力范圍時，通過反饋系統要求發(fā)端重發(fā)。時，通過反饋系統要求發(fā)端重發(fā)。概述概述(1)按按功能功能分：分：檢錯碼：僅能檢測誤碼檢錯碼：僅能檢測誤碼糾錯碼：可糾正誤碼糾錯碼：可糾正誤碼 糾刪碼：兼糾錯和檢錯能力糾刪碼：兼糾錯和檢錯能力(2)按信息碼元與監(jiān)督碼元之間的按信息碼元與監(jiān)督碼元之間的檢驗關系檢驗關系分：分：線性碼：滿足線性關系線性碼：滿足線性關系 非線性碼：不存在線性關系非線性碼：不存在線性關系 糾錯碼糾錯碼1 1 糾錯碼的分類糾錯碼的分類(3)按信息碼元與監(jiān)督碼元之間的按信息碼元與監(jiān)督碼元之間的約束方式約束方式不同分：不同分：分組碼：本碼組的監(jiān)督碼元僅和本碼組的信息元相關。分組碼：本碼組的監(jiān)督碼元僅和本碼組的信息元相關。樹碼：本碼組的監(jiān)督碼元不僅和本碼組的信息元相關，樹碼：本碼組的監(jiān)督碼元不僅和本碼組的信息元相關，而且與前面碼組的信息碼元有關。如果是線性關系則稱而且與前面碼組的信息碼元有關。如果是線性關系則稱為卷積碼。為卷積碼。(4)按信息碼元在編碼后是否保持原形式不變：按信息碼元在編碼后是否保持原形式不變：系統碼：信息碼元與監(jiān)督碼元在分組內有確定位置，系統碼：信息碼元與監(jiān)督碼元在分組內有確定位置，編碼后的信息碼元保持不變；編碼后的信息碼元保持不變；非系統碼：信息位打亂，與編碼前不同。非系統碼：信息位打亂，與編碼前不同。1 1 糾錯碼的分類糾錯碼的分類(5)(5)按糾正差錯的類型可分為：按糾正差錯的類型可分為：糾糾隨機錯誤隨機錯誤碼碼糾糾突發(fā)錯誤突發(fā)錯誤碼碼糾糾隨機和突發(fā)錯誤隨機和突發(fā)錯誤碼碼1 1 糾錯碼的分類糾錯碼的分類糾錯碼按結構分類如下：糾錯碼按結構分類如下：1 1 糾錯碼的分類糾錯碼的分類l分組碼的表示方法：分組碼的表示方法：（二元分組碼）二元分組碼）信息碼組由信息碼組由k 個信息碼元（個信息碼元（信息位信息位）組成，共有組成，共有2k 個不同的信息碼組；個不同的信息碼組；附加附加 個校驗碼元（個校驗碼元（校驗位或監(jiān)督位校驗位或監(jiān)督位），每，每個校驗碼元是該信息碼組的某些信息碼元模個校驗碼元是該信息碼組的某些信息碼元模2和；和；編碼器輸出長度為編碼器輸出長度為n的碼字；的碼字；碼字的數目共有碼字的數目共有2k；這這2k個碼字的集合稱為個碼字的集合稱為(n,k)分組碼；分組碼；2 2 糾錯碼的基本概念糾錯碼的基本概念l對對二進制二進制(n,k)線性分組線性分組碼，合法碼字數為碼，合法碼字數為2k，可用，可用編碼空間的編碼空間的序列序列數為數為2n個。個。許用序列許用序列，禁用序列，禁用序列l(wèi)任一種任一種2k信息集合到二進制序列集合信息集合到二進制序列集合(2 2n n)的映射都是的映射都是一種一種(n,k)碼碼，因此總共可能的編碼方案有因此總共可能的編碼方案有種。種。2 2 糾錯碼的基本概念糾錯碼的基本概念l信息傳輸率（碼率）信息傳輸率（碼率）l編碼效率編碼效率l發(fā)現或構造好碼是信道編碼研究的主要問題。發(fā)現或構造好碼是信道編碼研究的主要問題。l線性分組碼線性分組碼是最具實用價值的一類碼，比如漢明碼、是最具實用價值的一類碼，比如漢明碼、循環(huán)碼、循環(huán)碼、BCH碼、碼、RS碼等。碼等。2 2 糾錯碼的基本概念糾錯碼的基本概念2 2 糾錯碼的基本概念糾錯碼的基本概念對信道編碼的一般要求是：對信道編碼的一般要求是：糾錯檢錯能力強；糾錯檢錯能力強；信息傳輸率高；信息傳輸率高；編碼規(guī)律簡單，實現設備簡單且費用合理；編碼規(guī)律簡單，實現設備簡單且費用合理；與信道的差錯統計特性相匹配。與信道的差錯統計特性相匹配。漢明距離漢明距離漢明距離滿足距離公理漢明距離滿足距離公理(1)非負性非負性(2)對稱性對稱性(3)(3)三角不等式三角不等式2 2 糾錯碼的基本概念糾錯碼的基本概念漢明重量漢明重量碼碼C的最小距離的最小距離線性分組碼的最小距離等于非零碼字的最小重量。線性分組碼的最小距離等于非零碼字的最小重量。2 2 糾錯碼的基本概念糾錯碼的基本概念碼1碼2碼3碼4碼5碼6000111000001000011101110000001100010000000110110111110100000010100111001011101112 2 糾錯碼的基本概念糾錯碼的基本概念3 3 線性分組碼線性分組碼3.1校驗矩陣與生成矩陣校驗矩陣與生成矩陣(1)校驗矩陣校驗矩陣3 3 線性分組碼線性分組碼l被稱為被稱為校驗矩陣校驗矩陣。l對對線性分組碼，校驗矩陣為線性分組碼，校驗矩陣為維矩陣。維矩陣。l對于系統碼，校驗矩陣可以表示為對于系統碼，校驗矩陣可以表示為其中為維矩陣，為維單位矩陣。3 3 線性分組碼線性分組碼由校驗方程，得到由校驗方程，得到(2)生成矩陣生成矩陣3 3 線性分組碼線性分組碼令令3 3 線性分組碼線性分組碼其中其中為為維矩陣，維矩陣，為為維單位矩陣。維單位矩陣。l被稱為被稱為生成矩陣生成矩陣。l對對線性分組碼，生成矩陣為線性分組碼，生成矩陣為維矩陣。維矩陣。l對于系統碼，生成矩陣可以表示為對于系統碼，生成矩陣可以表示為3 3 線性分組碼線性分組碼l把生成矩陣的每一行用一個行向量把生成矩陣的每一行用一個行向量來表來表示，則生成矩陣可以表示為示，則生成矩陣可以表示為l令令，則，則3 3 線性分組碼線性分組碼l由于生成矩陣由于生成矩陣G的每一行都是一個碼字，所以的每一行都是一個碼字，所以G 的每的每行都滿足行都滿足 ，則有則有l(wèi)對于標準形式的校驗矩陣和監(jiān)督矩陣，有對于標準形式的校驗矩陣和監(jiān)督矩陣，有(3)校驗矩陣和生成矩陣的關系校驗矩陣和生成矩陣的關系3 3 線性分組碼線性分組碼l線性分組碼的封閉性線性分組碼的封閉性：線性分組碼中任意兩個碼字之：線性分組碼中任意兩個碼字之和仍然是該碼的碼字。和仍然是該碼的碼字。證明：設證明：設 和和 分別是碼分別是碼 中的兩個碼字，因此有中的兩個碼字，因此有即即 滿足監(jiān)督方程，所以是碼滿足監(jiān)督方程，所以是碼 中的一個碼字。中的一個碼字。3 3 線性分組碼線性分組碼例例1：3重復碼是一個（重復碼是一個（3,1）線性分組碼。其生成矩陣為）線性分組碼。其生成矩陣為3 3 線性分組碼線性分組碼例例2：（：（4,3）偶校驗碼是一個（）偶校驗碼是一個（4,3）線性分組碼，其生）線性分組碼，其生成矩陣為成矩陣為3 3 線性分組碼線性分組碼例例3：已知生成矩陣為已知生成矩陣為求生成的線性分組碼及由求生成的線性分組碼及由H生成的線性生成的線性分組碼。分組碼。3 3 線性分組碼線性分組碼3 3 線性分組碼線性分組碼11111111111100111011100011101110101011001100000101110110111010101011010011001101100010000100111011100101100110100010101011110100010010100110011110001000100110001000100000000000Cm3 3 線性分組碼線性分組碼3.2線性分組碼的糾、檢錯能力線性分組碼的糾、檢錯能力對于一個二進制對稱信道，當輸入為對于一個二進制對稱信道，當輸入為2k個等可能的個等可能的n長碼長碼字，則最大后驗概率準則等效于最小漢明距離譯碼準則。字，則最大后驗概率準則等效于最小漢明距離譯碼準則。3 3 線性分組碼線性分組碼關于碼的最小距離與糾、檢錯能力的關系有以下結論：對關于碼的最小距離與糾、檢錯能力的關系有以下結論：對于于（n，k）線性分組碼，設線性分組碼，設為碼的最小距離則為碼的最小距離則（）這組碼有糾正（）這組碼有糾正u 個錯誤的充要條件是個錯誤的充要條件是uu2u+13 3 線性分組碼線性分組碼lll+1（）具有檢測（）具有檢測l個錯誤的充要條件是個錯誤的充要條件是3 3 線性分組碼線性分組碼ulu+l+1（）具有糾正（）具有糾正u 個錯誤，同時可以發(fā)現個錯誤，同時可以發(fā)現l個錯誤的充分個錯誤的充分必要條件為必要條件為3 3 線性分組碼線性分組碼碼的糾錯能力碼的糾錯能力u與碼字的長度與碼字的長度n和消息數和消息數M滿足以下關系：滿足以下關系：3 3 線性分組碼線性分組碼3.3校驗矩陣與碼的最小距離的關系校驗矩陣與碼的最小距離的關系對于（對于（n，k）線性分組碼：線性分組碼：校驗矩陣校驗矩陣H中的任意中的任意t列線性無關而列線性無關而t+1列線列線性相關，則碼的最小距離性相關，則碼的最小距離(碼字的最小重量碼字的最小重量)為為t+1。反過來說，若碼的最小距離反過來說，若碼的最小距離(碼字的最小重量碼字的最小重量)為為t+1則則H的任意的任意t列線性無關而列線性無關而t+1列線性相關。列線性相關。3 3 線性分組碼線性分組碼3.4線性分組碼的伴隨式線性分組碼的伴隨式R=C+EE=e1e2en1)，說明，說明R 是一個碼字是一個碼字;2)2)，說明，說明R 不是碼字，傳輸過程產生了誤碼。不是碼字，傳輸過程產生了誤碼。3 3 線性分組碼線性分組碼例：某（例：某（5,2）系統線性碼的生成矩陣是）系統線性碼的生成矩陣是設收碼是設收碼是，問它是否是碼字，問它是否是碼字。3 3 線性分組碼線性分組碼令令則則（其中（其中表示表示的列向量）的列向量）3 3 線性分組碼線性分組碼結論：結論：1)當傳輸過程沒有錯誤時當傳輸過程沒有錯誤時，即，即，2)2)當發(fā)生一位錯誤時，當發(fā)生一位錯誤時，是校驗矩陣的某一列。是校驗矩陣的某一列。3)3)當發(fā)生多個錯誤時，當發(fā)生多個錯誤時，為校驗矩陣對應列的模為校驗矩陣對應列的模2 2和。和。例例：設設(7,3)線性分組碼的校驗矩陣為線性分組碼的校驗矩陣為3 3 線性分組碼線性分組碼（1）接收碼字）接收碼字R=(1010011)，傳輸過程中沒有誤碼，傳輸過程中沒有誤碼，3 3 線性分組碼線性分組碼（2）接收碼字）接收碼字R=(1110011)，第，第2位出錯，位出錯，3 3 線性分組碼線性分組碼（3）接收碼字）接收碼字R=(0011011)，與與中的任一列都不相同，中的任一列都不相同，不能確定到底是哪兩位出錯，不能正確譯碼。不能確定到底是哪兩位出錯，不能正確譯碼。3 3 線性分組碼線性分組碼線性分組碼的伴隨式譯碼線性分組碼的伴隨式譯碼3 3 線性分組碼線性分組碼3 3 線性分組碼線性分組碼若（若（n，k）線性分組碼能夠糾正線性分組碼能夠糾正u 個錯誤，則其校驗位個錯誤，則其校驗位的數目必須滿足的數目必須滿足4漢明碼漢明碼上式等號成立則稱為上式等號成立則稱為完備碼完備碼如果是能糾正一位錯誤的完備碼則完備碼具有下述特性：（1）以每個發(fā)送碼字為球心，以u為半徑畫一個球，那么每一個接收碼字都落在其中一個球中，因此接收碼字與發(fā)送碼字的距離至多為u；（2）所有差錯數小于等于u的接收碼字都能得到糾正；（3）差錯數大于等于u+1的接收碼字，因為落在另一個球內被糾正為其他的發(fā)送碼字。完備碼并不多見，我們知道的有u=1的漢明碼、u=3的高萊碼，以及(n,1)中n為奇數的重復碼等。4漢明碼漢明碼完備碼非完備碼0001110000010101001111101010110000001101000000000100010001000100010000000111001101101011000111101001001011110101110111001011110111.1101011010.4漢明碼漢明碼l漢明碼是一種能夠糾正單個錯誤的完備碼。漢明碼是一種能夠糾正單個錯誤的完備碼。漢明碼最小碼距漢明碼最小碼距設監(jiān)督碼共有設監(jiān)督碼共有r 位，對于漢明碼必然有位，對于漢明碼必然有。通常漢明碼可以表示成通常漢明碼可以表示成。4漢明碼漢明碼在同樣的糾錯能力下，漢明碼的碼率是最高的在同樣的糾錯能力下，漢明碼的碼率是最高的l漢明碼監(jiān)督矩陣構成的兩種方式：漢明碼監(jiān)督矩陣構成的兩種方式：按按r 位的二進制數的位的二進制數的自然自然順序從左到右排列（不包順序從左到右排列（不包括全括全0列）。當發(fā)生可糾的單個錯誤時，伴隨式為列）。當發(fā)生可糾的單個錯誤時，伴隨式為H 陣中對應的列，譯碼比較方便。陣中對應的列，譯碼比較方便。構成構成H H 陣的標準形式，陣的標準形式，。非標準形式的。非標準形式的監(jiān)督矩陣可以通過列置換變成標準形式的監(jiān)督矩陣，監(jiān)督矩陣可以通過列置換變成標準形式的監(jiān)督矩陣，糾錯能力保持不變。糾錯能力保持不變。4漢明碼漢明碼例：構造一個例：構造一個r=3的二元（的二元（7,4）漢明碼）漢明碼解：解：r=3的漢明碼，的漢明碼，列置換列置換4漢明碼漢明碼4漢明碼漢明碼信息信息比特比特碼字碼字（循環(huán)（循環(huán)1）信息信息比特比特碼字碼字（循環(huán)（循環(huán)2）信息信息比特比特碼字碼字000100100101011010001011110000010110010110010110001100011000101101100011000100011 010001111001101011011110001110101001110111010100111010100111101001111010000001111000000011111114漢明碼漢明碼l如果給漢明碼添加一位奇偶校驗位，可得到擴展?jié)h明碼：如果給漢明碼添加一位奇偶校驗位，可得到擴展?jié)h明碼：信息位保持不變，監(jiān)督位增加一位。信息位保持不變，監(jiān)督位增加一位。最小碼距最小碼距，可糾正一位錯誤，可糾正一位錯誤，同時發(fā)現兩位錯誤。同時發(fā)現兩位錯誤。l擴展?jié)h明碼的監(jiān)督方程：擴展?jié)h明碼的監(jiān)督方程：4漢明碼漢明碼5 循環(huán)碼循環(huán)碼信息信息比特比特碼字碼字（循環(huán)（循環(huán)1）信息信息比特比特碼字碼字（循環(huán)（循環(huán)2）信息信息比特比特碼字碼字00010010010101101000101111000001011001011001011000110001100010110110001100010001101000111100110101101111000111010100111011101010011101010011110100111101000000111100000001111111l循環(huán)碼是線性分組碼的一個重要子集。循環(huán)碼是線性分組碼的一個重要子集。l循環(huán)碼除了具有線性分組碼的一般性質外，還具有循環(huán)碼除了具有線性分組碼的一般性質外，還具有循循環(huán)性環(huán)性：循環(huán)碼中任一碼字經過循環(huán)移位后，所得到的：循環(huán)碼中任一碼字經過循環(huán)移位后，所得到的碼字仍然是該碼的碼字。碼字仍然是該碼的碼字。l循環(huán)碼有嚴密的代數學理論基礎，檢錯和糾錯能力較循環(huán)碼有嚴密的代數學理論基礎，檢錯和糾錯能力較強，而且編碼和解碼設備都不太復雜。強，而且編碼和解碼設備都不太復雜。5 循環(huán)碼循環(huán)碼5 循環(huán)碼循環(huán)碼1)對于二進制碼，碼多項式的每個系數不是對于二進制碼，碼多項式的每個系數不是0就是就是1。2)僅是碼元僅是碼元位置的標記。我們并不關心位置的標記。我們并不關心的取值。的取值。l設循環(huán)碼的碼字為設循環(huán)碼的碼字為，用碼多項式，用碼多項式表示為表示為l碼字（碼字（1100101）可以表示為：）可以表示為：5 循環(huán)碼循環(huán)碼循環(huán)碼的循環(huán)特性可以用碼多項式來證明：循環(huán)碼的循環(huán)特性可以用碼多項式來證明：l在在整整數數運運算算中中，有有模模n運運算算。若若一一個個整整數數m可可以以表表示示為為:則則在模在模n運算下，一整數運算下，一整數m等于其被等于其被n除所得的余數。除所得的余數。5 循環(huán)碼循環(huán)碼l在碼多項式運算中也有類似的按模運算法則。在碼多項式運算中也有類似的按模運算法則。若一任意多項式若一任意多項式M(x)被一個被一個n次多項式次多項式N(x)除，得到商除，得到商式式Q(x)和一個次數小于和一個次數小于n 的余式的余式P(x)，也就是：，也就是：則可以寫為：則可以寫為：l在循環(huán)碼中，若在循環(huán)碼中，若 是一個長為是一個長為n的許用碼字，則的許用碼字，則在模在模運算下，也是一個許用碼字。運算下，也是一個許用碼字。5 循環(huán)碼循環(huán)碼例例:某循環(huán)碼的一個碼字為某循環(huán)碼的一個碼字為1100101，則，則若將此碼左移一位，得：若將此碼左移一位，得：對應的碼字為對應的碼字為1001011(即將碼字即將碼字1100101循環(huán)左移一位）。循環(huán)左移一位）。5 循環(huán)碼循環(huán)碼信息信息比特比特碼字碼字（循環(huán)（循環(huán)1）信息信息比特比特碼字碼字（循環(huán)（循環(huán)2）信息信息比特比特碼字碼字000100100101011010001011110000010110010110010110001100011000101101100011000100011010001111001101011011110001110101001110111010100111010100111101001111010000001111000000011111115 循環(huán)碼循環(huán)碼l從碼中取出一個前面從碼中取出一個前面k-1位都是位都是0的碼字，定義這個碼的碼字，定義這個碼字的碼多項式為生成多項式字的碼多項式為生成多項式。l在在循環(huán)碼中，除了全循環(huán)碼中，除了全0碼字以外，其他碼字的連碼字以外，其他碼字的連0個數最多只有個數最多只有k-1個。個。l生成多項式的次數為生成多項式的次數為，且常數項不為，且常數項不為0。5 循環(huán)碼循環(huán)碼l為了保證構成的生成矩陣為了保證構成的生成矩陣G的各行線性不相關，通常的各行線性不相關，通常用用 這樣來構造生成矩陣。這樣來構造生成矩陣。5 循環(huán)碼循環(huán)碼k-1個05 循環(huán)碼循環(huán)碼l設信息碼元為設信息碼元為時，由生成矩陣得到相應時，由生成矩陣得到相應碼字的碼多項式：碼字的碼多項式：所有碼多項式必定為所有碼多項式必定為 的倍式。的倍式。5 循環(huán)碼循環(huán)碼5 循環(huán)碼循環(huán)碼一致校驗多項式5 循環(huán)碼循環(huán)碼 循循環(huán)環(huán)碼碼的的伴伴隨隨多多項項式式 就就是是用用接接收收碼碼多多項項式式除除以以生成多項式生成多項式 所得的余式。所得的余式。l譯碼可分為三步：譯碼可分為三步：1 1)由接收到的碼多項式由接收到的碼多項式計算計算伴隨伴隨多項式多項式；2 2)由由伴隨伴隨多項式多項式確定錯誤圖樣確定錯誤圖樣 ；3)3)將錯誤圖樣將錯誤圖樣 與與 相加，糾正錯誤。相加，糾正錯誤。5 循環(huán)碼循環(huán)碼信息序列信息序列碼序列碼序列6 6 卷積碼卷積碼6 6 卷積碼卷積碼6 6 卷積碼卷積碼6 6 卷積碼卷積碼6 6 卷積碼卷積碼R=C+EE=e1e2en6 6 卷積碼卷積碼