Improved Channel Coding Performance Through Cost Variability

Channel coding is a fundamental problem focused on the reliable transmission of information over a noisy channel. Information transmission with arbitrarily small error probability is possible at all rates below the capacity $C$ of the channel, if the number $n$ of channel uses (also called the blocklength) is permitted to grow without bound [1]. At finite blocklengths, there is an unavoidable backoff from capacity due to the random nature of the channel. The second-order coding rate (SOCR) ([2, 3, 4, 5, 6]) quantifies the $O(n^{-1/2})$ convergence to the capacity.

In many practical scenarios, the channel input is subject to some cost constraints which limit the amount of resources that can be used for transmission. With a cost constraint present, the role of capacity is replaced by the capacity-cost function [1, Theorem 6.11]. One common form of the cost constraint is the almost-sure (a.s.) cost constraint ([3, 7]) which bounds the time-average cost of the channel input $X^{n}$ over all messages, realizations of any side randomness, channel noise (if there is feedback), etc.:

where $c(\cdot)$ is the cost function. Under the almost-sure (a.s.) cost constraint, the optimal first-order coding rate is the capacity-cost function, the strong converse holds [1, Theorem 6.11], and the optimal SOCR is also known [3, Theorem 3].

The a.s. cost constraint is quite unforgiving, never allowing the cost to exceed the threshold under any circumstances. Our first result (Theorem 1) shows that the SOCR can be strictly improved by merely allowing the cost to fluctuate above the threshold in a manner consistent with a noise process, i.e., the fluctuations have a variance of $O(1/n)$. Our second result (Theorem 2) shows that the a.s. cost framework does not allow feedback improvement to SOCR for simple-dispersion¹¹1See Definition 1. DMCs. This again contrasts with the scenario where random fluctuations with variance $O(1/n)$ above the threshold are allowed, as shown in [8, Theorem 3]. This highlights the important role cost variability plays in enabling feedback mechanisms to improve coding performance.

These findings raise the question of whether it is necessary to impose a constraint as stringent as (1). Cost constraints in communication systems are typically imposed to achieve goals such as operating circuitry in the linear regime, minimizing power consumption, and reducing interference with other terminals. It is worth noting that these goals do not always necessitate the use of the strict a.s. cost constraint. For example, the expected cost constraint is often used in wireless communication literature (see, e.g., [9, 10, 11, 12]) because it allows for a dynamic allocation of power based on the current channel state. The expected cost constraint bounds the cost averaged over time and the ensemble:

Yet, if the a.s. constraint is too strict, the expectation constraint is arguably too weak. The expectation constraint allows highly non-ergodic use of power, as shown in Section II-A, which is problematic both from the vantage points of operating circuitry in the linear regime and interference management.

The $O(1/n)$ variance allowance is a feature of a new cost formulation, referred to as mean and variance cost constraints in [8]. This formulation replaces (1) with the following conditions:

The mean and variance cost constraints were introduced as a relaxed version of the a.s. cost constraint that permits a small amount of stochastic fluctuation above the threshold $\Gamma$ while providing an ergodicity guarantee. Consider a random channel codebook whose codewords satisfy $(\ref{exp01})$ with equality. For a given input $x^{n}$, define an ergodicity metric $\mathcal{E}_{m}$ as

The definition in $(\ref{h23})$ only penalizes cost variation above the threshold and normalizes by the mean cost $\Gamma$. Let $\alpha>0$ be the desired ergodicity parameter. We say that a transmission $x^{n}$ is $\alpha$-ergodic if $\mathcal{E}_{m}(x^{n})\leq\alpha$. Let $\beta$ be the desired uncertainty parameter. We say that a random codebook is $(\alpha,\beta)$-ergodic if $\mathbb{P}\left(\mathcal{E}_{m}(X^{n})\leq\alpha\right)\geq 1-\beta$, where $X^{n}$ is a random transmission from the codebook.

Under the mean and variance cost formulation, we have $\mathbb{P}\left(\mathcal{E}_{m}(X^{n})\leq\alpha\right)\geq 1-\beta$ if

