信息論無(wú)失真信源編碼

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

一個(gè)分組碼若對(duì)于任意有限的整數(shù)N，其N階擴(kuò)展碼均為非奇異的，則稱之為唯一可譯碼。含義：無(wú)論碼由多少個(gè)碼字組成，總是能夠正確譯碼，不存在二義性。第6頁(yè)，共13頁(yè)，2023年，2月20日，星期日即時(shí)碼無(wú)需知道下一個(gè)碼字的碼符號(hào)，即可譯碼，這樣的唯一可譯碼成為即時(shí)碼。命題5.2.1

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