17ec54-Information Theory and Coding

SKIT Teaching Process Rev No.: 1.
0
Doc Code: SKIT-EC.Ph5b1.F02 Date: 18-08-2019
Title: Course Plan Page: 1 / 31
Copyright ©2017. cAAS. All rights reserved.
Table of Contents
17EC54 : INFORMATION THEORY AND CODING...................................2
A. COURSE INFORMATION.............................................................................................. 2
1. Course Overview.................................................................................................................. 2
2. Course Content.................................................................................................................... 2
3. Course Material.................................................................................................................... 3
4. Course Prerequisites............................................................................................................. 3
B. OBE PARAMETERS....................................................................................................... 3
1. Course Outcomes................................................................................................................. 3
2. Course Applications............................................................................................................. 4
3. Articulation Matrix............................................................................................................... 5
4. Mapping Justification............................................................................................................ 5
5. Curricular Gap and Content.................................................................................................. 7
6. Content Beyond Syllabus...................................................................................................... 7
C. COURSE ASSESSMENT................................................................................................ 7
1. Course Coverage.................................................................................................................. 7
2. Continuous Internal Assessment (CIA)..................................................................................8
D1. TEACHING PLAN - 1................................................................................................ 8
Module - 1............................................................................................................................... 8
Module – 2............................................................................................................................. 10
E1. CIA EXAM – 1......................................................................................................... 12
a. Model Question Paper - 1................................................................................................... 12
b. Assignment -1................................................................................................................... 13
D2. TEACHING PLAN - 2.............................................................................................. 14
Module – 3............................................................................................................................. 14
Module – 4............................................................................................................................. 16
E2. CIA EXAM – 2......................................................................................................... 17
b. Assignment – 2.................................................................................................................. 18
D3. TEACHING PLAN - 3.............................................................................................. 19
Module – 5............................................................................................................................. 19
E3. CIA EXAM – 3......................................................................................................... 20
b. Assignment – 3.................................................................................................................. 21
F. EXAM PREPARATION................................................................................................. 21
1. University Model Question Paper......................................................................................... 21
2. SEE Important Questions..................................................................................................... 24
Dept EC
Prepared by Checked by
Approved
SKIT Teaching Process Rev No.: 1.0
Note : Remove “Table of Content” before including in CP Book

Each Course Plan shall be printed and made into a book with cover page
Blooms Level in all sections match with A.2, only if you plan to teach / learn at higher
levels
17EC54 : INFORMATION THEORY AND CODING

A. COURSE INFORMATION
1. Course Overview
Degree: B.E Program: EC
Year / Semester : 3/5 Academic Year: 2019-20
Course Title: INFORMATION THEORY AND CODING Course Code: 17EC54
Credit / L-T-P: 4/L SEE Duration: 180 Minutes
Total Contact
50 SEE Marks: 100 Marks
Hours:
CIA Marks: 40 Assignment 1 / Module
Course Plan Author: NAYANA HEGDE Sign Dt:
Checked By: Sign Dt:
2. Course Content
Mod Module Content Teaching Module Blooms
ule Hours Concepts Level
1 Introduction, Measure of information, Information content 10 Entropy
of message, Average Information content of symbols in Markov Model L2,L3
Long Independent sequences, Average Information content
of symbols in Long dependent sequences, Markov Statistical
Model of Information Sources, Entropy and Information rate
of Markoff Sources
2 Source coding theorem, Prefix Codes, Kraft McMillan 10 Uniqueness of L2
Inequality property – KMI Encoding of the Source Output, code
Shannon’s Encoding Algorithm Shannon Fano Encoding
Algorithm, Huffman codes, Extended Huffman coding, Encoding
Arithmetic Coding, Lempel – Ziv Algorithm Algorithms
3 Communication Channels Channel Models, Channel Matrix, 10 Communicatio L2,L3
Dept EC
Approved
Joint probability Matrix, Binary Symmetric Channel, System n channels

