Zero-error single-channel source coding has been studied extensively over the past decades. Its natural multi-channel generalization is however not well investigated. While the special case with multiple symmetric-alphabet channels was studied a decade ago, codes in such setting have no advantage over single-channel codes in data compression, making them worthless in most applications. With essentially no development since the last decade, in this paper, we break the stalemate by showing that it is possible to beat single-channel source codes in terms of compression assuming asymmetric-alphabet channels. We present the multi-channel analog of several classical results in single-channel source coding, such as that a multi-channel Huffman code is an optimal tree-decodable code. We also show some evidences that finding an efficient construction of multi-channel Huffman codes may be hard. Nevertheless, we propose a suboptimal code construction whose redundancy is guaranteed to be no larger than that of an optimal single-channel source code.
翻译:在过去几十年中,对零危险单一通道源编码进行了广泛研究,但其自然多通道一般化却没有得到很好地调查。虽然十年前曾对多个对称阿尔法特信道的特例进行了研究,但这种设置的编码在数据压缩方面没有比单一通道编码的优势,使这些编码在大多数应用中毫无价值。由于自过去十年以来基本上没有发展,本文件通过表明有可能在不对称的通道内压缩时,在单一通道源编码中击败单一通道源编码,从而打破了僵局。我们在单通道源编码中展示了多个经典结果的多通道模拟,例如多通道Huffman编码是一种最佳的树代号。我们还表明,找到高效地构建多通道Huffman编码可能很困难。然而,我们提议了一种次优化的编码结构,其冗余保证不会大于最佳的单一通道源编码。