TD9, An introduction to LDPC codes

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).

1  An information theoretic game

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₁,…,y_n. You could try to find a formula expressing lnp/1−p in terms of the lnp_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.

2  A similar game

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₁,…,b_n−1 uniformly at random. The last one b_n depends on the others since b_n = b ⊕ b₁ ⊕ … ⊕ 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₁,…,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).

3  A mixture of both games

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₁,…,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 ?

4  Another mixture

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=2t. Can you give a coding interpretation of this game ?

5  Suggesting an algorithm for decoding a linear code

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^AT_EX by H^EV^EA.