Entropies, Mutual Information, Channel Capacity, Channel
Capacity of : Binary Symmetric Channel, Binary Erasure Channel
Channel, Muroga,s Theorem, Continuous Channels capacity
4 Error Control Coding Introduction, Examples of Error control 10 Syndrome L3,L4
coding, methods of Controlling Errors, Types of Errors, calculation
types of Codes, Linear Block Codes: matrix description of
Linear Block Codes, Error Detection and Error Correction Error
Capabilities of Linear Block Codes, Single Error Correcting detection and
hamming Codes, Table lookup Decoding using Standard correction
Array. Binary Cyclic Codes: Algebraic Structure of Cyclic
Codes, Encoding using an (n-k) Bit Shift register, Syndrome
Calculation, Error Detection and Correction
5 Golay Codes, BCH Codes 10 Coding L3,l4
Convolution Codes Convolution Encoder, Time domain
approach, Transform domain approach, Code Tree, Trellis Encoder and
and State Diagram, The Viterbi Algorithm decoder
design
3. Course Material
Mod Details Available
ule
1 Text books
Digital and analog communication systems, K. Sam Shanmugam, John In Lib
Wiley
India Pvt. Ltd, 1996.
2 Digital communication, Simon Haykin, John Wiley India Pvt. Ltd, 2008 In Lib
3 Information Theory and Coding, Muralidhar Kulkarni, K.S. Shivaprakasha,
Wiley
India Pvt. Ltd, 2015, ISBN:978-81-265-5305-1.
2 Reference books
1 ITC and Cryptography, Ranjan Bose, TMH, II edition, 2007 In dept
2 Principles of digital communication, J. Das, S. K. Mullick, P. K. Chatterjee, In dept
Wiley, 1986 - Technology & Engineering
3 Digital Communications Fundamentals and Applications, Bernard Sklar, In dept
Second Edition, Pearson Education, 2016, ISBN: 9780134724058.
4 Information Theory and Coding, K.N.Haribhat, D.Ganesh Rao, Cengage In dept
Learning, 2017
3 Others (Web, Video, Simulation, Notes etc.)
Not Available
Dept EC
Approved
4. Course Prerequisites
SNo Course Course Name Module / Topic / Description Sem Remarks Blooms
Code Level
1 17MAT Engineering Knowledge on set theory 3 L3
31 mathematics
17MAT Engineering Knowledge on probability 3 L3
31 mathematics
17EC44 principles knowledge of principles 4 L4
communication communication system
system
Note: If prerequisites are not taught earlier, GAP in curriculum needs to be addressed. Include in
Remarks and implement in B.5.
B. OBE PARAMETERS
1. Course Outcomes
# COs Teach. Concept Instr Assessmen Blooms’
Hours Method t Method Level
17EC54.1Understand entropy by measure of 4 Entropy Lecture Cia/assigna L2
information content of the message ment/quiz Understand
17EC54.2Apply entropy and oder of 6 Markov Lecture Cia/assigna L3
information sources to analyze Model ment/quiz
Markov model
17EC54.3Understand uniqueness of code 3 Uniqueness Lecture Cia/assigna L2
using Kraft Inequality and prefix property ment/quiz
code
17EC54.4Understand the conversion of 7 Encoding Lecture Cia/assigna L3
information into binary sequence algorithms / PPT ment/quiz Apply
using Shanon, Shanon Fano and
Huffman encoding algorithms
17EC54.5Model continuous and discrete 4 Communica Lecture Cia/assigna L2
communication channels using tion ment/quiz
input, out and joint probability channel
matrix
17EC54.6Determine channel capacity of 6 Channel Lecture Cia/assigna L3
Dept EC
Approved
binary symmetric and binary erasure capacity and ment/quiz

channels using mutual information Tutorial
and Muroga’s theorem
17EC54.7Determine a codeword comprising 3 Syndrome Lecture Cia/assigna L3
of the check bits computed using ( error) ment/quiz
Linear calculation
Block codes, cyclic code.
17EC54.8Apply syndrome calculation and 7 Error Lecture Cia/assigna L2

detect and correct error in binary detection ment/quiz
code using LBC,cyclic code and and
hamming code,Golay code and BCH correction
code
17EC54.9Design encoder circuit for for Linear 2 Encoder Lecture Cia/assigna L3
Block codes, cyclic codes, circuit ment/quiz
convolution codes, BCH and Golay design
codes
17EC54.1 Design decoder circuit for for Linear 8 Decoder Lecture Cia/assigna L4
0 Block codes, cyclic codes, circuit ment/quiz
convolution codes, BCH and Golay design
codes
- Total 50 - - - -
Note: Identify a max of 2 Concepts per Module. Write 1 CO per concept.
2. Course Applications
SNo Application Area CO Level
1 Provide a generalized method of considering microscopic behavior to make CO1 L2
macroscopic predictions, under given conditions.
2 Markov model used in non-observable biological sequence analysis CO2 L3

3 Uniqueness property and prefix codes are widely used in applications that CO3 L2
compress data, including JPEG for images and MP3 for music.
4 Encoding algorithms are used in lossless data compression CO4 L3
5 Transfer information between sender and receiver. CO5 L2
6 To design MIMO system. CO6 L2
7 Used in digital communication. CO7 L3
8 Used in computer memory system CO8 L2
9 Used for speed, secrecy, security, or saving space by shrinking size of CO9 L2
information.
10 Retrieve original information from received message. CO10 L4
Note: Write 1 or 2 applications per CO.
Dept EC
Approved
3. Articulation Matrix
(CO – PO MAPPING)
- Course Outcomes Program Outcomes
# COs PO PO2 PO PO PO PO6 PO PO PO9 PO PO PO Level
1 3 4 5 7 8 10 11 12
17EC54.1 Understand entropy by 3 3 3 2 1 1 1 1 3 1 1 1 L2
measure of information
content of the message
17EC54.2 Apply entropy and oder of 3 3 3 1 1 1 1 1 3 1 1 1 L2
information sources to
statistical Markov model
17EC54.3 Understand uniqueness of 3 3 3 1 1 1 1 1 2 1 1 1 L2
code using Kraft Inequality and
prefix code
17EC54.4 Understand the conversion of 3 3 3 1 1 1 1 1 3 1 1 1 L3
information into binary
sequence using Shanon,
Shanon Fano and Huffman
encoding algorithms
17EC54.5 Model continuous and discrete 3 3 3 2 1 1 1 1 2 1 1 1 L2
communication channels using
input, out and joint probability
matrix
17EC54.6 Determine channel capacity of 3 3 3 2 1 1 1 1 2 1 1 1 L2
binary symmetric and binary
erasure channels using mutual
information and Muroga’s
theorem
17EC54.7 Determine a codeword 3 3 3 2 1 1 1 1 3 1 1 1 L3
comprising of the check bits
computed using Linear
17EC54.8 Apply syndrome calculation 3 3 3 1 1 1 1 1 3 1 1 1 L2
and detect and correct error in
binary code using LBC, cyclic
code and hamming code,Golay
code and BCH code
17EC54.9 Design encoder circuit for 3 3 3 2 1 1 1 1 3 1 1 1 L2
Linear Block codes, cyclic
codes, convolution codes, BCH
and Golay codes
17EC54.10 Design decoder circuit for 3 3 3 1 1 1 1 1 3 1 1 1 L4
Dept EC
Approved
Linear Block codes, cyclic

