ارائه يك كد شبه بهينه با معيار ميانگين افزونگي براي منابع يكنوا

چكيده انگليسي :

A Suboptimal Code in the Sense of Average Redundancy for the Class of Monotone Sources Parvin Rastegari P Rastegari@ec iut ac ir Date of Submission 2011 02 19 Department of Electrical and Computer Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language Persian Supervisor M A Khosravifard khosravi@cc iut ac ir Abstract One of the main problems in the context of source coding is finding a code with minimum average codelength for a given memoryless source The average codelength should be small because of saving expensive resources such as hard disk space and transmission bandwidth In addition to the average codelength instantaneous decodability of a code should be considered This is important in many applications such as video compression where the encoded data must be decoded with the minimum possible delay Prefix free codes for which no codeword is prefix of any other codeword are instantaneous It is well known that the Kraft inequality is a necessary and sufficient condition for the existence of a binary prefix free code with a given codelength vector Under the Kraft inequality constraint the average codelength is lower bounded by the entropy This is why the redundancy which is the difference between the average codelength and the entropy is usually considered as a criterion for evaluating the performance of a code for a source Since assigning prefix free codewords to the given codelengths is a straightforward task the main problem is to find the appropriate codelength vector which minimizes the redundancy under the condition of the Kraft inequality For a given source the optimal prefix free code can be obtained by the well known Huffman algorithm But in some practical cases symbol probability vector varies in time and or are not completely known Hence the problem will be finding a unique code for a class of sources The performance of a code for a class of sources can be evaluated by its average redundancy i e MinAve criterion Consider the case where the only information about the source is its alphabet size and the order of symbol probabilities In other words the class of monotone sources with N symbols is considered Assuming a uniform distribution on this class of sources the optimal code in the sense of MinAve criterion is called M code The main goal of this thesis is to study the structure of the M code and employ it to propose simple suboptimal alternative There are two major motivations for such a study x The M code is a fixed code for all monotone sources with N symbols i e it is enough to apply the Huffman algorithm on the average distribution and employ the derived code on all sources in the class Clearly it is much simpler and faster especially for large N than applying the Huffman algorithm for each source Interestingly simulations show that the average redundancy of the M code tends to that of the Huffman code for large values of N almost equal to 0 0287 Hence for a randomly chosen monotone source with large alphabet the cost of using the M code instead of applying the Huffman algorithm is ignorable in the average sense x The average redundancy of the M code is an upper bound on the average redundancy of the Huffman code Thus the performance of the M code is important to examine the Huffman code

رستگاري، پروين

ارائه يك كد شبه بهينه با معيار ميانگين افزونگي براي منابع يكنوا

كد گذاري منبع , طول كد , كدهافمن , كدM