# The Efficiency of the ANS Entropy Encoding

Dmitry Kosolobov
Ural Federal University, Ekaterinburg, Russia
<EMAIL_ADDRESS>
###### Abstract

The Asymmetric Numeral Systems (ANS) encoder invented by Duda in 2009 is an
entropy encoder that had an immense impact on the data compression,
substituting arithmetic and Huffman coding. The optimality of the ANS was
studied by Duda and others but the precise asymptotic behaviour of its
redundancy (in comparison to the source entropy) was not completely
understood. In this paper we establish an optimal bound on the redundancy for
the tabled ANS (tANS), which is the most popular ANS variant used in practice.
Let $a_{1},a_{2},\ldots,a_{n}$ be a sequence of letters from an alphabet
$\\{0,1,\ldots,\sigma-1\\}$ such that each letter $a$ occurs in it $f_{a}$
times and $n=2^{r}$, for an integer $r$. The tANS encoder using Duda’s
“precise initialization” to fill the tANS table transforms this sequence into
a bit string of the following length (the table of frequencies is not included
in the encoding size):

$\sum\limits_{a\in[0..\sigma)}f_{a}\cdot\log\frac{n}{f_{a}}+O(\sigma+r),$

where the $O(\sigma+r)$ term can be upperbounded by $\sigma\log e+r$. The
$r$-bit additive term is an artifact of the initial encoder state,
indispensable to ANS; the rest incurs a redundancy of $O(\frac{\sigma}{n})$
bits per letter, which improves the previously known bound
$O(\frac{\sigma}{n}\log n)$. We complement this upper bound with a series of
examples showing that an $\Omega(\sigma+r)$ redundancy is indeed necessary
when $\sigma>n/3$; the $\Omega(\sigma+r)$ in our construction is greater than
$\frac{\sigma-1}{4}+r-2$. We argue that similar examples can be described for
any reasonable methods that distribute letters in the tANS table using only
the knowledge about frequencies. Thus, we disprove Duda’s conjecture that the
redundancy is $O(\frac{\sigma}{n^{2}})$ bits per letter.

We also propose a new variant of the range ANS (rANS), called rANS with fixed
accuracy, that is parameterized by an integer $k\geq 1$. In this variant the
division operation, which is unavoidable in rANS encoders, is performed only
in cases when its result belongs to the range $[2^{k}..2^{k+1})$. Therefore,
the division can be computed by faster methods provided $k$ is small. We
upperbound the redundancy for the rANS with fixed accuracy $k$ by
$\frac{n}{2^{k}-1}\log e+r$.

The unconventional way by which we introduce the ANS encoders might be
interesting by itself.

Keywords: asymmetric numeral systems, ANS, tANS, rANS, finite state entropy,
FSE, arithmetic coding, entropy, range coding, redundancy

##  1 Introduction

_Asymmetric numeral systems (ANS)_ is a class of entropy encoders invented by
Duda in 2009 [11, 12, 14]. These encoders had a huge impact on the data
compression by providing the same rates of compression as the arithmetic
coding [18, 19, 21] while being as fast as the Huffman coding [17] (and even
faster in some scenarios). Since the invention of ANS and the emergence of its
efficient implementation by Collet [7], several high performance compressors
based on ANS appeared [1, 6, 16] and it was integrated in some modern media
formats [2, 3]. The theoretical community also contributed to the study of ANS
in a series of works [4, 13, 20, 23, 24, 25], though less actively than the
practitioners [5, 8, 15, 16].

The primary focus of the theoretical analysis for entropy encoders is in the
estimation of the redundancy, the difference between the number of bits
produced by the encoder and the information theoretic entropy lower bound. The
results of the present paper are twofold: first, we establish tight asymptotic
upper and lower bounds on the redundancy of the most popular variant of ANS,
called the tabled ANS (tANS) or, sometimes, the Finite State Entropy (FSE);
second, we introduce and analyze a novel variant of the range ANS (rANS),
another version of ANS used in practice.

An entropy encoder receives as its input a sequence of $n$ numbers from a set
$\\{0,1,\ldots,\sigma-1\\}$ and transforms it into a bit string. Duda analyzed
his tANS encoder and found that its redundancy is $O(\frac{\sigma}{n}\log n)$
bits per letter111All logarithms in the paper are in base two. provided an
appropriate initialization is used for tANS tables (details are explained in
the sequel); see Equation (40) in [11] (his estimation, however, is somewhat
imprecise and in a slightly different setting). Based on experimental
evaluations, Duda conjectured that the tight bound for the redundancy is
$O(\frac{\sigma}{n^{2}})$ bits per letter [12]. Yokoo and Dubé [25]
investigated the same problem in more rigorous terms and closer to our setting
and showed that the redundancy per letter vanishes as the length $n$ tends to
infinity while $\sigma$ is fixed (however, they have some questionable
assumptions in their derivations).

In this paper we prove that the redundancy for tANS is $O(\frac{\sigma}{n})$
bits per letter. We complement this upper bound by a series of examples
showing that it is asymptotically tight when $\sigma>n/3$. As in the works
cited above, here we did not include in this bound the $r$ redundant bits that
are always produced by ANS encoders in the worst case (it is an artifact of
the initial state of the encoder). After uncovering the constant under the
big-O and including this $r$-bit term, the upper bound for the tANS redundancy
that we establish can be expressed as $\sigma\log e+r$ bits over all letters
(not per letter). Our lower bound examples show that a redundancy of
$\frac{\sigma-1}{4}+r-2$ bits is attainable, for $\sigma\approx n/3$. An
important part of tANS is the initialization of its internal tables, which has
a significant impact on the compression performance. The examples, however,
work for a wide class of initialization algorithms so that the same redundancy
can be observed for any adequate algorithm that generates the tANS tables
using only the known frequencies of letters without processing the sequence
itself (however, methods that analyze the sequence might avoid this effect
[10, 13]).

The second contribution of the present paper is a modification of the range
ANS (rANS). The rANS is another variant of ANS invented by Duda, which is
noticeably slower in practice than the tANS. However, rANS has a number of
advantages in some use scenarios because of which it was favoured by some
practitioners (and because it is easier to learn). The main advantage of rANS
is that it does not need tANS tables. Due to the less wasteful use of memory,
the rANS is more suitable for (pseudo)adaptive compression or when several
streams of data are encoded simultaneously [5, 15, 16]. The inherent problem
of rANS that slows down it significantly is the necessity to perform the
integer division during the encoding, which is expensive on modern processors.
The proposed modification of rANS, which we call rANS with fixed accuracy,
tries to mitigate this issue making the encoder faster while preserving the
same good properties of rANS.

The new rANS takes as a regulated parameter an integer $k\geq 1$. It is
guaranteed that the division can be performed only in cases when its result
belongs to the range $[2^{k}..2^{k+1})$. Thus, the division can be computed by
faster methods provided $k$ is small. We upperbound the redundancy for the
rANS with fixed accuracy $k$ by $\frac{n}{2^{k}-1}\log e+r$. The new rANS
variant is faster than the standard rANS but is still not as fast as tANS: in
our experiments, the rANS with fixed accuracy $k=3$ was 1.8 slower than tANS
implemented by Collet [7] (however, we did not use the technique of
interleaving streams by Giesen [16] in our implementation). We believe that
the rANS with fixed accuracy might be more suitable for hardware
implementations, where its restricted division operation can be sped up more
efficiently using versatile capabilities for parallelization.

The paper is organized as follows. After short preliminaries, Section 3
introduces a simple variant of the range ANS and, based on it, the tabled ANS.
Section 4 presents a tight analysis of the redundancy for the tabled ANS,
upper and lower bounds. Section 5 describes a novel variant of range ANS and
analyzes it. We conclude with some open problems in Section 6.

##  2 Preliminaries

A _letter_ is an element of a finite set of integers called an _alphabet_. We
consider sequences of letters. The sequences are also sometimes called
_strings_. Integer intervals are denoted by $[i..j]=\\{k\in\mathbb{Z}\colon
i\leq k\leq j\\}$ and $[i..j)=[i..j]\setminus\\{j\\}$. Fix an alphabet
$[0..\sigma)$ with $\sigma$ letters and a sequence of letters
$a_{1},a_{2},\ldots,a_{n}$ from it. For each letter $a$, denote by $f_{a}$ the
number of occurrences of $a$ in the sequence. The number $f_{a}$ is called the
_frequency of $a$_. The number $f_{a}/n$ is the _empirical probability of
$a$_. An entropy encoder transforms this sequence into a sequence of bits that
is then transmitted to a decoder. The encoder usually also transmits to the
decoder a table of frequencies. However, the problem of the storage for the
table is out of the scope of the present paper and we focus only on the
encoding for the sequence itself implicitly assuming that both sides know the
length $n$ of the sequence and the frequencies of letters. It is well known
that any encoder in the worst case should spend at least the following number
of bits for the sequence encoding (even under the assumption that the table of
frequencies is known), which the entropy information theoretic lower bound
[9]:

$\sum\limits_{a\in[0..\sigma)}f_{a}\log\frac{n}{f_{a}},$ (1)

assuming that $f_{a}\log\frac{n}{f_{a}}=0$ whenever $f_{a}=0$. We call (1) the
_entropy formula_ (though the empirically calculated entropy itself is this
value divided by $n$). The difference between the number of bits produced by
an encoder and the optimal number of bits from (1) is called a _redundancy_.
The redundancy is the primary focus of our analysis of ANS.

For each letter $a$, denote $c_{a}=\sum_{a^{\prime}\in[0..a)}f_{a^{\prime}}$.
Typically, encoders stores two arrays of $\sigma$ numbers $c_{a}$ and $f_{a}$
and some additional tables necessary for encoding. The ANS encoders are not an
exception.

