# General Form of Almost Instantaneous
Fixed-to-Variable-Length Codes

Ryosuke Sugiura, Yutaka Kamamoto, and Takehiro Moriya

###### Abstract

A general class of the almost instantaneous fixed-to-variable-length (AIFV)
codes is proposed, which contains every possible binary code we can make when
allowing finite bits of decoding delay. The contribution of the paper lies in
the following. (i) Introducing $N$-bit-delay AIFV codes, constructed by
multiple code trees with higher flexibility than the conventional AIFV codes.
(ii) Proving that the proposed codes can represent any uniquely-encodable and
uniquely-decodable variable-to-variable length codes. (iii) Showing how to
express codes as multiple code trees with minimum decoding delay. (iv)
Formulating the constraints of decodability as the comparison of intervals in
the real number line. The theoretical results in this paper are expected to be
useful for further study on AIFV codes.

##  1 Introduction

For years, years, data compression techniques have greatly contributed to the
development of many coding applications, such as audio and video codecs [1, 2,
3, 4], which are now essential for our communication tools. Especially,
lossless compression is one of the fundamental factors even for lossy
situations [5, 6]. In audio and video codecs, compression schemes are often
required to encode given sequences of input signals with their distributions
assumed using some models. There are two well-known approaches for compression
in these cases: Huffman coding [7, 8] gives us the minimum-redundancy codes
among instantaneously decodable fixed-to-variable-length (FV) codes;
arithmetic coding [2, 8, 9] gives us variable-to-variable-length (VV) codes
which are not necessarily minimum redundancy but asymptotically achieve
entropy rates when the input sequence is long enough.

Although Huffman coding guarantees its optimality, it shows lower compression
efficiency compared to the arithmetic coding for many practical cases. This
fact is mainly due to its constraint of instantaneous decodability, which
strongly restricts the flexibility of the codeword construction: Instantaneous
FV codes only allow the set of codewords that can be represented as a single
code tree, with the input source symbols separately assigned to its leaves.

Yamamoto ${\it et}$ ${\it al}$. proposed a more flexible class of FV codes,
the almost instantaneous FV (AIFV) codes [10, 11, 12]. They loosen the
constraints mentioned above by permitting, in binary code symbol cases, two
bits of delay for decoding. This relaxation enables us to construct two code
trees to represent codewords with more freedom for the source symbol
assignment. This scheme is extended as AIFV-$m$ codes [13, 14, 15, 16], which
permit $m$ bits of decoding delay to use $m$ code trees to represent
codewords.

AIFV-$m$ codes have more freedom for codeword construction than the
instantaneous ones and can potentially outperform Huffman codes. However, we
cannot say that AIFV-$m$ codes are fully using the advantage of decoding delay
relaxation. Our previous works [17, 18] revealed some types of practical AIFV
codes that do not follow the rules for AIFV-$m$ codes. This paper aims to show
what kind of code trees we can actually construct under a given decoding
delay, which must be useful to make better use of the almost-instantaneous
condition.

The paper first prepares the basic ideas in Section 2, reviewing the
conventional AIFV codes and clarifying the general definition of decoding
delay. Then, in Section 3, we define a broader class of AIFV codes proving its
decodability and generality. Fundamental properties of the code-tree structure
are analyzed theoretically in Section 4, which are expected to be essential
for constructing code trees. Here, we focus only on binary code symbols for
simplicity. However, it should be noted that the proposed scheme can also be
applied to the cases of non-binary code symbols.

##  2 Preliminaries

###  2.1 Notations

The notations below are used for the following discussions.

  * •

$\mathbb{N}$: The set of all natural numbers.

  * •

$\mathbb{R}$: The set of all real numbers.

  * •

$\mathbb{Z}^{+}$: The set of all non-negative integers.

  * •

$\mathbb{Z}^{+}_{<M}$: The set of all non-negative integers smaller than an
integer $M$.

  * •

$\mathbb{A}_{M}$: $\\{a_{m}\mid m\in\mathbb{Z}^{+}_{<M}\\}$, the source
alphabet of size $M$.

  * •

$\mathbb{S}_{M}$: the Kleene closure of $\mathbb{A}_{M}$, or the set of all
$M$-ary source symbol sequences, including a zero-length sequence $\epsilon$.

  * •

$\mathbb{W}$: The set of all binary strings, including a zero-length one
‘$\lambda$’. ‘$\lambda$’ can be a prefix of any binary string.

  * •

$\mathbb{M}$:
$\\{\textsc{Words}\subseteq\mathbb{W}\mid\textsc{Words}\neq\emptyset\\}$, the
set of all non-empty subsets of $\mathbb{W}$.

  * •

$\preceq$, $\npreceq$, $\prec$, $\nprec$: Dyadic relations defined in
$\mathbb{W}$. $w\preceq w^{\prime}\text{ (resp.~{}$w\npreceq w^{\prime}$) }$
indicates that $w$ is (resp. is not) a prefix of $w^{\prime}$. $\prec$ (resp.
$\nprec$) excludes $=$ (resp. $\neq$) from $\preceq$ (resp. $\npreceq$).

  * •

$\mathbb{PF}$: $\\{\textsc{Words}\in\mathbb{M}\mid\forall w\neq
w^{\prime}\in\textsc{Words}:w\npreceq w^{\prime}\\}$, the set of all prefix-
free binary string sets.

  * •

$\parallel$: A dyadic relation defined for $\mathbb{W}$ or $\mathbb{M}$. For
$\mathbb{W}$, $w\parallel w^{\prime}$ indicates that $w$ and $w^{\prime}$
satisfy either $w\preceq w^{\prime}$ or $w^{\prime}\preceq w$. If $w\npreceq
w^{\prime}$ and $w^{\prime}\npreceq w$, we write $w\nparallel w^{\prime}$. For
$\mathbb{M}$, $\textsc{Words}\parallel\textsc{Words}^{\prime}$ indicates that
there are some $w\in\textsc{Words}$ and $w^{\prime}\in\textsc{Words}^{\prime}$
satisfying $w\parallel w^{\prime}$.
$\textsc{Words}\nparallel\textsc{Words}^{\prime}$ means any pair of
$w\in\textsc{Words}$ and $w^{\prime}\in\textsc{Words}^{\prime}$ is
$w\nparallel w^{\prime}$.

  * •

$\oslash$: An operator defined for $\mathbb{W}$. $w_{\rm pre}\oslash w$
subtracts the prefix $w_{\rm pre}$ from $w$.

  * •

$\|\cdot\|_{\rm len}$: The length of a sequence in $\mathbb{S}_{M}$ or a
string in $\mathbb{W}$.

Note that $\preceq$ is a partial order on $\mathbb{W}$, which satisfies
reflexivity, antisymmetry, and transitivity, while $\parallel$ is a dependency
relation, which satisfies reflexivity and symmetry but not transitivity.

###  2.2 Conventional binary AIFV and AIFV-$m$ codes

(a) Example of a binary AIFV code, equivalent to one shown in [10].  (b)
Example of an AIFV-$m$ code, equivalent to one shown in [13].

Figure 1: Examples of the conventional codes. Square boxes indicate the nodes
assigned with source symbols.

As we mentioned in the introduction, the conventional binary AIFV codes [10]
prepare multiple code trees to represent more flexible encoding rules. The
code trees $T_{0}$ and $T_{1}$ are constructed to follow the rules below.

######  Rule 1 (Properties the code trees of binary AIFV codes must satisfy
[10])

  1. a.

Incomplete internal nodes (nodes with one child) are divided into two
categories, master nodes and slave nodes.

  2. b.

Source symbols are assigned to either master nodes or leaves.

  3. c.

The child of a master node must be a slave node, and the master node is
connected to its grandchild by code symbols ‘00’.

  4. d.

The root of $T_{1}$ has two children. The child connected by ‘0’ from the root
is a slave node. The slave node is connected by ‘1’ to its child.

This rule allows us to combine two code trees to a single coding rule. The
encoding works by switching the code trees according to the previous input:

######  Procedure 1 (Encoding a source symbol sequence into a binary AIFV
codeword sequence [10])

Follow the steps below for the input symbol sequence $x_{0}x_{1}\cdots$.

  1. a.

Use $T_{0}$ to encode the initial source symbol $x_{0}$.

  2. b.

When $x_{i}$ is encoded by a leaf (resp. a master node), then use $T_{0}$
(resp. $T_{1}$) to encode the next symbol $x_{i+1}$.

Fig. 1 shows an example of a set of code trees $T_{0}$ and $T_{1}$ constructed
for source symbols $\\{a,b,c,d\\}\in\mathbb{A}_{4}$. Under the restrictions of
Rule 1, we can assign source symbols to internal nodes, as well as to leaves.
In this paper, we write the code-tree switching rules in the nodes with their
assigned source symbols to make them clear.

For example, let us encode $acca$ using the code trees in Fig. 1 (a). The
encoder starts with $T_{0}$ to encode $a$, outputting the codeword ‘0’. Then,
it encodes $c$ by $T_{0}$ as ‘11’ and switches the code tree to $T_{1}$.
$T_{1}$ gives another ‘11’ for $c$, with the code tree still being $T_{1}$.
Similarly, ‘01’ is output for $a$ with $T_{1}$ used. As a result, the encoded
codeword sequence becomes ‘0111101’. By using two code trees, we can assign
the codewords more flexibly than a single one: In the case of Fig. 1 (a), by
introducing a slave node above the leaf assigned with $d$, a 2-bit codeword
becomes available for $c$, which is impossible to assign in the binary Huffman
codes for $\\{a,b,c,d\\}$ when $a$ is 1 bit and $b$ is 2 bits.

The decoding also uses the code-tree switching to decode the source symbols
uniquely:

######  Procedure 2 (Decoding a source symbol sequence from a binary AIFV
codeword sequence [10])

Follow the steps below for the input codeword sequence.

  1. a.

Use $T_{0}$ to decode the initial source symbol $x_{0}$.

  2. b.

Trace the codeword sequence as long as possible from the root in the current
code tree. Then, output the source symbol assigned to the reached master node
or leaf.

  3. c.

If the reached node is a leaf (resp. a master node), then use $T_{0}$ (resp.
$T_{1}$) to decode the next source symbol from the current position on the
codeword sequence.

Decoding the codeword sequence in the above example goes as follows. The
decoder starts the decoding from $T_{0}$, tracing the codeword sequence
‘0111101’ as long as possible from the root. It reaches the leaf ‘0’ assigned
with $a$, and thus $x_{0}=a$. Then, the decoder traces the sequence ‘111101’
according to $T_{0}$ again. Since ‘11’ is a master node assigned with $c$ but
‘111’ is not in $T_{0}$, the decoder can determine $x_{1}$ as $c$, switching
the code tree to $T_{1}$. The next symbol is decoded from the sequence ‘1101’.
‘11’ is a master node assigned with $c$, but ‘1101’ is not in $T_{1}$.
Therefore, $x_{3}$ is $c$, and $x_{4}$ is decoded from ‘01’ by $T_{1}$. The
decoder can reach the leaf ‘01’ of $T_{1}$ assigned with $a$, and thus
$x_{4}=a$. As a result, we can get the correct source symbol sequence $acca$.

When decoding $c$ in the example, the decoder checks at most 2 bits after
getting the codeword ‘11’ for $c$ to confirm whether the encoder encoded $c$
and switched the code tree to $T_{1}$ or encoded $d$ instead of $c$. This
check requires 2 bits of decoding delay for the decoder.

As explained above, the binary AIFV code uses two code trees, permitting 2
bits of decoding delay. As an extension, AIFV-$m$ code is presented [13] to
tune the bit length with finer precision using more decoding delay. It uses
$m$ code trees, permitting $m$ bits of decoding delay. The rules for the code
trees $T_{0},T_{1},\cdots,T_{m-1}$ are modified from Rule 1 as follows.

######  Rule 2 (Properties the code trees of AIFV-$m$ codes must satisfy [13])

  1. a.

Any node in the code trees is either a slave node, a master node, or a
complete internal node. Source symbols are only assigned to master nodes.

  2. b.

The degree $k$ of master nodes must satisfy $0\leq k<m$.

  3. c.

$T_{k}$ ($1\leq k<m$) has a node connected to the root by a $k$-length run of
zeros and is a slave-1 node.

The terms used in this rule are defined as follows.

  * •

Slave-0 node (resp. slave-1 node): A slave node that connects to its child by
‘0’ (resp. ‘1’).

  * •

Master node of degree $k$: For $k>0$, an incomplete internal node satisfying
(i) $k$ consecutive-descendant nodes are slave-0 nodes and (ii) the $(k+1)$-th
descendant is not a slave-0 node. The master nodes of degree 0 are treated as
leaves.

As the binary AIFV coding, AIFV-$m$ coding introduces a code-tree switching
rule to realize uniquely-decodable codes from multiple code trees:

######  Procedure 3 (Encoding a source symbol sequence into an AIFV-$m$
codeword sequence [13])

Follow the steps below for the input symbol sequence $x_{0}x_{1}\cdots$.

  1. a.

Use $T_{0}$ to encode the initial source symbol $x_{0}$.

  2. b.

When $x_{i}$ is encoded by a master node of degree $k$, then use $T_{k}$ to
encode the next symbol $x_{i+1}$.

######  Procedure 4 (Decoding a source symbol sequence from an AIFV-$m$
codeword sequence [13])

Follow the steps below for the input codeword sequence.

  1. a.

Use $T_{0}$ to decode the initial source symbol $x_{0}$.

  2. b.

Trace the codeword sequence as long as possible from the root in the current
code tree. Then, output the source symbol assigned to the reached master node
or leaf.

  3. c.

If the reached node is a master node of degree $k$, then use $T_{k}$ to decode
the next source symbol from the current position on the codeword sequence.

Fig. 1 (b) gives an example of an AIFV-3 code. We can see that the switching
rule is controlled by the number of consecutive incomplete nodes below the
master node: $T_{0}$ switches to $T_{1}$ after encoding/decoding $c$ since
there is one slave-0 node below the master node assigned with $c$; $T_{1}$
switches to $T_{2}$ after encoding/decoding $c$ since there are two slave-0
nodes below the master node assigned with $c$. When decoding $c$ by $T_{1}$,
the decoder has to check at most 3 bits after getting the codeword ‘11’ for
$c$ to confirm whether the encoder encoded $c$ and switched the code tree to
$T_{2}$ or encoded $d$ instead of $c$.

Both the binary AIFV and AIFV-$m$ codes determine the switching rules by one-
to-one correspondence between which code tree to switch and the number of
consecutive-descendant slave-0 nodes of the nodes assigned with the source
symbols: The code tree always switches to $T_{k}$ if and only if we
encode/decode source symbols whose nodes have $k$ consecutive-descendant
slave-0 nodes; the code tree always switches to $T_{0}$ if and only if we
encode/decode the source symbols assigned to leaves. This restriction strongly
limits the variety of codes represented by the multiple code trees. When we
are allowed $m$ bits of decoding delay, we have to use $m$ consecutive-
descendant slave-0 somewhere to fully utilize the permitted delay. However, it
makes a large difference between the code lengths of the source symbols
assigned to the master node of degree $m$ and its descendant node. Therefore,
AIFV-$m$ codes need the source distributions to be biased if we want to
enhance the compression efficiency by using larger values for $m$.

Moreover, the conventional AIFV codes cannot represent all the codes we can
uniquely decode with a given delay. The AIFV codes presented in our previous
works [17, 18] are uniquely decodable, although they do not obey Rule 2. Note
that they are designed for infinite source symbols $\mathbb{A}_{\infty}$ but
can be truncated to represent AIFV codes for finite source symbols. In the
later sections, we propose a scheme of AIFV codes to represent any code of a
given decoding delay.

###  2.3 Decoding delay for general codes

####  2.3.1 Definition and an example for Huffman code

Figure 2: Example of a Huffman code.

For the later discussions, let us clarify the definition of delay. In this
paper, we focus on the delay that happens in decoding each source symbol
sequentially.

######  Definition 1 (Decoding delay for $s\in\mathbb{S}_{M}$)

The maximum length of the binary string needed for the decoder to determine
$s$ from $\\{s^{\prime}\in\mathbb{S}_{M}\mid\|s^{\prime}\|_{\rm
len}=\|s\|_{\rm len}\\}$ as its output, after reading the codeword that the
encoder can immediately determine as its output when encoding $s$.

######  Definition 2 (Decoding delay of a code)

The maximum decoding delay for all $s\in\mathbb{S}_{M}$.

This definition of delay can be applied generally. For example, Let us think
of an extended Huffman code [9], a Huffman code for a Cartesian product of
source symbols, as in Fig. 2. From now on, we omit the code symbol for each
edge when two edges are connected to the same node and assume left-hand-side
(resp. right-hand-side) edges are for code symbol ‘0’ (resp. ‘1’). This code
is instantaneously decodable if we interpret
$\\{aa,ab,ac,ba,bb,bc,ca,cb,cc\\}$ as $\mathbb{A}_{9}$, and thus has no
decoding delay for $aa,ab,ac,ba,bb,bc,ca,cb$, and $cc$. However, if we
interpret it as a code for $\mathbb{A}_{3}=\\{a,b,c\\}$, we can break down the
code to decode the source symbols sequentially and define the decoding delay
for $a$, $b$, and $c$.

In the case of Fig. 2, the encoder can immediately determine ‘0’ as its output
when encoding $a$ because ‘0’ is a prefix of every codeword corresponding to
the sequence beginning with $a$. The decoder can also determine $a$ as its
output when decoding ‘0’ because every codeword having a prefix ‘0’
corresponds to the symbol sequences beginning with $a$. Therefore, the
decoding delay for the source symbol $a$ is zero. On the other hand, the
encoder can immediately determine ‘1’ as its output when encoding $b$ because
‘1’ is a prefix of every codeword corresponding to the sequence beginning with
$b$. However, the decoder cannot determine $b$ as its output only by getting
‘1’ because the codewords corresponding to the sequences beginning with $c$
also begin with ‘1’. For this sake, the decoder has to read ‘01’, ‘100’, or
‘110’ after ‘1’ to determine $b$ as its output. Similarly, the decoder has to
read ‘00’, ‘101’, or ‘111’ to determine $c$ as its output. Therefore, the
extended Huffman code of this example is decodable with a decoding delay of 3
bits.

####  2.3.2 Leading and following codewords

When thinking of a code with a non-symbol-wise coding rule like the extended
Huffman code, its decoding delay depends on how we break down a code to make
symbol-wise decoding, and in general, the way of breaking down a code is not
unique: The example stated above for Fig. 2 shows one way of breaking down the
extended Huffman code, but it is not the only way to get a symbol-wise coding
rule. Although it is more awkward, we can say, for instance, that the encoder
can immediately determine ‘$\lambda$’ as its output when encoding $b$ because
‘$\lambda$’ is a prefix of every codeword corresponding to the sequence
beginning with $b$ in Fig. 2. In this case, the decoder has to read ‘101’,
‘1100’, or ‘1110’ after ‘$\lambda$’ to determine $b$ as its output. When
breaking down the code in this way and implementing symbol-wise encoder and
decoder according to it, the decoding delay becomes 4 bits. The important fact
for the main discussion is that we can break down a code in some way, even if
it is not defined in a symbol-wise manner.

