Universal Codes

Notions of Universality

Universality w.r.t. channel types

* Different BMS channels with the same capacity
* A single code that performs well over these channels

Universality w.r.t. channel parameters

* Rateless codes perform well on one channel type with different capacities
* LT codes are universal for the single user scenario (for the erasure channel)
* Multi-user scenarios not studied

Universality w.r.t. the source correlation

* Encoder/Decoder do NOT depend on source statistics
* Coding performance is asymptotically the same
* Random coding is universal for the Slepian-Wolf problem
* Can be shown to be the same as universality w.r.t. channel types for symmetric correlation

System Model

We wish to transmit the outputs of two discrete memoryless correlated sources $\left(U_i^{(1)},U_i^{(2)}\right)$, for $i=1,2,\cdots,k$ to a central receiver through two independent discrete memoryless channels with capacities $C_1$ and $C_2$, respectively. We will assume that each channel can be parametrized by a single parameter $\epsilon_i$ for $i=1,2$ (e.g., the erasure probability or crossover probability). The two sources are not allowed to collaborate and, hence, they use two independent encoding functions which map the $k$ input symbols in to $n_1$ and $n_2$ output symbols, respectively. The rates of the encoders are given by $R_1 = k/n_1$ and $R_2 = k/n_2$.

In such a problem, it is clear that one has to take advantage of the correlation between the sources to reduce the required bandwidth to transmit the information to the central receiver. Thus, this joint source-channel coding problem can be seen to be an instance of Slepian-Wolf coding in the presence of a noisy channel. The sources can be reliably decoded at the receiver iff

(1)

\begin{align} \label{eq:sw} \begin{split} \frac{C_1 (\epsilon_1)}{R_1} &\geq \textnormal{H}\left(U^{(1)}|U^{(2)}\right) \\ \frac{C_2 (\epsilon_2)}{R_2} &\geq \textnormal{H}\left(U^{(2)}|U^{(1)}\right) \\ \frac{C_1 (\epsilon_1)}{R_1}+\frac{C_2 (\epsilon_2)}{R_2}&\geq \textnormal{H}\left(U^{(1)},U^{(2)}\right) \end{split} \end{align}

If $\epsilon_1$ and $\epsilon_2$ are known to transmitter 1 and transmitter 2 respectively, the encoding functions can be chosen to have rates governed by (\ref{eq:sw}). Hence, the problem becomes one of Slepian-Wolf coding of the two sources at rates $R_1$ and $R_2$.

Universal Codes - Motivation

In several practical situations, it is unrealistic for the transmitters to have a priori knowledge of $\epsilon_1$ and $\epsilon_2$. Therefore, we consider the case when the transmitters use the same code of rate $R$ (though it is possible to extend this to different rates $R_1$ and $R_2$). We then wish to find a universal source-channel coding scheme such that reliable transmission is possible over different channel parameters $(\epsilon_1,\epsilon_2)$. Ideally, we would like to have one code of rate $R_1 = R_2 = R$ that allows error free communication of the sources for any set of channel parameters $(\epsilon_1,\epsilon_2)$ for which $\epsilon_1,\epsilon_2$ satisfy the conditions in (\ref{eq:sw}).