導航:首頁 > 源碼編譯 > lzw編解碼平均碼長和信息熵

lzw編解碼平均碼長和信息熵

發布時間:2022-09-28 13:15:50

㈠ 數據壓縮技術的數據壓縮技術簡史

電腦里的數據壓縮其實類似於美眉們的瘦身運動,不外有兩大功用。第一,可以節省空間。拿瘦身美眉來說,要是八個美眉可以擠進一輛計程車里,那該有多省錢啊!第二,可以減少對帶寬的佔用。例如,我們都想在不到 100Kbps 的 GPRS 網上觀看 DVD 大片,這就好比瘦身美眉們總希望用一尺布裁出七件吊帶衫,前者有待於數據壓縮技術的突破性進展,後者則取決於美眉們的恆心和毅力。
簡單地說,如果沒有數據壓縮技術,我們就沒法用 WinRAR 為 Email 中的附件瘦身;如果沒有數據壓縮技術,市場上的數碼錄音筆就只能記錄不到 20 分鍾的語音;如果沒有數據壓縮技術,從 Internet 上下載一部電影也許要花半年的時間……可是這一切究竟是如何實現的呢?數據壓縮技術又是怎樣從無到有發展起來的呢? 一千多年前的中國學者就知道用「班馬」這樣的縮略語來指代班固和司馬遷,這種崇尚簡約的風俗一直延續到了今天的 Internet 時代:當我們在 BBS 上用「 7456 」代表「氣死我了」,或是用「 B4 」代表「 Before 」的時候,我們至少應該知道,這其實就是一種最簡單的數據壓縮呀。
嚴格意義上的數據壓縮起源於人們對概率的認識。當我們對文字信息進行編碼時,如果為出現概率較高的字母賦予較短的編碼,為出現概率較低的字母賦予較長的編碼,總的編碼長度就能縮短不少。遠在計算機出現之前,著名的 Morse 電碼就已經成功地實踐了這一準則。在 Morse 碼表中,每個字母都對應於一個唯一的點劃組合,出現概率最高的字母 e 被編碼為一個點「 . 」,而出現概率較低的字母 z 則被編碼為「 --.. 」。顯然,這可以有效縮短最終的電碼長度。
資訊理論之父 C. E. Shannon 第一次用數學語言闡明了概率與信息冗餘度的關系。在 1948 年發表的論文「通信的數學理論( A Mathematical Theory of Communication )」中, Shannon 指出,任何信息都存在冗餘,冗餘大小與信息中每個符號(數字、字母或單詞)的出現概率或者說不確定性有關。 Shannon 借鑒了熱力學的概念,把信息中排除了冗餘後的平均信息量稱為「信息熵」,並給出了計算信息熵的數學表達式。這篇偉大的論文後來被譽為資訊理論的開山之作,信息熵也奠定了所有數據壓縮演算法的理論基礎。從本質上講,數據壓縮的目的就是要消除信息中的冗餘,而信息熵及相關的定理恰恰用數學手段精確地描述了信息冗餘的程度。利用信息熵公式,人們可以計算出信息編碼的極限,即在一定的概率模型下,無損壓縮的編碼長度不可能小於信息熵公式給出的結果。
有了完備的理論,接下來的事就是要想辦法實現具體的演算法,並盡量使演算法的輸出接近信息熵的極限了。當然,大多數工程技術人員都知道,要將一種理論從數學公式發展成實用技術,就像僅憑一個 E=mc 2 的公式就要去製造核武器一樣,並不是一件很容易的事。 設計具體的壓縮演算法的過程通常更像是一場數學游戲。開發者首先要尋找一種能盡量精確地統計或估計信息中符號出現概率的方法,然後還要設計一套用最短的代碼描述每個符號的編碼規則。統計學知識對於前一項工作相當有效,迄今為止,人們已經陸續實現了靜態模型、半靜態模型、自適應模型、 Markov 模型、部分匹配預測模型等概率統計模型。相對而言,編碼方法的發展歷程更為曲折一些。
1948 年, Shannon 在提出信息熵理論的同時,也給出了一種簡單的編碼方法—— Shannon 編碼。 1952 年, R. M. Fano 又進一步提出了 Fano 編碼。這些早期的編碼方法揭示了變長編碼的基本規律,也確實可以取得一定的壓縮效果,但離真正實用的壓縮演算法還相去甚遠。
第一個實用的編碼方法是由 D. A. Huffman 在 1952 年的論文「最小冗餘度代碼的構造方法( A Method for the Construction of Minimum Rendancy Codes )」中提出的。直到今天,許多《數據結構》教材在討論二叉樹時仍要提及這種被後人稱為 Huffman 編碼的方法。 Huffman 編碼在計算機界是如此著名,以至於連編碼的發明過程本身也成了人們津津樂道的話題。據說, 1952 年時,年輕的 Huffman 還是麻省理工學院的一名學生,他為了向老師證明自己可以不參加某門功課的期末考試,才設計了這個看似簡單,但卻影響深遠的編碼方法。
Huffman 編碼效率高,運算速度快,實現方式靈活,從 20 世紀 60 年代至今,在數據壓縮領域得到了廣泛的應用。例如,早期 UNIX 系統上一個不太為現代人熟知的壓縮程序 COMPACT 實際就是 Huffman 0 階自適應編碼的具體實現。 20 世紀 80 年代初, Huffman 編碼又出現在 CP/M 和 DOS 系統中,其代表程序叫 SQ 。今天,在許多知名的壓縮工具和壓縮演算法(如 WinRAR 、 gzip 和 JPEG )里,都有 Huffman 編碼的身影。不過, Huffman 編碼所得的編碼長度只是對信息熵計算結果的一種近似,還無法真正逼近信息熵的極限。正因為如此,現代壓縮技術通常只將 Huffman 視作最終的編碼手段,而非數據壓縮演算法的全部。
科學家們一直沒有放棄向信息熵極限挑戰的理想。 1968 年前後, P. Elias 發展了 Shannon 和 Fano 的編碼方法,構造出從數學角度看來更為完美的 Shannon-Fano-Elias 編碼。沿著這一編碼方法的思路, 1976 年, J. Rissanen 提出了一種可以成功地逼近信息熵極限的編碼方法——算術編碼。 1982 年, Rissanen 和 G. G. Langdon 一起改進了算術編碼。之後,人們又將算術編碼與 J. G. Cleary 和 I. H. Witten 於 1984 年提出的部分匹配預測模型( PPM )相結合,開發出了壓縮效果近乎完美的演算法。今天,那些名為 PPMC 、 PPMD 或 PPMZ 並號稱壓縮效果天下第一的通用壓縮演算法,實際上全都是這一思路的具體實現。
對於無損壓縮而言, PPM 模型與算術編碼相結合,已經可以最大程度地逼近信息熵的極限。看起來,壓縮技術的發展可以到此為止了。不幸的是,事情往往不像想像中的那樣簡單:算術編碼雖然可以獲得最短的編碼長度,但其本身的復雜性也使得算術編碼的任何具體實現在運行時都慢如蝸牛。即使在摩爾定律大行其道, CPU 速度日新月異的今天,算術編碼程序的運行速度也很難滿足日常應用的需求。沒辦法,如果不是後文將要提到的那兩個猶太人,我們還不知要到什麼時候才能用上 WinZIP 這樣方便實用的壓縮工具呢。 逆向思維永遠是科學和技術領域里出奇制勝的法寶。就在大多數人絞盡腦汁想改進 Huffman 或算術編碼,以獲得一種兼顧了運行速度和壓縮效果的「完美」編碼的時候,兩個聰明的猶太人 J. Ziv 和 A. Lempel 獨辟蹊徑,完全脫離 Huffman 及算術編碼的設計思路,創造出了一系列比 Huffman 編碼更有效,比算術編碼更快捷的壓縮演算法。我們通常用這兩個猶太人姓氏的縮寫,將這些演算法統稱為 LZ 系列演算法。
按照時間順序, LZ 系列演算法的發展歷程大致是: Ziv 和 Lempel 於 1977 年發表題為「順序數據壓縮的一個通用演算法( A Universal Algorithm for Sequential Data Compression )」的論文,論文中描述的演算法被後人稱為 LZ77 演算法。 1978 年,二人又發表了該論文的續篇「通過可變比率編碼的獨立序列的壓縮( Compression of Indivial Sequences via Variable Rate Coding )」,描述了後來被命名為 LZ78 的壓縮演算法。 1984 年, T. A. Welch 發表了名為「高性能數據壓縮技術( A Technique for High Performance Data Compression )」的論文,描述了他在 Sperry 研究中心(該研究中心後來並入了 Unisys 公司)的研究成果,這是 LZ78 演算法的一個變種,也就是後來非常有名的 LZW 演算法。 1990 年後, T. C. Bell 等人又陸續提出了許多 LZ 系列演算法的變體或改進版本。
說實話, LZ 系列演算法的思路並不新鮮,其中既沒有高深的理論背景,也沒有復雜的數學公式,它們只是簡單地延續了千百年來人們對字典的追崇和喜好,並用一種極為巧妙的方式將字典技術應用於通用數據壓縮領域。通俗地說,當你用字典中的頁碼和行號代替文章中每個單詞的時候,你實際上已經掌握了 LZ 系列演算法的真諦。這種基於字典模型的思路在表面上雖然和 Shannon 、 Huffman 等人開創的統計學方法大相徑庭,但在效果上一樣可以逼近信息熵的極限。而且,可以從理論上證明, LZ 系列演算法在本質上仍然符合信息熵的基本規律。
LZ 系列演算法的優越性很快就在數據壓縮領域里體現 了 出來,使用 LZ 系列演算法的工具軟體數量呈爆炸式增長。 UNIX 系統上最先出現了使用 LZW 演算法的 compress 程序,該程序很快成為了 UNIX 世界的壓縮標准。緊隨其後的是 MS-DOS 環境下的 ARC 程序,以及 PKWare 、 PKARC 等仿製品。 20 世紀 80 年代,著名的壓縮工具 LHarc 和 ARJ 則是 LZ77 演算法的傑出代表。
今天, LZ77 、 LZ78 、 LZW 演算法以及它們的各種變體幾乎壟斷了整個通用數據壓縮領域,我們熟悉的 PKZIP 、 WinZIP 、 WinRAR 、 gzip 等壓縮工具以及 ZIP 、 GIF 、 PNG 等文件格式都是 LZ 系列演算法的受益者,甚至連 PGP 這樣的加密文件格式也選擇了 LZ 系列演算法作為其數據壓縮的標准。
沒有誰能否認兩位猶太人對數據壓縮技術的貢獻。我想強調的只是,在工程技術領域,片面追求理論上的完美往往只會事倍功半,如果大家能像 Ziv 和 Lempel 那樣,經常換個角度來思考問題,沒准兒你我就能發明一種新的演算法,就能在技術方展史上揚名立萬呢。 LZ 系列演算法基本解決了通用數據壓縮中兼顧速度與壓縮效果的難題。但是,數據壓縮領域里還有另一片更為廣闊的天地等待著我們去探索。 Shannon 的資訊理論告訴我們,對信息的先驗知識越多,我們就可以把信息壓縮得越小。換句話說,如果壓縮演算法的設計目標不是任意的數據源,而是基本屬性已知的特種數據,壓縮的效果就會進一步提高。這提醒我們,在發展通用壓縮演算法之餘,還必須認真研究針對各種特殊數據的專用壓縮演算法。比方說,在今天的數碼生活中,遍布於數碼相機、數碼錄音筆、數碼隨身聽、數碼攝像機等各種數字設備中的圖像、音頻、視頻信息,就必須經過有效的壓縮才能在硬碟上存儲或是通過 USB 電纜傳輸。實際上,多媒體信息的壓縮一直是數據壓縮領域里的重要課題,其中的每一個分支都有可能主導未來的某個技術潮流,並為數碼產品、通信設備和應用軟體開發商帶來無限的商機。
讓我們先從圖像數據的壓縮講起。通常所說的圖像可以被分為二值圖像、灰度圖像、彩色圖像等不同的類型。每一類圖像的壓縮方法也不盡相同。
傳真技術的發明和廣泛使用促進了二值圖像壓縮演算法的飛速發展。 CCITT (國際電報電話咨詢委員會,是國際電信聯盟 ITU 下屬的一個機構)針對傳真類應用建立了一系列圖像壓縮標准,專用於壓縮和傳遞二值圖像。這些標准大致包括 20 世紀 70 年代後期的 CCITT Group 1 和 Group 2 , 1980 年的 CCITT Group 3 ,以及 1984 年的 CCITT Group 4 。為了適應不同類型的傳真圖像,這些標准所用的編碼方法包括了一維的 MH 編碼和二維的 MR 編碼,其中使用了行程編碼( RLE )和 Huffman 編碼等技術。今天,我們在辦公室或家裡收發傳真時,使用的大多是 CCITT Group 3 壓縮標准,一些基於數字網路的傳真設備和存放二值圖像的 TIFF 文件則使用了 CCITT Group 4 壓縮標准。 1993 年, CCITT 和 ISO (國際標准化組織)共同成立的二值圖像聯合專家組( Joint Bi-level Image Experts Group , JBIG )又將二值圖像的壓縮進一步發展為更加通用的 JBIG 標准。
實際上,對於二值圖像和非連續的灰度、彩色圖像而言,包括 LZ 系列演算法在內的許多通用壓縮演算法都能獲得很好的壓縮效果。例如,誕生於 1987 年的 GIF 圖像文件格式使用的是 LZW 壓縮演算法, 1995 年出現的 PNG 格式比 GIF 格式更加完善,它選擇了 LZ77 演算法的變體 zlib 來壓縮圖像數據。此外,利用前面提到過的 Huffman 編碼、算術編碼以及 PPM 模型,人們事實上已經構造出了許多行之有效的圖像壓縮演算法。
但是,對於生活中更加常見的,像素值在空間上連續變化的灰度或彩色圖像(比如數碼照片),通用壓縮演算法的優勢就不那麼明顯了。幸運的是,科學家們發現,如果在壓縮這一類圖像數據時允許改變一些不太重要的像素值,或者說允許損失一些精度(在壓縮通用數據時,我們絕不會容忍任何精度上的損失,但在壓縮和顯示一幅數碼照片時,如果一片樹林里某些樹葉的顏色稍微變深了一些,看照片的人通常是察覺不到的),我們就有可能在壓縮效果上獲得突破性的進展。這一思想在數據壓縮領域具有革命性的地位:通過在用戶的忍耐范圍內損失一些精度,我們可以把圖像(也包括音頻和視頻)壓縮到原大小的十分之一、百分之一甚至千分之一,這遠遠超出了通用壓縮演算法的能力極限。也許,這和生活中常說的「退一步海闊天空」的道理有異曲同工之妙吧。
這種允許精度損失的壓縮也被稱為有損壓縮。在圖像壓縮領域,著名的 JPEG 標準是有損壓縮演算法中的經典。 JPEG 標准由靜態圖像聯合專家組( Joint Photographic Experts Group , JPEG )於 1986 年開始制定, 1994 年後成為國際標准。 JPEG 以離散餘弦變換( DCT )為核心演算法,通過調整質量系數控制圖像的精度和大小。對於照片等連續變化的灰度或彩色圖像, JPEG 在保證圖像質量的前提下,一般可以將圖像壓縮到原大小的十分之一到二十分之一。如果不考慮圖像質量, JPEG 甚至可以將圖像壓縮到「無限小」。
JPEG 標準的最新進展是 1996 年開始制定, 2001 年正式成為國際標準的 JPEG 2000 。與 JPEG 相比, JPEG 2000 作了大幅改進,其中最重要的是用離散小波變換( DWT )替代了 JPEG 標准中的離散餘弦變換。在文件大小相同的情況下, JPEG 2000 壓縮的圖像比 JPEG 質量更高,精度損失更小。作為一個新標准, JPEG 2000 暫時還沒有得到廣泛的應用,不過包括數碼相機製造商在內的許多企業都對其應用前景表示樂觀, JPEG 2000 在圖像壓縮領域里大顯身手的那一天應該不會特別遙遠。
JPEG 標准中通過損失精度來換取壓縮效果的設計思想直接影響了視頻數據的壓縮技術。 CCITT 於 1988 年制定了電視電話和會議電視的 H.261 建議草案。 H.261 的基本思路是使用類似 JPEG 標準的演算法壓縮視頻流中的每一幀圖像,同時採用運動補償的幀間預測來消除視頻流在時間維度上的冗餘信息。在此基礎上, 1993 年, ISO 通過了動態圖像專家組( Moving Picture Experts Group , MPEG )提出的 MPEG-1 標准。 MPEG-1 可以對普通質量的視頻數據進行有效編碼。我們現在看到的大多數 VCD 影碟,就是使用 MPEG-1 標准來壓縮視頻數據的。
為了支持更清晰的視頻圖像,特別是支持數字電視等高端應用, ISO 於 1994 年提出了新的 MPEG-2 標准(相當於 CCITT 的 H.262 標准)。 MPEG-2 對圖像質量作了分級處理,可以適應普通電視節目、會議電視、高清晰數字電視等不同質量的視頻應用。在我們的生活中,可以提供高清晰畫面的 DVD 影碟所採用的正是 MPEG-2 標准。
Internet 的發展對視頻壓縮提出了更高的要求。在內容交互、對象編輯、隨機存取等新需求的刺激下, ISO 於 1999 年通過了 MPEG-4 標准(相當於 CCITT 的 H.263 和 H.263+ 標准)。 MPEG-4 標准擁有更高的壓縮比率,支持並發數據流的編碼、基於內容的交互操作、增強的時間域隨機存取、容錯、基於內容的尺度可變性等先進特性。 Internet 上新興的 DivX 和 XviD 文件格式就是採用 MPEG-4 標准來壓縮視頻數據的,它們可以用更小的存儲空間或通信帶寬提供與 DVD 不相上下的高清晰視頻,這使我們在 Internet 上發布或下載數字電影的夢想成為了現實。
就像視頻壓縮和電視產業的發展密不可分一樣,音頻數據的壓縮技術最早也是由無線電廣播、語音通信等領域里的技術人員發展起來的。這其中又以語音編碼和壓縮技術的研究最為活躍。自從 1939 年 H. Dudley 發明聲碼器以來,人們陸續發明了脈沖編碼調制( PCM )、線性預測( LPC )、矢量量化( VQ )、自適應變換編碼( ATC )、子帶編碼( SBC )等語音分析與處理技術。這些語音技術在採集語音特徵,獲取數字信號的同時,通常也可以起到降低信息冗餘度的作用。像圖像壓縮領域里的 JPEG 一樣,為獲得更高的編碼效率,大多數語音編碼技術都允許一定程度的精度損失。而且,為了更好地用二進制數據存儲或傳送語音信號,這些語音編碼技術在將語音信號轉換為數字信息之後又總會用 Huffman 編碼、算術編碼等通用壓縮演算法進一步減少數據流中的冗餘信息。
對於電腦和數字電器(如數碼錄音筆、數碼隨身聽)中存儲的普通音頻信息,我們最常使用的壓縮方法主要是 MPEG 系列中的音頻壓縮標准。例如, MPEG-1 標准提供了 Layer I 、 Layer II 和 Layer III 共三種可選的音頻壓縮標准, MPEG-2 又進一步引入了 AAC ( Advanced Audio Coding )音頻壓縮標准, MPEG-4 標准中的音頻部分則同時支持合成聲音編碼和自然聲音編碼等不同類型的應用。在這許多音頻壓縮標准中,聲名最為顯赫的恐怕要數 MPEG-1 Layer III ,也就是我們常說的 MP3 音頻壓縮標准了。從 MP3 播放器到 MP3 手機,從硬碟上堆積如山的 MP3 文件到 Internet 上版權糾紛不斷的 MP3 下載, MP3 早已超出了數據壓縮技術的范疇,而成了一種時尚文化的象徵了。
很顯然,在多媒體信息日益成為主流信息形態的數字化時代里,數據壓縮技術特別是專用於圖像、音頻、視頻的數據壓縮技術還有相當大的發展空間——畢竟,人們對信息數量和信息質量的追求是永無止境的。 從信息熵到算術編碼,從猶太人到 WinRAR ,從 JPEG 到 MP3 ,數據壓縮技術的發展史就像是一個寫滿了「創新」、「挑戰」、「突破」和「變革」的羊皮卷軸。也許,我們在這里不厭其煩地羅列年代、人物、標准和文獻,其目的只是要告訴大家,前人的成果只不過是後人有望超越的目標而已,誰知道在未來的幾年裡,還會出現幾個 Shannon ,幾個 Huffman 呢?
談到未來,我們還可以補充一些與數據壓縮技術的發展趨勢有關的話題。
1994年, M. Burrows 和 D. J. Wheeler 共同提出了一種全新的通用數據壓縮演算法。這種演算法的核心思想是對字元串輪轉後得到的字元矩陣進行排序和變換,類似的變換演算法被稱為 Burrows-Wheeler 變換,簡稱 BWT 。與 Ziv 和 Lempel 另闢蹊徑的做法如出一轍, Burrows 和 Wheeler 設計的 BWT 演算法與以往所有通用壓縮演算法的設計思路都迥然不同。如今, BWT 演算法在開放源碼的壓縮工具 bzip 中獲得了巨大的成功, bzip 對於文本文件的壓縮效果要遠好於使用 LZ 系列演算法的工具軟體。這至少可以表明,即便在日趨成熟的通用數據壓縮領域,只要能在思路和技術上不斷創新,我們仍然可以找到新的突破口。
分形壓縮技術是圖像壓縮領域近幾年來的一個熱點。這一技術起源於 B. Mandelbrot 於 1977 年創建的分形幾何學。 M. Barnsley 在 20 世紀 80 年代後期為分形壓縮奠定了理論基礎。從 20 世紀 90 年代開始, A. Jacquin 等人陸續提出了許多實驗性的分形壓縮演算法。今天,很多人相信,分形壓縮是圖像壓縮領域里最有潛力的一種技術體系,但也有很多人對此不屑一顧。無論其前景如何,分形壓縮技術的研究與發展都提示我們,在經過了幾十年的高速發展之後,也許,我們需要一種新的理論,或是幾種更有效的數學模型,以支撐和推動數據壓縮技術繼續向前躍進。
人工智慧是另一個可能對數據壓縮的未來產生重大影響的關鍵詞。既然 Shannon 認為,信息能否被壓縮以及能在多大程度上被壓縮與信息的不確定性有直接關系,假設人工智慧技術在某一天成熟起來,假設計算機可以像人一樣根據已知的少量上下文猜測後續的信息,那麼,將信息壓縮到原大小的萬分之一乃至十萬分之一,恐怕就不再是天方夜譚了。
回顧歷史之後,人們總喜歡暢想一下未來。但未來終究是未來,如果僅憑你我幾句話就可以理清未來的技術發展趨勢,那技術創新的工作豈不就索然無味了嗎?依我說,未來並不重要,重要的是,趕快到 Internet 上下載幾部大片,然後躺在沙發里,好好享受一下數據壓縮為我們帶來的無限快樂吧。

