پيشنهاد كدهاي بدون پيشوند-پسوند شبه متقارن در كدينگ منبع

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

Introducing Quasi Symmetric Fix Free Codes in Source Coding Adel Aghajan a aghajanabdollah@ec iut ac ir Date of Submission 2012 2 27 Department of Electrical and Computer Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language Farsi Supervisor M A Khosravifard khosravi@cc iut ac ir AbstractThe goal of source coding is to compress the data generated by an information source Data compressionhelps saving valuable resources such as transmission bandwidth and storage memory Hence coding a sourceby a code with minimum possible average codelength is more desirable In many applications such as videocompression decoding has to be done without delay This requirement is satisfied by employing prefix freecodes i e codes in which no codeword is the prefix of another codeword It is well known that the necessaryand sufficient condition for the existence of a prefix free code can be expressed by the Kraft inequality Thisconstraint on the codeword lengths makes the entropy as a lower bound on the average codeword length Therefore the performance of a code is usually evaluated by its redundancy which is defined as thedifference between the average codelength and the entropy Regardless of the probability distribution of thesource the redundancy of the optimal prefix free code is less than 1 bit per symbol Due to the sensitivity ofprefix free codes to transmission error fix free codes are used in various applications instead In fix freecodes no codeword is the prefix or suffix of any other codeword In addition to their error resilience fix freecodes enable bidirectional decidability of the streams of codewords Therefore fix free codes are used invideo standards such as H 263 and MPEG 4 It has been shown that is the sufficientcondition for the existence of a fix free code for lengths The most important consequence of thissufficient condition is that the redundancy of the optimal fix free code cannot be greater than 1 0817 bits persymbol However in general decoding of fix free codes requires two tables or two trees This takes up twiceas much memory as when decoding prefix free codes Hence in order to benefit from the advantages of fix free codes with limited memory symmetric fix free codes were introduced In these codes as the nameimplies the codewords not only possess the fix free property but are also symmetric However thesymmetry of the codewords is achieved at the cost of more redundancy In this thesis we show that for somesources the symmetry property can impose a great amount of redundancy on the fix free codes In order toovercome this issue in this thesis we propose a new class of fix free codes referred to as quasi symmetricfix free codes In these codes the reverse of each codeword is itself a codeword In this thesis it is shownthat the performance of quasi symmetric fix free codes in terms of the redundancy and required memory liesbetween fix free and symmetric fix free codes The main contribution of this thesis is to show that most ofthe sufficient conditions on the existence of fix free codes are indeed sufficient conditions for the existenceof quasi symmetric fix free codes as well Another important result of this thesis is that the redundancy ofthe optimal quasi symmetric fix free code is at most 1 0817 bits per symbol the same as fix free code Key Words Fix Free Code Symmetric Fix Free Code Quasi Symmetric Fix Free Code

آقاجان، عادل

پيشنهاد كدهاي بدون پيشوند-پسوند شبه متقارن در كدينگ منبع