Type is all you need

• Introduction
• Definitions
• Rate of Constant Composition Code
• Error Exponent of Constant Composition Code
  • Lower Bound
  • Upper Bound
• Conclusion

Introduction

There is a surprising result from Imre Csiszar’s Coding Theorems for Discrete Memoryless Systems which states the following: For any discrete memoryless channels, as long as the codewords all belong to some type class, an upperbound on the rate of the code can be established that depends only on the type. This result is significant for a variety of researches and here I attempt to demonstrate it by simplifying the proofs in the book. Note that a basic understanding of information theory is required.

Definitions

For any discrete set $\mathcal{X}$, and for $n\in \mathbb{N}$, sequence of length $n$ is defined as $\mathbf{x}\triangleq (x_1,\dots ,x_n)\in {\mathcal{X}}^n$. Type, which is the empirical distribution of a sequence is defined as ${\hat{p}}_{\mathbf{x}}(x)=\frac{N\left(x|\mathbf{x}\right)}{n}=\frac{1}{n}\sum _{i=1}^n\mathbf{1}\{x_i=x\}$. For any type $P$ , type class ${\mathcal{T}}_P^n$ is defined as the set of all sequence $x\in {\mathcal{X}}^n$ such that ${\hat{p}}_{\mathbf{x}}(x)=P$. $\mathbb{I}(P_X,W_{Y|X})$ is the mutual information between $X$ and $Y$ when $X$ ~ $P_X$ and $Y$ ~ $\sum _x{P}_X(x)W_{Y|x}$ , where $W_{Y|x}$ is a conditional distribution on $Y\in \mathcal{Y}$ given $x\in \mathcal{X}$. Message is defined as $m\in [1;|\mathcal{M}|]$ with cardinality of message set as $|\mathcal{M}|$. Note that there is an inconsistency with the way I defined message $m$, unlike $\mathbf{x},\mathbf{y}$, exceptionally, lowercase unbold letter is used to represent a message sequence $m$ and set $\mathcal{M}$ is used to represent message sequence of length $k$. Notice that we use base $e$ log for this blog.

Rate of Constant Composition Code

We attempt to show the following:

For arbitrary $ϵ,\tau \in (0,1)$, if $(f,\psi )$ is an $(n,ϵ)$-code for some discrete memoryless channel $W$ such that all codewords belong to ${\mathcal{T}}_P^n$, then the rate of the code is bounded as:

$$\begin{array}{}\text{(1)}& R<\mathbb{I}(P,W)+2\tau \end{array}$$

The outline of the proof is the following: By fixing some type $P$ such that all codewords belong the typeclass, we construct maximal code and find lower bound on the cardinality of message set by considering the conditional typicality of received codewords. Thus an upper bound on the rate can be as a function of the conditional mutual information on type $P$.

Proof:

Let ${\mathcal{X}}^n$ and ${\mathcal{Y}}^n$ be two finite sets of input and output codewords. Define a stochastic matrix $W:\mathcal{X}\to \mathcal{Y}$, whose entries $W(y|x)$ should be interpreted as conditional probability mapping of every state of $\mathcal{X}$ to every state of $\mathcal{Y}$. Thus, $n$ channel use can be written as $W^n:{\mathcal{X}}^n\to {\mathcal{Y}}^n$. Given a channel $W$, a code for channel can be uniquely specified by any encoder/decoder pair $(f:\mathcal{M}\to {\mathcal{X}}^n,\psi :{\mathcal{Y}}^n\to {\mathcal{M}}^{\prime })$, such as we can define equivalent channel as:

$$T(m^{\prime }|m)\triangleq W(\mathbf{y}={\psi }^{-1}(m^{\prime })|\mathbf{x}=f(m)).$$

The probability of erroneous decoding of message $m$ can be now defined as:

$$e_m=e_m(W,f,\psi )\triangleq {\cup }_{m^{\prime }\ne m}T(m^{\prime }|m)=1-T(m|m).$$

The channel coding problem is essentially the task to make $|\mathcal{M}|$ as large as possible while keeping the maximum probability of error $e=\underset{m\in \mathcal{M}}{\max }{e}_m$ as low as possible. We will focus solely on discrete memoryless channel defined as $W^n(\mathbf{y}|\mathbf{x})=\prod _{i=1}^{n}W(y_i|x_i).$ Thus, an $n$-length block code with maximum probability of error bounded as $e(W_n,f,\psi )\le ϵ$ will be called an $(n,ϵ)$-code.

