UNIT III

Error Controlling & Coding

1. Introduction to Error Controlling and Coding

In any communication system, the transmitted information may get corrupted

due to noise, interference, attenuation, and distortion, fading, or
synchronization problems. Because of these impairments, the received data
may not be exactly the same as the transmitted data.

To make communication reliable, we use error control coding.

Meaning of Error Control Coding

Error control coding is a technique in which extra bits, called redundant bits,
are added to the original message before transmission so that the receiver can:

 detect whether an error has occurred, and

 correct the error if possible.

So, coding improves the reliability of communication at the cost of:

 extra bandwidth,
 increased complexity,
 additional processing time.

Need of Error Control Coding

Error control coding is essential because:

 channels are noisy,

 digital data must be received accurately,
 retransmission may be costly or impossible in some systems,
 it improves performance in data communication, satellite communication,
mobile communication, computer networks, storage devices, etc.

Basic Idea

Suppose we want to send a 4-bit message:

101110111011
If we transmit only these 4 bits, any error caused by noise may change the
information.
Instead, we encode it into a longer bit sequence, such as 7 bits, by adding
redundancy. Then the receiver checks the received pattern and decides whether
there is an error.

2. Basic Terminology

Before studying codes, students should know some important terms.

1. Information Bits

These are the actual message bits.

2. Redundant Bits / Parity Bits

These are extra bits added for error detection and correction.

3. Codeword

The complete bit pattern after adding redundancy is called a codeword.

If a message has k bits and after coding it becomes n bits, then:

 k = number of message bits

 n = number of codeword bits
 n−k = number of redundant bits

4. Block Length

The total number of bits in one codeword is called the block length.

5. Code Rate

The efficiency of a code is measured by code rate:

R=k / R

Higher code rate means less redundancy and better bandwidth efficiency.

3. Methods of Controlling Errors

There are two main methods of controlling errors in digital communication.

A. Forward Error Correction (FEC)

In this method, enough redundant bits are added so that the receiver can detect
and correct the error by itself, without asking for retransmission.

Features

 No need of retransmission
 Useful in one-way communication systems
 Suitable for satellite and space communication
 More complex coding and decoding required

Examples

 Hamming code
 BCH code
 Reed-Solomon code
 Convolutional code

B. Automatic Repeat reQuest (ARQ)

In this method, the receiver only detects errors. If an error is found, it asks the
sender to retransmit the data.

Features

 Simpler receiver design

 Requires feedback channel
 Increases delay due to retransmission
 Suitable where retransmission is possible

Types of ARQ

 Stop-and-Wait ARQ
 Go-Back-N ARQ
 Selective Repeat ARQ

C. Hybrid Method
A combination of FEC and ARQ is also used in practical systems.

Example:

 First, use coding to correct small errors.

 If error is too large, request retransmission.

4. Types of Errors

During transmission, different kinds of bit errors may occur.

1. Single Bit Error

Only one bit in a data unit changes from 0 to 1 or from 1 to 0.

Example

Transmitted: 1011001

Received: 1010001

Only one bit has changed.

Cause

Usually occurs in parallel transmission or in channels where noise affects only

one bit position.

2. Multiple Bit Error

More than one bit is altered in the same data unit.

Example

Transmitted: 1011001

Received: 1000001

Several bits are changed.

3. Burst Error

Two or more bits in a sequence are corrupted, usually in consecutive positions.

Example

Transmitted: 1101011001

Received: 1100010001

A group of bits is affected.

Note: Burst error length is measured from the first corrupted bit to the last
corrupted bit.

Importance: Burst errors are common in practical communication systems due

to impulse noise or fading.

5. Types of Codes

Error control codes can be broadly classified as follows.

1. Error Detecting Codes

These codes are used only to detect the presence of errors.

Examples

 Single parity check code

 Two-dimensional parity check
 Checksum
 Cyclic Redundancy Check (CRC)

These codes are often used with ARQ.

2. Error Correcting Codes

These codes can both detect and correct errors.

Examples

 Hamming code
  BCH code
 Reed-Solomon code
 Convolutional code

3. Block Codes

In block codes, message bits are grouped into fixed-size blocks and each block
is encoded separately.

If k message bits are converted into n bits, the code is called an (n, k) block
code.

Example:

 (7,4) code means 4 message bits are encoded into 7-bit codewords.

4. Convolutional Codes

In convolutional codes, coding is performed continuously on the data stream,

using memory elements.

Since your topic specifically includes linear block codes, that will be our main
focus.

6. Linear Block Codes

Definition

A linear block code is a block code in which:

1. each codeword has fixed length n,