codes, convolution codes, BCH
and Golay codes
Note: Mention the mapping strength as 1, 2, or 3
4. Mapping Justification
Mapping Justification Mapping
Level
CO PO - -
CO1 PO1 Applies basic mathematics and science knowledge for solution L2
to engineering problems
CO1 PO2 Identify, formulate and review complex engineering problems L2
CO1 PO3 Design digital system components L2
CO1 PO9 Applies to individual and team work for project, internship and L3
mini project
mini project
mini project
mini project
mini project
Dept EC
Approved

mini project
mini project
mini project
mini project
mini project
Note: Write justification for each CO-PO mapping.
5. Curricular Gap and Content

SNo Gap Topic Actions Planned Schedule Planned Resources Person PO Mapping
1
2
3
4
5
Note: Write Gap topics from A.4 and add others also.
Dept EC
Approved
6. Content Beyond Syllabus

SNo Gap Topic Actions Planned Schedule Planned Resources Person PO Mapping
1
2
3
4
5
6
7
8
9
10
Note: Anything not covered above is included here.
C. COURSE ASSESSMENT
1. Course Coverage
Mod Title Teaching No. of question in Exam CO Levels
ule Hours CIA- CIA- CIA- Asg Extra SEE
# 1 2 3 Asg
1 Information Theory 10 2 - - 1 1 2 CO1, L2, L3
CO2
2 Source Coding 10 2 - - 1 1 2 CO3, L2, L3
CO4
3 Information Channels 10 - 2 - 1 1 2 CO5, L2, L3
CO6
4 Error Control Coding and Binary 10 - 2 - 1 1 2 CO7, L2, L3
Cyclic Codes C08
5 Some Important Cyclic Codes and 10 - - 4 1 1 2 CO9, L3,L4

Convolution Codes CO10
- Total 50 4 4 4 5 5 10 - -
Note: Distinct assignment for each student. 1 Assignment per chapter per student. 1 seminar per
test per student.
2. Continuous Internal Assessment (CIA)

Evaluation Weight age in Marks CO Levels
Dept EC
Approved
CIA Exam – 1 30 CO1, CO2, CO3, CO4 L2, l3, L2, l3

CIA Exam – 2 30 CO5, CO6, CO7, C08 L2, L3, L2, l3
CIA Exam – 3 30 CO9, CO10 L3, L4
Assignment - 1 05 CO1, CO2, CO3, CO4 L2, l3, L2, l3

Assignment - 2 05 CO5, CO6, CO7, CO8 L2, L3, L2, l3
Assignment - 3 05 CO9, CO10 L3, L4
Seminar - 1
Seminar - 2
Seminar - 3
Other Activities – define

– Slip test
Final CIA Marks 40 - -
Note : Blooms Level in last column shall match with A.2 above.
D1. TEACHING PLAN - 1

Module - 1
Title: Information Theory Appr 16 Hrs
Time:
a Course Outcomes - Blooms
- The student should be able to: - Level
1 Understand entropy by measure of information content of the CO1 L2
message
2 Apply entropy and oder of information sources to statistical Markov CO2 L3
model
b Course Schedule - -
Class Module Content Covered CO Level
No
1 Introduction to Subject, course objectives and outcomes C01 L2
2 Information, data, measure of information C01 L2
3 Information content of message C01 L2
4 Average Information content of symbols in Long Independent C01 L2
sequences
5 Average Information content of symbols in Long dependent C02 L3
sequences
6 Markov Statistical Model of Information Sources C02 L3
7 Markov Statistical Model of Information Sources C02 L3
8 Entropy and Information rate of Markov Sources C02 L3
Dept EC
Approved

c Application Areas CO Level

1 Provide a generalized method of considering microscopic behavior to CO1 L2
make macroscopic predictions, under given conditions.
2 Markov model used in non-observable biological sequence analysis CO2 L3
d Review Questions - -
1 With a neat block diagram explain information(communication CO1 L2
system)
2 Define symbol rate, self information, zero memory source, average CO1 L2
information, information rate
3 Obtain an expression for entropy of zero memory source information CO1 L2
source emitting independent sequence of symbols
4 Discuss various properties of entropy CO1 L2
5 A code is composed of dots and dashes. Assuming that adashis 3 CO1 L2
times long as a dot has 1/3 probability of occurrence. Calculate
i)information in dot and dash ii)the entropy of dot dash code iii)the
average rate of information if dot lasts for 10 msec and this time is
allowed between symbols.
6 Find relation between Hartelys, nats and bits CO1 L2
7 The output of an information source consists of 128 sysmbols,16 of CO1 L2
which occur with probability of 1/32 and remaining with a probability
of1/224. The source emits 1000 symbols per second. Assuming
symbols are chosen randomly, find entropy and average rate of
information.
8 A pair of dice is tossed simultaneously in an experiment. Outcome of CO1 L2
the first dice is noted as X1 and outcome of second dice as X2. If the
two events are :
A={X1,X2 : such as (X1+X2)<=8} ;B={X1,X2 :such as X1>X2}
Then find the self-information of A and B and entropy of the
experiment.
9 State diagram of Markov source is shown in fig. Calculate: State CO2 L3
probability, state entropy, Entropy of the source.
10 State diagram of Markov source is shown in fig. Calculate: State CO2 L3

probability, state entropy , Entropy of the source.
Dept EC
Approved
11 For the first order Markov source shown in fig, find state probabilities, CO2 L3
entropy of the states, entropy of the source and G1, G2.
12 State diagram of Markov source is shown in fig Calculate: State CO2 L3

