第4章 數(shù)據(jù)壓縮

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