ECT306 Information Theory &

Coding
Dr. Lakshmi V.S.
Assistant Professor
Electronics & Communication Department
Sree Chitra Thirunal College of Engineering, Trivandrum

Department of Electronics & Communication 1

 ECT 306
INFORMATION THEORY AND CODING

Theory Tutorial Practical Credits YEAR OF

Hours/Week Hours/Week Hours/Week INTRODUCTION

3 1 0 4 2019

Department of Electronics & Communication 2

 Preamble & Prerequisite
Preamble:
✓ This course aims to lay down the foundation of information theory introducing both
source coding and channel coding.
✓ It also aims to expose students to algebraic and probabilistic error-control codes that
are used for reliable transmission.

Prerequisite:
✓ MAT 201 Linear Algebra and Calculus, MAT 204 Probability, Random Process and
Numerical Methods, ECT 204 Signals and Systems.

Department of Electronics & Communication

3
 Assessment Pattern
Continuous Internal Evaluation Pattern:
– Attendance : 10 marks
Total Marks CIE ESE ESE Duration
– Continuous Assessment Test (2 numbers) : 25 marks
150 50 100 3 hours
– Assignment/Quiz/Course project : 15 marks

End Semester Examination Pattern:

• There will be two parts; Part A and Part B.
• Part A contain 10 questions with 2 questions from each Continuous Assessment End Semester
module, having 3 marks for each question. Students should Bloom’s Category Tests Examination
1 2
answer all questions. Remember 10 10 20
• Part B contains 2 questions from each module of which Understand 30 30 60
Apply 10 10 20
student should answer any one. Each question can have Analyse
maximum 2 sub-divisions and carry 14 marks. Evaluate
Create
Department of Electronics & Communication
4
 Motivation

• As long as channel noise exists, communication cannot be error-free.

• But we can improve the transmission accuracy by reducing the probability of error.

Department of Electronics & Communication 5

 Motivation
• In digital systems, Probability of error 𝑃𝑒 𝛼 𝑒 −𝑘𝐸𝑏

• For eg. In BPSK or QPSK,

1 𝐸𝑏
𝑃𝑒 = erfc
2 𝑁0
• Probability of error, 𝑃𝑒 can be reduced by increasing energy per bit, 𝐸𝑏

• Signal power, 𝑃𝑖 = 𝐸𝑏 𝑅𝑏 , where 𝑅𝑏 - Bit rate

↑ 𝑃𝑖 (for a given 𝑅𝑏 ) or
To Increase 𝐸𝑏
↓ 𝑅𝑏 (for a given 𝑃𝑖 )
• Due to physical limitations, 𝑃𝑖 cannot be increased beyond a certain limit

• So, to reduce 𝑃𝑒 , we need to reduce 𝑅𝑏 in order to increase 𝐸𝑏 for a given 𝑃𝑖

• To make 𝑃𝑒 → 0, 𝑅𝑏 → 0

Department of Electronics & Communication 6

 Motivation
• As 𝑃𝑒 → 0, only when 𝑅𝑏 → 0

• Error-free communication is impossible in the presence of channel noise - Thought of

communication engineers until 1948

• In 1948, Claude E Shannon published the paper “A Mathematical Theory of Communication” in the
Bell Systems Technical Journal

• He found that 𝑃𝑒 → 0 can be attained if we maintain 𝑅𝑏 below some value, termed as channel
capacity, C. ( i.e., 𝑅𝑏 < C)

Department of Electronics & Communication 7

 Shannon’s Definition of Communication

• “The fundamental problem of communication is that of reproducing at

one point either exactly or approximately a message selected at
another point.”

Claude E Shannon

Department of Electronics & Communication 8

 Shannon’s Vision on Communication
• Shannon wants to find a way for “reliably” transmitting data through the channel at “maximal”
possible rate.

• In his 1948 paper he build a rich theory to the problem of reliable communication, now called
“Information Theory” or “The Shannon Theory” in honor of him.

Information
Coding
Source

Communication
Channel

Destination Decoding

Department of Electronics & Communication 9

Shannon’s paper - “A Mathematical Theory of Communication”
• Answered some fundamental questions…

• How to quantify information?

- Entropy as measure of information

• What is the fundamental limit for information compression?

- Source Coding Theorem

• What is the fundamental limit on information transmission rate over a communication channel?

- Channel Coding Theorem

Department of Electronics & Communication 10

 Communication System
Change to an efficient representation, Change to an efficient representation
i.e., data compression for transmission, i.e., error control
Any source of information coding

channel is anything transmitting

