1、 第三章討論無失真信源編碼，給出無失真編碼所需最小速率R H(U)/logD. 信道給定，以任意小的錯誤概率實現可靠通信的最大傳輸速率為多少？ Shannon于1948年提出并證明了信道編碼定理，揭示了在什么條件下可以實現可靠通信，在什么情況下不能實現。 后來很多研究者給出了更嚴格、更一般化的證明，指出了各種信道和編碼條件下所能達到的編碼定理的上、下限。 這些理論的進展為合理設計實際通信系統提供了理論依據。什么條件？RC信道信道信源信源信源編碼信源編碼信道編碼信道編碼調 制 器調 制 器干 擾 源干 擾 源信宿信宿信源譯碼信源譯碼信道譯碼信道譯碼解 調 器解 調 器數字通信系統模型數字通信系統

2、模型信道編碼信道編碼信道編碼（糾錯編碼）的任務是將輸入的信息數字序列信道編碼（糾錯編碼）的任務是將輸入的信息數字序列變換成另一個數字序列送入有擾離散信道。人為的按一變換成另一個數字序列送入有擾離散信道。人為的按一定規則增加多余度，以便糾正傳送過程中可能出現的錯定規則增加多余度，以便糾正傳送過程中可能出現的錯誤，以盡可能小的錯誤概率恢復原來的信源序列。誤，以盡可能小的錯誤概率恢復原來的信源序列。0001101100000101011101001111r = 1111011010 (10)011-p101-ppp 假設假設p0.5不編碼，誤碼率不編碼，誤碼率pb=p編碼，編碼，pe=3p2+p3-

3、6p4+3p5信道編碼器模型信道編碼器模型c0000=,cscsnknk每個信息數字持續時間為每個信息數字持續時間為 秒秒ssR/1編碼器通常對信息數字進行分段，稱為信息段，信息段，設其長度為 . 0ksk00n在 時間段內，編碼器計算出 個編碼數字送入信道，稱為碼段碼段。 編碼數字持續時間為編碼數字持續時間為 秒秒,信道編碼分類信道編碼分類通常糾錯碼被分為兩類，分組碼和格狀碼。通常糾錯碼被分為兩類，分組碼和格狀碼。（N,K)分組碼：每分組碼：每 K個信息數字為一組，計算出個信息數字為一組，計算出 N 個編個編碼數字構成一個分組，一個分組又稱為一個碼字。碼數字構成一個分組，一個分組又稱為一個碼

4、字。碼字之間是不相關的。碼字之間是不相關的。格狀碼：輸出的碼段不僅依賴于當前的格狀碼：輸出的碼段不僅依賴于當前的K0位信息數字，位信息數字，還依賴于前還依賴于前m個信息段的信息數字，即總共與（個信息段的信息數字，即總共與（m+1)K0個信息數字有關。個信息數字有關。 稱（稱（m+1)K0為編碼約束長度。為編碼約束長度。稱稱 或或 為糾錯碼的編碼速率或簡稱碼率為糾錯碼的編碼速率或簡稱碼率 00/nkR NKR/要求糾錯能力越強，所需多余度越大，碼率就越低。0001101110101100100111011111編碼編碼jm1jm11 0111111 100101 1 0 1jm1jm2jm1jX

