近代信息論第三章

近代信息論第三章第1頁，共25頁，2023年，2月20日，星期四主要內(nèi)容第三節(jié)：平均碼長界限定理第四節(jié)：無失真信源編碼定理第五節(jié)Huffman編碼第2頁，共25頁，2023年，2月20日，星期四第三節(jié)：平均碼長界限定理定義1：平均碼長含義：從平均意義上說，一個信源符號所需的平均碼符號數(shù)。第3頁，共25頁，2023年，2月20日，星期四平均碼長界限定理定義2碼率coderate(碼的信息傳輸率）含義：，每一個碼符號所能攜帶的信息量。問題雖然R和平均碼長和H(S)有關(guān)，但當(dāng)信源固定（H(S)一定時），平均碼長增大，R減小，有效性差。我們的目的：尋找平均碼長盡可能小的碼。手段：使得碼長和概率相搭配（概率大的與碼長小的相配）由“平均碼長界限定理”給出這個界。第4頁，共25頁，2023年，2月20日，星期四定理：若一個離散無記憶信源S具有熵H(S)，并有r個碼符號集X:{a1，a2,…,ar},則總可以找到一種無失真編碼，構(gòu)成單義可譯碼，使平均碼長滿足：平均碼長界限定理證明第5頁，共25頁，2023年，2月20日，星期四平均碼長界限定理證明——下界即：第6頁，共25頁，2023年，2月20日，星期四平均碼長界限定理證明——上界按上式選擇碼長構(gòu)成的碼滿足Kraft不等式，則至少可構(gòu)成單義可譯碼。第7頁，共25頁，2023年，2月20日，星期四平均碼長界限定理證明——上界注：按（1）式所構(gòu)成的單義可譯碼，平均碼長小于上界即：平均碼長小于上界時，單義可譯碼存在。但不意味著，平均碼長大于上界就不能構(gòu)成單義可譯碼。第8頁，共25頁，2023年，2月20日，星期四平均碼長界限定理推論1碼率：定義1碼的每秒信息傳輸率要無差錯傳輸，必須使每秒所傳遞的平均信息量小于信道每秒能通過的最大信息量。第9頁，共25頁，2023年，2月20日，星期四定義2平均碼長界限定理信道每秒所能傳遞的信源符號數(shù)back第10頁，共25頁，2023年，2月20日，星期四第四節(jié)：無失真信源編碼定理有界限定理可知平均碼長有下界，問：能否達(dá)到下界？是否存在這樣的碼？——無失真信源編碼定理：（Shannon第一定理）對于平均符號熵為H(S)的離散平穩(wěn)無記憶信源，對S的L次擴(kuò)展進(jìn)行編碼，存在一種無失真編碼，使得：(1)(2)第11頁，共25頁，2023年，2月20日，星期四無失真信源編碼定理證明對S的L次擴(kuò)展信源進(jìn)行編碼S1，S2,…,SL,設(shè)用r進(jìn)制碼元X:{a1，a2,…,ar}做變長編碼。（1）由平均碼長界限定理，存在單義可譯碼，L次擴(kuò)展后平均碼長滿足：第12頁，共25頁，2023年，2月20日，星期四（2）定義變長碼編碼速率編碼效率無失真信源編碼定理證明back第13頁，共25頁，2023年，2月20日，星期四第五節(jié)Huffman編碼Shannon編碼Fano編碼Huffman編碼例第14頁，共25頁，2023年，2月20日，星期四Shannon編碼碼長滿足計算出相應(yīng)的碼長，在碼樹上挑碼。例：則：第15頁，共25頁，2023年，2月20日，星期四Fano編碼——概率r等份步驟：按概率大小次序排列；將消息分成近似于等概的r個子集：{a1},{a2,a3,a4},{a5,…,a9}分別與碼樹的一級節(jié)點(diǎn)對應(yīng)；同樣各組分成等概子集第16頁，共25頁，2023年，2月20日，星期四P第一次劃分第二次劃分第三次劃分碼字碼長01201201201200111212021220221222122222333第17頁，共25頁，2023年，2月20日，星期四第18頁，共25頁，2023年，2月20日，星期四例2P第一次劃分第二次劃分第三次劃分第四次劃分010.570.43010.200.37010.170.26010101第19頁，共25頁，2023年，2月20日，星期四由此例可見：Fano法，效率低，仍不盡人意Fano編碼——概率r等份Huffman編碼第20頁，共25頁，2023年，2月20日，星期四Huffman編碼按概率大小排序；用碼符號a1，a2,…,ar分別代表概率最小的r個符號并將這r個符號合并成一個符號，從而得到只有q-r+1個符號的新信源，S1(一次縮減）又以概率大小對S1排序，用碼符號a1，a2,…,ar分別代表概率最小的r個符號并將這r個符號合并成得到S2(二次縮減）按以上方法依次繼續(xù)當(dāng)縮減過程進(jìn)行到第a次，Sa只含有r個符號，則只剩最后一步，將這r個符號用a1，a2,…,ar表示。逆次序分配碼字如果第a步時，Sa中的符號數(shù)小于r,則在原信源S中增加m=r-[q-(r-1)a]個概率為0的符號，重新開始。步驟：第21頁，共25頁，2023年，2月20日，星期四例1101010100.260.350.390.610101111001101000100010000Huffman編碼優(yōu)于Fano編碼第22頁，共25頁，2023年，2月20日，星期四例2r=3,X:{0,1,2}當(dāng)二次縮減后，S2中含符號數(shù)q-(r-1)*2=2<3,需增加1個0。1020.221020.541020202122101112第23頁，共25頁，2023年，2月20日，星期四例3碼長方差合并后的概率和盡量處于高位，可減小方差0.20.40.61010101001110010101011100.2100.40.41010100001110111第24頁，共25頁，2023年，2月20日，星期四關(guān)于Huffman編碼可以證明Huffman編碼是最佳的。Huffman編出的碼不唯一。Huffman碼字長