Technical Program

Paper Detail

Paper Title Decision Procedure for the Existence of Two-Channel Prefix-Free Codes
Paper IdentifierWE1.R7.2
Authors Hoover H.F. Yin, Ka Hei Ng, The Chinese University of Hong Kong, Hong Kong SAR of China; Yu Ting Shing, St. Francis Xavier's College, Hong Kong SAR of China; Russell W. F. Lai, Friedrich-Alexander Universität Erlangen-Nürnberg, Germany; Xishi (Nicholas) Wang, The Chinese University of Hong Kong, Hong Kong SAR of China
Session Lossless Compression I
Location Bièvre, Level 5
Session Time Wednesday, 10 July, 09:50 - 11:10
Presentation Time Wednesday, 10 July, 10:10 - 10:30
Manuscript  Click here to download the manuscript
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.