Information Theory and Coding

(BECE313L)
Winter Semester 2024-25

Dr. Dilip Kumar Choudhary

Ph.D. (IIT-ISM, Dhanbad)
Assistant Professor, Department of Communication Engineering
School of Electronics Engineering (SENSE)
Vellore Institute of Technology, Vellore
Email Id: [email protected]
Cabin: SJT Annex 203 (J)
Website : https://sites.google.com/site/dilipiitdh
Winter Semester : 2024-25 Information Theory and Coding Slide No: 2

Module-7: Channel Coding for 5G standard

• Low Density Parity Check code - LDPC code construction,
construction in 5G standard, encoding of LDPC codes,
Message passing decoding on Tanner graph.
• Polar code – Representation, generator matrix, Successive
cancellation decoder for polar codes.

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 3

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 4

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 5

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 6

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 7

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 8

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 9

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 10

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 11

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 12

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 13

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 14

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 15

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 16

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 17

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 18

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 19

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 20

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 21

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 22

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 23

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 24

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 25

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 26

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 27

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 28

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 29

Low Density Parity Check Code (LDPC)

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 30

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 31

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 32

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 33

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 34

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 35

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 36

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 37

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 38

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 39

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 40

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 41

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 42

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 43

https://www.youtube.com/watch?v=bAZnP
4kdb44&ab_channel=NPTEL-NOCIITM

https://www.youtube.com/watch?v=YVtw_
SlVRVM&ab_channel=NPTEL-NOCIITM

https://www.youtube.com/watch?v=rB0rhQ
KyV34&ab_channel=NPTEL-NOCIITM

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 44

Low Density Parity Check Codes

 LDPC ( Low Density Parity Check ) codes are a class of linear bock code.
 The term “Low Density” refers to the characteristic of the parity check matrix which
contains only few ‘1’s in comparison to ‘0’s.
 LDPC codes are arguably the best error correction codes in existence at present.
 LDPC codes were first introduced by R. Galager in his PhD thesis in 1960 and soon
forgotten due to introduction of Reed-Solomon codes and the implementation issues
with limited technological knowhow at that time.
 The LDPC codes were rediscovered in mid 90s by R. Neal and D. Mackay at the
Cambridge University.

 We can define N bit long LDPC code in terms of M number of parity check
equations and describing those parity check equations with a M x N parity check
matrix H. Where,
M – Number of parity check equations
N – Number of bits in the codeword
Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT
Winter Semester : 2024-25 Information Theory and Coding Slide No: 45

Consider the 6 bit long codeword in the form c  c1 , c2 , c3 , c4 , c5 , c6 

which satisfies 3 parity check equations as shown below.
c1  c2  c5  0 We can now define 3x6 parity check matrix as,
c1  c4  c6  0 c1  c2  c5
c1  c2  c3  c6  0

The density of ‘1’s in LDPC code parity check matrix is very low
1 1 0 0 1 0
H  1 0 0 1 0 1
Row weight wc  - number of ‘1’s in a row Number of
Number of symbols taking part in a parity check 1 1 1 0 0 1

wr and wc changes, therefore this is an

Column weight wc  - number of ‘1’s in a column
irregular parity check matrix
Number of times a symbol taking part in parity checks

If the parity check matrix has uniform row weight and uniform column weight (same number
of ‘1’ in a column and same number of ‘1’ in a row) we call that a regular parity check matrix.

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 46

1 1 0 0 1 0 The H M  N parity check matrix defines a rate R  K N,  N, K  code

H  1 0 0 1 0 1 where K  N  M

1 1 1 0 0 1 Codeword is said to be valid if it satisfies the syndrome calculation

z  c.H T  0
We can generate the codeword in by multiplying message m with generator matrix G
c  m.G

We can obtain the generator matrix G from parity check matrix H by,
1 0 0 1 0 1