Considering the above fact, we generalize the idea to arbitrary VV codes. Say
$V:\mathbb{S}_{M}\to\mathbb{W}$ is some VV code. We define some terms using
$V(s)$ for any source symbol sequence $s(\in\mathbb{S}_{M})$:

  * •

$\textrm{Lcword}_{V}(s)$: Leading codeword, a codeword that the encoder of $V$
can immediately determine as its output when encoding $s$, regardless of its
succeeding source symbols. In other words, one picked up from
$\\{w\in\mathbb{W}\mid\forall\textrm{Tail}\in\mathbb{S}_{M}:w\preceq
V(s\textrm{Tail})\\}$. It is arbitrarily selected for each $s$. By definition,
$\textrm{Lcword}_{V}(\epsilon)=$‘$\lambda$’.

  * •

$\textrm{Fcword}_{V}(s|\textrm{Tail})$: Following codeword, a codeword that
follows the leading codeword $\textrm{Lcword}_{V}(s)$ when encoding
$s\textrm{Tail}$ by $V$. In other words, one picked up from
$\\{w\mid\textrm{Lcword}_{V}(s)w\preceq V(s\textrm{Tail}),w\in\mathbb{W}\\}$.
It is arbitrarily selected for each $(s,\textrm{Tail})$.

When a code $V(s)$ is given, we have some choices of which binary string to
set as $\textrm{Lcword}_{V}(s)$ for each $s$. The leading codeword
$\textrm{Lcword}_{V}(s)$ can be any binary string that forms a common prefix
of all encoded words staring with $s$. For given $V(s)$ and
$\textrm{Lcword}_{V}(s)$, we also have some choices for
$\textrm{Fcword}_{V}(s|\textrm{Tail})$. The following codeword
$\textrm{Fcword}_{V}(s|\textrm{Tail})$ can be any binary string that makes
$\textrm{Lcword}_{V}(s)\textrm{Fcword}_{V}(s|\textrm{Tail})$ a prefix of
$V(s\textrm{Tail})$ and enables the decoder to decode $s$ from
$\textrm{Lcword}_{V}(s)\textrm{Fcword}_{V}(s|\textrm{Tail})$.

Using the notation above, we can write as follows the condition where the
decoder of $V$ can determine $s$ as its output.

$\forall s^{\prime}\neq s,\|s^{\prime}\|_{\rm len}=\|s\|_{\rm
len},\forall\textrm{Tail},\textrm{Tail}^{\prime}\in\mathbb{S}_{M}:\textrm{Lcword}_{V}(s)\textrm{Fcword}_{V}(s|\textrm{Tail})\nparallel\textrm{Lcword}_{V}(s^{\prime})\textrm{Fcword}_{V}(s^{\prime}|\textrm{Tail}^{\prime}).$
(1)

If $V(s)$ is decodable with a decoding delay of $N$ bits, it means we can set
such leading and following codewords with the length of the following codeword
not longer than $N$ bits. For uniquely decodable $V(s)$, we can always set
some leading and following codewords satisfying Eq. (1) because, in the worst
case, setting
$\textrm{Fcword}_{V}(s|\textrm{Tail})=\textrm{Lcword}_{V}(s)\oslash
V(s\textrm{Tail})$ will do. Note that $\textrm{Lcword}_{V}(s)$ can take
‘$\lambda$’ so that we can always set the leading codewords as well.

Table 1: Example of the leading and following codewords for the code in Fig. 2.  $s_{1}$ | $\textrm{Lcword}_{V}(s_{1})$ | $s_{2}$ | $\textrm{Fcword}_{V}(s_{1}|s_{2})$ |  | $s_{1}$ | $\textrm{Lcword}_{V}(s_{1})$ | $s_{2}$ | $\textrm{Fcword}_{V}(s_{1}|s_{2})$
---|---|---|---|---|---|---|---|---
$a$ | ‘0’ | $a$ | ‘$\lambda$’ |  | $aa$ | ‘00’ | $\epsilon$ | ‘$\lambda$’
$b$ |  | $ab$ | ‘010’
$c$ |  | $ac$ | ‘011’
$b$ | ‘1’ | $a$ | ‘01’ |  | $ba$ | ‘101’
$b$ | ‘110’ |  | $bb$ | ‘1110’
$c$ | ‘100’ |  | $bc$ | ‘1100’
$c$ | ‘1’ | $a$ | ‘00’ |  | $ca$ | ‘100’
$b$ | ‘101’ |  | $cb$ | ‘1101’
$c$ | ‘111’ |  | $cc$ | ‘1111’

For the code of Fig. 2, we can set the leading and following codewords as in
Table 1. Owing to this setting, for example, we can retrieve $a$ from
$\textrm{Lcword}_{V}(a)\textrm{Fcword}_{V}(a|a)=\textrm{Lcword}_{V}(a)\textrm{Fcword}_{V}(a|b)=\textrm{Lcword}_{V}(a)\textrm{Fcword}_{V}(a|c)=$‘0’
and $b$ from $\textrm{Lcword}_{V}(b)\textrm{Fcword}_{V}(b|a)$=‘101’,
$\textrm{Lcword}_{V}(b)\textrm{Fcword}_{V}(b|b)$=‘1110’, or
$\textrm{Lcword}_{V}(b)\textrm{Fcword}_{V}(b|c)$=‘1100’.

Moreover, by breaking down the codewords, we can determine the codewords for
an arbitrary length sequence. In the case of Fig. 2, the codewords are defined
for each source symbol pair, and thus usually, we cannot encode sequences of
odd lengths. However, the decoder can retrieve the source symbol sequentially
if we have properly-set leading and following codewords. So, if the odd-length
sequence ends with $b$, we can encode it into the leading codeword ‘1’ and one
of the following codewords, say ‘01’. For instance, $V(aaa)$ for the code in
Fig. 2 can be given by ‘000’, ‘00’ from $V(aa)$ and ‘0’ from
$\textrm{Lcword}_{V}(a)\textrm{Fcword}_{V}(a|a)$. $V(caabc)$ can be written as
‘100010100’, ‘100’ from $V(ca)$, ‘010’ from $V(ab)$, and ‘100’ from
$\textrm{Lcword}_{V}(c)\textrm{Fcword}_{V}(c|a)$. Of course, the decoder has
to know the exact length of the source symbol sequence if it wants to retrieve
exactly $caabc$ rather than $caabca$. However, at least the decoder never
mistakes the retrieval of the $caabc$ part. In this case, the codeword
$\textrm{Fcword}_{V}(c|a)$ is what we call the termination codeword in the
later discussion.

It should be noted that, in this paper, we do not focus on how to find the
leading and following codeword for a given code. Our purpose is only to show
that the decoding delay is a general idea for VV codes.

####  2.3.3 Example for VF code

Figure 3: Example of a VF code.  Table 2: Example of the leading and following codewords for the code in Fig. 3.  $s_{1}$ | $\textrm{Lcword}_{V}(s_{1})$ | $s_{2}$ | $\textrm{Fcword}_{V}(s_{1}|s_{2})$ |  | $s_{1}$ | $\textrm{Lcword}_{V}(s_{1})$ | $s_{2}$ | $\textrm{Fcword}_{V}(s_{1}|s_{2})$
---|---|---|---|---|---|---|---|---
$a$ | ‘$\lambda$’ | $aaa$ | ‘0’ |  | $aa$ | ‘0’ | $aa$ | ‘0’
$aab$ |  | $ab$
$ab$ |  | $b$ | ‘10’
$ba$ |  | $ab$ | ‘$\lambda$’ | $a$ | ‘011’
$bb$ | ‘100’ |  | $b$ | ‘100’
$b$ | ‘1’ | $aa$ | ‘01’ |  | $ba$ | ‘1’ | $a$ | ‘01’
$ab$ | ‘1’ |  | $b$ | ‘10’
$b$ |  | $bb$ | ‘111’ | $\epsilon$ | ‘$\lambda$’

Some may think that the above discussion supports only FV codes. However, it
can also be applied to Variable-to-Fixed-length (VF) codes. Fig. 3 shows an
example. In this case, the codewords corresponding to the sequences beginning
with $a$ are ‘000’, ‘001’, ‘010’, ‘011’, and ‘100’. Since there are codewords
starting with ‘0’ and with ‘1’, the encoder cannot determine any codeword by
only getting $a$, so the leading codeword for $a$ is
$\textrm{Lcword}_{V}(a)=$‘$\lambda$’. However, every codeword starting with
‘0’ corresponds to $a\cdots$, and so the decoder can retrieve $a$ from $0$. Of
course, it can also decode $a$ from ‘100’. Therefore, we can set ‘0’ and ‘100’
as the following codewords.

Similarly, we can set the leading and following codewords as in Table 2. Using
these codewords, we can define the codewords for any length of source
sequence: For instance, $V(baba)=$‘1100’, ‘110’ from $V(bab)$ and ‘0’ from
$\textrm{Lcword}_{V}(a)\textrm{Fcword}_{V}(a|aaa)$; $V(ababa)=$‘011101’, ‘011’
from $V(aba)$ and ‘101’ from
$\textrm{Lcword}_{V}(ba)\textrm{Fcword}_{V}(ba|a)$.

##  3 Proposed $N$-bit-delay AIFV codes

###  3.1 Basic structure

Based on the decoding delay defined in the previous section, we propose a
scheme of AIFV codes that can represent all codes we can decode within a given
amount of delay. To show the proposed scheme, we first introduce a term
“mode,” the core concept of the proposed codes. Modes play a critical role in
representing the rules of the code tree structure. As explained later, the
mode defined here is used as sets of allowed prefixes for a code tree and
works as a query for the decoder to determine which tree is used. However, we
want to clarify the whole class before discussing the consistency of the code.
Therefore, we define the mode simply as follows.

######  Definition 3 (Mode of a code tree)

An arbitrary member of $\mathbb{M}$ assigned to a code tree.

We redefine the code trees by assigning a mode Mode ($\in\mathbb{M}$) to each
one:

  * •

$\mathbb{T}_{M}=\\{(\textrm{Cword}_{k},\textrm{Point}_{k},\textsc{Mode}_{k},k)\mid\textrm{Cword}_{k}:\mathbb{A}_{M}\to\mathbb{W},\textrm{Point}_{k}:\mathbb{A}_{M}\to\mathbb{Z}^{+},\textsc{Mode}_{k}\in\mathbb{M},k\in\mathbb{Z}^{+}\\}$,
a set of all code trees for source symbols $\mathbb{A}_{M}$.

Here, $\textrm{Cword}_{k}(a)$ and $\textrm{Point}_{k}(a)$ are respectively the
codeword and the index of the next code tree corresponding to the source
symbol $a$. $k$ is the index of the code tree, and throughout this paper, we
indicate it by a subscript like in $T_{k}$.

A code-tree set $\\{T_{k}\\}$ is represented here as an element of a subset of
$\mathbb{T}_{M}$ whose code trees are all available for encoding and decoding
processes:

  * •

$\mathbb{RT}_{M}=\\{\\{T_{k}\mid
k\in\mathbb{Z}^{+}_{<K}\\}\subset\mathbb{T}_{M}\mid K\in\mathbb{N}$, $T_{k}$
is reachable from $T_{0}$ for $k\neq 0$, $T_{k}$ may not reach
$T_{k^{\prime}}$ of $k^{\prime}\notin\mathbb{Z}^{+}_{<K}\\}$, a set of all
reachable (and closed) code-tree sets.

The word “reachable” is used here similarly to the context of Markov chains
[19]: $T_{k}$ is reachable from $T_{0}$, or $T_{0}$ may reach $T_{k}$, when
the encoder can switch the code tree to $T_{k}$ from $T_{0}$ within finite
steps following the switching rules. Note that $\mathbb{T}_{M}$ and
$\mathbb{RT}_{M}$ only clarify the components of code trees and code-tree sets
without discussing their decodability.

As shown by an example in Fig. 4, each code tree determines, for every source
symbol, the codeword and the next code tree. The code-tree set can be
equivalently written in the form of a table as in Table 3 and is used for the
encoding and decoding procedures as follows.

######  Procedure 5 (Encoding a source symbol sequence into a proposed AIFV
codeword sequence)

Follow the steps below with the $L$-length source symbol sequence
$x_{0}x_{1}\cdots x_{L-1}$ ($\in\mathbb{S}_{M}$) and code-tree set
$\\{T_{k}\\}$ ($\in\mathbb{RT}_{M}$) being the inputs of the encoder.

  1. a.

Start encoding from $k=0$.

  2. b.

For $i=0,1,\cdots,L-1$, output the codeword $\textrm{Cword}_{k}(x_{i})$ in the
current code tree $T_{k}$ and switch the code tree by updating the index $k$
with $\textrm{Point}_{k}(x_{i})$.

  3. c.

Output some binary string in the mode $\textsc{Mode}_{k}$ (here, we call it
the termination codeword).

As proven later, the termination codeword can be an arbitrary member of
$\textsc{Mode}_{k}$. However, from a practical perspective, we use the one
having minimum length unless otherwise specified.

######  Procedure 6 (Decoding a source symbol sequence from a proposed AIFV
codeword sequence)

Follow the steps below with the codeword sequence, code-tree set
$\\{T_{k}\\}$, and output length $L$ being the inputs of the decoder.

  1. a.

Start decoding from $k=0$.

  2. b.

Compare the codeword sequence with the codewords in the current code tree
$T_{k}$. If the codeword $\textrm{Cword}_{k}(a)$ matches the codeword
sequence, and some codeword
$\textrm{Query}\in\textsc{Mode}_{\textrm{Point}_{k}(a)}$ matches the codeword
sequence after $\textrm{Cword}_{k}(a)$, output the source symbol $a$ and
continue the process from the codeword sequence right after
$\textrm{Cword}_{k}(a)$.

  3. c.

Switch the code tree by updating the index $k$ with $\textrm{Point}_{k}(a)$.

  4. d.

If the decoder has output less than $L$ symbols, return to b.

For example, think of encoding a source symbol sequence $abbaa$ using the code
trees in Fig. 4. The encoder starts with $T_{0}$ to encode $a$, outputting the
codeword ‘$\lambda$’. Then, it switches the code tree to $T_{1}$ to encode
$b$, outputting another ‘$\lambda$’ and switching the code tree to $T_{3}$.
$T_{3}$ gives the codeword ‘100’ for $b$ and switches the code tree to
$T_{0}$. Similarly, it respectively outputs codewords ‘$\lambda$’ and ‘1’
using $T_{0}$ and $T_{1}$ for $a$ and another $a$. For the code’s termination,
the encoder outputs the minimum-length binary string in the mode of $T_{4}$,
‘1’. As a result, the encoded codeword sequence becomes
‘$\lambda\lambda$100$\lambda$11’, namely ‘10011’.

The decoder starts the decoding from $T_{0}$, checking at first whether the
codeword ‘$\lambda$’ of $a$ matches the codeword sequence ‘10011’. The
codeword for $a$ is ‘$\lambda$’ and thus matches the sequence. Then, the
decoder checks whether any codeword in the mode of $T_{1}$, the code tree $a$
points, matches the sequence. Since ‘1’ is included, it outputs $a$ and
switches the code tree to $T_{1}$. The next symbol is decoded from the
codeword sequence following ‘$\lambda$’, i.e., ‘10011’. The codeword
‘$\lambda$’ for $b$ in $T_{1}$ matches the sequence, and the following ‘100’
is included in the mode of $T_{3}$. Therefore, $b$ is output, and the third
symbol is decoded from ‘10011’ by $T_{3}$. The codeword ‘100’ is for $b$ in
$T_{3}$, and ‘$\lambda$’ in the mode of $T_{0}$ obviously matches the
following sequence so that another $b$ is output, with the fourth symbol
decoded from ‘11’ by $T_{0}$. Similarly, the decoder outputs $a$ and decodes
the fifth symbol from ‘11’ by $T_{1}$. Although ‘11’ matches the codeword
‘$\lambda$’ of the symbol $b$ in $T_{1}$, no codeword in the mode of $T_{3}$
matches ‘11’. Thus, the decoder does not output $b$ and instead checks the
codeword for $a$. Since the codeword ‘1’ of $a$ matches the sequence and the
following ‘1’ is included in the mode of $T_{4}$, the decoder can determine
the last source symbol $a$ to output. As a result, we can get the correct
source symbol sequence $abbaa$.

The termination codewords in step c of the encoding are necessary when the
decoder only knows the total length $L$ of the source symbol sequence and
cannot know the end of the codeword sequence. We can easily understand their
role by thinking of encoding a single $a$ using the code trees in Fig. 4. The
code tree $T_{0}$ gives ‘$\lambda$’, and thus if there is no termination
codeword and the decoder does not know the end of the codeword sequence, it
starts to check the following irrelevant binary strings: When some binary
string unrelated to the AIFV codeword sequence begins with ‘000’ and follows
the encoded ‘$\lambda$’, even if the decoder knows it has to decode only one
source symbol, it checks the following ‘000’ and outputs $b$. If the encoder
outputs the termination codeword ‘1’ after ‘$\lambda$’, the decoder checks it,
outputs $a$ correctly, and stops the decoding process before reading the
following irrelevant binary strings.

The code defined by Fig. 4, gives the codewords ‘11’, ‘101’, ‘011’, ‘011’,
‘100’, ‘00’, and ‘010’ respectively for the source symbols sequences
$aaa\cdots$, $aab\cdots$, $aba\cdots$, $abb\cdots$, $ba\cdots$, and
$bb\cdots$. It is effective for sources where $a$ appears a little more
frequently than $b$, which the conventional AIFV codes cannot effectively
compress because it requires the difference of the code lengths of $a$ and $b$
to be 3 bits in some code tree to utilize the allowed 3-bit decoding delay.

Indeed, the table size increases by $|\\{T_{k}\\}|$ times compared to the
binary Huffman codes. However, the proposed AIFV codes can assign codewords
more flexibly to source symbol sequences with simple encoding/decoding
processes: The difference between Huffman coding in the encoding process is
only the symbol-wise switching of the code trees; the decoding process
requires only at most $M(=|\mathbb{A}_{M}|)$ times of additional check of
codewords in the modes. Of course, the computational complexity depends on how
to implement the processes. For example, if we implement the decoding process
as a finite-state automaton, it needs only one check for each source symbol.

