در این رساله به بررسی عملکرد کد هافمن و چند کد شبه بهینه شامل: «کد طول ثابت»، «کد یکنواخت»، «کد یکنواخت با منبع مرتب شده»، «کد M» و «کد شانون»، بر روی «منابع بدون حافظه با الفبای بزرگ» می‌پردازیم. در روش‌های کدگذاری «طول ثابت» و «یکنواخت» به همه‌ی منابعِ با اندازه الفبای یکسان، یک کد یکسان نسبت داده می‌شود. در طرف دیگر در کدگذاری‌های «یکنواخت با منبع مرتب شده» و «M»، ابتدا منابع براساس ترتیب احتمال وقوع سمبل‌ها مرتب می‌شوند و سپس به آن‌ها یک بردار کد معین نسبت داده می‌شود. اما در کدگذاری‌های «شانون» و «هافمن»، بردار کد در حالت کلی به مقادیر دقیق همه‌ی احتمال سمبل‌ها وابسته است. ثابت خواهیم کرد که برای کدهای مورد بررسی، واریانس افزونگی بر روی مجموعه منابع با اندازه الفبای معین، با افزایش اندازه الفبا به صفر میل می‌کند. در نتیجه برای اغلب منابع با الفبای بزرگ n، افزونگی هر یک از این کدها تقریباً برابر است با میانگین افزونگی آن کد بر روی مجموعه منابع با n سمبل. برای کدهای «هافمن» و «M»، میانگین افزونگی منابع n-سمبلی برابر است با افزونگی به ازاء «توزیع میانگین منابع یکنوای n-سمبلی» که این مقدار، برای اندازه الفبای بزرگ n، در بازه‌ی 0.02873 و 0.02877 بیت در نوسان است. همچنین، میانگین افزونگی کد «شانون» بر روی مجموعه منابع n سمبلی فرمول‌بندی می‌شود. ثابت خواهیم کرد که این مقدار یک دنباله‌ی واگرا برحسب n است که برای مقادیر بزرگ n در اطراف 0.5 بیت در نوسان است. برای کدهای «طول ثابت»، «یکنواخت» و «یکنواخت با منبع مرتب شده» نشان خواهیم داد که در حالت مجانبی، یعنی هنگامی که اندازه الفبا n بزرگ شود، میانگین افزونگی هر کد بر روی منابع n-سمبلی تابعی متناوب از جزء صحیح لگاریتم n است. برای هر یک از کدهای فوق، این تابع متناوب در بازه‌های، به ترتیب، [0.6099,1.6099)، [0.6099,0.6960) و [0.3254,0.6099) بیت در نوسان است. با مقایسه‌ی مقادیر فوق بین کدهای M و یکنواخت، مشاهده می‌شود که برای اغلب منابع با الفبای بزرگ دانستن یا ندانستنِ ترتیب احتمال وقوع سمبل‌ها باعث افزایش حدود 0.581 بیتی در افزونگی کدگذاری منبع می‌شود. یک نتیجه‌ی قابل توجه، که از مقایسه‌ی افزونگی کد بهینه با M به دست می‌آید، آن است که برای اغلب منابع با الفبای بزرگ کدگذاری «M» یک کدگذاری نزدیک به بهینه است در حالی که ساختار کدگذاریِ آن به مراتب ساده‌تر از کد بهینه است. به این معنی که کد بهینه‌ی یک منبع، تابعی از احتمال وقوعِ همه‌ی سمبل‌های منبع است اما در کدگذاری M به همه‌ی منابع مرتب شده، یک بردار کد یکسان نسبت داده می‌شود. بنابراین می‌توان گفت که برای اغلب منابع با الفبای بزرگ، دانستن ترتیب احتمال وقوع سمبل‌ها (و نه مقدار دقیق آن‌ها) برای رسیدن به یک کد منبع نزدیک به بهینه کافی است.
کد نوشتار : 297503