1.) Arranging the parity check matrix in systematic form H sys  I M P M  K  H sys  0 1 0 1 1 1
using row and column operations 0 0 1 0 1 1

1 1 0 1 0 0
2.) Rearranging the systematic parity check matrix G  P  T
K M IK  G  0 1 1 0 1 0
1 1 1 0 0 1
3.) We can verify our results as G.H T  0

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 47

1 1 0 0 1 0
H  1 0 0 1 0 1
Tanner graph is a graphical representation of parity check matrix
specifying parity check equations.
1 1 1 0 0 1 Tanner graph consists of N number of variable nodes and M number
of check nodes

In Tanner graph mth check node is connected to nth variable node if and only if nth element in
mth row hmn in parity check matrix H is a ‘1’.

z1 z2 z3

c1 c2 c3 c4 c5 c6

The marked path z2 → c1 → z3 → c6 → z2 is an example for short cycle of 4

The number of steps needed to return to the original position is known as the girth of
the code

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 48

1. Suppose we have codeword c as follows: c  c1 , c2 , c3 , c4 , c5 , c6 

where each ci is either ‘0’ or ‘1’ and codeword now has three parity-check
equations.
c1  c2  c5  0
c1  c4  c6  0
c1  c2  c3  c6  0

a.) Determine the parity check matrix H by using the above equation
b.) Show the systematic form of H by applying Gauss Jordan elimination
c.) Determine Generator matrix G from H and prove G * HT = 0
d.) Find out the dimension of the H, G
e.) State whether the matrix is regular or irregular

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 49

c1  c2  c5  0
1 1 0 0 1 0 6 columns and 3 rows
c1  c4  c6  0
H  1 0 0 1 0 1
c1  c2  c3  c6  0
1 1 1 0 0 1

Convert H into systematic form H sys using basic row and operations (try to avoid column operations)

1 1 0 0 1 0 1 1 0 0 1 0
H  1 0 0 1 0 1 R2  R3 1 1 1 0 0 1
 
1 1 1 0 0 1 1 0 0 1 0 1

1 1 0 0 1 0 1 1 0 0 1 0
H  1 1 1 0 0 1 R2  R3  R2 0 1 1 1 0 0
1 0 0 1 0 1 1 0 0 1 0 1

1 1 0 0 1 0 1 1 0 0 1 0
H  0 1 1 1 0 0 R3  R3  R2  R1 0 1 1 1 0 0
1 0 0 1 0 1 0 0 1 0 1 1

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 50

1 1 0 0 1 0 1 0 0 1 0 1
H  0 1 1 1 0 0 R1  R1  R2  R3 0 1 1 1 0 0
0 0 1 0 1 1 0 0 1 0 1 1

1 0 0 1 0 1 1 0 0 1 0 1
H  0 1 1 1 0 0 R2  R2  R3 0 1 0 1 1 1
0 0 1 0 1 1 0 0 1 0 1 1

1 0 0 1 0 1
H sys  0 1 0 1 1 1 
H sys  I M P M  K  
G  PKTM I K 
0 0 1 0 1 1
1 1 1
1 0 1
1 1 0 1 0 0 1 1 0 1 0 0   0 0 0 
G  0 1 1 0 1 0
0 0 1 
G.H T  0 1 1 0 1 0. 
  0 0 0 
0 1 0
1 1 1 0 0 1  0 0 0
1 1 1 0 0 1 1 0 0 
 
0 1 1
Dimensions of H = 3x6
Since the column weight and row weight changes, this
Dimensions of G = 3x6 is an irregular parity check matrix

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 51

2. The parity check matrix H of LDPC code is given below:

1 0 1 0 0 1 1 0 1 0 1 0
0 1 1 1 1 0 1 0 0 0 0 1 

0 1 0 1 0 1 0 1 1 1 0 0 
H   
1 1 1 0 0 0 0 1 1 0 1 0 
0 0 0 1 1 0 1 0 0 1 1 1 
 
 1 0 0 0 1 1 0 1 0 1 1 0 