Figure 4: An example of a code-tree set $\\{T_{k}\\}$ of the proposed code, with modes {‘$\lambda$’}, {‘1’, ‘011’}, {‘0’, ‘10’}, {‘011’, ‘100’}, and {‘1’, ‘01’} for the respective code trees.  Table 3: Table for the code in Fig. 4.  |  $T_{0}$: {‘$\lambda$’} |  $T_{1}$: {‘1’, ‘011’} |  $T_{2}$: {‘0’, ‘10’} |  $T_{3}$: {‘011’, ‘100’} |  $T_{4}$: {‘1’, ‘01’}
---|---|---|---|---|---
Source | Codeword | Next tree | Codeword | Next tree | Codeword | Next tree | Codeword | Next tree | Codeword | Next tree
$a$ |  ‘$\lambda$’ |  $T_{1}$ | ‘1’ | $T_{4}$ | ‘0’ | $T_{0}$ | ‘011’ | $T_{0}$ | ‘1’ | $T_{0}$
$b$ | ‘0’ |  $T_{2}$ |  ‘$\lambda$’ | $T_{3}$ | ‘10’ | $T_{0}$ | ‘100’ | $T_{0}$ | ‘01’ | $T_{0}$
Figure 5: Expanded trees representing the expanded codewords of $T_{0}$ and
$T_{1}$ in Fig. 4.

As is evident from the example, the proposed AIFV codes have no one-to-one
correspondence between the switching rules and the code tree structure: For
example, in $T_{0}$, the code tree switches to $T_{2}$ instead of $T_{0}$ when
encoding $b$ even though it is assigned to the leaf. This fact allows for much
more flexible code design than the conventional ones. The binary strings in
the modes work as queries suggesting which code tree the encoder switched. To
discuss the rule for the code tree construction, let us define the idea of
expanding codewords.

######  Definition 4 (Expanded codewords for $a$ of a code tree $T_{k}$)

$\textsc{Expand}_{k}(a)=\\{\textrm{Cword}_{k}(a)\textrm{Query}\mid\textrm{Query}\in\textsc{Mode}_{\textrm{Point}_{k}(a)}\\}$

######  Definition 5 (Expanded codeword set of a code tree $T_{k}$)

$\textsc{Expands}_{k}=\\{\textsc{Expand}_{k}(a)\mid a\in\mathbb{A}_{M}\\}$

For example, in Table 3, $T_{0}$ has codewords $\textrm{Cword}_{0}(a)=$
‘$\lambda$’ and $\textrm{Cword}_{0}(b)=$ ‘0’ with the corresponding modes
$\textsc{Mode}_{\textrm{Point}_{0}(a)}=\\{$‘1’, ‘011’$\\}$ and
$\textsc{Mode}_{\textrm{Point}_{0}(b)}=\\{$‘0’, ‘10’$\\}$. In this case, the
sets of expanded codewords of $T_{0}$ for $a$ and $b$ are
$\textsc{Expand}_{0}(a)=\\{$‘1’, ‘011’$\\}$ and
$\textsc{Expand}_{0}(b)=\\{$‘00’, ‘010’$\\}$, respectively.

The rule to make a code-tree set $\\{T_{k}\\}$ representing a uniquely-
decodable code is written as

######  Rule 3 (Constraints for the proposed AIFV codes to be uniquely
decodable)

  1. a.

$\forall k,\forall a\neq
a^{\prime}:\textsc{Expand}_{k}(a)\nparallel\textsc{Expand}_{k}(a^{\prime})$.

  2. b.

$\forall k,\forall\textrm{Expcw}\in\textsc{Expands}_{k}$,
$\exists\textrm{Query}\in\textsc{Mode}_{k}$:
$\textrm{Query}\preceq\textrm{Expcw}$.

Rule 3 a means that, for any code tree, the sets of expanded codewords are
prefix-free to each other. Rule 3 b requires, for any code tree, that every
expanded codeword has a prefix being a member of its mode. We can represent
the constraints in a code-tree-wise way as above by using the idea of expanded
codewords, constructed by the binary strings in the modes of the code trees
pointed. Fig. 5 shows an example of expanded trees that represent all the
expanded codewords of $T_{0}$ and $T_{1}$ in Fig. 4. It is clear that both of
them are prefix-free. The mode of $T_{0}$ is $\\{$‘$\lambda$’$\\}$, and thus
every expanded codeword of $T_{0}$ has a prefix in its mode. The expanded
codewords of $T_{1}$ are ‘011’, ‘100’, ‘101’, and ‘11’, having ‘1’ or ‘011’
($\in\textsc{Mode}_{1}$) as a prefix.

We use the following notation for the discussions below to represent the
constraints.

  * •

$\mathbb{DT}_{M}=\\{\\{T_{k}\\}\in\mathbb{RT}_{M}\mid\\{T_{k}\\}$ satisfies
Rule 3 $\\}$, a set of all reachable code-tree sets meeting Rule 3.

###  3.2 Decodability

Unique decodability is guaranteed for the encoding and decoding procedures
stated above:

######  Theorem 1 (Decodability of the proposed AIFV codes)

For any code-tree set $\\{T_{k}\\}\in\mathbb{DT}_{M}$, the codeword sequence
given by Procedure 5 using $\\{T_{k}\\}$ is uniquely decodable by Procedure 6
using $\\{T_{k}\\}$.

Proof: Suppose the encoding algorithm in Procedure 5 encodes an $L$-length
source symbol sequence $x_{0}x_{1}\cdots x_{L-1}(\in\mathbb{S}_{M})$ using
code trees $T_{k_{0}},T_{k_{1}},\cdots,T_{k_{L-1}}$, respectively. The encoded
codeword sequence becomes $w_{\rm
total}=\textrm{Cword}_{k_{0}}(x_{0})\textrm{Cword}_{k_{1}}(x_{1})\cdots\textrm{Cword}_{k_{L-1}}(x_{L-1})\textrm{Query}_{k_{L}}$.
Here, $\textrm{Query}_{k_{L}}$ is the termination codeword, a member of
$\textsc{Mode}_{k_{L}}$ where $k_{L}=\textrm{Point}_{k_{L-1}}(x_{L-1})$. We
claim Procedure 6 can retrieve $x_{0}x_{1}\cdots x_{L-1}$ from $w_{\rm total}$
when $\\{T_{k}\\}$ satisfies Rule 3. We will prove it inductively, showing the
decoding algorithm in the $i$-th iteration uses the code tree $T_{k_{i}}$ and
decodes $x_{i}$ correctly.

i) [Base case] Procedure 6 starts at $T_{0}=T_{k_{0}}$. Since
$k_{1}=\textrm{Point}_{k_{0}}(x_{0})$ and since $\\{T_{k}\\}$ satisfies Rule 3
b, there is a binary string $\textrm{Query}_{k_{1}}\in\textsc{Mode}_{k_{1}}$
being a prefix of
$\textrm{Cword}_{k_{1}}(x_{1})\cdots\textrm{Cword}_{k_{L-1}}(x_{L-1})\textrm{Query}_{k_{L}}$.
Thus, $\textrm{Cword}_{k_{0}}(x_{0})\textrm{Query}_{k_{1}}\preceq w_{\rm
total}$. Because of Rule 3 a, the expanded codeword
$\textrm{Cword}_{k_{0}}(x_{0})\textrm{Query}_{k_{1}}(\in\textsc{Expand}_{k_{0}}(x_{0}))$
is prefix-free among the expanded codewords in $\textsc{Expand}_{k_{0}}(a)$
for any other symbol $a\neq x_{0}$ of $T_{k_{0}}$. So the decoder can retrieve
$x_{0}$ uniquely from $\textrm{Cword}_{k_{0}}(x_{0})\textrm{Query}_{k_{1}}$,
switching the code tree to $T_{k_{1}}$.

ii) [Induction step] Suppose the decoder uses $T_{k_{i}}$ in the $i$-th
iteration. Since $k_{i+1}=\textrm{Point}_{k_{i}}(x_{i})$ and since
$\\{T_{k}\\}$ satisfies Rule 3 b, there is a binary string
$\textrm{Query}_{k_{i+1}}\in\textsc{Mode}_{k_{i+1}}$ which is a prefix of
$\textrm{Cword}_{k_{i+1}}(x_{i+1})\cdots\textrm{Cword}_{k_{L-1}}(x_{L-1})\textrm{Query}_{k_{L}}$.
Thus,
$\textrm{Cword}_{k_{i}}(x_{i})\textrm{Query}_{k_{i+1}}\preceq\textrm{Cword}_{k_{i}}(x_{i})\textrm{Cword}_{k_{i+1}}(x_{i+1})\cdots\textrm{Cword}_{k_{L-1}}(x_{L-1})\textrm{Query}_{k_{L}}$.
Because of Rule 3 a, the expanded codeword
$\textrm{Cword}_{k_{i}}(x_{i})\textrm{Query}_{k_{i+1}}(\in\textsc{Expand}_{k_{i}}(x_{i}))$
is prefix-free among the expanded codewords in $\textsc{Expand}_{k_{i}}(a)$
for any other symbol $a\neq x_{i}$ of $T_{k_{i}}$, and so the decoder can
retrieve $x_{i}$ uniquely from
$\textrm{Cword}_{k_{i}}(x_{i})\textrm{Query}_{k_{i+1}}$, switching the code
tree to $T_{k_{i+1}}$. $\qquad\blacksquare$

As we mentioned before, we can use any termination codeword as long as it is a
member of $\textsc{Mode}_{k}$. In fact, the minimum-length one should be used
to make the encoded codeword sequence as short as possible.

###  3.3 Decoding delay

We can determine the decoding delay of the proposed AIFV codes by checking
their modes:

######  Theorem 2 (Decoding delay of the proposed AIFV codes)

Decoding delay of the code given by Procedure 5 and Procedure 6 with
$\\{T_{k}\\}\in\mathbb{DT}_{M}$ is

$\max_{k}\left(\max\\{\|\textrm{Query}_{k}\|_{\rm
len}\mid\exists\textrm{Expcw}\in\textsc{Expands}_{k}:\textrm{Query}_{k}\preceq\textrm{Expcw},\textrm{Query}_{k}\in\textsc{Mode}_{k}\\}\right).$
(2)

Proof: As in the previous proof, suppose the encoding algorithm in Procedure 5
encodes an $L$-length source symbol sequence $x_{0}x_{1}\cdots
x_{L-1}(\in\mathbb{S}_{M})$ using code trees
$T_{k_{0}},T_{k_{1}},\cdots,T_{k_{L-1}}$, respectively. During Procedure 5,
the leading codeword when encoding $x_{0}x_{1}\cdots x_{i-1}$
($i\in\mathbb{Z}^{+}_{<L}$) corresponds to
$\textrm{Cword}_{k_{0}}(x_{0})\textrm{Cword}_{k_{1}}(x_{1})\cdots\textrm{Cword}_{k_{i-1}}(x_{i-1})$.
The following codeword needed for the decoder to determine $x_{0}x_{1}\cdots
x_{i-1}$ as its output is $\textrm{Query}_{k_{i}}$, which is a member of
$\textsc{Mode}_{k_{i}}$. Since
$\textrm{Query}_{k_{i}}\preceq\textrm{Cword}_{k_{i}}(x_{i})\textrm{Query}_{k_{i+1}}(\in\textsc{Expands}_{k_{i}})$
from Rule 3 b, even if some binary string is in $\textsc{Mode}_{k_{i}}$, it
would not be output in Procedure 5 as $\textrm{Query}_{k_{i}}$ unless it is a
prefix of some expanded codeword of $T_{k_{i}}$. Therefore, the decoding delay
of the code is given by the maximum length of the binary string in any mode
being the prefix of some expanded codeword. $\qquad\blacksquare$

The theorem reveals that the decoding delay heavily depends on the modes of
code trees. Note that when determining the decoding delay of the proposed AIFV
codes, we have to check whether the members of the modes are actually used as
the prefixes of the expanded codewords, as well as to check their lengths.
From now on, we define the proposed AIFV codes as follows.

######  Definition 6 ($N$-bit-delay AIFV code)

The code given by Procedure 5 using a code-tree set
$\\{T_{k}\\}\in\mathbb{DT}_{M}$ with modes having codewords of at most
$N$-bit-length.

It should be noted that $0$-bit-delay AIFV codes are identical to
instantaneous FV codes, including Huffman codes: They can be interpreted as
codes using code-tree sets of size 1 and $\\{$‘$\lambda$’$\\}$ for the mode.
The relationship between the conventional AIFV-$m$ and the proposed codes is
explained in the later section.

###  3.4 Generality

We claim that any VV code, decodable within a finite delay, can be constructed
as a set of code trees in the proposed scheme.

######  Theorem 3 (Generality of the proposed $N$-bit-delay AIFV codes)

For any uniquely encodable and uniquely decodable VV code
$V:\mathbb{S}_{M}\to\mathbb{W}$ which can be decoded with a decoding delay of
$N$ bits, there is an $N$-bit-delay AIFV code giving a codeword $V(s)$ for any
$s\in\mathbb{S}_{M}$.

Proof: We show here that we can rewrite $V(s)$ equivalently into a code-tree
set satisfying the constraints of $N$-bit-delay AIFV codes. From the
assumption, $V(s)$ is decodable with a decoding delay of $N$ bits, and thus we
can define the leading and following codewords $\textrm{Lcword}_{V}(s)$ and
$\textrm{Fcword}_{V}(s|\textrm{Tail})$ for any
$s,\textrm{Tail}\in\mathbb{S}_{M}$ satisfying Eq. (1) and
$\|\textrm{Fcword}_{V}(s|\textrm{Tail})\|_{\rm len}\leq N$.

Without loss of generality, we can set $\textrm{Lcword}_{V}(s)$ and
$\textrm{Fcword}_{V}(sa|\textrm{Tail})$ to satisfy the following.

$\textrm{Lcword}_{V}(s)\textrm{Fcword}_{V}(s|\epsilon)=V(s),$ (3) $\forall
a\in\mathbb{A}_{M}:\textrm{Lcword}_{V}(s)\preceq\textrm{Lcword}_{V}(sa),$ (4)
$\forall
a\in\mathbb{A}_{M}:\textrm{Lcword}_{V}(s)\textrm{Fcword}_{V}(s|a\textrm{Tail})\preceq\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(sa|\textrm{Tail}).$
(5)

[Reason for Eq. (3)] Setting
$\textrm{Fcword}_{V}(s|\epsilon)=\textrm{Lcword}_{V}(s)\oslash V(s)$ does not
conflict with the definition of the following codeword $\textrm{Fcword}_{V}$.

[Reason for Eqs. (4) and (5)] Let us think by dividing the conditions. We can
say from the definitions of $\textrm{Lcword}_{V}$ and $\textrm{Fcword}_{V}$
that $\textrm{Lcword}_{V}(s)\parallel\textrm{Lcword}_{V}(sa)$ and
$\textrm{Lcword}_{V}(s)\textrm{Fcword}_{V}(s|a\textrm{Tail})\parallel\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(sa|\textrm{Tail})$.

i) If $\textrm{Lcword}_{V}(sa)\prec\textrm{Lcword}_{V}(s)$ and
$\textrm{Lcword}_{V}(s)\textrm{Fcword}_{V}(s|a\textrm{Tail})\preceq\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(sa|\textrm{Tail})$,
we can reset $\textrm{Lcword}_{V}(sa)$ and
$\textrm{Fcword}_{V}(sa|\textrm{Tail})$ as

$\displaystyle\textrm{Lcword}_{V}(sa)$ $\displaystyle\equiv$
$\displaystyle\textrm{Lcword}_{V}(s)$ (6)
$\displaystyle\textrm{Fcword}_{V}(sa|\textrm{Tail})$ $\displaystyle\equiv$
$\displaystyle\textrm{Lcword}_{V}(s)\oslash(\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(s|a\textrm{Tail})).$
(7)

Eq. (6) obeys the definition of $\textrm{Lcword}_{V}(sa)$. This operation does
not change the codeword of
$\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(sa|\textrm{Tail})$, and thus Eq.
(1) still holds. Even if $\textrm{Tail}=\epsilon$,
$\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(sa|\epsilon)=V(sa)$ still holds,
too. Additionally, Eq. (7) shortens $\textrm{Fcword}_{V}(sa|\textrm{Tail})$ so
that $\|\textrm{Fcword}_{V}(sa|\textrm{Tail})\|_{\rm len}<N$.

ii) If $\textrm{Lcword}_{V}(s)\preceq\textrm{Lcword}_{V}(sa)$ and
$\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(sa|\textrm{Tail})\prec\textrm{Lcword}_{V}(s)\textrm{Fcword}_{V}(s|a\textrm{Tail})$,
we can reset $\textrm{Fcword}_{V}(s|a\textrm{Tail})$ as

$\textrm{Fcword}_{V}(sa|\textrm{Tail})\equiv\textrm{Lcword}_{V}(s)\oslash(\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(s|a\textrm{Tail})).$
(8)

This operation shortens $\textrm{Fcword}_{V}(sa|\textrm{Tail})$ and gives
$\textrm{Lcword}_{V}(s)\textrm{Fcword}_{V}(s|a\textrm{Tail})=\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(sa|\textrm{Tail})$.
Since we can retrieve $sa$ from
$\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(sa|\textrm{Tail})$, we can of
course retrieve $s$ from
$\textrm{Lcword}_{V}(s)\textrm{Fcword}_{V}(s|a\textrm{Tail})$, and so Eq. (1)
still holds.

iii) If $\textrm{Lcword}_{V}(sa)\prec\textrm{Lcword}_{V}(s)$ and
$\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(sa|\textrm{Tail})\prec\textrm{Lcword}_{V}(s)\textrm{Fcword}_{V}(s|a\textrm{Tail})$,
we can reset $\textrm{Lcword}_{V}(s)$ and
$\textrm{Fcword}_{V}(s|a\textrm{Tail})$ as

$\displaystyle\textrm{Lcword}_{V}(s)$ $\displaystyle\equiv$
$\displaystyle\textrm{Lcword}_{V}(sa)$ (9)
$\displaystyle\textrm{Fcword}_{V}(s|a\textrm{Tail})$ $\displaystyle\equiv$
$\displaystyle\textrm{Fcword}_{V}(sa|\textrm{Tail}).$ (10)

Eq. (9) only shortens $\textrm{Lcword}_{V}(s)$ so that it does not disturb the
definition of $\textrm{Lcword}_{V}(s)$. Eq. (10) does not make the length of
$\textrm{Fcword}_{V}(s|a\textrm{Tail})$ longer than $N$. Similarly to ii), Eq.
(1) still holds. Therefore, the conditions in Eqs. (4) and (5) do not disturb
the generality.

Using the above fact, we can equivalently represent the VV code by setting the
code trees as follows.

$T_{k_{s}}=(\textrm{Cword}_{k_{s}},\textrm{Point}_{k_{s}},\textsc{Mode}_{k_{s}},k_{s}),$
(11)

where

$\displaystyle\textrm{Cword}_{k_{s}}(a)$ $\displaystyle=$
$\displaystyle\textrm{Lcword}_{V}(s)\oslash\textrm{Lcword}_{V}(sa),$ (12)
$\displaystyle\textrm{Point}_{k_{s}}(a)$ $\displaystyle=$ $\displaystyle
k_{sa},$ (13) $\displaystyle\textsc{Mode}_{k_{s}}$ $\displaystyle=$
$\displaystyle\\{\textrm{Fcword}_{V}(s|\textrm{Tail})\mid\textrm{Tail}\in\mathbb{S}_{M}\\}\equiv\textsc{Follow}_{V}(s).$
(14)

