【正文】 n個(gè)碼字構(gòu)成，與一一對應(yīng)。 ? 是符號集，由 m個(gè)碼元 構(gòu)成，符號集中間的碼元組成輸出碼字。 32 ? 當(dāng)信源發(fā)出某個(gè)隨機(jī)事件（消息）后，接收端收到一個(gè)相應(yīng)的碼字。 ? 那么，接收到的這個(gè)碼字中包含了多少有用的信息呢？ ? 信息是用不確定性的量度定義的。 ? 消息出現(xiàn)的可能性愈小，則其帶給人們的信息就愈多；反之，消息出現(xiàn)的可能性愈大，則它能給人們提供的新信息（有用信息）就愈少。 ? 在數(shù)學(xué)上，一條消息所傳輸?shù)男畔⑹瞧涑霈F(xiàn)概率的單調(diào)下降函數(shù)。 33 信息量 ? 信息量：從 N個(gè)可能事件中選出一個(gè)事件所需要的信息度量或含量。 ? 對于計(jì)算機(jī)的二進(jìn)制編碼，可以這么理解：從 N個(gè)事件中辨別出一個(gè)特定事件，最少需要回答多少次“ ”疑問。 ? 事實(shí)上，每次提問都會得到一個(gè)“ ”的答復(fù)，可以用 0或 1表示，即 1，如果提問n次，則信息量為。 34 示例 ? 例一：從 1～ 64的整數(shù)中選出一個(gè)數(shù)。 ? 可先提問“是否大于 32?”，以消除半數(shù)的可能，然后再進(jìn)行半數(shù)的詢問，這樣只需 6次便可確定一個(gè)數(shù)，其信息量為 6。 ? 例二：如果只要辨別某個(gè)數(shù)是否大于 32，則只需詢問一次便可得出結(jié)論，其信息量只有 1。 ? 從上兩例中可看出，大于或者小于 32，這種情況的概率比具體等于某一個(gè)數(shù)的概率要大，但其信息量反而小（單調(diào)下降）。 35 信息量的數(shù)學(xué)表述 ? 信息論定義了一種度量信息量的方法： ? 其中： ? I()是信源 X發(fā)出后，接收端接收到的信息量的量度。 ? P()是信源 X發(fā)出的先驗(yàn)概率，有： njxPxI jj ,.. .,3,2,1)(log)( 2 ??? ),2,1(1011njpp jnjj ???????請用上述公式求例一的信息量。 36 信息熵 ? 如果將信源所有可能事件的信息量進(jìn)行統(tǒng)計(jì)平均（即求其數(shù)學(xué)期望），就得到了信息熵。 ? 信源 X發(fā)出的（ 1,2,… ），出現(xiàn)的概率為P()，則信源 X的熵為： ? ? )(log)()()( 211jnjjjnjj xPxPxIxPXH ?????????37 示例 ? 假設(shè)一幅由 40個(gè)像素組成的灰度圖像，共有 5級灰度，每一級灰度都是一種信源發(fā)出的符號，分別用表示。 ? 40個(gè)像素中有 15個(gè)灰度為 A， 7個(gè)灰度為B， 7個(gè)灰度為 C， 6個(gè)灰度為 D， 5個(gè)灰度為 E。 ? 試求該灰度圖像的熵。 38 ∴ 該灰度圖像的熵為 。 ? ?405log405406log406407log407407log4074015log4015)(log)()()(22222211????????????????? ????jnjjjnjjxPxPxIxPXH39 統(tǒng)計(jì)編碼的目的 ? 統(tǒng)計(jì)編碼就根據(jù)信源信號出現(xiàn)概率的分布特性進(jìn)行壓縮的。 ? 統(tǒng)計(jì)編碼的目的： ? 在信源符號和碼字之間建立明確的一一對應(yīng)關(guān)系； ? 編碼過程中不丟失信息量（即信息熵的大小不變），以便在恢復(fù)時(shí)能準(zhǔn)確地再現(xiàn)原信號，實(shí)現(xiàn)無損壓縮； ? 平均碼長或碼率應(yīng)盡量小。 40 熵和平均碼長 ? 可用熵來衡量該編碼是否為最佳編碼： ? 當(dāng) ，有冗余，不是最佳； ? 當(dāng) ，不可能出現(xiàn)； ? 當(dāng) ，是最佳編碼（ 稍大于 ） ? 其中 表示編碼器輸出碼字的平均碼長。 ? 可見，熵值是平均碼長的下限。 )( xHN ?? )( xH? )( xN ??N )(xHN ???njjj LPN141 編碼 ? 最佳編碼定理： ? 在變字長碼中，對于出現(xiàn)概率大的信息符號編以短字長的碼，對于出現(xiàn)概率小的信息符號編以長字長的碼。 ? 如果碼字長度嚴(yán)格按照符號概率的大小的相反順序排列，則平均碼字長度一定小于按任何其他符號順序排列方式得到的碼字長度。 ? 編碼：利用了最佳編碼定理，是最常用的一種統(tǒng)計(jì)編碼。 42 ? 編碼方法先把信源符號按概率大小順序排列，并設(shè)法按逆次序分配碼字長度。 ? 對于出現(xiàn)頻率大的符號用較少的位數(shù)來表示；對于出現(xiàn)頻率小的符號用較多的位數(shù)來表示。 ? 編碼方法采用的碼字長度是可變的，因此較難在壓縮編碼后的文件中進(jìn)行內(nèi)容的查找。 43 編碼的思路 1. 把信源符號按概率大小順序排列，并設(shè)法按逆次序分配碼字的長度。 2. 在分配碼字長度時(shí)，首先將出現(xiàn)概率最小的兩個(gè)符號的概率相加合成一個(gè)概率。 3. 把這個(gè)合成概率看成是一個(gè)新組合符號地概率，重復(fù)上述做法直到最后只剩下兩個(gè)符號概率為止。 4. 完成以上概率順序排列后，再反過來逐步向前進(jìn)行編碼，每一次有二個(gè)分支各賦予一個(gè)二進(jìn)制碼，可以對概率大的賦為 0，概率小的賦為 1。 44 編碼的步驟 1. 對每個(gè)信息符號進(jìn)行概率統(tǒng)計(jì)； 2. 將信源符號按概率的遞減順序排列； 3. 將最后的兩個(gè)小概率相加作為新符號的概率， 此時(shí)概率個(gè)數(shù)將減少一個(gè)； 4. 重復(fù)第 3步，直到只剩兩個(gè)概率； 5. 將概率大的賦“ 0”，概率小的賦“ 1”； 6. 逆順序往信源符號推，不是合并的編碼不變，如果是合并的，則在編碼后面按照第 5步的方法添加 0或 1。 45 編碼實(shí)例 ? 信源 X有 7個(gè)信息符號，其概率為： ? 請對其進(jìn)行編碼，寫出其碼樹、碼長，并計(jì)算平均碼長和熵。 Ｘ 1 Ｘ 2 Ｘ 3 Ｘ 4 Ｘ 5 Ｘ 6 Ｘ 7 46 信息符號 概率 第 1步 第 2步 第 3步 第 4步 第 5步 Ｘ 1 Ｘ 2 Ｘ 3 Ｘ 4 Ｘ 5 Ｘ 6 Ｘ 7 0 1 1 00 01 00 01 10 11 00 10 11 010 011 00 10 010 011 110 111 00 10 010 011 110 1110 1111 47 ? 碼字的平均碼長為： ? 熵為： bitxPxPxPxPHjjjnjjj498 )()(log)()(log)(222222271212???????????????????? ????48 編碼小結(jié) ? 平均碼長大于熵，小于等長碼的碼長。 ? 編碼能保證解碼的唯一性，短碼字不會是長碼字的前綴。 ? 編碼沒有錯(cuò)誤保護(hù)功能。 ? 使用編碼時(shí)，接收端需保存一個(gè)與發(fā)送端完全相同的碼表。 ? 編碼在信源符號出現(xiàn)概率分布不均勻時(shí)編碼效率較高，若概率分別均勻時(shí)一般不采用編碼。 ? 編碼的壓縮比取決于信源符號出現(xiàn)的概率，越集中則壓縮比越高。 49 算術(shù)編碼 ? 20世紀(jì) 60年代初，首次提出了算術(shù)編碼的概念。 ? 1976年，發(fā)展了算術(shù)編碼的實(shí)用技術(shù)。 ? 算術(shù)編碼方法比編碼復(fù)雜，但它不需要接收端保存一份碼表，且具有自適應(yīng)能力。 ? 算術(shù)編碼是目前實(shí)現(xiàn)高效壓縮數(shù)據(jù)中很有前途的編碼方法。 50 基本原理和編碼步驟 ? 算術(shù)編碼實(shí)際上是用一個(gè)浮點(diǎn)數(shù)代替一個(gè)輸入流中的符號。 ? 將實(shí)數(shù)半開區(qū)間 [0, 1) 進(jìn)行分割，每一符號對應(yīng) [0, 1)上的一個(gè)子區(qū)間，區(qū)間長度為該符號出現(xiàn)的概率； ? 把要編碼的整段消息映射到 [0, 1)，根據(jù)這段消息符號的順序確定新的實(shí)數(shù)子區(qū)間； ? 最終得到一個(gè) [0,