2019/04/27 by Hoover H. F. Yin, Ka Hei Ng, Yin, Hoover H. F. +7
Computer Science · Engineering · Mathematics · #Algorithms and Data Compression #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #graph theory and CDMA systems #math.IT #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1904.12112
18 pages; 5 figures; 1 algorithm; full version of the conference paper having the same title which to be appeared in 2019 IEEE International Symposium on Information Theory
arxiv created 2019/04/27 · openalex publication_date 2019/04/27 · arxiv updated 2019/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.