$k_{s}$ is a non-negative integer defined for $s\in\mathbb{S}_{M}$ and being
$k_{s}\neq k_{s^{\prime}}$ for $s\neq s^{\prime}$. Especially,
$k_{\epsilon}=0$.

If we use $\textrm{Fcword}_{V}(s|\epsilon)$ ($\in\textsc{Follow}_{V}(s)$) when
encoding $s$, the codeword sequence for $s$ given by $\\{T_{k}\\}$ is
$\textrm{Lcword}_{V}(s)\textrm{Fcword}_{V}(s|\epsilon)$, which is $V(s)$
according to Eq. (3). Therefore, $\\{T_{k}\\}$ gives equivalent codewords as
$V$.

The expanded codewords of $T_{k_{s}}$ are

$\textsc{Expand}_{k_{s}}(a)=\\{\textrm{Lcword}_{V}(s)\oslash\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(sa|\textrm{Tail})\mid\textrm{Tail}\in\mathbb{S}_{M}\\}.$
(15)

From Eq. (1),

$\forall a^{\prime}\neq
a,\forall\textrm{Tail},\textrm{Tail}^{\prime}\in\mathbb{S}_{M}:\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(sa|\textrm{Tail})\nparallel\textrm{Lcword}_{V}(sa^{\prime})\textrm{Fcword}_{V}(sa^{\prime}|\textrm{Tail}^{\prime}),$
(16)

which becomes, by using Eq. (4),

$\displaystyle\forall a^{\prime}\neq
a,\forall\textrm{Tail},\textrm{Tail}^{\prime}\in\mathbb{S}_{M}:$
$\displaystyle\textrm{Lcword}_{V}(s)\oslash\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(sa|\textrm{Tail})$
$\displaystyle\nparallel$
$\displaystyle\textrm{Lcword}_{V}(s)\oslash\textrm{Lcword}_{V}(sa^{\prime})\textrm{Fcword}_{V}(sa^{\prime}|\textrm{Tail}^{\prime})$
$\displaystyle\iff\forall a^{\prime}\neq a,\textsc{Expand}_{k_{s}}(a)$
$\displaystyle\nparallel$ $\displaystyle\textsc{Expand}_{k_{s}}(a^{\prime}).$
(17)

Thus, $\\{T_{k}\\}$ satisfies Rule 3 a. On the other hand, from Eq. (5), we
have

$\forall
a\in\mathbb{A}_{M}:\textrm{Fcword}_{V}(s|a\textrm{Tail})\preceq\textrm{Lcword}_{V}(s)\oslash\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(sa|\textrm{Tail}),$
(18)

where $\textrm{Fcword}_{V}(s|a\textrm{Tail})\in\textsc{Follow}_{V}(s)$ and
$\textrm{Lcword}_{V}(s)\oslash\textrm{Lcword}_{V}(sa)\textrm{Fcword}_{V}(sa|\textrm{Tail})\in\textsc{Expand}_{k_{s}}(a)$
Therefore, Rule 3 b holds. Additionally, every codeword in the mode
$\textsc{Follow}_{V}(s)$ is used as a prefix of the expanded codeword in
$\textsc{Expand}_{k_{s}}(a)$. According to the assumption of decoding delay of
the VV code, every codeword in the mode $\textsc{Follow}_{V}(s)$ is not longer
than $N$ bits. So the code trees in Eq. (11) construct an $N$-bit-delay AIFV
code. $\qquad\blacksquare$

This theorem reveals that there exists an $N$-bit-delay AIFV code for any VV
code if we set an appropriate decoding delay $N$. The proof above also implies
that we can make the modes from the following codewords. Therefore, the modes
can be inferred from code-tree sets as ones of the conventional AIFV codes,
whose modes are not defined.

##  4 Properties of code-tree modes

###  4.1 Basic modes

Figure 6: Example of a reduced binary string set. A tree representing Words on
the left, circled nodes illustrating the members of $F_{\rm
full}(\textsc{Words})$ in the middle, and the tree of $F_{\rm
red}(\textsc{Words})$ on the right.

According to the definition of the mode, any binary string set can be a mode
of a code tree as long as Rule 3 is satisfied. However, many code trees are
meaningless: We can replace the codewords and modes to shorten the decoding
delay for any code trees without changing the encoding output. To discuss the
basic pattern of the modes, we introduce the following notation.

  * •

$\sim$: A dyadic relation defined for $\mathbb{DT}_{M}$.
$\\{T_{k}\\}\sim\\{T^{\prime}_{k}\\}$ indicates that for every source symbol
sequence, the codeword sequences given by respectively using $\\{T_{k}\\}$ and
$\\{T^{\prime}_{k}\\}$ become identical when their termination codewords are
truncated appropriately.

This relation groups code-tree sets neglecting the trivial difference due to
termination codewords. Say we encode $ab$ using $\\{T_{k}\\}$ as ‘0’ for $a$
by $T_{0}$, ‘$\lambda$’ for $b$ by $T_{1}$, and a termination codeword ‘100’
in $T_{2}$, which results in ‘0100’. If we have $\\{T^{\prime}_{k}\\}$ that
gives ‘0’ for $a$ by $T^{\prime}_{0}$, ‘1’ for $b$ by $T^{\prime}_{1}$, and a
termination codeword ‘0’ in $T^{\prime}_{2}$, which results in ‘010’, the
codewords for $ab$ can be identical by truncating the end of the termination
codeword ‘100’ in $T_{2}$. If we can always make the outputs identical by
truncating the end of the termination codeword, we write as
$\\{T_{k}\\}\sim\\{T^{\prime}_{k}\\}$.

The following functions are also introduced.

  * •

$f_{\rm cmn}$: $\mathbb{M}\to\mathbb{W}$. $f_{\rm cmn}(\textsc{Words})$
outputs the maximum-length common prefix of $\textsc{Words}\in\mathbb{M}$.

  * •

$F_{\rm full}$: $\mathbb{M}\to\mathbb{M}$. $F_{\rm
full}(\textsc{Words})=\\{\textrm{Prefix}\in\mathbb{W}\mid\forall\textrm{Suffix}\in\mathbb{W},\exists
w\in\textsc{Words}:\textrm{Prefix}\>\textrm{Suffix}\parallel w\\}$.

  * •

$F_{\rm red}$: $\mathbb{M}\to\mathbb{PF}$. $F_{\rm
red}(\textsc{Words})=\\{\hat{w}\in F_{\rm
full}(\textsc{Words})\mid\forall\textrm{Prefix}\in F_{\rm
full}(\textsc{Words}):\textrm{Prefix}\nprec\hat{w}\\}$.

It is easier to understand $F_{\rm full}(\textsc{Words})$ and $F_{\rm
red}(\textsc{Words})$ as operations on trees. For a tree given by
$\textsc{Words}\in\mathbb{M}$, $F_{\rm full}(\textsc{Words})$ finds the nodes
that have full trees below, and $F_{\rm red}(\textsc{Words})$ cuts off such
trees.

Fig. 6 provides an example. $F_{\rm full}(\textsc{Words})$ checks for every
string whether we can make it prefix-free from Words by adding some suffix: If
we make some string $\hat{w}=$ ‘0 Suffix’ by any
$\textrm{Suffix}\in\mathbb{W}$, there is always a string $w\in\textsc{Words}$
that is $\hat{w}\parallel w$, and thus ‘0’ $\in F_{\rm full}(\textsc{Words})$;
for ‘1’, we can make ‘111’ $\nparallel w(\in\textsc{Words})$, and thus ‘1’
$\notin F_{\rm full}(\textsc{Words})$. As a result, $F_{\rm
full}(\textsc{Words})$ contains the codewords corresponding to the circled
nodes shown in the middle of Fig. 6. $F_{\rm full}(\textsc{Words})$ also
contains the descendants of the leaves in Words. Then, $F_{\rm
red}(\textsc{Words})$ picks up only the nodes which have no prefix in $F_{\rm
full}(\textsc{Words})$, namely $\\{$‘0’, ‘10’, ‘110’$\\}$. Eventually, every
full subtree in Words gets reduced in the tree represented by $F_{\rm
red}(\textsc{Words})$.

Note that $F_{\rm red}(\textsc{Words})$ is defined for
$\textsc{Words}\in\mathbb{M}$, which includes binary string sets not
satisfying the prefix condition. When we interpret $F_{\rm
red}(\textsc{Words})$ as an operation of reducing trees, we do not have to
consider strings in Words which have a prefix included in Words. For example,
in Fig. 6, if we have also ‘$11$’ as a member of Words, the tree below
‘$\lambda$’ becomes a full tree. This is because ‘$11$’ added to Words is a
prefix of ‘$\lambda 111$’, and we cannot make any prefix-free binary string
starting with ‘$\lambda$’. Due to the definition of $F_{\rm
red}(\textsc{Words})$, the reduced binary string set is always prefix-free,
even if Words is not.

The functions $f_{\rm cmn}(\textsc{Words})$ and $F_{\rm red}(\textsc{Words})$
help us represent some essential features of the code-tree sets and modes:

######  Definition 7 (Full code-tree set)

A code-tree set where each code tree $T_{k}$ has a mode $\textsc{Mode}_{k}$
and an expanded codeword set $\textsc{Expand}_{k}(a)$ satisfying $F_{\rm
red}(\textsc{Mode}_{k})=F_{\rm red}(\textsc{Expands}_{k})$ and especially
$\textsc{Mode}_{0}=\\{$‘$\lambda$’$\\}$.

######  Definition 8 (Basic mode)

A mode $\\{f_{\rm
cmn}(\textsc{Words})\oslash\hat{\textrm{Query}}\mid\hat{\textrm{Query}}\in
F_{\rm red}(\textsc{Words})\\}$ using arbitrary $\textsc{Words}\in\mathbb{M}$.

Full code-tree sets are contained with code trees whose expanded codewords
cannot satisfy Rule 3 if any single string is added to them. Basic mode is a
class of modes having no common prefix except ‘$\lambda$’ and being invariable
by $F_{\rm red}$, which play an important role in defining representative
modes for code trees. Let us define a conversion using the basic modes:

######  Procedure 7 (Conversing a code-tree set into one with basic modes
only)

For a given code-tree set
$\\{T_{k}=(\textrm{Cword}_{k},\textrm{Point}_{k},\textsc{Mode}_{k},k)\\}$,
output

$\\{\tilde{T}_{k}=(\tilde{\textrm{Cword}}_{k},\textrm{Point}_{k},\tilde{\textsc{Mode}}_{k},k)\\},$
(19)

where

$\displaystyle\tilde{\textsc{Mode}}_{k}$ $\displaystyle=$
$\displaystyle\\{f_{\rm
cmn}(\textsc{Mode}_{k})\oslash\hat{\textrm{Query}}_{k}\mid\hat{\textrm{Query}}_{k}\in
F_{\rm red}(\textsc{Mode}_{k})\\}$ (20)
$\displaystyle\tilde{\textrm{Cword}}_{k}(a)$ $\displaystyle=$ $\displaystyle
f_{\rm cmn}(\textsc{Mode}_{k})\oslash\textrm{Cword}_{k}(a)f_{\rm
cmn}(\textsc{Mode}_{\textrm{Point}_{k}(a)}).$ (21)

The code-tree sets made by Procedure 7 show the following properties.

######  Theorem 4 (Equivalence)

$\\{\tilde{T}_{k}\\}$ given by $\\{T_{k}\\}\in\mathbb{DT}_{M}$ using Procedure
7 satisfies $\\{\tilde{T}_{k}\\}\sim\\{T_{k}\\}$ when
$\textsc{Mode}_{0}=\\{$‘$\lambda$’$\\}$.

######  Theorem 5 (Minimum delay)

When $\\{T_{k}\\}\in\mathbb{DT}_{M}$ is a full code-tree set, among every
$\\{T^{\prime}_{k}\\}\sim\\{T_{k}\\}$, $\\{\tilde{T}_{k}\\}$ given by
$\\{T_{k}\\}$ using Procedure 7 constructs a code with the shortest decoding
delay.

Fig. 7 gives an example. The code-tree set in (a) represents a code for
$\mathbb{A}_{3}$. Note that in $T_{0}$, we have both $a$ and $b$ assigned to
the root, and the decodability is guaranteed by using different code trees
after encoding $a$ and $b$. The code $V(s)$ represented by Fig. 7 (a) gives
$V(aa)=$‘000’, $V(ab)=$‘001’, $V(ac)=$‘010’, $V(ba)=$‘011’, $V(bb)=$‘100’,
$V(bc)=$‘101’, and $V(c)=$‘11’. $\\{T_{k}\\}$ follows Rule 3 b but there are
some useless binary strings in its modes: The common prefix ‘$0$’ in
$\textsc{Mode}_{1}$ can be moved to $T_{0}$ because the encoder at $T_{0}$ can
immediately determine as its output when encoding $a$; the decoder at $T_{0}$
needs only to read ‘00’, instead of ‘000’ or ‘001’ in $\textsc{Mode}_{1}$, to
determine $a$ as the output because any codeword starting with ‘00’
corresponds to symbol sequence starting with $a$; ‘10’, instead of ‘100’ or
‘101’ in $\textsc{Mode}_{2}$, is enough for the decoder at $T_{0}$ to
determine $b$ as the output.

Procedure 7 reduces such useless modes by using only the basic modes. Fig. 7
(b) describes the code-tree set given by converting $\\{T_{k}\\}$ of the above
example. The code $\tilde{V}(s)$ represented by Fig. 7 (b) outputs the same
codewords as $V(s)$ for $aa$, $ab$, $ac$, $ba$, $bb$, $bc$, and $c$. $V(s)$
and $\tilde{V}(s)$ differ only when we use non-zero-length termination
codewords. For example, $V(ca)=$‘11000’ comprises a codeword ‘$11\lambda$’ for
$ca$ and a termination codeword ‘$000$’ ($\in\textsc{Mode}_{1}$), and
$\tilde{V}(ca)=$‘1100’ comprises a codeword ‘$110$’ for $ca$ and a termination
codeword ‘$0$’ ($\in\tilde{\textsc{Mode}}_{1}$). The difference of the outputs
lies only in their ends, and we can make $V(ca)$ and $\tilde{V}(ca)$ identical
by truncating the termination codeword ‘$000$’. The binary strings in the
modes get shortened by the conversion with a trivial change in the output
codewords.

(a) Example of a code-tree set $\\{T_{k}\\}\in\mathbb{DT}_{3}$ with modes
$\\{$‘$\lambda$’$\\}$, $\\{$‘000’, ‘001’, ‘010’$\\}$, and $\\{$‘011’, ‘100’,
‘101’$\\}$.  (b) The code-tree set $\\{\tilde{T}_{k}\\}$ with the basic modes
$\\{$‘$\lambda$’$\\}$, $\\{$‘0’, ‘10’$\\}$, and $\\{$‘011’, ‘10’$\\}$.

Figure 7: Example of constructing a code-tree set
$\\{\tilde{T}_{k}\\}\sim\\{T_{k}\\}$ using only the basic modes.

We use the following lemma to prove the above theorems.

######  Lemma 1 (Properties of the reduced binary string set)

$F_{\rm red}(\textsc{Words})$ obeys the following properties for any
$\textsc{Words}\in\mathbb{M}$.

  1. a.

$\forall\hat{w}\in F_{\rm red}(\textsc{Words}),\exists
w\in\textsc{Words}:\hat{w}\preceq w$.

  2. b.

$\forall w\in\textsc{Words},\exists\hat{w}\in F_{\rm
red}(\textsc{Words}):\hat{w}\preceq w$.

  3. c.

$(\forall w\in\textsc{Words},\exists
w^{\prime}\in\textsc{Words}^{\prime}:w^{\prime}\preceq
w)\Longrightarrow(\forall\hat{w}\in F_{\rm
red}(\textsc{Words}),\exists\hat{w}^{\prime}\in F_{\rm
red}(\textsc{Words}^{\prime}):\hat{w}^{\prime}\preceq\hat{w})$.

  4. d.

$\forall\hat{w}\in F_{\rm red}(\textsc{Words}),\forall
w^{\prime}\in\mathbb{W}:(\hat{w}\parallel w^{\prime}\Longrightarrow(\exists
w\in\textsc{Words}:w^{\prime}\parallel w))$.

  5. e.

$\forall\textrm{Prefix}\in\mathbb{W}:F_{\rm red}(\\{\textrm{Prefix}\>w\mid
w\in\textsc{Words}\\})=\\{\textrm{Prefix}\>\hat{w}\mid\hat{w}\in F_{\rm
red}(\textsc{Words})\\}$.

  6. f.

$F_{\rm red}(F_{\rm red}(\textsc{Words}))=F_{\rm red}(\textsc{Words})$.

Propositions a and b show that $F_{\rm red}$ simply shortens the strings and
never extends or neglects them. It is guaranteed by c that $F_{\rm red}$
preserves the relationship of Words always being some prefix of
$\textsc{Words}^{\prime}$. Owing to d, we can check whether some string $w$ is
related to Words by checking the relation between $w$ and $F_{\rm
red}(\textsc{Words})$. Additionally, according to e and f, $F_{\rm red}$ also
preserves common prefixes and outputs irreducible binary string sets.

Proof of Lemma 1: The following can be said for any
$\textsc{Words}\in\mathbb{M}$.

a. $F_{\rm red}(\textsc{Words})\subseteq F_{\rm full}(\textsc{Words})$ from
the definition of $F_{\rm red}$. Assume there is some string $\hat{w}\in
F_{\rm red}(\textsc{Words})$ that is $\hat{w}\npreceq w$ for any
$w\in\textsc{Words}$. Combining the fact with the definition of $F_{\rm
full}$, we have $\forall\textrm{Suffix}\in\mathbb{W},\exists
w\in\textsc{Words}:w\prec\hat{w}\>\textrm{Suffix}$. However, since
$w\in\textsc{Words}\subseteq F_{\rm full}(\textsc{Words})$ is obvious from the
definition of $F_{\rm full}$, $w\prec\hat{w}$ conflicts with $\hat{w}\in
F_{\rm red}(\textsc{Words})$. Therefore, every $\hat{w}\in F_{\rm
red}(\textsc{Words})$ satisfies $\exists w\in\textsc{Words}:\hat{w}\preceq w$.

b. If we assume some $w\in\textsc{Words}$ that meets $\forall\hat{w}\in F_{\rm
red}(\textsc{Words}):\hat{w}\npreceq w$, it is naturally $w\notin F_{\rm
red}(\textsc{Words})$. Since $w\in\textsc{Words}\subseteq F_{\rm
full}(\textsc{Words})$ and $w\notin F_{\rm red}(\textsc{Words})$, we can
derive from the definition of $F_{\rm red}$ that there must be some
$\hat{w}\in F_{\rm red}(\textsc{Words})$ satisfying $\hat{w}\prec w$. However,
this conflicts with the assumption, and thus every $w\in\textsc{Words}$ meets
$\exists\hat{w}\in F_{\rm red}(\textsc{Words}):\hat{w}\preceq w$.