probability, state entropy , Entropy of the source
13 For the first order Markoff source shown in fig, find state CO2 L3
probabilities, entropy of the states, entropy of the source
e Experiences - -
1 CO1 L2
2
3
4 CO3 L3
5
Dept EC
Approved
Module – 2
Title: Source Coding Appr 10 Hrs
Time:
1 Understand uniqueness of code using Kraft Inequality and prefix code CO3 L2
2 Understand the conversion of information into binary sequence using CO4 L3
Shanon, Shanon Fano and Huffman encoding algorithms
No
11 Source coding theorem CO3 L2
12 Prefix Codes CO3 L2
13 Kraft McMillan CO3 L2
Inequality property – KMI
14 Encoding of the Source Output CO4 L3
15 Shannon’s Encoding Algorithm CO4 L3
16 Shannon Fano Encoding Algorithm CO4 L3
17 Huffman codes CO4 L3
18 Extended Huffman coding CO4 L3
19 Arithmetic Coding CO4 L3
20 Lempel – Ziv Algorithm CO4 L3

1 Uniqueness property and prefix codes are widely used in applications CO3 L2
that compress data, including JPEG for images and MP3 for music.
2 Encoding algorithms are used in lossless data compression CO4 L3
14 Define coding. Explain necessity of coding. CO3 L2
15 Explain prefix property with an example. CO3 L2
16 What is KRAFT inequality? Explain with suitable example. CO3 L2
17 Explain code efficiency and code redundancy CO3 L2
18 State and prove source coding theorem. CO3 L2
19 State and prove Shanon’s first theorem CO3 L2
20 Explain classification of binary codes. CO3 L2
Dept EC
Approved
21 Check for KMI property for the following set of codes. CO3 L2
A 1
B 10
C 110
D 1110
E 1111
22 Apply Shannon encoding algorithm and generate binary codes for the set of symbols CO4 L2
given in table below. Also find efficiency.
Symbol A B C D E F G
P 1/2 1/4 1/8 1/16 1/32 1/64 1/64
23 Using Shanon-Fano encoding algorithms find the code words and efficiency and CO4 L2
redundancy for the probabilities given in the table
Symbo A B C D E F G H I
l
P 0.2 0.18 0.15 0.12 0.10 0.08 0.07 0.05 0.03

2
24 A discrete memory less source has an alphabet of seven symbols with probabilities as 4 L2
given below:
Symbol A B C D E F G
P 0.25 0.25 0.125 0.125 0.125 0.0625 0.0625

Compute Huffman Code for the set of symbols shown above by moving
combined symbols as high as possible. Find efficiency and variance.
25 Consider a DMS with X={X,Y,Z} with respective probabilities CO4 L2

P={0.6,0.2,0.2}. Find code word for message “YXZXY” using arithmetic
coding.
26 Encode the following information using LZ algorithm. ”THIS_IS_HIS_HIT” CO4 L2
27 Encode the following input string using LZ algorithm CO4 L2
W_PNW_NW_WNP_P
e Experiences - -
1 CO1 L2
2
3
4 CO3 L3
5
Dept EC
Approved
E1. CIA EXAM – 1

a. Model Question Paper - 1
Crs 15EC54 Sem:5 I Marks: 30 Time: 75 minutes
Code:
Course: Information Theory and Coding
- - Note: Answer any 1 full question from each module Marks CO Level
1 a Discus various properties of entropy 5 CO1 L2
b The output of an information source consists of 128 symbols,16 of which occur 5 CO1 L2
with probability of 1/32 and remaining with a probability of1/224. The source
emits 1000 symbols per second. Assuming symbols are chosen randomly, find
entropy and average rate of information.
c A pair of dice is tossed simultaneously in an experiment. Outcome of the first dice 5 CO1 L2
is noted as X1 and outcome of second dice as X2. If the two events are :
A={X1,X2 : such as (X1+X2)<=8} ;B={X1,X2 :such as X1>X2}
Then find the self-information of A and B and entropy of the experiment.
d
2 a Define:- symbol rate, self-information, zero memory source, average self- 5 CO1 L2
information, information rate
b For the first order Markov source shown in fig, find state probabilities, entropy of 10 CO2 L3
the states, entropy of the source and G1, G2.
3 a Using Shanon’s binary encoding algorithms find the code words and efficiency 5 CO4 L2
and redundancy for the probabilities given in the table
Symb A B C D E F G H I
ol
P 0.25 0.15 0.15 0.12 0.10 0.08 0.06 0.05 0.04
b Using Shanon-Fano encoding algorithms find the code words and efficiency and 5 CO4 L2
redundancy for the probabilities given in the table
Symbol A B C D E
P 0.1 0.5 0.2 0.125 0.125

5
c Explain Kraft Inequality with examples 5 CO3 L2
d
4 a A discrete memory less source has an alphabet of seven symbols with 8 CO4 L2
probabilities as given below
Dept EC
Approved
Symbo A B C D E F G H
l
P 7/3 8/39 6/39 10/3 3/39 1/39 2/39 2/39

9 9
b Consider a DMS with X={X,Y,Z} with respective probabilities 7 CO4 L2
coding.
c
d
b. Assignment -1
Note: A distinct assignment to be assigned to each student.
Model Assignment Questions
Crs Code: 15EC54 Sem: I Marks: 5 / 10 Time: 90 – 120 minutes
Note: Each student to answer 2-3 assignments. Each assignment carries equal mark.
SNo USN Assignment Description Mark CO Level
s
1 Discuss additive and symmetric property of entropy 6 CO1 L2
2 A binary information source produces message 0 and 1 5 CO1 L2
with P and 1-P. Determine the entropy of this source and
sketch the variations of entropy with P.
3 Prove that information content of N independent messages 5 CO1 L2
are additive.
4 For the Markov source shown, find source entropy and G1, 10 CO2 L3
G2, G3
5 A black and white TV consists of 526 lines of picture 4 CO1 L2