Source Channel Channel or storing information –
Source a radio link, a cable, a disk, a
coder coder CD, a piece of paper, …

Channel Channel Source Sink,

decoder decoder receiver

Recover from channel distortion

Uncompress
Department of Electronics & Communication 11
 Example: Disk Storage

Data Zip Add CRC

Channel

User Unzip Verify CRC

CRC stands for Cyclic Redundancy Check

Department of Electronics & Communication 12

 In terms of Information Theory Terminology

Source
Zip = Data Compression Example: Disk Storage
Encoding

Source
Unzip = Data Decompression
Decoding

Channel Add
Add CRC = Encoding
Error Protection Data Zip
CRC Chann
Channel Verify el
Verify CRC = Error Correction User Unzip
Decoding CRC
CRC stands for Cyclic Redundancy Check

Department of Electronics & Communication 13

 Example: VCD and DVD

MPEG RS
Moive
Encoder Encoding
CD/DVD
MPEG RS
TV
Decoder Decoding

RS stands for Reed-Solomon Code

Department of Electronics & Communication 14

Example: Cellular Phone

Speech CC
Encoding Encoding
Channel
Speech CC
Decoding Decoding

GSM/CDMA
CC stands for Convolutional Code

Department of Electronics & Communication 15

 Example: WLAN IEEE 802.11b

CC
Data Zip
Encoding
Channel
CC
User Unzip
Decoding

IEEE 802.11b
CC stands for Convolutional Code

Department of Electronics & Communication 16

 Applications

Source Coding Theorem has applied to

JPEG 2000

Image MPEG Audio/Video

Compression Compression

Data Audio
MP3
Compression Compression

Department of Electronics & Communication 17

 Applications
Channel Coding Theorem has applied to
• VCD/DVD – Reed-Solomon Codes
• Optical Communication – Reed-Solomon Codes
• Computer Network – LT codes, Raptor Codes
• Space Communication – Convolutional Codes
• Wireless Communication – Convolutional Codes, Turbo Codes (4G), LDPC Codes (5G),
Polar Codes (5G)

Department of Electronics & Communication 18

 Application of Information Theory also extends to
• All kinds of Communications

• Stock Market, Economics

• Game Theory and Gambling

• Linguistics

• Quantum Physics

• Cryptography

• Biology and Genetics

• and many more…

Department of Electronics & Communication 19

 Syllabus
• Module 1– Entropy, Sources and Source Coding
✓ Entropy, Properties of Entropy, Joint and Conditional Entropy, Mutual Information, Properties of Mutual Information.
✓ Discrete memoryless sources, Source code, Average length of source code, Bounds on average length, Uniquely
decodable and prefix-free source codes. Kraft Inequality (with proof), Huffman code. Shannon’s source coding
theorem (both achievability and converse) and operational meaning of entropy.
• Module 2 – Channels and Channel Coding
✓ Discrete memoryless channels. Capacity of discrete memoryless channels. Binary symmetric channels (BSC), Binary
Erasure channels (BEC). Capacity of BSC and BEC. Channel code. Rate of channel code. Shannon’s channel coding
theorem (both achievability and converse without proof) and operational meaning of channel capacity.
✓ Modeling of Additive White Gaussian channels. Continuous-input channels with average power constraint. Differential
entropy. Differential Entropy of Gaussian random variable. Relation between differential entropy and entropy.
Shannon-Hartley theorem (with proof – mathematical subtlities regarding power constraint may be overlooked).
✓ Inferences from Shannon Hartley theorem – spectral efficiency versus SNR per bit, power-limited and bandwidth-
limited regions, Shannon limit, Ultimate Shannon limit.

Department of Electronics & Communication 20

 Syllabus
• Module 3 – Introduction to Linear Block Codes
✓ Overview of Groups, Rings, Finite Fields, Construction of Finite Fields from Polynomial rings, Vector spaces.
✓ Block codes and parameters. Error detecting and correcting capability. Linear block codes. Two simple examples --
Repetition code and single parity-check code. Generator and parity-check matrix. Systematic form.
✓ Maximum likelihood decoding of linear block codes. Bounded distance decoding. Syndrome. Standard array decoding.
• Module 4 – A Few Important Classes of Algebraic codes
✓ Cyclic codes. Polynomial and matrix description. Interrelation between polynomial and matrix view point. Systematic
encoding. Decoding of cyclic codes.
✓ (Only description, no decoding algorithms) Hamming Codes, BCH codes, Reed-Solomon Codes.
• Module 5 – Convolutional and LDPC Codes
✓ Convolutional Codes. State diagram. Trellis diagram. Maximum likelihood decoding. Viterbi algorithm.
✓ Low-density parity check (LDPC) codes. Tanner graph representation. Message-passing decoding for transmission
over binary erasure channel.

