Details

Autor(en) / Beteiligte

• Yin, Hoover H. F.
• Ng, Ka Hei
• Shing, Yu Ting
• Lai, Russell W. F.
• Wang, Xishi

Titel

Decision Procedure for the Existence of Two-Channel Prefix-Free Codes

Ist Teil von

• 2019 IEEE International Symposium on Information Theory (ISIT), 2019, p.1522-1526

Ort / Verlag

IEEE

Erscheinungsjahr

2019

Quelle

IEEE Xplore

Beschreibungen/Notizen

• 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.