5、2jX11 01 01 00實實 例例分組碼分組碼(5,2)卷積碼卷積碼(2,1,3)分組碼的譯碼準則分組碼的譯碼準則以分組碼為例討論信道編碼的譯碼問題。),(21Nyyyy長為K的二元信息序列總數為 個 ，而長為N的二元數字序列總數為 個。KM2N2分組編碼就是從 個N長數字序列中選出 個碼字，分別用于代表M個不同的信息序列。任何一種指定方案就給定了一種編碼方案。 N2KM2令令 是是 信道輸入相應的信道輸出。信道輸入相應的信道輸出。),(21Nmxxxx分組碼的譯碼準則分組碼的譯碼準則糾錯譯碼器的作用就是根據接收到的糾錯譯碼器的作用就是根據接收到的y和編碼規則，對發和編碼規則，對發送的是送

6、的是M個可能序列中的哪一個做出判決。個可能序列中的哪一個做出判決。設譯碼器在收到設譯碼器在收到y后將它譯為后將它譯為 。若。若 ，就出現，就出現了錯誤。這種事件出現的概率是了錯誤。這種事件出現的概率是誤組率誤組率 。mxmm epekp其中其中 是第是第 k 位出現錯誤的概率位出現錯誤的概率一個碼字發生錯誤意味著一個碼字發生錯誤意味著N長二元數字序列中至少有一長二元數字序列中至少有一位錯。位錯。K11Kbekkpp誤比特率誤比特率是譯碼后錯誤比特數與總比特數之比是譯碼后錯誤比特數與總比特數之比)|(max)| (yupympNuN跑遍所有碼字分組碼的譯碼準則分組碼的譯碼準則譯碼準則就是猜測規則

7、，即當信道的輸出值為譯碼準則就是猜測規則，即當信道的輸出值為y時，時，將其譯為哪個碼字將其譯為哪個碼字m最合理？最合理？最大后驗概率準則最大后驗概率準則對特定接收序列對特定接收序列y，)(1)()(yyymmpmmppNNe譯碼時要求譯碼時要求 最小最小)(yep若有一個以上的若有一個以上的m，使，使 取同樣的最大值時，取同樣的最大值時，我們可從其中任選一個，而不會影響平均錯誤概率我們可從其中任選一個，而不會影響平均錯誤概率)(ympN最小錯誤概率譯碼準則最小錯誤概率譯碼準則)|(max) |(uypmypNuN跑遍所有碼字分組碼的譯碼準則分組碼的譯碼準則最大似然譯碼準則最大似然譯碼準則)()