2. each message block has fixed length k,
3. the modulo-2 sum of any two codewords is also a valid codeword.

So, if C1 and C2 are two codewords, then: C1+C2 (modulo-2 addition) is also a
codeword.

This property is called linearity.

Representation

A linear block code is represented by: (n, k)

where:
 n = total number of bits in codeword
 k = number of message bits
 n-k = number of parity bits

Example
A (7,4) code has:
 4 information bits
 3 parity bits
 7 bits in each codeword

Number of Codewords

For a linear block code with k information bits:

Number of codewords =2^k

Example: For (7,4) code: 2^4 = 16 possible codewords.

Why Linear Block Codes are Important

 mathematically simple,
 easy to implement,
 useful for both error detection and correction,
 foundation for many advanced coding techniques.

7. Properties of Linear Block Codes

A linear block code has the following important properties:

1. All-zero codeword is always present

Since it is linear, the all-zero message maps to all-zero codeword.

2. Closure under modulo-2 addition

Sum of any two codewords is another codeword.

3. Minimum distance determines error capability

The performance of the code depends on the minimum Hamming distance.

8. Hamming Distance and Hamming Weight

These are very important concepts.

Hamming Distance

The Hamming distance between two codewords is the number of positions in

which they differ.

Example: C1=101101 & C2=100001

Comparing bit by bit, they differ in 2 positions.

So, d(C1,C2)=2

Minimum Hamming Distance dmin

It is the smallest Hamming distance between any two distinct codewords in the
code.

This is the most important parameter of a code.

Hamming Weight

The number of 1s in a codeword is called its Hamming weight.

Example: 101101 has weight 4.

For linear block codes, the minimum distance equals the minimum weight of all
non-zero codewords:

dmin=wmin
9. Matrix Description of Linear Block Code

A linear block code is described using two important matrices:

 Generator Matrix G
 Parity Check Matrix H

A. Generator Matrix GGG

The generator matrix is used at the transmitter to generate codewords from

message bits.

For an (n, k) linear block code:

 GGG has dimension k×n

If the message vector is: m=[m1 m2 ... mk]

then the codeword is obtained as: c=mG

where multiplication is performed using modulo-2 arithmetic.

Systematic Code

If the codeword contains message bits directly followed by parity bits, it is

called a systematic code.

For a systematic code: G=[Ik P]

where:

 Ik = identity matrix of order k

 P = parity matrix

B. Parity Check Matrix H

The parity check matrix is used at the receiver to test whether the received
codeword is valid.

For an (n, k) code:

  H has dimension (n−k)×n

For a valid codeword c: cHT=0

If the result is not zero, an error is present.

For a systematic code: H=[PT In−k]

Relation between G and H

For a valid linear block code: GHT=0

This is an important condition.

10. Encoding Process Using Generator Matrix

Suppose a message vector is:

m=[m1 m2 ... mk]

Using generator matrix G, codeword is: c=mG

All operations are modulo-2.

Modulo-2 Rules

 0+0=1
 0+1=1
 1+0=1
 1+1=0

There is no carry in modulo-2 addition.

11. Syndrome and Error Detection

At the receiver, let the received vector be r.

To check whether error has occurred, calculate the syndrome:

S=rHT

Cases
  If S=0, then either no error is present or an undetectable error has
occurred.
 If S≠0, then error is detected.

For many codes, syndrome also helps identify the error location.

12. Error Detection and Error Correction Capabilities of Linear Block

Code

The error handling ability of a code depends on its minimum distance dmin

A. Error Detection Capability

A code with minimum distance dmin can detect up to:

dmin−1

bit errors.

Reason

If fewer than dmin bits change, the received word cannot become another valid
codeword, so the error is detectable.

B. Error Correction Capability

A code with minimum distance dmin can correct up to:

t=⌊(dmin−1)/2⌋

bit errors.

where t is the maximum number of correctable errors.

C. Combined Requirement

To correct t errors, minimum distance must satisfy:

dmin≥2t+1

To detect s errors:

dmin≥s+1

Examples

Example 1

If: dmin=3 then:

 detect up to 3−1=2 errors

 correct up to

⌊(3−1)/2⌋=1

error

Example 2

If: dmin=5 then:

 detect up to 4 errors
 correct up to 2 errors

13. Standard Array Concept (Brief Teaching Idea)

To explain correction visually, you can mention that the receiver chooses the
valid codeword that is at the minimum Hamming distance from the received
word.

That means:

 nearest codeword decoding,

 also called minimum distance decoding.

This idea is the basis of error correction.

14. Simple Linear Block Code Example