A set $\mathbb{B}\subset {\mathcal{Y}}^n$ is an $\eta$-image ($\eta \in (0,1]$) of a set $\mathbb{A}\subset {\mathcal{X}}^n$ over $W$ if $W(\mathbb{B}|\mathbf{x})\ge \eta \mathrm{\forall }\mathbf{x}\in \mathbb{A}$ , which is to say for every element in $\mathbb{B}$, the probability of the event associated with the element is higher than $\eta$ conditioned on all possible $\mathbf{x}\in \mathbb{A}$. Define the minimum cardinality of such $\eta$-image as:

$$g_W(\mathbb{A},\eta )=\underset{\mathbb{B}}{\min }|\mathbb{B}|.$$

Let $(f,\psi )$ be an $(n,ϵ)$-code satisfying $f(m)\in \mathbb{A}\subset {\mathcal{T}}_P^n$ (all codewords generated by encoder $f$ from a message belong to the same type class of type $P$) and ${\psi }^{-1}(m)\subset {\mathcal{T}}_W^n(f(m))$ (if message $m$ is received at decoder, the mapping of $\psi :\mathcal{M}\to {\mathcal{Y}}^n$ belongs to the conditional type class of $W_{Y|X}$ given $P_X$).

Thus, we can define $\mathbb{B}$ as $\mathbb{B}\triangleq {\cup }_{m\in \mathcal{M}}{\psi }^{-1}(m),$ which is to say set $\mathbb{B}$ is union of all possible received codewords such that the decoding outcome is of $m\in \mathcal{M}$. In other words, using graphical representation, we say that $\mathbb{B}$ is a union of hamming spheres of all possible codewords. Now we further restrict $(f,\psi )$ to be an $(n,ϵ)$ maximal code, meaning that no extension on the code can be possible. With this definition, note that if we have a non-zero probability of $W^n({\mathcal{T}}_W({\mathbf{x}}^{\prime })-\mathbb{B}|{\mathbf{x}}^{\prime })\ge 1-ϵ,$ then the code is no longer maximal, as essentially we can add a new message $m^{\prime }$ with codeword $f(m^{\prime })={\mathbf{x}}^{\prime }$ whose hamming sphere exists outside of $\mathbb{B}$. Thus, it is necessary for maximal code that

$$W^n({\mathcal{T}}_W(\mathbf{x})-\mathbb{B}|\mathbf{x})<1-ϵ\mathrm{\forall }\mathbf{x}\in \mathbb{A}.$$

Since provided for all $n\ge n_0(|\mathcal{X}|,|\mathcal{Y}|,\tau )$ (which is just a fancy way to say $n$ is sufficiently long depending on $|\mathcal{X}|,|\mathcal{Y}|,\tau$). By the definition of typicality, $W^n({\mathcal{T}}_W(\mathbf{x})|\mathbf{x})\ge 1-\tau \mathrm{\forall }\mathbf{x}\in \mathbb{A}$ , it follows that $W^n(\mathbb{B}|\mathbf{x})>ϵ-\tau \mathrm{\forall }\mathbf{x}\in \mathbb{A}$, and therefore by definition $|\mathbb{B}|\ge g_{W^n}(\mathbb{A},ϵ-\tau )$. On the other hand, by Asymptotic Equipartition Property on conditional type, we have $|\mathbb{B}|\le |\mathcal{M}|e^{n(H(W|P)+\tau )}$. The following two results are thus immediate:

$$|\mathcal{M}|\ge g_{W^n}(\mathbb{A},ϵ-\tau )e^{-n(H(W|P)+\tau )},$$ $$\frac{1}{n}\log g_{W^n}({\mathcal{T}}_P,ϵ-\tau )\ge H(\mathcal{Y})-\tau .$$

Now, let ${\mathbb{B}}^{\prime }\subset \mathcal{Y}$ be an $(ϵ+\tau )$-image of ${\mathbb{A}}^{\prime }\subset \mathbb{A}$ for which $|{\mathbb{B}}^{\prime }|=g_{W^n}({\mathbb{A}}^{\prime },ϵ+\tau )$, since $e_m=1-W^n({\psi }^{-1}(m)|f(m))\le ϵ$, we have $W^n({\mathbb{B}}^{\prime }\cap {\psi }^{-1}(m)|f(m))\ge \tau$ for every $m:{\psi }^{-1}(m)\in {\mathbb{A}}^{\prime }$. We also know that if $X\subset {\mathcal{X}}^n$, $P^n(X)\ge \eta$, then $\frac{1}{n}\log |X|\ge H(P)-{ϵ}_n$, and we can apply this result to conclude $|{\mathbb{B}}^{\prime }\cap {\psi }^{-1}(m)|\ge e^{n(H(W|P)-\tau )}$, and it follows that