c. Assume $\hat{w}\in F_{\rm red}(\textsc{Words})$ satisfying
$\forall\hat{w}^{\prime}\in F_{\rm
red}(\textsc{Words}^{\prime}):\hat{w}^{\prime}\npreceq\hat{w}$ when $\forall
w\in\textsc{Words},\exists
w^{\prime}\in\textsc{Words}^{\prime}:w^{\prime}\preceq w$. The assumption
naturally gives $\forall\hat{w}^{\prime}\in F_{\rm
red}(\textsc{Words}^{\prime}):\hat{w}^{\prime}\nprec\hat{w}$ and
$\hat{w}\notin F_{\rm red}(\textsc{Words}^{\prime})$, which leads to
$\hat{w}\notin F_{\rm full}(\textsc{Words}^{\prime})$. Since $\hat{w}\in
F_{\rm red}(\textsc{Words})$, it meets
$\forall\textrm{Suffix}\in\mathbb{W},\exists
w\in\textsc{Words}:\hat{w}\>\textrm{Suffix}\parallel w$. However, combining it
with the assumption, we have $\forall\textrm{Suffix}\in\mathbb{W},\exists
w^{\prime}\in\textsc{Words}^{\prime}:\hat{w}\>\textrm{Suffix}\parallel
w^{\prime}$, which conflicts with $\hat{w}\notin F_{\rm
full}(\textsc{Words}^{\prime})$. Therefore, $\exists\hat{w}^{\prime}\in F_{\rm
red}(\textsc{Words}^{\prime}):\hat{w}^{\prime}\preceq\hat{w}$ must always
hold.

d. For any $\hat{w}\in F_{\rm red}(\textsc{Words})$ and
$w^{\prime}\in\mathbb{W}$, it is obvious from $\hat{w}\in F_{\rm
red}(\textsc{Words})$ that $\exists w\in\textsc{Words}:w^{\prime}\parallel w$
if $w^{\prime}\prec\hat{w}$. If $\hat{w}\preceq w^{\prime}$, we can make
$\hat{w}\>\textrm{Suffix}=w^{\prime}$ by some $\textrm{Suffix}\in\mathbb{W}$.
From the definition of $F_{\rm full}$, we have $\exists
w\in\textsc{Words}:\hat{w}\>\textrm{Suffix}\parallel w$, and thus there is
always some $w$ that satisfies $w^{\prime}\parallel w$.

e. For $\textrm{Prefix}\in\mathbb{W}$, let us write as
$\textsc{Words}^{\prime}\equiv\\{\textrm{Prefix}\>w\mid w\in\textsc{Words}\\}$
and
$\hat{\textsc{Words}}^{\prime}\equiv\\{\textrm{Prefix}\>\hat{w}\mid\hat{w}\in
F_{\rm red}(\textsc{Words})\\}$. If $\hat{w}\in F_{\rm red}(\textsc{Words})$,
it satisfies $\forall\textrm{Suffix}\in\mathbb{W},\exists
w\in\textsc{Words}:\hat{w}\>\textrm{Suffix}\parallel w$. Equivalently, it is
$\forall\textrm{Suffix}\in\mathbb{W},\exists\textrm{Prefix}\>w\in\textsc{Words}^{\prime}:\textrm{Prefix}\>\hat{w}\>\textrm{Suffix}\parallel\textrm{Prefix}\>w$.
Therefore, $\textrm{Prefix}\>\hat{w}\in F_{\rm red}(\textsc{Words}^{\prime})$,
namely $\hat{\textsc{Words}}^{\prime}\subseteq F_{\rm
red}(\textsc{Words}^{\prime})$.

On the other hand, if $\hat{w}^{\prime}\in F_{\rm
red}(\textsc{Words}^{\prime})$, we have

$\forall\textrm{Suffix}\in\mathbb{W},\exists\textrm{Prefix}\>w\in\textsc{Words}^{\prime}:\hat{w}^{\prime}\>\textrm{Suffix}\parallel\textrm{Prefix}\>w.$
(22)

It is $\textrm{Prefix}\preceq\hat{w}^{\prime}$ because if not, Eq. (22) gives
$\hat{w}^{\prime}\prec\textrm{Prefix}$ but becomes false for some Suffix
meeting $\textrm{Suffix}\nparallel\hat{w}^{\prime}\oslash\textrm{Prefix}$.
Consequently, it can be written as $\hat{w}^{\prime}=\textrm{Prefix}\>\hat{w}$
with some $\hat{w}\in\mathbb{W}$, and
$\forall\textrm{Suffix}\in\mathbb{W},\exists\textrm{Prefix}\>w\in\textsc{Words}^{\prime}:\textrm{Prefix}\>\hat{w}\>\textrm{Suffix}\parallel\textrm{Prefix}\>w$
holds, which gives $\forall\textrm{Suffix}\in\mathbb{W},\exists
w\in\textsc{Words}:\hat{w}\>\textrm{Suffix}\parallel w$, namely $\hat{w}\in
F_{\rm red}(\textsc{Words})$. So, we have $F_{\rm
red}(\textsc{Words}^{\prime})\subseteq\hat{\textsc{Words}}^{\prime}$, and thus
$F_{\rm red}(\textsc{Words}^{\prime})=\hat{\textsc{Words}}^{\prime}$.

f. If $\textrm{Prefix}\in F_{\rm full}(F_{\rm red}(\textsc{Words}))$, it meets
$\forall\textrm{Suffix}\in\mathbb{W},\exists\hat{w}\in F_{\rm
red}(\textsc{Words}):\textrm{Prefix}\>\textrm{Suffix}\parallel\hat{w}$. Using
proposition d, it becomes $\forall\textrm{Suffix}\in\mathbb{W},\exists
w\in\textsc{Words}:\textrm{Prefix}\>\textrm{Suffix}\parallel w$, and therefore
$F_{\rm full}(F_{\rm red}(\textsc{Words}))\subseteq F_{\rm
full}(\textsc{Words})$.

On the other hand, if $\textrm{Prefix}\in F_{\rm full}(\textsc{Words})$, it
meets $\forall\textrm{Suffix}\in\mathbb{W},\exists
w\in\textsc{Words}:\textrm{Prefix}\>\textrm{Suffix}\parallel w$. Combining it
with proposition b, we can get
$\forall\textrm{Suffix}\in\mathbb{W},\exists\hat{w}\in F_{\rm
red}(\textsc{Words}):\textrm{Prefix}\>\textrm{Suffix}\parallel\hat{w}$, and
$F_{\rm full}(\textsc{Words})\subseteq F_{\rm full}(F_{\rm
red}(\textsc{Words}))$. Therefore, $F_{\rm full}(\textsc{Words})=F_{\rm
full}(F_{\rm red}(\textsc{Words}))$. Accordingly,

$\displaystyle F_{\rm red}(F_{\rm red}(\textsc{Words}))$ $\displaystyle=$
$\displaystyle\\{\hat{w}\in F_{\rm
full}(\textsc{Words})\mid\forall\textrm{Prefix}\in F_{\rm
full}(\textsc{Words}):\textrm{Prefix}\nprec\hat{w}\\}$ (23) $\displaystyle=$
$\displaystyle F_{\rm red}(\textsc{Words}).\qquad\blacksquare$

Proof of Theorem 4: We prove the theorem by taking some steps revealing the
following.

  1. a.

It is always possible to make Eq. (19).

  2. b.

$\\{\tilde{T}_{k}\\}$ satisfies Rule 3 a.

  3. c.

$\\{\tilde{T}_{k}\\}$ satisfies Rule 3 b.

  4. d.

If $\textsc{Mode}_{0}=\\{$‘$\lambda$’$\\}$, we can make the codeword sequences
of $\\{T_{k}\\}$ and $\\{\tilde{T}_{k}\\}$ identical by truncating their
termination codewords.

a. To make Eq. (19), every string in $F_{\rm red}(\textsc{Mode}_{k})$ must
have a prefix $f_{\rm cmn}(\textsc{Mode}_{k})$, and every
$\textrm{Cword}_{k}(a)f_{\rm cmn}(\textsc{Mode}_{\textrm{Point}_{k}(a)})$ must
have a prefix $f_{\rm cmn}(\textsc{Mode}_{k})$. Due to Lemma 1 e, every string
in $F_{\rm red}(\textsc{Mode}_{k})$ has a prefix $f_{\rm
cmn}(\textsc{Mode}_{k})$.

On the other hand, from Rule 3 b for $\\{T_{k}\\}$,

$\exists\textrm{Query}_{k}\in\textsc{Mode}_{k}:f_{\rm
cmn}(\textsc{Mode}_{k})\preceq\textrm{Query}_{k}\preceq\textrm{Cword}_{k}(a)\textrm{Query}_{\textrm{Point}_{k}(a)}$
(24)

holds for any
$\textrm{Query}_{\textrm{Point}_{k}(a)}\in\textsc{Mode}_{\textrm{Point}_{k}(a)}$
and $a\in\mathbb{A}_{M}$. Eq. (24) implies that $f_{\rm
cmn}(\textsc{Mode}_{k})$ is a common prefix of
$\\{\textrm{Cword}_{k}(a)\textrm{Query}_{\textrm{Point}_{k}(a)}\mid\textrm{Query}_{\textrm{Point}_{k}(a)}\in\textsc{Mode}_{\textrm{Point}_{k}(a)}\\}$.
Since the maximum-length common prefix can be written as
$\textrm{Cword}_{k}(a)f_{\rm cmn}(\textrm{Query}_{\textrm{Point}_{k}(a)})$,
every $\textrm{Cword}_{k}(a)f_{\rm
cmn}(\textsc{Mode}_{\textrm{Point}_{k}(a)})$ has a prefix $f_{\rm
cmn}(\textsc{Mode}_{k})$. So, we can always make $\\{\tilde{T}_{k}\\}$ from
$\\{T_{k}\\}$.

b. The expanded codeword sets of the code trees in $\\{\tilde{T}_{k}\\}$ are
written as

$\displaystyle\tilde{\textsc{Expand}}_{k}(a)$ $\displaystyle\equiv$
$\displaystyle\\{\tilde{\textrm{Cword}}_{k}(a)\tilde{\textrm{Query}}_{\textrm{Point}_{k}(a)}\mid\tilde{\textrm{Query}}_{\textrm{Point}_{k}(a)}\in\tilde{\textsc{Mode}}_{\textrm{Point}_{k}(a)}\\}$
(25) $\displaystyle=$ $\displaystyle\\{f_{\rm
cmn}(\textsc{Mode}_{k})\oslash\textrm{Cword}_{k}(a)\hat{\textrm{Query}}_{\textrm{Point}_{k}(a)}\mid\hat{\textrm{Query}}_{\textrm{Point}_{k}(a)}\in
F_{\rm red}(\textsc{Mode}_{\textrm{Point}_{k}(a)})\\}.$

Lemma 1 d can be rewritten using the contraposition as

$\forall\hat{w}\in F_{\rm red}(\textsc{Words}),\forall
w^{\prime}\in\mathbb{W}:((\forall w\in\textsc{Words}:w^{\prime}\nparallel
w)\Longrightarrow\hat{w}\nparallel w^{\prime}).$ (26)

Substituting $\textsc{Words}=\textsc{Expand}_{k}(a)$ to Eq. (26) and combining
it with $\textsc{Expand}_{k}(a)\nparallel\textsc{Expand}_{k}(a^{\prime})$,
from Rule 3 a, gives $F_{\rm
red}(\textsc{Expand}_{k}(a))\nparallel\textsc{Expand}_{k}(a^{\prime})$.
Applying Eq. (26) again to it with
$\textsc{Words}=\textsc{Expand}_{k}(a^{\prime})$, we have

$F_{\rm red}(\textsc{Expand}_{k}(a))\nparallel F_{\rm
red}(\textsc{Expand}_{k}(a^{\prime}))$ (27)

for any $a\neq a^{\prime}$. Based on Lemma 1 e,

$\displaystyle F_{\rm red}(\textsc{Expand}_{k}(a))$ $\displaystyle=$
$\displaystyle F_{\rm
red}(\\{\textrm{Cword}_{k}(a)\textrm{Query}_{\textrm{Point}_{k}(a)}\mid\textrm{Query}_{\textrm{Point}_{k}(a)}\in\textsc{Mode}_{\textrm{Point}_{k}(a)}\\})$
(28) $\displaystyle=$
$\displaystyle\\{\textrm{Cword}_{k}(a)\hat{\textrm{Query}}_{\textrm{Point}_{k}(a)}\mid\hat{\textrm{Query}}_{\textrm{Point}_{k}(a)}\in
F_{\rm red}(\textsc{Mode}_{\textrm{Point}_{k}(a)})\\},$

and therefore

$\displaystyle\\{\textrm{Cword}_{k}(a)\hat{\textrm{Query}}_{\textrm{Point}_{k}(a)}\mid\hat{\textrm{Query}}_{\textrm{Point}_{k}(a)}\in
F_{\rm red}(\textsc{Mode}_{\textrm{Point}_{k}(a)})\\}$ (29)
$\displaystyle\nparallel$
$\displaystyle\\{\textrm{Cword}_{k}(a^{\prime})\hat{\textrm{Query}}_{\textrm{Point}_{k}(a^{\prime})}\mid\hat{\textrm{Query}}_{\textrm{Point}_{k}(a^{\prime})}\in
F_{\rm red}(\textsc{Mode}_{\textrm{Point}_{k}(a^{\prime})})\\}.$

Since $f_{\rm
cmn}(\textsc{Mode}_{k})\preceq\textrm{Cword}_{k}(a)\hat{\textrm{Query}}_{\textrm{Point}_{k}(a)}$
and $f_{\rm
cmn}(\textsc{Mode}_{k})\preceq\textrm{Cword}_{k}(a^{\prime})\hat{\textrm{Query}}_{\textrm{Point}_{k}(a^{\prime})}$
from Eq. (24), we can derive from Eq. (29) that

$\tilde{\textsc{Expand}}_{k}(a)\nparallel\tilde{\textsc{Expand}}_{k}(a^{\prime}).$
(30)

Therefore, $\\{\tilde{T}_{k}\\}$ obeys Rule 3 a.

c. From the definition of $\textsc{Expands}_{k}$, we can write Rule 3 b as

$\forall\textrm{Query}_{\textrm{Point}_{k}(a)}\in\textsc{Mode}_{\textrm{Point}_{k}(a)},\exists\textrm{Query}_{k}\in\textsc{Mode}_{k}:\textrm{Query}_{k}\preceq\textrm{Cword}_{k}(a)\textrm{Query}_{\textrm{Point}_{k}(a)}$
(31)

for all $a\in\mathbb{A}_{M}$. Using Lemma 1 c and e to Eq. (31), we get

$\forall\hat{\textrm{Query}}_{\textrm{Point}_{k}(a)}\in F_{\rm
red}(\textsc{Mode}_{\textrm{Point}_{k}(a)}),\exists\hat{\textrm{Query}}_{k}\in
F_{\rm
red}(\textsc{Mode}_{k}):\hat{\textrm{Query}}_{k}\preceq\textrm{Cword}_{k}(a)\hat{\textrm{Query}}_{\textrm{Point}_{k}(a)}$
(32)

for all $a$. Therefore,

$\forall\tilde{\textrm{Expcw}}\in\tilde{\textsc{Expand}}_{k}(a),\exists\tilde{\textrm{Query}}_{k}\in\tilde{\textsc{Mode}}_{k}:\tilde{\textrm{Query}}_{k}\preceq\tilde{\textrm{Expcw}}$
(33)

so that $\\{\tilde{T}_{k}\\}$ satisfies Rule 3 b as well.

d. For any source symbol sequence $x_{0}x_{1}\cdots x_{L-1}$, the encoder
using the code-tree set $\\{T_{k}\\}$ gives a codeword sequence as

$\displaystyle\textrm{Cword}_{k_{0}}(x_{0})\textrm{Cword}_{k_{1}}(x_{1})\cdots\textrm{Cword}_{k_{L-1}}(x_{L-1})\textrm{Query}_{k_{L}}$
(34) $\displaystyle=$
$\displaystyle\textrm{Cword}_{k_{0}}(x_{0})\textrm{Cword}_{k_{1}}(x_{1})\cdots\textrm{Cword}_{k_{L-1}}(x_{L-1})f_{\rm
cmn}(\textsc{Mode}_{k_{L}})(f_{\rm
cmn}(\textsc{Mode}_{k_{L}})\oslash\textrm{Query}_{k_{L}})$

where $k_{0}=0$ and $k_{i+1}=\textrm{Point}_{k_{i}}(x_{i})$
($i\in\mathbb{Z}^{+}_{<L+1}$) are the indexes of the code trees used for the
encoding, and $\textrm{Query}_{k_{L}}\in\textsc{Mode}_{k_{L}}$ is the
termination codeword. Meanwhile, when $f_{\rm
cmn}(\textsc{Mode}_{k_{0}})=$‘$\lambda$’, the codeword sequence given by using
$\\{\tilde{T_{k}}\\}$ is

$\displaystyle(f_{\rm
cmn}(\textsc{Mode}_{k_{0}})\oslash\textrm{Cword}_{k_{0}}(x_{0})f_{\rm
cmn}(\textsc{Mode}_{k_{1}}))(f_{\rm
cmn}(\textsc{Mode}_{k_{1}})\oslash\textrm{Cword}_{k_{1}}(x_{1})f_{\rm
cmn}(\textsc{Mode}_{k_{2}}))\cdots$ (35) $\displaystyle\>\>\>\>(f_{\rm
cmn}(\textsc{Mode}_{L-1})\oslash\textrm{Cword}_{k_{L-1}}(x_{L-1})f_{\rm
cmn}(\textsc{Mode}_{k_{L}}))(f_{\rm
cmn}(\textsc{Mode}_{k_{L}})\oslash\hat{\textrm{Query}}_{k_{L}})$
$\displaystyle=$
$\displaystyle\textrm{Cword}_{k_{0}}(x_{0})\textrm{Cword}_{k_{1}}(x_{1})\cdots\textrm{Cword}_{k_{L-1}}(x_{L-1})f_{\rm
cmn}(\textsc{Mode}_{k_{L}})(f_{\rm
cmn}(\textsc{Mode}_{k_{L}})\oslash\hat{\textrm{Query}}_{k_{L}})$

where $f_{\rm
cmn}(\textsc{Mode}_{k_{L}})\oslash\hat{\textrm{Query}}_{k_{L}}\in\tilde{\textsc{Mode}}_{k_{L}}$
is the termination codeword. We can make Eqs. (34) and (35) identical by
truncating their termination codewords.

It is $\\{\tilde{T}_{k}\\}\in\mathbb{DT}_{M}$ from steps b and c. Therefore,
step d leads to $\\{\tilde{T}_{k}\\}\sim\\{T_{k}\\}$. $\qquad\blacksquare$