information. Assume each line consists of 526 pixels and
each can have 255 brightness level. Picture is repeated
at30 frames/sec. Calculate the rate of information
conveyed by TV for viewer.
Dept EC
Approved
6 A pair of dice is tossed simultaneously in an experiment. 5 CO1 L2

Outcome of the first dice is noted as X1 and outcome of
second dice as X2. If the two events are :
A={X1,X2 : such as (X1+X2)<=8} ;B={X1,X2 :such as
X1>X2}
Then find the self-information of A and B and entropy of
the experiment.
7 A certain data source has 8 symbols that are produced in 5 CO1 L2
blocks of 4 at a rate of 500 blocks/sec. The first symbol in
each block is always the same. The remaining 3 are filled
by any of the 8 symbols with equal probability. What is the
entropy of this source?
8 The output of an information source consists of 128 5 CO1 L2

symbols,16 of which occur with probability of 1/32 and
remaining with a probability of1/224. The source emits
1000 symbols per second. Assuming symbols are chosen
randomly, find entropy and average rate of information.
9 Define: - symbol rate, self-information, zero 5 CO1 L2
memory sources, average self-information,

Information rate
10 A card is drawn from a deck. You are told it is a spade. 5 CO1 L2
How much information did you receive. How much
information is received if it is told as ace.

Module – 3
Title: Information Channels Appr 10 Hrs
Time:
1 Model continuous and discrete communication channels using input, CO5 L2
out and joint probability matrix
2 Determine channel capacity of binary symmetric and binary erasure CO6 L3
channels using mutual information and Muroga’s theorem
No
21 Communication Channels CO5 L2
22 Channel Models, Channel Matrix CO5 L2
Dept EC
Approved
23 Joint probability Matrix, Binary Symmetric Channel CO5 L2

24 System Entropies CO5 L3
25 Mutual Information, Channel Capacity CO6 L3
26 Channel Capacity of Binary Symmetric Channel CO6 L3
27 Channel Capacity of Binary Symmetric Channel CO6 L3
28 Channel Capacity Binary Erasure Channel CO6 L3
29 Muroga,s Theorem CO6 L3
30 Muroga,s Theorem, Continents Channels CO6 L3

1 Transfer information between sender and receiver. CO5 L2
2 To design MIMO system. CO6 L3
27 State and prove Shanon Hartley theorem CO5 L3
28 Write a short note on channel matrix, JPM, properties of JPM and give CO5 L3
example for channel diagram.
29 Prove the identities CO5 L3
i)H[X,Y]=H[X]+H[Y]
ii)H[X,Y]=H[X]+H[Y/X]
30 Find H[X],H[Y],H[X Y], H[X/Y] and H[Y/X] for the channel shown below CO5 L3
31 Define mutual information and its properties CO6 L3

32 Prove mutual information CO6 L3
I(X,Y)=H(X)-H(X/Y)=H(Y)-H(Y/X)
33 Derive the expression for channel capacity of binary channel shown CO6 L3
34 Prove that H(X/Y)=p.H(X) for a binary erasure channel CO6 L3

35 Two noisy channels are cascaded whose channel matrices are given by
Dept EC
Approved
find the overall mutual information I(X,Y) and I(X,Z)

36 A Gaussian channel has 10 Mhz BW is (S/N) ratio is 100.Calculate CO6 L3
channel capacity and maximum information rate.
e Experiences - -
1 CO1 L2
2
3
4 CO3 L3
5
Module – 4
Title: Error Control Coding Appr 10 Hrs
Time:
1 Determine a code word comprising of the check bits computed using CO3 L2
Linear
2 Apply syndrome calculation and detect and correct error in binary CO4 L3
code using LBC, cyclic code and hamming code
No
31 Introduction, Examples of Error control coding CO7 L2
32 methods of Controlling Errors CO7 L2
33 Types of Errors, types of Codes CO7 L2
34 Linear Block Codes: matrix description of Linear Block Codes CO7 L3
35 Error Detection and Error Correction Capabilities of Linear Block CO8 L3
Codes,
36 Single Error Correcting hamming Codes, Table lookup Decoding using CO8 L3
Standard Array.
37 Algebraic Structure of Cyclic Codes CO8 L3
38 Encoding using an (n-k) Bit Shift register CO8 L3
39 Syndrome Calculation CO8 L3
40 Error Detection and Correction CO8 L3
Dept EC
Approved

1 Used in digital communication. CO7 L2
2 Used in computer memory system CO8 L3
d Review Questions - -37

