# The Computability of the Channel Reliability Function and Related Bounds
## 2 Definitions and Basic Results
### Basic Concepts of Information Theory
: _For \(R\) with \(C_{0}(W)<R<C(W)\), there exists \(A(W,R),B(W,R)\in\mathbb{R}^{+}\), such that_  
\[2^{-nA(W,R)+o(1)}\leq P_{e,\text{max}}(W,R,n)\leq 2^{-nB(W,R)+o(1)}.\]  
We also define the discrete memoryless channel with noiseless feedback (DMCF). By this, we mean that, in addition to the DMC, there exists a return channel that sends the element of \(\mathcal{Y}\) actually received back from the receiving point to the transmitting point. It is assumed that this information is received at the transmitting point before the next letter is sent and can therefore be used to choose the next letter to be sent. We assume that this feedback is noiseless. We denote the feedback capacity of a channel \(W\) by \(C^{FB}(W)\) and the zero-error feedback capacity by \(C^{FB}_{0}(W)\). [PERSON] proved in [40] that \(C(W)=C^{FB}(W)\)This is, in general, not true for the zero-error capacity. We see that the zero-error (feedback) capacity is related to the reliability function, which we analyze in this paper. It is defined as follows. **Definition 9**. : _The channel reliability function (error exponent) is defined by_  
\[E(W,R)=\limsup_{n\to\infty}-\frac{1}{n}\log_{2}P_{e,\max}(W,R,n). \tag{1}\]  
**Remark 3**. : _We make use of the common convention that \(\log_{2}0:=-\infty\)._  
**Remark 4**. : _We need the \(\limsup\) in (1), because it is not known whether the limit value, i.e., the limits on the right-hand side of (1), exist._  
The first simple observation is that for \(R>C(W)\), we have \(E(W,R)=0\), and if \(C_{0}(W)>0\) for \(0\leq R<C_{0}(W)\), we have \(E(W,R)=+\infty\). One well-known upper bound is the sphere packing bound, which can be defined as follows (see [10]). **Definition 10**. : _Let \(\mathcal{X},\mathcal{Y}\) be finite alphabets, and \((\mathcal{X},\mathcal{Y},W)\) be a DMC. Then, for all \(R\in(0,C(W))\), we define the sphere packing bound function:_  
\[E_{SP}(W,R)=\sup_{\rho>0}\max_{P\in\mathcal{P}(\mathcal{X})}\left(-\log\sum_{ y}\left(\sum_{x}P(x)W(y|x)^{\frac{1}{1+\rho}}\right)^{1+\rho}-\rho R\right). \tag{2}\]  
**Theorem 1** ([PERSON] 1961, [PERSON], [PERSON], [PERSON] 1967). : _For any DMC \(W\) and for all \(R\in(0,C(W))\), it holds that_  
\[E(W,R)\leq E_{SP}(W,R).\]  
The sphere packing upper bound is an important upper bound. The following two lower bounds of the reliability function are also very important. In [41], the random coding bound was defined as follows:  
**Definition 11**. : _Let \(\mathcal{X},\mathcal{Y}\) be finite alphabets, and \((\mathcal{X},\mathcal{Y},W)\) be a DMC. Then, for all \(R\in(0,C(W))\), we define the random coding bound function as_  
\[P_{e}(\mathcal{C}(n),W,m)=\Pr\{d(Y^{n})\
eq m|X^{n}=e(m)\}.\]0 \[P_{e}(\mathcal{C}(n),W,m)=\Pr\{d(Y^{n})\
eq m|X^{n}=e(m)\}.\]1  
**Theorem 2**. : _Let \(\mathcal{X},\mathcal{Y}\) be finite alphabets and \((\mathcal{X},\mathcal{Y},W)\) be a DMC; then,_  
\[P_{e}(\mathcal{C}(n),W,m)=\Pr\{d(Y^{n})\
eq m|X^{n}=e(m)\}.\]2  
[PERSON] also defined in [41] the \(k\)-letter expurgation bound as follows:  
**Definition 12**. : _Let \(\mathcal{X},\mathcal{Y}\) be finite alphabets and \((\mathcal{X},\mathcal{Y},W)\) be a DMC; then, for all \(R\in(0,C(W))\), we define the \(k\)-letter expurgation bound function:_\[P_{e}(\mathcal{C}(n),W,m)=\Pr\{d(Y^{n})\
eq m|X^{n}=e(m)\}.\]3 \[P_{e}(\mathcal{C}(n),W,m)=\Pr\{d(Y^{n})\
eq m|X^{n}=e(m)\}.\]4 (6) \[P_{e}(\mathcal{C}(n),W,m)=\Pr\{d(Y^{n})\
eq m|X^{n}=e(m)\}.\]5 (7) \[P_{e}(\mathcal{C}(n),W,m)=\Pr\{d(Y^{n})\
eq m|X^{n}=e(m)\}.\]6  
**Theorem 3**. : _Let \(\mathcal{X},\mathcal{Y}\) be finite alphabets and \((\mathcal{X},\mathcal{Y},W)\) be a DMC. Then, for all \(R\in(0,C(W))\), we have_  
\[P_{e}(\mathcal{C}(n),W,m)=\Pr\{d(Y^{n})\
eq m|X^{n}=e(m)\}.\]7  
The inequality in (9) follows from [PERSON]'s lemma. The smallest value of \(R\), at which the convex curve \(E_{SP}(W,R)\) meets its supporting line of slope -1, is called the critical rate and is denoted by \(R_{crit}\)[9]. For the certain interval \([R_{crit},C]\), the random coding lower bound corresponds to the sphere packing upper bound.