Decision Procedure for the Existence of Two-Channel Prefix-Free Codes
Yin HH, Ng KH, Shing YT, Lai RWF, Wang X (2019)
Publication Type: Conference contribution
Publication year: 2019
Publisher: Institute of Electrical and Electronics Engineers Inc.
Book Volume: 2019-July
Pages Range: 1522-1526
Conference Proceedings Title: IEEE International Symposium on Information Theory - Proceedings
Event location: Paris, FRA
ISBN: 9781538692912
DOI: 10.1109/ISIT.2019.8849758
Abstract
The Kraft inequality gives a necessary and sufficient condition for the existence of a single channel prefix-free code. However, the multichannel Kraft inequality does not imply the existence of a multichannel prefix-free code in general. It is natural to ask whatever there exists an efficient decision procedure for the existence of multichannel prefix-free codes. In this paper, we tackle the two-channel case of the above problem by relating it to a constrained rectangle packing problem. Although a general rectangle packing problem is NP-complete, the extra imposed constraints allow us to propose an algorithm which can solve the problem efficiently.
Authors with CRIS profile
Involved external institutions
China (CN)How to cite
APA:
Yin, H.H., Ng, K.H., Shing, Y.T., Lai, R.W.F., & Wang, X. (2019). Decision Procedure for the Existence of Two-Channel Prefix-Free Codes. In IEEE International Symposium on Information Theory - Proceedings (pp. 1522-1526). Paris, FRA: Institute of Electrical and Electronics Engineers Inc..
MLA:
Yin, Hoover H.F., et al. "Decision Procedure for the Existence of Two-Channel Prefix-Free Codes." Proceedings of the 2019 IEEE International Symposium on Information Theory, ISIT 2019, Paris, FRA Institute of Electrical and Electronics Engineers Inc., 2019. 1522-1526.
BibTeX: Download