37 Draw the block diagram of digital communication system and explain CO7 L2
functions of each block
38 What are different methods of controlling errors CO7 L2
39 What are types of error and types of codes in error control coding CO7 L2
40 Compare fixed length and variable length code CO7 L2
41 Define terms burst error, systematic LBC, galois Field, Hamming CO7 L2
weight
42 Define hamming weight, hamming distance and minimum distance of CO7 L2
linear block code
43 If C is valid code vector then prove that CH T=0 where HT is transpose of CO7 L2
parity check matrix H
44 Test Hamming bound of (7,4) hamming code and show that it is a CO7 L3
perfect code.
45 For a systematic LBC (6,3) parity check matrix is CO8 L3
find all possible code vector, minimum weight of the code, parity
check matrix, for received code R=110010, detect and correct the
error occurred.
46 For a Linear Block Code the syndrome is given by: CO8 L3
S1= r1+r2 + r3+ r5 ,
S2= r1+r2 + r4+ r6 ,
S3= r1+r3+ r4+ r7
(i) Find Generator Matrix (ii) Find Parity Check Matrix (ii) Draw the Encoder
Circuit (iii) How many errors can be detected and corrected?
47 For a (6,3) cyclic code Find out: CO8 L3
i)Generator Polynomial ii)Generator Matrix
iii)Parity Check matrix iv)Equation for code words
48 A (7,4) Cyclic Code has the generator polynomial g(x) = 1+x+x 3. Calculate the CO8 L3
syndrome for received vector R=[1 1 1 1 1 1 1],R=[1 0 1 0 1 0 1].
Draw syndrome calculation circuit.
e Experiences -
1 L2
2
3
Dept EC
Approved
4 L3
5
E2. CIA EXAM – 2

Crs 15EC54 Sem: I Marks: 30 Time: 75 minutes
Code:
- - Note: Answer any 1 full questions, each from one module. Mark CO Level
s
1 a State and prove source coding theorem. 5 CO3 L3
b Apply Shannon encoding algorithm and generate binary codes for the 5 CO4 L3
set of symbols given in table below. Also find efficiency.
c Check for KMI property for the following set of codes 5 CO3 L3
2 a A discrete memory less source has an alphabet of seven symbols with probabilities 8 CO4 L3
as given below:
b Consider a DMS with X={X,Y,Z} with respective probabilities 7 CO4 L3
coding.
c
d
Dept EC
Approved
3 a Write a short note on channel matrix, JPM, properties of JPM and give 10 CO5 L3
example for channel diagram.
b An analog source has a bandwidth of 4KHz. The signal is sampled at 2.5 5 CO5 L3
times the Nyquist Rate and each sample is quantized into 256 equally likely
levels. Assume that the successive samples are statistically independent.
Find the information rate of the source. Can the output of this source be
transmitted without error over an analog channel of Bandwidth 50Khz and
S/N = 20db. If the output of the source is to be transmitted without error
over an analog channel having S/N = 10, compute the bandwidth required.
4 a Consider a Symmetric Channel whose channel diagram is given by 10 CO6 L3

Find channel capacity.
b Write a note on continuous channel and differential entropy. 5 CO6 L3
b. Assignment – 2
Crs Code: 15EC54 Sem: I Marks: 5 / 10 Time: 90 – 120 minutes
s
1 Construct Huffman code for given data and find 5 CO5 L3
theefficiency
2 For the data given apply shanon’sencoding algorithm and 5 CO5 L3
find the code words. Find the efficiency.
3 Apply shanon -fano algorithm for the data and find the 5 CO5 L3
code words.
½,1/4,1/8,1/8,
4 Using arithmetic coding find out the code words for given 5 CO5 L3
input sequence. “ABABHT”
5 Construct the code tree for the given code. 5 CO4 L2

6 Check KMI property for given set of codes. 5 CO4 L2
7 Check whether the given set of codes is prefix code. 5 CO4 L2
8 Using Lempel Ziv coding find out the code words. 5 CO5 L3
9 Encode the following information using LZ algorithm. 5 CO5 L3
”THIS_IS_HIS_HIT”
10 Write a short note on Shanon Fano algorithm 5 CO5 L3
Dept EC
Approved

Module – 5
Title: Some Important Cyclic codes and convolutional code Appr 10 Hrs
Time:
1 Design encoder circuit for Linear Block codes, cyclic codes, CO3 L2
convolution codes, BCH and Golay codes
2 Design decoder circuit for Linear Block codes, cyclic codes, CO4 L3
convolution codes
No
41 Golay Codes, BCH Codes CO9 L3
42 Convolution Encoder CO9 L4
43 Time domain approach CO9 L4
44 Transform domain approach CO9 L4
45 Code Tree CO9 L4
46 Code Tree CO10 L4
47 Trellis and State Diagram CO10 L4
48 Trellis and State Diagram CO10 L4
49 The Viterbi Algorithm CO10 L4
50 The Viterbi Algorithm CO10 L4

1 Used for speed, secrecy, security, or saving space by shrinking size of CO9 L2
information.
2 Retrieve original information from received message. CO10 L3
51 Write short note on Golay code and BCH code CO9 L3
52 What are convolution codes? How they are different from block codes. CO9 L3
53 For a (3,1,2) convolution encoder with generator sequences CO9 L4
g =110, g =101,g =111
1 2 3
Find the encoder block diagram

Find generator matrix and o/p for 11101
Find the code word for 11101 using time domain approach
draw the state diagram and tree diagram
54 A (15,5) binary cyclic code has a generator polynomial CO9 L4
Dept EC
Approved
Draw encoder block diagram

Find code polynomial for message polynomial
55 For a (6,3) cyclic code Find out: O9 L4

56 A (7,4) Cyclic Code has the generator polynomial g(x) = 1+x+x 3 . Calculate the CO9 L4
Draw syndrome calculation circuit
57 CO9 L4
For the encoder shown in the fig. Draw the state diagram. Draw the
code tree. Find code word for 10111.
e Experiences - -
1 CO1 L2
2
3
4 CO3 L3
5
E3. CIA EXAM – 3

Crs 15EC54 Sem: I Marks: 30 Time: 75 minutes
Code:
- - Note: Answer any 2 questions, each carry equal marks. Mark CO Level
s
1 a For a Linear Block Code the syndrome is given by: 10 CO9 L4
Dept EC
Approved
S1= r1+r2 + r3+ r5 ,