㈡ 關於哈夫曼編碼試題的計算

太復雜了,樓主一會記得多給我點分!謝謝啦!
先設權w=(31,22,18,14,10,4,1),n=7,則m=13,按照哈夫曼演算法可以構造一棵哈夫曼樹如下:
100
40 60
22 18 31 29
14 15
10 5
4 1
末端結點為22,18,31,14,10,4,1,你自己把上面的加上線連成一棵二叉樹就行,記得左分支標0,右分支標1(為了得出後面的哈夫曼編碼HC)
然後需要列出HT初態表和HT終態表,如下:
HT初態表 HT終態表
weight parent lchild rchild weight parent lchild rchild
1 31 0 0 0 31 12 0 0
2 22 0 0 0 22 11 0 0
3 18 0 0 0 18 11 0 0
4 14 0 0 0 14 10 0 0
5 10 0 0 0 10 9 0 0
6 4 0 0 0 4 8 0 0
7 1 0 0 0 1 8 0 0
8 - 0 0 0 5 9 6 7
9 - 0 0 0 15 10 5 8
10 - 0 0 0 29 12 4 9
11 - 0 0 0 40 13 2 3
12 - 0 0 0 60 13 1 10
13 - 0 0 0 100 0 11 12
最後得出哈夫曼編碼HC:
1——>10
2——>00
3——>01
4——>110
5——>1110
6——>11110
7——>11111
平均碼字長度為(0.31+0.22+0.18)×2+0.14×3+0.1×4
+(0.04+0.01)×5=2.47
編碼效率為[(1-0.01)×3+0.01×2]/2.47=1.21
解答完畢!
補充:對於其中的編碼效率問題本人有點淡忘,我選擇的是用
普通平均編碼長度除上了哈夫曼平均編碼長度得出,不知對否。
辛苦半天,望樓主能賜我分數,不勝感激!
註:提交後發現格式不太規整,對於哈夫曼樹誰是誰的左孩子、右孩子比較容易分出(左右孩子結點相加可知父親結點),對於HT初態表和HT終態表1列1列的看就行!其中數字第一列為序號,從第2列到第9列分別對應HT初態表的weight parent lchild rchild 和HT終態表的weight parent lchild rchild 。