Department of Electronics & Communication 21

 Course Outcomes (COs)
CO
COs
Number

1 Explain measures of information – entropy, conditional entropy, mutual information

2 Apply Shannon’s source coding theorem for data compression

3 Apply the concept of channel capacity for characterize limits of error-free transmission

4 Apply linear block codes for error detection and correction

5 Apply algebraic codes with reduced structural complexity for error correction

6 Understand encoding and decoding of convolutional and LDPC codes

Department of Electronics & Communication 22

 Programme Outcomes (POs)
Engineering graduates will be able to:

1. Engineering knowledge: Apply the knowledge of mathematics, science, engineering fundamentals, and an
engineering specialization to the solution of complex engineering problems.

2. Problem analysis: Identify, formulate, review research literature, and analyze complex engineering
problems reaching substantiated conclusions using first principles of mathematics, natural sciences, and
engineering sciences.

3. Design/development of solutions: Design solutions for complex engineering problems and design system
components or processes that meet the specified needs with appropriate consideration for the public
health and safety, and the cultural, societal, and environmental considerations.

4. Conduct investigations of complex problems: Use research-based knowledge and research methods
including design of experiments, analysis and interpretation of data, and synthesis of the information to
provide valid conclusions.

Department of Electronics & Communication 23

 Programme Outcomes (POs)
5. Modern tool usage: Create, select, and apply appropriate techniques, resources, and modern engineering
and IT tools including prediction and modeling to complex engineering activities with an understanding of
the limitations.

6. The engineer and society: Apply reasoning informed by the contextual knowledge to assess societal,
health, safety, legal and cultural issues and the consequent responsibilities relevant to the professional
engineering practice.

7. Environment and sustainability: Understand the impact of the professional engineering solutions in
societal and environmental contexts, and demonstrate the knowledge of, and need for sustainable
development.

8. Ethics: Apply ethical principles and commit to professional ethics and responsibilities and norms of the
engineering practice.

9. Individual and team work: Function effectively as an individual, and as a member or leader in diverse
teams, and in multidisciplinary settings.

Department of Electronics & Communication 24

 Programme Outcomes (POs)
[Link]: Communicate effectively on complex engineering activities with the engineering
community and with society at large, such as, being able to comprehend and write effective reports and
design documentation, make effective presentations, and give and receive clear instructions.

[Link] management and finance: Demonstrate knowledge and understanding of the engineering and
management principles and apply these to one’s own work, as a member and leader in a team, to manage
projects and in multidisciplinary environments.

[Link]-long learning : Recognize the need for, and have the preparation and ability to engage in independent
and life-long learning in the broadest context of technological change.

Department of Electronics & Communication 25

 Programme Specific Objectives(PSO)

Apply the concept of discrete electronics and solid state engineering in the
PSO1 analysis and design of VLSI and nano level electronic systems, based on
recent research in these areas.

Apply the fundamental concepts acquired in the field of communication for solving
PSO2 real world engineering problems in next generation communication and IoT
systems.

Motivate/ inspire students to implement their skills learnt in signal processing to

PSO3
solve real world problems by integrating machine learning techniques.

Department of Electronics & Communication 26

Mapping of course outcomes with program outcomes

PO PO PO PO PO PO PO PO PO PO PO PO PSO PSO PSO

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3
CO 1 3 3 3
CO 2 3 3 2 3 3 3
CO 3 3 3 2 3 3 2 2 3
CO 4 3 3 2 3 3 2 2 3
CO 5 3 3 2 3 3 2 2 3
CO 6 3 3 2 3 3 2 2 3

Department of Electronics & Communication 27

 Textbooks & References
1. “Elements of Information Theory”, Joy A Thomas, Thomas M Cover, Wiley-Interscience.

2. “Information Theory, Inference and Learning Algorithms”, David JC McKay, Cambridge University
Press

3. “Principles of digital communication”, R G Gallager, Cambridge University Press

4. “Digital Communication Systems”, Simon Haykin, Wiley.

5. “Introduction to Coding Theory”, Ron M Roth, Cambrdige University Press

6. “Error Control Coding : Fundamentals and Applications”, Shu Lin & Daniel J. Costello. Jr., 2nd
Edition.

7. “Modern Coding Theory”, Rüdiger Urbanke and T J Richardson, Cambridge University Press.

Department of Electronics & Communication 28

THANK YOU…

Department of Electronics & Communication 29