Channel simulation

In information theory, channel simulation (also known as channel synthesis) refers to the setting where the encoder and the decoder wish to simulate a noisy channel using noiseless communication. It is the dual problem to channel coding which is the simulation of a noiseless communication channel using a noisy channel.

The $n$-letter setting

Consider a memoryless channel $P_{Y|X}$ to be simulated, where the input alphabet is ${𝒳}$ and the output alphabet is ${𝒴}$. A channel simulation scheme in the $n$-letter setting consists of an encoding function $f_n:{{𝒳}}^n\times {{𝒰}}_n\to [1:2^{nR}]$ (possibly randomized) and a decoding function $g_n:[1:2^{nR}]\times {{𝒰}}_n\to {{𝒴}}^n$ (possibly randomized), where ${{𝒰}}_n$ is the alphabet of the common randomness, and $R$ is the communication rate. Upon observing the input symbols $X^n=(X_1,\dots ,X_n)$ which is an i.i.d. sequence following $P_X$, and the common randomness $U_n\sim P_{U_n}$, the encoder sends $M=f_n(X^n,U_n)$ (consisting of $nR$ bits) to the decoder. The decoder outputs $Y^n=g_n(M,U_n)$ based on $M,U_n$. Our goal is to make $Y^n$ appear almost as if they are the outputs of the given memoryless channel $P_{Y|X}$ upon the inputs $X^n$, in the sense that the average total variation distance between the distribution $\prod _{i=1}^n{P}_X(x_i)P_{Y|X}(y_i|x_i)$ and the actual joint distribution of $X^n,Y^n$ induced by the scheme is small. In the asymptotic setting where $n\to \mathrm{\infty }$, we require the total variation distance to approach zero.

The central result of channel simulation is the reverse Shannon theorem, which states that if the common randomness is unlimited (we can choose any $P_{U_n}$), in the asymptotic setting $n\to \mathrm{\infty }$, the smallest possible rate $R$ is the mutual information $I(X;Y)$. This is the dual result to Shannon's noisy channel coding theorem. The smallest possible rate for the case with limited or no common randomness has also been characterized.

Channel simulation is closely related to lossy data compression and rate-distortion theory. One way to prove the achievability of the rate-distortion function $R(D)=\underset{P_{\hat{X}|X}:E[d(X,\hat{X})]\le D}{\min }I(X;\hat{X})$ is to simulate the channel $P_{\hat{X}|X}$, which requires a communication rate $I(X;\hat{X})$. An advantage of channel simulation over traditional lossy compression schemes is that the distribution of the output $Y^n$ can be controlled, which may improve the perceptual quality of the output.

The one-shot setting

Interestingly, channel simulation can be performed even if the length of the input is $n=1$. In this setting, we often allow $M$ to be in a prefix code rather than having a fixed length. Several schemes have been proposed. In particular, the strong functional representation lemma states that, with unlimited common randomness, channel simulation can be performed exactly (the total variation distance is zero) with an expected length of $M$ being at most $I(X;Y)+{\log }_2(I(X;Y)+2)+3$ bits, which is close to the asymptotic rate $I(X;Y)$.

Common approaches to the construction of channel simulation schemes include rejection sampling., importance sampling, dithering and Poisson point process

Applications

• Lossy data compression
• Communication complexity
• Machine learning
• Differential privacy

References

This article "Channel simulation" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Channel simulation. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• Exformation
• Channel use
• Deduction Theory
• Infonomics
• Informatics Practices
• Fungible information
• Murray polygon

---