تعداد نشریات | 44 |
تعداد شمارهها | 1,306 |
تعداد مقالات | 15,987 |
تعداد مشاهده مقاله | 52,407,332 |
تعداد دریافت فایل اصل مقاله | 15,167,479 |
تولید همه کدهای فشرده با محدودیت روی کوچکترین طولکد | ||
مجله مهندسی برق دانشگاه تبریز | ||
دوره 54، شماره 4 - شماره پیاپی 110، آذر 1403، صفحه 465-476 اصل مقاله (651.02 K) | ||
نوع مقاله: علمی-پژوهشی | ||
شناسه دیجیتال (DOI): 10.22034/tjee.2024.58987.4752 | ||
نویسندگان | ||
حامد نریمانی؛ سیدمحمدعلی خسروی فرد* | ||
دانشیار، دانشکده مهندسی برق و کامپیوتر، دانشگاه صنعتی اصفهان، اصفهان، ایران | ||
چکیده | ||
اگرچه با استفاده از الگوریتم هافمن میتوان کد فشرده (کد با مجموع کرافت مساوی یک) با حداقل افزونگی را برای یک منبع اطلاعات بدون حافظه ساخت، در برخی مسائل لازم میشود که ابتدا همه کدهای فشرده ممکن ساخته شوند و بعد از بین آنها کد مناسب با معیار مورد نظر انتخاب شود. به طور خاص اگر طول همه کلمهکدهای یک کد فشرده n تایی λ یا بیشتر باشد، آنگاه اختلاف بزرگترین و کوچکترین طول کلمهکد آن به n-2^λ محدود میشود و درنتیجه با افزایش مقدار λ میتوان تفاوت در تاخیر کدبرداری سمبلهای مختلف منبع را کاهش داد. ساخت چنین کدهایی هدف اصلی این مقاله است و برای این کار الگوریتمی ارائه میشود که فقط همین کدها (کدهای فشرده n تایی که طول همه کلمهکدهای آنها λ یا بیشتر باشد) را تولید میکند. با توجه به تناظری که بین بردارهای چندگانگی کدهای فشرده با برخی دنبالههای اعداد وجود دارد، شرط لازم و کافی برای اینکه یک دنباله از اعداد متناظر یک کد فشرده که کوتاهترین کلمه کدش حداقل λ بیت باشد را پیدا میکنیم. بدین ترتیب با تولید همه دنبالههای مناسب، همه کدهای فشرده مطلوب ساخته میشوند بدون اینکه هیچ کد فشرده دیگری تولید شود. با استفاده از الگوریتم پیشنهادی منابع محاسباتی کمتری برای تولید کدهای مطلوب لازم میشود. بهعنوان مثال برای 3=λ، منابع محاسباتی لازم برای تولید (فقط) کدهای مطلوب، 5 درصد حالتی است که همه کدهای فشرده تولید شوند. | ||
کلیدواژهها | ||
کد فشرده؛ مجموع کرافت؛ کد هافمن؛ بردار چندگانگی؛ کوچکترین طول کلمهکد؛ افزونگی | ||
مراجع | ||
[1] ثریا عمویی، کمال میرزایی، « فشردهسازی تصویر توسط چندیسازی برداری مبتنی بر الگوریتم کرم شبتاب بهبودیافته »، مجله مهندسی برق دانشگاه تبریز، جلد 49، شماره 2، صفحات 693-707، 1398. [2] محمود طوماری، سپیده جباری، « فشردهسازی سیگنالهای ژنوم با کمک حسگری فشرده و کاربرد آن در مقایسه دنبالههای ژنی»، مجله مهندسی برق دانشگاه تبریز، جلد 49، شماره 1، صفحات 307-316، 1398. [3] مریم مگری، هادی گرایلو، « فشردهسازی سیگنالهای الکترومایوگرام مبتنی بر هموارسازی به کمک تکنیک پیشتاکید-واتاکید»، مجله مهندسی برق دانشگاه تبریز، جلد 49، شماره 4، صفحات 1837-1848، 1398. [4] T. M. Cover, J. A. Thomas, "Elements of information theory", Wiley, New York, 1991. [5] Y. G. Chen, C. Elsholtz, L. L. Jiang, "Egyptian fractions with restrictions", Acta Arithmetica, vol. 154, no. 2, pp. 109–123, 2012. [6] F. N. Castro, "On the Equation in Distinct Odd or Even Numbers", Contributions to Discrete Mathematics, vol. 11, no. 2, pp. 63-78, 2017. [7] J. Leeuwen, "On the construction of Huffman trees", Proceedings of Third International Colloquium on Automata, Languages and Programming, pp. 382-410, 1976. [8] J. Rissanen, "Minimax codes for finite alphabets", IEEE Transactions on Information Theory, vol. 24, no. 3, pp. 389–392, 1978. [9] A. Mahmood, A. B. Wagner, "Minimax Rate-Distortion", IEEE Transactions on Information Theory, vol. 69, no. 12, pp. 7712–7737, 2023. [10] M. Khosravifard, H. Saidi, M. Esmaeili, T.A. Gulliver, "The minimum average code for finite memoryless monotone sources", IEEE Transactions on Information Theory, vol. 53, no. 3, pp. 957–977, 2007. [11] H. Narimani, M. Khosravifard, "A new code for encoding all monotone sources with a fixed large alphabet size", IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1474–1481, 2020. [12] S. Banchhor, R. Gajjala, Y. Sabharwal, S. Sen, "Generalizations of Length Limited Huffman Coding for Hierarchical Memory Settings", arXiv preprint arXiv:2010.05005, 2021. [13] G. Lakhani, "Modified JPEG Huffman coding", IEEE Transactions on Image Processing, vol. 12, no. 2, pp.159-169, 2003. [14] L. L. Larmore, D. S. Hirschberg, "A fast algorithm for optimal [15] M. Khosravifard, M. Esmaeili, H. Saidi, T. Aron Gulliver, "A tree based algorithm for generating all possible binary compact codes with N codewords," IEICE Transactions Fundamentals, vol. E86-A, no. 10, pp. 2510-2516, 2003. [16] S. Even, A. Lempel, "Generation and enumeration of all solutions of the characteristic sum condition", Information and Control, vol. 21, pp. 476-482, 1972. [17] P. Flajolet, H. Prodinger, "Level number sequences for trees", Discrete Mathematics, vol. 65, no. 2, pp. 149–156, 1987. [18] H. Narimani, M. Khosravifard, "The supertree of the compact codes", Proceedings of International Symposium on Telecommunications (IST), pp. 649-655, 2008. [19] D. Hoffman, P. Johnson, N. Wilson, "Generating Huffman sequences", Journal of Algorithms, vol. 54, pp. 115-121, 2005. [20] E. Norwood, "The number of different possible compact codes", IEEE Transactions on Information Theory, vol. 13, no. 4, pp. 613-616, 1967. [21] C. Elsholtz, C. Heuberger, H. Prodinger, "The number of Huffman codes, compact trees, and sums of unit fractions", IEEE Transactions on Information Theory, vol. 59, no. 2, pp. 1065-1075, 2013. [22] C. Elsholtz, C. Heuberger C, D. Krenn, "Algorithmic counting of nonequivalent compact Huffman codes", Applicable Algebra in Engineering, Communication and Computing, Jan. 2023 Available online at: https://doi.org/10.1007/s00200-022-00593-0. [23] J. Paschke, J. Burkert, R. Fehribach, "Computing and estimating the number of n-ary Huffman sequences of a specified length", Discrete Mathematics, vol. 311, pp. 1-7, 2011. [24] K. Hashimoto, K. Iwata, H. Yamamoto, "Enumeration and Coding of Compact Code Trees for Binary AIFV Codes", Proceedings IEEE International Symposium on Information Theory (ISIT), pp. 1527-1531, Jul. 2019. [25] J. Komlos, W. Moser, T. Nemetz, "On the asymptotic number of prefix codes", Mitteilungen aus dem Mathematischen Seminar Giessen, Heft 165, Teil III, pp. 35-48, 1984. [26] D. Krenn, S. Wagner, "Compositions into powers of b: asymptotic enumeration and parameters", Algorithmica, vol. 75, pp. 606-631, 2016. [27] مهرزاد منصوری «بررسی بسامد نویسههای فارسی و مناسبت جایگاه آنها بر صفحه کلید رایانهها»، مجله زبانشناسی و گویشهای خراسان، شماره 7، صفحات 109-129 ، پاییز و زمستان 1391 | ||
آمار تعداد مشاهده مقاله: 118 تعداد دریافت فایل اصل مقاله: 30 |