On Multi-Channel Huffman Codes for Asymmetric-Alphabet Channels

Our starting point is the observation that, in some cases, a multi-channel code with asymmetric alphabets achieves a better compression ability than an optimal single-channel code. Specifically, we consider the network in Fig. 1 and compare the expected codeword (description) length²²2The description length of a codeword is the number of information unit (e.g., nat) required to represent this codeword. of an optimal $(2,3)$-ary tree-decodable code³³3A multi-channel prefix-free code might not have a decoding tree. We defer the detailed discussion regarding this issue to Section II-D., the binary Huffman code, and the ternary Huffman code for the information sources with probability masses $\{1/6,1/6,1/3,1/3\}$ and $\{1/6,1/6,1/6,1/2\}$ respectively in the following examples. For convenience, we use the information unit nat (base $e$, the Euler’s number) throughout this paper.

We summarize the above two examples and give the numerical values of the expected codeword length in Table I. We can see that the expected codeword length when both channels are in used is shorter than the other two single-channel cases, i.e., the optimal multi-channel source code outperforms the optimal single-channel source codes.

Given the above examples, it is natural to ask if a multi-channel generalization of the Huffman procedure systematically produces an optimal code. We give a partial affirmative answer to the above question. In particular, we formulate the generalized Huffman procedure and show that it indeed produces an optimal tree-decodable code. The generalized Huffman procedure follows the same idea of iteratively merging the smallest probability masses into bigger ones, until reaching probability $1$. However, unlike the single-channel case, there is more than one choice of the number of masses to be merged in each iteration. This results in an exponential number of potential merge sequences, and only choosing a “correct” merging step in every iteration results in an optimal code. It is therefore unclear how the generalized Huffman procedure can be computed in polynomial time.

Towards designing an algorithm which computes or approximates the generalized Huffman procedure in polynomial time, we devise and investigate several heuristics for pruning the merging steps. We first investigate pruning by some natural measures such as (our multi-channel generalization of) local redundancy, expected codeword length, and entropy. Unfortunately none of these simplistic strategies can guarantee the production of an optimal code.

One of our results is the following pruning strategy based on iterative executions of the (single-channel) Huffman procedure: For a multiset of probability masses either given initially or produced by the previous iteration, we run the Huffman procedure on these masses with respect to the alphabet size of each channel. Let $q$ be the alphabet size of the resulting Huffman code with the smallest expected length. We merge the $q$ smallest probability masses into one and proceed to the next round.

Since all single-channel Huffman codes are included as potential choices of the above minimizing procedure, the resulting code guarantees a compression ability no worse than any of the optimal single-channel codes. While we are unable to show that this heuristic produces an optimal tree-decodable code, we have yet to find a counterexample either. We leave it as an open problem to prove the (sub)optimality of the resulting code. We remark that even if the heuristic produces an optimal tree-decodable code, it is unclear if the code is also an optimal prefix code except for the $2$-channel case. It is also unclear if an optimal prefix code is an optimal uniquely decodable code.

We first introduce the background of multi-channel source coding in Section II. Then, we present some generalizations of some well-known results for single-channel source coding in Section III and the multi-channel Huffman procedure for asymmetric-alphabet channels in Section IV. We show some evidence that an efficient construction of multi-channel Huffman codes is not trivial and propose a suboptimal code construction in Section V. Lastly, we conclude the paper and propose some future directions in Section VI.

The definition of a multi-channel source code was proposed in [2] for symmetric-alphabet channels and extended in [3] for asymmetric-alphabet channels. Consider an $n$-channel system where the $i$th channel uses an alphabet $\mathcal{Z}_{i}$ of size $q_{i}$, $i\in[n]$. Without loss of generality, we assume $q_{1}\leq q_{2}\leq\ldots\leq q_{n}$ in this paper. Let $\mathcal{Z}$ be the alphabet of the information source $Z$. Denote by $\epsilon$ the empty string. Define $\mathcal{Z}_{i}^{0}=\{\epsilon\}$ and $\mathcal{Z}_{i}^{j}=\{wv\colon w\in\mathcal{Z}_{i}^{j-1},v\in\mathcal{Z}_{i}\}$ for $j\in\mathbb{Z}^{+}$. That is, $\mathcal{Z}_{i}^{j}$ contains all the strings of length $j$ over the alphabet $\mathcal{Z}_{i}$. The set of all the strings of countable length over the alphabet $\mathcal{Z}_{i}$ is denoted by $\mathcal{Z}_{i}^{\ast}=\bigcup_{j=0}^{\infty}\mathcal{Z}_{i}^{j}$. Every element in $\prod_{i=1}^{n}\mathcal{Z}_{i}^{\ast}$ is called a word.

