The Optimal Fix-Free Code for Anti-Uniform Sources

Abstract

An n symbol source which has a Huffman code with codelength vector L_n = (1, 2, 3, …, n − 2, n − 1, n − 1) is called an anti-uniform source. In this paper, it is shown that for this class of sources, the optimal fix-free code and symmetric fix-free code is $C_n^{*}=(0,11,101,1001,\cdots ,1\stackrel{n-2}{\overbrace{0\cdots 0}}1).$

1. Introduction

One of the basic problems in the context of source coding is to assign a code C_n = (c₁, c₂, ⋯, c_n) with codelength vector L_n = (ℓ₁, ℓ₂, ⋯, ℓ_n) to a memoryless source with probability vector P_n = (p₁, p₂, ⋯, p_n). Decoding requirements often constrain us to choose a code C_n from a specific class of codes, such as prefix-free codes, fix-free codes or symmetric fix-free codes. With a prefix-free code, no codeword is the prefix of another codeword. This property ensures that decoding in the forward direction can be done without any delay (instantaneously). Alternatively, with a fix-free code no codeword is the prefix or suffix of any other codeword [1,2]. Therefore, decoding of a fix-free code in both the forward and backward directions can be done without any delay. The ability to decode a fix-free code in both directions makes them more robust to transmission errors and faster decoding can be achieved compared to prefix-free codes. As a result, fix-free codes are used in video standards such as H.263+ and MPEG-4 [3]. A symmetric fix-free code is a fix-free code whose codewords are symmetric. In general, decoder implementation for a fix-free code requires more memory compared to that for a prefix-free code. Although the decoder for a symmetric fix-free code is the same as for a fix-free code [4], symmetric codes have greater redundancy in general.

Let $S({\mathit{L}}_n)={\displaystyle {\sum }_{i=1}^n{2}^{-{\ell }_i}}$ denote the Kraft sum of the codelength vector L_n. A well-known necessary and sufficient condition for the existence of a prefix-free code with codelength vector L_n is the Kraft inequality, i.e., S(L_n) ≤ 1 [5]. However, this inequality is only a necessary condition on the existence of a fix-free code. Some sufficient conditions on the existence of a fix-free code were introduced in [6–11].

The optimal code for a specific class of codes is defined as the code with the minimum average codelength, i.e., ${\displaystyle {\sum }_{i=1}^n{p}_i{\ell }_i}$ among all codes in that class. The optimal prefix-free code can easily be obtained using the Huffman algorithm [12]. Recently, two methods for finding the optimal fix-free code have been developed. One is based on the A^* algorithm [13], while the other is based on the concept of dominant sequences [14]. Compared to the Huffman algorithm, these methods are very complex.

A source with n symbols having Huffman code with codelength vector L_n = (1, 2, 3, ⋯, n − 2, n − 1, n − 1) is called an anti-uniform source [15,16]. Such sources have been shown to correspond to particular probability distributions. For example, it was shown in [17] and [18], respectively, that the normalized tail of the Poisson distribution and the geometric distribution with success probability greater than some critical value are anti-uniform sources. It was demonstrated in [15,16] that a source with probability vector P_n = (p₁, p₂, ⋯, p_n) where p₁ ≥ p₂ ≥ ⋯ ≥ p_n, is anti-uniform if and only if

$${\displaystyle \sum _{j=i+2}^n{p}_j\le p_i\text{for}1\le i}\le n-3.$$

(1)

As mentioned above, finding an optimal fix-free or symmetric fix-free code is complex. Thus, in this paper optimal fix-free and symmetric fix-free codes are determined for anti-uniform sources. In particular, it is proven that

$$C_n^{*}=(0,11,101,1001,\cdots ,1\stackrel{n-2}{\overbrace{0\cdots 0}}1),$$

is an optimal fix-free code for this class of sources. Since $C_n^{*}$ is symmetric, this code is also an optimal symmetric fix-free code. Although for an anti-uniform source, the difference between the average codelength of the optimal prefix-free code and $C_n^{*}$ is small (it is exactly equal to p_n), it is not straightforward to prove that $C_n^{*}$ is the optimal fix-free code. In [19], the optimality of $C_n^{*}$ among symmetric fix-free codes for a family of exponential probability distributions, which is an anti-uniform source, was discussed.

