第4章數(shù)據(jù)壓縮為什么即時碼是漸進(jìn)最優(yōu)碼？構(gòu)造即時碼的基本方法？4.1即時碼定義1、信源編碼信源符號序列到不等長碼序列的映射進(jìn)制變換冗余壓縮不等長離散型隨機(jī)變量序列C1C2…Cl2、平均碼長信源各消息碼字長度的數(shù)學(xué)期望，用L表示定義信源編碼及平均碼長例1某種信源編碼平均碼長信源的熵例2二次擴(kuò)展信源信源編碼及平均碼長某種信源編碼平均碼長信源的熵3、編碼效率定義信源的熵與信源編碼的碼率之比從提高傳輸效率的角度，碼率越接近熵越好4、非奇異碼定義表示信源發(fā)出的每條消息映射為不同的碼字——一一對應(yīng)5、碼的擴(kuò)展編碼定義表示消息串的碼字等于消息的碼字串6、唯一可譯碼定義表示碼的擴(kuò)展編碼為非奇異碼唯一可譯碼——由碼字串可唯一譯出消息串——自我間斷碼7、即時碼定義碼表中無任何碼字是其它碼字的前綴即時碼可以用樹圖構(gòu)造二進(jìn)制即時碼00,10,11和0,10,11各自所對應(yīng)的二叉樹圖010101010即時碼——任何碼字結(jié)束時即可譯出的自我間斷碼全體編碼非奇異碼唯一可譯碼即時碼例3奇異碼非奇異碼非唯一可譯唯一可譯碼非即時即時碼x10000x2110110x310101111例4左移1位=0？=10？輸出x1Y輸出x2YNN輸出x3左移2位結(jié)束？YN輸入碼字串結(jié)束4.2克拉夫特不等式定理對于二進(jìn)制即時碼，碼長l1,l2,…,lNn必定滿足不等式反之，給定滿足以上不等式的一組碼長，則存在相應(yīng)的二進(jìn)制即時碼二進(jìn)制即時碼第k個碼字的碼長為lk考慮一棵lmax級二叉滿樹，在第lmax級共有2lmax個節(jié)點，在第lk級共有2lk個節(jié)點根據(jù)即時碼的定義，對lk≠lmax的第k個碼字，在第lmax級不能用的節(jié)點數(shù)為2lmax-lk，對lk=lmax的第k個碼字，第lmax級未用的節(jié)點數(shù)為1構(gòu)造二進(jìn)制即時碼的樹圖上總共不能用和未用的第lmax級節(jié)點總數(shù)第2級被用掉或不能用的節(jié)點總數(shù)為010100101反之，從樹根出發(fā)由短及長依次按碼長lk生長二叉樹枝，即可構(gòu)造出一顆lmax級二叉樹，相應(yīng)得到二進(jìn)制即時碼4.3漸進(jìn)最優(yōu)碼定理二進(jìn)制即時碼的平均碼長必定滿足不等式當(dāng)且僅當(dāng)2-lk=P(xk)k=1,2,…,Nn，等式成立對于n次擴(kuò)展信源n次擴(kuò)展信源的編碼效率對于n次擴(kuò)展信源n次擴(kuò)展信源的編碼效率4.4漸進(jìn)最優(yōu)碼碼長的界定理二進(jìn)制即時碼的平均碼長的取值范圍在其下界與下界加1比特之間，即滿足不等式對于n次擴(kuò)展信源4.5赫夫曼碼①將信源發(fā)出消息xkk=1,2,…,Nn按概率降序排列②為概率最小的兩條消息各自分配一個二進(jìn)制碼元③將概率最小的兩條消息合并成一條新消息，用兩者概率之和作為新消息的概率編碼步驟重復(fù)①②③步驟，直到合并出新消息的概率為1時結(jié)束，分配給消息xk的全部碼元作為該消息的碼字ckk=1,2,…,Nn例1編赫夫曼碼并計算編碼效率①將信源發(fā)出消息xkk=1,2,…,Nn按概率降序排列②為概率最小的兩條消息各自分配一個二進(jìn)制碼元③將概率最小的兩條消息合并成一條新消息，用兩者概率之和作為新消息的概率10重復(fù)①②③步驟，直到合并出新消息的概率為1時結(jié)束，分配給消息xk的全部碼元作為該消息的碼字ckk=1,2,…,Nn101010更緊湊的編碼過程描述101010例2分別對信源和二次擴(kuò)展信源編赫夫曼碼并計算編碼效率(1)信源編赫夫曼碼并計算編碼效率1010(2)二次擴(kuò)展信源編赫夫曼碼并計算編碼效率0.05100.09010.110010.19010.350.410100.61010.05100.09010.110010.19010.350.410100.6101例3兩種排列方式進(jìn)行赫夫曼編碼并計算平均碼長(1)排列方式1——合并后的新消息排在其它相同概率消息之后0.2100.410100.6101(1)排列方式2——合并后的