Our analysis utilizes the following well-known logarithmic inequalities:
$\log(1+x)\leq x\log e$ and $\log(1-x)\geq\frac{-x}{1-x}\log e=\frac{-\log
e}{1/x-1}$.

##  3 ANS Encoders

On a high level, an ANS encoder can be described as a data structure that
maintains a positive integer $w$ that can be modified by two stack operations
“$w=\mathsf{push}(w,a)$” and “$(w,a)=\mathsf{pop}(w)$”: $\mathsf{push}$
encodes a letter $a$ into the number $w$ and returns the modified value for
$w$, and $\mathsf{pop}$ performs a reverse operation decoding the letter $a$
and restoring the old value for $w$. Given a sequence of letters
$a_{1},a_{2},\ldots,a_{n}$, the encoder pushes them consecutively and
transmits the resulting integer $w$ to a decoder, which in turn retrieves the
sequence from $w$ performing pop operations. Note that the letters appear in
the reverse order during the decoding, which is a distinctive feature of ANS.
For their correct coordinated work, both encoder and decoder should receive in
advance the same table of (approximate) frequencies of letters in the sequence
$a_{1},a_{2},\ldots,a_{n}$.

For didactic reasons, ANS encoders are usually first described in their
unbounded form in which they operate on very long integers $w$, which is
unrealistic. In practice, _streaming ANS encoders_ are used, which maintain
the value of $w$ during the construction within a fixed range fitting into a
machine word and they store all excessive bits in an output buffer by
performing a “renormalization” (akin to arithmetic encoders). However, in what
follows, we significantly diverge from this standard way of explanation for
ANS and introduce only the streaming ANS but in an unconventional manner; the
unbounded ANS variant is not discussed at all.

###  3.1 Basic Range ANS

Suppose that we are to encode a sequence of letters $a_{1},a_{2},\ldots,a_{n}$
from the alphabet $[0..\sigma)$. For each letter $a\in[0..\sigma)$, denote by
$f_{a}$ its frequency in the sequence (i.e., its empirical probability is
$\frac{f_{a}}{n}$). We assume that $n$ is a power of two, i.e., $n=2^{r}$ for
an integer $r\geq 0$. It is a standard assumption for both ANS and arithmetic
coding that simplifies implementations. If the length of the sequence is not a
power of two, then either the real probabilities of letters are approximated
with numbers $f_{a}/2^{r}$ or the sequence is split into chunks whose lengths
are powers of two; we discuss the former case briefly in the end of Section
4.1 but most details are omitted as they are not in the scope of this paper.

The streaming ANS encoder reads the letters $a_{1},a_{2},\ldots,a_{n}$ from
left to right and, after processing $a_{1},a_{2},\ldots,a_{i}$, encodes the
processed part into a positive integer $w_{i}$. Initially, $w_{0}=2^{r}$; the
choice for $w_{0}$ is somewhat arbitrary, the only necessary condition is
$w_{0}\geq 2^{r}$. To encode a new letter $a_{i+1}$, we transform the number
$w_{i}$ into $w_{i+1}$ by increasing the value stored in the $r+1$ highest
bits of $w_{i}$. Thus, $w_{0}<w_{1}<\cdots<w_{i+1}$. According to our
terminology, we have $w_{i+1}=\mathsf{push}(w_{i},a_{i+1})$. It is instructive
to image the number $w_{i}$ as a bit stream written from the highest bit
(which is always 1) to lowest bits. We replace at most $r+1$ highest bits with
a new larger value; see Figure 1.

$\begin{array}[]{rr}w_{i}=&\underline{10010}\,011001000010110\\\
w_{i+1}=&\underbrace{1001011}_{r+1\text{ bits}}011001000010110\end{array}$
Figure 1: A transformation of the number $w_{i}$ into $w_{i+1}$.

The numbers $w_{i}$ might be very long. However, since only the highest $r+1$
bits of $w_{i}$ matter for the encoder, all lower bits can be stored in an
output buffer. The integer $r$ is chosen so that the $r+1$ bits can be stored
into one machine word. For simplicity of the exposition, we omit this
technical detail and continue to discuss the numbers $w_{i}$ as if they were
stored explicitly.

The goal is to encode the whole sequence optimally so that, ideally, the final
number $w_{n}$ occupies $\sum_{a}f_{a}\log\frac{n}{f_{a}}$ bits. Intuitively,
one can achieve this by encoding each letter $a$ into
$\log\frac{n}{f_{a}}=r-\log f_{a}$ bits. During the processing of $a=a_{i+1}$,
we could have achieved this by replacing the highest $\log f_{a}+1$ bits of
$w_{i}$ with $r+1$ bits that store a new larger value; then, the number of
bits in $w_{i+1}$ and $w_{i}$ will differ by $r+1-(\log
f_{a}+1)=\log\frac{n}{f_{a}}$. But the number $\log f_{a}$ is not integer in
general. Therefore, instead, we replace either $\lfloor\log f_{a}\rfloor+1$ or
$\lfloor\log f_{a}\rfloor+2$ highest bits of $w_{i}$ with new $r+1$ bits. As a
result, the number of bits in $w_{i+1}$ increases by either $r-\lfloor\log
f_{a}\rfloor$ or $r-\lfloor\log f_{a}\rfloor-1$, which is approximately
$\log\frac{n}{f_{a}}$. The cumulative growth of $w_{n}$ may approach the
optimal $\log\frac{n}{f_{a}}$ bits per letter $a$ on average if the case when
$\lfloor\log f_{a}\rfloor+2$ bits are replaced happens more often. (Note that
when $f_{a}\geq n/2=2^{r-1}$, we have $\lfloor\log f_{a}\rfloor=r-1$ and the
number of bits in $w_{i}$ sometimes might not change at all; but the content
will change.)

What is the content of the $r+1$ new highest bits in $w_{i+1}$ and how do we
decide whether $\lfloor\log f_{a}\rfloor+1$ or $\lfloor\log f_{a}\rfloor+2$
highest bits of $w_{i}$ will be replaced?

Denote by $x^{\prime}$ the value stored in the highest $r+1$ bits of
$w_{i+1}$, i.e., $w_{i+1}=x^{\prime}\cdot 2^{\lfloor\log
w_{i+1}\rfloor-r}+\Delta$, where $0\leq\Delta<2^{\lfloor\log
w_{i+1}\rfloor-r}$ and $2^{r}\leq x^{\prime}<2^{r+1}$. Denote by $x$ the value
of the highest bits of $w_{i}$ that were replaced with $x^{\prime}$, i.e.,
$w_{i}=x\cdot 2^{\lfloor\log w_{i+1}\rfloor-r}+\Delta$, where $x\geq 1$. (In
the example of Figure 1 $x$ and $x^{\prime}$ are emphasized and $\Delta$ is a
common part of $w_{i}$ and $w_{i+1}$.) The scheme must be reversible: the
number $x^{\prime}$ must provide sufficient information for the decoder to
restore the letter $a_{i+1}$ and the number $x$. Since
$\sigma\leq\sum_{a}f_{a}=2^{r}$, there is enough place to encode $a_{i+1}$
into the $r$ lowest bits of $x^{\prime}$ (the highest, $(r+1)$th, bit of
$x^{\prime}$ is $1$). “Excessive” $2^{r}-\sigma$ possible values of
$x^{\prime}$ will be used to restore the number $x$, the replaced highest bits
of $w_{i}$.

The $r$ lowest bits of $x^{\prime}$ can store any number from the range
$[0..2^{r})$. The encoder chooses one of these numbers depending on the values
of $x$ and $a_{i+1}$. We distribute the numbers from $[0..2^{r})$ among the
letters according to their frequencies: for each letter $a$, denote
$c_{a}=\sum_{a^{\prime}\in[0..a)}f_{a^{\prime}}$; the subrange of values
$[c_{a}..c_{a+1})$ is allocated for $a$. Hence, given a letter $a=a_{i+1}$, we
have a room in the range that can store any number from $[0..f_{a})$ and this
information should suffice to restore the replaced number $x$ from
$x^{\prime}$. As an example, Figure 2 depicts a distribution of the range
$2^{r}=2^{4}$ among letters $a,b,c,d$ with frequencies $3,5,6,2$,
respectively.

