Source code error bound in the excess rate region

Author

Singh, Samar ; Kambo, N.S.

Volume

23

Issue

1

fYear

1977

fDate

1/1/1977 12:00:00 AM

Firstpage

65

Lastpage

70

Abstract

The problem of encoding a discrete memoryless source with respect to a single-letter fidelity criterion, using a block code of length $n$ and rate $R$ , is considered. The probability of error, $p_{n}(R,D)$ , is defined to be the minimum probability, over all such codes, that the source will generate a sequence which cannot be encoded with distortion $D$ or less. For sufficiently large $R$ , that $p_{n}(R,D)$ decreases doubly exponentially with blocklength, $n$ is shown. It is known that $p_{n}(R,D) = 0$ for some finite $n$ , denoted by $n_{0}(R,D)$ . An upper bound to $n_{0}(R,D)$ is also presented and numerically evaluated. The results derived hold independently of the source statistics. It is shown that a theorem of Omura and Shohara for symmetric sources is a special case of the results herein. Additionally, a useful characterization of $R \\ast (D)$ for row-balanced distortion matrices is obtained.

Keywords

Rate-distortion theory; Block codes; Encoding; Error probability; Mathematics; Probability distribution; Rate-distortion; Research and development; Statistics; Symmetric matrices; Upper bound;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.1977.1055656

Filename

1055656