$$g_{W^n}({\mathbb{A}}^{\prime },ϵ+\tau )=|{\mathbb{B}}^{\prime }|\ge \sum _{m:{\psi }^{-1}(m)\in {\mathbb{A}}^{\prime }}|{\mathbb{B}}^{\prime }\cap {\psi }^{-1}(m)|\ge |{\mathcal{M}}^{\prime }|e^{n(H(W|P)-\tau )},$$

where ${\mathcal{M}}^{\prime }=\{m:{\psi }^{-1}(m)\in {\mathbb{A}}^{\prime }\}$. Since ${\mathbb{A}}^{\prime }\subset \mathbb{A}$, we have

$$\frac{1}{n}\log |{\mathcal{M}}^{\prime }|<\frac{1}{n}\log g_{W^n}(\mathbb{A},ϵ+\tau )-H(W|P)-\tau .$$

Finally, note that since

$$|{\mathbb{B}}^{\prime }|=g_{W^n}({\mathbb{A}}^{\prime },ϵ+\tau )\le g_{W^n}(\mathbb{A},ϵ+\tau )\le e^{n(H(W)+\tau )},$$

we finally arrive at the result, where note that the left hand side of the equation is the rate.

$$\frac{1}{n}\log |{\mathcal{M}}^{\prime }|<\mathbb{I}(P,W)+2\tau$$

Error Exponent of Constant Composition Code

We know that for rate region described by the above result, error tends to zero for sufficiently long $n$, however, it can be shown that even the rate of those convergence depend on type only. We provide both lower and upper bounds on error and error exponent. Note that an upper bound on error is a lower bound on error exponent, since the exponent involves the negative sign.

Lower Bound

The following statement is made in Csiszar’s coding theorems for discrete memoryless channels. For every $R>\lambda >0$ and every type $P$ of sequence in ${\mathcal{X}}^n$, there exists an $n$-length block code $(f,\psi )$ of rate

$$\frac{1}{n}\log |{\mathcal{M}}^{\prime }|\ge R-\delta ,$$

such that all codewords $f(m),m\in {\mathcal{M}}^{\prime }$ are of type $P$ and the error can be bounded as:

$$\begin{array}{}\text{(2)}& e(W^n,f,\psi )\le e^{-n((\underset{V}{\min }D(V||W|P)+|\mathbb{I}(P,V)-R{|}^{+})-\delta )}.\end{array}$$

Here, $E_r(R,P,W)=\underset{V}{\min }D(V||W|P)+|\mathbb{I}(P,V)-R{|}^{+}$ is known as random coding error exponent of channel $W$ with input distribution of type $P$, and $V:\mathcal{X}\to \mathcal{Y}$ ranges over all channels.

My opinion is that Csiszar’s proof is very obscure and therefore I will restate the main results using Gallagher’s proof.

Assume we have a fixed composition code of composition $Q$, and we define the typical set ${\mathcal{T}}_{Q_X}^n$ to be its composition. In other words

$$|{\mathcal{T}}_{Q_X}^n|=\exp \{n[H(Q)-{\delta }_n]\}$$

for ${\delta }_n\to 0,n\to \mathrm{\infty }$. The probability of decoding error for the $m$-th codeword in a code $\mathcal{C}$ is defined using maximum likelihood decoder as

$$P_e=\underset{m}{\max }{P}_{e,m}$$

We know that a code $|\mathcal{C}|=M$ can be expurgated into a code of size $\frac{M}{2}$ by removing the half worst performing codewords, with a resulting maximum probability of error at most twice the average of original code. Hence, the distinction between using maximum or average error probability is minimal. If we define ${\mathcal{T}}_{Q_X{\hat{P}}_{Y|X}}^n$ to be the joint type of $X,Y$, then we have

$$|{\mathcal{T}}_{Q_X{\hat{P}}_{Y|X}}^n|=\exp \{n[H(Q,\hat{P})-{\delta }_n]\}.$$