㈢ 怎樣用c++實現香農-范諾編碼

#include"iostream.h"
#include<iomanip.h>
#include"vector"
#include"algorithm"
#include"math.h"
using namespace std;
struct bitree
{//定義結構用於存儲編碼結果的二叉樹結構,在解碼時用到
char ch; //用於存儲碼符號
char mz; //用於存儲碼字
bitree * lchild;
bitree * rchild;

};
struct data
{//用於存儲相關的信源符號以及其概率
double p;
char ch;
vector<char> code;
int ml;
};
bool sortspecial(data dt1,data dt2)
{//用於排序時用
return dt1.p>dt2.p;
}
void print2(vector<char>vd)
{//用於列印解碼結果
for(int i=0;i<vd.size();i++)
cout<<vd[i]<<" ";
cout<<endl;
}
void read(vector <data> &vd)
{//用於讀入相關的信源符號以及概率
int n;
while(true)
{
cout<<"請輸入信源符號數:";
cin>>n;
cout<<"請輸入相應的信源符號及其概率:"<<endl;
data dt;
int i=0;
while(i<n)
{
cin>>dt.ch;
cin>>dt.p;
dt.ml=0;
vd.push_back(dt);
i++;

}
double sum=0;
vector<data>::iterator pit;
/* for(pit=vd.begin();pit!=vd.end();pit++)
{
sum+=pit->p;
}
if(sum!=1)
{
cout<<"你輸入的概率不符合要求,請重新輸入."<<endl;
sum=0;
continue;
}*/
sort(vd.begin(),vd.end(),sortspecial);
break;
}
}