a.) Determine the degree of rows and column

b.) State whether the LDPC code is regular or irregular
c.) Determine the rate of the LDPC code
d.) Draw the tanner graph representation of this LDPC code.
e.) What would be the code rate if we make rows equals to column
f.) Write down the parity check equation of the LDPC code

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 52

1 0 1 0 0 1 1 0 1 0 1 
0
0 1 1 1 1 0 1 0 0 0 0 1  Dimensions of the H matrix = 6x12

0 1 0 1 0 1 0 1 1 1 0 0  M  6, N  12, K  N  M  6
H   
1 1 1 0 0 0 0 1 1 0 1 0 
0 0 0 1 1 0 1 0 0 1 1 1  Row weight wr  6
 
 1 0 0 0 1 1 0 1 0 1 1 0  Column weight wc  3

Since the parity check matrix has a uniform row weight and uniform column weight, this
is a regular LDPC parity check matrix

Since the parity check matrix has a uniform row weight and uniform column weight, this
is a regular LDPC parity check matrix

Code rate R  K 6 1 , R 1
N 12 2 2

If we make the number of rows equal to columns code rate will be equal to ‘0’

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 53

1 0 1 0 0 1 1 0 1 0 0 1 
 0 1 1 1 1 0 1 0 0 0 0 1 
 
 0 1 0 1 0 1 0 1 1 1 0 0 
H   
1 1 1 0 0 0 0 1 1 0 1 0 
 0 0 0 1 1 0 1 0 0 1 1 1 
 
 1 0 0 0 1 1 0 1 0 1 1 0 

The parity check equations of the matrix are

z1  c1  c3  c6  c7  c9  c12
z 2  c2  c3  c4  c5  c7  c12
z3  c2  c4  c6  c8  c9  c10
z4  c1  c2  c3  c8  c9  c11
z5  c4  c5  c7  c10  c11  c12
z6  c1  c5  c6  c8  c10  c11

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 54

3. Consider parity check matrix H generated in question 1,

a.) Determine message bits length K, parity bits length M, codeword length N
b.) Use the generator matrix G obtained in question 1 to generate all possible codewords c.

1 1 0 0 1 0 1 1 0 1 0 0
H  1 0 0 1 0 1 G  0 1 1 0 1 0
Dimensions of the H matrix = 3x6
1 1 1 0 0 1 1 1 1 0 0 1
M  3, N  6, K  N M 3

All possible message set All possible codeword set

 msg_ 1   000   codeword_1   msg_ 1.G  000000 
 msg_2   001  codeword_2   msg_2 .G  111001 
         
 msg_3   010   codeword_3   msg_3 .G  011010 
         
msg_4 011 codeword_4 msg_4 .G 100011
m    c   
 msg_5  100   codeword_5   msg_5 .G  110100 
         
 msg_6   101   codeword_6   msg_6 .G   001101 
 msg_7  110  codeword_7   msg_7 .G  101110 
         
 msg_8   111   codeword_8   msg_8 .G   010111 

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT

Winter Semester : 2024-25 Information Theory and Coding Slide No: 55

Question 4.
a.) What is the difference between regular and irregular LDPC codes?
b.) What is the importance of cycles in parity check matrix?
c.) Identify the cycles of 4 in the following tanner graph.

If the parity check matrix has uniform row weight and uniform column weight (same number of ‘1’ in a
column and same number of ‘1’ in a row) we call that a regular parity check matrix.

The decoding algorithm assumes that the LDPC code is cycle free ( large girth sizes ). The short cycles
in the code ( cycles with a girth of 4 and cycles of girth of 6 ) weakens the code. Therefore the codes
must be carefully constructed to be free of short cycles.
Check Nodes

Variable Nodes

Dr. Dilip Kumar Choudhary, Asst. Prof. (Sr), SENSE,VIT