8、()()(yxyywpmQmpmNN最大后驗概率最大后驗概率若所有可能消息序列的先驗概率相等若所有可能消息序列的先驗概率相等，則最大后驗概率準則，則最大后驗概率準則可進一步簡化為可進一步簡化為)|(max) |(uypmypNuN跑遍所有碼字最大后驗概率譯碼最大后驗概率譯碼)(ln)(ln)(ln) (lnmNmNpmQpmQxyxy mm 最大似然譯碼（當消息先驗概率相等時）最大似然譯碼（當消息先驗概率相等時）)(ln)(lnmNmNppxyxy mm 譯碼準則的對數形式譯碼準則的對數形式)()()()(yxyywpmQmpmNN后驗概率后驗概率【注注2】在消息先驗等概條件下，它等價于最大后

9、驗概率在消息先驗等概條件下，它等價于最大后驗概率 譯碼，因而也是最佳的。但若消息先驗概率不確譯碼，因而也是最佳的。但若消息先驗概率不確 知時，采用最大似然譯碼就不一定保證譯碼錯誤知時，采用最大似然譯碼就不一定保證譯碼錯誤 概率最小。概率最小?！咀⒆?】它并不要求消息的先驗概率。它并不要求消息的先驗概率。【注注3】實際系統中，信源發出的序列傳送到信道之前都實際系統中，信源發出的序列傳送到信道之前都 已進行信源編碼，經過有效的信源編碼，輸出碼已進行信源編碼，經過有效的信源編碼，輸出碼 元的概率分布會均勻化，所以信道的輸入近似為元的概率分布會均勻化，所以信道的輸入近似為 等概，因此在工程應用中采用最

10、大似然譯碼盡管等概，因此在工程應用中采用最大似然譯碼盡管 不會使錯誤概率達到最小，但也接近最小。不會使錯誤概率達到最小，但也接近最小。最大似然譯碼準則最大似然譯碼準則例例 題題設有一個離散信道，其轉移概率矩陣為設有一個離散信道，其轉移概率矩陣為 4 . 03 . 03 . 05 . 03 . 02 . 02 . 03 . 05 . 0/xyP并設并設 ， ， ，試分別按最小錯，試分別按最小錯誤概率準則與最大似然譯碼準則確定譯碼規則，并計誤概率準則與最大似然譯碼準則確定譯碼規則，并計算相應的譯碼錯誤概率？算相應的譯碼錯誤概率？41)(1xp41)(2xp21)(3xp根據根據最大似然譯碼準則最大

11、似然譯碼準則，譯碼函數為，譯碼函數為233211)()()(:abDabDabDB在輸入等概分布時的采用在輸入等概分布時的采用最大似然譯碼準則最大似然譯碼準則的平均錯誤概的平均錯誤概率：率：567. 0)4 . 02 . 0() 3 . 03 . 0() 3 . 02 . 0(31)/(31*),(xypPaXxye在輸入分布為（在輸入分布為（0.25,0.25,0.5）時的采用）時的采用最大似然譯碼準則最大似然譯碼準則的平均錯誤概率：的平均錯誤概率：6 . 0)4 . 02 . 0 (21) 3 . 03 . 0 (41) 3 . 02 . 0 (41)/()(*),(xypxpPaXxye

12、根據根據最小錯誤概率最小錯誤概率譯碼準則譯碼準則，譯碼函數為，譯碼函數為2 . 015. 015. 0125. 0075. 005. 005. 0075. 0125. 0 xyP333231)()()(:abDabDabDC在輸入分布為在輸入分布為（0.25,0.25,0.5）時的采用時的采用最大似然譯最大似然譯碼準則碼準則的平均錯誤概率：的平均錯誤概率：5 . 0)5 . 02 . 0 (21) 3 . 03 . 0 (41) 2 . 05 . 0 (41)/()(*),(xypxpPaXxye可見，在輸入不等概分布時的采用可見，在輸入不等概分布時的采用最大似然譯碼準則最大似然譯碼準則的平的

13、平均錯誤概率不是最小。均錯誤概率不是最小。平均錯誤概率平均錯誤概率Pe與譯碼規則有關，而譯碼規則又由信道特與譯碼規則有關，而譯碼規則又由信道特性來決定。性來決定。由于信道存在噪聲和干擾，使得接收到輸出符號后，對發由于信道存在噪聲和干擾，使得接收到輸出符號后，對發送的是什么符號還存在不確定性。送的是什么符號還存在不確定性?？梢?，可見，Pe與信道懷疑義度與信道懷疑義度H(X/Y)是有一定關系，也即滿是有一定關系，也即滿足足Fano不等式。不等式。) 1(log)()/(MPPHYXHeeFano不等式不等式證明：證明： 定義隨機變量定義隨機變量 ererpzppzpxyxyZ) 1(,1)0(10

14、)()()(XYZHYXHYXZH0)(XYZH)(YXH)()()(ZYXHYZHYXZH)()(ZYXHZH)()(ZYXHpHe), 1(), 0()1 ()(YZXHpYZXHpZYXHee) 1log() 1log(0MpMpee) 1log()()(MppHYXZHee)()() 1log(YXHpHMpee) 1log()()(MppHYXHeeFano不等式不等式)(1)() 1log(LLbbVUHLpHMp證明：證明： )()()(112UVUHVUHVUHLLLLLllLVUHUUVUHlLL11)()(1由由Fano不等式，可得不等式，可得LlelelLllLLpHMp

15、VUHVUHl11)() 1log()()(LlelepHMLp1)() 1log(LlelepLp11由引理由引理2兩邊對兩邊對l求和，得求和，得LleeleelLlelpppppH1111log)1 (1log)(eeeeppLpLp11log)1 (1log綜上綜上)() 1log()(eeLLpLHMLpVUH即即)(1)() 1log(LLeeVUHLpHMpLlelepLp11)(epLHLleleLLpHMLpVUH1)() 1log()(eeleelelelelell epppppppppHlog)1 (loglog)1 (log)(Fano不等式不等式對于給定的信源、信道及編

16、譯碼規則，即給定了聯合對于給定的信源、信道及編譯碼規則，即給定了聯合空間空間 ，則信道的含糊度，則信道的含糊度 就可被確定，這個值就給定了譯碼錯誤概率的下限。就可被確定，這個值就給定了譯碼錯誤概率的下限。 ),(,vupUV);()()(VUIUHVUH)()() 1log(VUHpHMpee分組碼的譯碼分組碼的譯碼 分組碼編碼：消息空間分組碼編碼：消息空間UL到輸出空間到輸出空間YN的一種映射的一種映射譯碼規則可以看成是譯碼規則可以看成是YN到到UL的一種映射，即將空間的一種映射，即將空間YN按譯碼準則劃分成不相交的判決空間按譯碼準則劃分成不相交的判決空間 。11,MMYYY 最大后驗概率譯

17、碼最大后驗概率譯碼 最大似然譯碼最大似然譯碼 )(ln)(ln)(ln) (ln:mNmNmpmQpmQYYxyxy mm )(ln)(ln:mNmNmppYYxyxy mm 其中其中 ,kiYY , ik 11MiNiYY若接收矢量若接收矢量 ，就將，就將y判為消息判為消息m。若若 ，就將，就將y作為刪除或檢錯處理。作為刪除或檢錯處理。mYy1MYy令令cmY表示表示mY的補集，當發送消息為的補集，當發送消息為m，而接收，而接收y落入落入中就會產生譯碼錯誤。中就會產生譯碼錯誤。1)(McmYYmNemppyxy若消息若消息m的先驗概率為的先驗概率為Q(m)，則平均譯碼錯誤概率為，則平均譯碼錯

18、誤概率為MmemepmQp1)(1McmYY分組碼的譯碼分組碼的譯碼若消息若消息m的先驗概率為的先驗概率為Q(m)，則，則可檢測可檢測譯碼錯誤概率為譯碼錯誤概率為 給定給定m時的時的不可檢測不可檢測譯碼錯誤概率為譯碼錯誤概率為MmmMNuYpmQp11)()(xy定義： 和 的漢明距離 為),(21Nyyyy),(21Nxxxx( ,)Hdx yNmmmHyxd1),(),(yx其中mmmmmmyxyxyx10),(當所有碼字為等概時，信道為BSC，最大似然譯碼為( ,)(1)( ,)( ,)(1)( ,)HHHHNdppdNdppdmmmmy xy xy xy x),(),(mmxyxyHH

19、dd對所有的 在對稱信道條件下，離散輸入序列的最大似然譯碼等價于在對稱信道條件下，離散輸入序列的最大似然譯碼等價于最小漢明距離譯碼。最小漢明距離譯碼。二元對稱信道（BSC）的譯碼011-p101-ppp 假設假設p0.5 假設p0.5，可化簡為mm 例例 題題設設M=2且兩個消息等概，令且兩個消息等概，令 ， 。通過轉移概率為通過轉移概率為p1/2的的BSC信道傳送。信道傳送。(1)若采用完備譯碼，試根據最大后驗概率準則劃分譯若采用完備譯碼，試根據最大后驗概率準則劃分譯碼區間并給出相應的譯碼錯誤概率。碼區間并給出相應的譯碼錯誤概率。(2)若可以劃分三個區間，試確定譯碼規則并給出譯碼若可以劃分三

20、個區間，試確定譯碼規則并給出譯碼錯誤概率和有錯不能判決的概率？錯誤概率和有錯不能判決的概率？)0000(1x)1111(2x解：消息等概，最大后驗概率準則最大后驗概率準則等效等效最大似然譯碼準則最大似然譯碼準則。223421)1 (3)1 (4ppppppppeee1.若采用完備譯碼，即對任何情況都必須做出判決。判決空間判決空間劃分劃分Y1=0000，0001，0010，0100，1000，0011，1100，1001Y2=1111，1110，1101，1011，0111，1010，0101，0110這時不難算出錯誤概率為：2.若可以劃分三個區間，若可以劃分三個區間，可將可將Y劃分成：劃分成：

21、0000，0001，0010，0100，10001111，1110，1101，1011，01110011，1100，0110，1001，1010，0101這時不難算出錯誤概率為：)1 (43421ppppppeee發現有錯而不能判決的概率為：22)1 (6pppd連續序列的譯碼此時以轉移概率密度 描述信道的轉移特性。最大后驗概率準則為找尋m，使),|()|(mmPP對所有的yxyxmm由貝葉斯公式，等價于),|()()|() (mmpmQpmQ對所有的mmxyxy若各信號為等概的，則最大后驗概率準則就轉化為最大似然準則，即),|()|(mmpp對所有的mmxyxy高斯白噪聲信道的譯碼準則高斯白噪聲信道的譯碼準則若加性信道噪聲是均值為0，雙邊功率譜密度為 的高斯白噪聲，則信號轉移概率密度可以表示為)(exp)1()|(022/110NxyNpkmkNkmxy)(