In [20], another class of fix-free codes called weakly symmetric fix-free codes was examined. A fix-free code is weakly-symmetric if the reverse of each codeword is also a codeword. In fact, every symmetric fix-free code is a weakly symmetric fix-free code, and every weakly symmetric fix-free code is a fix-free code. Thus, since the optimal code among fix-free codes and symmetric fix-free codes for anti-uniform sources is $C_n^{*}$, this code is also optimal for weakly symmetric fix-free codes.

The remainder of this paper is organized as follows. In Section 2, a sketch of the proofs of the main theorems, i.e., Theorems 1 and 3, is provided, followed by the main results of the paper. Then detailed proofs of these results are given in Section 3.

2. A Sketch of the Proofs

Since a fix-free code is also a prefix-free code, the Kraft sum of an optimal fix-free code is not greater than 1. Therefore, the Kraft sum of this code is either equal to 1 or smaller than 1.

Proposition 1. If

$$({\ell }_1^{*},\cdots ,{\ell }_{n-1}^{*},{\ell }_n^{*})=\arg \underset{L_n:S(L_n)\le 1}{\min }{\displaystyle \sum _{i=1}^n{p}_i{\ell }_i},$$

then we have

$$({\ell }_1^{*},\cdots ,{\ell }_{n-1}^{*},{\ell }_n^{*}+1)=\arg \underset{L_n:S(L_n)<1}{\min }{\displaystyle \sum _{i=1}^n{p}_i{\ell }_i}.$$

It can be inferred from Proposition 1 that if the Kraft sum of an optimal fix-free code is smaller than 1, then the average codelength of this code is not better than the codelength vector $({\ell }_1^{*},\cdots ,{\ell }_{n-1}^{*},{\ell }_n^{*}+1)$. The optimal prefix-free code for an anti-uniform source has codelength vector (1, 2, ⋯, n − 1, n − 1). Therefore, the optimal codelength vector with Kraft sum smaller than 1 for an anti-uniform source is the codelength vector (1, 2, ⋯, n−1, n). Further, the codelength vector of $C_n^{*}$ is (1, 2, ⋯, n−1, n). Thus, if the Kraft sum of the optimal fix-free code for an anti-uniform source is smaller than 1, then the code $C_n^{*}$ is optimal.

Proposition 2. There is no symmetric fix-free code with Kraft sum 1 for n > 2.

According to Proposition 2, the Kraft sum for an optimal symmetric fix-free code is smaller than 1. Thus, Propositions 1 and 2 prove the following theorem.

Theorem 1. The optimal symmetric fix-free code for an anti-uniform source P_n is the code$C_n^{*}$.

There exist fix-free codes with Kraft sum 1, for example (00, 01, 10, 11) and (01, 000, 100, 110, 111, 0010, 0011, 1010, 1011) [21]. Therefore, proving that the code $C_n^{*}$ is the optimal fix-free code for anti-uniform sources requires that the average codelength for this code be better than every possible codelength for a fix-free code. To achieve this, we use the following theorem which was proven in [21].

Theorem 2. [21] Let L_n = (ℓ₁, ⋯, ℓ_n), M_i(L_n) = |{j|ℓ_j = i}| for 1 ≤ i ≤ max_1≤j≤n ℓ_j and$H_i=2i-\frac{1}{i}{\displaystyle {\sum }_{j=1}^i{2}^{(i,j)}}$ where (i, j) denotes the greatest common divisor of i and j. If S(L_n) = 1, M_i(L_n) > H_i for some i and|{ℓ₁, ⋯, ℓ_n}| > 1, then no fix-free code exists with codelength vector L_n.

According to the definition of H_i, we have that H₁ = 0 and H₂ = 1. Therefore from Theorem 2, for L_n with Kraft sum 1 and

$$M_1(L_n)>0\text{and}{L}_n\ne (1,1),$$