Let us consider a simple (3,2) linear block code.

Suppose message bits are:

m=[m1 m2]

Let generator matrix be:

[ 10 1]
G = 0 11

This is a (3,2) code.

Codeword Generation

For message:

m=[1 0]

Then:

c=mG

[ 10 1]
c=[1 0] 0 11

Taking modulo-2 multiplication:

 first bit = 1⋅1+0⋅0=1

 second bit = 1⋅0+0⋅1=0
 third bit = 1⋅1+0⋅1=1
 So, c=[1 0 1]

All Possible Codewords

For all possible messages:

For m=[0 0]

c=[0 0 0]

For m=[0 1]
 c=[0 1 1]

For m=[1 0]

c=[1 0 1]

For m=[1 1]

c=[1 1 0]

So the codewords are:

000, 011, 101, 110

Minimum Distance

Distances are:

 000 and 011 → 2

 000 and 101 → 2
 000 and 110 → 2

Minimum distance:

dmin=2

Therefore:

 Error detection capability = dmin−1=1

 Error correction capability =⌊(2−1)/2⌋=0
 So this code can detect 1 error but cannot correct any error.

15. Matrix Description Example with GGG and HHH

Consider a systematic (7,4) code.

Let

G=[I4 P]

Suppose

P=¿
 101
011
1 11 ¿

Then

G= ¿
0 1 0 0 10 1
0 0 1 0 0 11
0 0 0 1 11 1¿

Now parity check matrix is:

H=[PT I3]
H= ¿
1 0 11 0 1 0
0 1 11 0 0 1¿

This matrix can be used at the receiver for syndrome calculation.

16. Simple Numerical on Encoding

Problem

A (3,2) linear block code has generator matrix

G= ¿
0 1 1¿

Find the codeword for message m=[1 1]

Solution

c=mG

c=[11]¿
0 1 1¿

Now calculate each bit modulo-2:

 First bit: 1⋅1+1⋅0=1

 Second bit: 1⋅0+1⋅1=1
  Third bit: 1⋅1+1⋅1=0
 So, c=[1 1 0]
 Answer

The transmitted codeword is: 110

17. Simple Numerical on Syndrome Checking

Using the same code, the valid codewords are: 000, 011, 101, 110

Let the received word be: r=111

Check whether error is present.

We know 111 is not a valid codeword, so error is present.

Now using parity check matrix: H=[1 1 1]

because for this code, all valid codewords have even parity.

Now calculate syndrome: S=rHT

So: S=1≠0

Conclusion: An error is detected.

18. Simple Numerical on Error Detection/Correction Capability

Problem

A linear block code has minimum distance:

dmin=4

Find:

1. maximum number of detectable errors

2. maximum number of correctable errors

Solution

Detectable errors : dmin−1=4−1=3

Correctable errors :

t=⌊(4−1)/2⌋=⌊1.5⌋=1

Answer

 Detects up to 3 errors
 Corrects up to 1 error

19. Important Differences: Detection vs Correction

Basis Error Detection Error Correction

Find whether error
Purpose Find and remove error
occurred
Redundancy required Less More
Complexity Lower Higher
Detects and reconstructs
Receiver action Detects only
data
Retransmission needed Usually yes Usually no

20. Advantages of Error Control Coding

 improves reliability of communication,

 reduces effect of noise,
 enables accurate digital transmission,
 essential for storage and wireless systems,
 supports long-distance communication.

21. Limitations

 extra redundant bits increase bandwidth,

 encoder and decoder complexity increases,
 some codes only detect but cannot correct,
 correction capability depends on code design.

22. Applications

Error control coding is used in:

  mobile communication,
 satellite communication,
 Wi-Fi and Bluetooth,
 computer networks,
 deep-space communication,
 CDs, DVDs, hard disks, SSDs,
 digital television,
 data storage systems.

23. Key Formula Summary

Code rate : R=k/n

Number of codewords : 2k

Valid codeword condition: cHT=0

Syndrome : S=rHT

Error detection capability: dmin−1

Error correction capability: t=⌊(dmin−1)/2⌋

For correcting t errors : dmin≥2t+1

24. Conclusion

Error control coding is a fundamental part of digital communication systems.

Since errors are unavoidable in practical channels, coding techniques are used to
add redundancy to transmitted data so that errors can be detected and corrected.
Among various coding schemes, linear block codes are very important because
they are simple, mathematical, and easy to implement. Their behavior is
described using generator matrix and parity check matrix, while their
performance depends on the minimum Hamming distance. Hence,
understanding error control coding helps students build a strong foundation for
advanced topics in communication engineering and information theory.