پديد آورنده :
كلباسي، محمدجواد
عنوان :
بررسي كران هاي افزونگي كدهافمن
مقطع تحصيلي :
كارشناسي ارشد
گرايش تحصيلي :
برق - مخابرات ﴿سيستم﴾
محل تحصيل :
اصفهان: دانشگاه صنعتي اصفهان، دانشكده برق و كامپيوتر
صفحه شمار :
نه،78ص.: نمودار
يادداشت :
ص.ع.به فارسي و انگليسي
استاد راهنما :
محمدعلي خسروي فرد
توصيفگر ها :
كد بدون پيشوند , كد بدون پيشوند - پسوند
تاريخ نمايه سازي :
2/12/93
استاد داور :
حسين سعيدي، حامد نريماني
دانشكده :
مهندسي برق و كامپيوتر
چكيده فارسي :
چكيده يكي از بخشهاي مهم هر سيستم مخابراتي كدگذار منبع مي باشد كه موجب كاهش هزينه ارسال داده ميگردد در بسياري از كاربردها الزم است كدبرداري به صورت آني انجام پذيرد براي دستيابي به اين هدف بايد از كد بدون پيشوند استفاده شود كه در آن هيچ كلمهكدي پيشوند كلمهكد ديگر نيست افزونگي مهمترين معيار براي ارزيابي كارآيي يك كد بدون پيشوند است كد بدون پيشوند بهينه كدي است كه داراي كم ترين مقدار افزونگي باشد اين كد توسط الگوريتم معروف هافمن به دست ميآيد شانون نشان داد كه در حالت كلي افزونگي كد بدون پيشوند بهينه مقداري بين صفر و يك است اگر اطالعاتي در مورد احتمال وقوع سمبلهاي منبع در اختيار باشد كران هاي صفر و يك قابل بهبود هستند در اين خصوص تا كنون كران هايي بر حسب بزرگترين كوچكترين و يك احتمال دلخواه از سمبلهاي منبع به دست آمده است كه در اين پاياننامه بررسي مي گردند در اين پاياننامه با بررسي روشهاي موجود در محاسبه كرانها ديدگاه هاي متفاوتي پيشنهاد مي شود كه از طريق آنها ميتوان كرانهاي باال و پايين جديدي بر حسب دو احتمال دلخواه از سمبلهاي منبع به دست آورد همچنين با تعميم ديدگاه ارائه شده در مورد كران پايين كران هاي پايين جديدي براي كدهاي بدون پيشوند پسوند و كدهاي با مجموع كرافت مشخص ارائه مي گردد كلمات كليدي 3 كد بدون پيشوند 2 افزونگي 1 كد هافمن 4 كد بدون پيشوند پسوند
چكيده انگليسي :
Investigating the Bounds on the Redundancy of Huffman codes Mohammad Javad kalbasi m javadkalbasi@ec iut ac ir Date of Submission 2014 9 21 Department of Electrical and Computer Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language FarsiSupervisor M A Khosravifard khosravi@cc iut ac irAbstractOne of the important blocks in any communication system is the source encoder which reduces the rate oftransferred data In many applications instantaneous decoding is an essential requirement This enforces thedesigner to use prefix free codes in which no codeword is the prefix of any other codeword Redundancy isthe most important measure for evaluating the performance of a code for a source The optimal prefix freecode for a source is one with the minimum redundancy The optimal code can be easily obtained by the well known Huffman algorithm Shannon showed that in general the redundancy of the optimal prefix free codelies between zero and one Clearly if something about the symbol probabilitites is known the bounds zeroand one can be improved The bounds in terms of the most likely the least likely and an arbitrary symbolprobability have been obtained in the literatures which are reviewed in this thesis After investigating theknown approaches to obtaining the bounds some different viewpoints are proposed which lead us to derivenew upper and lower bounds in terms of two known arbitrary symbol probabilities Also the proposedapproach is used to obtain new lower bounds for the redundancy of the optimal fix free codes and the optimalcodes with a given Kraft sum Key words Prefix Free Code Redundancy Huffman Code Fix Free Code
استاد راهنما :
محمدعلي خسروي فرد
استاد داور :
حسين سعيدي، حامد نريماني