Proof of Theorem 5: As the definition, we have $f_{\rm
cmn}(\textsc{Mode}_{0})=$‘$\lambda$’ when $\\{T_{k}\\}$ is a full code-tree
set. If any $f_{\rm cmn}(\textsc{Mode}_{k})$ is not ‘$\lambda$’, thinking
similarly to Eq. (35) in the proof of Theorem 4, we can obviously shorten the
decoding delay from $\\{T_{k}\\}$ by altering $\textsc{Mode}_{k}$ and
$\textrm{Cword}_{k}(a)$ respectively as $\\{f_{\rm
cmn}(\textsc{Mode}_{k})\oslash\textrm{Query}_{k}\mid\textrm{Query}_{k}\in\textsc{Mode}_{k}\\}$
and $f_{\rm cmn}(\textsc{Mode}_{k})\oslash\textrm{Cword}_{k}(a)f_{\rm
cmn}(\textsc{Mode}_{\textrm{Point}_{k}(a)})$. Therefore, without loss of
generality, we here only discuss the cases of

$\forall k:f_{\rm cmn}(\textsc{Mode}_{k})=\text{`$\lambda$'}.$ (36)

In such cases, we can rewrite $\\{\tilde{T}_{k}\\}$ as

$\\{\tilde{T}_{k}=(\textrm{Cword}_{k},\textrm{Point}_{k},\tilde{\textsc{Mode}}_{k},k)\\},$
(37)

where

$\tilde{\textsc{Mode}}_{k}=F_{\rm red}(\textsc{Mode}_{k}).$ (38)

The expanded codeword sets become

$\tilde{\textsc{Expand}}_{k}(a)=\\{\textrm{Cword}_{k}(a)\tilde{\textrm{Query}}_{\textrm{Point}_{k}(a)}\mid\tilde{\textrm{Query}}_{\textrm{Point}_{k}(a)}\in
F_{\rm red}(\textsc{Mode}_{\textrm{Point}_{k}(a)})\\},$ (39)

and say
$\tilde{\textsc{Expands}}_{k}\equiv\\{\tilde{\textsc{Expand}}_{k}(a)\mid
a\in\mathbb{A}_{M}\\}$.

Since $\\{T_{k}\\}$ is a full code-tree set, $F_{\rm
red}(\textsc{Mode}_{k})=F_{\rm red}(\textsc{Expands}_{k})$, which becomes

$\forall\textrm{Query}_{k}\in\textsc{Mode}_{k},\exists\hat{\textrm{Expcw}}\in
F_{\rm red}(\textsc{Expands}_{k})\text{:
}\textrm{Query}_{k}\preceq\hat{\textrm{Expcw}}$ (40)

using Lemma 1 b and

$\forall\textrm{Query}_{k}\in\textsc{Mode}_{k},\exists\textrm{Expcw}\in\textsc{Expands}_{k}\text{:
}\textrm{Query}_{k}\preceq\textrm{Expcw}$ (41)

using Lemma 1 a. It means that every binary string in the modes is a prefix of
some expanded codeword.

Let us write a codeword set $\\{T^{\prime}_{k}\\}$ ($\in\mathbb{DT}_{M}$,
$\sim\\{T_{k}\\}$) as

$\displaystyle\\{T^{\prime}_{k}=(\textrm{Cword}^{\prime}_{k},\textrm{Point}^{\prime}_{k},\textsc{Mode}^{\prime}_{k},k)\\}$
(42)

and its expanded codeword sets as

$\displaystyle\textsc{Expand}^{\prime}_{k}(a)$ $\displaystyle\equiv$
$\displaystyle\\{\textrm{Cword}^{\prime}_{k}(a)\textrm{Query}^{\prime}_{\textrm{Point}^{\prime}_{k}(a)}\mid\textrm{Query}^{\prime}_{\textrm{Point}^{\prime}_{k}(a)}\in\textsc{Mode}^{\prime}_{\textrm{Point}^{\prime}_{k}(a)}\\}$
(43) $\displaystyle\textsc{Expands}^{\prime}_{k}$ $\displaystyle\equiv$
$\displaystyle\\{\textsc{Expand}^{\prime}_{k}(a)\mid a\in\mathbb{A}_{M}\\}.$
(44)

Since $\\{T^{\prime}_{k}\\}\sim\\{T_{k}\\}$, it must be $f_{\rm
cmn}(\textsc{Mode}^{\prime}_{0})=$‘$\lambda$’. For the same reason above, we
can assume

$\forall k:f_{\rm cmn}(\textsc{Mode}^{\prime}_{k})=\text{`$\lambda$'}$ (45)

without loss of generality. Still without loss of generality, we can also
assume

$\forall\textrm{Query}^{\prime}_{k}\in\textsc{Mode}^{\prime}_{k},\exists\textrm{Expcw}^{\prime}\in\textsc{Expands}^{\prime}_{k}\text{:
}\textrm{Query}^{\prime}_{k}\preceq\textrm{Expcw}^{\prime}.$ (46)

This is because we can just omit $\textrm{Query}^{\prime}_{k}$ from
$\textsc{Mode}^{\prime}_{k}$, without affecting the decodability and decoding
delay, if it is not a prefix of any expanded codeword.

For any source symbol sequence $x_{0}x_{1}\cdots x_{L-1}$, the encoder using
the code-tree set $\\{T^{\prime}_{k}\\}$ gives a codeword sequence as

$\textrm{Cword}^{\prime}_{k^{\prime}_{0}}(x_{0})\textrm{Cword}^{\prime}_{k^{\prime}_{1}}(x_{1})\cdots\textrm{Cword}^{\prime}_{k^{\prime}_{L-1}}(x_{L-1})\textrm{Query}^{\prime}_{k^{\prime}_{L}}$
(47)

where $k^{\prime}_{0}=0$ and
$k^{\prime}_{i+1}=\textrm{Point}^{\prime}_{k^{\prime}_{i}}(x_{i})$
($i\in\mathbb{Z}^{+}_{<L+1}$) are the indexes of the code trees used for the
encoding, and
$\textrm{Query}^{\prime}_{k^{\prime}_{L}}\in\textsc{Mode}^{\prime}_{k^{\prime}_{L}}$
is the termination codeword.

We prove the theorem by taking some steps showing the following facts.

  1. a.

$\\{\tilde{T}_{k}\\}$ is a full code-tree set.

  2. b.

If there is some $k^{\prime}$ for each $k$ that meets
$\forall\tilde{\textrm{Query}}_{k}\in\tilde{\textsc{Mode}}_{k},\exists\textrm{Query}^{\prime}_{k^{\prime}}\in\textsc{Mode}^{\prime}_{k^{\prime}}:\|\tilde{\textrm{Query}}_{k}\|_{\rm
len}\leq\|\textrm{Query}^{\prime}_{k^{\prime}}\|_{\rm len}$, the decoding
delay using $\\{\tilde{T}_{k}\\}$ is not longer than the one using
$\\{T^{\prime}_{k}\\}$.

  3. c.

For any $x_{0}x_{1}\cdots x_{L-1}$ and $L$, there is some $w\in\mathbb{W}$
that makes
$\forall\tilde{\textrm{Query}}_{k_{i}}\in\tilde{\textsc{Mode}}_{k_{i}},\exists\textrm{Query}^{\prime}_{k^{\prime}_{i}}\in\textsc{Mode}^{\prime}_{k^{\prime}_{i}}:w\>\tilde{\textrm{Query}}_{k_{i}}\parallel\textrm{Query}^{\prime}_{k^{\prime}_{i}}$.

  4. d.

The condition in step c becomes
$w\>\tilde{\textrm{Query}}_{k_{i}}\preceq\textrm{Query}^{\prime}_{k^{\prime}_{i}}$
when $\\{\tilde{T}_{k}\\}$ is a full code-tree set.

a. Since $\\{T_{k}\\}$ is a full code-tree set, $F_{\rm
red}(\textsc{Mode}_{k})=F_{\rm red}(\textsc{Expands}_{k})$. Using Lemma 1 f,
we have

$F_{\rm red}(\tilde{\textsc{Mode}}_{k})=F_{\rm red}(F_{\rm
red}(\textsc{Mode}_{k}))=F_{\rm red}(\textsc{Mode}_{k})=F_{\rm
red}(\textsc{Expands}_{k}).$ (48)

When $\textrm{Prefix}\in F_{\rm full}(\tilde{\textsc{Expands}}_{k})$, it must
satisfy

$\displaystyle\forall\textrm{Suffix}\in\mathbb{W},\exists\tilde{\textrm{Expcw}}\in\tilde{\textsc{Expands}}_{k}:\textrm{Prefix}\>\textrm{Suffix}\parallel\tilde{\textsc{Expands}}_{k}$
(49) $\displaystyle\iff$
$\displaystyle\forall\textrm{Suffix}\in\mathbb{W},\exists(a\in\mathbb{A}_{M},\tilde{\textrm{Query}}_{\textrm{Point}_{k}(a)}\in
F_{\rm
red}(\textsc{Mode}_{\textrm{Point}_{k}(a)})):\textrm{Prefix}\>\textrm{Suffix}\parallel\textrm{Cword}_{k}(a)\tilde{\textrm{Query}}_{\textrm{Point}_{k}(a)}.$

From Lemma 1 d, Eq. (49) becomes

$\displaystyle\forall\textrm{Suffix}\in\mathbb{W},\exists(a\in\mathbb{A}_{M},\textrm{Query}_{\textrm{Point}_{k}(a)}\in\textsc{Mode}_{\textrm{Point}_{k}(a)}):\textrm{Prefix}\>\textrm{Suffix}\parallel\textrm{Cword}_{k}(a)\textrm{Query}_{\textrm{Point}_{k}(a)}$
(50) $\displaystyle\iff$
$\displaystyle\forall\textrm{Suffix}\in\mathbb{W},\exists\textrm{Expcw}\in\textsc{Expands}_{k}:\textrm{Prefix}\>\textrm{Suffix}\parallel\textsc{Expands}_{k},$

and thus $\textrm{Prefix}\in F_{\rm full}(\textsc{Expands}_{k})$, namely
$F_{\rm full}(\tilde{\textsc{Expands}}_{k})\subseteq F_{\rm
full}(\textsc{Expands}_{k})$.

Similarly, when $\textrm{Prefix}\in F_{\rm full}(\textsc{Expands}_{k})$, it
must satisfy

$\forall\textrm{Suffix}\in\mathbb{W},\exists(a\in\mathbb{A}_{M},\textrm{Query}_{\textrm{Point}_{k}(a)}\in\textsc{Mode}_{\textrm{Point}_{k}(a)}):\textrm{Prefix}\>\textrm{Suffix}\parallel\textrm{Cword}_{k}(a)\textrm{Query}_{\textrm{Point}_{k}(a)},$
(51)

which becomes

$\displaystyle\forall\textrm{Suffix}\in\mathbb{W},\exists(a\in\mathbb{A}_{M},\tilde{\textrm{Query}}_{\textrm{Point}_{k}(a)}\in
F_{\rm
red}(\textsc{Mode}_{\textrm{Point}_{k}(a)})):\textrm{Prefix}\>\textrm{Suffix}\parallel\textrm{Cword}_{k}(a)\tilde{\textrm{Query}}_{\textrm{Point}_{k}(a)}$
(52) $\displaystyle\iff$
$\displaystyle\forall\textrm{Suffix}\in\mathbb{W},\exists\tilde{\textrm{Expcw}}\in\tilde{\textsc{Expands}}_{k}:\textrm{Prefix}\>\textrm{Suffix}\parallel\tilde{\textsc{Expands}}_{k}$

according to Lemma 1 b. So, it is also $F_{\rm
full}(\textsc{Expands}_{k})\subseteq F_{\rm
full}(\tilde{\textsc{Expands}}_{k})$.

Based on the fact above, it is $F_{\rm full}(\textsc{Expands}_{k})=F_{\rm
full}(\tilde{\textsc{Expands}}_{k})$ and thus

$\displaystyle F_{\rm red}(\tilde{\textsc{Expands}}_{k})$ $\displaystyle=$
$\displaystyle\\{\hat{w}\in F_{\rm
full}(\textsc{Expands}_{k})\mid\forall\textrm{Prefix}\in F_{\rm
full}(\textsc{Expands}_{k}):\textrm{Prefix}\nprec\hat{w}\\}$ (53)
$\displaystyle=$ $\displaystyle F_{\rm red}(\textsc{Expands}_{k}).$

With Eq. (48), we have $F_{\rm red}(\tilde{\textsc{Mode}}_{k})=F_{\rm
red}(\tilde{\textsc{Expands}}_{k})$. Therefore, $\\{\tilde{T}_{k}\\}$ is also
a full code-tree set.

b. Assume there is some
$\tilde{\textrm{Query}}_{k}\in\tilde{\textsc{Mode}}_{k}$ that is
$\forall\tilde{\textrm{Expcw}}\in\tilde{\textsc{Expands}}_{k}\text{:
}\tilde{\textrm{Query}}_{k}\npreceq\tilde{\textrm{Expcw}}$. In this case, it
has to be either $\tilde{\textrm{Expcw}}\prec\tilde{\textrm{Query}}_{k}$ or
$\tilde{\textrm{Query}}_{k}\nparallel\tilde{\textrm{Expcw}}$. If
$\tilde{\textrm{Expcw}}\prec\tilde{\textrm{Query}}_{k}$, because of Eq. (33)
derived from Rule 3 b for $\\{\tilde{T}_{k}\\}$, there is some
$\tilde{\textrm{Query}}^{*}_{k}\in\tilde{\textsc{Mode}}_{k}$ satisfying
$\tilde{\textrm{Query}}^{*}_{k}\preceq\tilde{\textrm{Expcw}}$. It leads to
$\tilde{\textrm{Query}}^{*}_{k}\prec\tilde{\textrm{Query}}_{k}$, which
conflicts with $\tilde{\textsc{Mode}}_{k}\in\mathbb{PF}$.

Due to this fact, under the assumption above, it must be
$\forall\tilde{\textrm{Expcw}}\in\tilde{\textsc{Expands}}_{k}\text{:
}\tilde{\textrm{Query}}_{k}\nparallel\tilde{\textrm{Expcw}}$, namely
$\exists\tilde{\textrm{Query}}_{k}\in F_{\rm
red}(\textsc{Mode}_{k}),\forall(a\in\mathbb{A}_{M},\tilde{\textrm{Query}}_{\textrm{Point}_{k}(a)}\in
F_{\rm red}(\textsc{Mode}_{\textrm{Point}_{k}(a)})\text{:
}\tilde{\textrm{Query}}_{k}\nparallel\textrm{Cword}_{k}(a)\tilde{\textrm{Query}}_{\textrm{Point}_{k}(a)}$.
However, using Lemma 1 a, it becomes
$\exists\textrm{Query}_{k}\in\textsc{Mode}_{k},\forall(a\in\mathbb{A}_{M},\textrm{Query}_{\textrm{Point}_{k}(a)}\in\textsc{Mode}_{\textrm{Point}_{k}(a)})\text{:
}\textrm{Query}_{k}\nparallel\textrm{Cword}_{k}(a)\textrm{Query}_{\textrm{Point}_{k}(a)}$,
which conflicts with Eq. (41). Therefore,

$\forall\tilde{\textrm{Query}}_{k}\in\tilde{\textsc{Mode}}_{k},\exists\tilde{\textrm{Expcw}}\in\tilde{\textsc{Expands}}_{k}\text{:
}\tilde{\textrm{Query}}_{k}\preceq\tilde{\textrm{Expcw}}$ (54)

holds.

Owing to Eqs. (46) and (54), the values of the decoding delay given by Eq. (2)
respectively for $\\{\tilde{T}_{k}\\}$ and $\\{T^{\prime}_{k}\\}$ are

$\max_{k}\left(\max\\{\|\tilde{\textrm{Query}}_{k}\|_{\rm
len}\mid\tilde{\textrm{Query}}_{k}\in\tilde{\textsc{Mode}}_{k}\\}\right)$ (55)
$\max_{k^{\prime}}\left(\max\\{\|\textrm{Query}^{\prime}_{k^{\prime}}\|_{\rm
len}\mid\textrm{Query}^{\prime}_{k^{\prime}}\in\textsc{Mode}^{\prime}_{k^{\prime}}\\}\right).$
(56)

Thus, at least if there is some $k^{\prime}$ for each $k$ that meets
$\forall\tilde{\textrm{Query}}_{k}\in\tilde{\textsc{Mode}}_{k},\exists\textrm{Query}^{\prime}_{k^{\prime}}\in\textsc{Mode}^{\prime}_{k^{\prime}}:\|\tilde{\textrm{Query}}_{k}\|_{\rm
len}\leq\|\textrm{Query}^{\prime}_{k^{\prime}}\|_{\rm len}$, the decoding
delay using $\\{\tilde{T}_{k}\\}$ is not longer than the one using
$\\{T^{\prime}_{k}\\}$.

Figure 8: Example of the relationship represented by Eq. (57) between the
codeword sequences given respectively by $\\{T_{k}\\}$ and
$\\{T^{\prime}_{K}\\}$. $\\{T_{k}\\}\sim\\{T^{\prime}_{K}\\}$ requires both
codeword sequences to be identical except for the grayed-out area.

c. Since $\\{T^{\prime}_{k}\\}\sim\\{T_{k}\\}$, for any source symbol sequence
$x_{0}x_{1}\cdots x_{L-1}$, there must be some binary strings
$\textrm{Adjust}^{\prime}_{k_{i}}(x_{i})$ and
$\textrm{Adjust}_{k^{\prime}_{i}}(x_{i})$ ($\in\mathbb{W}$,
$i\in\mathbb{Z}^{+}_{<L}$) giving

$\left\\{\begin{array}[]{rcl}\textrm{Cword}^{\prime}_{0}(x_{0})\textrm{Adjust}^{\prime}_{0}(x_{0})&=&\textrm{Cword}_{0}(x_{0})\textrm{Adjust}_{0}(x_{0})\\\
\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash(\textrm{Cword}^{\prime}_{k^{\prime}_{i}}(x_{i})\textrm{Adjust}^{\prime}_{k_{i}}(x_{i}))&=&\textrm{Adjust}_{k^{\prime}_{i-1}}(x_{i-1})\oslash(\textrm{Cword}_{k_{i}}(x_{i})\textrm{Adjust}_{k^{\prime}_{i}}(x_{i}))\end{array}\right.,$
(57)

as illustrated in Fig. 8. If
$\textrm{Adjust}_{k^{\prime}_{i-1}}(x_{i-1})\neq\text{`$\lambda$'}$ ($i>0$)
exists, it means $\\{\textrm{Cword}_{k_{i}}(x_{i})\mid
x_{i}\in\mathbb{A}_{M}\\}$ has a common prefix of at least 1 bit. If so,
$f_{\rm cmn}(\textsc{Expands}_{k_{i}})\neq\text{`$\lambda$'}$, and from Lemma
1 e, $f_{\rm cmn}(F_{\rm
red}(\textsc{Expands}_{k_{i}}))\neq\text{`$\lambda$'}$. Since $\\{T_{k}\\}$ is
a full code-tree set, it must be $f_{\rm cmn}(F_{\rm
red}(\textsc{Mode}_{k_{i}}))=f_{\rm cmn}(F_{\rm
red}(\textsc{Expands}_{k_{i}}))\neq\text{`$\lambda$'}$, and therefore $f_{\rm
cmn}(\textsc{Mode}_{k_{i}})\neq\text{`$\lambda$'}$ from Lemma 1 e. This fact
conflicts with the assumption of Eq. (36), and thus
$\textrm{Adjust}_{k^{\prime}_{i-1}}(x_{i-1})$ must be ‘$\lambda$’, resulting
in

$\textrm{Cword}_{k_{i}}(x_{i})=\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash(\textrm{Cword}^{\prime}_{k^{\prime}_{i}}(x_{i})\textrm{Adjust}^{\prime}_{k_{i}}(x_{i})),$
(58)

which also holds for $i=0$ if we define
$\textrm{Adjust}_{k^{\prime}_{-1}}(x_{-1})\equiv$ ‘$\lambda$’.

On the other hand, recursively applying Rule 3 b for $\\{\tilde{T}_{k}\\}$
implies that there is
$\tilde{\textrm{Query}}_{k_{i}}\in\tilde{\textsc{Mode}}_{k_{i}}$ satisfying

$\tilde{\textrm{Query}}_{k_{i}}\preceq\tilde{\textrm{Cword}}_{k_{i}}(x_{i})\tilde{\textrm{Cword}}_{k_{i+1}}(x_{i+1})\cdots\tilde{\textrm{Cword}}_{k_{L-1}}(x_{L-1})\tilde{\textrm{Query}}_{k_{L}}$
(59)

where $\tilde{\textrm{Query}}_{k_{L}}\in\tilde{\textsc{Mode}}_{k_{L}}$. Due to
Eq. (58), this condition is equivalent to

$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\tilde{\textrm{Query}}_{k_{i}}\preceq\textrm{Cword}^{\prime}_{k^{\prime}_{i}}(x_{i})\textrm{Cword}^{\prime}_{k^{\prime}_{i+1}}(x_{i+1})\cdots\textrm{Cword}^{\prime}_{k^{\prime}_{L-1}}(x_{L-1})\textrm{Adjust}^{\prime}_{k_{L-1}}(x_{L-1})\tilde{\textrm{Query}}_{k_{L}}.$
(60)

Similarly, there is
$\textrm{Query}^{\prime}_{k^{\prime}_{i}}\in\textsc{Mode}^{\prime}_{k^{\prime}_{i}}$
satisfying

$\textrm{Query}^{\prime}_{k^{\prime}_{i}}\preceq\textrm{Cword}^{\prime}_{k^{\prime}_{i}}(x_{i})\textrm{Cword}^{\prime}_{k^{\prime}_{i+1}}(x_{i+1})\cdots\textrm{Cword}^{\prime}_{k^{\prime}_{L-1}}(x_{L-1})\textrm{Query}^{\prime}_{k^{\prime}_{L}},$
(61)

where
$\textrm{Query}^{\prime}_{k^{\prime}_{L}}\in\textsc{Mode}^{\prime}_{k^{\prime}_{L}}$.
If
$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\tilde{\textrm{Query}}_{k_{i}}\nparallel\textrm{Query}^{\prime}_{k^{\prime}_{i}}$
in this case, both
$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\tilde{\textrm{Query}}_{k_{i}}$
and $\textrm{Query}^{\prime}_{k^{\prime}_{i}}$ must have a common prefix
$\textrm{Cword}^{\prime}_{k^{\prime}_{i}}(x_{i})\textrm{Cword}^{\prime}_{k^{\prime}_{i+1}}(x_{i+1})\cdots\textrm{Cword}^{\prime}_{k^{\prime}_{L-1}}(x_{L-1})$.
However, it cannot hold for arbitrary $L$ because the decoding delay is
finite. Therefore, it is always
$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\tilde{\textrm{Query}}_{k_{i}}\parallel\textrm{Query}^{\prime}_{k^{\prime}_{i}}$.
As a result, we have

$\forall\tilde{\textrm{Query}}_{k_{i}}\in\tilde{\textsc{Mode}}_{k_{i}},\exists\textrm{Query}^{\prime}_{k^{\prime}_{i}}\in\textsc{Mode}^{\prime}_{k^{\prime}_{i}}:\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\tilde{\textrm{Query}}_{k_{i}}\parallel\textrm{Query}^{\prime}_{k^{\prime}_{i}}$
(62)

for any $i\in\mathbb{Z}^{+}$.

Figure 9: Outline of step d in the proof of Theorem 5.
$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})$ and
$\textrm{Adjust}^{\prime}_{k_{i}}(x_{i})$ are omitted here for simplicity.

d. We show by an inductive approach that it is actually
$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\tilde{\textrm{Query}}_{k_{i}}\preceq\textrm{Query}^{\prime}_{k^{\prime}_{i}}$
in Eq. (62). The outline of the proof is depicted in Fig. 9.

i) [Base case] Since $\\{\tilde{T}_{k}\\}$ is a full code-tree set,
$\tilde{\textsc{Mode}}_{k_{0}}=\\{$‘$\lambda$’$\\}$, and therefore it is
always
$\textrm{Adjust}^{\prime}_{k_{-1}}(x_{-1})\tilde{\textrm{Query}}_{k_{0}}=\tilde{\textrm{Query}}_{0}=$
‘$\lambda$’ $\preceq\textrm{Query}^{\prime}_{k_{0}}$.

ii) [Induction step] Think of the case where

$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\tilde{\textrm{Query}}_{k_{i}}\preceq\textrm{Query}^{\prime}_{k^{\prime}_{i}}$
(_Assumption 1_)

holds in Eq. (62) for arbitrary $x_{0}x_{1}\cdots x_{i-1}$. We prove the
statement also holds in the case of $x_{0}x_{1}\cdots x_{i}$ using a proof by
contradiction. Let us assume, for some $x_{0}x_{1}\cdots x_{i}$, and
$\tilde{\textrm{Query}}_{k_{i+1}}\in\tilde{\textsc{Mode}}_{k_{i+1}}$, that

$\forall\textrm{Query}^{\prime}_{k^{\prime}_{i+1}}\in\textsc{Mode}^{\prime}_{k^{\prime}_{i+1}}:\textrm{Adjust}^{\prime}_{k_{i}}(x_{i})\tilde{\textrm{Query}}_{k_{i+1}}\npreceq\textrm{Query}^{\prime}_{k^{\prime}_{i+1}}$
(_Assumption 2_)

Here, we use the notation

$l_{i+1}(a)=\textrm{Point}_{k_{i}}(a),\>\>l^{\prime}_{i+1}(a)=\textrm{Point}^{\prime}_{k^{\prime}_{i}}(a)$
(63)

for $a\in\mathbb{A}_{M}$. Naturally, $l_{i+1}(x_{i})=k_{i+1}$ and
$l^{\prime}_{i+1}(x_{i})=k^{\prime}_{i+1}$.

(_Substep 1_ in Fig. 9) We can write the expanded codeword of
$\tilde{T}_{k_{i}}$ for $x_{i}$ as

$\displaystyle\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})$ $\displaystyle\equiv$
$\displaystyle\textrm{Cword}_{k_{i}}(x_{i})\tilde{\textrm{Query}}_{k_{i+1}}$
(64) $\displaystyle=$
$\displaystyle\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash(\textrm{Cword}^{\prime}_{k^{\prime}_{i}}(x_{i})\textrm{Adjust}^{\prime}_{k_{i}}(x_{i})\tilde{\textrm{Query}}_{k_{i+1}})$

using $\tilde{\textrm{Query}}_{k_{i+1}}$ of _Assumption 2_. Due to the same
assumption and Eq. (62), any expanded codeword of
$T^{\prime}_{k^{\prime}_{i}}$ for $x_{i}$,

$\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(x_{i})\equiv\textrm{Cword}^{\prime}_{k^{\prime}_{i}}(x_{i})\textrm{Query}^{\prime}_{k^{\prime}_{i+1}},$
(65)

meets
$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(x_{i})\prec\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})$.

(_Substep 2_ in Fig. 9) Meanwhile, any expanded codeword of
$\tilde{T}_{k_{i}}$ for $a\neq x_{i}$ is written as

$\tilde{\textrm{Expcw}}_{k_{i}}(a)\equiv\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash(\textrm{Cword}^{\prime}_{k^{\prime}_{i}}(a)\textrm{Adjust}^{\prime}_{k_{i}}(a)\tilde{\textrm{Query}}_{l_{i+1}(a)})$
(66)

with
$\tilde{\textrm{Query}}_{l_{i+1}(a)}\in\tilde{\textsc{Mode}}_{l_{i+1}(a)}$.
According to Eq. (62), there is always some
$\textrm{Query}^{\prime}_{l^{\prime}_{i+1}(a)}\in\textsc{Mode}^{\prime}_{l^{\prime}_{i+1}(a)}$
satisfying
$\textrm{Adjust}^{\prime}_{k_{i}}(a)\tilde{\textrm{Query}}_{l_{i+1}(a)}\parallel\textrm{Query}^{\prime}_{l^{\prime}_{i+1}(a)}$.
Since we can write the expanded codeword of $\\{T^{\prime}_{k}\\}$ for $a\neq
x_{i}$ as

$\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(a)\equiv\textrm{Cword}^{\prime}_{k^{\prime}_{i}}(a)\textrm{Query}^{\prime}_{l^{\prime}_{i+1}(a)},$
(67)

we have

$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(a)\parallel\tilde{\textrm{Expcw}}_{k_{i}}(a).$
(68)

Following Rule 3 a for $T^{\prime}_{k^{\prime}_{i}}$, it must be

$\displaystyle\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(x_{i})$
$\displaystyle\nparallel$
$\displaystyle\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(a)$
$\displaystyle\iff\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(x_{i})$
$\displaystyle\nparallel$
$\displaystyle\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(a).$
(69)

Combining it with Eq. (68) gives

$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(x_{i})\npreceq\tilde{\textrm{Expcw}}_{k_{i}}(a),$
(70)

whose derivation uses the idea illustrated in Fig.10. Since
$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(x_{i})\prec\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})$
under _Assumption 2_ , it must be
$\tilde{\textrm{Expcw}}_{k_{i}}(a)\nprec\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(x_{i})$
to obey
$\tilde{\textrm{Expcw}}_{k_{i}}(a)\nparallel\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})$
from Rule 3 a for $\tilde{T}_{k_{i}}$. Therefore, it must be
$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(x_{i})\nparallel\tilde{\textrm{Expcw}}_{k_{i}}(a)$.

(_Substep 3_ in Fig. 9) According to the definition of $F_{\rm red}$ and
$F_{\rm full}$,
$\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})\in\tilde{\textsc{Expand}}_{k_{i}}(x_{i})=\\{\textrm{Cword}_{k_{i}}(x_{i})\tilde{\textrm{Query}}_{k_{i+1}}\mid\tilde{\textrm{Query}}_{k_{i+1}}\in
F_{\rm red}(\textsc{Mode}_{k_{i+1}})\\}$ implies that we can make from any
${\textrm{Prefix}}\prec\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})$, by using some
${\textrm{Suffix}}\in\mathbb{W}$, a binary string satisfying $\forall
w\in\tilde{\textsc{Expand}}_{k_{i}}(x_{i}):{\textrm{Prefix}}\>{\textrm{Suffix}}\nparallel
w$. Therefore, we can make such
${\textrm{Prefix}}\>{\textrm{Suffix}}\equiv{\textrm{Unused}}$ under the
condition of
$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(x_{i})\preceq{\textrm{Unused}}$,
awing to
$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(x_{i})\prec\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})$.
Because of
$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(x_{i})\nparallel\tilde{\textrm{Expcw}}_{k_{i}}(a)$,
it is also $\forall
w\in\tilde{\textsc{Expand}}_{k_{i}}(a):{\textrm{Unused}}\nparallel w$.
Eventually, under _Assumption 2_ , Unused satisfies $\forall
w\in\tilde{\textsc{Expands}}_{k_{i}}:\textrm{Unused}\nparallel w$.

(_Substep 4_ in Fig. 9) We can extend from any prefix of
$\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})$ to make Unused, which means $F_{\rm
full}(\tilde{\textsc{Expands}}_{k_{i}})$ does not include any prefix of
$\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})$. Meanwhile, we know
$\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})\in F_{\rm
full}(\tilde{\textsc{Expands}}_{k_{i}})$ from the definition of $F_{\rm
full}$. Therefore, $\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})\in F_{\rm
red}(\tilde{\textsc{Expands}}_{k_{i}})$. Since $\\{\tilde{T}_{k}\\}$ is a full
code-tree set, $\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})\in F_{\rm
red}(\tilde{\textsc{Mode}}_{k_{i}})=\tilde{\textsc{Mode}}_{k_{i}}$ also holds.

Combining
$\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})\in\tilde{\textsc{Mode}}_{k_{i}}$ with
_Assumption 1_ , there must be some string in
$\textsc{Mode}^{\prime}_{k^{\prime}_{i}}$ that has
$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})=\textrm{Cword}^{\prime}_{k^{\prime}_{i}}(x_{i})\textrm{Adjust}^{\prime}_{k_{i}}(x_{i})\tilde{\textrm{Query}}_{k_{i+1}}$
as its prefix. However, such string cannot be a prefix of any expanded
codeword in $\textsc{Expand}^{\prime}_{k^{\prime}_{i}}(x_{i})$ because of
_Assumption 2_. Moreover, from
$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\oslash\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(x_{i})\prec\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})$
and Eq. (69), it has to be
$\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\tilde{\textrm{Expcw}}_{k_{i}}(x_{i})\nparallel\textrm{Expcw}^{\prime}_{k^{\prime}_{i}}(a)$.
These facts suggest that $\textsc{Mode}^{\prime}_{k^{\prime}_{i+1}}$ must have
some string that cannot be a prefix of any expanded codeword in
$\textsc{Expands}^{\prime}_{k^{\prime}_{i}}$, which conflicts with Eq. (46).
Therefore,
$\textrm{Adjust}^{\prime}_{k_{i}}(x_{i})\tilde{\textrm{Query}}_{k_{i+1}}\preceq\textrm{Query}^{\prime}_{k^{\prime}_{i+1}}$
also holds.

As a result, we have

$\forall\tilde{\textrm{Query}}_{k_{i}}\in\tilde{\textsc{Mode}}_{k_{i}},\exists\textrm{Query}^{\prime}_{k^{\prime}_{i}}\in\textsc{Mode}^{\prime}_{k^{\prime}_{i}}:\textrm{Adjust}^{\prime}_{k_{i-1}}(x_{i-1})\tilde{\textrm{Query}}_{k_{i}}\preceq\textrm{Query}^{\prime}_{k^{\prime}_{i}},$
(71)

and therefore

$\forall\tilde{\textrm{Query}}_{k_{i}}\in\tilde{\textsc{Mode}}_{k_{i}},\exists\textrm{Query}^{\prime}_{k^{\prime}_{i}}\in\textsc{Mode}^{\prime}_{k^{\prime}_{i}}:\|\tilde{\textrm{Query}}_{k_{i}}\|_{\rm
len}\leq\|\textrm{Query}^{\prime}_{k^{\prime}_{i}}\|_{\rm len}$ (72)

for any $i\in\mathbb{Z}^{+}$. From the result of step b, the decoding delay of
a code using $\\{\tilde{T}_{k}\\}$ cannot be longer than the one using any
$\\{T^{\prime}_{k}\\}$. $\qquad\blacksquare$

Figure 10: Example of the relations between binary strings satisfying
$w\parallel\bar{w}$ and $\bar{w}\nparallel w^{\prime}$, which leads to
$w^{\prime}\npreceq w$.

###  4.2 Representation of modes by fixed-length strings

Owing to the above theorem, we can ignore useless codes, whose delay we can
shorten without changing the codewords. We need only to consider the basic
modes, which have no common prefix except ‘$\lambda$’ and are invariable by
$F_{\rm red}$. It should be noted that the basic mode corresponding to modes
with 1 bit always be $\\{$‘$\lambda$’$\\}$. For this reason, 1 bit of decoding
delay never contributes to the compression efficiency in binary codes, which
is consistent with the fact proven in the previous work [20].

For decoding delay longer than 1 bit, the basic modes can be represented
simpler using their constraints. To introduce such representation, we add a
notation:

  * •

$B_{N}$: The member of $\mathbb{M}$ including all the binary strings of length
$N$.

All of the basic modes can be written by this notation as follows.

######  Theorem 6 (Basic mode variation)

For an arbitrary $\textsc{Mode}\in\mathbb{M}$, suppose
$\tilde{\textsc{Mode}}=\\{f_{\rm
cmn}(\textsc{Mode})\oslash\hat{\textrm{Query}}\mid\hat{\textrm{Query}}\in
F_{\rm red}(\textsc{Mode})\\}$. If
$\forall\tilde{\textrm{Query}}\in\tilde{\textsc{Mode}}:\|\tilde{\textrm{Query}}\|_{\rm
len}\leq N$ ($N\geq 2$),

$\exists\textsc{Lb},\textsc{Ub}\subset B_{N-1}:F_{\rm
red}(\\{\text{`0'}\textrm{Lbin}\mid\textrm{Lbin}\in\textsc{Lb}\\}\cup\\{\text{`1'}\textrm{Ubin}\mid\textrm{Ubin}\in\textsc{Ub}\\})=\tilde{\textsc{Mode}}.$
(73)

Proof: It is obvious from the definition that, for any $n\in\mathbb{N}$,
$\textsc{Words}\in\mathbb{M}$ and $w\in\textsc{Words}$,

$F_{\rm red}((\textsc{Words}\setminus\\{w\\})\cup\\{wb\mid b\in
B_{n}\\}\\})=F_{\rm red}(\textsc{Words}).$ (74)

Using Lemma 1 e and f, $F_{\rm
red}(\tilde{\textsc{Mode}})=\tilde{\textsc{Mode}}$. Therefore,
$\tilde{\textsc{Mode}}$ can be rewritten as

$\tilde{\textsc{Mode}}=F_{\rm red}(\tilde{\textsc{Mode}})=F_{\rm
red}(\\{\tilde{\textrm{Query}}b_{N-\|\tilde{\textrm{Query}}\|_{\rm len}}\mid
b_{N-\|\tilde{\textrm{Query}}\|_{\rm len}}\in
B_{N-\|\tilde{\textrm{Query}}\|_{\rm
len}},\tilde{\textrm{Query}}\in\tilde{\textsc{Mode}}\\}),$ (75)

and every binary string in the set
$\\{\tilde{\textrm{Query}}b_{N-\|\tilde{\textrm{Query}}\|_{\rm len}}\\}$ is
$N$-length.

Additionally, $f_{\rm cmn}(\tilde{\textsc{Mode}})=f_{\rm
cmn}(\textsc{Mode})\oslash f_{\rm cmn}(\textsc{Mode})=\text{`$\lambda$'}$ due
to Lemma 1 e. Thus, $\tilde{\textsc{Mode}}$ must contain some strings
respectively starting with ‘0’ and ‘1’. $\qquad\blacksquare$

Owing to the above theorem, we only have to consider the combination of
$N$-bit strings when setting the modes for $N$-bit-delay AIFV codes. For
example, $2$-bit-delay AIFV codes have nine patterns of basic modes, which
have no common prefix except ‘$\lambda$’ and are invariable by $F_{\rm red}$:
$\\{$‘$\lambda$’$\\}$, $\\{$‘0’, ‘10’$\\}$, $\\{$‘0’, ‘11’$\\}$, $\\{$‘00’,
‘1’$\\}$, $\\{$‘00’, ‘10’$\\}$, $\\{$‘00’, ‘11’$\\}$, $\\{$‘01’, ‘1’$\\}$,
$\\{$‘01’, ‘10’$\\}$, and $\\{$‘01’, ‘11’$\\}$. They can be rewritten as some
sets of 2-bit binary strings by altering as ‘$\lambda$’ $\to$ $\\{$‘00’, ‘01’,
‘10’, ‘11’$\\}$, ‘0’ $\to$ $\\{$‘00’, ‘01’$\\}$ and ‘1’ $\to$ $\\{$‘10’,
‘11’$\\}$. The rewritten basic modes always include 2-bit binary strings
beginning with ‘0’ and ones with ‘1’. Therefore, they can be represented as a
pair of 1-bit binary string sets Lb and Ub: When
$\tilde{\textsc{Mode}}=\\{$‘$\lambda$’$\\}$, $\textsc{Lb}=\textsc{Ub}=\\{$‘0’,
‘1’$\\}$; when $\tilde{\textsc{Mode}}=\\{$‘0’, ‘10’$\\}$,
$\textsc{Lb}=\\{$‘0’, ‘1’$\\}$ and $\textsc{Ub}=\\{$‘0’$\\}$.

###  4.3 Representation of decodable condition by intervals

Figure 11: Correspondence of nodes and probability intervals of the expanded
$T_{0}$ in Fig. 5.

Since every basic mode is a member of $\mathbb{PF}$, Rule 3 a can be
equivalently written in a simpler way when the code trees contain only the
basic modes:

######  Rule 4 (Equivalent Rule 3 a for $\\{T_{k}\\}$ with the basic modes)

  1. a.

$\forall k:\textsc{Expands}_{k}\in\mathbb{PF}$.

In other words, we must keep the expanded codeword sets to satisfy the prefix
condition if we want to design the proposed AIFV codes. It is well-known that
Kraft’s inequality allows us to check whether there are some codes satisfying
the prefix condition. However, we cannot know from the inequality the expanded
codeword set is following Rule 3. We here show one way to tackle this problem
by mapping the codewords to intervals among the real number line, which is a
similar approach to the range coding [2]. Let us use notations and functions
as below.

  * •

$\bm{[}{x_{l},x_{u}}\bm{)}$: $\\{x\in\mathbb{R}\mid x_{l}\leq x<x_{u}\\}$, an
interval between $x_{l}$ and $x_{u}$ ($\in\mathbb{R}$).

  * •

$\mathbb{PI}$: $\\{R\subset\bm{[}{0,1}\bm{)}\\}$, a set of all probability
intervals, intervals included between $0$ and $1$.

  * •

$f_{\rm dec}$: $\mathbb{W}\to\bm{[}{0,1}\bm{)}$. $f_{\rm
dec}($‘$y_{0}y_{1}\cdots
y_{L-1}$’$)=\sum_{i\in\mathbb{Z}^{+}_{<L}}y_{i}/2^{i+1}$ for
$y_{i}\in\\{0,1\\}$.

  * •

$F_{\rm prob}$: $\mathbb{W}\to\mathbb{PI}$. $F_{\rm prob}(w)=\bm{[}{f_{\rm
dec}(w),f_{\rm dec}(w)+1/2^{\|w\|_{\rm len}}}\bm{)}$.

Since

$F_{\rm prob}(\text{`$y_{0}y_{1}\cdots y_{L-1}$'})=\bm{\biggl{[}}{f_{\rm
dec}(\text{`$y_{0}y_{1}\cdots y_{L-1}$'}),\>\>f_{\rm
dec}(\text{`$y_{0}y_{1}\cdots y_{L-1}$'})+\frac{1}{2^{L}}}\bm{\biggr{)}},$
(76)

the boundaries of the interval given by $F_{\rm prob}($‘$y_{0}y_{1}\cdots
y_{L-1}$’$)$ can be written in binary numbers as $0.y_{0}y_{1}\cdots
y_{L-1}00\cdots$ and $0.y_{0}y_{1}\cdots y_{L-1}11\cdots$. Therefore, for
$w_{1},w_{2}\in\mathbb{W}$, $F_{\rm prob}(w_{1})\cap F_{\rm prob}(w_{2})$ is
not empty if and only if $w_{1}\parallel w_{2}$, and we get an alternative
condition for checking Rule 3 a (Rule 4):

$\forall\textsc{Expands}\in\mathbb{M}:\textsc{Expands}\in\mathbb{PF}\iff\bigcup_{w_{1},w_{2}\in\textsc{Expands},w_{1}\neq
w_{2}}(F_{\rm prob}(w_{1})\cap F_{\rm prob}(w_{2}))=\emptyset.$ (77)

Fig. 11 depicts an example of the tree representing the expanded codewords of
$T_{0}$ in Fig. 5. The modes of the next code trees corresponding to $a$ and
$b$ are respectively $F_{\rm red}(\\{$‘011’, ‘100’, ‘101’, ‘110’, ‘111’$\\})$
and $F_{\rm red}(\\{$‘000’, ‘001’, ‘010’, ‘011’, ‘100’, ‘101’$\\})$, and the
probability intervals of the expanded codewords $\bm{[}{0,0.25}\bm{)}$,
$\bm{[}{0.25,0.375}\bm{)}$, $\bm{[}{0.375,0.5}\bm{)}$, and
$\bm{[}{0.5,1}\bm{)}$ do not overlap with each other.

It is also obvious that for $w_{1},w_{2}\in\mathbb{W}$, $F_{\rm
prob}(w_{1})\subseteq F_{\rm prob}(w_{2})$ if and only if $w_{2}\preceq
w_{1}$, and

$\displaystyle\forall(\textsc{Mode}\in\mathbb{PF},\textsc{Expands}\in\mathbb{M},\textrm{Expcw}\in\textsc{Expands}):$
$\displaystyle(\exists\textrm{Query}\in\textsc{Mode}:\textrm{Query}\preceq\textrm{Expcw})$
$\displaystyle\iff$ $\displaystyle F_{\rm
prob}(\textrm{Expcw})\subseteq\bigcup_{\textrm{Query}\in\textsc{Mode}}F_{\rm
prob}(\textrm{Query}).$ (78)

This condition can be used to check Rule 3 b. Especially in the case of a full
code-tree set, the right-hand side of Eq. (78) will be equal.

Owing to Eqs. (77) and (78), we can check the decodability only by placing the
intervals on the real number line. This property is expected to be useful in
constructing the proposed codes.

##  5 Further discussions

###  5.1 Relationship with conventional codes

(a) Optimal AIFV-$3$ code introduced in [21].  (b) Proposed 3-bit-delay AIFV
code.

Figure 12: Example of codes for $\mathbb{A}_{4}$ distributed as $p_{\rm
src}(a)=0.9$, $p_{\rm src}(b)=0.05$, $p_{\rm src}(c)=0.049$, and $p_{\rm
src}(d)=0.001$. The proposed 3-bit-delay AIFV code achieves a shorter expected
code length than the AIFV-$3$ one.

The conventional AIFV-$m$ codes can be interpreted, when $m=N$, as $N$-bit-
delay AIFV codes with their code trees $\\{T_{k}\\}\in\mathbb{DT}_{M}$ limited
to

$\bigcup_{\textrm{Query}_{k}\in\textsc{Mode}_{k}}F_{\rm
prob}(\textrm{Query}_{k})=\bm{\biggl{[}}{0,1}\bm{\biggr{)}}\>\>\text{or}\>\>\bm{\biggl{[}}{2^{-(N-n+1)},1}\bm{\biggr{)}},$
(79)

with $n=1,2,\cdots,N-1$. Fig. 12 shows an example of the difference between
the conventional AIFV-$m$ and proposed $N$-bit-delay AIFV codes. The AIFV-$3$
code is the one introduced in the previous work [21] as optimal for
$\mathbb{A}_{4}$ whose probabilities are $p_{\rm src}(a)=0.9$, $p_{\rm
src}(b)=0.05$, $p_{\rm src}(c)=0.049$, and $p_{\rm src}(d)=0.001$. We can see
that Fig. 12 (a) satisfies Rule 2 for AIFV-$m$ codes, which is equivalent to
using only the modes $F_{\rm red}(\\{$‘000’, ‘001’, ‘010’, ‘011’, ‘100’,
‘101’, ‘110’, ‘111’$\\})$, $F_{\rm red}(\\{$‘001’, ‘010’, ‘011’, ‘100’, ‘101’,
‘110’, ‘111’$\\})$, and $F_{\rm red}(\\{$‘010’, ‘011’, ‘100’, ‘101’, ‘110’,
‘111’$\\})$. The expected code length of the AIFV-3 code is

$\displaystyle(0\times p_{\rm src}(a)+4\times p_{\rm src}(b)+4\times p_{\rm
src}(c)+7\times p_{\rm src}(d))\times\Pi_{0}$ (80) $\displaystyle+$
$\displaystyle(0\times p_{\rm src}(a)+4\times p_{\rm src}(b)+4\times p_{\rm
src}(c)+7\times p_{\rm src}(d))\times\Pi_{1}$ $\displaystyle+$
$\displaystyle(1\times p_{\rm src}(a)+3\times p_{\rm src}(b)+3\times p_{\rm
src}(c)+6\times p_{\rm src}(d))\times\Pi_{2}=0.655\cdots$

where the stationary probability $\Pi_{k}$ for $T_{k}$ is given by

$(\Pi_{0},\Pi_{1},\Pi_{2})=(\Pi_{0},\Pi_{1},\Pi_{2})\left(\begin{array}[]{ccc}p_{\rm
src}(b)+p_{\rm src}(d)&p_{\rm src}(a)+p_{\rm src}(c)&0\\\ p_{\rm
src}(b)+p_{\rm src}(d)&p_{\rm src}(c)&p_{\rm src}(a)\\\ p_{\rm src}(a)+p_{\rm
src}(b)+p_{\rm src}(d)&p_{\rm src}(c)&0\end{array}\right).$ (81)

The expected code length of the $N$-bit-delay AIFV code is similarly
calculated as $0.604\cdots$. It is much closer to the entropy $0.576\cdots$
than AIFV-3 code. Although the proposed code uses more code trees, it still
keeps the decoding delay within 3 bits and makes more use of the allowed
delay.

As stated above, the conventional AIFV-$m$ codes always use modes whose
intervals are continuous. This is also true for arithmetic coding if we
interpret it as AIFV codes using code-tree sets. The relationship between
arithmetic coding and AIFV codes has been reported in previous works [22, 23].
Arithmetic coding is identical to the one of the proposed codes when
$N\to\infty$, using infinite code trees with the intervals of their modes
constrained to be continuous.

Some class of AIFV codes reported [24, 25] uses modes whose intervals can be
discontinuous. It is a subclass of the proposed codes which limits the code
trees to two using every available mode.

###  5.2 Open questions

One of the essential questions remaining is the theoretical worst-case
redundancy of the proposed codes. From a very conservative perspective, it is
lower than or equal to the redundancy stated in the previous work [13].
However, the results are based on the condition where the number of code trees
is identical to the decoding delay, which is not a very reasonable assumption
in this case. There must be a stricter bound to evaluate the redundancy.
Recently, some properties have been found for general codes decodable within
finite lengths of decoding delay [26, 27]. These results may be combined with
the proposed theories.

Another interesting question is how to obtain optimal codes for a given
source. Although we presented a method making some $N$-bit-delay AIFV code
from a given VV code in Proof of Theorem 3, its main purpose was to show the
existence of some code-tree set corresponding to the given code. It requires
setting a new code tree $T_{k_{s}}$ every time we break down the given code
and may be impractical for constructing general VV codes. One possible
approach for practical construction is to divide the code-tree optimization
problem into tree-wise forms, as the previous works [21, 28] do. The decodable
condition introduced in the paper will be helpful in designing the
optimization algorithm in such a case. Since the proposed code is a wide
class, including any conventional codes presented here, it is expected to
outperform other codes if we have such an algorithm.

##  6 Conclusions

We presented $N$-bit-delay AIFV codes, which can represent every code we can
make when permitting decoding delay up to $N$ bits. By introducing the
concepts of modes and expanded codewords, we explained the relationships
between the decoding delay and the code structure. It was shown that to
construct uniquely decodable codes, the expanded codewords should be prefix-
free and have prefix included in the corresponding mode. Additionally, the
decoding delay of the proposed code was shown to be the maximum-length string
in the modes.

Then, we detected the class of modes, basic modes, that achieves minimum
decoding delay among the codes giving the same codeword sequences. The idea of
basic modes greatly reduced the freedom of modes we have to consider.
Moreover, we derived a reasonable formulation of constraints for decodability
in the case of basic modes. Based on the conversion of binary strings to
intervals in the real number line, it was shown that we need only to compare
the intervals corresponding to expanded codewords and modes. This formulation
will make it easier to guarantee decodability numerically when constructing
codes.

Although there are still many questions, the theoretical results presented in
this paper must be essential for future study.

## References

  * [1] A. Puri, Multimedia Systems, Standards, and Networks.  CRC Press, 2000.
  * [2] S. Salomon and G. Motta, Handbook of Data Compression.  Springer, 2010.
  * [3] A. Spanias, T. Painter, and V. Atti, Audio Signal Processing and Coding.  John Wiley & Sons, Ltd, 2007.
  * [4] T. Backstrom, Speech Coding: with Code-Excited Linear Prediction.  Springer, 2018.
  * [5] T. Robinson, “SHORTEN: Simple lossless and near-lossless waveform compression,” Cambridge Univ. Eng. Dept., Cambridg, UK, Tech. Rep. 156,, 1994.
  * [6] G. Fuchs, C. Helmrich, G. Markovic, M. Neusinger, E. Ravelli, and T. Moriya, “Low delay LPC and MDCT-based audio coding in the EVS codec,” in Proc. ICASSP 2015, pp. 5723–5727, Apr. 2015.
  * [7] D. A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes,” Proceedings of the IRE, vol. 40, no. 9, pp. 1098–1101, 1952.
  * [8] A. Moffat and A. Turpin, Compression and coding algorithms.  Kluwer Academic Publishers, 2002.
  * [9] K. Sayood, Introduction to Data Compression (Third Edition).  Morgan Kaufmann, 2006.
  * [10] H. Yamamoto, M. Tsuchihashi, and J. Honda, “Almost Instantaneous Fixed-to-Variable Length Codes,” IEEE Trans. on Information Theory, vol. 61, pp. 6432–6443, Dec 2015.
  * [11] K. Iwata and H. Yamamoto, “A dynamic programming algorithm to construct optimal code trees of AIFV codes,” in 2016 International Symposium on Information Theory and Its Applications, pp. 641–645, 2016.
  * [12] M. Golin and E. Harb, “Speeding up the AIFV-2 dynamic programs by two orders of magnitude using Range Minimum Queries,” Theoretical Computer Science, vol. 865, pp. 99–118, 2021.
  * [13] W. Hu, H. Yamamoto, and J. Honda, “Worst-case Redundancy of Optimal Binary AIFV Codes and Their Extended Codes,” IEEE Trans. on Information Theory, vol. 63, pp. 5074–5086, Aug 2017.
  * [14] H. Yamamoto and K. Iwata, “An Iterative Algorithm to Construct Optimal Binary AIFV-m Codes,” p. 519–523, 2017.
  * [15] T. Kawai, K. Iwata, and H. Yamamoto, “A Dynamic Programming Algorithm to Construct Optimal Code Trees of Binary AIFV-m Codes,” IEICE technical report, vol. 117, pp. 79–84, May 2017.
  * [16] R. Fujita, K. Iwata, and H. Yamamoto, “On a Redundancy of AIFV-m Codes for m =3,5,” in 2020 IEEE International Symposium on Information Theory, pp. 2355–2359, 2020.
  * [17] R. Sugiura, Y. Kamamoto, N. Harada, and T. Moriya, “Optimal Golomb-Rice Code Extension for Lossless Coding of Low-Entropy Exponentially Distributed Sources,” IEEE Trans. on Information Theory, vol. 64, no. 4, pp. 3153–3161, 2018.
  * [18] R. Sugiura, Y. Kamamoto, and T. Moriya, “Extended-domain Golomb code and symmetry of relative redundancy,” IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, vol. E104-A, no. 08, 2021\.
  * [19] D. A. Levin, Y. Peres, and E. L. Wilmer, Markov chains and mixing times.  American Mathematical Society, 2006.
  * [20] K. Hashimoto and K. Iwata, “Optimality of Huffman Code in the Class of 1-Bit Delay Decodable Codes,” IEEE Journal on Selected Areas in Information Theory, vol. 3, no. 4, pp. 616–625, 2022.
  * [21] R. Fujita, K. Iwata, and H. Yamamoto, “An Optimality Proof of the Iterative Algorithm for AIFV-m Codes,” in 2018 IEEE International Symposium on Information Theory (ISIT), pp. 2187–2191, 2018.
  * [22] N. Uchida and M. Nishiara, “On searching for optimal non-alphabetic arithmetic codes based on A* algorithm,” vol. 118, pp. 19–23, Sept. 2018 (in Japanese).
  * [23] N. Uchida and M. Nishiara, “On searching for optimal non-alphabetic arithmetic codes with low delay based on A* algorithm,” in 2019 IEEE International Symposium on Information Theory (ISIT), Recent Results Session (Poster), 2019.
  * [24] K. Hashimoto and K. Iwata, “On the Optimality of the AIFV Code for Average Codeword Length,” pp. 56–61, Dec. 2020 (in Japanese).
  * [25] K. Hashimoto and K. Iwata, “On the Optimality of Binary AIFV Codes with Two Code Trees,” in 2021 IEEE International Symposium on Information Theory (ISIT), pp. 3173–3178, 2021.
  * [26] K. Hashimoto and K. Iwata, “Properties of k-bit Delay Decodable Codes,” arXiv, cs.IT 2306.07563, 2023.
  * [27] K. Hashimoto and K. Iwata, “The Optimality of AIFV Codes in the Class of 2-bit Delay Decodable Codes,” arXiv, cs.IT 2306.09671, 2023.
  * [28] R. Fujita, K. Iwata, and H. Yamamoto, “An Iterative Algorithm to Optimize the Average Performance of Markov Chains with Finite States,” in 2019 IEEE International Symposium on Information Theory (ISIT), pp. 1902–1906, 2019.