void append(char ch1,char ch2,bitree *&bt)
{//用於再構造碼字二叉樹時向其中添加結點
bitree * bit=new bitree;
bit->ch=ch1;
bit->mz=ch2;
bit->lchild=NULL;
bit->rchild=NULL;
if(ch1=='0')
bt->rchild=bit;
else bt->lchild=bit;
}
void Creatmz1(vector<data>& vd,int begin1,int end1 ,double pn ,bitree *&bt)
{//進行編碼,用遞歸的方法進行編碼
int begin=begin1,end=end1;
if(begin==end) return;
else if(begin+1==end)
{
return;
}
else if(begin+2==end){
vd[begin].code.push_back('0');
vd[begin].ml++;
append('0',vd[begin].ch,bt);
vd[end-1].code.push_back('1');
vd[end-1].ml++;
append('1',vd[end-1].ch,bt);
return;
}
else{
double sum0=0,sum1=0,sum2=0;
do{
sum1+=vd[begin].p;
sum2=sum1+vd[begin+1].p;
begin++;
}while(fabs(sum1/pn-0.5)>fabs(sum2/pn-0.5));//用於找到上下兩組碼的分點使得其概率和近於相同
for(int i=begin1;i<begin;i++){
vd[i].code.push_back('0');
vd[i].ml++;
}
if(begin1+1 == begin){
append('0',vd[begin1].ch,bt);
}
else append('0','0',bt);
for(int j=begin;j<=end1-1;j++){
vd[j].code.push_back('1');
vd[j].ml++;
}
if(begin+1 == end1){
append('1',vd[begin].ch,bt);
}
else append('1','0',bt);
Creatmz1(vd,begin1 ,begin,sum1,bt->rchild );//對分點前的進行編碼
Creatmz1(vd,begin ,end1,pn-sum1,bt->lchild);//對分點後的進行編碼*/

}
}
void print1(vector<data> vd)
{//用於列印編碼結果
cout<<"xi"<<setw(8)<<"P(xi)"<<setw(8)<<"碼長"
<<setw(8)<<"碼字"<<setw(8)<<endl;
for(int i=0;i<vd.size();i++){
cout<<vd[i].ch<<setw(8)<<vd[i].p<<setw(8)<<vd[i].ml<<setw(8);
for(int j=0;j<vd[i].code.size();j++)
cout<<vd[i].code[j];
cout<<setw(8)<<endl;
}
}

void clear(bitree * & bt)
{//對二叉樹的動態存儲空間進行釋放
if(bt!=NULL&&bt->lchild!=NULL)
clear(bt->lchild);
if(bt!=NULL&&bt->rchild!=NULL)
clear(bt->rchild);
delete bt;
}

bool des_code(vector <char> & vr,vector <char> vt,bitree *bt)
{//用二叉編碼樹進行解碼
if(bt==NULL)
{
cout<<"碼樹不存在!!!"<<endl;
return false;
}
int pit=0;
bitree * mbt=bt;
while ((mbt->lchild!=NULL||mbt->rchild!=NULL)||pit<vt.size())
{
if(mbt->lchild==NULL&&mbt->rchild==NULL&&mbt->mz!='0')
{
vr.push_back(mbt->mz);
mbt=bt;
}
if(mbt->lchild!=NULL&& vt[pit]=='1')
{
mbt=mbt->lchild;
pit++;
}
else if(mbt->rchild!=NULL&& vt[pit]=='0')
{
mbt=mbt->rchild;
pit++;
}
else if(mbt->lchild!=NULL&&mbt->rchild!=NULL) break;
}
if(mbt->lchild!=NULL&&mbt->rchild!=NULL)
{
cout<<"你輸入的是一個錯誤的碼序列,請較正後再輸入."<<endl;
return false;
}
else {
vr.push_back(mbt->mz);
return true;
}
}
void read1(vector<char>& vd)
{//用於讀入要解碼的序列
cout<<"請輸要解碼的序列(以'#'結束):"<<endl;
char dt;
int i=0;
cin>>dt;
while(dt!='#')
{
vd.push_back(dt);
cin>>dt;
}
}

void print_H_L_R(vector<data>vd)
{//用於計算並列印信息熵,平均碼長,效率
double H=0,L=0,R=0;
for(int i=0;i<vd.size();i++)
{
H+=vd[i].p*(log10(1/vd[i].p)/log10(2));
L+=vd[i].p*(double)vd[i].ml;
}
R=H/L;
cout<<"此碼的信息熵(H)是:"<<H<<endl;
cout<<"此碼的平均碼長(L)為:"<<L<<endl;
cout<<"此碼的效率(U)為:"<<R<<endl;
}
int main()
{
bitree * bt=new bitree;
bt->ch = '#';
bt->mz = '*';
bt->lchild=NULL;
bt->rchild=NULL;
vector <data> vd;
vector <char> vr;
vector <char> vt;
cout<<"************下面將對Fano編,解碼的過程進行演示*************"<<endl;
cout<<"__________________________________________________________"<<endl;
cout<<endl;
cout<<"************下面顯示編碼的過程及相關參數和結果************"<<endl;
read(vd);
if(vd.size()==1)
{
vd[0].code.push_back('0');
vd[0].ml++;
append('0',vd[0].ch,bt);
}
cout<<endl;
Creatmz1(vd,0,vd.size(),1,bt);
cout<<"************** 編碼結果 **************"<<endl;
print1(vd);
print_H_L_R(vd);
cout<<endl;
cout<<"************ 下面將進行解碼過程操作的演示 ************"<<endl;
cout<<endl;
read1(vt);
if(des_code(vr,vt,bt))
print2(vr);
clear(bt);
return 1;
}

一定要提高懸賞分喲。

㈣ 什麼是信源在允許一定失真的條件下,信源熵所能壓縮的極限

1.統計編碼原理──信息量和信息熵

根據香農資訊理論的原理,最佳的數據壓縮方法的理論極限是信息熵。如果要求在編碼過程中不丟失信息量,即要求保存信息熵,這種信息保持的編碼又叫熵保存編碼,或叫熵編碼。熵編碼是無失真壓縮。當然在考慮人眼失真不易察覺的生理特性時,有些圖像編碼不嚴格要求熵保存,信息允許通過部分損失來換取高的數據壓縮比。這種編碼屬於有失真數據壓縮。
信息是用不確定性的量度定義的,也就是說信息被假設為由一系列的隨機變數所代表,它們往往用隨機出現的符號來表示。我們稱輸出這些符號的源為「信源」。也就是要進行研究與壓縮的對象。 信息量