For any source symbol $z\in\mathcal{Z}$, the ordered $n$-tuple $\mathcal{Q}(z)$ is the codeword for $z$. The $i$th component of the codeword is transmitted through the $i$th channel. When we transmit more than one codeword, the codewords are concatenated channel-wise, i.e., the boundaries of the codewords are not explicit.

By convention, a prefix-free code is also called a prefix code. Any codeword of a uniquely decodable multi-channel source code can be decoded without referring to the symbols of any future codewords if and only if the code is a multi-channel prefix code [2, 3].

As a channel does not interfere the symbols in another channel, we can express a multi-channel word as a single-channel word with a dynamic alphabet. For example, let $\mathcal{Z}_{1}=\{0,1\}$ and $\mathcal{Z}_{2}=\{a,b,c\}$. A $2$-channel word $(01,bca)$ can be expressed as either $01bca$, $0b1ca$, $0bc1a$, $0bca1$, $b01ca$, $b0c1a$, $b0ca1$, $bc01a$, $bc0a1$, or $bca01$. Note that $\mathcal{Z}_{1}$ and $\mathcal{Z}_{2}$ have different letter costs.

However, this single-channel representation is different from a single-channel word with unequal letter cost, a concept proposed in [4]. For example, in a single-channel code with unequal letter cost for the alphabet $\{0,1,a,b,c\}$, the words $0$ and $a$ are prefix-free. However, the $2$-channel words $(0,\epsilon)$ and $(\epsilon,a)$ are not prefix-free although their single-channel representations are $0$ and $a$ respectively.

When the alphabet sizes of the channels are the same, we can see that the single-channel representation of a multi-channel code can be reduced to a single-channel code with equal letter cost. That is why the compression ability cannot be enhanced in the setting proposed in [2].

Let $n$ and $m$ be the number of channels and number of codewords respectively. Denote by $H(\cdot)$ the entropy measured in nats. All results can be trivially generalized to use other bases of logarithm.

The length of the $j$th codeword in the $i$th channel is denoted by $\ell_{i}^{j}$. The length tuple of the $j$th codeword is $(\ell_{1}^{j},\ldots,\ell_{n}^{j})$. The (description) length of the codeword, defined by $\ell^{j}:=\sum_{i}\ell_{i}^{j}\ln q_{i}$, is the number of nats required to represent it. Define $\ell^{\text{max}}_{i}:=\max_{j=1}^{m}\ell_{i}^{j}$.

The multi-channel analog to Kraft inequality and entropy bound were proposed in [2] for symmetric-alphabet channels. They were extended for asymmetric-alphabet channels in the conference paper [3] but their proofs were separated in the preprint [5]. For the sake of completeness, we reproduce the proofs in this paper.

The single-channel Kraft inequality gives a necessary and sufficient condition for the existence of a single-channel uniquely decodable code. However in the multi-channel analog, the sufficiency does not hold in general. The reason can be easily seen from the rectangle packing formulation for prefix codes in [3]: The Kraft inequality only states that the sum of areas of blocks (codewords) is no larger than the area of the container (all possible words). The geometry of the blocks (the packability of the blocks in the container) is not captured. On the other hand, the interpretation of the entropy bound is consistent with the traditional version that the expected codeword (description) length is no less than the entropy.

A single-channel prefix code can be represented by a decoding tree. Each branch of an internal node (including the root node) corresponds to a symbol in the alphabet. When we decode a codeword, we traverse the tree from the root node. We read the symbols in the codeword one by one. For each symbol, we traverse through the corresponding branch. We can decode a codeword once we reach a leaf of the tree.

