【正文】 Y b b b b??Y無失真信源編碼 ? 設(shè)信源符號序列的長度為 L ? 變換成由 KL個符號組成的 碼序列（ 碼字 ） ? 變換要求 ? 能夠無失真或無差錯地從 Y 恢復(fù) X，也就是能正確地進(jìn)行反變換或譯碼 ? 傳送 Y 時所需要的信息率最小 ? ?? ?1212, , , , ,lLl i nX X X XX a a a a??Xl ogLKKmL?2021/6/15 63 定長編碼定理 ? 定長編碼定理 ：由 L個符號組成的、每個符號的熵為 HL(X)的無記憶平穩(wěn)信源符號序列 X1X2… Xl… XL，可用 KL個符號 Y1, Y2,…, Yk,… YKL（每個符號有 m種可能值）進(jìn)行定長編碼。 ? 對任意 ε0， δ0，只要 則當(dāng) L足夠大時，必可使譯碼差錯小于 δ； ? 反之，當(dāng) 時，譯碼差錯一定是有限值，而當(dāng) L足夠大時，譯碼幾乎必定出錯。 ? ?l o gL LK mHL ???X? ?l o g 2L LK mHL ???X2021/6/15 64 編碼效率 ?差錯概率 ? 當(dāng)信源序列長度 L滿足 時， 就能達(dá)到差錯率要求。 ?編碼效率 ? 最佳編碼效率為 ()LHK? ? X22()eP L??? X22()L ????X() ,0()LLHH?? ????XX2021/6/15 65 變長編碼定理 ?單個符號 變長編碼定理 ? 若一離散無記憶信源的符號熵為 H(X)，每個信源符號用 m進(jìn)制碼元進(jìn)行變長編碼，一定存在一種無失真編碼方法，其碼字平均長度滿足下列不等式 1l o g)(l o g)( ???mXHKmXH2021/6/15 66 變長編碼定理 ?離散平穩(wěn)無記憶序列 變長編碼定理 ? 對于平均符號熵為 HL(X)的離散平穩(wěn)無記憶信源，必存在一種無失真編碼方法，使平均信息率 滿足不等式 ? 其中， ε為任意小正數(shù)。 ( ) ( ) LLH K H ?? ? ?XXK2021/6/15 67 香農(nóng)編碼步驟 1. 將信源消息符號按其概率從大到小排列 2. 確定滿足下列不等式的整數(shù)碼長 Ki 3. 令 P1=0，計算第 i個消息的累加概率 4. 將累加概率 Pi變換成二進(jìn)制數(shù)，取小數(shù)點后 Ki位為該消息的碼字 ? ? ? ? ? ?12 np x p x p x? ? ?? ? ? ?l og l og 1i i ip x K p x? ? ? ? ?? ?11iikkP p x??? ?2021/6/15 68 費諾編碼方法 ? 費諾編碼屬于 概率匹配編碼 ，不是最佳的編碼方法。編碼過程如下： 1. 將信源消息符號按其出現(xiàn)的概率依次排列 p(x1)≥ p(x2)≥…≥ p(xn) 2. 按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近或相等，并為每一組分配一位碼元。如編二進(jìn)制碼就分成兩組，編 m進(jìn)制碼就分成 m組。 3. 將每一分組再按同樣原則劃分，重復(fù)步驟 2，直至概率不再可分為止。 4. 信源符號所對應(yīng)的碼字即為費諾碼。 2021/6/15 69 哈夫曼編碼方法 ? 哈夫曼編碼的步驟 1. 將信源消息符號按其出現(xiàn)的概率大小依次排列 p(x1)≥p(x2)≥…≥ p(xn) 2. 取兩個概率最小的符號分別配以 0和 1，并將這兩個概率相加作為一個新符號的概率，與未分配碼元的符號重新排隊。 3. 對重排后的兩個概率最小符號重復(fù)步驟 2的過程。 4. 繼續(xù)上述過程，直到最后兩個符號配以 0和 1為止。 5. 從最后一級開始，向前返回得到各個信源符號所對應(yīng)的碼元序列，即相應(yīng)的碼字。 2021/6/15 70 三種編碼的比較 ? 香農(nóng)碼、費諾碼、哈夫曼碼都考慮了信源的統(tǒng)計特性，經(jīng)常出現(xiàn)的信源符號對應(yīng)較短的碼字，使信源的平均碼長縮短，從而實現(xiàn)對信源的壓縮。 ? 香農(nóng)碼 有系統(tǒng)的、惟一的編碼方法，但在很多情況下編碼效率不是很高。 ? 費諾碼和哈夫曼碼的編碼方法都不惟一。 ? 費諾碼 比較適合于對分組概率相等或接近的信源編碼。 ? 哈夫曼碼 對信源的統(tǒng)計特性沒有特殊要求，編碼效率比較高，對編碼設(shè)備的要求也比較簡單，因此綜合性能優(yōu)于香農(nóng)碼和費諾碼。 2021/6/15 71 限失真信源編碼定理 ? 設(shè)離散無記憶信源 X的信息率失真函數(shù)為 R(D) ? 當(dāng)信息率 R＞ R(D)時，只要信源序列長度 L 足夠長，一定存在一種編碼方法，其譯碼失真小于或等于 D＋ ε， ε為任意小的正數(shù)。 ? 反之，若 R＜ R(D) ，則無論采用什么樣的編碼方法，其譯碼失真必大于 D。 ? 如果是二元信源，則對于任意小的 ε＞ 0，每一個信源符號的平均碼長滿足如下公式： ???? )()( DRKDR2021/6/15 72 第 6章 信道編碼 ? 重點掌握 ? 差錯控制相關(guān)的基本概念 ? 差錯控制系統(tǒng)分類 ? 檢、糾錯能力 ? 有擾離散信道編碼定理 ? 一般了解 ? 糾錯碼分類 ? 糾錯碼的基本思路 2021/6/15 73 與差錯控制有關(guān)的基本概念 ? 漢明重量 （ 碼重 ）：碼字中非 0碼元的個數(shù)，用 W表示。對于二進(jìn)制來說，指碼字中碼元 1的數(shù)目。 ? 漢明距離 （ 碼距 ）：兩個等長碼字之間對應(yīng)碼元不相同的數(shù)目，用 D表示。 ? 碼的最小距離 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次擴(kuò)展信道中，差錯的形式也可以用二元序列來描述，稱為 錯誤圖樣 。 ? 設(shè)發(fā)送碼字為 C=(c1c2… )，接收碼字為R=(r1r2… rn)，兩者的差別為 ? 分組碼 ：每個碼字中增加的 r 個校驗元只由本組的 k個信息元產(chǎn)生，與其他信息組的信息元無關(guān)。記為 (n, k) ? 卷積碼 ：增加的 r個校驗元既與本組信息元有關(guān)，還與前面 L組信息元有關(guān)。記為 (n, k, L) ? ?12 nE e e e C R? ? ?2021/6/15 75 差錯控制系統(tǒng)分類 ? 前向糾錯方式 （ FEC） ? 自動請求重發(fā)方式 （ ARQ） ? 混合糾錯 （ HEC） 譯碼設(shè)備不復(fù)雜，對突發(fā)錯誤特別有效 實時性好，適用于單工通信 檢錯、糾錯能力強(qiáng)，譯碼設(shè)備復(fù)雜，應(yīng)用廣泛 2021/6/15 76 檢錯與糾錯能力 ? 檢錯與糾錯能力 ? 糾錯碼的檢、糾錯能力是指能夠檢測、糾正差錯的數(shù)目。 ? 檢錯能力 ? 糾錯能力 ? 檢、糾錯能力 ? 將檢錯和糾錯統(tǒng)一考慮，情況會有所變化。 ? 要增加檢錯能力，必須抑制糾錯能力。 e≤ dmin－ 1 ed+ec≤ dmin1 t =INT[(dmin1)/2] 2021/6/15 77 有擾離散信道編碼定理 ? 若有一離散無記憶平穩(wěn)信道，其容量為 C，輸入符號序列長度為 N。只要待傳送的信息率 R＜ C，總可以找到一種編碼方法，當(dāng) N足夠長時，使譯碼錯誤概率 Pe＜ ε， ε為任意正數(shù)。 ? 反之，當(dāng) R＞ C時，任何編碼的 Pe＞ 0。當(dāng) N→∞時， Pe→1 。 ? 與信源編碼定理類似，香農(nóng)第二定理只是一個存在性定理 ，它指出信道容量是一個臨界值，只要信息傳輸率不超過這個臨界值，信道就可以幾乎無失真地把信息傳送過去。 2021/6/15 78 差錯控制 ?差錯控制：從公式和概念兩條途徑來論述差錯控制與信道編碼的基本原理。 ?途徑一：信道編碼定理的公式 ? 增大 C、減小 R、增加 N ?途徑二：從概念上分析糾錯編碼的基本原理 ? 利用冗余度 ? 噪聲均化 ? ?NE RePe?