信息量指從N個相等可能事件中選出一個事件所需要的信息度量或含量,也可以說是辨別N個事件中特定事件過程中所需提問「是」或「否」的最小次數。
例如:從64個數(1~64的整數)中選定某一個數(採用折半查找演算法),提問:「是否大於32?」,則不論回答是與否,都消去半數的可能事件,如此下去,只要問6次這類問題,就可以從64個數中選定一個數,則所需的信息量是 =6(bit)。 我們現在可以換一種方式定義信息量,也就是資訊理論中信息量的定義。
設從N中選定任一個數X的概率為P(x),假定任選一個數的概率都相等,即P(x)=1/N,則信息量I (x)可定義為:

上式可隨對數所用「底」的不同而取不同的值,因而其單位也就不同。設底取大於1的整數α,考慮一般物理器件的二態性,通常α取2,相應的信息量單位為比特(bit);當α=e,相應的信息量單位為奈特(Nat);當α=10,相應的信息量單位為哈特(Hart)。顯然,當隨機事件x發生的先驗概率P(x)大時,算出的I(x)小,那麼這個事件發生的可能性大,不確定性小,事件一旦發生後提供的信息量也少。必然事件的P(x)等於1, I(x)等於0,所以必然事件的消息報導,不含任何信息量;但是一件人們都沒有估計到的事件(P(x)極小),一旦發生後,I(x)大,包含的信息量很大。所以隨機事件的先驗概率,與事件發生後所產生的信息量,有密切關系。I(x)稱x發生後的自信息量,它也是一個隨機變數。
P(x)大時,算出的I(x)小 必然事件的P(x)等於1, I(x)等於0。
P(x)小時,算出的I(x)大 必然事件的P(x)等於0, I(x)等於1。
I(x)稱x發生後的自信息量,它也是一個隨機變數。
信息熵

現在可以給「熵」下個定義了。信息量計算的是一個信源的某一個事件(X)的自信息量,而一個信源若由n個隨機事件組成,n個隨機事件的平均信息量就定義為熵(Entropy)。
熵的准確定義是:信源X發出的xj(j=1,2,……n), 共n個隨機事件的自信息統計平均(求數學期望),即

H(X)在資訊理論中稱為信源X的「熵 (Entropy)」 ,它的含義是信源X發出任意一個隨機變數的平均信息量。

更詳細的說,一般在解釋和理解信息熵有4種樣式
(1) 當處於事件發生之前,H(X)是不確定性的度量;
(2) 當處於事件發生之時,是一種驚奇性的度量;
(3) 當處於事件發生之後,是獲得信息的度量;
(4) 還可以理解為是事件隨機性的度量. 下面為了掌握信息熵的概念,我們來做一道計算題。
例如:以信源X中有8個隨機事件,即n=8。每一個隨機事件的概率都相等,即P(x1)=P(x2)=P(x3)……P(x8)=1/8 ,計算信源X的熵。
應用「熵」的定義可得其平均信息量為3比特

再例: 信源X中有17個隨機事件,即n=17。每一個隨機事件的概率分別為:

計算信源X的熵。
信息熵的計算公式:

信源X的熵:

定長碼與變長碼
定長碼(fixed-length code)即採用相同的位數(bit)對數據進行編碼。大多數存儲數字信息的編碼系統都採用定長碼。如我們常用的ASCII碼就是定長碼,其碼長為1位元組(Byte)。漢字國標碼也是定長碼,其碼長為2位元組(Byte)。變長碼(variable-length code)即採用不相同的位數(bit)對數據進行編碼,以節省存儲空間。例如,不同的字元或漢字出現的概率是不同的,有的字元出現的概率非常高,有的則非常低。根據統計,英文字母中「E」的使用概率約為13%,而字母「Z」的使用概率則為0.08%。又如大多數圖像常含有單色的大面積圖塊,而且某些顏色比其他顏色出現更頻繁。為了節省空間,在對數據進行編碼時,就有可能對那些經常出現的數據指定較少的位數表示,而那些不常出現的數據指定較多的位數表示。這樣從總的效果看還是節省了存儲空間。用這種方法得到的代碼,其碼的位數,也即碼長就是不固定的,故稱為變長碼。香農-范諾編碼,以及霍夫曼編碼,都是變長碼。
2.赫夫曼(Huffman)編碼基本原理:按信源符號出現的概率大小進行排序,出現概率大的分配短碼,出現概率小的則分配長碼。(定長碼採用相同的碼長對數據進行編碼,如ASCII碼是定長碼,其碼長為1位元組。)
定理:在變長碼中,對於出現概率在的信息符號編以短字長的碼,對於出現概率小的信息符號以長字長的碼,如果碼字長度嚴格按照符號概率的大小的相反順序排列,則平均碼字長度一定小於按任何其他符號順序排列方式得到的碼字長度。
定理證明

設最佳排列方式的碼字平均長度為 ,則有:

式中 為信源符號 出現的概率, 是符號 的編碼長度。規定 , 。如果將 的碼字與 的碼字互換,其餘碼字不變,經過這樣的互換以後,平均碼字長度變成 ,即

因為 ,所以 ,也就是說 最短。證畢。
Huffman編碼的編碼步驟

① 概率統計(如對一幅圖像,或m幅同種類型圖像作灰度信號統計),得到n個不同概率的信息符號。
② 將n個信源信息符號的n個概率,按概率大小排序。
③ 將n個概率中,最後兩個小概率相加,這時概率個數減為n-1個。
④ 將n-1個概率,按大小重新排序。
⑤ 重復③,將新排序後的最後兩個小概率再相加,相加和與其餘概率再排序。
⑥ 如此反復重復n-2次,得到只剩兩個概率序列。
⑦ 以二進制碼元(0.1)賦值,構成霍夫曼碼字。編碼結束。

利用Huffman編碼方式對信源進行編碼

已知信源:
編碼結果:平均碼長: =(0.35+0.20)×2+(0.15+0.10+0.10)×3+(0.06+0.04)×4=2.55(bit)(對於等長碼則需要3比特)。

Huffman編碼的特點

(1)平均碼長 (熵);
(2)平均碼長 bits(等長碼需要的比特數);
(3)保證解碼的唯一性,短碼字不構成長碼字的前綴;
(4)在接收端需保存一個與發送端相同的赫夫曼碼表。 Huffman不足方面:(1)構造出的碼不唯一,其原因是:一是在給兩個分支賦值時,可以是左支(或上支)為0,也可以是右支(或下支)為0,造成編碼的不唯一;二是當兩個消息的概率相等時,誰前誰後也是隨機的,構造出來的碼字也不唯一。
(2)編碼碼字字長參差不齊,因此硬體實現起來不大方便。
(3)編碼對不同信編碼效率是不同的。在概率頒很不均勻時,Huffman編碼才會有顯著的效果,在信源頒均勻的情況下,一般不使用Huffman編碼。
3.算術編碼(Arithmetic Coding)算術編碼方法也是利用信源概率分布特性、能夠趨近熵極限的編碼的方法。算術編碼不按符號編碼,即不是用一個特定的碼字與輸入符號之間建立一一對應的關系,而是從整個符號序列出發,採用遞推形式進行連續編碼,用一個單獨的浮點數來表示一串輸入符號。算術編碼是將被編碼的信息表示成實數0和1之間的一個間隔。信息越長編碼表示它的間隙就越小,表示這一間隙所須二進位就越多,大概率符號出現的概率越大對應於區間愈寬,可用長度較短的碼字表示;小概率符號出現概率越小層間愈窄,需要較長碼字表示。它的編碼方法比Huffman編碼方式要復雜,但它不需要傳送像Huffman編碼中的Huffman碼表,同時算術編碼還有自適應的優點,所以算術編碼是實現高效壓縮數據中很有前途的編碼方法。特點:方法比較復雜,具有自適應能力(隨著編碼符號流中01出現的概率的變化將自適應的改變)。在信源符號概率接近時,算術編碼比Huffman編碼效率要高。 算術編碼與解碼舉例

