Generating all compact codes with constraint on the smallest codelength

Document Type : Original Article

Authors

Department of electrical and computer engineering, Isfahan University of Technology, Isfahan, Iran

Abstract

Although by employing the Huffman algorithm one can construct the compact code (code with Kraft sum equal to 1) with minimum redundancy for an information source, in some problems it is required to first construct all possible compact codes and then select an appropriate one on the basis of a desired criterion. In particular, if the length of all codewords of an n-tuple compact code is λ or more, then the difference between the largest and the smallest codeword lengths is limited to n-2^λ, and as a result, by considering larger values for λ, the variation in delay of decoding different symbols of the source can be reduced. The main goal of this paper is construction of all such codes and an algorithm is introduced which generates only these codes (i.e., n-tuple compact codes with all codewords of length λ or more). Noting the correspondence between the multiplicity vectors of the compact codes and some sequences of numbers, we find the necessary and sufficient condition that a sequence of numbers is correspondent with a compact code with the shortest codeword at least λ bits long. This way by generating all suitable sequences, all the desired compact codes can be constructed without generating any other compact code. Using the proposed algorithm, less computational resources are required. For example, for λ=3, the required computational resources for generating only the desired compact codes are 5 percent of those when all compact codes are generated.

Keywords

Main Subjects

References

[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
length-limited Huffman codes", Journal of the ACM, vol. 37, no. 3,
pp. 464–473, 1990.
[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
TABRIZ JOURNAL OF ELECTRICAL ENGINEERING
Volume 54, Issue 4 - Serial Number 110
December 2024
Pages 465-476

Files

Share

How to cite

Statistics