【正文】 ?途徑一：信道編碼定理的公式 ? 增大 C、減小 R、增加 N ?途徑二：從概念上分析糾錯編碼的基本原理 ? 利用冗余度 ? 噪聲均化 ? ?NE RePe??。 ? 與信源編碼定理類似，香農(nóng)第二定理只是一個存在性定理 ，它指出信道容量是一個臨界值，只要信息傳輸率不超過這個臨界值，信道就可以幾乎無失真地把信息傳送過去。 ? 反之，當(dāng) R＞ C時，任何編碼的 Pe＞ 0。 e≤ dmin－ 1 ed+ec≤ dmin1 t =INT[(dmin1)/2] 2021/6/15 77 有擾離散信道編碼定理 ? 若有一離散無記憶平穩(wěn)信道，其容量為 C，輸入符號序列長度為 N。 ? 檢錯能力 ? 糾錯能力 ? 檢、糾錯能力 ? 將檢錯和糾錯統(tǒng)一考慮，情況會有所變化。記為 (n, k) ? 卷積碼 ：增加的 r個校驗元既與本組信息元有關(guān)，還與前面 L組信息元有關(guān)。 ? 碼的最小距離 dmin：在某一碼集 C中，任意兩個碼字之間漢明距離的最小值稱為該碼的最小距離，即 ? ?? ?m i n m in , ,i j i j i jd D C C C C C C? ? ?　 　 　 　C最小碼距是衡量該碼糾錯能力的重要依據(jù) 2021/6/15 74 與差錯控制有關(guān)的基本概念 ? 錯誤圖樣 ? 在二元無記憶 N次擴展信道中，差錯的形式也可以用二元序列來描述，稱為 錯誤圖樣 。對于二進制來說，指碼字中碼元 1的數(shù)目。 ? 反之，若 R＜ R(D) ，則無論采用什么樣的編碼方法，其譯碼失真必大于 D。 ? 哈夫曼碼 對信源的統(tǒng)計特性沒有特殊要求，編碼效率比較高，對編碼設(shè)備的要求也比較簡單，因此綜合性能優(yōu)于香農(nóng)碼和費諾碼。 ? 費諾碼和哈夫曼碼的編碼方法都不惟一。 2021/6/15 70 三種編碼的比較 ? 香農(nóng)碼、費諾碼、哈夫曼碼都考慮了信源的統(tǒng)計特性，經(jīng)常出現(xiàn)的信源符號對應(yīng)較短的碼字，使信源的平均碼長縮短，從而實現(xiàn)對信源的壓縮。 4. 繼續(xù)上述過程，直到最后兩個符號配以 0和 1為止。 2021/6/15 69 哈夫曼編碼方法 ? 哈夫曼編碼的步驟 1. 將信源消息符號按其出現(xiàn)的概率大小依次排列 p(x1)≥p(x2)≥…≥ p(xn) 2. 取兩個概率最小的符號分別配以 0和 1，并將這兩個概率相加作為一個新符號的概率，與未分配碼元的符號重新排隊。 3. 將每一分組再按同樣原則劃分，重復(fù)步驟 2，直至概率不再可分為止。編碼過程如下： 1. 將信源消息符號按其出現(xiàn)的概率依次排列 p(x1)≥ p(x2)≥…≥ p(xn) 2. 按編碼進制數(shù)將概率分組，使每組概率盡可能接近或相等，并為每一組分配一位碼元。 ?編碼效率 ? 最佳編碼效率為 ()LHK? ? X22()eP L??? X22()L ????X() ,0()LLHH?? ????XX2021/6/15 65 變長編碼定理 ?單個符號 變長編碼定理 ? 若一離散無記憶信源的符號熵為 H(X)，每個信源符號用 m進制碼元進行變長編碼，一定存在一種無失真編碼方法，其碼字平均長度滿足下列不等式 1l o g)(l o g)( ???mXHKmXH2021/6/15 66 變長編碼定理 ?離散平穩(wěn)無記憶序列 變長編碼定理 ? 對于平均符號熵為 HL(X)的離散平穩(wěn)無記憶信源，必存在一種無失真編碼方法，使平均信息率 滿足不等式 ? 其中， ε為任意小正數(shù)。 ? 對任意 ε0， δ0，只要 則當(dāng) L足夠大時，必可使譯碼差錯小于 δ； ? 反之，當(dāng) 時，譯碼差錯一定是有限值，而當(dāng) L足夠大時，譯碼幾乎必定出錯。 4. 按 唯一可譯碼判斷法 進行判斷。若不滿足，一定不是唯一可譯碼。若是，一定不是唯一可譯碼。最終得到碼 C的所有可能的尾隨后綴的集合 F。依此下去，直到?jīng)]有一個尾隨后綴是碼字的前綴為止。若是，將其所有可能的尾隨后綴排列出。 2021/6/15 60 唯一可譯碼的判斷法 ? 將碼 C中所有可能的尾隨后綴組成一個集合 F，當(dāng)且僅當(dāng)集合 F中沒有包含任一碼字，則可判斷此碼 C為唯一可譯碼。 ) ( ) ( / ) l o g()jii j iij jp y xI X Y p x p y xpy? ?? 信道固定 輸入概率分布固定 2021/6/15 55 率失真函數(shù)和信道容量的比較 2021/6/15 56 第 5章 信源編碼 ? 重點掌握 ? 分組碼的屬性 ? 唯一可譯碼的判斷方法 ? 信源編碼定理 ? 香農(nóng)編碼、費諾編碼、哈夫曼編碼 ? 一般了解 ? 編碼的術(shù)語 ? 游程編碼、算術(shù)編碼 2021/6/15 57 分組碼屬性 碼 非分組碼 分組碼 奇異碼 非奇異碼 非唯一可譯碼 唯一可譯碼 非即時碼 即時碼（非延長碼） 2021/6/15 58 碼樹 ? 中間節(jié)點不安排碼字，只在終端節(jié)點安排碼字 ? 每個終端節(jié)點對應(yīng)的碼字由從根節(jié)點出發(fā)到終端節(jié)點走過的路徑上所對應(yīng)的符號組成 ? 當(dāng)?shù)?i階的節(jié)點作為終端節(jié)點，且分配碼字，則碼字的碼長為 i ? 按樹圖法構(gòu)成的碼一定滿足即時碼的定義 ? 樹碼的各個分支都延伸到最后一級端點，則稱為 滿樹 ，否則為 非滿樹 ? 滿樹碼是定長碼，非滿樹碼是變長碼 2021/6/15 59 11inKim ????克勞夫特不等式 ?唯一可譯碼 存在 的充分和必要條件為：各碼字的長度 Ki 應(yīng)滿足下式。 )ipxC I X Y?)。 ? 信道傳遞概率 p(yj /xi)的下凸函數(shù)。 2021/6/15 54 率失真函數(shù)和信道容量的比較 ? 平均互信息 I(X。 ? R(D)在定義域內(nèi)是關(guān)于 D的連續(xù)函數(shù)。 ? R(D)的定義域 ? 率失真函數(shù)的定義域問題就是在信源和失真函數(shù)已知的情況下，討論允許平均失真度 D的最小和最大取值問題，即 [Dmin,Dmax] ? Dmin的計算 ? Dmax的計算 ( ) m in ( 。 D? ? ? ? ? ? ? ? ? ?1 1 1 1, / ,n m n mi j i j i j i i ji j i jD p a b d a b p a p b a d a b? ? ? ???? ? ? ?2021/6/15 50 ? ? ? ? ? ? ? ?1 1 1 1,=LLL n m Li l j l i l i l j l ll i j lD L p x p y x d x y D? ? ? ?? ? ? ? ?/平均失真 ? L維信源符號序列的平均失真度 ? 當(dāng)信源與信道無記憶時， ? 信源符號平均失真度（平均每個符號的平均失真度） ? ?111 LLllD D L DLL??? ?? ? ? ? ? ? ? ?11LLnmijD L p p d??? ?? i j i i jx / xx ,yy? ? ? ? ? ?1 1 1,LLn m Lil jli j lp p d x y? ? ?? ? ? ?i j i/x y xlD表示信源符號序列的第 l 個符號的平均失真 2021/6/15 51 保真度準則 ? 保真度準則 ? 平均失真度不大于允許的失真 ? D允許信道 ? D允許的試驗信道，即滿足保真度準則的試驗信道。 ? 平均失真 ： ? 平均失真對信源和信道進行的統(tǒng)計平均。 ? 失真函數(shù) d(xi,yj) ? 描述某個信源符號通過傳輸后失真的大小。Y) ? 信道相對冗余度 ? ? ? ?。 ? 信息匹配 ? 對于某一信道，只有當(dāng)輸入符號的概率分布滿足一定條件時，才能達到其信道容量。但到一定階段后，增加變得緩慢。 ? 信道容量 C一定時， 帶寬 W增大， 信噪比 SNR可降低，即二