假設信源符號為{00, 01, 10, 11},這些符號的概率分別為{ 0.1, 0.4, 0.2, 0.3 },根據這些概率可把間隔[0,1)分成4個子間隔:[0, 0.1), [0.1, 0.5), [0.5, 0.7), [0.7, 1),其中[x,y)表示半開放間隔,即包含x不包含y。上面的信息可綜合在下表中。 表 信源符號,概率和初始編碼間隔 符號00011011概率0.10.40.20.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)
如果二進制消息序列的輸入為:10 00 11 00 10 11 01。編碼時首先輸入的符號是10,找到它的編碼范圍是[0.5, 0.7)。由於消息中第二個符號00的編碼范圍是[0, 0.1),因此它的間隔就取[0.5, 0.7)的第一個十分之一作為新間隔[0.5, 0.52)。依此類推,編碼第3個符號11時取新間隔為[0.514, 0.52),編碼第4個符號00時,取新間隔為[0.514, 0.5146),… 。消息的編碼輸出可以是最後一個間隔中的任意數。整個編碼過程如下圖示:
表: 編碼過程步驟 輸入符號編碼間隔 編碼判決110[0.5, 0.7)符號的間隔范圍[0.5, 0.7) 200[0.5, 0.52)[0.5, 0.7)間隔的第一個1/10311[0.514, 0.52)[0.5, 0.52)間隔的最後三個1/10400[0.514, 0.5146)[0.514, 0.52)間隔的第一個1/10510[0.5143, 0.51442)[0.514, 0.5146)間隔的第六個1/10開始的兩個1/10611[0.514384, 0.51442)[0.5143, 0.51442)間隔的最後三個1/10701[0.5143836, 0.514402)[0.514384, 0.51442)間隔的從第二個1/10開始的四個1/108從[0.5143876, 0.514402中選擇一個數作為輸出:0.51439
表:解碼過程步驟間隔解碼符號 解碼判決 1[0.5, 0.7)100.51439在間隔 [0, 1) 第六個1/102[0.5, 0.52)000.51439在間隔 [0.5, 0.7)的第一個1/103[0.514, 0.52)110.51439在間隔[0.5, 0.52)的第八個1/104[0.514, 0.5146)000.51439在間隔[0.514, 0.52)的第一個1/105[0.5143, 0.51442)100.51439在間隔[0.514, 0.5146)的第七個1/106[0.514384, 0.51442)110.51439在間隔[0.5143, 0.51442)的第八個1/107[0.5143876, 0.514402)010.51439在間隔[0.5143876, 0.514402)的第二個1/108解碼的消息:10 00 11 00 10 11 01解碼器的解碼過程應無限制地運行下去。在解碼器中需要添加一個專門的終止符,當解碼器看到終止符時就停止解碼。在算術編碼中需要注意的幾個問題:
①由於實際的計算機的精度不可能無限長,運算中出現溢出是一個明顯的問題,但多數機器都有16位、32位或者64位的精度,因此這個問題可使用比例縮放方法解決。
②算術編碼器對整個消息只產生一個碼字,這個碼字是在間隔[0, 1)中的一個實數,因此解碼器在接受到表示這個實數的所有位之前不能進行解碼。
③算術編碼也是一種對錯誤很敏感的編碼方法,如果有一位發生錯誤就會導致整個消息譯錯。

算術編碼可以是靜態的或者自適應的。在靜態算術編碼中,信源符號的概率是固定的。在自適應算術編碼中,信源符號的概率根據編碼時符號出現的頻繁程度動態地進行修改,在編碼期間估算信源符號概率的過程叫做建模。需要開發自適應算術編碼的原因是因為事先知道精確的信源概率是很難的,而且是不切實際的。當壓縮消息時,不能期待一個算術編碼器獲得最大的效率,所能做的最有效的方法是在編碼過程中估算概率。因此動態建模就成為確定編碼器壓縮效率的關鍵。
算術編碼的實現相應地比Huffman編碼復雜,但當與信號源符號的出現概率接近時,算術編碼的效率高於Huffman編碼。在圖像測試中表明,算術編碼效率比Huffman效率高5%左右。

㈤ 數據無損壓縮演算法

所謂無損壓縮格式,顧名思義,就是毫無損失地將聲音信號進行壓縮的音頻格式。常見的像MP3、WMA等格式都是有損壓縮格式,相比於作為源的WAV文件,它們都有相當大程度的信號丟失,這也是它們能達到10%的壓縮率的根本原因。而無損壓縮格式,就好比用Zip或RAR這樣的壓縮軟體去壓縮音頻信號,得到的壓縮格式還原成WAV文件,和作為源的WAV文件是一模一樣的!但是如果用Zip或RAR來壓縮WAV文件的話,必須將壓縮包解壓後才能播放。而無損壓縮格式則能直接通過播放軟體實現實時播放,使用起來和MP3等有損格式一模一樣。總而言之,無損壓縮格式就是能在不犧牲任何音頻信號的前提下,減少WAV文件體積的格式。

經常使用的無損壓縮演算法有 Shannon-Fano 編碼,Huffman 編碼,行程(Run-length)編碼,LZW(Lempel-Ziv-Welch)編碼和算術編碼等。

Huffman 編碼
該方法完全依據字元出現概率來構造異字頭的平均長度最短的碼字,有時稱之為最佳編碼,一般就叫做Huffman編碼。它是統計獨立信源能達到最小平均碼長的編碼方法。編碼效率高 。

基本原理:

依據信源字元出現的概率大小來構造代碼,對出現概率較大的信源字元,給予較短碼長,而對於出現概率較小的信源字元,給予較長的碼長,最後使得編碼的平均碼字最短。

編碼步驟:

(1)初始化,根據符號概率的大小按由大到小順序對符號進行排序。

(2)把概率最小的兩個符號組成一個節點。

(3)重復步驟2。

(4)從根節點開始到相應於每個符號的「樹葉」,從上到下標上「0」(上枝)或者「1」(下枝)至於哪個為「1」哪個為「0」則無關緊要,最後的結果僅僅是分配的代碼不同,而代碼的平均長度是相同的。

(5)從根節點開始順著樹枝到每個葉子分別寫出每個符號的代碼。

無損壓縮演算法有哪些

Huffman編碼的注意點:

Huffman編碼沒有錯誤保護功能,如果碼中有錯誤,則可能引起接下來的一連串解碼錯誤。

Huffman編碼是可變長編碼,因此很難隨意查找或調用中的文件內容。

Huffman依賴於信源的統計特性。 Huffman編碼的每個碼字都是整數:因此實際上平均碼長很難達到信息熵的大小。

Huffman編碼解碼必須要有碼表,如果消息數目很多,那麼

㈥ 資訊理論基礎的作品目錄

第1章緒論1
1.1信息的基本概念1
1.1.1資訊理論的產生1
1.1.2信息的基本概念2
1.2香農資訊理論研究的內容3
1.2.1通信系統模型4
1.2.2香農資訊理論的主要內容6
1.3香農資訊理論研究的進展與應用8
1.3.1香農資訊理論創立的背景8
1.3.2香農的主要貢獻9
1.3.3香農資訊理論的研究進展9
1.3.4香農資訊理論的應用12
思考題12
第2章離散信息的度量14
2.1自信息和互信息14
2.1.1自信息14
2.1.2互信息17
2.2信息熵18
2.2.1信息熵的定義與計算18
2.2.2條件熵與聯合熵21
2.2.3熵的基本性質22
2.3平均互信息27
2.3.1平均互信息的定義27
2.3.2平均互信息的性質28
2.3.3平均條件互信息30
本章小結33
思考題34
習題34
第3章離散信源37
3.1離散信源的分類與數學模型37
3.1.1離散信源的分類37
3.1.2離散無記憶信源的數學模型38
3.1.3離散有記憶信源的數學模型39
3.2離散無記憶信源的熵39
3.2.1單符號離散無記憶信源的熵39
3.2.2離散無記憶信源N次擴展源的熵40
3.3離散平穩信源的熵40
3.3.1離散平穩信源40
3.3.2離散平穩有記憶信源的熵41
3.4有限狀態馬爾可夫鏈42
3.4.1馬氏鏈基本概念43
3.4.2齊次馬氏鏈43
3.4.3馬氏鏈狀態分類46
3.4.4馬氏鏈的平穩分布47
3.5馬爾可夫信源48
3.5.1馬氏源的基本概念48
3.5.2馬氏源的產生模型50
3.5.3馬氏鏈N次擴展源的熵的計算51
3.5.4馬氏源符號熵的計算53
3.6信源的相關性與剩餘度55
3.6.1信源的相關性55
3.6.2信源剩餘度(冗餘度)55
3.6.3自然語言的相關性和剩餘度56
本章小結59
思考題59
習題60
第4章連續信息與連續信源64
4.1連續隨機變數集合的熵64
4.1.1連續隨機變數的離散化65
4.1.2連續隨機變數集的熵65
4.1.3連續隨機變數集的條件熵65
4.1.4連續隨機變數集的聯合熵66
4.1.5連續隨機變數集合差熵的性質66
4.1.6連續隨機變數集合的信息散度68
4.2離散時間高斯信源的熵69
4.2.1一維高斯隨機變數集的熵69
4.2.2多維獨立高斯隨機變數集的熵69
4.2.3多維相關高斯隨機變數集的熵69
4.3連續最大熵定理70
4.3.1限峰值最大熵定理71
4.3.2限功率最大熵定理71
4.3.3熵功率和剩餘度72
4.4連續隨機變數集的平均互信息72
4.4.1連續隨機變數集的平均互信息72
4.4.2連續隨機變數集平均互信息的性質73
4.5離散集與連續集之間的互信息75
4.5.1離散事件與連續事件之間的互信息76
4.5.2離散集合與連續集合的平均互信息76
本章小結77
思考題77
習題77
第5章無失真信源編碼80
5.1概述80
5.1.1信源編碼器80
5.1.2信源編碼的分類81
5.1.3分組碼82
5.2定長碼83
5.2.1無失真編碼條件83
5.2.2信源序列分組定理84
5.2.3定長碼信源編碼定理86
5.3變長碼88
5.3.1異前置碼的性質88
5.3.2變長碼信源編碼定理90
5.4哈夫曼編碼93
5.4.1二元哈夫曼編碼93
5.4.2多元哈夫曼編碼96
5.4.3馬氏源的編碼97
*5.5幾種實用的編碼方法99
5.5.1算術編碼99
5.5.2遊程編碼100
5.5.3L-Z編碼101
本章小結101
思考題102
習題102
第6章離散信道及其容量105
6.1概述105
6.1.1信道的分類105
6.1.2離散信道的數學模型106
6.1.3信道容量的定義109
6.2單符號離散信道及其容量109
6.2.1離散無噪信道的容量109
6.2.2離散對稱信道的容量110
6.2.3一般離散信道的容量112
6.3級聯信道及其容量116
6.4多維矢量信道及其容量118
6.4.1多維矢量信道輸入與輸出的性質118
6.4.2離散無記憶擴展信道及其容量120
6.4.3並聯信道及其容量122
6.4.4和信道及其容量122
6.5信道容量的迭代計算123
本章小結125
思考題126
習題126
第7章有噪信道編碼129
7.1概述129
7.1.1信道編碼的基本概念129
7.1.2判決與解碼規則130
7.1.3解碼錯誤概率131
7.2最佳判決與解碼准則132
7.2.1最大後驗概率准則132
7.2.2最大似然准則133
7.3信道編碼與最佳解碼134
7.3.1線性分組碼134
7.3.2序列最大似然解碼 135
7.3.3幾種簡單的分組碼136
7.4費諾(Fano)不等式137
7.4.1信道疑義度137
7.4.2費諾(Fano)不等式138
7.5有噪信道編碼定理139
7.5.1聯合典型序列140
7.5.2有噪信道編碼定理141
7.5.3無失真信源信道編碼定理143
7.6糾錯編碼技術簡介144
7.6.1線性分組碼的編譯碼144
7.6.2幾種重要的分組碼148
7.6.3卷積碼簡介149
*7.7信道編碼性能界限150
7.7.1漢明球包界150
7.7.2VarsharmovGilbert界151
7.7.3Plotkin界152
本章小結153
思考題153
習題154
第8章波形信道159
8.1離散時間連續信道159
8.1.1時間離散連續信道模型159
8.1.2平穩無記憶連續信道160
8.1.3多維矢量連續信道的性質160
8.1.4離散時間連續信道的容量160
8.2加性雜訊信道與容量161
8.2.1加性雜訊信道的容量161
8.2.2加性高斯雜訊信道的容量162
8.2.3一般加性雜訊信道容量界163
8.2.4並聯加性高斯雜訊信道的容量164
8.3AWGN信道的容量166
8.3.1加性高斯雜訊波形信道166
8.3.2波形信道的互信息與容量167
8.3.3AWGN信道的容量168
8.3.4高斯雜訊信道編碼定理170
8.3.5功率利用率和頻譜利用率的關系171
8.4有色高斯雜訊信道173
8.4.1有色高斯雜訊信道容量173
8.4.2AWGN信道容量的進一步討論175
*8.5數字調制系統的信道容量176
本章小結179
思考題180
習題180
第9章信息率失真函數183
9.1概述183
9.1.1系統模型184
9.1.2失真測度184
9.2離散信源信息率失真函數185
9.2.1信息率失真函數185
9.2.2R(D)函數的性質185
9.3限失真信源編碼定理188
9.3.1碼率的壓縮188
9.3.2限失真信源編碼定理189
9.3.3限失真信源信道編碼定理190
9.4離散信源信息率失真函數的計算190
9.4.1R(D)參量表示法求解191
9.4.2R(D)求解過程歸納192
9.4.3參量s的意義193
9.5連續信源信息率失真函數195
9.5.1信息率失真函數與性質195
9.5.2R(D)函數的計算195
9.5.3差值失真測度196
9.6高斯信源的R(D)函數197
9.6.1離散時間無記憶高斯信源197
9.6.2獨立並聯高斯信源199
9.7一般連續信源R(D)函數201
*9.8有損數據壓縮技術簡介201
9.8.1量化202
9.8.2預測編碼202
9.8.3子帶編碼203
9.8.4變換編碼203
本章小結204
思考題205
習題205
第10章有約束信道及其編碼208
10.1標號圖的性質208
10.1.1標號圖的基本概念208
10.1.2標號圖的變換210
10.2有約束信道容量211
10.2.1有約束信道容量的定義211
10.2.2等時長符號有約束信道的容量212
10.2.3不等時長符號無約束信道的容量213
10.2.4不等時長符號有約束信道的容量214
10.3有約束序列的性質215
10.3.1信道對傳輸序列的約束215
10.3.2遊程長度受限序列(RLL)215
10.3.3部分響應最大似然(PRML)序列217
10.3.4直流平衡序列218
10.3.5其他頻域受限序列220
10.4有約束信道編碼定理220
10.4.1編碼器的描述220
10.4.2有約束信道編碼定理221
10.4.3有限狀態編碼定理221
10.4.4編碼器性能指標222
*10.5有約束序列編碼與應用222
10.5.1塊編碼器222
10.5.2實用直流平衡序列223
10.5.3常用有約束序列編碼及應用225
本章小結227
思考題227
習題227
第11章網路資訊理論初步230
11.1概述230
11.2多址接入信道231
11.2.1二址接入信道的容量232
11.2.2不同多址方式下的接入信道容量分析236
11.2.3多址接入信道的容量238
11.3廣播信道238
11.3.1退化廣播信道239
11.3.2退化廣播信道的容量區域240
11.4相關信源編碼242
11.4.1典型的相關信源編碼模型243
11.4.2Slepian-Wolf相關信源編碼定理244
本章小結247
思考題248
習題249
*第12章信息理論方法及其應用250
12.1信源熵的估計250
12.1.1離散信源序列熵的估計251
12.1.2連續信源熵的估計254
12.2最大熵原理255
12.2.1最大熵原理的描述255
12.2.2熵集中定理258
12.2.3幾種重要的最大熵分布259
12.3最小交叉熵原理261
12.3.1最小交叉熵原理261
12.3.2交叉熵的性質263
12.3.3最小交叉熵推斷的性質264
12.3.4交叉熵法265
12.4信息理論方法的應用265
12.4.1DNA序列的熵估計和壓縮265
12.4.2最大熵譜估計和最小交叉熵譜估計267
12.4.3最大熵建模及其在自然語言處理中的應用269
12.4.4最大熵原理在經濟學中的應用271
12.4.5信息理論方法應用展望273
本章小結273
思考題274
習題274
參考文獻276

㈦ 典型的有損壓縮編碼方法錯誤的是

錯誤的是:啥夫曼編碼將出現概率大的信源符號用長碼表示,出現概率小的信源符號用短碼表示。
對於多媒體數據,按照壓縮的原理可分為熵編碼、源編碼和混合編碼。其中,源編碼包含預測編碼去、變換編碼法和矢量量化編碼法,屬於有損壓縮編碼,如表210所示。啥夫曼編碼是最著名的熵編碼,它將出現概率大的信源符號用短碼表示,而出現概率小的信源符號用長碼表示,於是平均碼長接近信息熵的理論值。因此這個是錯誤的。

㈧ 用費諾編碼實現信源編解碼

我回答你的問題啊!呵呵,你怎麼不給分啊????實驗命令:clc;clear all;
N=input('N=');%輸入信源符號的個數
s=0;l=0;H=0;
for i=1:N
fprintf('第%d個',i);
p(i)=input('p=');%輸入信源符號概率分布矢量,p(i)<1
if p(i)<=0
error('不符合概率分布')
end
s=s+p(i)
H=H+(- p(i)*log2(p(i)));%計算信源信息熵
end
if (s<=0.999999||s>=1.000001)
error('不符合概率分布')
end
tic;
for i=1:N-1 %按概率分布大小對信源排序
for j=i+1:N
if p(i)<p(j)
m=p(j);p(j)=p(i);p(i)=m;
end
end
end
x=f1(1,N,p,1);
for i=1:N %計算平均碼長
L(i)=length(find(x(i,:)));
l=l+p(i)*L(i);
end
n=H/l; %計算編碼效率
fprintf('按概率降序排列的碼字:\n');
disp(x) %顯示按概率降序排列的碼字
fprintf('平均碼長:\n');
disp(l)% 顯示平均碼長
fprintf('信源信息熵:\n');
disp(H)%顯示信源信息熵
fprintf('編碼效率:\n');
disp(n) %顯示編碼效率
fprintf('計算耗時time= %f\n',toc);
再建立兩個M文件:%函數f1存放於f1.m
function x=f1(i,j,p,r)
global x;
x=char(x);
if(j<=i)
return;
else
q=0;
for t=i:j %對於區間[i,j]自上而下求累加概率值
q=p(t)+q;y(t)=q;
end
for t=i:j%把所有自上而下的累加概率值與該區間總概率值減該累加概率值之差取絕對值存在一數組
v(t)=abs(y(t)-(q-y(t)));
end
for t=i:j
if(v(t)==min(v)) %求該數組中最小的一個值來確定分界點位置
for k=i:t %賦值碼字
x(k,r)='0';
end
for k=(t+1):j
x(k,r)='1';
end
d=t;
f1(i,d,p,r+1); %遞歸調用及相互調用
f2(d+1,j,p,r+1);
f1(d+1,j,p,r+1);
f2(i,d,p,r+1);
else
end
end
end
return;第二個:%函數f2存放於f2.m
function x=f2(i,j,p,r)
global x;
x=char(x);
if(j<=i)
return;
else
q=0;
for t=i:j %對於區間[i,j]自上而下求累加概率值
q=p(t)+q;y(t-i+1)=q;
end
for t=1:j-(i-1)%把所有自上而下的累加概率值與該區間總概率值減該累加概率值之差取絕對值存在一數組
v(t)=abs(y(t)-(q-y(t)));
end
for t=1:j-(i-1)
if(v(t)==min(v)) %求該數組中最小的一個值來確定分界點位置
d=t+i-1;
for k=i:d %賦值碼字
x(k,r)='0';
end
for k=(d+1):j
x(k,r)='1';
end
f2(d+1,j,p,r+1);%遞歸調用及相互調用
f1(i,d,p,r+1);
f2(i,d,p,r+1);
f1(d+1,j,p,r+1);
else
end
end
end
return;

㈨ 如何計算密碼所攜帶的信息熵

可加性與強可加性(涉及到了兩個變數!)H(XY)為兩個隨機變數的聯合熵。可加性:H(XY)等於 X的無條件熵,加上已知 X 時 Y的條件概率的熵的平均值,即條件熵。對於 X 與 Y 獨立的情況有:(強可加性)資訊理論基礎2011年3月教材和參考書傅祖芸編著《資訊理論-基礎理論與應用》,電子工業出版社,2006第二版. 孟慶生《資訊理論》,西安交通大學,1986。(數學家寫的研究生教材,含編碼和密碼)朱雪龍《應用資訊理論基礎》,清華大學出版社,2000。(研究生教材,面向電子類,含編碼方法。王育民、梁傳甲《信息與編碼理論》,西電教材。 (內容深入,推導過程少)沈連豐、葉芝惠編著《資訊理論與編碼》東南大學碩士教材,科學出版社,2004,(面向通信專業)。周蔭清主編《信息理論基礎》北航出版社,2006(簡潔,面向電子類)T. M. Cover & J. A. Thomas , Elements of Information Theory ,Addison-Wesley Pub, 1990, 清華影印。R. J. McEliece《The Theory of Information and Coding》第二版,電子工業出版社,2003。(內容簡練,編碼方面較全) * J.H.Van Lint 《Introction to coding theory》 GTM 86, Springer-Verlag, 1998. * Roman 《Coding and information theory》, GTM 134,新的教材:在廣義資訊理論、網路資訊理論方面的內容有所增加。第一講 1-1 資訊理論的主要內容 1-2 信息的度量-信息熵 1-3 信息熵的性質 信息熵 1-1. 資訊理論的主要內容 香農資訊理論最初是為了解決通信問題而提出的。通信的重要意義是勿庸置疑的。類傳遞思想、表達情感,就需要相互交流。人類的勞動、生產、政治、文化、日常生活等都離不開通信。人類利用眼、耳、鼻、舌、身等五種感覺器官來感受外界的信息,形成一個信息流通的體系。通信方式的不斷提高,代表了人類文明和科技水平的不斷提高。通信的根本任務:將一地點的消息可靠地、有效地傳送到另一地點。信源干擾源信道信宿通信系統的基本模型:為了使消息可靠地、有效地傳送到信宿,就需要對信源的消息進行處理;信源編碼:實現有效性;信道編碼:實現可靠性;密碼:實現保密性及認證性;有沒有可靠的、有效的處理方法?如何進行編碼?香農資訊理論奠定了通信的理論基礎。信息是消息的不確定性度量。某消息出現的概率大,它的信息量就小,相反某消息出現的概率小,則它的信息量就大。通信的關鍵是信息的傳輸問題。 信源,信源,編碼信宿,信道,信道編碼,信道解碼,信源解碼加密鑰,加密解密鑰,解密 干擾源提出的背景:在香農資訊理論出現以前,沒有系統的通信理論。是香農,開創了資訊理論的研究,奠定了一般性通信 理論的基礎。對數字通信技術的形成有很大貢獻。(不論什麼樣的干擾信道,抓住了本質問題Shannon, 1916-2001)「A Mathematical Theory of Communication 」「 Communication Theory of Secrecy System 」 About Claude Elwood Shannon: 1916年生於 Gaylord, MI 的一個小鎮。母親是一個語言教師和中學校長,父親是一個商人。 16歲高中畢業,進入密西根大學。1936年獲得電子工程和數學雙學士學位。隨後進入 MIT,作為研究生和研究人員。

閱讀全文

與lzw編解碼平均碼長和信息熵相關的資料

熱點內容
java反向工程 瀏覽:110
pdf文檔轉換excel 瀏覽:8
主角叫楚天的都市小說 瀏覽:754
程序員三重境界 瀏覽:871
菜雞方舟上怎麼開伺服器 瀏覽:727
馬林固件編譯錯誤 瀏覽:910
市場營銷案例pdf 瀏覽:770
魔爪閱讀網 瀏覽:19
app地推業績統計在哪裡 瀏覽:993
維語電影網站大全 瀏覽:958
程序員骨腫瘤上熱搜 瀏覽:847
聚優電影 瀏覽:45
國企保底工資演算法 瀏覽:730
視聽說伺服器地址是什麼意思 瀏覽:657
一部男主叫大志的電影叫 瀏覽:650
安卓反編譯後編譯不回來 瀏覽:195
快穿肉文推薦 瀏覽:263
lol新手推薦什麼伺服器 瀏覽:283
尼桑奇駿壓縮機 瀏覽:170
android模態對話框 瀏覽:793