تولید همه کدهای فشرده با محدودیت روی کوچک ترین طول کد

اگرچه با استفاده از الگوریتم هافمن می توان کد فشرده (کد با مجموع کرافت مساوی یک) با حداقل افزونگی را برای یک منبع اطلاعات بدون حافظه ساخت، در برخی مسائل لازم می شود که ابتدا همه کدهای فشرده ممکن ساخته شوند و بعد از بین آنها کد مناسب با معیار مورد نظر انتخاب شود. به طور خاص اگر طول همه کلمه کدهای یک کد فشرده n تایی λ یا بیشتر باشد، آنگاه اختلاف بزرگ ترین و کوچک ترین طول کلمه کد آن به n-۲^λ محدود می شود و درنتیجه با افزایش مقدار λ می توان تفاوت در تاخیر کدبرداری سمبل های مختلف منبع را کاهش داد. ساخت چنین کدهایی هدف اصلی این مقاله است و برای این کار الگوریتمی ارائه می شود که فقط همین کدها (کدهای فشرده n تایی که طول همه کلمه کدهای آنها λ یا بیشتر باشد) را تولید می کند. با توجه به تناظری که بین بردارهای چندگانگی کدهای فشرده با برخی دنباله های اعداد وجود دارد، شرط لازم و کافی برای اینکه یک دنباله از اعداد متناظر یک کد فشرده که کوتاه ترین کلمه کدش حداقل λ بیت باشد را پیدا می کنیم. بدین ترتیب با تولید همه دنباله های مناسب، همه کدهای فشرده مطلوب ساخته می شوند بدون اینکه هیچ کد فشرده دیگری تولید شود. با استفاده از الگوریتم پیشنهادی منابع محاسباتی کمتری برای تولید کدهای مطلوب لازم می شود. به عنوان مثال برای ۳=λ، منابع محاسباتی لازم برای تولید (فقط) کدهای مطلوب، ۵ درصد حالتی است که همه کدهای فشرده تولید شوند.

کلیدواژه ها:

کد فشرده ، مجموع کرافت ، کد هافمن ، بردار چندگانگی ، کوچک ترین طول کلمه کد ، افزونگی