## TD9, An introduction to LDPC codes## INF563 Introduction to Information Theory## March 12, 2020 |

The purpose of this TD is to introduce/manipulate the basic principles behind LDPC codes.
We will denote a binary symmetric channel of crossover *p* by BSC(*p*).

Consider a bit *b* which is uniformy distributed (its probability of being equal to 1 is equal to 1/2).
It is sent several times to someone through *n* noisy communication channels. The receiver receives
from each of these channels a signal *y*_{i} from which is he able to infer the conditional probability
*p*_{i} = *p*(*b*=1|*y*_{i}) that the bit is equal to 1. We assume that the *y*_{i}’s are independent conditionally of the value of
*b*. What is the best strategy for guessing this bit ?

*Hint:* It could be helpful to express the conditional probability *p* that the bit *b*
is equal to 1 given *y*_{1},…,*y*_{n}. You could try to find a formula expressing ln*p*/1−*p* in terms
of the ln*p*_{i}/1−*p*_{i}’s.

Estimate the probability of error on the bit *b* by writing a simulation program in the case where each of this channel
is a uniform mixture of 4 binary symmetric channels (BSC in short): a BSC(0.4), a BSC(0.3), a BSC(0.2) and
a BSC(0.1).
Each of these BSC is chosen with probability 0.25. This means that transmission over such a channel is done as follows:
first one of these 4 channels is chosen according to the uniform distribution, then the bit is sent through the
corresponding BSC and is received by the receiver together with a number ∈ {1,2,3,4} identifying the BSC which was chosen.
Estimate this probability of error when *n* ranges from 1 to 10.

We still have *n* communication channels with the same assumptions on them. But now they are used in a slightly different manner.
Instead of sending the bit *b* directly, the sender first chooses *n*−1 random bits *b*_{1},…,*b*_{n−1} uniformly at random. The last one *b*_{n} depends
on the others since *b*_{n} = *b* ⊕ *b*_{1} ⊕ … ⊕ *b*_{n−1}. Each of these bits *b*_{i} are now sent independently through the *n* channels.
The receiver is then asked to find the best strategy to recover *b* from the received values *y*_{1},…,*y*_{n}.

Estimate the probability of error on the bit *b* by writing a simulation program
when *n* ranges from 1 to 10. You will consider two scenarios here

- Scenario 1 The channels are the same as in the previous game.
- Scenario 2 The channels are all a uniform mixture of two BSC: a BSC(0.1) and a BSC(0.02).

We now have a mixed scenario where we have *n*+1 communication channels for sending information about a bit *b*.
The sender uses the *n* first channels as in the previous game but also sends directly *b* through the last channel.
You are asked to find the best strategy to recover *b* from the received values *y*_{1},…,*y*_{n+1}.

Give the optimal strategy for recovering *b* and estimate the probability of error of this strategy by writing a simulation program with the same channel model as in Scenario 2 before
when *n* ranges from 1 to 40. Can you give a coding interpretation of this game ?

We have now *t* sets of *n* channels each. Each set of *n* channels is used for sending information
about a bit *b* in the same way as in the second game. We also have an auxiliary channel where we send directly the
bit *b*.

Estimate the probability of error on the bit *b* by writing a simulation program with the same channel model as in Scenario 2 before
when *t* ranges from 2 to 20 and when *n*=2*t*. Can you give a coding interpretation of this game ?

By using the answer to the fourth game, suggest a method for decoding a linear code and a family of linear codes for which this decoding algorithm might be efficient.

This document was translated from L^{A}T_{E}X byH^{E}V^{E}A.