$\begin{array}[]{ll}\begin{array}[]{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline\cr
a&a&a&b&b&b&b&b&c&c&c&c&c&c&d&d\\\ \hline\cr\end{array}&{}\\\
0&\\!\\!\\!\\!\\!2^{r}\end{array}$ Figure 2: A distribution of letters in a
range of length $2^{r}$.

Let $a=a_{i+1}$. Denote by $x_{1}$ and $x_{2}$ the values stored in,
respectively, the highest $\lfloor\log f_{a}\rfloor+1$ and the highest
$\lfloor\log f_{a}\rfloor+2$ bits of $w_{i}$. We assume that $x=x_{1}$ if
$x_{1}\geq f_{a}$, and $x=x_{2}$ otherwise. Thus, the condition $x_{1}\geq
f_{a}$ determines whether $\lfloor\log f_{a}\rfloor+1$ or $\lfloor\log
f_{a}\rfloor+2$ highest bits of $w_{i}$ will be used for $x$. Note that
$2^{\lfloor\log f_{a}\rfloor}\leq x_{1}<2\cdot f_{a}$ and $x_{2}\leq 2\cdot
x_{1}+1$. Therefore, we have $f_{a}\leq x<2\cdot f_{a}$ and, thus, $x\bmod
f_{a}=x-f_{a}$. The latter can be clearly seen in Figure 3: the bits occupied
by $x_{1}$ and $x_{2}$ are emphasized, respectively, on the left and right;
note that the number $f_{a}$ occupies $\lfloor\log f_{a}\rfloor+1$ bits.

$\begin{array}[]{rlcrl}w_{i}=&\underline{10110}011001000010110&{}{}{}\hfil&w_{i}=&\underline{100100}11001000010110\\\
f_{a}=&10011&{}{}{}\hfil&f_{a}=&\phantom{1}10011\\\ x\bmod
f_{a}=&\phantom{111}11&{}{}{}\hfil&x\bmod f_{a}=&\phantom{1}10001\end{array}$
Figure 3: Two cases: $x$ occupies $\lfloor\log f_{a}\rfloor+1$ (left) or
$\lfloor\log f_{a}\rfloor+2$ (right) highest bits of $w_{i}$.

In order to restore the value $x$ from $x^{\prime}$, it suffices to encode
somehow the value $x\bmod f_{a}$ into $x^{\prime}$: then, $x$ is restored as
$x=f_{a}+(x\bmod f_{a})$. To this end, the range $[c_{a}..c_{a+1})$ allocated
for the letter $a$ has exactly enough room. Thus, we have the following
transformation to encode $a$:

$x^{\prime}=2^{r}+c_{a}+(x\bmod f_{a}),\text{ where }f_{a}\leq x<2\cdot
f_{a}.$ (2)

With this approach, the decoder should perform a reverse transformation for
the $r+1$ highest bits of the number $w_{i+1}$ in order to restore $w_{i}$.
The decoding is straightforward:

$x=f_{a}+(x^{\prime}\bmod 2^{r})-c_{a},\text{ where }c_{a}\leq x^{\prime}\bmod
2^{r}<c_{a+1}.$ (3)

The decoded letter $a$ is determined by examining to which range
$[c_{a}..c_{a+1})$ the number $x^{\prime}\bmod 2^{r}$ belongs. This is how the
operation “$(w_{i},a_{i+1})=\mathsf{pop}(w_{i+1})$” is performed. It remains
to observe that $x^{\prime}>x$ since $x^{\prime}\geq 2^{r}+(x\bmod
f_{a})>f_{a}+(x\bmod f_{a})=x$. Therefore, the number $w_{i+1}$ indeed is
larger than $w_{i}$.

The described scheme is the simplest form of the so-called _range ANS (rANS)_.
As will be seen later, the size of $w_{n}$ in bits can be bounded by
$\sum_{a}f_{a}\log\frac{n}{f_{a}}+O(n)$. The redundancy $O(n)$ is quite
significant for many applications and, indeed, the described scheme does not
perform well in practice. The following section describes an additional
“shuffling” step in the encoder that fixes this issue. There exists, however,
a more elaborate version of the range ANS that does not have such a problem
and works well without shuffling; we discuss it briefly in Section 5 where we
also present a novel variant of the range ANS with good compression
guarantees.

###  3.2 Shuffling and Tabled ANS

The idea of the shuffling step enhancing the simple range ANS is to shuffle
the lower bits of $x^{\prime}$ in a random-like fashion so that the scheme (2)
is changed as follows:

$x^{\prime}=2^{r}+\mathsf{shuffle}[c_{a}+(x\bmod f_{a})],\text{ where
}f_{a}\leq x<2\cdot f_{a}.$ (4)

The array $\mathsf{shuffle}[0..2^{r}{-}1]$ is a permutation of the range
$[0..2^{r})$ but it is not entirely random: in order to guarantee the
inequality $x^{\prime}>x$ (which implies $w_{i+1}>w_{i}$), it must satisfy the
following property:

$\mathsf{shuffle}[c_{a}+i]<\mathsf{shuffle}[c_{a}+j],\text{ whenever }0\leq
i<j<f_{a}.$ (5)

Due to this condition, we have $x^{\prime}>x$ since $x^{\prime}\geq
2^{r}+(x\bmod f_{a})>f_{a}+(x\bmod f_{a})=x$. It is convenient to view
$\mathsf{shuffle}$ as defined via an additional array
$\mathsf{range}[0..2^{r}{-}1]$ that stores an (arbitrary) permutation of the
array of letters from Figure 2 in which every letter $a$ occurs exactly
$f_{a}$ times; then, for $i\in[0..f_{a})$, $\mathsf{shuffle}[c_{a}+i]$ is
equal to the index of the $(i+1)$th occurrence of the letter $a$ in
$\mathsf{range}$ (see Figure 4). Thus, to define $\mathsf{shuffle}$, it
suffices to initialize the array $\mathsf{range}$; we will implicitly imply
this relation in the sequel when the initialization of $\mathsf{shuffle}$ is
discussed.

$\begin{array}[]{rll}{}\hfil&\begin{array}[]{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline\cr
a&a&a&\leavevmode\hbox to4.29pt{\vbox
to6.94pt{\pgfpicture\makeatletter\hbox{\hskip 2.14583pt\lower-3.47221pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.14583pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$b$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox to0.0pt{}{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&\leavevmode\hbox
to4.29pt{\vbox to6.94pt{\pgfpicture\makeatletter\hbox{\hskip
2.14583pt\lower-3.47221pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.14583pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$b$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox to0.0pt{}{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&\leavevmode\hbox
to4.29pt{\vbox to6.94pt{\pgfpicture\makeatletter\hbox{\hskip
2.14583pt\lower-3.47221pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.14583pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$b$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox to0.0pt{}{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&\leavevmode\hbox
to4.29pt{\vbox to6.94pt{\pgfpicture\makeatletter\hbox{\hskip
2.14583pt\lower-3.47221pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.14583pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$b$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox to0.0pt{}{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&\leavevmode\hbox
to4.29pt{\vbox to6.94pt{\pgfpicture\makeatletter\hbox{\hskip
2.14583pt\lower-3.47221pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.14583pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$b$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox to0.0pt{}{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&c&c&c&c&c&c&d&d\\\
\hline\cr\end{array}&{}\\\ {}\hfil&0&\\!\\!\\!\\!\\!2^{r}\\\
\mathsf{range}=&\begin{array}[]{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline\cr\leavevmode\hbox
to4.29pt{\vbox to6.94pt{\pgfpicture\makeatletter\hbox{\hskip
2.14583pt\lower-3.47221pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.14583pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$b$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox to0.0pt{}{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&d&a&c&c&\leavevmode\hbox
to4.29pt{\vbox to6.94pt{\pgfpicture\makeatletter\hbox{\hskip
2.14583pt\lower-3.47221pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.14583pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$b$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox to0.0pt{}{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&a&\leavevmode\hbox
to4.29pt{\vbox to6.94pt{\pgfpicture\makeatletter\hbox{\hskip
2.14583pt\lower-3.47221pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.14583pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$b$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox to0.0pt{}{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&c&d&\leavevmode\hbox
to4.29pt{\vbox to6.94pt{\pgfpicture\makeatletter\hbox{\hskip
2.14583pt\lower-3.47221pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.14583pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$b$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox to0.0pt{}{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&c&c&\leavevmode\hbox
to4.29pt{\vbox to6.94pt{\pgfpicture\makeatletter\hbox{\hskip
2.14583pt\lower-3.47221pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.14583pt}{-3.47221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$b$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox to0.0pt{}{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}&c&a\\\
\hline\cr\end{array}&{}\\\
{}\hfil&0&\\!\\!\\!\\!\\!2^{r}\end{array}\leavevmode\hbox to1.5pt{\vbox
to3.2pt{\pgfpicture\makeatletter\hbox{\hskip 1.19998pt\lower-1.59998pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ } { {}{}{}{}{}}{}{ {}{}{}{}{}}
{{{{{}}{ {}{}}{{}{}} {}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{{
{\pgfsys@beginscope\pgfsys@setlinewidth{0.32pt}\pgfsys@setdash{}{0.0pt}\pgfsys@roundcap\pgfsys@roundjoin{}
{}{}{} {}{}{}
\pgfsys@moveto{-1.19998pt}{1.59998pt}\pgfsys@curveto{-1.09998pt}{0.99998pt}{0.0pt}{0.09999pt}{0.29999pt}{0.0pt}\pgfsys@curveto{0.0pt}{-0.09999pt}{-1.09998pt}{-0.99998pt}{-1.19998pt}{-1.59998pt}\pgfsys@stroke\pgfsys@endscope}}
}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} { {}{}{}{}{}}{}{ {}{}{}{}{}} {{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{}{{{{{}}{ {}{}}{{}{}}
{}{}}{}{}}}{{}}{}{}{}{}{}{}{}{{}}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.45999pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox
to0.0pt{}{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}$ Figure 4: A shuffled
distribution of letters. Here, we have
$\mathsf{shuffle}[c_{b}]=0,\mathsf{shuffle}[c_{b}+1]=5,\mathsf{shuffle}[c_{b}+2]=7$.

The decoding procedure (3) performs a reverse transformation in an obvious
way:

$x=f_{a}+\mathsf{unshuffle}[x^{\prime}\bmod 2^{r}]-c_{a},\text{ where
}\mathsf{range}[x^{\prime}\bmod 2^{r}]=a.$

Note the use of the array $\mathsf{range}$ in the decoder to determine the
letter $a$. The array $\mathsf{unshuffle}$ is the inverse of
$\mathsf{shuffle}$ such that $\mathsf{unshuffle}[\mathsf{shuffle}[z]]=z$, for
any $z\in[0..2^{r})$. Thus, it “moves” the value $x^{\prime}\bmod 2^{r}$ to
its “correct” location and we have to add $f_{a}$ and subtract $c_{a}$
afterward. However, implementations usually construct, instead of the arrays
$\mathsf{unshuffle}$ and $\mathsf{range}$, an array $\mathsf{decode}$ that
stores, for each number $x^{\prime}\bmod 2^{r}$, an already corrected value
for $x$ and the corresponding letter $a$; hence, the decoding is much simpler:

$(x,a)=\mathsf{decode}[x^{\prime}\bmod 2^{r}].$

The described scheme is called a _tabled ANS (tANS)_. It is the most popular
variant of ANS widely used in practice. The choice of a shuffling method is
crucial for its performance. Some methods are considered in the next section.
There are several additional technical improvements that can be applied to
this basic scheme. Perhaps, the most notable of them is that one can feed to
the decoder more than $r+1$ bits at once, decoding many letters in one step
(the information about the decoded letters and the new value for $x$ must be
stored in the array $\mathsf{decode}$). We do not discuss these details
further.

###  3.3 Shuffling Methods

The general rule for shuffling is to distribute letters in the array
$\mathsf{range}$ as uniformly as possible so that, for any letter $a$, the
distance between consecutive occurrences of $a$ is approximately
$\frac{n}{f_{a}}$. Implementations usually use heuristics for this [7] or
Duda’s method [12] (which is introduced below). Let us discuss some
considerations on this regard that will be developed in a more rigorous way in
Section 4 in the sequel.

The following informal argument justifies the scheme with shuffling. The value
$\log x^{\prime}-\log x$ is, in a sense, an increase in bits from the number
$w_{i}$ to $w_{i+1}$; the bit length of $w_{n}$, the final encoding, is
approximately the sum of the increases (this reasoning is formalized in
Section 4). Denote $\delta=x\bmod f_{a}$. We have $x=f_{a}+\delta$. If the
letters in the array $\mathsf{range}$ are distributed uniformly, the distance
between two consecutive letters $a$ is approximately $\frac{n}{f_{a}}$.
Therefore, the encoder transforms $x$ approximately to $x^{\prime}\approx
2^{r}+\frac{n}{f_{a}}\delta=\frac{n}{f_{a}}(f_{a}+\delta)=\frac{n}{f_{a}}x$
(recall that $n=2^{r}$). Hence, we obtain $\log x^{\prime}-\log
x\approx\log\frac{n}{f_{a}}$, which is precisely the optimal number of bits
for the letter $a$ according to the entropy formula.

The argument suggests that the shuffling method should spread the letters in
the array $\mathsf{range}$ in such a way that the distance between two
consecutive occurrences of $a$ is approximately $\frac{n}{f_{a}}$ and the
encoder transforms the number $x=f_{a}+\delta$ as close as possible to the
number $2^{r}+\frac{n}{f_{a}}\delta$. Under this assumption of “uniformity”,
if the first occurrence of letter $a$ is at position $p$ in $\mathsf{range}$,
then $x$ is transformed into $x^{\prime}\approx
2^{r}+\frac{n}{f_{a}}\delta+p$. The term $p$ adds to the redundancy associated
with $f_{a}$ letters $a$: the larger the value of $p$, the more bits are spent
per letter $a$. Therefore, the first occurrences of more frequent letters
should be closer to the beginning of the array $\mathsf{range}$ so that they
produce less redundancies overall. Duda’s method, which he called a _precise
initialization_ , tries to take into account all these considerations.

Duda’s algorithm maintains a priority queue with the following operations:
$\mathsf{put}(q,a)$ adds a pair of numbers $(q,a)$ to the queue;
$(q,a)=\mathsf{getmin}()$ removes from the queue a pair $(q,a)$ with the
smallest value $q$ (breaking ties arbitrarily). We first give in Algorithm 1
simplified Duda’s algorithm, which is easier to analyze.

Algorithm 1 A simple initialization algorithm.

for $a\in[0..\sigma)$ do

$\mathsf{put}(0,a),\,d_{a}=c_{a};$

for $i=0,1,\ldots,2^{r}-1$ do

$(q,a)=\mathsf{getmin}(),$ $\mathsf{range}[i]=a,$ $\mathsf{shuffle}[d_{a}]=i;$

$\mathsf{put}(q+\frac{n}{f_{a}},a),$ $d_{a}=d_{a}+1;$

The array $\mathsf{range}$ corresponding to $\mathsf{shuffle}$ is not needed
for the encoder and its construction is added here for the convenience of the
reader.

At every moment during the work of the algorithm, there is only one instance
of each letter in the priority queue and, if a letter $a$ was assigned to the
array $\mathsf{range}$ exactly $k$ times, then it is represented by the pair
$(\frac{n}{f_{a}}k,a)$ in the queue. Therefore, after $f_{a}$ assignments of
$a$ into $\mathsf{range}$, the letter is represented by $(n,a)$ and all other
letters $b$ that had less than $f_{b}$ assignments in $\mathsf{range}$ are
represented as $(q,b)$ with $q<n$. Hence, in the end, each letter $a$ occurs
in $\mathsf{range}$ exactly $f_{a}$ times.

Duda’s original “precise initialization” is the same as Algorithm 1 except
that the operation “$\mathsf{put}(0,a)$” from the first loop is changed to
“$\mathsf{put}(\frac{1}{2}\cdot\frac{n}{f_{a}},a)$”. Its correctness is proved
analogously.

##  4 Analysis of the Tabled ANS

We are to estimate the redundancy of the output produced by the ANS encoder,
i.e., the difference between $\lceil\log w_{n}\rceil$ and the information
theoretic lower bound $\sum_{a}f_{a}\log\frac{n}{f_{a}}$. We postpone the
analysis of the ANS without shuffling to the next section, where its more
general variant is considered. In this subsection we consider the ANS with
shuffling, i.e., the tabled ANS (tANS). To the best of our knowledge, the
following analysis, albeit quite simple, evaded the attention of researchers
and was not present in prior works. Our proof methods, however, stem from
observations and arguments from Dubé and Yokoo [25] and Duda [11, 12].

###  4.1 Upper Bounds

Let us upperbound $\log w_{i+1}-\log w_{i}=\log\frac{w_{i+1}}{w_{i}}$, a bit
increase after one step of the encoding procedure. The total number of bits
will be then estimated as follows (the term $r$ appears because $w_{0}=2^{r}$
and $\log w_{0}=r$):

$\log
w_{n}=\log\frac{w_{n}}{w_{n-1}}+\log\frac{w_{n-1}}{w_{n-2}}+\cdots+\log\frac{w_{1}}{w_{0}}+r.$
(6)

Suppose that $w_{i+1}$ was obtained from $w_{i}$ by “inserting” a letter $a$
as described above. Denote $\ell=\lfloor\log w_{i+1}\rfloor-r$ so that
$w_{i}=x\cdot 2^{\ell}+\Delta$ and $w_{i+1}=x^{\prime}\cdot 2^{\ell}+\Delta$,
where $0\leq\Delta<2^{\ell}.$ Then,
$\log\frac{w_{i+1}}{w_{i}}=\log\left(\frac{x^{\prime}2^{\ell}+\Delta}{x2^{\ell}+\Delta}\right)=\log\left(\frac{x^{\prime}}{x}\left(\frac{1+\Delta/(x^{\prime}2^{\ell})}{1+\Delta/(x2^{\ell})}\right)\right)=\log
x^{\prime}-\log
x+\log\left(\frac{1+\Delta/(x^{\prime}2^{\ell})}{1+\Delta/(x2^{\ell})}\right)$.
Since $x^{\prime}>x$, the additive term
$\log\left(\frac{1+\Delta/(x^{\prime}2^{\ell})}{1+\Delta/(x2^{\ell})}\right)$
is negative and, thus, we have obtained the following inequality:

$\log w_{i+1}-\log w_{i}\leq\log x^{\prime}-\log x.$ (7)

It remains to estimate how close is $\log x^{\prime}-\log x$ to the optimum
$\log\frac{n}{f_{a}}$. We first consider the case when the encoder uses the
shuffling produced by simplified Duda’s algorithm (Algorithm 1).

Fix a letter $a$ and a number $\delta\in[0..f_{a})$. Denote by $k$ the index
of the $(\delta+1)$th occurrence of $a$ in $\mathsf{range}$. Note that
$\mathsf{shuffle}[c_{a}+\delta]=k$, by definition. For each $b\in[0..\sigma)$,
denote by $k_{b}$ the number of letters $b$ in the subrange
$\mathsf{range}[0..k{-}1]$. Clearly, we have $k=\sum_{b}k_{b}$. The shuffling
algorithm implies the following inequality:

$(k_{b}-1)\frac{n}{f_{b}}\leq\delta\frac{n}{f_{a}}.$ (8)

We express $k_{b}$ from (8) as $k_{b}\leq\delta\frac{f_{b}}{f_{a}}+1$. Summing
over all $b\in[0..\sigma)$, we deduce from this
$k\leq\delta\frac{n}{f_{a}}+\sigma$. It follows from (7) that, in order to
analyze the number of bits per letter produced by the encoder, we have to
estimate $\log x^{\prime}-\log x$, where, by (4),
$x^{\prime}=2^{r}+\mathsf{shuffle}[c_{a}+(x\bmod f_{a})]$. Assuming
$\delta=x\bmod f_{a}$, we obtain $x=f_{a}+\delta$ and
$x^{\prime}=2^{r}+k=n+k$. Therefore, $\log x^{\prime}-\log x=\log(n+k)-\log
x\leq\log(n+\delta\frac{n}{f_{a}}+\sigma)-\log
x=\log(\frac{n}{f_{a}}x+\sigma)-\log
x=\log\frac{n}{f_{a}}+\log(1+\frac{\sigma}{nx/f_{a}})\leq\log\frac{n}{f_{a}}+\frac{\sigma}{n}\log
e$. Thus, we estimate the number of bits per letter $a$ as
$\log\frac{n}{f_{a}}+\frac{\sigma}{n}\log e$, i.e., the redundancy is
$\frac{\sigma}{n}\log e$ bits per letters.

Now let us analyze Duda’s original algorithm. The algorithm is the same as
Algorithm 1 except that the operation “$\mathsf{put}(0,a)$” from the first
loop is changed to “$\mathsf{put}(\frac{1}{2}\cdot\frac{n}{f_{a}},a)$”. The
analysis is slightly more complicated. First, an equation analogous to (8) for
this case looks as follows:

$\left(k_{b}-\frac{1}{2}\right)\frac{n}{f_{b}}\leq\left(\delta+\frac{1}{2}\right)\frac{n}{f_{a}}.$

We then similarly deduce
$k_{b}\leq(\delta+\frac{1}{2})\frac{f_{b}}{f_{a}}+\frac{1}{2}$ and, summing
over all $b$, $k\leq(\delta+\frac{1}{2})\frac{n}{f_{a}}+\frac{\sigma}{2}$.
Again, assuming $x=f_{a}+\delta$, it follows from this that $\log
x^{\prime}-\log
x\leq\log(\frac{n}{f_{a}}x+\frac{n}{2f_{a}}+\frac{\sigma}{2})-\log
x=\log\frac{n}{f_{a}}+\log(1+\frac{1}{2x}+\frac{\sigma}{2nx/f_{a}})\leq\log\frac{n}{f_{a}}+(\frac{1}{2f_{a}}+\frac{\sigma}{2n})\log
e$. The letter $a$ occurs in the sequence exactly $f_{a}$ times. Hence, the
redundancies $\frac{1}{2f_{a}}\log e$ for letters $a$ sum up to
$\frac{1}{2}\log e$ over all these occurrence and, therefore, in the end we
obtain $\frac{\sigma}{2n}\log e$ bits per letter contributed by the terms
$\frac{1}{2f_{a}}\log e$, for all letters $a$, in the final encoding. Adding
to this the $\frac{\sigma}{2n}\log e$ bits per letter, we obtain
$\frac{\sigma}{n}\log e$ redundant bits per letter in the final encoding.

It remains to add the additive term $r$ from (6) to the redundancy, which
contributes $\frac{r}{n}$ bits per letter, and the following theorem is
proved.

######  Theorem 1.

Given a sequence $a_{1},a_{2},\ldots,a_{n}$ of letters from an alphabet
$[0..\sigma)$ such that each letter $a$ occurs in it $f_{a}$ times and
$n=2^{r}$ for an integer $r$, the ANS encoder using [simplified] Duda’s
precise initialization transforms this sequence into a bit string of length

$\sum\limits_{a\in[0..\sigma)}f_{a}\cdot\log\frac{n}{f_{a}}+O(\sigma+r),$

where the $O(\sigma+r)$ term can be bounded by $\sigma\log e+r$. Thus, we have
$O(\frac{\sigma+r}{n})$ redundant bits per letter.

In practice, the length $m$ of the encoded sequence $a_{1},a_{2},\ldots,a_{m}$
is not necessarily a power of two. A typical solution for this case is to
approximate the real empirical probabilities $f_{a}/m$ of letters with
approximate ones $\hat{f}_{a}/2^{r}$, where $\sum_{a}\hat{f}_{a}=2^{r}$. The
ANS encoder then processes the sequence as usually but using the “frequencies”
$\hat{f}_{a}$ instead of $f_{a}$. The same analysis can be applied for this
case: Equations (6) and (7) trivially hold and the value $\log x^{\prime}-\log
x$ is bounded in the same manner by
$\log\frac{2^{r}}{\hat{f}_{a}}+\frac{\sigma}{2^{r}}\log e$, for simplified
Duda’s initialization, and by
$\log\frac{2^{r}}{\hat{f}_{a}}+(\frac{1}{2\hat{f}_{a}}+\frac{\sigma}{2\cdot
2^{r}})\log e$, for Duda’s initialization. Summing the redundancies over all
$m$ letters, we obtain the following theorem (for simplicity, the theorem is
stated only for simplified Duda’s initialization).

######  Theorem 2.

Let $a_{1},a_{2},\ldots,a_{m}$ be a sequence of letters from an alphabet
$[0..\sigma)$ such that each letter $a$ occurs in it $f_{a}$ times. Let the
probabilities $f_{a}/m$ be approximated by numbers $\hat{f}_{a}/n$ such that
$\hat{f}_{a}$ are integers, $n=2^{r}$, for an integer $r$, and
$\sum_{a\in[0..\sigma)}\hat{f}_{a}=n$. The ANS encoder that uses the
approximate probabilities and simplified Duda’s initialization transforms this
sequence into a bit string of length

$\sum\limits_{a\in[0..\sigma)}f_{a}\cdot\log\frac{n}{\hat{f}_{a}}+O(\frac{\sigma
m}{n}+r),$

where the $O(\frac{\sigma m}{n}+r)$ term can be bounded by $\frac{\sigma
m}{n}\log e+r$.

###  4.2 Lower Bound Example

Apparently, the $r$-bit redundancy incurred by the initial value $w_{0}$ is
unavoidable in the described scheme. It is less clear whether an $O(\sigma)$
additive term is necessary in Theorem 1. An informal argument supporting that
this is the case is as follows. Consider a sequence in which all letters are
(approximately) equiprobable, i.e., their frequencies $f_{a}$ are
${\sim}\frac{n}{\sigma}$. The lower bound for the encoding of the sequence is
$n\log\sigma$ bits. The array $\mathsf{range}$ constructed by Duda’s
initialization algorithm for the sequence looks (approximately) as $n/\sigma$
blocks, each of which is of size $\sigma$ and consists of consecutive letters
$0,1,\ldots,\sigma-1$. Hence, when the encoder receives a letter
$a_{i+1}=a\in[0..\sigma)$ during its work, it transforms a number
$x=f_{a}+\delta$, where $\delta=x\bmod f_{a}$, occupying leading bits of
$w_{i}$, into the number
$x^{\prime}=2^{r}+\frac{n}{f_{a}}\delta+a=\frac{n}{f_{a}}x+a=\sigma x+a$ (note
that $f_{a}=n/\sigma$, by our assumption). As in the previous section, one can
deduce from this that $\log x^{\prime}-\log
x=\log\sigma+\log(1+\frac{a}{\sigma x})$. Since $x<2f_{a}=2\frac{n}{\sigma}$,
the redundant additive term $\log(1+\frac{a}{\sigma x})$ can be estimated as
$\log(1+\frac{a}{\sigma
x})\geq\log(1+\frac{a}{2n})\geq\frac{a}{2n}\cdot\frac{1}{1+a/(2n)}$. Thus, the
redundancy is approximately $\frac{a}{2n}$ bits per letter $a$, which sums to
the total redundancy of
$\sum_{a}\frac{a}{2n}f_{a}=\sum_{a}\frac{a}{2\sigma}=\frac{\sigma+1}{4}$ bits
over all letters in the sequence.

This informal argument is only an intuition since the negative terms
$\log\left(\frac{1+\Delta/(x^{\prime}2^{\ell})}{1+\Delta/(x2^{\ell})}\right)$
that appear in the analysis of Section 4.1 could, in principle, diminish the
described effect. Nevertheless, as we are to show, an $\Omega(\sigma)$
redundancy indeed appears in some instances.

Fix an even integer $r>0$. Observe that $2^{r}\equiv 1\pmod{3}$ since $r$ is
even. Denote $n=2^{r}$. The sequence under construction will contain
$\sigma=(n-1)/3+1$ letters $0,1,\ldots,\sigma-1$. Each letter
$a\in[0..\sigma{-}1)$ has exactly three occurrences in the sequence (i.e.,
$f_{a}=3$) and the letter $\sigma-1$ occurs only once (i.e.,
$f_{\sigma-1}=1$); note that $\sum_{a\in[0..\sigma)}f_{a}=3(\sigma-1)+1=n$.
The entropy formula gives the following lower bound on the encoding size for
the sequence:

$(n-1)\log\frac{n}{3}+\log n=(n-1)(r-\log 3)+r=(n-1)(r-1.58496...)+r.$ (9)

It is straightforward that with such frequencies of letters both Duda’s
initialization algorithm and its simplified variant (Algorithm 1) construct
the same array $\mathsf{range}$: the subrange $\mathsf{range}[0..\sigma{-}1]$
contains consecutively the letters $0,1,\ldots,\sigma-1$ (in this order) and
the subranges $\mathsf{range}[\sigma..2\sigma{-}2]$ and
$\mathsf{range}[2\sigma{-}1..n{-}1]$ are equal and both contain consecutively
the letters $0,1,\ldots,\sigma-2$ (in this order). Now let us arrange the
letters in the sequence $a_{1},a_{2},\ldots,a_{n}$.

The last letter $a_{n}$ is $\sigma-1$. The rest, $a_{1},a_{2},\ldots,a_{n-1}$,
consists of letters $a\in[0..\sigma{-}1)$ whose frequencies are $f_{a}=3$
($11_{2}$ in binary). When the encoder processes a letter
$a_{i+1}=a\in[0..\sigma{-}1)$ and modifies the number $w_{i}$ representing the
prefix $a_{1},a_{2},\ldots,a_{i}$, it replaces either two or three leading
bits of $w_{i}$ with new $r+1$ bits, thus producing the number $w_{i+1}$. The
choice of whether to replace two or three bits depends on whether the two
leading bits of $w_{i}$ are $11$ or $10$, respectively (i.e., whether the two
bits store a number less than $f_{a}=3$ or not). We are to arrange the letters
$[0..\sigma{-}1)$ in the sequence $a_{1},a_{2},\ldots,a_{n-1}$ in such a way
that the encoder chooses the two options alternatingly: it replaces three
leading bits of $w_{i}$ if $i$ is even, and two bits if $i$ is odd. The total
number of bits produced in this way is at least
$\frac{n-1}{2}(r-1)+\frac{n-1}{2}(r-2)+r=(n-1)(r-1.5)+r$ (the additive term
$r$ appears when the last letter $a_{n}=\sigma-1$ is encoded). Comparing this
to (9), we can see that the encoding generated by ANS is larger than the
optimum (9) by at least $(\log 3-1.5)(n-1)>0.08496(n-1)$. By simple
calculations, we deduce from the equality $\sigma=(n-1)/3+1$ that the
redundancy $0.08496(n-1)$ is larger than $\frac{\sigma-1}{4}$. Let us describe
an arrangement of letters that produces such effect of “alternation”.

The encoder consecutively transforms the initial value $w_{0}=2^{r}$ into
$w_{1},w_{2},\ldots$ by performing the push operations:
$w_{i+1}=\mathsf{push}(w_{i},a_{i+1})$. Let us call the number $\lfloor
w_{i}/2^{\lfloor\log w_{i}\rfloor-r}\rfloor\bmod 2^{r}$ a _state_ ; it is the
value stored in the highest $r+1$ bits of the number $w_{i}$ currently
processed by the encoder minus the highest bit 1. The range of possible states
is $[0..2^{r})=[0..n)$. We split this range into three disjoint segments
numbered i, ii, iii: $[0..\sigma)$, $[\sigma..2\sigma-1)$, $[2\sigma-1..n)$,
whose lengths are $\sigma$, $\sigma-1$, $\sigma-1$, respectively. The subarray
$\mathsf{range}[0..\sigma{-}1]$ corresponding to the segment i contains all
letters $[0..\sigma)$; each of the subarrays
$\mathsf{range}[\sigma..2\sigma-2]$ and $\mathsf{range}[2\sigma-1..n-1]$
corresponding to the segments ii and iii, respectively, contains all letters
$[0..\sigma{-}1)$.

Receiving the letter $\sigma-1$ (which occurs in the sequence only once), the
encoder transforms any current state to the state $\sigma-1$ (it is the index
of the letter $\sigma-1$ in the array $\mathsf{range}$). In order to describe
how states are transformed by other letters, let us split the state range
$[0..2^{r})$ into three segments called A, B, C: $[0..2^{r-2})$,
$[2^{r-2}..2^{r-1})$, $[2^{r-1}..n)$, whose lengths are $2^{r-2}$, $2^{r-2}$,
$2^{r-1}$, respectively. The segments are related as follows: receiving a
letter from $[0..\sigma{-}1)$, the encoder translates the current state from
the segment A (respectively, B, C) to a state from the segment ii
(respectively, iii, i); see Figure 5 where this transition of states is
illustrated by dashed lines connecting the corresponding segments.

Figure 5: Two splits of the state range $[0..2^{r})$ into segments. Here
$r=6$. Common first bits of numbers $w_{i}$ corresponding to the states
belonging to the segments A, B, C are written above the respective segments.
Observe that the bits start with $11$ only when a state belongs to the segment
C. The range $[0..\sigma{-}1)$ is depicted under the segment ii: the encoder
receives letters from the right part $[\sigma/2-1..\sigma-1)$ when the current
state is from the segment A, and from the left part $[0..\sigma/2)$ when the
state is from the segment C.

Receiving $a_{i+1}=a\in[0..\sigma{-}1)$, the encoder replaces two leading bits
of $w_{i}$ with $r+1$ new bits if the current state is from the segment C;
otherwise, it replaces three leading bits of $w_{i}$. This behaviour is
determined by first bits of $w_{i}$, which are equal to $11...$ only for
states from the segment C; see Figure 5. The execution of the encoder starts
with the state $0$, which belongs to the segment A. We are to arrange letters
in the sequence $a_{1},a_{2},\ldots,a_{n-1}$ so that, for odd $i$, the state
corresponding to $w_{i}$ belongs to the segment C, and for even $i$, to the
segment A. The states in our arrangement will never belong to the segment B.

Since $\sigma+\sigma/2-1=n/2$ and $n/2$ is the leftmost state from the segment
C, any state from the segment A transits to a state from the segment C when
the encoder receives a letter $a$ from the range $[\sigma/2-1..\sigma-1)$; the
new state is $\sigma+a$, the $a$th element of the segment ii (see Figure 5 for
an illustration). Similarly, since $\sigma/2<n/4$ and $n/4-1$ is the rightmost
state from the segment A, any state from the segment C transits to a state
from the segment A when the encoder receives a letter $a\in[0..\sigma/2)$.
Accordingly, for $i\in[1..n)$, we put in the sequence as the letter $a_{i}$ a
letter from $[\sigma/2-1..\sigma-1)$ if $i$ is odd, and a letter from
$[0..\sigma/2)$ if $i$ is even (note that both ranges share a common letter
$\sigma/2-1$; it is not a mistake). The states thus “bounce” between the
segments A and C during the processing of $a_{1},a_{2},\ldots,a_{n-1}$ by the
encoder. Since the sizes of both ranges $[0..\sigma/2)$ and
$[\sigma/2-1..\sigma-1)$ are $\sigma/2$ and they share a common letter
$\sigma/2-1$, the letters $[0..\sigma{-}1)$ can be distributed in the sequence
$a_{1},a_{2},\ldots,a_{n-1}$ in such way that each letter occurs exactly three
times and each letter $a_{i}$ is from the range $[\sigma/2-1..\sigma-1)$, for
odd $i$, and from the range $[0..\sigma/2)$, for even $i$.

We thus have obtained a redundancy of $(\log 3-1.5)(n-1)>\frac{\sigma-1}{4}$
bits. Adding to this $r-2$ bits produced by the $r-2$ lowest bits of the
initial value $w_{0}$, we have proved the following theorem.

######  Theorem 3.

For arbitrarily large $n=2^{r}$, there exists a sequence
$a_{1},a_{2},\ldots,a_{n}$ of letters from an alphabet $[0..\sigma)$ with
$\sigma>n/3$ such that the ANS encoder using [simplified] Duda’s precise
initialization transforms this sequence into a bit string of length at least

$\sum\limits_{a\in[0..\sigma)}f_{a}\cdot\log\frac{n}{f_{a}}+\frac{\sigma-1}{4}+r-2,$

where $f_{a}$ is the number of occurrences for letter $a$. Thus, the
redundancy is $\frac{\sigma-1}{4}+r-2$ bits.

The example that attains the lower bound of Theorem 3 is very simple. Hence,
it is reasonable to assume that any adequate shuffling method would have the
same redundancy $\Omega(\sigma+r)$ as in Theorem 3 on a similarly constructed
sequence $a_{1},a_{2},\ldots,a_{n}$. We believe, therefore, that Duda’s
conjecture that the redundancy can be $O(\frac{\sigma}{n^{2}})$ bits per
letter when an appropriate shuffling method is used is disproved.

##  5 Range ANS with Fixed Accuracy

In Section 3.1, a simple range ANS (rANS) was described, which is just the ANS
without shuffling. Now we are to introduce another variant of rANS, called
_rANS with fixed accuracy_ to distinguish it from the rANS as defined by Duda
[12, 14] (which is also sketched below). Our exposition is less detailed than
in the previous sections since we believe that all ideas and intuition
necessary for understanding were developed above.

Let $a_{1},a_{2},\ldots,a_{n}$ be a sequence of letters over an alphabet
$[0..\sigma)$, where $n=2^{r}$ and the frequencies of letters are denoted by
$f_{a}$ (i.e., the probability for letter $a$ is $\frac{f_{a}}{n}$). Fix an
integer $k\geq 0$, which will serve as a user-defined accuracy parameter
regulating the size of redundancy (typically, $0\leq k\leq 4$). As in the
simple rANS, the encoder starts its work with a number $w_{0}=2^{r+k}$; the
value $w_{0}$ might be arbitrary, the only necessary condition is $w_{0}\geq
2^{r+k}$. The encoder consecutively performs operations
$w_{i+1}=\mathsf{push}(w_{i},a_{i+1})$, for $i=0,1,\ldots,n-1$, but the
operation $\mathsf{push}(w,a)$ works differently this time: it substitutes
either $\lfloor\log f_{a}\rfloor+k+1$ or $\lfloor\log f_{a}\rfloor+k+2$
highest bits of $w$ that store a number $x$ by $r+k+1$ new bits that store the
number $x^{\prime}=\lfloor x/f_{a}\rfloor 2^{r}+c_{a}+(x\bmod f_{a})$, where
$c_{a}=\sum_{b\in[0..a)}f_{b}$; the condition determining the number of bits
occupied by $x$ is essentially the same as in the simple rANS from Section
3.1.

More formally, the algorithm for $\mathsf{push}(w,a)$ is as follows. Denote by
$x_{1}$ and $x_{2}$ the values stored in, respectively, the highest
$\lfloor\log f_{a}\rfloor+k+1$ and $\lfloor\log f_{a}\rfloor+k+2$ bits of $w$.
We assume that $x=x_{1}$ if $x_{1}\geq f_{a}2^{k}$, and $x=x_{2}$ otherwise.
Since $2^{\lfloor\log f_{a}\rfloor+k}\leq x_{1}<f_{a}2^{k+1}$ and $x_{2}\leq
2\cdot x_{1}+1$, we have $f_{a}2^{k}\leq x<f_{a}2^{k+1}$. Denote
$\ell=\lfloor\log w\rfloor-\lfloor\log x\rfloor$. Note that $w=x\cdot
2^{\ell}+(w\bmod 2^{\ell})$. The value $w^{\prime}=\mathsf{push}(w,a)$ is
computed as $w^{\prime}=x^{\prime}\cdot 2^{\ell}+(w\bmod 2^{\ell})$ by
replacing the part $x$ of $w$ by $r+k+1$ bits representing a number
$x^{\prime}$ defined as:

$x^{\prime}=\lfloor x/f_{a}\rfloor 2^{r}+c_{a}+(x\bmod f_{a}).$ (10)

Since $f_{a}2^{k}\leq x<f_{a}2^{k+1}$, we have $2^{k}\leq\lfloor
x/f_{a}\rfloor<2^{k+1}$ and, therefore, the number $x^{\prime}$ indeed fits
into $r+k+1$ bits and its highest $(r+k+1)$th bit is 1. The reverse operation
$(w,a)=\mathsf{pop}(w^{\prime})$ producing the old value $w$ and the letter
$a$ from $w^{\prime}$ is straightforward. Given a number $x^{\prime}$, which
occupies $r+k+1$ highest bits of $w^{\prime}$ (i.e., $x^{\prime}=\lfloor
w^{\prime}/2^{\ell}\rfloor$, where $\ell=\lfloor\log w^{\prime}\rfloor-r-k$),
we first determine the letter $a$ by examining to which range
$[c_{a}..c_{a+1})$ the number $x^{\prime}\bmod 2^{r}$ belongs and, then, we
compute $x$ as follows:

$x=\lfloor x^{\prime}/2^{r}\rfloor f_{a}+(x^{\prime}\bmod 2^{r})-c_{a}.$ (11)

Once $x$ is known, we put $w=x\cdot 2^{\ell}+(w^{\prime}\bmod 2^{\ell})$. It
remains to observe that $x^{\prime}>x$ since $x^{\prime}=\lfloor
x/f_{a}\rfloor 2^{r}+(x\bmod f_{a})>\lfloor x/f_{a}\rfloor f_{a}+(x\bmod
f_{a})=x$. Therefore, we have $w_{0}<w_{1}<\cdots<w_{n}$.

Note that, when $k=0$, the described scheme degenerates simply to the ANS
without shuffling.

To estimate the size of the final number $w_{n}$ in bits, we derive by analogy
to (6) and (7) using the condition $x^{\prime}>x$ the following two equations
(here we have $w_{i}=x\cdot 2^{\ell}+\Delta$ and $w_{i+1}=x^{\prime}\cdot
2^{\ell}+\Delta$, where $\Delta\in[0..2^{\ell})$):

$\log
w_{n}=\log\frac{w_{n}}{w_{n-1}}+\log\frac{w_{n-1}}{w_{n-2}}+\cdots+\log\frac{w_{1}}{w_{0}}+r+k;$
$\log w_{i+1}-\log w_{i}\leq\log x^{\prime}-\log x.$

From (11), we deduce $\log x\geq\log(\lfloor x^{\prime}/2^{r}\rfloor
f_{a})\geq\log f_{a}+\log(x^{\prime}/2^{r}-1)=\log
f_{a}+\log(x^{\prime}/2^{r})+\log(1-2^{r}/x^{\prime})=\log\frac{f_{a}}{2^{r}}+\log
x^{\prime}+\log(1-2^{r}/x^{\prime})$. Since $2^{r+k}\leq x^{\prime}$, we
derive further $\log(1-2^{r}/x^{\prime})\geq\log(1-1/2^{k})\geq-\frac{\log
e}{2^{k}-1}$. Therefore, we obtain

$\log x^{\prime}-\log x\leq\log\frac{n}{f_{a}}+\frac{\log e}{2^{k}-1}.$

Summing the values $\log x^{\prime}-\log x$ over all $n=2^{r}$ letters of the
sequence, we obtain the following theorem.

######  Theorem 4.

Given a sequence $a_{1},a_{2},\ldots,a_{n}$ of letters from an alphabet
$[0..\sigma)$ such that each letter $a$ occurs in it $f_{a}$ times and
$n=2^{r}$ for an integer $r$, the rANS encoder with fixed accuracy $k\geq 1$
transforms this sequence into a bit string of length

$\sum\limits_{a\in[0..\sigma)}f_{a}\cdot\log\frac{n}{f_{a}}+O\left(\frac{n}{2^{k}}+r\right),$

where the $O\left(\frac{n}{2^{k}}+r\right)$ redundancy term can be bounded by
$\frac{n\log e}{2^{k}-1}+r$.

For completeness, let us briefly describe the standard rANS [12, 14]. The
encoder similarly starts with the number $w_{0}=2^{r}$ and consecutively
computes $w_{1},w_{2},\ldots,w_{n}$ for the sequence
$a_{1},a_{2},\ldots,a_{n}$, where $n=2^{r}$. The encoder maintains a number
$t$ (initially $t=r+1$) and, receiving a new letter, it replaces the highest
$t$ bits of the current number $w_{i}$ with a larger value and increases $t$
accordingly. A “renormalization” is sometimes performed by reducing the value
$t$ in order to contain numbers within a range fitting into a machine word.
More precisely, receiving a letter $a=a_{i+1}$, the encoder takes the value
$x$ stored in the $t$ highest bits of $w_{i}$ (i.e., $w_{i}=x\cdot
2^{\ell}+\Delta$, where $\ell=\lfloor\log w_{i}\rfloor+1-t$ and
$\Delta\in[0..2^{\ell})$), calculates a number $x^{\prime}$ by formula (10),
and replaces $x$ with $x^{\prime}$, thus producing $w_{i+1}=x^{\prime}\cdot
2^{\ell}+\Delta$. After this, the value $t$ is increased by $\lfloor\log
x^{\prime}\rfloor-\lfloor\log x\rfloor$. Once $t$ is larger than a fixed
threshold $T$, it is decreased but the resulting $t$ should be larger than
$r$. Usually, for performance reasons, encoders decrease $t$ by a multiple of
8 or 16: $t=r+1+((t-r-1)\bmod b)$, where $b=8$ or $b=16$. Implementations
maintain the $t$-bit number $x$, assigning $x=x^{\prime}$ after processing
each letter, and the decreased number of bytes from $x$ are “dumped” into an
external stream. The decoder executes the same operations but in the reverse
order computing $x$ from $x^{\prime}$ as in (11).

The analysis of this rANS variant is not in the scope of the present paper;
see [12, 22].

#### Implementation notes

In our experiments the described rANS encoder with fixed accuracy $k=3$ was
1.8 times slower than the tANS encoder implemented by Collet [7] and had
approximately the same compression rate.222In [16] Giesen showed that
interleaving streams can significantly speed up the rANS. We did not use this
trick, however, because Collet’s tANS does not use it either, though we
believe that tANS can utilize this technique too, albeit less efficiently. It
is unsurprising since the inner encoding loop of tANS computing (2)
essentially consists of just a couple of accesses to tables stored in the L1
cache. However, the rANS with fixed accuracy is faster than one could have
expected from the standard rANS. The key feature that allows the speed boost
is that the operation of division $\lfloor x/f_{a}\rfloor$ in (10) guarantees
that its result is in the range $[2^{k}..2^{k+1})$. Therefore, the division
can be executed by simpler instructions in a branchless code: we used
arithmetic and bit operations and the instruction cmov from x86 (it is also
possible to use only arithmetic and bit instructions). The code, however,
turns out to be quite cumbersome, which noticeably diminishes the benefits of
the division-free branchless loop.

Denote $R=r+k$. The main loop of the encoder calls the function
$\mathsf{encode}$ from Algorithm 2 consecutively for the letters
$a_{1},a_{2},\ldots,a_{n}$ in the encoded sequence. The function receives as
its parameters an $(R+1)$-bit number $w$ and a letter $a$. The function stores
some lowest bits of $w$ in an external storage and returns an $(R+1)$-bit
value $x^{\prime}$ computed as in (10) (details follow). The parameter $w$ is
actually an $(R+1)$-bit number $x^{\prime}$ produced by the previous call to
the function $\mathsf{encode}$ in the encoding loop; the first call receives
$w=2^{R}$.

Algorithm 2 The encoding function of rANS with fixed accuracy $k=3$.

1:function $\mathsf{encode}$($w,a$) $\triangleright$ rANS with fixed accuracy
$k=3$

2: $(c_{a},f_{a},d)=\mathsf{table}[a];$ $\triangleright$
$d=(t\mathrel{\small{\mathtt{<<}}}(R+1))-(f_{a}\mathrel{\small{\mathtt{<<}}}(t+k))$,
where $t=r-\lfloor\log f_{a}\rfloor$

3: $s=(w+d)\mathrel{\tt\mathtt{>>}}(R+1);$ $\triangleright$ Collet’s trick

4: $\mathsf{outputBits}(w,s);$ $\triangleright$ output $s$ lowest bits of $w$
into an external storage

5: $x=w\mathrel{\tt\mathtt{>>}}s;\;$

6: $x=x-(f_{a}\mathrel{\small{\mathtt{<<}}}3);$

7: $q=0;$

8: for $i=2,1,0$ do $\triangleright$ the loop must be unrolled

9: $x_{0}=x-(f_{a}\mathrel{\small{\mathtt{<<}}}i);\;$

10:
$q=q\mathrel{\mathbf{or}}(x_{0}\mathrel{\mathbf{and}}(1\mathrel{\small{\mathtt{<<}}}(R+i)));$

11: $\mathbf{if}\,(x_{0}\geq 0)\;x=x_{0};\;$ $\triangleright$ it is compiled
into cmov on x86

12: return
$((q\mathrel{\mathbf{xor}}(15\mathrel{\small{\mathtt{<<}}}R))\mathrel{\tt\mathtt{>>}}k)+c_{a}+x;$

Denote $t=r-\lfloor\log f_{a}\rfloor$. The number $x$ occupies either $R-t+1$
or $R-t+2$ highest bits of $w$. The presented pseudocode uses Collet’s trick
[7] to determine $x$ with a branchless code. To this end, the array
$\mathsf{table}$ stores, for each letter $a\in[0..\sigma)$, besides the values
$c_{a}$ and $f_{a}$ the number
$d=(t\mathrel{\small{\mathtt{<<}}}(R+1))-(f_{a}\mathrel{\small{\mathtt{<<}}}(t+k))$.
The trick is that, in this case, the number
$w+d=(t\mathrel{\small{\mathtt{<<}}}(R+1))+w-(f_{a}\mathrel{\small{\mathtt{<<}}}(t+k))$
contains in its highest bits $R+1,R+2,\ldots$ either the number $t$ or $t-1$
depending on whether $w\geq(f_{a}\mathrel{\small{\mathtt{<<}}}(t+k))$ or not.
Therefore, $x=w\mathrel{\tt\mathtt{>>}}s$, where
$s=(w+d)\mathrel{\tt\mathtt{>>}}(R+1)$.

The code in lines 6–11 accumulates the quotient $\lfloor x/f_{a}\rfloor$ in
the variable $q$ and the remainder $x\bmod f_{a}$ in the variable $x$. It is
done by subtracting the numbers $f_{a}\mathrel{\small{\mathtt{<<}}}i$, for
$i=3,2,1,0$, from $x$, thus, reconstructing $q$ bit by bit; note, however,
that the bits in $q$ are inverted and, hence, in the end we have to perform
xor with $15$ ($1111_{2}$ in binary).

The standard rANS has a couple of advantages over tANS in some use cases [16]:
it does not require a table of size $2^{r}$ like tANS and, hence, is more
convenient for the (pseudo) adaptive mode when the table of frequencies is
sometimes rebuilt during the execution of the encoder; due to this less heavy
use of memory, the rANS might be better for interleaving several streams of
data and utilizes more efficiently the instruction-level parallelism for this
task. For these reasons, the rANS was used in some high performance
compressors [16]. The described rANS with fixed accuracy shares the same good
features of the standard rANS plus the described above benefits of the
controlled division. In addition, we believe that the rANS with fixed accuracy
can potentially have more efficient hardware implementations using a
parallelization for the computation of the division, which is possible since
the resulting quotient is in a small range $[2^{k}..2^{k+1})$.

##  6 Conclusion and Open Problems

Theorems 1 and 3 describe the tight asymptotic behaviour of the redundancy for
the tANS. We believe that Theorem 4, albeit not complemented with a lower
bound, is asymptotically tight too. However, it is open to provided a series
of examples supporting this claim. A number of other problems listed below
still remain open too.

(i) The main remaining open problem concerning ANS encoders, as we see it, is
to construct a genuine FIFO encoder with the same performance characteristics
as tANS or rANS. The known ANS variants work as stacks (LIFO) while it is more
natural and, in some scenarios, preferable to have an encoder that acts as a
queue, like the arithmetic coding that fulfils this requirement but is
noticeably worse than ANS in performance terms. For the same reason, the
current ANS variants are not suitable enough for the adaptive encoding when
frequencies of letters change as the algorithm reads the sequence from left to
right (however, the ANS can be applied for a pseudoadaptive mode when the
input sequence is split into chunks and the frequencies change after a whole
chunk is processed; the rANS is primarily used for this purpose since it
requires less tables to rebuild [16]).

(ii) Duda’s precise initialization and its simplified variant from Algorithm 1
are not particularly suitable for practice due to the overhead incurred by
operations on the priority queue and by floating point operations. Therefore,
usually they are replaced with heuristics. An implementation of a fast and
simple initialization method with good guarantees sufficient for Theorem 1 is
an open problem.

(iii) The constants in our lower and upper bounds in Theorems 1 and 3 do not
coincide and it remains open to find a tight constant for the tANS redundancy
term. We believe also that the $r$-bit redundancy produced by the initial
state $w_{0}$ of the encoder can be somehow reduced too by slightly modifying
the scheme. Clearly, one can omit the trailing zeros in the bit representation
of the resulting number $w_{n}$ but it is not enough to get rid of the $r$-bit
redundancy entirely.

(iv) Another problem that can be addressed is the encoding of the table of
frequencies (see [13]). We are not aware of a suitable lower bound like the
entropy formula that would include both the encoded sequence and the table of
frequencies. We believe that such a formula could be derived by analyzing
logarithms of multinomial coefficients and it is likely that the formula will
confirm that the current simple methods for encoding the frequency table are
close to optimal.

(v) We believe that the implementation of the rANS with fixed accuracy
presented in Algorithm 2 is not satisfactory and can be improved. The issue is
that it uses too many instructions and the cmov instructions, in particular,
which are relatively slow. A solution could be in precomputing some numbers
(akin to numbers $d$ in Collet’s trick) that would help to speed up the
computations.

(vi) In practice, for performance reasons, the empirical probabilities of
letters in the input sequence are usually approximated with probabilities of
the form $f/2^{r}$. Due to Theorem 2, the redundancy incurred by these
approximations can be (at least partially) estimated using the
Kullback–Leibler distance. The problem of the choice for the approximations in
practice is not so trivial and can be studies further; see [26].

## References

  * [1] Apple LZFSE compressor, https://github.com/lzfse/lzfse, accessed: 07.01.2022.
  * [2] J. Alakuijala, R. van Asseldonk, S. Boukortt, M. Bruse, I.-M. Comşa, M. Firsching, T. Fischbacher, E. Kliuchnikov, S. Gomez, R. Obryk, et al., JPEG XL next-generation image compression architecture and coding tools, in: Applications of Digital Image Processing XLII, vol. 11137, International Society for Optics and Photonics, 2019.
  * [3] T. Alonso, G. Sutter, J. E. L. De Vergara, LOCO-ANS: An optimization of JPEG-LS using an efficient and low-complexity coder based on ANS, IEEE Access 9 (2021) 106606–106626.
  * [4] I. Blanes, M. Hernandez-Cabronero, J. Serra-Sagrista, M. W. Marcellin, Redundancy and optimization of tANS entropy encoders, IEEE Transactions on Multimedia (2020) 4341–4350.
  * [5] C. Bloom, cbloom rants blog, http://cbloomrants.blogspot.com, accessed: 08.01.2022.
  * [6] Y. Collet, Facebook Zstandard compressor, https://github.com/facebook/zstd, accessed: 07.01.2022.
  * [7] Y. Collet, FSE implementation, https://github.com/Cyan4973/FiniteStateEntropy, accessed: 07.01.2022.
  * [8] Y. Collet, RealTime Data Compression blog, http://fastcompression.blogspot.com, accessed: 08.01.2022.
  * [9] T. M. Cover, J. A. Thomas, Information theory and statistics, Elements of Information Theory 1 (1) (1991) 279–335.
  * [10] D. Dubé, H. Yokoo, Fast construction of almost optimal symbol distributions for asymmetric numeral systems, in: 2019 IEEE International Symposium on Information Theory (ISIT), IEEE, 2019.
  * [11] J. Duda, Asymmetric numeral systems, arXiv preprint arXiv:0902.0271 (2009) 1–47.
  * [12] J. Duda, Asymmetric numeral systems: entropy coding combining speed of huffman coding with compression rate of arithmetic coding, arXiv preprint arXiv:1311.2540 (2013) 1–24.
  * [13] J. Duda, Encoding of probability distributions for asymmetric numeral systems, arXiv preprint arXiv:2106.06438 (2021) 1–5.
  * [14] J. Duda, K. Tahboub, N. J. Gadgil, E. J. Delp, The use of asymmetric numeral systems as an accurate replacement for Huffman coding, in: 2015 Picture Coding Symposium (PCS 2015), IEEE, 2015.
  * [15] F. Giesen, The ryg blog, https://fgiesen.wordpress.com, accessed: 07.01.2022.
  * [16] F. Giesen, Interleaved entropy coders, arXiv preprint arXiv:1402.3392 (2014) 1–16.
  * [17] D. A. Huffman, A method for the construction of minimum-redundancy codes, Proc. Institute of Radio Engineers (IRE) 40 (9) (1952) 1098–1101.
  * [18] G. N. N. Martin, Range encoding: an algorithm for removing redundancy from a digitised message, in: Proc. Institution of Electronic and Radio Engineers International Conference on Video and Data Recording, 1979.
  * [19] A. Moffat, R. M. Neal, I. H. Witten, Arithmetic coding revisited, ACM Transactions on Information Systems 16 (3) (1998) 256–294.
  * [20] A. Moffat, M. Petri, Large-alphabet semi-static entropy coding via asymmetric numeral systems, ACM Transactions on Information Systems 38 (4) (2020) 1–33.
  * [21] J. J. Rissanen, Generalized Kraft inequality and arithmetic coding, IBM Journal of research and development 20 (3) (1976) 198–203.
  * [22] J. Townsend, A tutorial on the range variant of asymmetric numeral systems, arXiv preprint arXiv:2001.09186 (2020) 1–11.
  * [23] N. Wang, C. Wang, S.-J. Lin, A simplified variant of tabled asymmetric numeral systems with a smaller look-up table, Distributed and Parallel Databases 39 (3) (2021) 711–732.
  * [24] H. Yokoo, On the stationary distribution of asymmetric binary systems, in: 2016 IEEE International Symposium on Information Theory (ISIT), IEEE, 2016.
  * [25] H. Yokoo, D. Dubé, Asymptotic optimality of asymmetric numeral systems, in: Proc. 42nd International Symposium on Information Theory and Its Applications (SITA 2019, 2019.
  * [26] H. Yokoo, T. Shimizu, Probability approximation in asymmetric numeral systems, in: Proc. 2018 International Symposium on Information Theory and Its Applications (ISITA 2018), IEEE, 2018.