無失真編碼PPT課件

1、 General model of discrete, lossless (無失真）, non-memory source:Input symbol setCode symbol setCode word set12(,.,);1,2,.,liiiiiiilsWxxxiq12 ,.,)irXx xx5.1 Lossless encoder第1頁/共34頁 How to code losslessly? Assuming that the statistical characteristics of the source can be ignored, it must satisfy the f

2、ollowing condition.To get the target of lossless coding, it must conform to the condition , which guarantees that there are plenty of code symbols to be used.NlqrlFrom the condition we can get an inequality,rqNlrqlNloglog第2頁/共34頁 E.g. 5.1 Suppose we only have the first eight letters of English alpha

3、bet (A to H) in our vocabulary. The Fixed Length Code (FLC) for this set of letters would beLetterCodewordLetterCodewordA000E100B001F101C010G110D011H111Fixed Length Code第3頁/共34頁A Variable Length Code (VLC) for the same set of letters can be LetterCodewordLetterCodewordA00E101B010F110C011G1110D100H11

4、11Variable Length Code1 (Huffman coding)第4頁/共34頁 Suppose we have to code the series of letters:” A BAD CAB”. The fixed length code and variable length code representations of the 7 letters areFixed Length Code000 001 000 011 010 000 001Total bits= 21Variable Length Code00 010 00 100 011 00 010Total

5、bits= 18It can be seen that the VLC uses a fewer number of bits than FLC since the letters, for example, A, appearing more frequently in the sentence are represented with a fewer number of bits 00.第5頁/共34頁 Instantaneous code (prefix code)(1) It is a kind of uniquely decodable code(2) In an unfixed l

6、ength code, there is no one code being prefix to other codes.(3) When decoding, it does not need to refer to its following codes, and can make the judgment immediately, carrying out non-delay decoding.第6頁/共34頁 Let us have a look at Example 5.1 again. Now we consider another VLC for the first 8 lette

7、rs of English alphabet:LetterCodewordLetterCodewordA0E10B1F11C00G000D01H111Variable Length Code2第7頁/共34頁 This second variable length code appears to be more efficient than the first one in terms of representation of the letters.Variable Length Code100 010 00 100 011 00 010Total bits= 18Variable Leng

8、th Code20 1 0 01 00 0 1Total bits= 9:Original: 0 1 0 01 00 0 1 - A BAD CABNow: 0 10 0 1 0 0 01 - A EAB AADOr 0 1 0 0 1 0 0 0 1 - A BAAB AAAB第8頁/共34頁 Definition 5.1 A Prefix Code is one in which no codeword forms the prefix of any other codeword. Such codes are also called Uniquely Decodable or Insta

9、ntaneous Codes.lThe optimal codeIt is a kind of uniquely decodable codeIts average code length is less than that of any other uniquely decodable code.第9頁/共34頁 5.2.1 Fixed length coding theorem5.2 Lossless source coding: As to the discrete, non-memory, stationary, ergodic source symbol sequence S=(S1

10、,S2 .Sq)，we can use r different symbols X =(x1, x2. xr) to perform fixed length code. For any 0 and0，as to the N-expansion source, If is satisfied, and when N is big enough，the decoding error can be less than .The fixed length coding theorem has presented a theoretical limit of the code length used

11、for fixed length coding. log( )(0)lrH SN 第10頁/共34頁 If the equal length code is demanded to be uniquely decodable, then it must has: If N1，then： Conclusion：for unique decoding, each source symbol needs at least code symbols to be represented. When use dual-code symbol to code, r2，then： Conclusion：whe

12、n use equal length dual-code, the limit code length of each source symbol is log/logqr1loglog ()Nlqlq bitN log ()q bitloglogNllqqrNrloglogqlrExample第11頁/共34頁5.2.2 Unfixed length (Variable length) source coding Several concepts of code type(Eg.2.4.2) Non-singular code and singular code Uniquely decod

13、able code Prefix code（instantaneous code, non-delay code） Kraft theorem Unfixed length coding theorem（Shannon First Theorem）第12頁/共34頁Kraft theorem question：find real-time, uniquely decodable code method：research the code partition condition of the real-time uniquely decodable code introduction：conce

