Maximum Likelihood Decoding

The codeword bits $c_k$ have to be mapped to real values in order to be transmitted over a channel. Here, we assume BPSK mapping, i.e. bits $ c_k \in \{0,1\} $ are converted to the real-valued amplitudes $ x_k \in \{\pm 1\} $ using the mapping rule
$$
x_k = 1-2\cdot c_k.
$$
The channel is assumed to disturb each symbol $ x_k $ by additive white Gaussian noise (AWGN) samples $ n_k \sim \mathcal{N}(0,\sigma^2) $ and the receiver observes the sequence
$$
y_k = x_k + n_k.
$$
An optimal way to decode a channel code for an AWGN channel is maximum likelihood (ML) decoding. In ML decoding, the decoder picks that codeword hypothesis $ \mathbf{x}_\mathrm{hyp} $ that minimizes the Euclidian distance to the received vector $ \mathbf{y} $. Mathematically, this is given by
$$
\hat{\mathbf{x}} = \arg \min_{\forall \mathbf{x}_\mathrm{hyp}} \lVert \mathbf{y} - \mathbf{x}_\mathrm{hyp}\rVert^2 = \arg \min_{\forall \mathbf{x}_\mathrm{hyp}} \sum_{k=1}^{N} (y_k-x_{\mathrm{hyp},k})^2
$$
For binary mapping, this can be further simplified to the a maximization of the cross-correlaton:
$$
\hat{\mathbf{x}} = \arg \max_{\forall \mathbf{x}_\mathrm{hyp}} \mathbf{y}\cdot\mathbf{x}_\mathrm{hyp}^T = \arg \max_{\forall \mathbf{x}_\mathrm{hyp}} \sum_{k=1}^{N} y_k\cdot x_{\mathrm{hyp},k}.
$$

**A note on the definition of the SNR**:

Depending on the channel, we use a different definition of the signal to noise ratio (SNR). For a real-valued channel, we define the SNR as $$ SNR_s = \frac{E_s}{N_0} = \frac{E_s}{\sigma^2} \qquad \text{and} \qquad SNR_s\vert_\mathrm{dB} = 10 \log_{10} \frac{E_s}{\sigma^2}, $$ where $E_s$ denotes the energy per codeword bit. For a complex-valued channel, both the real and the imaginary part experience a Gaussian noise of variance $\sigma^2$, and therefore we have $N_0=2\sigma^2$ and $$ SNR_s = \frac{E_s}{N_0} = \frac{E_s}{2\sigma^2} \qquad \text{and} \qquad SNR_s\vert_\mathrm{dB} = 10 \log_{10} \frac{E_s}{2\sigma^2}. $$ To compare codes with different code rates $R_c$, it is useful to introduce the SNR per information bit as $$ SNR_b = \frac{E_b}{N_0} = \frac{E_s}{R_c \cdot N_0} = \frac{1}{R_c}\cdot SNR_s, $$ with $E_b$ being the energy per information bit. For example, at a coderate $R_c=\frac{1}{2} $, we need twice as many channel symbols as information bits and hence, we say the energy per information bit is twice the energy per channel symbol, i.e. $E_b=2\cdot E_s$.

Note that the ML decoding method is only feasible for small codes, as the complexity scales linearly with the number of codewords and thus exponentially with $K$.

Depending on the channel, we use a different definition of the signal to noise ratio (SNR). For a real-valued channel, we define the SNR as $$ SNR_s = \frac{E_s}{N_0} = \frac{E_s}{\sigma^2} \qquad \text{and} \qquad SNR_s\vert_\mathrm{dB} = 10 \log_{10} \frac{E_s}{\sigma^2}, $$ where $E_s$ denotes the energy per codeword bit. For a complex-valued channel, both the real and the imaginary part experience a Gaussian noise of variance $\sigma^2$, and therefore we have $N_0=2\sigma^2$ and $$ SNR_s = \frac{E_s}{N_0} = \frac{E_s}{2\sigma^2} \qquad \text{and} \qquad SNR_s\vert_\mathrm{dB} = 10 \log_{10} \frac{E_s}{2\sigma^2}. $$ To compare codes with different code rates $R_c$, it is useful to introduce the SNR per information bit as $$ SNR_b = \frac{E_b}{N_0} = \frac{E_s}{R_c \cdot N_0} = \frac{1}{R_c}\cdot SNR_s, $$ with $E_b$ being the energy per information bit. For example, at a coderate $R_c=\frac{1}{2} $, we need twice as many channel symbols as information bits and hence, we say the energy per information bit is twice the energy per channel symbol, i.e. $E_b=2\cdot E_s$.