where we call $n_{c}$ the critical blocklength. Thus, the critical blocklength specifies the minimum blocklength of a channel code for which transmission behaves ergodically with high probability. For fixed $\alpha$, $\beta$, and $\Gamma$, the parameters $n_{c}$ and $V$ are in one-to-one correspondence, so one can view the choice of $V$ in (4) as specifying the critical blocklength. Note that with an expectation-only constraint, we effectively have $V=\infty$, so the transmission is not guaranteed to be ergodic at any blocklength. Furthermore, unlike the expected cost constraint, the mean and variance cost formulation:

• •

  allows for a strong converse [13, Theorem 77], [8],

• •

  allows for a finite second-order coding rate [8],

• •

  does not allow blasting power on errors in the feedback case [14].

The results of this paper also have significance in the context of previous works. Our result in Theorem 2 extends the previously known result that feedback does not improve the second-order performance for simple-dispersion DMCs without cost constraints [4]. It is also similar to the result in [15] that feedback does not improve the second-order performance for AWGN channels.

Random channel coding schemes often use independent and identically distributed (i.i.d.) codewords. It was noted in [16] that the a.s. cost constraint, which is the most commonly considered cost constraint in the context of discrete memoryless channels (DMCs), prohibits the use of i.i.d. codewords. It was shown in [16] that a feedback scheme that uses both i.i.d. and constant-composition codewords leads to an improved SOCR compared to the best non-feedback SOCR achievable under the a.s. cost constraint. Our result in Theorem 2 strengthens the result in [16] by showing that the aforementioned improvement also holds compared to the best feedback SOCR achievable under the a.s. cost constraint.

Let $\mathcal{A}$ and $\mathcal{B}$ be finite input and output alphabets, respectively, of the DMC $W$, where $W$ is a stochastic matrix from $\mathcal{A}$ to $\mathcal{B}$. For a given sequence $x^{n}\in\mathcal{A}^{n}$, the $n$-type $t=t(x^{n})$ of $x^{n}$ is defined as

for all $a\in\mathcal{A}$, where $\mathds{1}(.)$ is the standard indicator function. For a given sequence $x^{n}\in\mathcal{A}^{n}$, we will use $t(x^{n})$ or $P_{x^{n}}$ to denote its type. Let $\mathcal{P}_{n}(\mathcal{A})$ be the set of $n$-types on $\mathcal{A}$. For a given $t\in\mathcal{P}_{n}(\mathcal{A})$, $T^{n}_{\mathcal{A}}(t)$ denotes the type class, i.e., the set of sequences $x^{n}\in\mathcal{A}^{n}$ with empirical distribution equal to $t$. For a random variable $Z$, $||Z||_{\infty}$ denotes its essential supremum (that is, the infimum of those numbers $z$ such that $\mathbb{P}(Z\leq z)=1$). We will write $\log$ to denote logarithm to the base $e$ and $\exp(x)$ to denote $e$ to the power of $x$. The cost function is denoted by $c(\cdot)$ where $c:\mathcal{A}\to[0,c_{\max}]$ and $c_{\max}>0$ is a constant. Let $\Gamma_{0}=\min_{a\in\mathcal{A}}c(a)$. Let $\Gamma^{*}$ denote the smallest $\Gamma$ such that the capacity-cost function $C(\Gamma)$ is equal to the unconstrained capacity. We assume $\Gamma^{*}>\Gamma_{0}$ and $\Gamma\in(\Gamma_{0},\Gamma^{*})$ throughout the paper. For $\Gamma\in(\Gamma_{0},\Gamma^{*})$, the capacity-cost function is defined as

where $c(P):=\sum_{a\in\mathcal{A}}P(a)c(a)$. The function $C(\Gamma)$ is strictly increasing and differentiable [1, Problem 8.4] in the interval $(\Gamma_{0},\Gamma^{*})$. For a given $x^{n}\in\mathcal{A}^{n}$, we define

Let $\Pi_{W,\Gamma}^{*}$ be the set of all capacity-cost-achieving distributions, i.e., the set of maximizing distributions in $(\ref{main_form})$. For any $P^{*}\in\Pi_{W,\Gamma}^{*}$, let $Q^{*}=P^{*}W$ be the marginal distribution on $\mathcal{B}$. Note that the output distribution $Q^{*}$ is always unique, and without loss of generality, $Q^{*}$ can be assumed to satisfy $Q^{*}(b)>0$ for all $b\in\mathcal{B}$ [21, Corollaries 1 and 2 to Theorem 4.5.1].

The following definitions will remain in effect throughout the paper:

We will only focus on simple-dispersion channels for a fixed cost $\Gamma\in(\Gamma_{0},\Gamma^{*})$ and thus define

for any $P^{*}\in\Pi_{W,\Gamma}^{*}$.

With a blocklength $n$ and a fixed rate $R>0$, let $\mathcal{M}_{R}=\{1,\ldots,\lceil\exp(nR)\rceil\}$ denote the message set. Let $M\in\mathcal{M}_{R}$ denote the random message drawn uniformly from the message set.

Given $\epsilon\in(0,1)$, define

where $\bar{P}_{\text{e,fb}}(n,R,\Gamma)$ denotes the minimum average error probability attainable by any random $(n,R,\Gamma)$ code with feedback. Similarly, define

where $\bar{P}_{\text{e}}(n,R,\Gamma)$ denotes the minimum average error probability attainable by any random $(n,R,\Gamma)$ code without feedback. Define $M^{*}_{\text{fb}}(n,\epsilon,\Gamma,V)$ and $M^{*}(n,\epsilon,\Gamma,V)$ similarly for codes with mean and variance cost constraints.

We prove coding performance improvement in terms of the second-order coding rate, although equivalent results in terms of the average error probability improvement can also be shown as in [8, Theorems 1-3]. Let

• •

  $r_{\text{a.s.}}(\epsilon,\Gamma)$ denote the optimal SOCR with the a.s. cost constraint without feedback,

• •

  $r_{\text{a.s.,fb}}(\epsilon,\Gamma)$ denote the optimal SOCR with the a.s. cost constraint with feedback,

• •

  $r_{\text{m.v.}}(\epsilon,\Gamma,V)$ denote the optimal SOCR with the mean and variance cost constraints without feedback and

• •

  $r_{\text{m.v.,fb}}(\epsilon,\Gamma,V)$ denote the optimal SOCR with the mean and variance cost constraints with feedback

for channel codes operating with average error probability of at most $\epsilon\in(0,1)$. In the non-feedback case, $C(\Gamma)$ is the optimal first-order rate for DMCs with the a.s. cost constraint [1, Theorem 6.11] as well as the mean and variance cost formulation [8, Theorems 1 and 2], i.e.,

for all $\epsilon\in(0,1)$. The results $(\ref{str1})$ and $(\ref{str2})$ imply that the strong converse holds. We thus define the second-order rates with respect to the capacity-cost function $C(\Gamma)$ as follows:

For the feedback case, we simply take the convention to define the SOCR with respect to $C(\Gamma)$ as follows:

For the a.s. cost constraint, this convention is justified because from the result in Theorem 2, $C(\Gamma)$ is the optimal first-order rate, in the analogous sense to $(\ref{str1})$, for DMCs with feedback. For DMCs without cost constraints, Shannon [22, Theorem 6] showed that feedback does not increase the capacity.

Since $\mathcal{K}(r,V)$ is a continuous function [8, Lemma 3], it suffices to show that for all $r\in\mathbb{R}$ and $V>0$,

The LHS of $(\ref{bv})$ can be written as

where we used the constraint $\mathbb{E}[\Pi]=r$ to eliminate one of the decision variables.

Assume by contradiction that

for all $\pi\geq r$, $p\in[0,1]$ and $\frac{p}{1-p}(\pi-r)^{2}\leq V$. The assumption $\pi\geq r$ is without loss of generality since one of the two point masses must be greater than or equal to $r$.

If $(\ref{eq})$ holds, then

for all $\pi\geq r$, $p\in[0,1]$ and $\frac{p}{1-p}(\pi-r)^{2}=V$. Since $\pi=r+\sqrt{\frac{V(1-p)}{p}}$ in this case, we must have

for all $p\in[0,1]$.

Consider the function

with domain $p\in[0,1]$. For any $p\in(0,1)$,

In equality $(a)$, we have $r-\sqrt{\frac{Vp}{1-p}}<\tilde{r}<r$ by the mean value theorem. It is easy to see that for sufficiently small $p>0$, the expression in $(\ref{co})$ is negative. Since $f(0)=0$, we have $f(p)<0$ for some $p>0$, which contradicts $(\ref{gp})$.

For any $t\in\mathcal{P}_{n}(\mathcal{A})$, define

For any $0<\gamma\leq\frac{V(\Gamma)}{4|\mathcal{A}|\nu_{\max}}$, define