14、pt of “code tree” conclusion：present the condition that the real-time uniquely decodable code (prefix code) exists, that is, the Kraft theorem第13頁/共34頁code treeThe corresponding relationship between VLC and code tree：(1) Tree root Starting point of a code word(2) Number of branches from a tree node

15、Code dimension(3) Node Part of a code word(4) Terminal node End of a code word(5) Number of branches Code length (6) Non-full branch tree Variable length code (7) Full branch tree Fixed length code 第14頁/共34頁Theorem 5.1 (Kraft Inequality) A necessary and sufficient condition for the existence of a bi

16、nary prefix code set whose code words have lengths is Lnnn.21121LknkCode tree map for proof第15頁/共34頁 Average length of the prefix code A discrete non-memory stationary source Its limit source entropy is and the number of input symbol set is . The code length of each code word is , then the average c

17、ode length of prefix code is )(SH11,.,.,.,iqiqSsSsSsSpppP,1,2,.,il iqql5.3.3 Lossless unfixed length (variable length) source coding theorem 1qiiill p第16頁/共34頁 Lossless unfixed length source coding theorem () For discrete non-memory stationary source S, its limit entropy is and its code signals are

18、X=x1,xr. We can always code the source S by using a coding method to construct uniquely decodable code. Thus the average code length of each source signal satisfies:)(SH( )( )1loglogHsHslrr 第17頁/共34頁Theorem 5.3 () Let X be the set of letters from a DMS with finite entropy H(X) and xk, k= 1, 2, , L t

19、he output symbols, occurring with probabilities . Given these parameters, it is possible to construct a code that satisfies the prefix condition and has an average length R that satisfies the following inequalitykxP( )( )1H xRH x第18頁/共34頁 ： discrete source without memory412431sspSIts entropy is:134(

20、 )log4log0.811/443H SbitsymUse dual signals（0, 1; r=2）construct a prefix code：1,021ssThe average code length of each signal is：1l ( )0.811H SlThe code efficiency is：第19頁/共34頁Construct a prefix code of expansion source S2Prefix code s1s1 9/160 s1s2 3/1610 s2s1 3/16110 s2s2 1/16111i)(iPaverage code le

21、ngth：293312712331616161616l average code length of each signal in source S2 ：2727/ 21632l code efficiency：2( )0.961H SlAlso has:In order to improve the code efficiency, a two-dimensional union code is adopted by considering the 2nd order expansion source of S. 3( )0.985H Sl4( )0.991H Sl第20頁/共34頁： Us

22、ing unfixed length code, we can achieve quite high coding efficiency even when N is not very high. Moreover we may realize lossless coding. Also with N increasing, the coding efficiency more and more approaches to 1.第21頁/共34頁5.4 Typical example of lossless source coding5.4.1 Huffman coding Coding me

23、thod Characteristic Application第22頁/共34頁（Huffman coding）12341/ 21/ 41/81/8SssssP Eg. 5.7第23頁/共34頁Coding steps： 1) Sort the source message U according to their probabilities in a descending order; 2) Start from the two least probabilities; for example, the lower branch with little probability is assi

24、gned “1”, and the upper branch is assigned “0”. If the two branches probabilities are equal, still assign the lower branch “1”, and the upper “0”. 3) Combine the two coded branches, reorder and recode. 4) Repeat step 3）until the sum of the probabilities is 1. 5) Turn over from the rightmost end to t

25、he left along the tree branch to get the corresponding code word, like U3 “110”. 第24頁/共34頁（Huffman coding） E.g.1：第25頁/共34頁第26頁/共34頁E.g. 2Eight symbols (A-H) with the probabilities of occurrence given in the right table. Please draw the Huffman coding procedure and compute the coding efficiency. Symb

26、olProbabilityA0.10B0.18C0.40D0.05E0.06F0.10G0.07H0.04第27頁/共34頁第28頁/共34頁第29頁/共34頁(1) The entropy of this source is:222222220.10log (0.10)0.18log (0.18)0.40log (0.40)0.05log (0.05)0.06log (0.06)0.10log (0.1000)0.07log (0.07)0.04log (0.04)2.5524bits/symbolH (2) The average length of codeword is:0.10 30.18 30.40 1