S2= r1+r2 + r4+ r6 ,
S3= r1+r3+ r4+ r7
(i) Find Generator Matrix (ii) Find Parity Check Matrix (ii) Draw the Encoder
Circuit (iii) How many errors can be detected and corrected?
b Write short note on Golay code and BCH code 5 CO10 L3
2 a For a (6,3) cyclic code Find out: 8 CO9 L4

b A (7,4) Cyclic Code has the generator polynomial g(x) = 1+x+x 3 . Calculate the 7 CO9 L4
Draw syndrome calculation circuit.
c
d
3 a Write a note on Trellis diagram with example 15 CO9 L4

b
4 a For a (2,1,3) convolution encoder with g1=1101 and g2=1011 15 CO10 L4

draw the convolution encoder block diagram. Write down state
transition table. Draw code tree. Find the encoder output produced
by message 11101 traversing through the code tree.
b. Assignment – 3
Crs Code: 15EC54 Sem: 5 I Marks: 5 / 10 Time: 90 – 120 minutes
s
1 Obtain the output of the (2,1,2) convolution encoder for 10 CO9 L4
g1=111,g2= 011 for message 11101. Detail the contents
of the shift register after every clock.
2 Consider a convolution encoder with g1=110, g2=101, 10 CO9 L4
g3=111
find the constraint length, find the rate. Draw the encoder
block diagram.
3 Explain state diagram and state transition table. 5 CO9 L2
4 Explain tree diagram with an example. 5 CO9 L3
Dept EC
Approved
5 Explain Tellis diagram with an example. 5 CO10 L3

6 What do you mean by transfer function of a convolution 5 CO10 L3
code.
7 Write distance properties of constitutional codes. 5 CO10 L3
8 Write a short note on decoding of convolution codes. 5 CO10 L3
9 Explain Viterbi algorithm. 10 CO10 L3
10 What do you mean by catastropic code 5 CO10 L3
F. EXAM PREPARATION
1. University Model Question Paper
Course: Information Theory and Coding Month / Year May /2018
Crs Code: 15EC54 Sem: 5 Marks: 80 Time: 180
minutes
- Note Answer all FIVE full questions. All questions carry equal marks. Mar CO Leve
ks l
1 a Derive an expression for average entropy of long independent 4 CO1 L2
messages.
b Explain Markov statistical model used to represent dependent 4 L2 L2
information sources.
c Find H, G1,G2 for the given model 8 CO2 L3
OR
- a Define information. Explain how information is measured. Justify the 6 CO1 L2
use of logarithmic function in measure of information.
b Establish relation between i)Hartely and nats ii)nats and bits 4 CO2 L2
c For the Markov model find State probability, state entropy and source 8 CO2 L3
entropy.
2 a Apply Shanon’s encoding algorithms to generate binary code for set of 12 C03 L3
information
Dept EC
Approved
Sym AA BB CC DD EE FF GG
P 9/3 9/3 3/ 3/3 3/3 3/3 2/32

2 2 32 2 2 2
b Expalin prefix code 04 C03 L3
OR
- a Consider the following source. 6 CO3 L3
Sym AA BB CC DD EE FF
P 0.4 0.2 0.2 0.1 0.0 0.02

8
Find the code word using Shanon Fano algorithm.

b Consider the following source. 10 CO4 L3
Sy AA BB C D EE FF GG
m C D
P 1/ 1/ 1/ 1/ 1/ 1/27 1/27
3 27 3 9 27
Find the code word using Huffman algorithm.
3 a Write the channel matrix for the channel diagram given. 6 CO5 L3
b 10 L3
For the channel matrix given calculate H(X),H(Y) and channel capacity if
P(x1)=0.6
- a State and explain Shanon Hartely law. Derive expression for upper limit 7 CO5 L3
of channel capacity.
b Define mutual information and explain all properties of mutual 9 L3
Dept EC
Approved
information. Explain data rate.
4 a Find H for given generator matrix. 4 CO7 L4
G=1 1 0 1 0 0
111010
0 11 0 0 0
b Consider a systematic (8,4) LBC whose parity check sequence are given 12 L4
by
v4=u1+u2+u3
V5=u0+u1+u2
v6=u0+u1+u3
v7=u0+u2+u3
Write generator and parity check matrices. Draw the encoder diagram.
- a Consider a (7,4) Cyclic code with g(x)=1+x+x2 and obtain the code 12 CO7 L3
polynomial in non symmetric form for the input sequence 1010 and
1100
b Obtain generator and parity check matrix for an (n,k) cyclic code with 4 CO8 L4
g(x)=1+x+x2
5 a For the convolution code given, find the code rate and constraint CO9 L4
length.
Draw the tree diagram, trellis diagram
b For a convolution encoder has generator polynomial vector 8 CO10 L4

g1=100,g2=111 and g3=101. Draw encoder diagram. If the input is
10110. find out the output using transform domain approach.
OR
a Consider the convolution encoder. Draw the state diagram. Draw the 8 CO9 L4
code tree. Find the code sequence for 10111
Dept EC
Approved
b For a (2,1,2) convolutional encoder with generator sequence g1=111, 8 C010 L4

g2=101
draw the encoder circuit. Find the code word for message sequence
10111 using time domain approach.
2. SEE Important Questions

Course: Information Theory and Coding Month / Year May /2018
Crs Code: 15EC54 Sem: 4 Marks: 80 Time: 180
minutes
Note Answer all FIVE full questions. All questions carry equal marks. - -
Mo Qno. Important Question Marks CO Year
dul
e
1 1 Derive an expression for average information content of long 03 CO1 2018
independent sequence
2 For the given Markov source find out 10 CO2 2018
1)State probability
2)State entropy
3)Source entropy
4)G1 and G2
3 Define self information, entropy and information rate 03 CO1 2018