For a given input $\mathbf{x}$ of type $Q$, we have the conditional type in $\mathbf{y}$ such that $(x,y)\in {\mathcal{T}}_{Q_X{\hat{P}}_{Y|X}}^n$ as ${\mathcal{T}}_{{\hat{P}}_Y|Q_x}^n$, then assume that $\mathbf{x}\in {\mathcal{T}}_{Q_X}^n$ and ${\mathbf{x}}^{\prime }\in {\mathcal{T}}_{Q_X}^n$, the same permutation on $\mathbf{x}$ that results in ${\mathbf{x}}^{\prime }$ can permute $\mathbf{y}$ into $\mathbf{y}\in {\mathcal{T}}_{{\hat{P}}_Y|Q_{x^{\prime }}}^n$ it can be seen that $|{\mathcal{T}}_{{\hat{P}}_Y|Q_x}^n|=|{\mathcal{T}}_{{\hat{P}}_Y|Q_{x^{\prime }}}^n|\mathrm{\forall }\mathbf{x}\in {\mathcal{T}}_{Q_X}^n$. Hence we can conclude

$$|{\mathcal{T}}_{{\hat{P}}_Y|Q_x}^n|=\frac{|{\mathcal{T}}_{Q_X{\hat{P}}_{Y|X}}^n|}{|{\mathcal{T}}_{Q_X}^n|}.$$

Note that the left hand side is the conditional type, for instance $|{\mathcal{T}}_{{\hat{P}}_Y}^n|=\frac{|{\mathcal{T}}_{Q_X{\hat{P}}_{Y|X}}^n|}{|{\mathcal{T}}_{Q_X}^n|}$ is not true when $X$ and $Y$ are correlated sources. The immediate result is

$$|{\mathcal{T}}_{{\hat{P}}_Y|Q_x}^n|=\exp \{n[H(Q,\hat{P})-H(Q)-{\delta }_n]\},$$

which isn’t anything new. But this gives us an operational interpretation on the elements of ${\mathcal{T}}_{{\hat{P}}_Y|Q_x}^n$ as the set of output codewords arising from $\mathbf{x}$ under a given noise composition $\hat{P}$.

Now let’s introduce the discrete memoryless channel defined by some transition matrix $P$, the following relation can be established:

$$P(\mathbf{y}|\mathbf{x})=P(y_1|x_1)\dots P(y_n|x_n)=\exp \left\{n[\sum _{k,j}Q(x_k)\hat{P}(y_j|x_k)\ln P(y_j|x_k)]\right\}.$$

Note that we use $\mathrm{Pr}(.)$ to mean general probability and the left hand side of the above equation means the probability of receiving $\mathbf{y}\in {\mathcal{T}}_{{\hat{P}}_Y|Q_x}^n$ given that $\mathbf{x}\in {\mathcal{T}}_{Q_X}^n$ is transmitted over a channel with transition matrix $P$. Thus,

$$P[\mathbf{y}\in {\mathcal{T}}_{{\hat{P}}_Y|Q_x}^n|\mathbf{x}]=|{\mathcal{T}}_{{\hat{P}}_Y|Q_x}^n|P(\mathbf{y}|\mathbf{x})=\exp \{n[\sum _{k,j}Q(x_k)\hat{P}(y_j|x_k)\ln \frac{P(y_j|x_k)}{\hat{P}(y_j|x_k)}]-{\delta }_n\}.$$

This can be equivalently written as:

$$\begin{array}{}\text{(3)}& P[\mathbf{y}\in {\mathcal{T}}_{{\hat{P}}_Y|Q_x}^n|\mathbf{x}]=\exp \{-n[D(\hat{P}||P|Q)+{\delta }_n]\},\end{array}$$

where $D(\hat{P}||P|Q)=\sum _{k,j}Q(x_k)\hat{P}(y_j|x_k)\ln \frac{\hat{P}(y_j|x_k)}{P(y_j|x_k)}$ and we have dropped the subscripts on probability for clarity.
The next step of argument requires a new definition, define $Y\sim Q_X\circ P_{Y|X}\triangleq \sum _x{Q}_X(x){\hat{P}}_{Y|X}(y|x)$, note that this is different from the definition of joint type as the summation are over both $X$ and $Y$. The operational meaning is the output composition. Assume we have some noise composition $\hat{P}$ for which $|{\mathcal{T}}_{{\hat{P}}_Y|Q_x}^n|\ge \frac{2}{|\mathcal{C}|}|{\mathcal{T}}_{Q_X\circ P_{Y|X}}^n|$ (it will become clear what this assumption is made). Since the total output composition cardinality is $|{\mathcal{T}}_{Q_X\circ P_{Y|X}}^n|$, and there are a total of $|\mathcal{C}|$ codewords, hence the average message $m$ has $\frac{|{\mathcal{T}}_{Q_X\circ P_{Y|X}}^n|}{|\mathcal{C}|}$ corresponding outputs. This is equivalent to say that there exists a $m$ for which at most $\frac{|{\mathcal{T}}_{Q_X\circ P_{Y|X}}^n|}{|\mathcal{C}}|$ outputs are decoded into $m$. Now it becomes clear that the assumption $|{\mathcal{T}}_{{\hat{P}}_Y|Q_{x_m}}^n|\ge \frac{2}{|\mathcal{C}|}|{\mathcal{T}}_{Q_X\circ P_{Y|X}}^n|$ means there exists some $m$ such that half of $|{\mathcal{T}}_{{\hat{P}}_Y|Q_{x_m}}^n|$ are not decoded into $m$. Recall that the error is defined as the maximum over all realizations of codewords, since for some $m$, half of the decoding results in error, we have:

$$\begin{array}{}\text{(4)}& P_e\ge \frac{1}{2}P[{\mathcal{T}}_{{\hat{P}}_Y|Q_x}^n|\mathbf{x}].\end{array}$$

The graphical understanding of this result is that if the spheres of output sets ${\mathcal{T}}_{{\hat{P}}_Y|Q_x}^n$ are too large, they can not be packed disjointly into the output composition set ${\mathcal{T}}_{Q_X\circ P_{Y|X}}^n$, which means decoding error.

This is reason why this lower bound on error exponent is called sphere packing bound, and here we present a bit of a digression to explore this interpretation. The information-theoretic understanding of this packing can be understood using the following formula:

$$\frac{|{\mathcal{T}}_{Q_X\circ P_{Y|X}}^n|}{|{\mathcal{T}}_{{\hat{P}}_Y|Q_x}^n|}=\exp \{n[\sum _{k,j}Q(x_k)\hat{P}(y_j|x_k)\ln \frac{\hat{P}(y_j|x_k)}{\sum _{k}Q(x_k)\hat{P}(y_j|x_k)}]-{\delta }_n\}.$$

Now, the term in the exponent should be familiar, if we expand the mutual information between $X$ and $Y$, given that they are of composition $Q$ and $\hat{P}$:

$$\mathbb{I}(Q_X,{\hat{P}}_{Y|X})=\sum _{x}Q(x_k)\sum _y\hat{P}(y_i|x_k)\ln \frac{\hat{P}(y_i|x_k)}{\hat{P}(y_j)},$$

from which it should be obvious that

$$\frac{|{\mathcal{T}}_{Q_X\circ P_{Y|X}}^n|}{|{\mathcal{T}}_{{\hat{P}}_Y|Q_x}^n|}=\exp \{n[\mathbb{I}(Q_X,{\hat{P}}_{Y|X})-{\delta }_n]\}$$

Thus the assumption we made earlier $|{\mathcal{T}}_{{\hat{P}}_Y|Q_{x_m}}^n|\ge \frac{2}{|\mathcal{C}|}|{\mathcal{T}}_{Q_X\circ P_{Y|X}}^n|$ can be written as $R\ge \mathbb{I}(Q_X,{\hat{P}}_{Y|X})+{\delta }_n+\frac{\ln 2}{n}$

Now back to the main argument, combining equation (3) and (4), we see that the error is bounded as:

$$P_e\ge \exp \{-n[E_{sp}(R+{\delta }_n,Q_X,P_{Y|X})-{\delta }_n]\},$$

where the sphere packing error exponent is

$$E_{sp}(R,Q_X,P_{Y|X})=\underset{\hat{P}:\mathbb{I}(Q_X,{\hat{P}}_{Y|X})\le R}{\min }D(\hat{P}||P|Q).$$

The condition $\mathbb{I}(Q_X,{\hat{P}}_{Y|X})\le R$ seems counterintuitive, but note that $\hat{P}$ is not the channel transition matrix, it can be seen that if $\mathbb{I}(Q_X,P_{Y|X})\le R$ , $E_{sp}(R,Q_X,P_{Y|X})$ is zero, because we can choose $\hat{P}=P$ , since $R\le \mathbb{I}(Q_X,P_{Y|X})$ is required to have any rate, the violation of which means error never decreases with zero exponent.

Upper Bound

