Chapter 5
Linear Block
Codes
Department of
ECE
Raghu Engineering
College
Outline
s
Introduction to linear block codes
Syndrome and error detection
The minimum distance of a block
code
Error-detecting and error-correcting capabilities of a
block code
Standard array and syndrome decoding
Probability of an undetected error for linear codes
over a binary symmetric channel (BSC).
Single-Parity-Check Codes, Repetition Codes, and
Self-Dual Codes
2
Introduction to Linear Block
Codes
Principle of block coding
For the block of k message bits, (n-k) parity bits or check bits
are added. Hence the total bits at the output of channel encoder
are ‘n’. Such codes are called (n,k)block codes.
Functional block diagram of block
coder
Types
Systematic codes:
Block codes in which the message bits are transmitted in
unaltered form are called systematic codes. Generally in the
systematic block code, the message bits appear at the
beginning of the code word. The message appears first and
then check bits are transmitted in a block. This type of code is
called systematic code.
Nonsystematic codes:
In the nonsystematic block code it is not possible to identify
the message bits and check bits. They are mixed in the block.
Types
Linear block codes:
A code is said to be linear if any two code words in the code
can be added in modulo-2 arithmetic to produce a third
codeword in the code.
This shows that any code vector can be expressed as a linear
combination of other code vectors.
Rules for modulo-2 addition:
Modulo-2 addition is the EXCLUSIVE-OR operation
in logic
Types
Non-Linear block codes:
Addition of the non-linear code words does not necessarily
produce third code word.
Linear Block Codes
Consider that the particular code vector consists of m 1,m2, m3,
…mk message bits and c1,c2,c3…cq check bits. Then this code
vector can be written as,
X=(m1,m2,m3,…mk c1,c2,c3…cq)
Here q=n-k
Where q are the number of redundant bits added by the
encoder.
k = no. of message bits
n = no. of bits after encoding is called the block length
Code vector can also be written as
X=(M/C)
Where M= k-bit message vector
C= q-bit check vector
The main aim of linear block code is to generate check bits
and this check bits are mainly used for error detection and
correction.
Matrix Description Of Linear Block
Codes
The code vector can be also represented as
X = MG
Where X = code vector of 1x n size
M = message vector of 1x k size
G = generator matrix of k x n size
In matrix form
Generator Matrix
The generator matrix is represented as
Check Vector
Check vector may be obtained as
In the expanded form, above equation is written as
Check Vector
Solving the equation check vector may be obtained as
Question
The generator matrix for a (6,3) code is given below. Find all
code vectors of this code.
Solution
The code vector is obtained by using the following steps
1. Determine the sub matrix P from generator matrix.
2. Obtain equation for check bits using
3. Determine check bits for every message vector.
Solution
Step 1: Sub matrix P
Generator matrix is given by
Given matrix is
Solution
Comparing we get
Solution
Step 2: Check bits
Solution
Code vectors of (6,3) Block code
Concept of Parity Check Matrix (H)
It is given by
Concept of Parity Check Matrix (H)
Concept of Parity Check Matrix (H)
Hamming Codes
Hamming Codes
Hamming codes are defined as linear block codes satisfying
the following conditions:
1. No. of check bits q ≥ 3
2. Block length n = 2q -1
3. No. of message bits k = n – q
4. Minimum distance dmin = 3
Question
The parity check matrix of a particular (7,4) linear block code
is expressed as
1. Obtain the generator matrix (G)
2. List all the code vectors
3. What will be the minimum distance between code vectors
4. How many errors can be detected? How many errors can
be corrected?
Solution
Given n = 7, k = 4.
No. of check bits q = n-k = 7-4 =3
n = 2q – 1 = 2 3 – 1 = 7
This indicates that the given code is Hamming code.
The parity check matrix is of size qxn and is given by
Solution
From the given parity check matrix
Solution
The P sub matrix is obtained as
Generator matrix is obtained as
Solution
The check bits can be obtained using
Solving the above equation
Solution
Simplifying we get
Solution
All the code vectors are listed below
Solution
The minimum distance of a linear block code is equal to the
minimum weight of any non-zero code vector.
Hence dmin = 3
The no. of errors that can be detected(s) is given by
Solving this we get
S≤ 2
Hence two errors will be detected.
Solution
The no. of errors that can be corrected(t) is given by
dmin ≥ 2t+1
3 ≥ 2t+1
t ≤1
Therefore one error will be corrected.
Syndrome Calculation
Syndrome Decoding: Method to decode Errors
Let the transmitted code vector be X and corresponding
received code vector be represented by Y.
X = Y If there are no transmission errors
X ≠ Y If there are errors produced during transmission
Syndrome is represented by S and is written as
The transpose of parity check matrix has very important
properties:
1. XHT = 0
2. HHT = 0
3. YHT = 0 if no errors
4. YHT = non-zero if errors
Syndrome
But
This equation indicates that syndrome depends on the error
pattern only.
Question
The parity check matrix of (7,4) Hamming code is given by
Evaluate the syndrome vector for single bit errors.
Solution
Given parity check matrix H, we obtain its transpose HT
Single error pattern is listed below
Similarly calculate syndrome for all error patterns
Error correction using syndrome
vector
Let the transmitted code vector be
Let there be error created in 3rd bit in the received code vector
Y.
Calculate syndrome
S=(1 1 0) indicates error in 3rd bit.
E= [0 0 1 0 0 0 0]
The correct vector can be obtained as
Which is same as the tranmitted vector. Thus single error can
be corrected using syndrome decoding.
Cyclic Codes
Cyclic Codes
Cyclic codes may be described as the sub class of linear block
codes. They have the property that a cyclic shift of one code
word produces another code word.
As an example consider an n-bit code vector
If we shift the above code word cyclically, then we will get
another code word X’
It may be observed that every bit is shifted to left by one bit
position. Previously xn-1 was MSB but after shift it is at LSB
position.
Cyclic codes
Definition:
A linear code is known as cyclic code if every cyclic shift of
the code vector produces some other valid code vector.
The code vector may be defined with the help of polynomial
of degree < n - 1.
Where p is an arbitrary variable and power of p represents the
position of the codeword bits i.e, (n-1) power of p represents
MSB and p0 represents LSB.
Code vector polynomial X(p) is represented as
Where message signal polynomial of degree ≤ k. G(p) is the
generating polynomial of degree q.
Question
The generator polynomial of a (7,4) cyclic code is G(p) =
p3+p+1. Obtain all the code vectors in the non-systematic
form.
Solution
Here n=7, k=4, q=3
Let us consider any message vector
Message polynomial
We get M(p) = p2+1
G(p) = p3+p+1
X(p) = 0p6+p5+0p4+0p3+p2+p+1
X = (0 1 0 0 1 1 1)
This is the code vector for message (0101). This code vector is
non-systematic cyclic code vector.
Similarly other code vectors may be obtained using same
procedure.
Systematic code vectors
For systematic code vectors first we calculate check bits
Since q= 3
Perform division to find the remainder
C(p) = p2+0p+0
Hence check bits are
The code vector is written in systematic form as
BCH Codes
BCH Codes
