信息論無失真信源編碼第一頁，共十三頁，2022年，8月28日無失真信源編碼：解碼之后可以得到原始信息，例如霍夫曼編碼。它相對簡單，是本章的重點(diǎn)。有失真信源編碼：解碼之后的信息與原始信息有一定的差別，例如JPEG、MPEG第二頁，共十三頁，2022年，8月28日5.1編碼器信源編碼器表示為：例如：其中X稱為碼符號集，X中的元素xi稱為碼元或者碼符號。輸出符號Wi稱為碼字，碼字的集合C稱為代碼組或者碼。碼字Wi的長度li稱為碼字長度，簡稱碼長。要實(shí)現(xiàn)無失真編碼，編碼器的映射必須是一一對應(yīng)、可逆的。第三頁，共十三頁，2022年，8月28日碼的分類根據(jù)碼長固定長度碼（定長碼）：所有碼字的長度相同?？勺冮L度碼（變長碼）：碼字長短不一。碼字是否相同非奇異碼：所有碼字都不相同。奇異碼：存在相同的碼字。第四頁，共十三頁，2022年，8月28日5.2分組碼定義5.2.1將信源符號集中的每個信源符號si映射成一個固定的碼字Wi，這樣的碼稱為分組碼。通常在接收端收到的碼字之間并沒有明顯的間隔，表現(xiàn)為W1W2…Wq的形式，把這種形式稱為q階擴(kuò)展碼。例如前面的兩個例子，ACD編碼成為001011/0001111的形式，均為3階擴(kuò)展碼。碼字之間缺少間隔，給譯碼造成了一定的困難定長碼：不存在困難，001011必定譯碼成為ACD變長碼：存在困難，0001111可以譯碼成為ACD(0001111)，也可以譯碼成為AABD(0001111)。ABCD00011011ABCD001001111第五頁，共十三頁，2022年，8月28日唯一可譯性定義

一個分組碼若對于任意有限的整數(shù)N，其N階擴(kuò)展碼均為非奇異的，則稱之為唯一可譯碼。含義：無論碼由多少個碼字組成，總是能夠正確譯碼，不存在二義性。第六頁，共十三頁，2022年，8月28日即時碼無需知道下一個碼字的碼符號，即可譯碼，這樣的唯一可譯碼成為即時碼。命題

一個唯一可譯碼成為即時碼的充要條件是其中任何一個碼字都不是其他碼字的前綴。ABCD1101001000ABCD101001000110110010→BACB10110001→ABAD第七頁，共十三頁，2022年，8月28日5.3定長碼編碼速率：，其中l(wèi)是碼字長度，r是碼符號的個數(shù)，N代表N次擴(kuò)展信源。編碼效率：η=H(S)/R，其中H(S)是擴(kuò)展之前信源的熵。例如：S={A,B,C},等概率出現(xiàn)，N=2,SN={AA,…,CC}，對SN進(jìn)行二元編碼，則r=2，編碼方式如下，則l=4。那么，SN的編碼速率為R=(4log2)/2=2，SN的編碼效率為η=H(S)/R=log3/2=0.7925AAABACBABBBCCACBCC000000010010010001010110100010011010第八頁，共十三頁，2022年，8月28日5.4變長碼匹配編碼：根據(jù)概率進(jìn)行編碼，概率大的所給的代碼短，概率小的所給的代碼長。例如哈夫曼編碼。變換編碼：將信號從一個空間變換到另一個空間，在新的空間里對信號進(jìn)行編碼。例如JPEG。識別編碼：主要用于印刷或者打字機(jī)等有標(biāo)準(zhǔn)形狀的符號的編碼。第九頁，共十三頁，2022年，8月28日5.4.2兩個不等式定理5.4.1即時碼存在的充要條件是克拉夫特（Kraft）不等式。定理5.4.2唯一可譯碼存在的充要條件是麥克米倫（McMillan）不等式。第十頁，共十三頁，2022年，8月28日5.4.3唯一可譯碼判別準(zhǔn)則命題5.4.1一種碼是唯一可譯碼的充要條件是S1,S2,…中沒有一個含有S0中的碼字。S0S1S2S3S4S5S6S7abbcdedebaddebcbcdeabbbaddebbbcde第十一頁，共十三頁，2022年，8月28日5.4.4碼平均長度定義5.4.1設(shè)信源編碼后的碼字分別為W1W2…Wq，各碼字相應(yīng)的碼長分別為l1l2…lq。對唯一可譯碼，則這個碼的平均長度為定義5.4.2對應(yīng)一給定的信源和一給定的碼符號集，若有一種唯一可譯碼，其平均長度小于所有其他的唯一可譯碼，則稱這種碼為緊致碼，或最佳碼。第十二頁，共十三頁，2022年，8