5073

4770

كارشناسي ارشد

مخابرات سيستم

اصفهان: دانشگاه صنعتي اصفهان،دانشكده برق و كامپيوتر

1388

نه،70ص.: مصور،جدول،نمودار

ص.ع.به فارسي و انگليسي

محمدعلي خسروي فرد

حسين سعيدي

88/12/12

علي محمددوست حسيني،محمد دخيل عليان

مهندسي برق و كامپيوتر

ID4770

به فارسي و انگليسي: قابل رويت در نسخه ديجيتالي

Improved Upper Bounds on the Redundancy of the Optimal Fix Free Code Shima Kheradmand s kheradmand@ec iut ac ir Nov 2009 Department of Electrical and Computer Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Language Persian Degree M Sc st M A Khosravifard khosravi@cc iut ac irAbstractIn a communication system we try to convey information from one point calledinformation source to a determined destination very often in a noisy environment Beforethe information is transmitted the sequence of symbols generated by the source is usuallyprocessed by a block called source encoder In fact source coding is used to compress theinformation Data compression helps saving valuable resources such as transmissionbandwidth and storage memory Hence coding a source by a code with minimum possibleaverage codelength is more desirable Furthermore in some applications such as video compression decoding proceduremust be accomplished instantaneously This requirement necessitates using prefix freecodes in which no codeword is prefix of any other one It is well known that the codewordlengths of any binary prefix free code satisfy the Kraft inequality This constraint on thecodeword 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 isdefined as the difference between the average codelength and the entropy The optimalprefix free code which has the minimum average codeword length or equivalentlyminimum redundancy for an information source can be obtained by the well knownHuffman algorithm and called Huffman code Regardless of the probability distribution ofthe source the redundancy of the Huffman code is less than 1 bit per symbol A special class of prefix free codes is the fix free codes introduced bySch tzenberger Gilbert and Moor In a fix free code no codeword is a prefix or a suffixof any other codeword Fix free codes are used in video compression standards such asH 263 and MPEG 4 since their property of efficient decoding in both the forward andbackward directions assists with error resilience This property also potentially halves theaverage search time for a string in a compressed file relative to unidirectional prefix freecodes Fix free codes have possible applications in problems of information retrievalincluding the searching and indexing of compressed text But clearly these advantages are

محمدعلي خسروي فرد

حسين سعيدي

علي محمددوست حسيني،محمد دخيل عليان