تعداد نشریات | 43 |
تعداد شمارهها | 1,253 |
تعداد مقالات | 15,411 |
تعداد مشاهده مقاله | 51,249,522 |
تعداد دریافت فایل اصل مقاله | 14,256,703 |
تولید همه کدهای فشرده با محدودیت روی کوچکترین طولکد | ||
مجله مهندسی برق دانشگاه تبریز | ||
مقالات آماده انتشار، اصلاح شده برای چاپ، انتشار آنلاین از تاریخ 30 بهمن 1402 | ||
نوع مقاله: علمی-پژوهشی | ||
شناسه دیجیتال (DOI): 10.22034/tjee.2024.58987.4752 | ||
نویسندگان | ||
سیدمحمدعلی خسروی فرد* ؛ حامد نریمانی | ||
گروه مخابرات، دانشکده برق و کامپیوتر، دانشگاه صنعتی اصفهان، اصفهان، ایران | ||
چکیده | ||
اگرچه با استفاده از الگوریتم هافمن میتوان کد فشرده (کد با مجموع کرافت مساوی یک) با حداقل افزونگی را برای یک منبع اطلاعات بدون حافظه ساخت، در برخی مسائل لازم میشود که ابتدا همه کدهای فشرده ممکن ساخته شوند و بعد از بین آنها کد مناسب با معیار مورد نظر انتخاب شود. به طور خاص اگر طول همه کلمهکدهای یک کد فشرده n تایی λ یا بیشتر باشد، آنگاه اختلاف بزرگترین و کوچکترین طول کلمهکد آن به n-2^λ محدود میشود و درنتیجه با افزایش مقدار λ میتوان تفاوت در تاخیر کدبرداری سمبلهای مختلف منبع را کاهش داد. ساخت چنین کدهایی هدف اصلی این مقاله است و برای این کار الگوریتمی ارائه میشود که فقط همین کدها (کدهای فشرده n تایی که طول همه کلمهکدهای آنها λ یا بیشتر باشد) را تولید میکند. با توجه به تناظری که بین بردارهای چندگانگی کدهای فشرده با برخی دنبالههای اعداد وجود دارد، شرط لازم و کافی برای اینکه یک دنباله از اعداد متناظر یک کد فشرده که کوتاهترین کلمه کدش حداقل λ بیت باشد را پیدا میکنیم. بدین ترتیب با تولید همه دنبالههای مناسب، همه کدهای فشرده مطلوب ساخته میشوند بدون اینکه هیچ کد فشرده دیگری تولید شود. با استفاده از الگوریتم پیشنهادی منابع محاسباتی کمتری برای تولید کدهای مطلوب لازم میشود. بهعنوان مثال برای 3=λ، منابع محاسباتی لازم برای تولید (فقط) کدهای مطلوب، 5 درصد حالتی است که همه کدهای فشرده تولید شوند. | ||
کلیدواژهها | ||
کد فشرده؛ مجموع کرافت؛ کد هافمن؛ بردار چندگانگی؛ کوچکترین طول کلمهکد؛ افزونگی | ||
مراجع | ||
| ||
آمار تعداد مشاهده مقاله: 57 |