Next, we try to establish the upper bound on the error exponent for constant composition codes. Now we define a new typical set ${\mathcal{T}}_{Q_X|P_y^{\prime }}^n$, which the set of all input codewords in composition $Q$ that can be decoded into $\mathbf{y}$ in the presence of some noise composition $P^{\prime }$. For some message $m$, codeword ${\mathbf{x}}_m$ and received output $\mathbf{y}$, there is an error if there is some other codeword ${\mathbf{x}}_{m^{\prime }}$ in the set ${\mathcal{T}}_{Q_X|P_y^{\prime }}^n$ such that $P(\mathbf{y}|{\mathbf{x}}_{m^{\prime }})\ge P(\mathbf{y}|{\mathbf{x}}_m)$, which is to say

$$\begin{array}{}\text{(5)}& \exp \left\{n[\sum _{k,j}Q(x_k)P^{\prime }(y_j|x_k)\ln P(y_j|x_k)]\right\}\ge \exp \left\{n[\sum _{k,j}Q(x_k)\hat{P}(y_j|x_k)\ln P(y_j|x_k)]\right\}.\end{array}$$

Define $P(\hat{P})$ as the set of noise compositions $P^{\prime }$ such that (5) is satisfied, the error probability is then

$$Pr(\mathrm{error}|m,{\mathbf{x}}_m,\mathbf{y})\le \sum _{m^{\prime }\ne m}\sum _{P^{\prime }\in P(\hat{P})}Pr[{\mathbf{x}}_{m^{\prime }}\in {\mathcal{T}}_{Q_X|P_y^{\prime }}^n].$$

Given that $m^{\prime }$ is randomly selected out of ${\mathcal{T}}_{Q_X}^n$, we have

$$Pr[{\mathbf{x}}_{m^{\prime }}\in {\mathcal{T}}_{Q_X|P_y^{\prime }}^n]=\frac{|{\mathcal{T}}_{Q_X{P}_{Y|X}^{\prime }}^n|}{|{\mathcal{T}}_{Q_X}^n||{\mathcal{T}}_{Q_X\circ P_{Y|X}}^n|}\le \exp \{-n\mathbb{I}(Q_X,P_{Y|X}^{\prime })\}.$$

By type counting lemma, there are fewer than $(n+1{)}^{|\mathcal{X}||\mathcal{Y}|-1}$ joint composition of $Q{P}^{\prime }$ , and there are $|\mathcal{C}|-1=e^{nR}-1$ choices of $m^{\prime }\ne m$ , we bound the error as:

$$Pr(\mathrm{error}|m,{\mathbf{x}}_m,\mathbf{y})\le (e^{nR}-1)(n+1{)}^{|\mathcal{X}||\mathcal{Y}|-1}\underset{P^{\prime }\in P(\hat{P})}{\max }Pr[{\mathbf{x}}_{m^{\prime }}\in {\mathcal{T}}_{Q_X|P_y^{\prime }}^n]\le (n+1{)}^{|\mathcal{X}||\mathcal{Y}|-1}{e}^{-n[\mathbb{I}(Q_X,P_{Y|X}^{\prime })-R]}.$$

Define ${\delta }_n=\frac{|\mathcal{X}||\mathcal{Y}|-1}{n}\ln (n+1)$ , which goes to zero as $n\to \mathrm{\infty }$ , we have

$$Pr(\mathrm{error}|m,{\mathbf{x}}_m,\mathbf{y})\le e^{-n[\mathbb{I}(Q_X,P_{Y|X}^{\prime })-R-{\delta }_n]}.$$

Taking the maximum inside and recall that $P_{e,m}\le \sum _{\hat{P}}Pr(\mathrm{error}|m,{\mathbf{x}}_m,\mathbf{y}\in {\mathcal{T}}_{{\hat{P}}_Y|Q_{x_m}}^n)\exp \{-nD(\hat{P}||P|Q)\},$ and finally we have

$$P_e\le \exp [-n(E_r(R,Q_X,P_{Y|X})-{\delta }_n)],$$

where

$$E_r(R,Q_X,P_{Y|X})=\underset{\hat{P}}{\min }(D(\hat{P}||P|Q)+[\mathbb{I}(Q_X,{\hat{P}}_{Y|X})-R{]}^{+}),$$

is the random coding error exponent, which provides an upper bound on the error exponent of constant composition code. Once again, an upper bound on error is a lower bound on error exponent, since the exponent involves the negative sign. Hence we have the relation

$$E_r(R,Q_X,P_{Y|X})\le E\le E_{sp}(R,Q_X,P_{Y|X})$$

Conclusion

This result is useful in a lot of information-theoretic proofs as the error exponent of constant composition codes is also extensively discussed in literature. More recently, this result proves useful in joint sensing and communication as the sensing capacity is also heavily influenced by the type of the codeword.