4 Mention properties of entropy and prove external property. 07 CO1 2018
5 A source emits s1,s2,s3,s4 with probabilities 7/16,5/16,1/8 04 CO1 2018
and1/8. Prove that H(s )=2H(s) 2
6 A facsimile with 2.25x10 6 pixels/frame. For a good transmission 12 05 CO1 2018

brightness levels are necessary. All these levels are equally likely to
Dept EC
Approved
occur. Find rate of information is one picture is transmitted in 3 sec.
2 1 A discrete memory less source has probabilities 10 CO4 2018
find the average code word and variance.
2 Using Shanon fano 06 CO4 2018

encoding theorem
find the average
code word length and efficiency.
3 Write a short note on Lempel Ziv algorithm 05 CO4 2018

4 Derive source coding theorem 05 CO4 2018
5 Using Shanon 06 CO4 2018
coding algorithm find the code word, efficiency and redundancy.
3 1 Find the capacity of 04 CO5 2018

channel whose noise
matrix is
2 Define mutual information. Write properties of mutual information.

Prove that if I(X;Y)=H(X)+H(Y)-H(XY) bits/symbol.
3 06 CO6 2018
Channel has following characteristics. Find H(X),H(Y),H(X,Y)
4 Derive expression for channel capacity of binary erasure channel. 05 CO6 2018
5 Write a note on difference entropy 03 CO6 2018
4 1 For a systematic (6,3) LBC, parity is given by 10 CO8 2015

1)Find all possible code vector
2)Find the minimum weight of the code.
3)Find parity check matrix
Dept EC
Approved
4)for R=110010 detect and correct the error

2 What are different types of methods of controlling errors 06 CO7 2015
5 1 What is binary cyclic code? Describe the features of encoder and 10 CO10 2015
decoder used for cyclic codes using (h-k) bit shift register.
2 Write a short note on Golay code and BCH code. 06 CO9 2015
Dept EC
Approved

17ec54-Information Theory and Coding

Uploaded by

Copyright:

Available Formats

17ec54-Information Theory and Coding

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

17ec54-Information Theory and Coding

Uploaded by

Copyright:

Available Formats

SKIT Teaching Process Rev No.: 1.

Note : Remove “Table of Content” before including in CP Book

17EC54 : INFORMATION THEORY AND CODING

Joint probability Matrix, Binary Symmetric Channel, System n channels

binary symmetric and binary erasure capacity and ment/quiz

17EC54.8Apply syndrome calculation and 7 Error Lecture Cia/assigna L2

2 Markov model used in non-observable biological sequence analysis CO2 L3

Linear Block codes, cyclic

CO6 PO2 Identify, formulate and review complex engineering problems L2

5. Curricular Gap and Content

6. Content Beyond Syllabus

Note: Anything not covered above is included here.

5 Some Important Cyclic Codes and 10 - - 4 1 1 2 CO9, L3,L4

2. Continuous Internal Assessment (CIA)

CIA Exam – 1 30 CO1, CO2, CO3, CO4 L2, l3, L2, l3

Assignment - 1 05 CO1, CO2, CO3, CO4 L2, l3, L2, l3

Other Activities – define

D1. TEACHING PLAN - 1

9 Entropy and Information rate of Markov Sources C02 L3

c Application Areas CO Level

10 State diagram of Markov source is shown in fig. Calculate: State CO2 L3

12 State diagram of Markov source is shown in fig Calculate: State CO2 L3

c Application Areas CO Level

P 1/2 1/4 1/8 1/16 1/32 1/64 1/64

P 0.2 0.18 0.15 0.12 0.10 0.08 0.07 0.05 0.03

P 0.25 0.25 0.125 0.125 0.125 0.0625 0.0625

25 Consider a DMS with X={X,Y,Z} with respective probabilities CO4 L2

E1. CIA EXAM – 1

P 0.25 0.15 0.15 0.12 0.10 0.08 0.06 0.05 0.04

P 0.1 0.5 0.2 0.125 0.125

P 7/3 8/39 6/39 10/3 3/39 1/39 2/39 2/39

5 A black and white TV consists of 526 lines of picture 4 CO1 L2

6 A pair of dice is tossed simultaneously in an experiment. 5 CO1 L2

8 The output of an information source consists of 128 5 CO1 L2

memory sources, average self-information,

D2. TEACHING PLAN - 2

23 Joint probability Matrix, Binary Symmetric Channel CO5 L2

c Application Areas CO Level

31 Define mutual information and its properties CO6 L3

34 Prove that H(X/Y)=p.H(X) for a binary erasure channel CO6 L3

find the overall mutual information I(X,Y) and I(X,Z)

c Application Areas CO Level

d Review Questions - -37

E2. CIA EXAM – 2

4 a Consider a Symmetric Channel whose channel diagram is given by 10 CO6 L3

5 Construct the code tree for the given code. 5 CO4 L2

D3. TEACHING PLAN - 3

c Application Areas CO Level

Find the encoder block diagram

54 A (15,5) binary cyclic code has a generator polynomial CO9 L4

Draw encoder block diagram

55 For a (6,3) cyclic code Find out: O9 L4

E3. CIA EXAM – 3

S1= r1+r2 + r3+ r5 ,

2 a For a (6,3) cyclic code Find out: 8 CO9 L4

3 a Write a note on Trellis diagram with example 15 CO9 L4

4 a For a (2,1,3) convolution encoder with g1=1101 and g2=1011 15 CO10 L4

5 Explain Tellis diagram with an example. 5 CO10 L3