A Lego-Brick Approach to Coding
for Network Communication

Nadim Ghaddar, Student Member, IEEE,
Shouvik Ganguly, Member, IEEE,
Lele Wang, Member, IEEE,
and Young-Han Kim, Fellow, IEEE
This paper was presented, in part, at the Annual Allerton Conference on Communication, Control, and Computing 2015, the International Symposium on Information Theory (ISIT) 2021, and the Canadian Workshop on Information Theory (CWIT) 2022.
N. Ghaddar is with the Department of Electrical and Computer Engineering, University of California San Diego, La Jolla, CA 92093, USA (e-mail: nghaddar@ucsd.edu).
S. Ganguly is with Samsung Research America, Plano, TX 75023, USA (email<EMAIL_ADDRESS>L. Wang is with the Department of Electrical and Computer Engineering, University of British Columbia, Vancouver, BC V6T1Z4, Canada (email<EMAIL_ADDRESS>Y.-H. Kim is with the Department of Electrical and Computer Engineering, University of California San Diego, La Jolla, CA 92093, USA (email<EMAIL_ADDRESS>
Coding schemes for several problems in network information theory are constructed starting from point-to-point channel codes that are designed for symmetric channels. Given that the point-to-point codes satisfy certain properties pertaining to the rate, the error probability, and the distribution of decoded sequences, bounds on the performance of the coding schemes are derived and shown to hold irrespective of other properties of the codes. In particular, we consider the problems of lossless and lossy source coding, Slepian–Wolf coding, Wyner–Ziv coding, Berger–Tung coding, multiple description coding, asymmetric channel coding, Gelfand–Pinsker coding, coding for multiple access channels, Marton coding for broadcast channels, and coding for cloud radio access networks (C-RAN's). We show that the coding schemes can achieve the best known inner bounds for these problems, provided that the constituent point-to-point channel codes are rate-optimal. This would allow one to leverage commercial off-the-shelf codes for point-to-point symmetric channels in the practical implementation of codes over networks. Simulation results demonstrate the gain of the proposed coding schemes compared to existing practical solutions to these problems.

Network information theory, channel coding, Slepian–Wolf coding, Gelfand–Pinsker coding, Wyner–Ziv coding, Berger–Tung coding, multiple description coding, Marton coding, multiple access channels, cloud radio access networks.

§ INTRODUCTION

Today's modern infrastructure is becoming increasingly interconnected through information networks. Emerging applications in transportation systems, power systems, smart cities, cloud computing and digital healthcare, call for exceptionally efficient coding schemes to process, store and communicate the massive amounts of network data. In practice, the common paradigm of designing coding schemes over networks is to decompose the network into separate point-to-point links, where a point-to-point channel code is used over each link. Despite the practical convenience, such an approach is known to be sub-optimal from an information theoretic perspective, even when each link is utilized at its full capacity.

Network information theory studies the fundamental limits of network communication and the optimal coding schemes that achieve those limits. At a conceptual level, this theory has been hugely successful, with several basic coding schemes that are applicable to a variety of network models, and some optimal in certain special cases. Except for a few simple use cases, however, the coding schemes developed in network information theory have barely had any impact on the design of communication systems over networks. Even basic coding schemes such as Gelfand–Pinsker coding [1], Marton coding [2] and compress-and-forward relaying [3] have not been used in practice in any meaningful manner in the forty years since their inception. The main reason behind this noticeable gap between theory and practice is that most of these coding schemes, albeit being conceptually beautiful, are not in an easily-implementable form, which is exemplified by the ubiquitous use of high-complexity coding techniques such as joint typicality encoding and decoding, and maximum likelihood decoding.

This paper is an attempt to close the aforementioned gap between theory and practice, so that all the beautiful coding schemes in network information theory (e.g., all the ones described in [4]) can be implemented in real systems to their full potential. To achieve this goal, we take a modular approach to transform the conceptual coding schemes into practical implementations. More specifically, we seek to identify basic coding schemes that are designed for one (or more) communication setting and satisfy certain properties, and combine them together to build a more complex coding scheme for a different communication setting. Under such a framework, we ask:

* What are the most primitive properties that the basic coding schemes should satisfy while being versatile in building coding schemes for network communication?

* How can such coding blocks be assembled together in different network communication scenarios?

* How do the performance guarantees and the achievable rate regions translate in different communication settings?

We refer to such an approach to coding as a “Lego-brick approach” and to the basic coding blocks as “Lego bricks”, taking a literal analogy to building complex Lego objects starting from simple components. As we shall see, such a Lego-brick approach to coding allows one to leverage commercial off-the-shelf codes that are designed for single-user symmetric channels (e.g., turbo codes [5], low-density parity-check (LDPC) codes [6, 7, 8], polar codes [9], or even hypothetical codes to be invented in the future) to build practical coding schemes for multi-user communication.

§.§ Related Work

Many attempts to design practical coding schemes for multi-terminal scenarios have closely followed the footsteps of point-to-point channel coding. Polar codes, for example, have been specialized to several problems in network information theory, including, but not limited to, the Slepian–Wolf problem [10], the lossy source coding problem [11], Gelfand–Pinsker problem [12], the multiple description coding problem [13, 14], multiple-access channels [15, 16], broadcast channels [17], interference channels [18], and relay channels [19, 20]. Sparse graph codes with logarithmic check node degrees have also been shown to achieve the optimal rates for various coding problems under maximum likelihood decoding, including the lossy source coding problem [21], the Gelfand–Pinsker problem and the Wyner–Ziv problem [22]. Alternatively, low-density generator-matrix (LDGM) codes were shown to achieve the rate-distortion bound for the lossy source coding problem when optimal encoding is employed [23], and to approach that bound when a variant of the low-complexity belief propagation algorithm is used [24]. Spatial coupling of low-density graph codes was also shown to be useful for approaching the optimal rates of the lossy source coding problem [25] and the Wyner–Ziv and Gelfand–Pinsker coding problems [26] using the belief propagation algorithm with guided decimation. For Gaussian channels with Gaussian state that is known noncausally at the encoder (i.e., the dirty paper coding problem [27]), lattice codes have been shown to achieve capacity [28], and variants of these codes with practical decoders have been proposed in the literature (e.g., [29, 30]). On a separate note, randomly-constructed point-to-point channel codes were shown to be sufficient for achieving optimal rates for network coding problems; for example, random nested linear codes were shown to be optimal for asymmetric channels, Gelfand–Pinkser channels, and general broadcast channels [31], and random point-to-point codes were used in [32] along with rate splitting, block-Markov coding and successive cancellation decoding to achieve the best known achievable rate over interference channels. While these constructions either are specific to certain families of point-to-point channel codes or involve nonconstructive and asymptotic code design, the Lego-brick approach to network coding, which we espouse in this paper, aims to distinguish the sufficient properties that would allow point-to-point channel codes to be used as building blocks in an explicit construction of a coding scheme for a network setting.

Such an approach to coding for network communication is not new in general. In [33], Wyner constructed a Slepian–Wolf code for a doubly symmetric binary source starting from a point-to-point channel code designed for the binary symmetric channel (BSC). The duality between general Slepian–Wolf problems and point-to-point channel coding problems was further explored in [34, 35], where a maximum-likelihood channel decoder was assumed. In [36], linear Slepian–Wolf codes were constructed starting from linear point-to-point channel codes designed for symmetric channels, where the exact relation of the rates and probability of error between the two problems was established. Further, a general method for constructing codes for asymmetric point-to-point channels was described in <cit.>; the coding scheme uses a lossless source code and a channel code designed for a symmetric channel as its constituent building blocks. In [38, 39], codes for general (i.e., possibly asymmetric) channels were constructed using Slepian–Wolf codes, where constrained random number generators were used to construct the encoders and the decoders. Moreover, Marton coding for broadcast channels and successive cancellation decoding of multiple access channels were constructed in [40] starting from point-to-point codes that satisfy some basic properties. In particular, in our recent works of [41] and [42], coding schemes for lossy source coding, asymmetric channels and channels with state were constructed starting from point-to-point channel codes designed for symmetric channels.

§.§ Summary of Proposed Coding Schemes

This paper is an attempt to establish a systematic framework for constructing coding schemes for several problems in network information theory starting from simple building blocks (i.e., Lego bricks). Instead of restricting our attention to a particular channel code, we identify basic properties that point-to-point channel codes should satisfy so that they can be used in the construction of a coding scheme for a given network information theory problem. Under such a framework, we view the channel codes that satisfy those properties as “black boxes” which, when assembled together according to the guidelines that we will present, can be used as building blocks in the implementations of practical low-complexity coding schemes for network communication. The performance of the coding schemes in the new setting is derived in terms of the properties of the constituent point-to-point channel codes. Moreover, the proposed coding schemes can achieve rate regions that are strictly larger compared to the naive approach of coding over the point-to-point links of a network. In particular, we consider the problems of Slepian–Wolf coding [43], lossless and lossy source coding [44, 45], Wyner–Ziv coding [46], asymmetric channel coding [44], Gelfand–Pinkser coding [1], coding for multiple access channels [47], Marton coding for broadcast channels [2],  Berger–Tung coding for distributed lossy compression [48], multiple description coding [49], and coding for cloud radio access networks [50].

We identify two primitive properties of codes designed for point-to-point symmetric channels which allows to translate the performance of these codes to network communication settings. These two properties are the probability of error of the code and its shaping distance. Whereas the probability of error is a measure of the error correction capability of the code when simulated over the symmetric channel, the shaping distance is a measure of the shaping capability of the decoding function[See Section <ref> for a formal definition of the shaping distance.]. Bounds on the performance of our code constructions will be derived in terms of these two properties regardless of other properties of the code. Such flexibility allows us to be tightly coupled with the most recent development in coding theory for point-to-point communication (in terms of performance), but at the same time to be completely decoupled from it (in terms of architecture).

Fig. <ref> illustrates the different coding problems considered in this paper, along with their constituent Lego bricks. Arrows pointing from a set of coding problems towards another coding problem means that codes for these problems can be used as building blocks in the design of a code for the designated problem. More precisely, coding schemes for the following problems will be constructed starting from the following codes.

[node distance=2.5cm]
(p2p) [p2p-box] Code for P2P Symmetric Channel;
(sw) [slepian-box, left of=p2p, xshift=-2.5cm] Slepian–Wolf Code;
(lossless) [lossless-box, right of=p2p, xshift=2.5cm] Lossless Source Code;
(gp) [smallbox, below of=p2p, xshift=-2.3cm] Gelfand–Pinsker Code;
(asym) [smallbox, left of=gp, xshift=-2cm] Asymmetric Channel Code;
(wz) [wyner-box, right of=gp, xshift=2cm] Wyner–Ziv Code;
(lossy) [smallbox, right of=wz, xshift=2cm] Lossy Source Code;
(mac) [mac-box, below of=asym] Code for Multiple Access Channel;
(marton) [marton-box, below of=gp] Marton Code for Broadcast Channel;
(bt) [wyner-box, below of=wz] Berger–Tung Code;
(mdc) [mdc-box, below of=lossy] Multiple
Description Code;
(downlink-cran) [downlink-cran-box, below of=bt] Code for
downlink C-RAN;
(uplink-cran) [uplink-cran-box, below of=marton] Code for
uplink C-RAN;
[text width=2cm,fill=none] at (0.3,0.75) Sec. <ref>;
[text width=2cm,fill=none] at (-2.65,0.4) Sec. <ref>;
[text width=2cm,fill=none] at (-2.65,-0.3) Sec. <ref>;
[text width=2cm,fill=none] at (3.15,0.3) Sec. <ref>;
[text width=2cm,fill=none] at (-6.85,-1.7) Sec. <ref>;
[text width=2cm,fill=none] at (-2,-1.7) Sec. <ref>;
[text width=2cm,fill=none] at (2.75,-1.7) Sec. <ref>;
[text width=2cm,fill=none] at (7.5,-1.7) Sec. <ref>;
[text width=2cm,fill=none] at (-7.15,-4.25) Appx. <ref>;
[text width=2cm,fill=none] at (-2.65,-4.1) Appx. <ref>;
[text width=2cm,fill=none] at (3.275,-4.1) Appx. <ref>;
[text width=2cm,fill=none] at (7.85,-4.25) Appx. <ref>;
[text width=2cm,fill=none] at (-1.9,-6.7) Appx. <ref>;
[text width=2cm,fill=none] at (2.35,-6.7) Appx. <ref>;

[transform canvas=yshift=0.25em] [arrow] (p2p) – (sw);
[transform canvas=yshift=-0.25em] [arrow] (sw) – (p2p);
[arrow] (p2p) – (lossless);
[arrow] (p2p) – (gp);
[arrow] (sw) – (gp);
[arrow] (p2p) – (wz);
[arrow] (sw) – (wz);
[arrow] (p2p) – (asym);
[arrow] (sw) – (asym);
[arrow] (p2p) – (lossy);
[arrow] (lossless) – (lossy);
[arrow] (lossy) – (bt);
[arrow] (wz) – (bt);
[arrow] (lossy) – (mdc);
[arrow] (wz) – (mdc);
[arrow] (asym) – (mac);
[arrow] (asym) – (marton);
[arrow] (gp) – (marton);
[arrow] (marton) – (downlink-cran);
[arrow] (lossy) – (downlink-cran);
[arrow] (mac) – (uplink-cran);
[arrow] (bt) – (uplink-cran);

Overview of the proposed coding schemes and their constituent building blocks, along with the section number in which each coding scheme is presented.

* Code for point-to-point symmetric channel $\to$ Lossless source code

* Code for point-to-point symmetric channel $\to$ Slepian–Wolf code

* Slepian–Wolf code $\to$ Code for point-to-point symmetric channel

* Code for point-to-point symmetric channel + Lossless source code $\to$ Lossy source code

* Code for point-to-point symmetric channel + Slepian–Wolf code $\to$ Wyner–Ziv code

* Code for point-to-point symmetric channel + Slepian–Wolf code $\to$ Gelfand–Pinsker code

* Code for point-to-point symmetric channel + Slepian–Wolf code $\to$ Asymmetric channel code

* Two asymmetric channel codes $\to$ Code for the two-user multiple access channel

* Asymmetric channel code + Gelfand–Pinsker code $\to$ Marton code for the two-user broadcast channel

* Lossy source code + Wyner–Ziv code $\to$ Berger–Tung code

* Two lossy source codes + Wyner–Ziv code $\to$ Multiple description code

* Two lossy source codes + Marton code for broadcast channel $\to$ Code for the downlink C-RAN problem

* Multiple access channel code + Berger–Tung code $\to$ Code for the uplink C-RAN problem

It follows that all the coding schemes can be constructed starting from codes for point-to-point symmetric channels. As an example, since a Marton code for the two-user broadcast channel can be constructed starting from an asymmetric channel code and a Gelfand–Pinsker code, each of which can be constructed from a Slepian–Wolf code and a point-to-point channel code for a symmetric channel, and since the Slepian–Wolf code can be constructed from a point-to-point symmetric channel code, it follows that a Marton code can be constructed using four channel codes that are designed for point-to-point symmetric channels. Similarly, all other coding schemes follow from point-to-point channel coding. Such an approach enables one to leverage commercial off-the-shelf codes (such as those studied in [5, 6, 7, 8, 9]) for point-to-point channels to build codes for the aforementioned coding problems in network information theory. Provided that the point-to-point channel codes are rate-optimal, the proposed constructions can achieve the best known inner bounds for these coding problems.

In several of the constructions that we will present, it will be assumed that two of the constituent linear point-to-point channel codes are nested. Such a nested linear structure is helpful to construct low-complexity coding schemes for network communication, as previously pointed out in the literature (e.g., [31, 51]). Nonetheless, it turns out that the nestedness requirement is not necessary, as we shall see later on in the paper (Section <ref>), where, at the price of slightly larger implementation complexity, the constructions will be modified to account for the relaxed assumptions on the constituent point-to-point channel codes. One important implication of these modified constructions is the following: any set of sequences of point-to-point channel codes that have a vanishing error probability over a symmetric channel can be combined with any set of sequences of point-to-point channel codes that have a vanishing shaping distance to construct coding schemes that achieve the best known inner bounds for the coding problems considered in this paper. As a consequence of this observation, it follows that polar codes with successive cancellation decoding [9] can achieve the best known inner bounds for the aforementioned coding problems using the proposed constructions.

We conclude this section with two interesting observations regarding the proposed constructions. First, one can see some form of duality between some of the constructions. For example, the encoder of the asymmetric channel coding scheme looks almost identical to the decoder of the lossy source coding scheme, and vice versa. Such a relation is well-known in the literature and has been pointed out in [11] and [52]. Nonetheless, note that, in our construction, the asymmetric channel encoder has a “shaping role”, whereas the lossy source decoder has an “error correction role”. Although not mathematically precise, this suggests some form of duality between error correction and shaping in our constructions, which can be seen as analogous to the well-understood packing-and-covering duality in network information theory. Similar observations can be made between the Gelfand–Pinkser coding scheme and the Wyner–Ziv coding scheme, between the Marton coding scheme and the Berger–Tung coding scheme, as well as between the downlink and uplink C-RAN code constructions. Secondly, as will be apparent from most of our constructions, randomization plays an important role in the design of coding schemes for network communication. The Lego bricks will often be used alongside a “dithering” brick, which generates a binary sequence uniformly at random, or an “interleaver” brick, which applies a permutation chosen uniformly at random to a binary sequence. Such randomness can shape signals into a desired structure, and will often be assumed to be shared between the encoders and the decoders. Note that sharing randomness between the transmitter and the receiver is a common practice in wireless communications, e.g., sharing the (pseudo)random spreading code in code-division multiple access (CDMA) systems [53] or sharing the interleaving pattern in 5G NR systems [54].

§.§ Paper Organization and Notation

The rest of the paper is organized as follows. Section <ref> describes the problem of point-to-point channel coding, along with two primitive properties of point-to-point channel codes that we will focus on throughout the paper, namely, the error probability and the shaping distance. Section <ref> discusses the Slepian–Wolf coding problem, along with its specialization to the lossless source coding problem. More specifically, an “equivalence” is established between designing a code for the binary Slepian–Wolf problem and designing a point-to-point channel code for a symmetric binary-input channel. In Section <ref>, coding schemes for the symmetric and asymmetric lossy source coding problems are described, which can be extended to the case when side information is available at the decoder (i.e., the Wyner–Ziv problem). Section <ref> describes a coding scheme for the binary-input Gelfand–Pinsker problem, along with its specialization to asymmetric point-to-point channel coding. Simulation results are presented for lossy source coding of an asymmetric source and for Gelfand–Pinsker coding in Sections <ref> and <ref>, respectively. In Section <ref>, modified constructions of the coding schemes are presented, which not only do not require any nested structure between the constituent Lego bricks, but also involve properties that are easily verifiable in practice. The modified constructions have a block-Markov structure, i.e., they are defined based upon the encoding and decoding of multiple message blocks, where the input to one coding block can depend on the outputs of previous/subsequent blocks. To complete the picture, code constructions for the remaining multiterminal source and channel coding problems are provided in the appendices. Appendix <ref> considers coding for multiple access channels, and Appendix <ref> describes a Marton coding scheme for broadcast channels. As for multiterminal lossy compression, Appendices <ref> and <ref> present coding schemes for the Berger–Tung problem and the multiple description coding problem, respectively. Appendices <ref> and <ref> focus on the downlink and uplink C-RAN problems respectively, which are multihop networks entailing both source and channel coding counterparts. The code constructions in the appendices are largely inspired by their random coding counterparts as well as the previous constructions in the main sections of the paper, yet we choose to include them in the paper as they help to provide a comprehensive treatment of the Lego-brick approach to coding over networks. Simulation results are also provided in Appendices <ref>, <ref> and <ref> for the Marton coding problem, and the downlink and uplink C-RAN problems, respectively, which can be of independent interest for both theoreticians and practitioners in the field. Section <ref> concludes the paper and gives some insights towards potential future research directions.

Notation: The following notation will be used. We write $x_1^n$ to denote a column vector $(x_1, \ldots, x_n)^T$, and $x_i^j$, for $i < j$, to denote the subvector $(x_i,\ldots,x_j)^T$. Sets are denoted in calligraphic letters, random variables in upper-case letters, and realizations of random variables in lower-case letters, i.e., $\cX$ and $\cY$ are two sets, $X$ and $Y$ are random variables, and $x$ and $y$ are their respective realizations. The distribution of a random variable $X$ will be denoted as $p_X = p_X(x)$, $x \in \cX$. When clear from the context, we will also often use the shorthand notation $p(x)$ to mean $p_X(x)$. The probability of an event $A$ is denoted as $\P\{A\}$. For a positive integer $n$, we use $[n]$ to denote the set $\{1,\ldots,n\}$. For a finite set $\cS$, we write $\abs{\cS}$ to denote the cardinality of $\cS$. $H(X)$ is used to denote the entropy of a random variable $X$ (in base 2). When $X\sim \BERN(\theta)$, we write $H(\theta)$ to denote $H(X)$. With a slight abuse of notation, we will also use $H$ to denote a parity-check matrix of a linear code. The mutual information of two random variables $X$ and $Y$ is written as $I(X;Y)$. The symmetric capacity of a binary-input channel $p(y \cond x)$ is written as $I(\BERN(1/2), p(y \cond x))$.

§ PRELIMINARIES

§.§ Basic Lego Brick: Code for a Point-to-Point Symmetric Channel

Consider a binary-input discrete memoryless channel $p(y\cond x)$ with an input alphabet $\cX=\{0,1\}$, an output alphabet $\cY$ and a collection of conditional probability mass functions (pmf's)

$p(y\cond x)$ on $\cY$ for each $x\in \cX$. A $(k,n)$ point-to-point channel code $(f,\phi)$ for the channel $p(y\cond x)$ consists of

* a codebook $\cC \subseteq \{0,1\}^n$ of size $|\cC| = 2^{k}$,

* an encoder $f: [2^{k}] \to \cC$ that maps each message $m \in [2^{k}]$ to a codeword $x^n = f(m)$,

* a decoder $\phi: \cY^n\to \cC$ that assigns a codeword estimate $\hat{x}^n = \phi(y^n)$ to each received sequence $y^n$.

The rate of the code is $R=k/n$. We say that the channel code is linear if for any two codewords $c^n, \tilde{c}^n \in \cC$, we have $c^n \oplus \tilde{c}^n \in \cC$. A linear code can be alternatively defined by its parity-check matrix $H_{(n-k) \times n}$ and its decoding function $\phi$. In this case, the codebook can be written as $\cC = \{c^n: Hc^n = 0^{n-k}\}$. With a slight abuse of notation, when the code is linear and its parity-check matrix is $H$, we will refer to it as a $(k,n)$ linear point-to-point channel code $(H,\phi)$.

Given any $(n-k)\times n$ parity-check matrix $H$, we will assume throughout the paper that the last $n-k$ columns of $H$ are linearly independent, i.e., $H = \begin{bmatrix}A & B\end{bmatrix}$ for some nonsingular $(n-k)\times (n-k)$ matrix $B$. As it will be deemed useful in the sequel, we also introduce the following linear transformation of the parity-check matrix,

\begin{equation} \label{eqn:H_tilde}
\wtilde{H} = \begin{bmatrix}
\bf 0 \\
\end{bmatrix} = \begin{bmatrix} {\bf 0} & {\bf 0} \\
B^{-1}A & I
\end{bmatrix},
\end{equation}

where $\bf 0$ denotes the all-zero matrix of the appropriate dimension.

The classical result of Shannon [44] states that the maximum achievable rate for reliable communication over a discrete memoryless channel $p(y\cond x)$, known as the capacity $C$ of the channel, is given by the maximum mutual information,

\begin{equation} \label{eqn:capacity_p2p}
C = \underset{p(x)}{\max} \, I(X;Y).
\end{equation}

Shannon showed that this fundamental limit can be attained using a random coding scheme that generates the codebook i.i.d. according to the capacity-achieving distribution.

We say that a binary-input memoryless channel $p(y\cond x)$ is symmetric (abbreviated, a BMS channel) if there exists a permutation $\pi:\cY\to\cY$ such that $\pi^{-1} = \pi$ and $p(y\cond x) = p(\pi(y)\cond x\oplus 1)$ for all $y\in \cY$ and $x\in\{0,1\}$. The channel $p(y\cond x)$ is asymmetric if it is not symmetric.

The capacity-achieving input distribution for a BMS channel is the uniform distribution <cit.>. Note that this is the only input distribution that can be attained using linear code ensembles.

§.§ Symmetrized Channel

Given any binary-input channel $p(y\cond x)$ (that is not necessarily symmetric) and any input distribution $p(x)$ (that is not necessarily uniform), a technique that will be crucial for us in our code constructions is the concept of a symmetrized channel corresponding to the joint distribution $p(x,y) = p(x)p(y\cond x)$, defined as follows [35].

Given a binary-input channel $p(y \cond x)$ and an input distribution $p(x)$ (not necessarily uniform), the symmetrized channel corresponding to $p(x,y) = p(x)p(y \cond x)$ is defined as the channel $\bar{p}$ with input alphabet $\cX = \{0,1\}$, output alphabet $\cY\times \{0,1\}$ and transition probabilities

\begin{equation*}
\bar{p}(y,v \cond x) = p_{X,Y}(x\oplus v, y).
\end{equation*}

The following are immediate consequences of the definition of a symmetrized channel.

* The channel $\bar{p}$ is symmetric under permutation $\pi\big((y,v)\big) = (y,v \oplus 1)$. In other words, for any $s \in \{0,1\}$,

\[
\bar{p}(y,v \cond x) = \bar{p}(y,v\oplus s \cond x \oplus s),
\]

which extends naturally when considering length-$n$ sequences.

* The channel $\bar{p}$ is, in particular, the conditional distribution $p_{\widebar{Y}\cond \widebar{X}}$ when $\widebar{X} = X\oplus V$, $\widebar{Y} = (Y,V)$, $(X,Y)$ is distributed according to $p(x,y)$, and $V\sim \BERN(1/2)$ is independent of $(X,Y)$.

* Since $\bar{X} \sim \BERN(1/2)$ and the channel $\bar{p}$ is symmetric, it follows that the capacity of the symmetrized channel $\bar{p}$ is

\begin{equation*}
\begin{aligned}
I(\widebar{X};\widebar{Y}) &= H(\widebar{X}) - H(\widebar{X}\cond \widebar{Y}) \\
&= 1 - H(X\oplus V\cond Y,V) = 1-H(X\cond Y).
\end{aligned}
\end{equation*}

Observations (i) and (ii) made above are illustrated in Figure <ref>. If $(X^n,Y^n)$ are i.i.d. according to $p(x,y)$, then the symmetrized channel $\bar{p}$ is exactly the channel between $\widebar{X}^n = X^n\oplus V^n$ and $(Y^n,V^n)$, where $V^n$ is an i.i.d $\BERN(1/2)$ sequence that is independent of $(X^n,Y^n)$. Furthermore, the symmetric property of the channel $\bar{p}$ implies that, for any arbitrary sequence $S^n$, the channel between $\wtilde{X}^n = \widebar{X}^n \oplus S^n$ and $(Y^n,V^n\oplus S^n)$ is also described by $\bar{p}$. This property will turn out to be useful in several of our constructions in the coming chapters.

The symmetrized channel.

§.§ Two Primitive Properties: Error Probability and Shaping Distance

Given a $(k,n)$ linear point-to-point channel code $(H,\phi)$ designed for a BMS channel $p(y \cond x)$, we will focus throughout this paper on two properties of the code, namely, the error probability and the shaping distance, which we define precisely below.

* Error probability: Let $X^n \sim \Unif(\cC)$, where $\cC$ is the codebook corresponding to $H$, and let $Y^n$ be the output of the channel $p(y \cond x)$ when the input is $X^n$. The error probability $\eps$ of the code $(H,\phi)$ when used over the channel $p(y\cond x)$ is defined as the probability of block error of the decoding function, i.e.,

\[
\epsilon \triangleq \sum_{x^n \in \cC}\Big(2^{-k} \P\{\phi(Y^n)\neq X^n \,\cond \, X^n = x^n\}\Big).
\]

Shannon's point-to-point channel coding theorem [44], along with its achievability proof using linear codes [56], state that a sequence of $(nR,n)$ linear codes having a vanishing error probability over the BMS channel $p(y \cond x)$ exists if and only if the rate $R < I\big(\BERN(1/2), p(y \cond x)\big)$, where $I\big(\Bern(1/2),p(y \cond x)\big)$ means the mutual information $I(X;Y)$ of the channel $p(y|x)$ when the input $X \sim \Bern(1/2)$. Since the channel is symmetric, $I\big(\Bern(1/2),p(y \cond x)\big)$ is, in fact, the capacity of the channel.

* Shaping distance: Let $Y^n$ be an i.i.d. $p(y)$ sequence, where $p(y) \triangleq \sum_{x}\frac{1}{2}p(y \cond x)$ is the marginal output distribution when the input distribution is $\BERN(1/2)$. Define $X^n = \phi(Y^n)$. The shaping distance $\delta$ of the code $(H,\phi)$ with respect to the channel $p(y \cond x)$ is defined as the total variation distance between the distribution of $(X^n,Y^n)$ (let's denote that by $q(x^n,y^n)$) and the i.i.d. $\frac{1}{2}p(y \cond x)$ distribution, i.e.,

\[
\delta \triangleq \frac{1}{2}\sum_{x^n,y^n}\left|q(x^n,y^n) - \frac{1}{2^n}\prod_{i=1}^{n}p(y_i \cond x_i)\right|.
\]

The shaping distance can be understood as a measure of the stochastic behavior of the decoding function $\phi$ in comparison to the “backward” channel $p(x\cond y)$ corresponding to the capacity-achieving input distribution. A sequence of $(nR,n)$ linear codes with a vanishing shaping distance exists if and only if the rate $R > I\big(\BERN(1/2), p(y \cond x)\big)$. To see this, one can refer to results on the distributed channel synthesis problem, introduced by Bennett et al. in [57] and further characterized by Cuff in [58]. In this problem, an i.i.d. source $\widebar{Y}^n$ distributed according to $p(\bar{y})$ is encoded by an index $M \in [2^{nR_{\mathrm{s}}}]$ to a decoder that wishes to produce an output $\widebar{X}^n$ such that the joint distribution of $(\widebar{X}^n,\widebar{Y}^n)$ is indistinguishable (in total variation distance) from a given joint i.i.d distribution $p(\bar{x},\bar{y})$. This is referred to as “synthesizing” the channel $p(\bar{x} \cond \bar{y})$. The main result in the distributed channel synthesis literature [58] is that there exists a construction of an encoder-decoder pair to synthesize $p(\bar{x} \cond \bar{y})$ if and only if the channel synthesis rate $R_{\mathrm{s}}$ is larger than $I(\widebar{X};\widebar{Y})$. We point out that, when $\widebar{X} \sim \BERN(1/2)$, the construction in [58] can be generalized to a linear construction[This holds because Theorem VII.1 in [58] only uses the pairwise independence of the codewords.]. Therefore, one can see that the condition of a small shaping distance on the point-to-point channel code $(H,\phi)$ is similar in nature to the condition imposed in the distributed channel synthesis problem, where the information bits corresponding to the output of $\phi$ can be seen as the index shared to the decoder in channel synthesis. Note that the encoder of the construction for the distributed channel synthesis problem would be the decoder of our point-to-point channel code, while the decoder of the channel synthesis construction is the encoder of the point-to-point code.

In what follows, we will construct coding schemes for various problems in network information theory starting from one (or more) point-to-point channel codes. The properties of the point-to-point channel codes (either error probability or shaping distance) will be instrumental in translating the performance guarantees from one communication setting to another. For reference, Table <ref> shows a (possibly non-exhaustive) list of families of point-to-point channel codes (along with their decoding algorithms) that can achieve a vanishing error probability and a vanishing shaping distance asymptotically over any BMS channel.

1cCodes with a vanishing error probability     1cCodes with a vanishing shaping distance

Random linear codes with joint typicality decoding [56]     Random linear codes with likelihood decoding [58]

Polar codes with successive cancellation decoding [9]     Polar codes with successive cancellation decoding [11]

Spatially-coupled codes with belief propagation decoding [8]

Reed–Muller codes with maximum-a-posteriori (MAP) decoding [59, 60, 61]

Families of codes over BMS channels that have a vanishing error probability and a vanishing shaping distance asymptotically.

§ SLEPIAN–WOLF CODING

In this section, we establish an “equivalence” between constructing a code for a point-to-point BMS channel and constructing a binary Slepian–Wolf code. In other words, we show that a code for any binary Slepian–Wolf problem can be designed starting from a code for a suitable BMS channel. Conversely, a code for any BMS channel can be constructed starting from a Slepian–Wolf code. In both cases, the optimal rate can be achieved asymptotically provided that the constituent code is rate-optimal. As a special case, the Slepian–Wolf coding scheme can be specialized to lossless source coding of a binary source. The duality between Slepian–Wolf coding and coding for a BMS channel has been previously noted in [33, 34, 35, 36]; in particular, the constructions provided in this section are equivalent to the ones in [36].

§.§ Problem Statement

A binary Slepian–Wolf problem $p(x,y)$ consists of a source alphabet $\cX=\{0,1\}$, an arbitrary side information alphabet $\cY$, and a joint pmf $p(x,y)$ over $\cX \times \cY$ [43]. A discrete memoryless source $X$ with side information $Y$ generates a jointly i.i.d. random process $\{(X_i,Y_i)\}$ with $(X_i,Y_i)\sim p(x,y)$. An $(\ell,n)$ code $(g,\psi)$ for the Slepian–Wolf problem $p(x,y)$ consists of

* an index set $\cI \subseteq \{0,1\}^n$ such that $|\cI| = 2^{\ell}$,

* an encoder $g:\cX^n \to \cI$ that maps each source sequence $x^n$ to an index $s^n = g(x^n)$, and

* a decoder $\psi:\cI\times\cY^n \to \cX^n$ that assigns a source estimate $\hat{x}^n=\psi(s^n,y^n)$ to each index $s^n$ and side information sequence $y^n$.

The rate of the code is $R=\ell/n$. The average probability of error of the code is $\epsilon = \P\{\widehat{X}^n \neq X^n\}$. A rate $R$, $0\leq R\leq 1$, is said to be achievable for the binary Slepian–Wolf coding problem if there exists a sequence of $(nR,n)$ codes with vanishing error probability asymptotically. The classical result of Slepian and Wolf [43] states that any rate $R > H(X \cond Y)$ is achievable for the binary Slepian–Wolf coding problem.

The Slepian–Wolf code is linear when the encoding function $g$ is linear, i.e., if for any $x^n, \tilde{x}^n \in \{0,1\}^n$, we have $g(x^n \oplus \tilde{x}^n) = g(x^n) \oplus g(\tilde{x}^n)$. When an $(\ell,n)$ linear Slepian–Wolf code $(g,\psi)$ has an encoding function that is defined as a matrix multiplication $g(x^n) = \begin{bmatrix}\bf 0 \\
Hx^n \end{bmatrix}$, where $H$ is an $\ell \times n$ matrix, we will refer to the code as an $(\ell,n)$ linear Slepian–Wolf code $(H,\psi)$.

§.§ Code for P2P BMS Channel $\to$ Slepian–Wolf Code

Consider a binary Slepian–Wolf problem $p(x,y)$, as defined in the previous section. We will construct a linear Slepian–Wolf code for this problem starting from a linear point-to-point channel code for a BMS channel. The BMS channel of interest is the symmetrized channel corresponding to $p(x,y)$, as defined in Section <ref>. The following lemma will be helpful to describe the Slepian–Wolf coding scheme.

Let $H$ be a parity-check matrix for a codebook $\cC$, and let $\wtilde{H}$ be as defined in (<ref>). Define $\cS = \{s^n \in \{0,1\}^n: s^k = 0^k\}$. Then,

* For any $x^n \in \{0,1\}^n$, there exists a unique $s^n \in \cS$ such that $x^n \oplus s^n \in \cC$. In particular, $s^n = \wtilde{H}x^n$.

* If $X^n$ is i.i.d. $\BERN(1/2)$, then $X^n\oplus \wtilde{H}X^n \sim \Unif(\cC)$.

* If $C^n \sim \Unif(\cC)$ and $S^n \sim \Unif(\cS)$ are independent, then $C^n \oplus S^n$ is i.i.d. $\BERN(1/2)$.

See Appendix <ref>.

Intuitively, part (ii) of Lemma <ref> gives a general way of generating a codeword uniformly at random starting from a uniformly distributed binary sequence, as illustrated in Fig. <ref>. Conversely, part (iii) generates a uniformly distributed binary sequence starting from a codeword chosen uniformly at random.

Illustration of a shift to $X^n \IID \Bern(1/2)$ by $\wtilde{H}X^n$ in $\{0,1\}^n$ space.

The main idea of the construction of the Slepian–Wolf coding scheme is captured in the following lemma.

Let $(X^n,Y^n)$ be i.i.d. according to $p(x,y)$, and $V^n$ be i.i.d. $\mathrm{Bern}(1/2)$ and independent of $(X^n,Y^n)$. Let $\bar{p}$ be the symmetrized channel corresponding to $p(x,y)$, as defined in Definition <ref>. Consider a parity-check matrix $H$ for a codebook $\cC$, and let $\wtilde{H}$ be as defined in $(\ref{eqn:H_tilde})$. Consider the sequences

\begin{equation} \label{eqn:codify}
\begin{aligned}
C^n &= X^n \oplus V^n \oplus \widetilde{H}X^n \oplus \wtilde{H} V^n, \\
U^n &= V^n \oplus \widetilde{H}V^n \oplus \widetilde{H}X^n.
\end{aligned}
\end{equation}

\begin{equation*}
\P\{C^n = c^n, U^n= u^n, Y^n = y^n\} = \frac{1}{2^k}\prod_{i=1}^{n}\bar{p}(y_i,u_i\cond c_i)
\end{equation*}

for every $c^n \in \cC$, $u^n \in \{0,1\}^n$ and $y^n \in \cY^n$.

Lemma <ref> can be seen as a recast of Lemmas 2 and 3 in [36]. For completion, the proof is provided in Appendix <ref>.

Lemma <ref> says that if $Y^n$ is the output of the channel $p(y\cond x)$ when the channel input is $X^n$, then, for a uniformly distributed binary sequence $V^n$, the sequences $(Y^n,U^n)$ are distributed as the outputs of the channel $\bar{p}$ when the channel input is $C^n$, a uniformly distributed codeword in the codebook $\cC$, where $C^n$ and $U^n$ are as defined in (<ref>). The relations between the different random variables is illustrated in Fig. <ref>.

The relations between the random variables $(X^n,Y^n,C^n,U^n)$ defined in Lemma <ref>. Notice the similarity to Fig. <ref> when $S^n$ in Fig. <ref> is set to $\wtilde{H}(X^n\oplus V^n)$. To recover $X^n$ from $Y^n$, one can go through the path $(Y^n,U^n) \to C^n \to R^n \to X^n$. To get $C^n$ from $(Y^n,U^n)$, one can apply a decoder of a point-to-point channel code designed for the channel $\bar{p}$. This explains the Slepian–Wolf coding scheme shown in Fig. <ref>.

Now, we are ready to construct a coding scheme for the Slepian–Wolf problem $p(x,y)$. The coding scheme uses the following point-to-point channel code.
[P2P $\to$ SW]
a $(k,n)$ linear point-to-point channel code $(H,\phi)$ with codebook $\cC$ for the symmetrized channel $\bar{p}$ corresponding to $p(x,y)$, which is defined over an input alphabet $\cX = \{0,1\}$ and output alphabet $\cY\times\{0,1\}$ by

\begin{equation} \label{eqn:channelq}
\bar{p}(y,v \cond x) = p_{X,Y}(x\oplus v,y).
\end{equation}

Let $\eps$ be the average probability of error of the code $(H,\phi)$ when used over the channel $\bar{p}$.

Fig. <ref> shows the channel code $(H,\phi)$ when used over the channel $\bar{p}$. The average probability of error $\eps$ of the code can be expressed as

\[
\eps = \P\{\phi(\widetilde{U}^n,\widetilde{Y}^n) \neq \widetilde{C}^n\}.
\]

A code for the symmetric channel $\bar{p}$, defined in (<ref>).

Fig. <ref> illustrates the block diagram of the Slepian–Wolf coding scheme that uses the point-to-point channel code $(H,\phi)$. The coding scheme can be described as follows.

A Slepian–Wolf code starting from a point-to-point channel code.

Encoding: Upon observing the source sequence $x^n$, the sender transmits $s^n = \widetilde{H}x^n$, where $\wtilde{H}$ is as defined in (<ref>).

Decoding: Upon observing the side information sequence $y^n$ and receiving the index $s^n$, the decoder declares $\hat{x}^n = \phi(s^n \oplus v^n \oplus \widetilde{H}v^n, y^n) \oplus s^n \oplus v^n\oplus \widetilde{H}v^n$ as the source estimate, where $v^n$ is a realization of a random dither generated independently at the decoder. Notice the similarity of this decoding method with the observations made through Fig. <ref>.

Analysis of probability of error: We have

\begin{align}
&\P\{\widehat{X}^n \neq X^n\} \nonumber\\
&= \P\{\phi(V^n \hspace*{-0.2em} \oplus \hspace*{-0.2em} \widetilde{H}V^n \hspace*{-0.2em} \oplus \hspace*{-0.2em} \widetilde{H}X^n, Y^n) \hspace*{-0.2em} \oplus \hspace*{-0.2em}  \widetilde{H}X^n \hspace*{-0.2em} \oplus \hspace*{-0.2em} \widetilde{H}V^n \hspace*{-0.2em} \oplus \hspace*{-0.2em} V^n \neq X^n \} \nonumber \\
&= \P\{ \phi(V^n\hspace*{-0.2em} \oplus\hspace*{-0.2em} \widetilde{H}V^n \hspace*{-0.2em} \oplus \hspace*{-0.2em} \widetilde{H}X^n, Y^n)  \neq X^n \hspace*{-0.2em} \oplus \hspace*{-0.2em}  V^n \hspace*{-0.2em} \oplus \hspace*{-0.2em} \widetilde{H}(X^n \hspace*{-0.2em} \oplus\hspace*{-0.2em}  V^n)\} \nonumber \\
&=\P\{\phi(U^n,Y^n) \neq C^n\}\nonumber \\
&\overset{(a)}{=}\P\{\phi(\wtilde{U}^n,\wtilde{Y}^n) \neq \wtilde{C}^n\}= \epsilon,
\end{align}

where $(a)$ follows from Lemma <ref>. Note that since the probability of error averaged over $V^n$ is $\eps$, there exists a deterministic $v^n$ sequence such that the error probability is bounded by $\eps$.

Rate: By construction, the rate of the Slepian–Wolf code is $(n-k)/n$.

Recall the definition of $(\widebar{X},\widebar{Y})$ in Remark <ref>. A sequence of codes for the channel $\bar{p}$ with a vanishing error probability exists if and only if the rate is smaller than

\begin{equation*}
\begin{aligned}
I(\widebar{X};\widebar{Y}) &= H(\widebar{X}) - H(\widebar{X}\cond \widebar{Y}) \\
&= 1 - H(X\oplus U \cond Y,U) = 1-H(X\cond Y).
\end{aligned}
\end{equation*}

It follows that, if the rate of the code for the channel $\bar{p}$ is $\frac{k}{n} = I(\widebar{X};\widebar{Y}) - \gamma$ for some $\gamma > 0$, then the rate of the Slepian–Wolf code is $\frac{n-k}{n} = H(X \cond Y) + \gamma$.

Conclusion: From each linear $(k,n)$ code for the BMS channel $\bar{p}$ defined in (<ref>) with average probability of error $\eps$, one can construct a linear $(n-k,n)$ code for the Slepian–Wolf problem $p(x,y)$ with average probability of error $\eps$.

§.§ Slepian–Wolf Code $\to$ Code for P2P BMS Channel

Now, we consider a BMS channel $p(y \cond x)$. We show that a code for this channel can be constructed starting from the following Slepian–Wolf code.

[SW $\to$ P2P]
an $(n-k,n)$ linear Slepian–Wolf code $(H,\psi)$ for the problem $p(x,y) = \frac{1}{2}p(y \cond x)$ with an average probability of error $\eps$.

A linear Slepian–Wolf code, where $(\wtilde{X}^n, \wtilde{Y}^n)$ are i.i.d. according to $p(x,y)$.

Fig. <ref> shows the Slepian–Wolf code $(H,\psi)$, where $(\wtilde{X}^n, \wtilde{Y}^n)$ are i.i.d. sequences distributed according to $p(x,y)$. The average probability of error $\eps$ of the Slepian–Wolf code can be written as

\[
\eps = \P\left\{\psi\left(\begin{bmatrix}
{\bf 0} \\
\end{bmatrix}, \wtilde{Y}^n\right) \neq \wtilde{X}^n\right\}.
\]

To construct a code for the channel $p(y \cond x)$, let $V^n$ be an i.i.d. $\Bern(1/2)$ random dither shared between the encoder and the decoder, and let $C^n \in \cC$ represent the message to be transmitted, where $\cC$ is the codebook corresponding to $H$. Fig. <ref> illustrates the block diagram of the point-to-point channel code. The coding scheme can be summarized as follows:

A point-to-point channel code starting from a Slepian–Wolf code.

Encoding: To send the message $c^n \in \cC$, the sender transmits $x^n = c^n \oplus v^n$, where $v^n$ is a realization of a random dither shared between the encoder and the decoder.

Decoding: Upon observing $y^n$, the decoder declares $\hat{c}^n = \psi\left(\begin{bmatrix}
{\bf 0} \\
\end{bmatrix}, y^n\right) \oplus v^n$ as the message estimate.

Analysis of probability of error: We have

\begin{equation*}
\begin{aligned}
\P\{\widehat{C}^n \neq C^n\} &= \P\left\{\psi\left(\begin{bmatrix}
{\bf 0} \\
\end{bmatrix},Y^n\right)\oplus V^n \neq C^n\right\} \\
&\overset{(a)}{=} \P\left\{\psi\left(\begin{bmatrix}
{\bf 0} \\
\end{bmatrix},Y^n\right)\neq X^n\right\} \\
&\overset{(b)}{=} \P\left\{\psi\left(\begin{bmatrix}
{\bf 0} \\
\end{bmatrix},\wtilde{Y}^n\right)\neq \wtilde{X}^n\right\} \\
&= \eps,
\end{aligned}
\end{equation*}

where $(a)$ follows since $HX^n = HC^n \oplus HV^n = HV^n$, and $(b)$ follows since after dithering with the uniform $V^n$, $(X^n,Y^n)$ are identically distributed as $(\wtilde{X}^n, \wtilde{Y}^n)$ in the Slepian–Wolf problem. Note that since the probability of error averaged over $V^n$ is $\eps$, there exists a deterministic $v^n$ sequence such that the probability of error is bounded by $\eps$.

Rate: Since $\abs{\cC}  = 2^k$, the rate of the point-to-point channel code is $k/n$.

If the rate of the Slepian–Wolf code is $\frac{n-k}{n} = H(X \cond Y) + \gamma$ for some $\gamma > 0$, then the rate of the point-to-point channel code is

\begin{equation*}
1-H(X \cond Y) - \gamma = I\big(\Bern(1/2),p(y \cond x)\big) - \gamma,
\end{equation*}

where $I\big(\Bern(1/2),p(y \cond x)\big)$ is the maximum achievable rate for the BMS channel $p(y \cond x)$.

Conclusion: From each linear $(n-k,n)$ Slepian–Wolf code for the problem $p(x,y) = \frac{1}{2}p(y \cond x)$ with average probability of error $\eps$, one can construct a linear $(k,n)$ code for the BMS channel $p(y \cond x)$ with average probability of error $\eps$.

§.§ Specialization to Lossless Source Coding

As a special case of Slepian–Wolf coding, a lossless source code can be implemented using a point-to-point channel code that is designed for a binary symmetric channel. To see this, consider a binary memoryless source that generates an i.i.d. $\BERN(\theta)$ sequence $X^n$ for some $\theta \in (0,1/2)$. As in Slepian–Wolf coding, the goal is to represent the source sequence using as few bits as possible to a decoder that wishes to find an estimate $\widehat{X}^n$ of the sequence. The definition of a lossless source code, its rate and probability of error follow similarly as in Slepian–Wolf coding, with the exception that a lossless source decoder has no access to any side information sequence.

The coding scheme presented in Section <ref> can be specialized to lossless source coding when there is no side information. It is easy to check that, in the case of no side information, the symmetrized channel corresponding to $p(x)$ is a $\BSC(p_X(1))$. Therefore, a lossless source coding scheme for a $\BERN(\theta)$ source can be constructed starting from a point-to-point channel code designed for $\BSC(\theta)$, as given in the following Lego brick.
[P2P $\to$ Lossless]
a $(k,n)$ linear point-to-point channel code $(H,\phi)$ designed for $\BSC(\theta)$ with average probability of error $\eps$ when used over the channel.

A lossless source code starting from a point-to-point channel code.

Fig. <ref> shows the lossless source coding scheme, where $X^n$ is an i.i.d. $\BERN(\theta)$ source sequence, and $V^n$ is an i.i.d. $\BERN(1/2)$ sequence generated at the decoder independently of $X^n$. Notice that the coding scheme is very similar to the Slepian–Wolf coding scheme (Fig. <ref>), except that no side information sequence is used at the decoder side. As before, the rate of the lossless source code is $(n-k)/n$, and its average probability of error is given by $\eps$, which follows by specializing Lemma <ref> to the case when $p(y)$ is deterministic and independent of $p(x)$.

If the rate of the channel code is $\frac{k}{n} = 1-H(\theta) - \gamma$ for some $\gamma > 0$, then the rate of the lossless source code is $H(\theta) + \gamma$.

Conversely, a lossless source code can be used to construct a point-to-point channel code for a binary symmetric channel (BSC). This implies an “equivalence” between constructing a linear point-to-point channel code for the BSC and constructing a linear lossless source code for a binary source, which is well-understood in the literature [62].

§ LOSSY SOURCE CODING

In this section, we construct coding schemes for the lossy source coding problem starting from simple Lego bricks. We consider two cases: the first is the case of a symmetric source, and the second corresponds to a general asymmetric source. The distinction is made because a simpler construction is possible for the former case. More specifically, in the case of a symmetric source, our coding scheme is constructed starting from a single point-to-point symmetric channel code, whereas the coding scheme for the general asymmetric source uses both a point-to-point symmetric channel code and a lossless source code. In both cases, the proposed coding scheme is rate-optimal provided that the constituent Lego bricks are rate-optimal. First, let's start by defining the lossy source coding problem.

§.§ Problem Statement

Introduced by Shannon in [45], the problem of lossy compression of a binary memoryless source consists of an i.i.d. random process $\{X_i\}$ with $X_i \sim \mathrm{Bern}(\theta)$ for some $\theta \in (0,1/2]$. The goal is to efficiently represent a source sequence $X^n$ when some distortion is allowed during reconstruction. More formally, an $(R,n)$ code for the lossy source coding problem consists of an encoder $g: \{0,1\}^n \to [2^{nR}]$ that assigns an index $M$ to the source sequence $X^n$, and a decoder $\psi: [2^{nR}] \to \{0,1\}^n$ that assigns an estimate $\hat{X}^n$ to the index $M$.

The rate of the code is $R$, and its expected distortion is $\frac{1}{n}\E\left[ d_H(X^n,\widehat{X}^n) \right]$,

where $d_H(.,.)$ denotes the Hamming distance metric. A rate-distortion pair $(R,D)$ is said to be achievable if there exists a sequence of $(R,n)$ codes with

\[
\underset{n \to \infty}{\limsup} \frac{1}{n}\E\left[ d_H(X^n,\widehat{X}^n) \right] \leq D.
\]

The rate-distortion function $R(D)$ is defined as the infimum of all rates $R$ such that $(R,D)$ is achievable.

Shannon [45] showed that the rate-distortion function for a $\BERN(\theta)$ source can be expressed as

\[
R(D) = \begin{cases}
H(\theta) - H(D) &\quad \text{for } 0\leq D < \theta, \\
0 &\quad \text{for } D \geq \theta.
\end{cases}
\]

Shannon's random coding scheme assigns, for each typical source sequence $x^n$, a reconstruction sequence $\hat{x}^n$ that is jointly typical with $x^n$ for some desired conditional pmf $p(\hat{x}\cond x)$. For the case of a binary source, the desired conditional pmf $p(\hat{x}\cond x)$ corresponds to the case when the “backward” channel $p(x \cond \hat{x})$ is a $\BSC(D)$.

§.§ Symmetric Source

Consider a realization of a symmetric source $X^n \IID \Bern(1/2)$, and let $D\in (0,1/2)$ be some desired distortion level. We will construct a lossy source coding scheme for this source starting from the following point-to-point channel code.

[P2P $\to$ Sym. Lossy]
a $(k,n)$ linear point-to-point channel code $(H,\phi)$ for $\mathrm{BSC}(D)$ with a shaping distance $\delta$.

The main ingredient in the lossy source coding scheme is utilizing the shaping capability of the decoding function $\phi$ – manifested by its shaping distance property $\delta$ – in order to generate a sequence according to the desired distribution (or “close” to it). In the simple setting of a symmetric source, this can be done by simply declaring the output of the decoding function as the source reconstruction, and the corresponding information bits as the index shared to the decoder, as depicted in Fig. <ref>, where $G$ is the generator matrix of the code $(H,\phi)$, and $\mathrm{Info(.)}$ is the function that takes as input a codeword in a linear code  and outputs the corresponding information bits. The coding scheme can be summarized as follows.

Encoding: Upon observing the source sequence $x^n$, the encoder stores the information sequence $u^k$ such that $\phi(x^n) = u^kG$.

Decoding: Upon observing the index $u^k$, the decoder declares the sequence $\hat{x}^n = u^kG$ as the source estimate.

Analysis of the average distortion: Let $q(x^n,\hat{x}^n)$ denote the distribution of $(X^n,\widehat{X}^n)$, and let $p(x^n,\hat{x}^n)$ be the desired i.i.d. distribution, i.e.,

\[
p(x^n,\hat{x}^n) = \frac{1}{2^n} D^{\weight(x^n \oplus \hat{x}^n)}(1-D)^{n-\weight(x^n \oplus \hat{x}^n)}
\]

Since $\widehat{X}^n = \phi(X^n)$ and $X^n \IID \Bern(1/2)$ (which is the channel output distribution of $\BSC(D)$ under the capacity-achieving input distribution), the average distortion is given by

\begin{align*}
&\frac{1}{n}\E[d_H(X^n,\widehat{X}^n)] = \frac{1}{n}\sum_{x^n,\hat{x}^n}q(x^n,\hat{x}^n)d_H(x^n,\hat{x}^n)\\
&= \frac{1}{n}\sum_{x^n,\hat{x}^n}p(x^n,\hat{x}^n)d_H(x^n,\hat{x}^n) \\
&\quad + \frac{1}{n}\sum_{x^n,\hat{x}^n}\left(q(x^n,\hat{x}^n) - p(x^n,\hat{x}^n)\right) d_H(x^n,\hat{x}^n)\\
&\overset{(a)}{\leq} D + \frac{1}{2}\sum_{x^n,\hat{x}^n}\left|q(x^n,\hat{x}^n) - p(x^n,\hat{x}^n)\right|\\
&\overset{(b)}{=} D+\delta,
\end{align*}

where $(a)$ holds since $p(\hat{x}^n\cond x^n)$ is equivalent to $n$ independent uses of $\BSC(D)$ and the fact that $\sum_{i}c_i(a_i -b_i) \leq \frac{1}{2}\sum_{i}\left|a_i-b_i\right|$ whenever $0\leq c_i \leq 1$ and $\sum_{i}a_i = \sum_{i}b_i$, and $(b)$ follows by the definition of the shaping distance of the code $(H,\phi)$.

Rate: The rate of the coding scheme is $R = \frac{k}{n}$.

Thus, we have obtained an $(R,n)$ lossy source code for a symmetric source with an expected distortion that is bounded by $D+\delta$ starting from a point-to-point channel code for $\BSC(D)$ with shaping distance $\delta$.

A lossy source coding scheme for a symmetric source starting from a point-to-point channel code.

Following the discussion in Section <ref>, a sequence of linear point-to-point channel codes with a vanishing shaping distance $\delta$ exists if (and only if[The “only if” part clearly holds by our current construction and the lossy source coding theorem.]) the rate is larger than $1-H(D)$.

Note that for this construction, it suffices to have a point-to-point channel code that satisfies

\[
\abs{\frac{1}{n}\E[d_H(X^n,\phi(X^n))]-D} \leq \delta,
\]

rather than the more stringent condition of the shaping distance. Nonetheless, we show the shaping distance condition here for illustrative purposes, as it introduces the idea of using a decoding function for shaping a binary sequence, a theme that will be recurrent throughout the paper.

§.§ Asymmetric Source

Now, we consider the case of a general binary memoryless source that generates an i.i.d. $\BERN(\theta)$ sequence $X^n$ for some $\theta \in (0,1/2)$. Let $D \in (0,\theta)$ be some desired distortion level[Clearly, when $D \geq \theta$, a rate-zero coding scheme is possible by deterministically outputting the all-zero sequence as the source reconstruction.], and define

\[
\alpha \triangleq \frac{\theta - D}{1-2D}.
\]

Note that $\widehat{X} \sim \Bern(\alpha)$ when the conditional distribution $p(x \cond \hat{x})$ is $\mathrm{BSC}(D)$, which is the desired conditional distribution of the source given the reconstruction as inspired by Shannon's random coding scheme [45]. Let $p(x,\hat{x})$ denote the desired joint distribution between the source and the reconstruction, i.e.,

\begin{equation} \label{eqn:lossy_joint_distribution}
p(x,\hat{x}) = \alpha^{\hat{x}}(1-\alpha)^{1-\hat{x}}D^{x \oplus \hat{x}}(1-D)^{1-x\oplus \hat{x}}.
\end{equation}

The proposed lossy source coding scheme in this general setting utilizes a point-to-point channel code  and a lossless source code. At the encoder side, the point-to-point channel code is used to generate a sequence according to the desired distribution of the reconstruction (i.e., the i.i.d. $\BERN(\alpha)$ distribution), and the lossless source code is used to compress that sequence to the decoder. Another key ingredient in the coding scheme is the assumption that the two codebooks are nested.

Before we describe the coding scheme, we state the following lemma, which will be useful in several constructions in this paper.

Let $\bar{p}(\td{y}, \td{v} \cond \td{x})$ be the symmetrized channel corresponding to a given joint distribution $p(\td{x},\td{y})$. Let $(H,\phi)$ be a point-to-point channel code designed for $\bar{p}$, and let $\delta$ be its shaping distance. Let $\td{Y}^n$ be i.i.d. according to $p(\td{y})$ and $\td{V}^n$ be i.i.d. $\BERN(1/2)$ such that $\td{Y}^n$ and $\td{V}^n$ are independent, and let $\td{U}^n = \phi(\td{Y}^n,\td{V}^n)\oplus \td{V}^n$. Then,

\[
\frac{1}{2}\sum_{\td{u}^n,\td{y}^n}\left| \P\{\td{U}^n=\td{u}^n,\td{Y}^n=\td{y}^n\}-\prod_{i=1}^n p_{\td{X},\td{Y}}(\td{u}_i,\td{y}_i) \right| \leq \delta.
\]

See Appendix <ref>.

Intuitively, given an i.i.d sequence $\td{Y}^n$ distributed according to $p(\td{y})$, Lemma <ref> suggests a general method of constructing a sequence $\td{U}^n$ such that the joint distribution of $(\td{Y}^n,\td{U}^n)$ is $\delta$-away in total variable distance from a given joint i.i.d distribution $p(\td{x},\td{y})$. This can be done using a point-to-point channel code with a shaping distance $\delta$ over the symmetrized channel $\bar{p}$ corresponding to $p(\td{x},\td{y})$. This technique will be used in several constructions in the paper.

Now, we are ready to describe the lossy source coding scheme of a general asymmetric source. The coding scheme can be constructed from the following point-to-point channel code and lossless source code.

[P2P $\to$ Lossy]
a $(k_1,n)$ linear point-to-point channel code $(H_1,\phi_1)$ with codebook $\cC_1$ for the channel

\begin{equation} \label{eqn:p2p_lossy}
\bar{p}(x, v\cond\hat{x}) = p_{X, \widehat{X}}(x, \hat{x}\oplus v).
\end{equation}

Let $\delta$ denote the shaping distance of the code $(H_1,\phi_1)$ with respect to the channel $\bar{p}$.

[Lossless $\to$ Lossy]
an $(n-k_2,n)$ lossless source code $(H_2,\phi_2)$ for a $\BERN(\alpha)$ source with average probability of error $\eps$. Let $\cC_2$ be the codebook corresponding to $H_2$. We assume that $\cC_2 \subseteq \cC_1$, i.e., the two codebooks are nested.

The channel $\bar{p}$ defined in (<ref>) is the symmetrized channel corresponding to the joint distribution $p(x,\hat{x})$ (see Section <ref> for a formal definition of a symmetrized channel).

Since $\cC_2 \subseteq \cC_1$, we will assume, without loss of generality, that $H_1$ is a submatrix of $H_2$, i.e., $H_2 = \begin{bmatrix}
\end{bmatrix}$ for some $(k_1-k_2)\times n$ matrix $Q$.[Note that such a relation between $H_1$ and $H_2$ can be obtained for any pair of nested linear codes by basic row operations and column permutations.]

Starting from the aforementioned building blocks, Figure <ref> shows the block diagram of the lossy source coding scheme, where $V^n$ is an i.i.d. $\BERN(1/2)$ random dither shared between the encoder and the decoder. The lossy encoder generates the sequence $U^n=\phi_1(X^n,V^n)\oplus V^n$ which has a distribution that is $\delta$-away in total variation distance from the i.i.d. $\BERN(\alpha)$ distribution. This is a consequence of Lemma <ref>. Further, since $H_1U^n = H_1V^n$ and

\[
H_2U^n = \begin{bmatrix}
H_1U^n \\
\end{bmatrix} = \begin{bmatrix}
\end{bmatrix},
\]

the lossy decoder is able to reconstruct an estimate $\widehat{X}^n$ of the sequence $U^n$ using only the index $QU^n$ (since $V^n$ is shared randomness with the decoder) and the lossless source decoder $\phi_2$. The following lemma states that the joint distribution of $(X^n, \widehat{X}^n)$ is $(\delta+\eps)$-away in total variation distance from the desired i.i.d. $p(x,\hat{x})$ distribution.

Let $q(x^n,\hat{x}^n)$ denote the distribution of $(X^n,\widehat{X}^n)$, and let $p(x^n,\hat{x}^n)$ be the desired i.i.d. $p(x,\hat{x})$ distribution, where $p(x,\hat{x})$ is as defined in (<ref>). Then,

\begin{equation*}
\frac{1}{2}\sum_{x^n,\hat{x}^n}\left| q(x^n,\hat{x}^n) - p(x^n,\hat{x}^n) \right| \leq \delta + \eps.
\end{equation*}

See Appendix <ref>.

Therefore, the coding scheme can be summarized as follows.

Encoder and decoder of a lossy source code for an asymmetric source starting from a point-to-point channel code and a lossless source code.

Encoding: Upon observing the source sequence $x^n$, the encoder computes the sequence $u^n = \phi_1\left(x^n, v^n\right)\oplus v^n$ and transmits the index $m^{k_1-k_2} = Qu^n$, where $v^n$ is a realization of a random dither shared with the decoder.

Decoding: Upon observing the index $m^{k_1-k_2}$, the decoder declares the sequence

\[
\hat{x}^n = \phi_2\left( \begin{bmatrix}\bf 0 \\ H_1v^n \\ m^{k_1-k_2}\end{bmatrix} \right)
\]

as the source estimate.

Analysis of the average distortion: The average distortion of the coding scheme can be bounded as

\begin{align}
&\frac{1}{n}\E[d_H(X^n,\widehat{X}^n)] = \frac{1}{n}\sum_{x^n,\hat{x}^n}q(x^n,\hat{x}^n)d_H(x^n,\hat{x}^n) \nonumber \\
&= \frac{1}{n}\sum_{x^n,\hat{x}^n}p(x^n,\hat{x}^n)d_H(x^n,\hat{x}^n) \\
&\quad + \frac{1}{n}\sum_{x^n,\hat{x}^n}\left(q(x^n,\hat{x}^n) - p(x^n,\hat{x}^n)\right) d_H(x^n,\hat{x}^n)\nonumber \\
&\overset{(a)}{\leq} D + \frac{1}{2}\sum_{x^n,\hat{x}^n}\left|q(x^n,\hat{x}^n) - p(x^n,\hat{x}^n)\right|\nonumber \\
&\overset{(b)}{\leq} D+\delta+\eps,
\end{align}

where $(a)$ holds since $p(x^n\cond \hat{x}^n)$ is equivalent to $n$ independent uses of $\BSC(D)$ and the fact that $\sum_{i}c_i(a_i -b_i) \leq \frac{1}{2}\sum_{i}\left|a_i-b_i\right|$ whenever $0\leq c_i \leq 1$ and $\sum_{i}a_i = \sum_{i}b_i$, and $(b)$ follows by Lemma <ref>.

Rate: The rate of the coding scheme is $R = \frac{k_1-k_2}{n}$.

A sequence of linear point-to-point channel codes for the channel $\bar{p}$ with a vanishing shaping distance $\delta$ exists if (and only if) the rate is larger than $1-H(\widehat{X} \cond X)$. This follows by the discussion in Section <ref> and the properties of a symmetrized channel (Remark <ref>).

If the rate of the point-to-point channel code is $\frac{k_1}{n}=1-H(\widehat{X} \cond X)+\gamma_1$ for some $\gamma_1>0$, and the rate of the lossless source code is $\frac{n-k_2}{n} = H(\alpha)+\gamma_2 = H(\widehat{X}) + \gamma_2$ for some $\gamma_2 > 0$, then the rate of the lossy source code is

\[
\frac{k_1-k_2}{n} = I(X;\widehat{X}) + \gamma_1 + \gamma_2 = H(\theta)-H(D) + \gamma_1 + \gamma_2.
\]

Conclusion: Starting from a $(k_1,n)$ linear point-to-point channel code with shaping distance $\delta$ and an $(n-k_2,n)$ lossless source code with an average probability of error $\eps$, we have constructed a $(\frac{k_1-k_2}{n},n)$ lossy source code that targets a conditional distribution $p(\hat{x} \cond x)$ with an average distortion that is bounded by $D+\delta+\eps$. Note that the point-to-point channel code should be designed for the symmetrized channel $\bar{p}$ – and not, for example, for $\BSC(D)$ – since the source is asymmetric, and, hence, the source sequence $X^n$ is not distributed according to the channel output distribution of a $\BSC$.

§.§ Simulation Results

The lossy source coding scheme of Fig. <ref> is simulated for a $\BERN(0.3)$ source (i.e., $\theta = 0.3$) using polar codes with successive cancellation decoding as the constituent point-to-point channel codes. The lossless source decoder used in the construction can be implemented using a polar code designed for a binary symmetric channel, as described in Section <ref>. To construct the polar codes (i.e., identify the information sets), we use Arıkan's method of sorting upper bounds on the Bhattacharyya parameters of the synthetic polar bit-channels [9]. Since our coding scheme requires that the two codes are nested, the information set corresponding to the polar code $(H_2,\phi_2)$ is chosen to be a subset of that of the code $(H_1,\phi_1)$. Let $R_1$ and $R_2$ be the rates of the two polar codes.

Distortion level and bias of the sequence $U^n$ at the encoder side assuming a $\BERN(0.3)$ source and a polar code of block length $n=1024$.

We first consider the encoder of Fig. <ref>. We would like to see if the decoder $\phi_1$ correctly shapes the sequence $U^n$ according to the desired distribution. To this end, let $D_{\mathrm{enc}}$ and $\alpha_{\mathrm{enc}}$ denote respectively the distortion level and the bias of the sequence $U^n$ at the encoder side, i.e.,

\begin{equation*}
\begin{aligned}
D_{\mathrm{enc}} &= \frac{1}{n}\E[d_H(U^n,X^n)],\\
\alpha_{\mathrm{enc}} &= \frac{1}{n}\E[\weight(U^n)].
\end{aligned}
\end{equation*}

Fig. <ref> shows the plot of the achieved distortion level and bias at the encoder side for a block length $n=1024$. For comparison, the desired distortion and bias are also plotted. Note that the desired bias $\alpha$ corresponds to the mapping $D \mapsto \frac{\theta-D}{1-2D}$. At each distortion level $D$, the rate of the polar code $(H_1,\phi_1)$ is chosen to be close to the theoretical limit, i.e., we take

\[
R_1 = 1-H(\widehat{X} \cond X).
\]

The results demonstrate that the achieved distortion and bias at the encoder side follow closely the desired design values. This implies that polar codes indeed have good shaping properties, even at finite block length.

Next, the entire lossy source coding scheme of Fig. <ref> is simulated. The rate-distortion tradeoff for the coding scheme is shown in Fig. <ref> for different block lengths $n = 256$, $n=1024$, and $n=4096$. For good error performance of the lossless source decoder, the rate $R_2$ should be chosen with a small gap to its theoretical limit, i.e., we take

\[
R_2 = 1-H(\widehat{X}) -\gamma,
\]

for some small “back-off” parameter $\gamma > 0$. In our simulations, we used $\gamma = 1/8$. Each simulation point shown in Fig. <ref> corresponds to a chosen rate pair $(R_1,R_2)$ of the constituent channel codes, where the rate of the coding scheme is $R=R_1-R_2$. For reference, the rate-distortion function is also shown. Clearly, the practical performance approaches the theoretical limit for increasing block lengths. The simulation results demonstrate that off-the-shelf codes can be leveraged in the construction of practical lossy source coding schemes. For more details about the simulation setup, our code is available on GitHub [63].

Rate-distortion tradeoff achieved by the lossy source coding scheme for a $\BERN(0.3)$ source using polar codes of different block lengths.

§.§ Extension to Wyner–Ziv Coding

The lossy source coding scheme presented in this section can be easily extended to the binary Wyner–Ziv coding problem, simply by replacing the lossless source code with a Slepian–Wolf code. Let us first review the binary Wyner–Ziv coding problem [46]. This problem consists of a source alphabet $\cX = \{0,1\}$, arbitrary side information alphabet $\cY$, a reconstruction alphabet $\widehat{\cX} = \{0,1\}$, and a joint pmf $p(x,y)$ over $\cX \times \cY$. The source generates a jointly i.i.d. random process $\{(X_i,Y_i)\}$ with $(X_i,Y_i)\sim p(x,y)$. The goal is to efficiently represent a length-$n$ source sequence $X^n$ to a decoder which has access to the side information sequence $Y^n$ and wishes to reconstruct the source sequence up to some distortion level $D$. The definitions of a Wyner–Ziv code, its expected distortion and achievable rates are the same as in Section <ref>, with the exception that the decoding function takes an additional input, namely, the side information sequence. Wyner and Ziv [46] showed that for any conditional pmf $p(\hat{x}\cond x)$ such that $\E[d(X,\widehat{X})] \leq D$, any rate $R > I(X;\widehat{X} \cond Y)$ is achievable with a distortion level $D$.

In what follows, let $D$ be some desired distortion level, and let $p(\hat{x} \cond x)$ be a desired conditional pmf of the reconstruction given the source such that $\E[d(X,\widehat{X})] \leq D$, where $d(.,.)$ is the Hamming distortion metric. A code for the Wyner–Ziv coding problem can be constructed starting from the following point-to-point channel code and Slepian–Wolf code.

[P2P $\to$ WZ]
a $(k_1,n)$ linear point-to-point channel code $(H_1,\phi_1)$ with codebook $\cC_1$ for the channel

\begin{equation*}
\bar{p}(x, v\cond\hat{x}) = p_{\widehat{X},X}(\hat{x}\oplus v, x).
\end{equation*}

Let $\delta$ denote the shaping distance of the code $(H_1,\phi_1)$ with respect to the channel $\bar{p}$.

[SW $\to$ WZ]
an $(n-k_2,n)$ Slepian–Wolf code $(H_2,\phi_2)$ for the problem

\[
p(\hat{x},y) = \sum_{x}p(x,y)p(\hat{x} \cond x),
\]

with codebook $\cC_2$ and average probability of error $\eps_2$. We assume that the two codebooks are nested, i.e., $\cC_2 \subseteq \cC_1$.

Fig. <ref> shows the block diagram of the Wyner–Ziv coding scheme, where $V^n$ is an i.i.d. $\BERN(1/2)$ random dither shared between the encoder and the decoder. The main difference in comparison to the lossy source coding scheme of Section <ref> is that a Slepian–Wolf decoder is used instead of the lossless source decoder. The Slepian–Wolf decoder utilizes the available side information sequence at the decoder side. The description of the coding scheme and the analysis of its average distortion follow similarly as in the lossy source coding scheme.

If the rate of the point-to-point channel code is $\frac{k_1}{n}=1-H(\widehat{X} \cond X)+\gamma_1$ for some $\gamma_1>0$, and the rate of the Slepian–Wolf code is $\frac{n-k_2}{n} = H(\widehat{X} \cond Y)+\gamma_2$ for some $\gamma_2 > 0$, then the rate of the Wyner–Ziv code is

\begin{equation*}
\begin{aligned}
\frac{k_1-k_2}{n} &= H(\widehat{X} \cond Y) - H(\widehat{X} \cond X)+ \gamma_1 + \gamma_2 \\
&\overset{(a)}{=} I(X;\widehat{X} \cond Y) + \gamma_1 + \gamma_2,
\end{aligned}
\end{equation*}

where the equality $(a)$ holds since $Y$ and $\widehat{X}$ are independent given $X$.

Encoder and decoder of a Wyner–Ziv coding scheme starting from a point-to-point channel code and a Slepian–Wolf code.

Conclusion: Starting from a $(k_1,n)$ linear point-to-point channel code with shaping distance $\delta$ and an $(n-k_2,n)$ Slepian–Wolf code with an average probability of error $\eps$, we have constructed a $(\frac{k_1-k_2}{n},n)$ Wyner–Ziv code that targets a conditional distribution $p(\hat{x} \cond x)$ with an average distortion that is bounded by $D+\delta+\eps$.

§ GELFAND–PINSKER CODING

§.§ Problem Statement

The binary-input Gelfand–Pinsker problem consists of a discrete memoryless channel with state $p(y \cond x,s)p(s)$, input alphabet $\cX = \{0,1\}$, state alphabet $\cS$, output alphabet $\cY$, a collection of conditional probability mass functions $p(y,s\cond x)$ on $\cY \times \cS$ for each $x \in \cX$, and a probability mass function $p(s)$ on $\cS$, where the state sequence $(S_1, S_2, \ldots)$ is i.i.d. with $S_i \sim p(s_i)$ and is available noncausally only at the encoder [1]. An $(R, n)$ code $(g,\psi)$ for the Gelfand–Pinsker problem $p(y|x,s)p(s)$ consists of

* a message set $\cM$ such that $\abs{\cM} = 2^{nR}$,

* an encoder $g: \cM \times \cS^n \to \cX^n$ that assigns a codeword $x^n = g(m,s^n)$ to each message $m$ and state sequence $s^n$, and

* a decoder $\psi: \cY^n \to \cM$ that assigns an estimate $\hat{m} = \psi(y^n)$ to each received sequence $y^n$.

The average probability of error of the code is $\P\{\widehat{M} \neq M\}$. An $(R, n)$ Gelfand–Pinsker code $(g,\psi)$ is depicted in Fig. <ref>.

A rate $R$ is said to be achievable for the Gelfand–Pinsker problem if there exists a sequence of $(R,n)$ Gelfand–Pinsker codes with vanishing error probability asymptotically. The classical result by Gelfand and Pinsker [1] states that any rate

\begin{equation} \label{eqn:gelfand_capacity}
R < \underset{p(x|s)}{\max} \big(I(X;Y) - I(X;S)\big),
\end{equation}

is achievable for the Gelfand–Pinsker problem. Gelfand and Pinsker's random coding scheme assigns, for each message $m$ and state sequence $s^n$, a codeword $x^n$ that is jointly typical with $s^n$ for some conditional pmf $p(x|s)$.

A Gelfand–Pinsker code $(g,\psi)$ for a channel with a state that is known noncausally at the encoder.

§.§ Coding Scheme

In what follows, we describe a coding scheme for the Gelfand–Pinsker problem $p(y \cond x,s)p(s)$ starting from a Slepian–Wolf code and a point-to-point channel code designed for a symmetric channel. To this end, let $S^n$ be the state sequence that is i.i.d. according to $p(s)$, and let $p(x \cond s)$  be a desired conditional distribution of the channel input given the state sequence[For example, $p(x\cond s)$ can be chosen to be the maximizer of (<ref>).].

Inspired by Gelfand and Pinsker's random coding scheme, the main idea of the proposed coding scheme for the Gelfand–Pinsker problem is to shape the channel input sequence according to the desired conditional distribution $p(x\cond s)$. At the same time, the channel input sequence should encode the message to the decoder. As we shall see, a key ingredient in achieving these two goals is the nested structure of a pair of linear codes. More specifically, the Gelfand–Pinsker coding scheme can be constructed from the following Lego bricks.
[SW $\to$ GP]
an $(n-k_1,n)$ linear Slepian–Wolf code $(H_1,\phi_1)$ for the problem

\[
p(x,y) = \sum_{s}p(s)p(x \cond s)p(y \cond x,s).
\]

Let $\cC_1$ be the codebook corresponding to $H_1$, and let $\eps$ be the average probability of error of the Slepian–Wolf code.

[P2P $\to$ GP]
a $(k_2,n)$ linear point-to-point channel code $(H_2,\phi_2)$ with codebook $\cC_2$ for the channel

\begin{equation} \label{eqn:gelfand_symmetrized}
\bar{p}(s,v \cond x) = p_{X,S}(x\oplus v, s).
\end{equation}

Let $\delta$ denote the shaping distance of the code $(H_2,\phi_2)$ with respect to the channel $\bar{p}$. Furthermore, we assume that the two codes are nested, i.e., $\cC_2 \subseteq \cC_1$.

Since $\cC_2 \subseteq \cC_1$, we will assume, without loss of generality, that $H_1$ is a submatrix of $H_2$, i.e., $H_2 = \begin{bmatrix}
\end{bmatrix}$ for some $(k_1-k_2)\times n$ matrix $Q$. Further, let $H_2 = \begin{bmatrix}A & B\end{bmatrix}$, where $B$ is nonsingular, and let $\wtilde{H}_2$ be as defined in Remark <ref>.

The channel $\bar{p}$ in (<ref>) is the symmetrized channel corresponding to the desired joint distribution $p(x,s)$.

A Gelfand–Pinsker coding scheme starting from a point-to-point channel code and a Slepian–Wolf code.

Fig. <ref> shows the block diagram of the Gelfand–Pinsker coding scheme, where $V_1^{n-k_1}$ is an i.i.d. $\BERN(1/2)$ random dither shared between the encoder and the decoder, and $V_2^n$ is an i.i.d. $\BERN(1/2)$ sequence generated independently at the encoder (not necessarily shared with the decoder). To simplify the notation, let us denote the input to the Gelfand–Pinsker encoder in Fig. <ref> by

\begin{equation} \label{eqn:zn}
Z^n \triangleq \begin{bmatrix}\bf 0 \\
\end{equation}

The coding scheme uses the decoding function $\phi_2$ to shape the channel input $X^n$ according to the desired distribution. To see why this holds in the construction of Fig. <ref>, let $U^n = Z^n \oplus V_2^n \oplus \wtilde{H}_2V_2^n$ denote one of the two inputs to $\phi_2$, where the second input is $S^n$. Notice that by Lemma <ref>, $V_2^n \oplus \wtilde{H}_2V_2^n \, \sim \Unif(\cC_2)$, and $U^n$ is i.i.d. $\BERN(1/2)$ (and independent of $S^n$). Hence, by Lemma <ref>, the sequence $X^n =\phi_2(S^n,U^n)\oplus U^n$ satisfies that

\begin{equation} \label{eqn:gelfand}
\frac{1}{2}\sum_{x^n,s^n} \left| \P\{X^n = x^n, S^n=s^n\} - \prod_{i=1}^n p(x_i, s_i) \right| \, \leq \delta,
\end{equation}

and thus, the distribution of $(X^n,S^n)$ is $\delta$-away in total variation distance from the desired joint distribution.

Moreover, it holds that

\begin{equation*}
\begin{aligned}
\begin{bmatrix}
H_1X^n \\
\end{bmatrix} &= H_2X^n = H_2U^n \overset{(a)}{=} H_2Z^n \\
&= \begin{bmatrix}
A & B
\end{bmatrix}\begin{bmatrix}
\bf 0 \\
\end{bmatrix} = \begin{bmatrix}V_1^{n-k_1}\\
\end{aligned}
\end{equation*}

where $(a)$ follows since $V_2^n \oplus \wtilde{H}_2V_2^n \in \cC_2$. Therefore, $H_1X^n = V_1^{n-k_1}$, which is the index inputted to the Slepian–Wolf decoder $\phi_1$ at the decoder side.

Intuitively, the Gelfand–Pinsker construction can be understood as follows. The sequence $V_1^{n-k_1}$ represents a coset shift of the outer code $\cC_1$, whereas the message $M^{k_1-k_2}$ represents a coset shift of the inner code $\cC_2$ within the outer code. Since $H_2X^n = H_2Z^n$ (by construction), the channel input $X^n$ belongs to the coset of the inner code $\cC_2$ indexed by $(V_1^{n-k_1}, M^{k_1-k_2})$. Since the sequence $V_1^{n-k_1}$ is shared between the encoder and the decoder, and due to the nested structure of the two codes, the coset shift with respect to the outer code $\cC_1$ is known to the decoder, which can be leveraged by the Slepian–Wolf decoder to recover an estimate of the channel input sequence, and, hence, the message. Note that the idea of using such a nested structure to code over a Gelfand–Pinsker channel has been considered in [31], where a joint typicality encoder and decoder was used.

Therefore, the coding scheme can be summarized as follows.

Encoding: To transmit the message $m^{k_1-k_2}$ upon observing the state sequence $s^n$, the encoder computes the sequence $z^n$ as in (<ref>) using a random dither $v_1^{n-k_1}$ shared with the decoder, and sends $x^n = \phi_2(s^n, z^n \oplus v_2^n \oplus \wtilde{H}_2v_2^n) \oplus z^n \oplus v_2^n \oplus \wtilde{H}_2v_2^n$ over the channel, where $v_2^n$ is a random dither generated independently at the encoder.

Decoding: Upon observing the channel output $y^n$, the decoder computes $\hat{x}^n = \phi_1\left(\begin{bmatrix}\bf 0 \\ v_1^{n-k_1}\end{bmatrix}, y^n\right)$, and declares $\hat{m}^{k_1-k_2} = Q\hat{x}^n$ as the message estimate.

Analysis of the probability of error: Let $q(x^n,s^n)$ be the distribution of $(X^n,S^n)$ in Fig. <ref>, and let $p(x^n,s^n)$ be the i.i.d. distribution according to $p(x,s)$. The average probability of error can be bounded as

\begin{align}
&\P\{\widehat{M}^{k_1-k_2} \neq M^{k_1-k_2}\} \leq \P\{\widehat{X}^n \neq X^n\}  \nonumber \\
&=\hspace*{-0.2em}\sum_{x^n,s^n} \hspace*{-0.2em}\P\{\widehat{X}^n \hspace*{-0.2em}\neq \hspace*{-0.2em}X^n | X^n\hspace*{-0.2em}=\hspace*{-0.2em}x^n, S^n\hspace*{-0.2em}=\hspace*{-0.2em}s^n\} q(x^n,s^n)  \nonumber \\
&=\hspace*{-0.2em} \sum_{x^n,s^n} \hspace*{-0.2em}\P\{\widehat{X}^n \hspace*{-0.2em}\neq X^n\hspace*{-0.2em} | X^n\hspace*{-0.2em}=\hspace*{-0.2em}x^n, S^n\hspace*{-0.2em}=\hspace*{-0.2em}s^n\}\big(q(x^n,s^n) - p(x^n,s^n) \big)\nonumber \\
&\quad +\sum_{x^n,s^n}\P\{\widehat{X}^n \hspace*{-0.2em}\neq\hspace*{-0.2em} X^n | X^n\hspace*{-0.2em}=\hspace*{-0.2em}x^n, S^n\hspace*{-0.2em}=\hspace*{-0.2em}s^n\}p(x^n,s^n) \nonumber \\
&\overset{(a)}{\leq} \frac{1}{2}\sum_{x^n,s^n} \big| q(x^n,s^n) - p(x^n,s^n) \big| + \epsilon \nonumber \\
&\overset{(b)}{\leq} \delta + \epsilon,
\end{align}

where $(a)$ holds since $\sum_{i}c_i(a_i -b_i) \leq \frac{1}{2}\sum_{i}\left|a_i-b_i\right|$ whenever $0\leq c_i \leq 1$ and $\sum_{i}a_i = \sum_{i}b_i$ and by the fact that $\P\{\widehat{X}^n \neq X^n | X^n=x^n, S^n=s^n\}$ depends only on the channel $p(y|x,s)$, and $(b)$ follows by equation (<ref>).

Rate: The rate of the coding scheme is $R = \frac{k_1-k_2}{n}$.

Recall from Section <ref> and Remark <ref> that a sequence of point-to-point channel codes with a vanishing shaping distance $\delta$ over the channel $\bar{p}$ defined in (<ref>) exists if (and only if) the rate is larger than $1-H(X\cond S)$.

If the rate of the point-to-point channel code is $\frac{k_2}{n} = 1-H(X \cond S) + \gamma_1$ for some $\gamma_1 > 0$, and the rate of the Slepian–Wolf code is $\frac{n-k_1}{n} = H(X \cond Y) + \gamma_2$ for some $\gamma_2 > 0$, then the rate of the Gelfand–Pinsker coding scheme is

\begin{equation*}
\begin{aligned}
R=\frac{k_1-k_2}{n} &= H(X \cond S) - H(X \cond Y) - \gamma_1 - \gamma_2 \\
&= I(X;Y) - I(X;S) - \gamma_1 - \gamma_2.
\end{aligned}
\end{equation*}

Conclusion: Starting from an $(n-k_1,n)$ Slepian–Wolf code with an average probability of error $\eps$ and a $(k_2,n)$ linear point-to-point channel code with shaping distance $\delta$, we have constructed a $(\frac{k_1-k_2}{n},n)$ Gelfand–Pinsker code that targets a conditional distribution $p(x \cond s)$ of the channel input given the channel state and has an average probability of error that is bounded by $\delta+\eps$.

§.§ Simulation Results

In this part, we simulate the performance of the Gelfand–Pinsker coding scheme over a binary-input Gaussian channel with a binary state. The channel output can be expressed as

\begin{equation} \label{eqn:gelfand_simulation_model}
Y = X + gS + Z,
\end{equation}

where $X \in \{-\sqrt{P},\sqrt{P}\}$ is the channel input, $S \in \{-\sqrt{P},\sqrt{P}\}$ is a channel state that is known noncausally only at the encoder with $\P\{S = -\sqrt{P}\} = \theta$, and $Z \sim \cN(0,1)$ is a sample from an i.i.d. Gaussian noise process. In our simulations, we use $g = 0.9$ and $\theta = 0.1$.

By constructing the Slepian–Wolf code $(H_1,\phi_1)$ using its constituent point-to-point code (as described in Section <ref>), the Gelfand–Pinsker coding scheme can be implemented using two point-to-point channel codes. Inspired by the characterization (<ref>) of achievable rates for the Gelfand–Pinsker problem, the proposed coding scheme targets the the conditional distribution $p^{*}(x \cond s)$ that maximizes $I(X;Y)- I(X;S)$, i.e.,

\begin{equation} \label{eqn:gelfand_optimization}
p^{*}(x \cond s) = \underset{p(x \cond s)}{\arg\max} \left( I(X;Y)- I(X;S) \right).
\end{equation}

Since $X$ and $S$ are binary, the optimization (<ref>) can be solved efficiently using off-the-shelf numerical solvers (or simply using a grid search over the two parameters that define $p(x\cond s)$). We compare the proposed coding scheme with the simple strategy that encodes the transmitter's message using a point-to-point channel code while ignoring the available state sequence. Since the induced channel input distribution would be $\BERN(1/2)$ in this case, we refer to this strategy as the “symmetric coding” strategy.

We first look at the maximum achievable rate of the two coding strategies as a function of the power level $P$. For the proposed Gelfand–Pinsker coding scheme, the maximum achievable rate is given by

\[
C_{\mathrm{GP}} \triangleq \underset{p(x \cond s)}{\max} \left( I(X;Y)- I(X;S) \right),
\]

whereas the maximum achievable rate of the symmetric coding strategy is $C_{\mathrm{sym}} \triangleq I(X;Y)$, which is evaluated when $X$ is $\BERN(1/2)$ and independent of $S$. The solid lines in Fig. <ref> show the plots of $C_{\mathrm{GP}}$ and $C_{\mathrm{sym}}$ as a function of $P$. The plots demonstrate that, in theory, Gelfand–Pinsker coding can achieve larger rates asymptotically compared to the symmetric coding strategy.

Achieved rates of the Gelfand–Pinsker coding scheme at a fixed block error probability $P_e^{\mathrm{threshold}} = 10^{-2}$.

Before we describe what is meant by the dashed curves of Fig. <ref>, we shift our attention to evaluating the block error rate performance of the two coding strategies over the channel model (<ref>). The coding strategies are compared for the same block length $n=1024$ and rate $R=0.5$. We use polar codes with successive cancellation decoding as the constituent point-to-point channel codes. To ensure nestedness of the constituent codes in the proposed Gelfand–Pinsker coding scheme, the information set of the polar code corresponding to $(H_2,\phi_2)$ is taken to be a subset of that corresponding to the code $(H_1,\phi_1)$. Let $R_1$ and $R_2$ be the rates of the two polar codes. The rates $R_1$ and $R_2$ are chosen “close” to their theoretical limits (see Remark <ref>) when the conditional distribution of the channel input given the channel state is $p^{*}(x \cond s)$. More precisely, we take

\begin{equation} \label{eqn:gelfand_rates}
\begin{aligned}
R_1 &= 1-H(X\cond Y)-\gamma,\\
R_2 &= 1-H(X\cond S),
\end{aligned}
\end{equation}

where $\gamma > 0$ is a “back-off” parameter from the theoretical limit, which allows for a reasonable error probability for the code $(H_1,\phi_1)$. In our Gelfand–Pinsker simulations, we used $\gamma = 3/16$. Note that for the symmetric coding strategy, the polar code is designed for the average channel $p_{\mathrm{avg}}(y \cond x) \triangleq \sum_{s}p(s)p(y \cond x, s)$. Fig. <ref> shows the block error rate performance of the two coding strategies. The Gelfand–Pinsker coding scheme shows significant performance gain compared to symmetric coding.

By repeating the same experiment for different values of the rate $R$, one can plot $R$ as a function of the power level $P$, for a fixed block error probability $P_e^{\mathrm{threshold}}= 10^{-2}$. This is shown in the dashed curves of Fig. <ref>. For example, for a rate $R=0.5$, we know from Fig. <ref> that the Gelfand–Pinkser coding scheme achieves an error probability of $10^{-2}$ when the power level is around 4 dB, whereas the symmetric coding scheme has an error probability of $10^{-2}$ when the power level is around 5.5 dB. A similar approach is taken for other values of $R$. The dashed curves of Fig. <ref> show that the Gelfand–Pinsker coding scheme can achieve larger rates in practice (i.e., the gain from Gelfand–Pinsker coding is not only theoretical). These results demonstrate the performance gain from “shaping” the channel input with respect to the known state sequence. For more details about the simulation setup, our code is available on GitHub [63].

Simulation results of the Gelfand–Pinsker coding scheme for a block length $n=1024$ and rate $R = 0.5$ over a Gaussian channel with state.

Note that the symmetric coding scheme can be implemented as an instance of the Gelfand–Pinsker coding scheme (Fig. <ref>) for the case when $R_2=0$. Therefore, the simulation results here demonstrate that using strictly positive rates $R_2$ to target the conditional pmf $p^{*}(x \cond s)$ can achieve superior performance compared to the naive approach of coding for the average channel $p_{\mathrm{avg}}$.

§.§ Specialization to Asymmetric Channel Coding

The problem of coding for an asymmetric point-to-point channel (Section <ref>) can be seen as a special case of the Gelfand–Pinkser coding problem when the channel state is constant and independent of the channel output. This observation has been previously formalized in [40]. For completion, we give the details here, along with the resulting construction of an asymmetric channel coding scheme.

Suppose we have an $(R,n)$ code $(g,\psi)$ for the binary-input Gelfand–Pinsker problem $p(y \cond x,s)p(s)$, where $p(y\cond x,s)=p(y \cond x)$ (i.e., the channel output is independent of the state given the channel input) and $p_S(0) = 1$. Let $\eps$ be the average probability of error of the code. Define $f:[2^{nR}] \to \{0,1\}^n$ by $f(m) = g(m, {\bf 0})$. Then, $(f,\psi)$ forms a code for the channel $p(y \cond x)$ with length $n$, rate $R$ and average probability of error

\begin{align*}
&\sum_{m}2^{-nR}.\P\{\psi(Y^n) \neq m \cond X^n = f(m) \}\\
&= \hspace*{-0.2em}\sum_{m}2^{-nR}.\P\{\psi(Y^n) \neq m \cond X^n \hspace*{-0.2em}=\hspace*{-0.2em} g(m,{\bf 0}) \}\\
&= \hspace*{-0.2em}\sum_{m}2^{-nR}\Big(\P\{\psi(Y^n) \neq m \cond X^n \hspace*{-0.2em}= \hspace*{-0.2em}g(m,{\bf 0}), S^n \hspace*{-0.2em}= \hspace*{-0.2em}{\bf 0} \}\prod_{i=1}^n p_S(0) \\
&\quad + \sum_{s^n \neq {\bf 0}} \P\{\psi(Y^n) \neq m \cond X^n \hspace*{-0.2em}=\hspace*{-0.2em} g(m,{\bf 0}), S^n \hspace*{-0.2em}= \hspace*{-0.2em}s^n\}\prod_{i=1}^n p_S(s_i)\Big)\\
&\overset{(a)}{=} \hspace*{-0.2em}\sum_{m}2^{-nR}\P\{\psi(Y^n) \neq m \cond X^n \hspace*{-0.2em}= \hspace*{-0.2em}g(m,{\bf 0}), S^n \hspace*{-0.2em}= \hspace*{-0.2em}{\bf 0} \} \\
&\overset{(b)}{=} \hspace*{-0.2em}\sum_{m}2^{-nR}\Big(\P\{\psi(Y^n) \neq m \cond X^n \hspace*{-0.2em}= \hspace*{-0.2em}g(m,{\bf 0}), S^n \hspace*{-0.2em}= \hspace*{-0.2em}{\bf 0} \}\prod_{i=1}^n p_S(0) \\
&\quad+ \sum_{s^n \neq {\bf 0}} \P\{\psi(Y^n) \neq m \cond X^n \hspace*{-0.2em}= \hspace*{-0.2em}g(m,s^n), S^n \hspace*{-0.2em}= \hspace*{-0.2em}s^n\}\prod_{i=1}^n p_S(s_i)\Big)\\
&= \hspace*{-0.2em}\sum_{m, s^n}2^{-nR}\P\{\psi(Y^n) \neq m \cond X^n \hspace*{-0.2em}= \hspace*{-0.2em}g(m,s^n), S^n \hspace*{-0.2em}= \hspace*{-0.2em}s^n\}\prod_{i=1}^n p_S(s_i) \\
&= \eps,
\end{align*}

where $(a)$ and $(b)$ follow since $\prod_{i=1}^n p_S(s_i) = 0$ for $s^n \neq {\bf 0}$.

Therefore, the Gelfand–Pinsker coding scheme described in Section <ref> can be used to construct an asymmetric channel code in the special case when the state sequence is the constant all-zero sequence, i.e., $p_S(0)=1$. To this end, consider a binary-input channel $p(y \cond x)$ that is not necessarily symmetric. Let the desired input distribution be $p(x) \sim \BERN(\alpha)$ for some $\alpha \in (0,1/2)$. By specializing the Lego bricks of the Gelfand–Pinsker coding scheme to the case when $p_S(0)=1$ and the desired $p(x\cond s)$ is $\BSC(\alpha)$, the asymmetric channel coding scheme can be constructed using the following Lego bricks.

[SW $\to$ Asym]
an $(n-k_1,n)$ linear Slepian–Wolf code $(H_1,\phi_1)$ for the problem $p(x,y) = p(x)p(y \cond x)$ with codebook $\cC_1$ and average probability of error $\eps$.

[P2P $\to$ Asym]
a $(k_2,n)$ linear point-to-point channel code $(H_2,\phi_2)$ for $\mathrm{BSC}(\alpha)$ with codebook $\cC_2$ and shaping distance $\delta$. Furthermore, we assume that the two codes are nested, i.e., $\cC_2 \subseteq \cC_1$.

As before, it is assumed that $H_1$ is a submatrix of $H_2$, i.e., $H_2 = \begin{bmatrix}
\end{bmatrix}$ for some $(k_1-k_2)\times n$ matrix $Q$, and $H_2 = \begin{bmatrix}A & B\end{bmatrix}$, for some non-singular matrix $B$.

Fig. <ref> shows the block diagram for the asymmetric channel coding scheme, which can be seen as a specialization of the Gelfand–Pinsker coding scheme when the state sequence is the constant all-zero sequence. The description of the coding scheme and the analysis of its probability of error follow similarly as in the Gelfand–Pinsker case.

If the rate of the point-to-point channel code is $\frac{k_2}{n} = 1-H(X) + \gamma_1$ for some $\gamma_1 > 0$, and the rate of the Slepian–Wolf code is $\frac{n-k_1}{n} = H(X \cond Y) + \gamma_2$ for some $\gamma_2 > 0$, then the rate of the asymmetric channel coding scheme is

\[
\frac{k_1-k_2}{n} = I(X;Y) - \gamma_1 - \gamma_2.
\]

A coding scheme for an asymmetric channel starting from a Slepian–Wolf code and a point-to-point channel code.

The asymmetric channel encoder shown in Fig. <ref> is almost identical to the lossy source decoder shown in Fig. <ref> (when the constituent lossless source decoder is implemented using a point-to-point channel code). Similarly, the lossy source encoder is almost identical to the asymmetric channel decoder (when the constituent Slepian–Wolf decoder is implemented using a point-to-point channel code). This suggests some form of duality between the two constructions. A similar observation can be made between the Gelfand–Pinsker and Wyner–Ziv constructions.

Conclusion: Starting from an $(n-k_1,n)$ Slepian–Wolf code with an average probability of error $\eps$ and a $(k_2,n)$ linear point-to-point channel code with shaping distance $\delta$, we have constructed a $(k_1-k_2,n)$ code for an asymmetric point-to-point channel that targets an input distribution $p(x)$ and has an average probability of error that is bounded by $\delta+\eps$.

§ BLOCK-MARKOV CONSTRUCTIONS

In the constructions we presented so far in this paper, the shaping distance of a point-to-point channel code designed for a BMS channel was used as a primitive property in one of the constituent Lego bricks. Unfortunately, the shaping distance is difficult to be estimated for commercial off-the-shelf codes since it involves the computation of the total variation distance between distributions over exponentially large alphabets. To circumvent this inconvenience, we present in this section modified coding schemes involving properties that are easily verifiable in practice. More precisely, our assumptions in this section will be over alphabets with size that is at most polynomial in the block length. Moreover, the coding schemes presented here will not make assumptions of nestedness between the constituent Lego bricks, which was often assumed in the constructions thus far. However, as we shall see, these benefits will come at the cost of larger implementation complexity, a small penalty incurred in achievable rates, and a worse performance guarantee. In particular, the coding schemes presented in this section will have a block-Markov structure, i.e., they will be defined upon the transmission of several blocks of information and the inputs to one encoding/decoding block can depend on the outputs of previous blocks.

The following definitions will be used in the block-Markov constructions of coding schemes.

Given a linear point-to-point channel code $(H,\phi)$ for a binary-input binary-output channel $p(y \cond x)$, the shaping Hamming distance spectrum $W$ is defined as

\[
W \triangleq d_H\big(V^n, \phi(V^n)\big),
\]

where $V^n$ is i.i.d. $\mathrm{Bern}(1/2)$, and $d_H(.,.)$ denotes the Hamming distance metric. Therefore, we have that $W \in \{0,1,\ldots, n\}$, and

\[
\P\{W=w\} = \frac{\abs{\{v^n \in \mathbb{F}_2^n: d_H\big(v^n,\phi(v^n)\big) = w\}}}{2^n},
\]

for $0\leq w\leq n$.

Given a pair of sequences $(x^n,y^n)\in \cX^n\times \cY^n$, the joint-type of $(x^n,y^n)$, denoted $\mathrm{type}(x^n,y^n)$, is the number of occurrence of each symbol pair $(x,y)\in\cX\times \cY$ in $(x^n,y^n)$, i.e.,

\[
\mathrm{type}(x^n,y^n) = \left( \pi(x,y \cond x^n,y^n) \right)_{(x,y)\in \cX \times \cY},
\]

where $\pi(x,y \cond x^n,y^n) = \abs{\{i: 1\leq i \leq n, \, x_i=x, \, y_i=y\}}$.

Consider a symmetric binary-input channel $p(y \cond x)$ and a linear point-to-point channel code $(H,\phi)$. Let $Y^n$ be an i.i.d. according to $p(y)$, where $p(y) = \sum_{x}\frac{1}{2}p(y \cond x)$, and define $X^n = \phi(Y^n)$. The shaping joint-type spectrum $T$ is defined as the joint-type of the pair $(X^n,Y^n)$, i.e.,

\[
T \triangleq \mathrm{type}(X^n,Y^n).
\]

For example, if $\cY = \{0,1\}$, then $T = (T_{00},T_{01},T_{10},T_{11})$, where $T_{xy}$ is the number of occurrences of the symbol pair $(x,y)$ in the sequences $(X^n,Y^n)$, for $x,y \in \{0,1\}$.

The modified coding schemes presented in this section are based on the distributions of $W$ and $T$. The assumptions are easily-verifiable in practice since the distributions of $W$ and $T$ can be estimated efficiently for any commercial off-the-shelf code via Monte Carlo simulations. It turns out that all the previous constructions can be modified to work under these simplified assumptions. For conciseness, however, we will only focus on two problems: the asymmetric channel coding problem and the lossy source coding problem for an asymmetric source.

§.§ Asymmetric Channel Coding

Consider the problem of coding for a binary-input asymmetric channel $p(y\cond x)$, where the capacity-achieving input distribution is $p(x) \sim \mathrm{Bern}(\alpha)$ for some $\alpha \in (0,1/2)$. The coding scheme we present here is defined upon the transmission of $b$ blocks of information for some fixed $b$, and is constructed starting from the following three Lego bricks.

[SW $\to$ Asym]
an $(n-k_1,n)$ linear Slepian–Wolf code $(H_1,\phi_1)$ for the problem $p(x,y) = p(x)p(y \cond x)$ with an average probability of error $\eps$.

[P2P $\to$ Asym]
a $(k_2,n)$ linear point-to-point channel code $(H_2,\phi_2)$ for $\mathrm{BSC}(\alpha)$ with a shaping Hamming distance spectrum $W_2$ satisfying

\begin{equation} \label{eqn:tv_asym_bm}
\frac{1}{2}\sum_{w=0}^n \Big| \P\{W_2=w\} - \binom{n}{w}\alpha^{w}(1-\alpha)^{n-w} \Big| \, \leq \delta,
\end{equation}

for some $\delta > 0$. We assume that $k_2 < k_1$.

[P2P $\to$ Asym]
a $(k_{\mathrm{sym}},n)$ point-to-point channel code $(f_{\mathrm{sym}},\phi_{\mathrm{sym}})$ for the channel $p(y|x)$ with average probability of error $\eps_{\mathrm{sym}}$.[For example, one can use any code that approaches the symmetric capacity of the channel. Note that this code will be used only in the first transmission block.]

Since the alphabet size of $W_2$ is linear in $n$, the distribution of $W_2$ can be estimated for any off-the-shelf channel code via simulations. Hence, condition (<ref>) is easily verifiable in practice. In words, this condition states that the distribution of the shaping Hamming distance spectrum is $\delta$-away in total variation distance from a $\mathrm{Binom}(n,\alpha)$ distribution.

A block-Markov coding scheme for an asymmetric channel in the first transmission block using the code $(f_{\mathrm{sym}}, \phi_{\mathrm{sym}})$.

Now, we are ready to describe the coding scheme. For each $j\in [b]$, let $V_{(j)}^n$ be an i.i.d. $\BERN(1/2)$ random dither shared between the encoder and the decoder, and let $\Gamma_{(j)}:[n] \to [n]$ be a permutation chosen uniformly at random and shared between the encoder and the decoder.  We describe the encoding procedure starting from the $b$th block. Given a message $M_{(b)} \in \{0,1\}^{n-k_2}$, the encoder computes the sequence $Z_{(b)}^n$ as follows.

\begin{equation} \label{eqn:asym_bm_zb}
Z_{(b)}^n = \begin{bmatrix}
{\bf 0} \\
\end{bmatrix},
\end{equation}

where ${\bf 0}$ consists of $k_2$ zeros. Then, for each $j = b,\ldots, 2$, the encoder computes the sequences $\wtilde{X}_{(j)}^n$, $X_{(j)}^n$ and $Z_{(j-1)}^n$ as follows.

\begin{equation} \label{eqn:asym_bm_zj}
\begin{aligned}
\wtilde{X}_{(j)}^n &= \phi_2\big(Z_{(j)}^n \oplus V_{(j)}^n\big) \oplus Z_{(j)}^n \oplus V_{(j)}^n, \\
X_{(j)}^n  &= \Gamma_{(j)}\left(\wtilde{X}_{(j)}^n\right), \\
Z_{(j-1)}^n &= \begin{bmatrix}
{\bf 0} \\
H_1X_{(j)}^n \\
\end{bmatrix},
\end{aligned}
\end{equation}

where $M_{(j-1)} \in \{0,1\}^{k_1-k_2}$. Note that the sequence $Z_{(j-1)}^n$ in the $(j-1)$-th transmission block depends on the syndrome vector corresponding to the channel input $X_{(j)}^n$ in the $j$th block. Furthermore, notice that the sequences $Z_{(j)}^n$ satisfy that $\wtilde{H}_2 Z_{(j)}^n = Z_{(j)}^n$ for each $j =2,\ldots, b$, where $\wtilde{H}_2$ is as defined in (<ref>). Finally, in the first block, the transmitter uses the encoder $f_{\mathrm{sym}}$ to encode the syndrome vector $H_1X_{(2)}^n$, where $X_{(2)}^n$ is the transmitted sequence in the second block. Fig. <ref> and Fig. <ref> show the block diagrams of the coding scheme in the first block and the remaining blocks, respectively. Note that a loss in the overall rate is incurred in the first block, where no message is transmitted. However, this loss decays as $1/b$, and, thus, by choosing $b$ large enough, the rate loss becomes negligible.

A block-Markov coding scheme for an asymmetric channel in the $j$th transmission block, for $2\leq j \leq b-1$.

The following lemma states that under this construction, the distribution of the channel input $X_{(j)}^n$ is $\delta$-away in total variation distance from the i.i.d. $\BERN(\alpha)$ distribution, for each $j=2,\ldots,b$.

For the arrangement shown in Fig. <ref>, we have

\begin{equation*}
\frac{1}{2}\sum_{x^n} \left| \P\{X_{(j)}^n= x^n \} -  \alpha^{\weight(x^n)}(1-\alpha)^{n-\weight(x^n)}\right| \leq \delta,
\end{equation*}

for each $j=2,\ldots,b$.

See Appendix <ref>.

At the decoder side, the coding scheme proceeds as follows. In the first transmission block, the decoder uses the decoder $\phi_{\mathrm{sym}}$ to get an estimate of $H_1X_{(2)}^n$. In the subsequent blocks, the decoder views $(X_{(j)}^n,Y_{(j)}^n)$ as realizations of the Slepian–Wolf problem $p(x,y)$, uses the Slepian–Wolf decoder $\phi_1$ to recover $X_{(j)}^n$ using the estimate of $H_1X_{(j)}^n$ from previous blocks, and then reverse-engineers the operations at the encoder to get an estimate of the transmitted message $M_{(j)}$ and the subsequent index $H_1X_{(j+1)}^n$.

For the probability of error of the coding scheme, consider the performance of a genie-aided decoder which recovers an estimate of $M_{(j)}$ in the $j$th block based on the channel output $Y_{(j)}^n$ and the syndrome vector $H_1X_{(j)}^n$ (which is supplied correctly by a genie regardless of any decoding errors in previous blocks). Notice that such a decoder would have the same probability of error over the $b$ blocks as our decoder. To see this, observe that a decoding error can propagate from one block to another only through an error in the syndrome vector $H_1X_{(j)}^n$. Consider the first block where such an error happens. Both decoders would make an error in that block, which is precisely an error event over the $b$ blocks, irrespective of decisions made in subsequent blocks. A similar argument has been made in the analysis of the successive cancellation decoding of polar codes [9]. Therefore, it suffices to analyze the error probability of the genie-aided decoder over the $b$ blocks of transmission. Using similar bounding techniques as before, the average probability of error of the genie-aided decoder in the $j$th block can be bounded as

\[
\P\{\widehat{M}_{(j)} \neq M_{(j)}\} \leq \delta + \eps,
\]

and, thus, the average probability of error of our coding scheme over the $b$ transmission blocks can be bounded using the union bound as

\begin{equation}
\P\left\{\widehat{M}_{(j)} \neq M_{(j)} \text{ for some } j \in [b]\right\} \leq (b-1)(\delta+\eps) + \eps_{\mathrm{sym}},
\end{equation}

where $\epsilon_{\mathrm{sym}}$ is the average probability of error of the code used in the first block. The rate of the coding scheme is given by

\[
R = \frac{(b-1)(k_1-k_2)+n-k_1}{nb}.
\]

A point-to-point channel code with a shaping Hamming distance spectrum that is arbitrarily close in total variation distance to a $\Binom(n,\alpha)$ distribution exists for sufficiently large $n$ if and only if the rate $k_2/n$ of the code is larger than $1-H(\alpha)=1-H(X)$. To show this, the same argument of Section <ref> based on distributed channel synthesis can be used. Similarly, a Slepian–Wolf code for $p(x,y)$ with arbitrarily small error probability exists for sufficiently large $n$ if and only if its rate $\frac{n-k_1}{n}$ is larger than $H(X\cond Y)$. It follows that the rate $R$ of the block-Markov asymmetric channel coding scheme can be made arbitrarily close to $I(X;Y)$ for sufficiently large $n$ and $b$.

§.§ Lossy Source Coding for an Asymmetric Source

Consider the problem of lossy source coding of a $\BERN(\theta)$ source for some $\theta \in (0,1/2)$, as defined in Section <ref>. In this part, we construct a coding scheme for this problem starting from a point-to-point channel code and a lossless source code that satisfy some easily-verifiable properties. The coding scheme will be defined upon its operation on $b$ blocks of source sequences. To this end, let $D$ be some desired distortion level, and $p(x \cond \hat{x}) \sim \mathrm{BSC}(D)$ be the desired conditional pmf of the source given the reconstruction. Under this conditional pmf, the distribution of the reconstruction is $p(\hat{x})\sim \BERN(\alpha)$, where

\[
\alpha = \frac{\theta-D}{1-2D}.
\]

The coding scheme is constructed using the following Lego bricks.

[P2P $\to$ Lossy]
a $(k_1,n)$ linear point-to-point channel code $(H_1,\phi_1)$ for the channel

\[
\bar{p}(x,v \cond \hat{x}) = p_{X,\widehat{X}}(x,\hat{x}\oplus v),
\]

such that the code's shaping joint-type spectrum $T$ satisfies

\begin{equation} \label{eqn:tv_lossy_asym_bm}
d_{TV}\big(T,\, \mathrm{Multinomial}(n;p_{000},\ldots,p_{111})\big) \leq \delta
\end{equation}

for some $\delta > 0$, where $d_{TV}$ denotes the total variation distance and

\[
p_{i_1i_2i_3} = \frac{1}{2}p_{X,\widehat{X}}(i_1,i_2\oplus i_3), \qquad i_1,i_2,i_3 \in \{0,1\}.
\]

[Lossless $\to$ Lossy]
an $(n-k_2,n)$ lossless source code $(H_2,\phi_2)$ for a $\BSC(\alpha)$ source with average probability of error $\eps$ such that $k_2 < k_1$.

Condition (<ref>) says that the distribution of $T$ is $\delta$-away in total variation distance from a multinomial distribution. This condition can be easily verified in practice since the distribution of $T$ can be estimated efficiently for any commercial off-the-shelf code. Recall that a multinomial random variable $M\sim \mathrm{Multinomial}(n;p_1,\ldots,p_K)$ models the number of counts of each side of a $K$-sided die when rolled $n$ times, where $p_1, \ldots, p_K$ are the probabilities of observing each side. We have

\[
\P\{M = (m_1,\ldots, m_K)\} = \frac{n!}{m_1! \cdots m_K!}p_1^{m_1}\cdots p_K^{m_K}
\]

for each $(m_1,\ldots,m_K)$ such that $\sum_{i=1}^{K}m_i = n$.

Let $P$ and $Q$ denote submatrices of $H_2$ such that $H_2 = \begin{bmatrix}P\\
\end{bmatrix}$, for some $(n-k_1) \times n$ matrix $P$ and $(k_1-k_2) \times n$ matrix $Q$.

Encoder of the block-Markov lossy source coding scheme in the $j$th coding block, for $2\leq j\leq b$.

Fig. <ref> shows the encoding scheme of the lossy source code, where $V_{(j)}^{n}$ is a random dither shared with the decoder, and $\Gamma_{(j)}$ is a random permutation chosen uniformly at random and shared with the decoder. Similar to the coding scheme of Section <ref>, the main idea is to use the available Lego bricks to generate a sequence $U_{(j)}^n$ with a distribution that is “close” to the i.i.d. $p(\hat{x})$ distribution and then convey the sequence “losslessly” to the decoder.

The encoding procedure starts from the $b$th block. For each $j = b,\ldots, 2$, the encoder computes the sequences $Z_{(j)}^n$, $\wtilde{U}_{(j)}^n$, and $U_{(j)}^n$ as follows.

\begin{equation} \label{eqn:lossy_bm_zj}
\begin{aligned}
Z_{(j)}^n &= \begin{bmatrix}\bf 0 \\
PU_{(j+1)}^n\end{bmatrix} \oplus V_{(j)}^{n},\\
\wtilde{U}_{(j)}^n &= \phi_1\left( \Gamma_{(j)}^{-1}(X_{(j)}^n), Z_{(j)}^n \right) \oplus Z_{(j)}^n,\\
U_{(j)}^n &= \Gamma_{(j)}(\wtilde{U}_{(j)}^n),
\end{aligned}
\end{equation}

where $PU_{(b+1)}^n = {\bf 0}^{n-k_1}$. Notice that, for each $j=2,\ldots, b$, we have

\begin{equation} \label{eqn:lossy_asym_BM_indexU}
\wtilde{H}_1\wtilde{U}_{(j)}^n = \wtilde{H}_1Z_{(j)}^n = \begin{bmatrix}\bf 0 \\
PU_{(j+1)}^n\end{bmatrix} \oplus \wtilde{H}_1V_{(j)}^{n}.
\end{equation}

The next lemma states that the distribution of $(X_{(j)}^n,U_{(j)}^n)$ in Fig. <ref> is $\delta$-away in total variation distance from the i.i.d. $p(x,\hat{x})$ distribution.

Let $q(x^n,u^n)$ be the true distribution of $(X_{(j)}^n,U_{(j)}^n)$. Then, we have

\begin{equation*}
\frac{1}{2}\sum_{x^n,u^n} \left| q(x^n,u^n) - \prod_{i=1}^n p_{X,\widehat{X}}(x_i,u_i) \right| \leq \delta,
\end{equation*}

for each $j=2,\ldots,b$.

See Appendix <ref>.

Decoder of the block-Markov lossy source code in the $j$th coding block, for $2\leq j\leq b-1$.

Fig. <ref> shows the decoding scheme of the lossy source code. The decoder uses the lossless source decoder and the estimate $\widehat{PU_{(j)}^n}$ of $PU_{(j)}^n$ which the decoder had found in previous coding blocks to compute the reconstruction sequence $\widehat{X}_{(j)}^n$. The decoder then reverse-engineers the operations at the encoder side and computes an estimate $\widehat{PU_{(j+1)}^n}$ for the subsequent coding block using the observation of (<ref>), as shown in Fig. <ref>. Using similar arguments as in Section <ref>, it can be shown that the average distortion of the coding scheme over the $b$ blocks can be bounded as

\begin{equation}
\frac{1}{b-1}\sum_{j=2}^{b} \frac{1}{n}\E[d_H(X_{(j)}^n,\widehat{X}_{(j)}^n)] \leq D+\delta+b\eps,
\end{equation}

where the factor $b$ in front of $\eps$ pertains to the use of the union bound on the error probability over $b$ blocks. In this analysis, we assume that in the first coding block, $PU_{(2)}^n$ is passed to the decoder error-free. The rate of the coding scheme is

\[
R = \frac{(b-1)(k_1-k_2)+n-k_1}{(b-1)n}.
\]

A point-to-point channel code with a shaping joint-type spectrum that is arbitrarily close in total variation distance to a multinomial distribution exists for sufficiently large $n$ if and only if the rate $k_1/n$ of the code is larger than $1-H(\widehat{X}\cond X)$. A similar argument as in Section <ref> based on distributed channel synthesis can be used to show this. Similarly, a lossless source code for a $\BERN(\alpha)$ source with arbitrarily small error probability exists for sufficiently large $n$ if and only if its rate $\frac{n-k_2}{n}$ is larger than $H(\alpha)=H(\widehat{X})$. It follows that the rate $R$ of the block-Markov lossy source coding scheme can be made arbitrarily close to $I(X;\widehat{X})$ for sufficiently large $n$ and $b$.

§.§ Other Coding Problems

The two coding schemes presented in Sections <ref> and <ref> for the asymmetric channel coding problem and the lossy source coding problem were constructed starting from Lego bricks that satisfy some easily-verifiable properties. In a similar way, all other coding schemes presented in this paper (including the ones in the appendices) can be modified to start from such Lego bricks. For conciseness, we do not explicitly show those constructions; however, the two constructions of Sections <ref> and <ref> already give the gist of the idea. To summarize, the following differences in comparison with the previous constructions are noted.

* The assumptions made on the Lego bricks of the modified constructions involve the distribution of either the shaping Hamming distance spectrum or the shaping joint-type spectrum of the constituent codes, both of which can be estimated efficiently in practice for any commercial off-the-shelf code.

* The modified constructions do not require any constituent codebooks to be nested, unlike the previous constructions which often assumed that the codebook corresponding to one Lego brick is a subcode of another.

* A uniformly chosen random permutation that is shared between the encoder and the decoder is used in the modified constructions. The random permutation allows to shape the binary sequences according to the desired distribution, as shown in Lemma <ref> and Lemma <ref>.

* The modified coding schemes have a block-Markov structure, i.e., the inputs to one encoding/decoding block can depend on other coding blocks. Such a structure allows to share information about the transmitted sequences across coding blocks.

* The block-Markov constructions require the storage of sequences from the previous or subsequent transmission block. That is, the encoding and decoding schemes have a window size of 2.

Since the block-Markov constructions do not require any constituent codebooks to be nested, one major consequence of the constructions is the following: one can assemble any set of point-to-point channel codes with good error correction capabilities (i.e., small probability of error) with any set of point-to-point channel codes with good shaping properties (i.e., a shaping Hamming distance spectrum that is “close” to a Binomial, or a shaping joint-type spectrum that is “close” to a Multinomial, where “closeness” is measured via the total variation distance metric) to construct coding schemes for the network settings considered in this paper. That is, the block-Markov constructions imply that one can combine any set of codes that have a vanishing error probability asymptotically (e.g., first column in Table <ref>) with any set of codes that have a vanishing shaping distance (e.g., second column in Table <ref>) to construct coding schemes that can achieve the best known inner bounds for the network coding problems considered in this paper.

§ CONCLUDING REMARKS

The Lego-brick framework developed in this paper is promising, and provides guidelines to implement practical coding schemes for network communication. The proposed code constructions can achieve larger rates in theory and demonstrate better performance in practice compared to the naive approach of coding over the point-to-point links of a network. Moreover, the computational complexity of the proposed constructions is governed by the encoding/decoding complexities of the constituent Lego bricks, which can be taken “off-the-shelf”; hence, the constructions are friendly to hardware implementation using existing coding blocks. Finally, we point out that all the coding schemes that we presented in this paper can be extended to general (i.e., non-binary) discrete channels and sources when using non-binary linear point-to-point channel codes. For example, if a multi-user channel has an input alphabet of size $q$, similar coding schemes to the ones presented in this paper can be constructed using linear point-to-point channel codes over $\mathbb{F}_q$.

For future work, it is of particular interest to implement such a generalization to non-binary channels (including Gaussian channels with continuous inputs) starting from binary point-to-point channel codes. In principle, this would allow one to establish a general framework for implementing coded modulation techniques for multi-user settings. Another direction that is inspired by this work is to investigate the “shaping distance” performance of point-to-point channel codes (compared to the more-prominently studied “error probability” performance). To the best of the knowledge of the authors, apart from polar codes, there are no other known low-complexity point-to-point channel codes with a provably vanishing shaping distance over BMS channels. Ultimately, the goal would be to construct new families of codes with that property. As we saw in this paper, this can be helpful for constructing rate-optimal coding schemes in multi-user settings.

§ PROOF OF LEMMA <REF>

* Let $x^n \in \{0,1\}^n$, and let $\wtilde{H}$ be as defined in (<ref>). Then $s^n \triangleq \wtilde{H}x^n \, \in \cS$, and

\begin{equation*}
\begin{aligned}
H(x^n \oplus s^n) &= Hx^n \oplus \begin{bmatrix}A & B\end{bmatrix} \begin{bmatrix}{\bf 0} & {\bf 0} \\
B^{-1}A & I
\end{bmatrix}x^n \\
&= Hx^n \oplus Hx^n = 0,
\end{aligned}
\end{equation*}

where $H = \begin{bmatrix}A & B\end{bmatrix}$ for some nonsingular matrix $B$. Therefore, $x^n \oplus s^n \in \cC$. Now, assume there exists $s_1^n, s_2^n \in \cS$, $s_1^n \neq s_2^n$, such that $x^n \oplus s_1^n \in \cC$ and $x^n \oplus s_2^n \in \cC$. Thus, $Hs_1^n = Hs_2^n$, which implies that $Bs_{1,k+1}^n = Bs_{2,k+1}^n$, and, therefore, $s_1^n=s_2^n$. A contradiction.

* Let $C^n = X^n\oplus \wtilde{H}X^n$. For any $c^n \in \cC$, we have

\begin{equation*}
\begin{aligned}
&\P\{C^n = c^n\} = \sum_{s^n \in \cS}\P\{X^n\oplus \widetilde{H}X^n = c^n, \widetilde{H}X^n = s^n\} \\
&= \hspace*{-0.1em}\sum_{s^n \in \cS}\P\{X^n \hspace*{-0.1em}= \hspace*{-0.1em}c^n\hspace*{-0.1em}\oplus\hspace*{-0.1em} s^n\} \P\{\widetilde{H}X^n \hspace*{-0.1em}=\hspace*{-0.1em} s^n \cond X^n \hspace*{-0.1em}=\hspace*{-0.1em} c^n\hspace*{-0.1em}\oplus \hspace*{-0.1em}s^n \} \\
&\overset{(a)}{=} \sum_{s^n \in \cS} \frac{1}{2^n} \\
&= \frac{1}{2^k},
\end{aligned}
\end{equation*}

where $(a)$ follows since for any $c^n \in \cC$ and $s^n \in \cS$, $\widetilde{H}(c^n \oplus s^n) = 0^n \oplus \begin{bmatrix}
{\bf 0} & {\bf 0} \\
B^{-1}A & I
\end{bmatrix}\begin{bmatrix}
0^k \\
\end{bmatrix} = s^n$.

* Let $V^n = C^n \oplus S^n$. For any $v^n \in \{0,1\}^n$, we have

\begin{align*}
\P\{V^n=v^n\} &= \sum_{s^n\in \cS} \P\{V^n=v^n, S^n=s^n\}\\
&= \sum_{s^n\in \cS} \P\{C^n=v^n \oplus s^n, S^n=s^n\}\\
&= \frac{1}{2^{n-k}} \sum_{s^n\in \cS} \P\{C^n=v^n \oplus s^n\}\\
&\overset{(a)}{=} \frac{1}{2^n},
\end{align*}

where $(a)$ follows by part (i).

§ PROOF OF LEMMA <REF>

Let $R^n = X^n \oplus V^n$. Thus, $C^n = R^n \oplus \widetilde{H}R^n$. Since $R^n$ is i.i.d. $\mathrm{Bern}(\frac{1}{2})$, it follows by Lemma <ref> that $C^n$ is uniformly distributed over $\cC$. Now, for any $y^n \in \cY^n$ and $u^n \in \{0,1\}^n$, we have

\begin{equation*}
\begin{aligned}
&\P\{Y^n\hspace*{-0.1em} =\hspace*{-0.1em} y^n, U^n\hspace*{-0.1em} =\hspace*{-0.1em} u^n \cond C^n\hspace*{-0.1em} =\hspace*{-0.1em} c^n\} \\
&=\P\{Y^n \hspace*{-0.1em}=\hspace*{-0.1em} y^n, V^n \hspace*{-0.1em}\oplus \hspace*{-0.1em}\widetilde{H}V^n\hspace*{-0.1em}\oplus\hspace*{-0.1em} \widetilde{H}X^n = u^n \cond \\
&\qquad \qquad \qquad \,\, X^n\hspace*{-0.1em} \oplus\hspace*{-0.1em} V^n\hspace*{-0.1em} \oplus \hspace*{-0.1em}\widetilde{H}X^n\hspace*{-0.1em}\oplus\hspace*{-0.1em} \widetilde{H}V^n \hspace*{-0.1em}=\hspace*{-0.1em} c^n\} \\
&= \P\{Y^n\hspace*{-0.1em} = \hspace*{-0.1em}y^n, X^n\hspace*{-0.1em} = \hspace*{-0.1em}c^n \hspace*{-0.1em}\oplus\hspace*{-0.1em} u^n \cond X^n \hspace*{-0.1em}\oplus \hspace*{-0.1em}V^n \hspace*{-0.1em}\oplus\hspace*{-0.1em} \widetilde{H}(X^n\oplus V^n) \hspace*{-0.1em}= \hspace*{-0.1em}c^n \}\\
&\overset{(b)}{=} \P\{Y^n \hspace*{-0.1em}= \hspace*{-0.1em}y^n, X^n \hspace*{-0.1em}= \hspace*{-0.1em}c^n \hspace*{-0.1em}\oplus\hspace*{-0.1em} u^n\} \\
&=\prod_{i=1}^n p_{X,Y}(c_i \oplus u_i, y_i) \\
&=\prod_{i=1}^n \bar{p}(y_i,u_i \cond c_i),
\end{aligned}
\end{equation*}

where $(b)$ follows since $R^n = X^n \oplus V^n$ is independent of $X^n$, which implies that $C^n$ and $(X^n,Y^n)$ are independent. This completes the proof.

§ PROOF OF LEMMA <REF>

\begin{equation} \label{eqn:lemma_shaping_distance}
\begin{aligned}
\delta &= \frac{1}{2}\sum_{\td{y}^n,\td{v}^n,\td{x}^n}\left|\P\{\td{Y}^n=\td{y}^n,\td{V}^n=\td{v}^n,\td{X}^n=\td{x}^n\} - \frac{1}{2^n}\prod_{i=1}^{n}\bar{p}(\td{y}_i,\td{v}_i \cond \td{x}_i)\right| \\
&= \frac{1}{2}\sum_{\td{y}^n,\td{v}^n,\td{x}^n}\left|\P\{\td{Y}^n=\td{y}^n,\td{V}^n=\td{v}^n,\td{U}^n=\td{x}^n \oplus \td{v}^n\} - \frac{1}{2^n}\prod_{i=1}^{n}p_{X,Y}(\td{x}_i \oplus \td{v}_i,\td{y}_i)\right| \\
&= \frac{1}{2}\sum_{\td{y}^n,\td{v}^n,\td{u}^n}\left|\P\{\td{Y}^n=\td{y}^n,\td{V}^n=\td{v}^n,\td{U}^n=\td{u}^n\} - \frac{1}{2^n}\prod_{i=1}^{n}p_{X,Y}(\td{u}_i,\td{x}_i)\right| \\
&\geq \frac{1}{2}\sum_{\td{y}^n,\td{u}^n}\left| \sum_{\td{v}^n}\left(\P\{\td{Y}^n=\td{y}^n,\td{V}^n=\td{v}^n,\td{U}^n=\td{u}^n\} - \frac{1}{2^n}\prod_{i=1}^{n}p_{X,Y}(\td{u}_i,\td{y}_i)\right)\right| \\
&= \frac{1}{2}\sum_{\td{y}^n,\td{u}^n}\left| \P\{\td{U}^n=\td{u}^n,\td{Y}^n=\td{y}^n\} - \prod_{i=1}^{n}p_{X,Y}(\td{u}_i,\td{y}_i)\right|
\end{aligned}
\end{equation}

Denote $\td{X}^n = \phi(\td{Y}^n,\td{V}^n)$. Thus, $\td{U}^n = \td{X}^n \oplus \td{V}^n$. The shaping distance $\delta$ of the code $(H,\phi)$ with respect to the channel $\bar{p}$ can be bounded as in equation (<ref>) at the bottom of this page.

§ PROOF OF LEMMA <REF>

Let $q(x^n,u^n,\hat{x}^n)$ be the joint distribution of $(X^n,U^n,\widehat{X}^n)$, and let $p(x^n,u^n,\hat{x}^n)$ be defined as

\[
p(x^n,u^n,\hat{x}^n) = \left(\prod_{i=1}^n p_{X,\widehat{X}}(x_i,u_i)\right) \mathbbm{1}_{\{\hat{x}^n=u^n\}}.
\]

In the block diagram of Fig. <ref>, since $U^n = \phi_1(X^n,V^n) \oplus V^n$, we have that $H_1U^n = H_1V^n$, and, thus, $\begin{bmatrix}
\bf 0 \\
\end{bmatrix} = \begin{bmatrix}\bf 0 \\ H_1U^n \\ QU^n\end{bmatrix} = \begin{bmatrix}\bf 0 \\ H_1V^n \\ M^{k_1-k_2}\end{bmatrix}$,

i.e., the input to the lossless source decoder is the index corresponding to $U^n$. It follows that

\begin{align*}
&\frac{1}{2}\sum_{x^n,\hat{x}^n}\left| q(x^n,\hat{x}^n) - p(x^n,\hat{x}^n) \right| \\
&\leq \frac{1}{2}\sum_{x^n,u^n,\hat{x}^n}\left| q(x^n,u^n,\hat{x}^n) - p(x^n,u^n,\hat{x}^n) \right| \\
&\leq \frac{1}{2}\sum_{x^n,u^n,\hat{x}^n} \left| q(x^n,u^n) - p(x^n,u^n)\right|q(\hat{x}^n \cond x^n,u^n) \\
&\quad + \frac{1}{2}\sum_{x^n,u^n,\hat{x}^n} p(x^n,u^n) \left| q(\hat{x}^n \cond x^n,u^n) - \mathbbm{1}_{\{u^n=\hat{x}^n\}} \right|\\
&= \frac{1}{2}\sum_{x^n,u^n} \left| q(x^n,u^n) - p(x^n,u^n)\right| \\
&\quad+  \frac{1}{2}\sum_{\substack{x^n,u^n,\hat{x}^n: \\ u^n\neq \hat{x}^n}}p(x^n,u^n) q(\hat{x}^n \cond x^n,u^n) \\
&\quad + \frac{1}{2}\sum_{x^n,u^n}p(x^n,u^n)\Big(1-q_{\widehat{X}^n \cond X^n,U^n}(u^n \cond x^n,u^n)\Big)\\
&\overset{(a)}{\leq} \delta + \frac{1}{2}\eps+\frac{1}{2}\eps\\
\end{align*}

where $(a)$ follows by Lemma <ref> and the definition of the probability of error of a lossless source code.

§ PROOF OF LEMMA <REF>

Consider the block diagram shown in Fig. <ref>. Since $Z_{(j)}^n \oplus V_{(j)}^n$ is i.i.d $\BERN(1/2)$ for each $j=2,\ldots,b$, then the sequence $\wtilde{X}_{(j)}^n$ satisfies that

\[
\weight(\wtilde{X}_{(j)}^n) = d_H\big(\phi_2(Z_{(j)}^n \oplus V_{(j)}^n), Z_{(j)}^n \oplus V_{(j)}^n \big) \: \overset{d}{=} W_2,
\]

where $\overset{d}{=}$ denotes equality in distribution and $W_2$ is the shaping Hamming distance spectrum of the code $(H_2,\phi_2)$. It follows that, for any sequence $x^n$ with $\mathrm{wt}(x^n) = w$, we have that

\begin{equation*}
\begin{aligned}
&\P\{X_{(j)}^n= x^n \} \\
&= \sum_{\widetilde{x}^n: \mathrm{wt}(\widetilde{x}^n) = w}\P\{\Gamma_{(j)}(\widetilde{x}^n) = x^n\}\P\{\widetilde{X}_{(j)}^n=\widetilde{x}^n\} \\
&= \sum_{\widetilde{x}^n: \mathrm{wt}(\widetilde{x}^n) = w} \frac{w!(n-w)!}{n!} \P\{\widetilde{X}_{(j)}^n=\widetilde{x}^n\}\\
&= \frac{1}{\binom{n}{w}}\P\{\weight\big(\widetilde{X}_{(j)}^n\big) = w\} = \frac{1}{\binom{n}{w}}\P\{W_2 = w\}.
\end{aligned}
\end{equation*}

\begin{equation*}
\begin{aligned}
&\frac{1}{2}\sum_{x^n} \left| \P\{X_{(j)}^n = x^n \} - \alpha^{\weight(x^n)}(1-\alpha)^{n-\weight(x^n)} \right| \\
&= \frac{1}{2}\sum_{x^n} \left| \frac{\P\{W_2 = \mathrm{wt}(x^n)\}}{\binom{n}{\mathrm{wt}(x^n)}} - \alpha^{\mathrm{wt}(x^n)}\big(1-\alpha\big)^{n-\mathrm{wt}(x^n)}  \right| \\
&= \frac{1}{2}\sum_{w=0}^{n} \left|\P\{W_2=w\} - \binom{n}{w}\alpha^w(1-\alpha)^{n-w} \right| \\
&\leq \delta,
\end{aligned}
\end{equation*}

where the last step holds since $W_2$ satisfies condition (<ref>).

§ PROOF OF LEMMA <REF>

\begin{equation*}
\begin{aligned}
&\frac{1}{2}\sum_{x^n,u^n} \left| q(x^n,u^n) - \prod_{i=1}^n p_{X,\widehat{X}}(x_i,u_i)\right| = \frac{1}{2}\hspace*{-0.25em}\sum_{\substack{t = (t_{00}, t_{01}, t_{10},t_{11}): \\ \sum t_{ij} = n}} \sum_{\substack{x^n,u^n: \\ \mathrm{type}(x^n,u^n) = t}} \left| q(x^n,u^n) - \prod_{i=1}^n p_{X,\widehat{X}}(x_i,u_i)\right| \\
&= \frac{1}{2}\hspace*{-0.25em}\sum_{\substack{t = (t_{00}, t_{01}, t_{10},t_{11}): \\ \sum t_{ij} = n}} \sum_{\substack{x^n,u^n: \\ \mathrm{type}(x^n,u^n) = t}} \left| \frac{t_{00}!t_{01}!t_{10}!t_{11}!}{n!} \P\left\{\mathrm{type}(\widetilde{X}_{(t)}^n,\widetilde{U}_{(t)}^n) = t\right\} - \prod_{i,j=0}^{1} p_{ij}^{t_{ij}}\right| \\
&= \frac{1}{2}\hspace*{-0.25em}\sum_{\substack{t = (t_{00}, t_{01}, t_{10},t_{11}): \\ \sum t_{ij} = n}} \left| \P\left\{\mathrm{type}(\widetilde{X}_{(t)}^n,\widetilde{U}_{(t)}^n) = t\right\} - \frac{n!}{t_{00}!t_{01}!t_{10}!t_{11}!}\prod_{i,j=0}^{1} p_{ij}^{t_{ij}}\right| \\
&\leq \delta
\end{aligned}
\end{equation*}

Consider the encoding scheme shown in Fig. <ref>. Denote $C_{(j)}^{n} = \phi_1(\wtilde{X}_{(j)}^n, Z_{(j)}^{n})$. Since $\wtilde{X}_{(j)}^n$ is i.i.d. according to $p(x)$ and $Z_{(j)}^{n}$ is i.i.d. $\BERN(1/2)$, and $(\wtilde{X}_{(j)}^n,Z_{(j)}^{n})$ are independent, we have that

\[
\mathrm{type}\left(C_{(j)}^{n}, (\wtilde{X}_{(j)}^n, Z_{(j)}^{n})\right)
\]

satisfies condition (<ref>). Since $\wtilde{U}_{(j)}^n = C_{(j)}^{n} \oplus Z_{(j)}^{n}$, it follows using standard bounding techniques that

\begin{equation} \label{eqn:tv_lossy_asym_BM_proof}
\begin{aligned}
d_{TV}\big(&\mathrm{type}(\wtilde{X}_{(j)}^n,\wtilde{U}_{(j)}^n), \\
&\mathrm{Multinomial}(n;p_{00},p_{01},p_{10}, p_{11})\big) \leq \delta,
\end{aligned}
\end{equation}

where $p_{ij} = p_{X,\widehat{X}}(i,j)$, for $i,j \in \{0,1\}$.

Now, let $(x^n,u^n)$ be a pair of sequences such that $\mathrm{type}(x^n,u^n) = t$, where $t \triangleq (t_{00}, t_{01},t_{10}, t_{11})$ such that $\sum_{i,j}t_{ij} = n$. Then, we have that

\begin{equation*}
\begin{aligned}
&q(x^n, u^n) \\
&= \hspace*{-1em}\sum_{\substack{(\widetilde{x}^n, \widetilde{u}^n): \\ \mathrm{type}(\widetilde{x}^n, \widetilde{u}^n) = t}}\hspace*{-1.5em}\P\{\Gamma(\widetilde{x}^n) \hspace*{-0.1em}= \hspace*{-0.1em}x^n, \Gamma(\widetilde{u}^n) \hspace*{-0.1em}= \hspace*{-0.1em}u^n\}\P\{\widetilde{X}_{(j)}^n \hspace*{-0.1em}= \hspace*{-0.1em}\widetilde{x}^n, \widetilde{U}_{(j)}^n\hspace*{-0.1em}=\hspace*{-0.1em}\widetilde{u}^n\} \\
&= \sum_{\substack{(\widetilde{x}^n, \widetilde{u}^n): \\ \mathrm{type}(\widetilde{x}^n, \widetilde{u}^n) = t}} \frac{t_{00}!t_{01}!t_{10}!t_{11}!}{n!}\P\{\widetilde{X}_{(j)}^n = \widetilde{x}^n, \widetilde{U}_{(j)}^n=\widetilde{u}^n\} \\
&= \frac{t_{00}!t_{01}!t_{10}!t_{11}!}{n!} \P\left\{\mathrm{type}(\widetilde{X}_{(t)}^n,\widetilde{U}_{(t)}^n) = t\right\}.
\end{aligned}
\end{equation*}

Lemma <ref> then follows from the sequence shown at the bottom of this page, where the last inequality holds from (<ref>).

§ CODING FOR MULTIPLE ACCESS CHANNELS

In this appendix, we describe a coding scheme for the multiple access channel that uses two asymmetric channel codes, along with a successive cancellation decoder. The coding scheme can achieve a corner point in the optimal rate region of the multiple access channel, provided that the constituent asymmetric channel codes are rate-optimal.

§.§ Problem Statement