or

$$M_2(L_n)>1\text{and}{L}_n\ne (2,2,2,2),$$

there is no fix-free code.

Definition 1. For a given n, let

$${\mathbb{L}}_n=\left\{L_n\right|S(L_n)=1,M_1(L_n)=0\text{and}{M}_2(L_n)\le 1\}.$$

From Theorem 2, if the Kraft sum of the optimal fix-free code is equal to 1, then the average codelength for this code is not smaller than that of the optimal codelength vector among those in ${\mathbb{L}}_n$ for n > 4. It can easily be verified that $\left|{\mathbb{L}}_n\right|=0$ for n < 7. For anti-uniform sources, the following proposition characterizes the optimal codelength vector in ${\mathbb{L}}_n$ for n ≥ 7.

Proposition 3. Let P_n = (p₁, ⋯, p_n−1, p_n) be the probability vector of an anti-uniform source with p₁ ≥ ⋯ ≥ p_n−1 ≥ p_n. Then we have

$$\arg \underset{L_n\in {\mathbb{L}}_n}{\min }{\displaystyle \sum _{i=1}^n{p}_i{\ell }_i}=\{\begin{array}{ll}(2,3,3,3,3,3,3,)& ifn=7\\ (2,3,3,3,3,3,4,5,6,\cdots ,n-6,n-5,n-4,n-4),& ifn>7\end{array}$$

The last step requires that the average codelength of $C_n^{*}$ is better than that of the given codelength vector in Proposition 3. This is given in the proof of the following theorem.

Theorem 3. The optimal fix-free code for an anti-uniform source P_n is$C_n^{*}$ for n > 4.

Note that Theorem 3 is not true for n = 4. For example, for $P_4=(\frac{1}{3},\frac{1}{3},\frac{1}{6},\frac{1}{6})$ which is the probability vector of an anti-uniform source, the average codelength of the fix-free code (00, 01, 10, 11) is better than that of $C_n^{*}$.

3. Proofs of the Results in Section 2

Proof of Proposition 1: Let L_n = (ℓ₁, ⋯, ℓ_n−1, ℓ_n) with ℓ₁ ≤ ⋯ ≤ ℓ_n−1 ≤ ℓ_n and 1 > S(L_n). Thus, we have $2^{{\ell }_n}>2^{{\ell }_n}S(L_n)={\displaystyle {\sum }_{i=1}^n{2}^{{\ell }_n-{\ell }_i}}$, and consequently

$$2^{{\ell }_n}\ge 1+{\displaystyle \sum _{i=1}^n{2}^{{\ell }_n-{\ell }_i}}.$$

Therefore, we can write

$$\begin{array}{l}1\ge {\displaystyle \sum _{i=1}^n{2}^{-{\ell }_i}}+2^{-{\ell }_n}\\ ={\displaystyle \sum _{i=1}^{n-1}{2}^{-{\ell }_i}}+2^{-({\ell }_n-1)}.\end{array}$$

(2)

Let ${L^{\prime }}_n=({{\ell }^{\prime }}_1,\cdots ,{{\ell }^{\prime }}_{n-1},{{\ell }^{\prime }}_n)$ such that ${{\ell }^{\prime }}_i={\ell }_i$ for 1 ≤ i ≤ n − 1, and ${{\ell }^{\prime }}_n={\ell }_n-1$. From (2), we have that $S({L^{\prime }}_n)\le 1$. According to the definition of $({\ell }_1^{*},\cdots ,{\ell }_{n-1}^{*},{\ell }_n^{*})$, we can write

$${\displaystyle \sum _{i=1}^n{p}_i{\ell }_i^{*}}\le {\displaystyle \sum _{i=1}^n{p}_i{{\ell }^{\prime }}_i},$$

and consequently

$$\begin{array}{l}{\displaystyle \sum _{i=1}^{n-1}{p}_i{\ell }_i^{*}}+({\ell }_n^{*}+1)p_n={\displaystyle \sum _{i=1}^n{p}_i{\ell }_i^{*}}+p_n\\ \le {\displaystyle \sum _{i=1}^n{p}_i{{\ell }^{\prime }}_i}+p_n\\ ={\displaystyle \sum _{i=1}^n{p}_i{\ell }_i}.\end{array}$$

This shows that the average codelength of $({\ell }_1^{*},\cdots ,{\ell }_{n-1}^{*},{\ell }_n^{*}+1)$ is better than any other codelength vector, say L_n, with Kraft sum smaller than 1.

Proof of Proposition 2: Suppose that the Kraft sum of L_n, which is the codelength vector of the code C_n, is equal to 1. Let codeword c = x₁x₂·⋯ x _ℓ−10 (resp. c = x₁x₂·⋯ x_ℓ−11) with length ℓ (ℓ > 1), be the longest codeword of C_n. Since the Kraft sum of L_n is equal to 1, the codeword c′ = x₁x₂·⋯ x_ℓ−11 (resp. c′ = x₁x₂·⋯ x_ℓ−10) belongs to C_n. However, both c and c′ cannot be symmetric because x₁ = 0 and x₁ = 1 cannot both be true. Thus, C_n is not a symmetric fix-free code.

The following lemma will be used in the proof of Proposition 3.

Lemma 1. For n ≥ 7, let P_n = (p₁, ⋯, p_n−1, p_n) with p₁ ≥ ⋯ ≥ p_n−1 ≥ p_n and

$${P^{\prime }}_{n-1}=({p^{\prime }}_1,\cdots ,{p^{\prime }}_{n-2},{p^{\prime }}_{n-1})=(p_1,\cdots ,p_{n-2},p_{n-1}+p_n).$$

(3)

Further, suppose that

$$L_n^{*}=({\ell }_1^{*},\cdots ,{\ell }_{n-1}^{*},{\ell }_n^{*})=\arg \underset{L_n\in {\mathbb{L}}_n}{\min }{\displaystyle \sum _{i=1}^n{p}_i{\ell }_i},$$

and for n > 7

$${L^{\prime }}_{n-1}=({{\ell }^{\prime }}_1,\cdots ,{{\ell }^{\prime }}_{n-2},{{\ell }^{\prime }}_{n-1})=\arg \underset{L_{n-1}\in {\mathbb{L}}_{n-1}}{\min }{\displaystyle \sum _{i=1}^{n-1}{p^{\prime }}_i}{\ell }_i.$$

(4)

Then we have

$$({\ell }_1^{*},\cdots ,{\ell }_{n-2}^{*},{\ell }_{n-1}^{*},{\ell }_n^{*})=\{\begin{array}{ll}(2,3,3,3,3,3,3),& ifn=7\\ ({{\ell }^{\prime }}_1,\cdots ,{{\ell }^{\prime }}_{n-2},{{\ell }^{\prime }}_{n-1}+1,{{\ell }^{\prime }}_{n-1}+1),& ifn>7\end{array}$$

(5)

Proof. It can easily be verified that ${\mathbb{L}}_7$ consists of all permutations of 2, 3, 3, 3, 3, 3, 3. Thus, p₁ ≥ ⋯ ≥ p₆ ≥ p₇ completes the proof for n = 7. To prove the lemma for n > 7, we consider two cases: (1) ${\ell }_n^{*}=3$, and (2) ${\ell }_n^{*}>3$. First, note that ${\ell }_n^{*}={\max }_{1\le i\le n}{\ell }_i$, because p₁ ≥ ⋯ ≥ p_n−1 ≥ p_n.

• ${\ell }_n^{*}=3$: It can easily be shown that (3, 3, 3, 3, 3, 3, 3, 3) is the only codelength vector in ${\cup }_{n>7}{\mathbb{L}}_n$ with maximum codelength which is a not greater than 3. Therefore, to prove the lemma in this case it is enough to show that $({{\ell }^{\prime }}_1,\cdots ,{{\ell }^{\prime }}_7)=(3,3,3,3,3,3,2)$. According to the first argument in this proof, the codelength vector $({{\ell }^{\prime }}_1,\cdots ,{{\ell }^{\prime }}_7)$ is a permutation of 2, 3, 3, 3, 3, 3, 3. Thus, proving that p₇ + p₈ is maximum over all probabilities in ${P^{\prime }}_7$, i.e., p₇ + p₈ ≥ p₁, completes the proof for this case. If p₇ + p₈ < p₁, then the average codelength of $({{\ell }^{″}}_1,\cdots ,{{\ell }^{″}}_8)=(2,3,3,3,3,3,4,4)$, is better than that of $({\ell }_1^{*},\cdots ,{\ell }_8^{*})=(3,3,3,3,3,3,3,3)$, because

  $$\begin{array}{l}{\displaystyle \sum _{i=1}^8{p}_i{\ell }_i^{*}=3p_1+3(1-p_1)}\\ \stackrel{(\mathrm{a})}{>}2p_1+3(1-p_1)+p_7+p_8\\ ={\displaystyle \sum _{i=1}^8{p}_i{{\ell }^{″}}_i},\end{array}$$

  where (a) follows from p₇ + p₈ < p₁. Thus, the codelength vector (3, 3, 3, 3, 3, 3, 3) is not optimal, which is a contradiction. Therefore, p₇ + p₈ ≥ p₁ and the proof for this case is complete.
• ${\ell }_n^{*}>3$: The proof for this case is similar to the proof of the Huffman algorithm. Let $L_n=({\ell }_1,\cdots ,{\ell }_n)\in {\mathbb{L}}_n$, i.e., S(L_n) = 1, M₁(L_n) = 0 and M₂(L_n) ≤ 1, with ℓ₁ ≤ ⋯ ≤ ℓ_n and 3 < ℓ_n, and let ${L^{″}}_{n-1}=({{\ell }^{″}}_1,\cdots ,{{\ell }^{″}}_{n-1})=({\ell }_1,\cdots ,{\ell }_{n-2},{\ell }_{n-1}-1)$. It can easily be shown that S(L_n) = 1 implies that ℓ_n = ℓ_n−1. Since ℓ_n = ℓ_n−1, we have $S({L^{″}}_{n-1})=S(L_n)$, and consequently $S({L^{″}}_{n-1})=1$. Further, since ${\ell }_n={\max }_{1\le i\le n}{\ell }_i$ and ℓ_n > 3, M₁(L_n) = 0 and M₂(L_n) ≤ 1 imply that $M_1({L^{″}}_{n-1})=0$ and $M_2({L^{″}}_{n-1})\le 1$, which gives ${L^{″}}_{n-1}\in {\mathbb{L}}_{n-1}$, and we can write

  $$\begin{array}{l}{\displaystyle \sum _{i=1}^n{p}_i{\ell }_i^{*}=\underset{L_n\in {\mathbb{L}}_n}{\min }}{\displaystyle \sum _{i=1}^n{p}_i{\ell }_i}\\ (\underset{¯}{\underset{¯}{\mathrm{a}}})\left[\underset{L_n\in {\mathbb{L}}_n}{\min }{\displaystyle \sum _{i=1}^{n-2}{p}_i{\ell }_i+(p_{n-1}+p_n)({\ell }_{n-1}-1)}\right]+p_{n-1}+p_n\\ (\underset{¯}{\underset{¯}{\mathrm{b}}})\left[\underset{{L^{″}}_{n-1}\in {\mathbb{L}}_{n-1}}{\min }{\displaystyle \sum _{i=1}^{n-1}{p^{\prime }}_i{{\ell }^{″}}_i}\right]+p_{n-1}+p_n\\ (\underset{¯}{\underset{¯}{\mathrm{c}}}){\displaystyle \sum _{i=1}^{n-1}{p^{\prime }}_i{{\ell }^{\prime }}_i}+p_{n-1}+p_n,\end{array}$$

  where (a) follows from ${\ell }_n^{*}={\ell }_{n-1}^{*}$, (b) follows from the definition of ${L^{″}}_{n-1}$ and (3), and (c) follows from (4). Therefore, for n > 7, since the average codelength of the given codelength vector in (5) is equal to ${\displaystyle {\sum }_{i=1}^{n-1}{p^{\prime }}_i{{\ell }^{\prime }}_i+p_{n-1}+p_n}$_, this codelength vector is optimal and the proof is complete.

□

Proof of Proposition 3. The proposition is proved by induction on n. According to Lemma 1, the base of induction, i.e., n = 7, is true. Assume that the proposition is true for all anti-uniform sources with n−1 symbols. Let P_n = (p₁, ⋯, p_n) be the probability vector of an anti-uniform source. Also, suppose that ${P^{\prime }}_{n-1}=({p^{\prime }}_1,\cdots ,{p^{\prime }}_{n-2},{p^{\prime }}_{n-1})=(p_1,\cdots ,p_{n-2,}{p}_{n-1}+p_n)$. From (1), it is obvious that ${P^{\prime }}_{n-1}$ is the probability vector of an anti-uniform source and ${p^{\prime }}_1\ge {p^{\prime }}_2\ge \cdots \ge {p^{\prime }}_{n-3}\ge {p^{\prime }}_{n-2},{p^{\prime }}_{n-1}$. Since we have ${{\ell }^{\prime }}_{n-1}={{\ell }^{\prime }}_n$, where $({{\ell }^{\prime }}_1,\cdots ,{{\ell }^{\prime }}_{n-2},{{\ell }^{\prime }}_{n-1})=\arg {\min }_{L_{n-1}\in {\mathbb{L}}_{n-1}}{\displaystyle {\sum }_{i=1}^{n-1}{p^{\prime }}_i{\ell }_i}$_, from the induction assumption we can write

$$({{\ell }^{\prime }}_1,\cdots ,{{\ell }^{\prime }}_{n-2},{{\ell }^{\prime }}_{n-1})=\{\begin{array}{ll}(2,3,3,3,3,3,3),& \mathrm{if}n-1=7\\ (2,3,3,3,3,3,4,5,\cdots ,n-5,n-5),& \mathrm{if}n-1>7\end{array}.$$

Therefore, we have ${{\ell }^{\prime }}_{n-1}=n-5$, and Lemma 1 completes the proof.

Proof of Theorem 3. We have that $\left|{\mathbb{L}}_5\right|=\left|{\mathbb{L}}_6\right|=0$. Therefore, for n = 5, 6 the proof is complete. The proof for n = 7 is the same as the proof for n > 7, and so is omitted. Now suppose that n > 7. In the following, it is proven that the average codelength vector of $({{\ell }^{\prime }}_1,\cdots {{\ell }^{\prime }}_n)=(2,3,3,3,3,3,4,5,6,\cdots ,n-4,n-4)$ is greater than or equal to that of $C_n^{*}$, i.e., ${\displaystyle {\sum }_{i=1}^{n}i{p}_i}$, which completes the proof.

$$\begin{array}{l}{\displaystyle \sum _{i=1}^n{p}_i{{\ell }^{\prime }}_i=2p_1+3}(p_2+p_3+p_4+p_5+p_6)+{\displaystyle \sum _{i=7}^{n-1}(i-3)p_i+(n-4)p_n}\\ ={\displaystyle \sum _{i=1}^{n}i{p}_i}+p_1+p_2-p_4-2p_5-3p_6-3{\displaystyle \sum _{i=7}^n{p}_i-p_n}\\ ={\displaystyle \sum _{i=1}^{n}i{p}_i}+(p_1-p_3-p_4-p_n)+\left(p_2-{\displaystyle \sum _{i=4}^n{p}_i}\right)+\left(p_3-{\displaystyle \sum _{i=5}^n{p}_i}\right)+\left(p_4-{\displaystyle \sum _{i=6}^n{p}_i}\right)\\ \stackrel{(\mathrm{a})}{\ge }{\displaystyle \sum _{i=1}^{n}i{p}_i},\end{array}$$

where (a) follows from the fact that P_n is the probability vector of an anti-uniform source, i.e., $p_i\ge {\displaystyle {\sum }_{j=i+2}^n{p}_j}$ for n − 3 ≥ i ≥ 1.□