信息論與編碼糾錯第3章-預覽頁
【正文】 碼字的映射不是一一對應的。 【 例 】 用 {u1 ， u2 ， u3， u4}表示信源的四個消息，碼符號集為 {0,1}，下表列出了該信源的幾種不同編碼。 編碼輸出碼字 cm = cm1 cm2 … cmn， c mk∈ {b1, b2,…, bD}， k = 1, 2 , …, n ， n表示碼字長度，簡稱 碼長 。 信息論與編碼 信源編碼的概念 ：對信源的原始符號按一定的數(shù)學規(guī)則進行變換的一種代碼。 （ 2）增強通信的可靠性： 如何增加信號的抗干擾能力，提高傳輸?shù)目煽啃?，這是信道編碼主要考慮的問題。 概 述 一．信源編碼的模型 為了實現(xiàn)高質(zhì)量、高效率的通信，引入了信源編碼和信道編碼。信息論與編碼 第三章 離散信源無失真編碼 信息論與編碼 內(nèi)容提要 用盡可能少的符號來傳輸信源消息，目的是提高傳輸效率，這是信源編碼應考慮的問題，這章討論在不允許失真情況下的信源編碼。 信息論與編碼 167。這里又分兩種情況討論，即允許接收信號有一定的失真或不允許失真。這樣，設計者在取舍之間就要作均衡考慮。 {b1, b2,…, bD}是適合信道傳輸?shù)?D個符號，用作信源編碼器的編碼符號。對于同一個信源，編碼方法是多種的。 3．變長碼 若碼字集合 C中的所有碼字 cm (m = 1,2, …,M) ，其碼長不都相同，稱碼 C為變長碼，例中列出的碼 碼 4 就是變長碼。 信源消息 各消息概率 碼 1 碼 2 碼 3 碼 4 u1 p(u1) 00 00 0 1 u2 p(u2) 11 01 1 10 u3 p(u3) 10 10 00 100 u4 p(u4) 11 11 11 1000 信息論與編碼 6．原碼 C的 N次擴展碼 原碼 C的 N次擴展碼中的每個元素是 N次擴展信源中的序列所對應的 N個碼字組成的序列。 對于定長碼，若原碼是惟一可譯碼，則它的 N次擴展碼也是惟一可譯的，而對于變長碼則不盡然。 碼 3是無前綴碼；其他都不是無前綴碼。 即時碼是惟一可譯碼，而惟一可譯碼不一定是即時碼。 0 10 10 11樹 根u1u2u3u4編 碼10 10 0 10 0 0 1信息論與編碼 碼的分類結(jié)構(gòu)圖 碼奇 異 碼 非 奇 異 碼唯 一 可 譯 碼 非 唯 一 可 譯 碼變 長 碼 等 長 碼即 時 碼 延 長 碼由上面的結(jié)構(gòu)圖可看出，將碼分為 奇異碼 和 非奇異碼 兩大類，我們只討論非奇異碼。 信息論與編碼 四．信息傳輸速率 定義 ：信道的信息傳輸速率為 信道單位時間內(nèi)所傳輸?shù)膶嶋H信息量 。 等長碼及等長編碼定理 一．等長編碼定理 考慮對一簡單信源 S進行等長編碼，信源符號集有 K個符號，碼符號集含 D個符號，碼字長度記為 n。 【 定理 】 等長編碼定理 設離散無記憶信源 S ={x1, x2, …, xk}的熵為 H(X)， S的 L維擴展信源為 ? ?12, , , L(L ) kS s s s?? ?logHXnLD???? ?logHXnLD???信息論與編碼 二．編碼效率 根據(jù)等長碼的編碼定理，我們可以得到一個衡量編碼質(zhì)量的重要指標，編碼效率。并做如下編碼： ，得到唯一可譯碼。對于變長碼，往往在 L不是很大的情況下就可編出高效且無失真的碼。對于給定信源，使平均碼長達到最小的編碼方法，稱為 最佳編碼 ，得到的碼集稱為 最佳碼 。 信息論與編碼 167。 l o g ( ) l o g ( ) 1m m mp x n p x? ? ? ? ?（－ log p (xm)為整數(shù)時取等號） （ 4）計算出第 m個消息的累加概率 ，再將 pi變換成二進制小數(shù)，取小數(shù)點后面 nm位作為第 m個消息的代碼組。 1 2 3 4 5 6 7( ) 0 . 2 0 . 1 9 0 . 1 8 0 . 1 7 0 . 1 5 0 . 1 0 0 . 0 1X x x x x x x xpX? ? ? ??? ? ? ?? ? ? ?xm p(xm) 第一次分解 第二次分解 第三次分解 第四次分解 代碼組 長度 nm x1 （ 0） （ 0） 00 2 x2 （ 1） （ 0） 010 3 x3 （ 1） 011 3 x4 （ 1） （ 0） 10 2 x5 （ 1） （ 0） 110 3 x6 （ 1） （ 0） 1110 4 x7 （ 1） 1111 4 信源熵： 71( ) ( ) l o g ( ) 2 . 6 1mmmH X p x p x?? ? ??比特 /符號 平均碼長： 71( ) 2 . 7 4mmmn p x n????碼元 /符號 編碼效率： ( ) 2 . 6 1 0 . 9 3 5l o g 2 . 7 4 l o g 2HXnD? ? ? ??信息論與編碼 霍夫曼編碼法的具體步驟如下：（先考慮 D =2的情況） （ 1）將信源發(fā)出的 M個消息，按其概率遞減順序進行排列，得 p(x1 ) ? p(x2 ) ? p(x3) ? … ? p(xM ) （ 2）將概率最小的二個消息分別編碼為“ 1”和“ 0”，（一般，將概率大的編碼為“ 1”，概率小的編碼為“ 0”），再對這兩個消息求概率之和； （ 3）將上述概率之和作為一新消息的概率，與余下的消息一起組成一新的信源，再按概率遞減順序重新排列，如果概率之和與原信源的某個概率相等，則把概率之和排在上面，這樣可使合并消息重復編碼的次數(shù)減少，使短碼得到充分利用； （ 4）如此一直進行下去，直到兩個合并消息的概率之和為 1； （ 5）從最后一步驟開始，沿編碼逆程取下各步驟得到的碼符號，如此構(gòu)成的碼符號序列即為對應消息的碼字。 一．等長編碼定理 記 H（ X）為單符號信源熵， L為擴展信源輸出序列長度， n為碼字長度，D為碼符號集元素個數(shù)，當滿足條件 ? ?l ogHXnLD???則 L →∞ 時，可使譯碼差錯 pe δ(ε、 δ為無窮小量 )； 反之， ? ?logHXnLD???則不可能實現(xiàn)無差錯編碼。
高考資料相關推薦
鄂ICP備17016276號-1