Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On Unique Decodability   In this paper we propose a revisitation of the topic of unique decodability
and of some fundamental theorems of lossless coding. It is widely believed
that, for any discrete source X, every "uniquely decodable" block code
satisfies E[l(X_1 X_2 ... X_n)]>= H(X_1,X_2,...,X_n), where X_1, X_2,...,X_n
are the first n symbols of the source, E[l(X_1 X_2 ... X_n)] is the expected
length of the code for those symbols and H(X_1,X_2,...,X_n) is their joint
entropy. We show that, for certain sources with memory, the above inequality
only holds when a limiting definition of "uniquely decodable code" is
considered. In particular, the above inequality is usually assumed to hold for
any "practical code" due to a debatable application of McMillan's theorem to
sources with memory. We thus propose a clarification of the topic, also
providing an extended version of McMillan's theorem to be used for Markovian
sources.

20
The categories of this paper are: acc-phys
15
The categories of this paper are: nucl-ex
29
The categories of this paper are: funct-an
18
The categories of this paper are: econ
10
The categories of this paper are: q-bio
3
The categories of this paper are: physics
24
The categories of this paper are: dg-ga
6
The categories of this paper are: astro-ph
13
The categories of this paper are: quant-ph
35
The categories of this paper are: mtrl-th
5
The categories of this paper are: gr-qc
33
The categories of this paper are: plasm-ph
27
The categories of this paper are: comp-gas
25
The categories of this paper are: patt-sol
12
The categories of this paper are: nucl-th
36
The categories of this paper are: cmp-lg