When it comes to the multi-channel case, each internal node is assigned to a channel. An internal node belongs to class $i$ if it is assigned to the $i$th channel, and is only allowed to have at most $q_{i}$ children. The generalized depth of a leaf is defined as the length of the codeword that the leaf corresponds to. See Figs. 2(a) and 2(b) as examples of a multi-channel decoding tree. A codeword can be decoded by traversing the tree. Suppose the current node being traversed is of class $i$, we read a symbol from the $i$th channel of the codeword and traverse to the corresponding branch. Clearly decoding is sequential, i.e., without referring to the symbols of any future codewords. A code which has a decoding tree is called a tree-decodable code. The decoding tree of an optimal tree-decodable code is called an optimal decoding tree. Note that a tree-decodable code can have more than one decoding tree.

A tree-decodable code is a prefix code [2]. It is because for any two distinct leaves in a decoding tree, the codewords are not prefix of each other on the channel their lowest common ancestor corresponds to. The converse is not true in general for $n>2$ channels. For each channel, if there is a codeword of a prefix code having an empty string in this channel, then we cannot draw a decoding tree for the code. Below is an example given in [2].

The $2$-channel setting is special in the sense that there cannot exist a codeword having an empty string in the first channel, and another codeword having an empty string in the second channel, since they are not prefix-free. With a more careful argument, we have the following theorem.

We first state the following trivial but important result by viewing $q_{i}$-ary source codes as special cases of $(q_{1},\ldots,q_{n})$-ary source codes, which suggests the worthiness of studying multi-channel source codes.

Let $L_{\text{Huff}}$ be the expected codeword length of an optimal $q$-ary single-channel uniquely decodable code. One of the classical results by Shannon [7] which is known as the source coding theorem for symbol codes is that $H(Z)\leq L_{\text{Huff}}<H(Z)+\ln q$. That is, we can use no more than $\ln q$ nats from the entropy to represent an optimal code. The following theorem, which is a natural multi-channel analog, extends a similar idea that we can use no more than $\ln q_{1}$ nats (recall that $q_{1}=\min_{i=1}^{n}q_{i}$) from the entropy to represent an optimal code.

It is also not hard to show that the above upper bound is tight, which is stated in the following theorem.

The concept of local redundancy was introduced in [8], which is a tool for understanding the redundancy of a tree-decodable code. An internal node is a non-leaf node in a decoding tree. In the decoding tree of a single-channel $q$-ary source code, the local redundancy of an internal node $k$ is defined by $r_{k}=s_{k}(\ln q-h_{k})$ where $s_{k}$ and $h_{k}$ are the reaching probability and the entropy of the conditional branching probabilities respectively of node $k$. An interpretation is that we use $\ln q$ nats to represent the branches of node $k$ due to the restriction of the alphabet size, i.e., there are at most $q$ branches in a $q$-ary source code. However, minimally it can be done by $h_{k}$ nats. So, $\ln q-h_{k}$ is the amount of nats wasted at node $k$.

In the decoding tree of a multi-channel tree-decodable code, an internal node corresponds to a channel. Let $\alpha_{k}$ be the alphabet size of the channel node $k$ corresponds to. The number of branches of node $k$ is $\alpha_{k}$. We use $\ln\alpha_{k}$ nats to represent the $\alpha_{k}$ branches at node $k$ but minimally it can be done by $h_{k}$ nats. Therefore, we have the following straightforward extension of local redundancy.

Denote by $\mathcal{I}$ the index set of the internal nodes. Let $L$ be the expected codeword length of a multi-channel tree-decodable code measured in nats. We can show that $H(Z)=\sum_{k\in\mathcal{I}}s_{k}h_{k}$ by a conditional entropy argument. On the other hand, we can show that $L=\sum_{k\in\mathcal{I}}s_{k}\ln\alpha_{k}$ by a weighted bookkeeping argument. Then, by considering the difference $L-H(Z)$, we arrive at a multi-channel generalization of the local redundancy theorem.