Study Material
Subject Name: Information Theory & Coding
Subject Code: PECECE504A
Module 1
Information Theory: Basics of information theory – Entropy, Information rate,
classification of codes, Kraft McMillan inequality, Source coding theorem, Shannon-Fano
coding, Huffman coding, Extended Huffman coding, uniquely detectable codes, Joint and
conditional entropies, Mutual information – Discrete memoryless channels – BSC, BEC –
Channel capacity, Shannon limit.
Information Source – the symbols are undefined, and the “meaning” of the information being
sent is not dealt with – only an abstract measure of the “amount” or “quantity.
Examples
Text of various forms – reports, papers, memos, books, scientific data (numbers)
Pictures of various forms – diagrams, art, photographic images, scientific data (e.g. from
satellites)
Sound of various forms – music, speech, noises, recorded sound, radio animation of various
forms – moving pictures, film, video tape, video camera, television equations representing
mathematical ideas or algorithms – two textual representation systems with graphical output:
Tex & Mathematica
Information
A quantitative measure of the amount of information any event represents. I(p) = the amount
of information in the occurrence of an event of probability p.
Entropy
The average amount of information received on a per symbol basis from a source S = {s1, …,
sq} of symbols, si has probability pi. It is measuring the information rate.
In radix r, when all the probabilities are independent:
Entropy is amount of information in probability distribution.
Module 1 (Questions)
Information Theory
Q Modu Question & Hint Marks BL
No. le
1. 1 In a binary communication system (Figure 1.1), either 0 or 1 is 10 Evaluate 5
transmitted. Due to channel noise, a 1 can be received as 0 and vice
versa. Let m0 and m1 denote the events of transmitting 0 and 1,
respectively. Let r0 and r1 denote the events of receiving 0 and 1,
respectively Given P(m0) = 0.5, P(r1/m0) = 0.2 and P(r0/m1) = 0.1, (a)
Find P(r0) and P(r1). (b) If a 1 was received, what is the probability that
a 1 was sent? (c) If a 0 was received, what is the probability that a 0 was
sent? (d) Calculate the probability of error, Pe. (e) Calculate the
probability (Pc ) that the transmitted signal correctly reaches the
receiver.
Sol.
2 1 For the binary channel shown in Figure, Construct (a) the channel 10 Analyze 4
matrix, (b) P(y1) and P(y2) when P(x1) = P(x2) = 0.5, and (c) the joint
probabilities P(x1, y2) and P(x2, y1) when P(x1) = P(x2) = 0.5.
Sol.
3 1 Prove that the channel capacity of an ideal AWGN channel with infinite 5 Analyze 4
bandwidth is given by
Where, S and 𝜂/2 are the average signal power and the power spectral
density of the white Gaussian noise respectively.
Sol.
4 1 A telegraph source produces two symbols, dash and dot. The dot 10 Evaluate 5
duration is 0.2 s. The dash duration is 2 times the dot duration. The
probability of the dots occurring is twice that of the dash and the time
between symbols is 0.1 s. Determine the information rate of the
telegraph source.
Sol.
5 1 Consider an additive white Gaussian noise channel with 4 KHz 5 Evaluate 5
bandwidth and noise power spectral density η/2=10-2 w/Hz. The signal
power required at the receiver is 0.1 mw. Calculate capacity of this
channel.
Hint: Use Channel capacity
6 Calculate Entropy for English alphabet if 4 letters occur with 5 Evaluate 5
probability of 0.1, 5 letters occur with probability of 0.07, 8 letters occur
with probability of 0.02 and remaining letters occur with probability of
0.01.
Hint: Use Channel capacity
7 An alphabet consists of the letters A, B, C and D. The probability of 5 Evaluate 5
occurrence is P(A) = 0.4, P(B) = 0.1, P(C) = 0.2 and P(D) = 0.3. Find
the Huffman code of the symbols.
Hint: Use Huffman code
8 A high resolution black and white TV picture contains about 2 x 106 5 Evaluate 5
picture elements and 16 different brightness levels. Pictures are repeated
at the rate of 32 per second. All picture elements are assumed to be
independent and all levels have equal likelihood of occurrence.
Calculate the average rate of information conveyed by this TV picture
source.
Hint: Use Huffman coding
9 In an information source containing 5 symbols A,B,C,D,E each symbol 5 Evaluate 5
having a frequency of repetition of 12,8,6,6,4 respectively. Calculate the
probabilities of occurrence of each symbol and find out the code
generated for the individual symbols as per the Huffman algorithm.
Hint: Use Huffman coding
10 Given an AWGN channel with 4kHz bandwidth and the noise power 5 Evaluate 5
𝜂
spectral density =10-12W/Hz. The signal power required at the receiver
2
is [Link] the capacity of the channel.
Hint: Use BEC – Channel capacity
Module 2
Error Control Coding: Block Codes
Definitions and Principles: Hamming weight, Hamming distance, Minimum distance
decoding – Single parity codes, Hamming codes, Repetition codes – Linear block
codes, Cyclic codes – Syndrome calculation, Encoder and decoder – CRC Techniques
of coding and decoding of Cyclic codes.
Error Control Coding:
Channel coding:
• Transforming signals to improve communications performance by increasing the
robustness against channel impairments (noise, interference, fading,).
• Waveform coding: Transforming waveforms to better waveforms.
• Structured sequences: Transforming data sequences into better sequences, having
structured redundancy.
Channel coding schemes are listed below:
--Automatic repeat request (ARQ)
--Block coding
--Convolution coding
Automatic Repeat reQuest (ARQ)
Full-duplex connection, error detection codes. The receiver sends feedback to the
transmitter, saying that if any error is detected in the received packet or not (Not-
Acknowledgement (NACK) and Acknowledgement (ACK), respectively). The
transmitter retransmits the previously sent packet if it receives NACK.
•Forward Error Correction (FEC)
Simplex connection, error correction codes. The receiver tries to correct some errors
•Hybrid ARQ (ARQ+FEC)
Full-duplex, error detection and correction codes
Block Codes
Block codes are a type of error control coding technique used in digital communication
systems to detect and correct errors that occur during data transmission. They are based
on the concept of dividing the data into fixed-size blocks and adding redundant bits to
each block. These redundant bits, also known as error detection and correction codes,
are calculated based on the data bits and are appended to the original data to form a
coded block.
Let us consider some blocks of data, which contains k bits in each block. These bits are
mapped with the blocks which has n bits in each block. Here n is greater than k. The
transmitter adds redundant bits which are n−k bits.
The ratio k/n is the code rate. It is denoted by r and the value of r is r < 1.
The n−k bits added here, are parity bits. Parity bits help in error detection and error
correction, and also in locating the data. In the data being transmitted, the left most bits
of the code word correspond to the message bits, and the right most bits of the code
word correspond to the parity bits.
Module 2 (Questions)
Q Modul Question & Hint Marks BL
No. e
1. 2 Evaluate the syndrome vector for single bit error for parity 10 Evaluate 5
check matrix given by
1110 100
0111 010
1101 001
Hint: Use theory of linear block code
2 2 Construct an efficient, uniquely decodable binary code, 5 Analyze 4
having the prefix property and having the shortest possible
average code length per symbol, for an alphabet whose five
letters appear with these probabilities:
Letter Probability
A 1/2
B 1/4
C 1/8
D 1/16
E 1/16
How do you know that your code has the shortest possible
average code length per symbol?
Hint: Use classification of binary codes
3 2 The generator polynomial of (7, 4) cyclic code is 5 Analyze 4
G(p)=P3+P+1, obtain all the code vectors for the code in non-
systematic form.
Hint: Use Cyclic code
4 2 For a linear block code parity check matrix 10 Evaluate 5
H= 1011100
1101010
0111001
a) Construct G
b) The code word that begins with 1010
c) If the received code word Y=0111100 then decode
the received code word.
Hint: Use linear block code
5 2 The generator polynomial of a (7, 4) cyclic code is G(p)= 10 Evaluate 5
p3+p2+p+1
a) Obtain the code vector for message (0011).
b) Obtain Generator matrix
c) Obtain the parity check matrix
Hint: Use Cyclic code
6 2 Evaluate the syndrome vector for single bit error for parity 10 Evaluate 5
check matrix given by
1110 100
0111 010
1101 001
Hint Use linear block code
7 2 Consider a discrete memory less source with alphabet {S0, 10 Evaluate 5
S1, S2) and statistics { 0.7, 0.15, 0.15} for its output.
a) Apply the Huffman algorithm to this source. Hence
show that the average code word length of the
Huffman code is 1.3bits/symbol.
b) Let the source be extended to order two. Apply the
Huffman algorithm to the resulting extended source,
and show that the average code word length of the
new code 1.1975bits/symbol.
c) Compare the average code word length calculated in
part (b) with the entropy of the original source.
Hint: Use Huffman code
8 2 Design a (6,2) Cyclic code by choosing the shortest possible 10 Evaluate 5
generator polynomial.
a) Determine the generator matrix G (in the systematic
form) for this code and find all possible code words.
b) How many errors can be corrected by this code?
Hint: Use Cyclic code
Module 3:
Convolutional Codes: Error Control Coding
Convolutional codes – code tree, trellis, state diagram – Encoding – Decoding: Sequential
search and Viterbi algorithm – Principle of Turbo coding.
Convolutional codes are used extensively to achieve reliable data transfer in numerous
applications, such as digital video, radio, mobile communications and satellite
communications.
To convolutional encode data, start with k memory registers, each holding one input bit.
Unless otherwise specified, all memory registers start with a value of 0. The encoder
has n modulo-2 adders (a modulo 2 adder can be implemented with a single Boolean
XOR gate, where the logic is: 0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 = 0), and n generator
polynomials — one for each adder (see figure below). An input bit m1 is fed into the
leftmost register. Using the generator polynomials and the existing values in the
remaining registers, the encoder outputs n symbols. These symbols may be transmitted
or punctured depending on the desired code rate. Now bit shift all register values to the
right (m1 moves to m0, m0 moves to m−1) and wait for the next input bit. If there are
no remaining input bits, the encoder continues shifting until all registers have returned
to the zero state (flush bit termination).
The figure below is a rate 1⁄3 (m⁄n) encoder with constraint length (k) of 3. Generator
polynomials are G1 = (1, 1, 1), G2 = (0, 1, 1), and G3 = (1, 0, 1). Therefore, output bits
are calculated (modulo 2) as follows:
n1 = m1 + m0 + m−1
n2 = m0 + m−1
n3 = m1 + m−1.
Module 3(Questions)
Q Module Question & Hint Marks BL
No.
1. 3 For the Convolutional encoder, the received bits are 01 00 01 10 Evaluate 5
00 10 11 11 00. Decode this sequence using Viterbi’s
algorithm and Trellis algorithm.
Hint: Use Convolutional encoder
2 3 A Convolutional code is described by g1= [1 0 1], g2= [1 0 10 Evaluate 5
1], g3= [1 1 1]
a) Draw encoder corresponding to this code
b) Draw state transition diagram for this code
c) Draw trellis diagram for this code
d) Find the transfer function and free distance of this
code.
3 3 Sketch the Convolutional encoders for the following codes 10 Create 6
a) Rate 1/ 2, K=5, maximum free distance code.
b) Rate 1/ 3, K=5, maximum free distance code.
c) Rate 2/ 3, K=2, maximum free distance code.
4 3 A Convolutional encoder has a single shift register with two 10 Create 6
stages, (i.e., constraint length K=3), three modulo-2 adders
and an output multiplexer. The generator sequences of the
encoder is as follows
g(1)= (1, 0, 1)
g(2)= (1, 1, 0)
g(3)= (1, 1, 0)
draw the block diagram of the encoder
Module 4
BCH Coding
What is BCH in coding?
Bose, Chaudhuri, and Hocquenghem
The Bose, Chaudhuri, and Hocquenghem (BCH) codes form a large class of powerful
random error-correcting cyclic codes. This class of codes is a remarkable generalization
of the Hamming code for multiple-error correction.
Module 4(Questions)
Module 4: BCH (Bose-Chaudhuri-Hocquenghem) codes: Algebraic
Description, Frequency Domain Description, Decoding Algorithms for BCH
and RS Codes.
Q No. Module Question & Hint Marks BL
1 4 Explain the mathematical principles 5 Evaluate 5
behind BCH coding and how they
are applied in error correction.
Provide a detailed comparison
between BCH coding and other error
correction techniques, highlighting
their strengths and weaknesses in
various practical applications.
Answer:
BCH(Bose-Chaudhuri
Hocquenghem) codes are a class of
cyclic error-correcting codes that are
widely used in telecommunications
and data storage systems. At their
core, BCH codes rely on finite field
arithmetic and polynomial algebra.
The primary mathematical
principles behind BCH coding
involve constructing generator
polynomials and syndrome
polynomials based on specific
mathematical properties of finite
fields.
In BCH coding, a generator
polynomial is selected to define the
code's properties, such as its error-
correction capability. This
polynomial is carefully chosen to
ensure that the code can correct a
certain number of errors within a
given block size. Syndrome
polynomials are then calculated to
detect and correct errors during
decoding. These polynomials are
derived from received code words
and the generator polynomial.
Compared to other error correction
techniques like Hamming codes or
Reed-Solomon codes, BCH coding
offers several advantages. One
significant advantage is its ability to
correct a wide range of error patterns
within a relatively small overhead,
making it highly efficient for
correcting burst errors common in
communication channels.
Additionally, BCH codes have
simpler decoding algorithms
compared to Reed-Solomon codes,
which leads to faster decoding times
in practical applications.
However, BCH coding also has its
limitations. One drawback is that it
requires a higher computational
complexity during encoding and
decoding compared to simpler codes
like Hamming codes. This increased
complexity can be a limiting factor
in real-time applications or systems
with limited computational
resources. Furthermore, BCH codes
may not be optimal for scenarios
with highly variable error rates or
asymmetric error patterns.
In summary, BCH coding leverages
advanced mathematical concepts
such as finite fields and polynomial
algebra to provide efficient error
correction capabilities. While it
offers advantages in correcting burst
errors with low overhead, it also
comes with computational
complexity challenges.
Understanding the trade-offs
between BCH coding and other error
correction techniques is essential for
selecting the most suitable approach
for specific practical applications.
2 4 A BCH code is defined by the 5 Evaluate 5
generator polynomial 𝑔 (𝑥)
=𝑥4+𝑥3+1. Determine the minimum
distance of this BCH code, and
calculate the maximum number of
errors it can correct assuming a
block size of 𝑛=15.
Answer:
To determine the minimum distance
of the BCH code defined by the
generator polynomial 𝑔 (𝑥)
=𝑥4+𝑥3+1, we need to find the roots
of the derivative of 𝑔 (𝑥). The
minimum distance of a BCH code is
equal to the number of consecutive
roots of the derivative of its
generator polynomial.
The derivative of 𝑔 (𝑥) is 𝑔′ (𝑥)
=4𝑥3+3𝑥2. Setting 𝑔′ (𝑥) equal to
zero and solving for 𝑥, we find the
roots:
4𝑥3+3𝑥2=0
𝑥2 (4𝑥+3) =0
This equation has two roots: 𝑥=0 and
𝑥=−3/4. Since 𝑥=0 is a repeated root,
we only count it once. Therefore, the
minimum distance of the BCH code
is 𝑑=4.
To calculate the maximum number
of errors the BCH code can correct,
we use the formula:
𝑡=⌊𝑑−1/2⌋
Where 𝑡 is the maximum number of
errors the code can correct and 𝑑 is
the minimum distance of the code.
Substituting 𝑑=4 into the formula:
𝑡=⌊4−1/2⌋=⌊3/2⌋=1
So, the BCH code with a block size
of 𝑛=15 can correct up to 𝑡=1error.
3 4 Find the code word polynomial C(x) 10 Evaluate 5
if the decoder input is V(x) =
x13+x12+x11+x5. Hence find the
message polynomial m(x).
Hint:
Text Book Name, Author, Publisher:
Principles of error correcting
code,[Link] & Kapil Gupta
Platinum Publishers
Chapter Number: 4
Exercise question number: 4(b)
4 4 For a (15, 5) triple-error correcting 10 Analyze 4
code, find the error syndromes over
GF(24) and determine the error
location polynomial for a given
message word m(x)= x4+x2+1 that
suffers an error e(x)=x5+x3+x.
Hint:
Text Book Name, Author, Publisher:
Principles of error correcting
code,[Link] & Kapil Gupta
Platinum Publishers
Chapter Number: 4
Exercise question number: 4.11
5 4 Let a double error correcting (15, 7) 10 Analyze 4
BCH code has the generating
polynomial g(x0= x8+x7+x6+x4+1.
For the message polynomial m(x)=
x5+ x3+ x2+1,the code word
polynomial is c(x)= x13+x12+x9+
x5+x4+x3+ x2+[Link] that the
received code word v(x)= x13+ x9+
x5+ x3+x2+1 incurred two errors
e(x)= x12+x4. Find c(x).
Hint:
Text Book Name, Author, Publisher:
Principles of error correcting
code,[Link] & Kapil Gupta
Platinum Publishers
Chapter Number: 4
Exercise question number: 4.9
Module 5
Cryptography
Symmetric Cryptosystems: Substitution permutation networks DES and Enhancements –
AES and its Modes. Asymmetric Key Cryptography: Basic Ideas of Asymmetric Key
Cryptography – RSA Cryptosystem.
Basic Concepts of Cryptography
• Cryptography is the science or art of secret writing.
• The fundamental objective of cryptography is to enable two people (Alice and Bob) to
communicate over an insecure channel in such a way that an opponent (Oscar) cannot
understand what is being said.
• Plaintext: the information that Alice wants to send to Bob.
• Alice encrypts the plaintext, using a predetermined key, and send the resulting ciphertext to
Bob over the public channel.
• Upon receiving the ciphertext – Oscar cannot determine what the plaintext was – But Bob
knows the encryption key, can decrypt the ciphertext and get the plaintext.
• Cryptology - two competing areas: – Cryptography - Art of converting information to
a form that will be unintelligible to an unintended recipient, carried out by
cryptographer. – Cryptanalysis - Art of breaking cryptographic systems, carried out by
cryptanalyst.
• Two main types of cryptography in use today: – Symmetric or secret key cryptography
– Asymmetric or public key cryptography
Module 5 (Questions)
Cryptography
Q Module Question & Hint Marks BL
No.
1. 5 Two prime numbers are given 10 Evaluate 5
as P = 17 and Q = 29. Evaluate
N, E and D in an RSA
encryption process.
Solution: Here P = 17 and Q =
29.
Hence, N = P × Q = 17 × 29 =
493.
Now we calculate ϕ(N) = (P −
1) (Q − 1) = 16 × 28 = 448.
We now select the public key
E such that E is relatively
prime to ϕ(N) = 448 and less
than ϕ(N).
The factors of 448 are 2, 2, 2,
2, 2, 2, and 7 (since E = 2 × 2
× 2 × 2 × 2 × 2 × 7).
Now we have to choose E such
that none of the factors of E is
2 and 7.
Let us choose E as 11 (it could
have been any other number
that does not have any of the
factors 2 and 7)
Now we determine the private
key D such that (D × E) mod
(448) = 1.
We have: (D × 11) mod (448)
= 1.
After making some
calculations, we find the
correct value is D = 285,
because (285 × 11) mod (448)
= 3135 mod (448) = 1.
2 5 Assume we perform a known- 5 Evaluate 5
plaintext attack against DES
with one pair of plaintext and
ciphertext. How many keys do
we have to test in a worst-case
scenario if we apply an
exhaustive key search in a
straightforward way? How
many on average?
Solution: Worst-Case: 256
keys.
Average: 256/2 = 255 keys.
3 5 Define the type of attack in 5 Analyze 4
each of the following cases:
a. A student breaks into a
professor’s office to obtain a
copy of the next test.
b. A student gives a check for
$10 to buy a used book. Later
the student finds out that the
check was cashed for $100.
c. A student sends hundreds of
e-mails per day to the school
using a phony return e-mail
address.
Hint: Analyze the security.
4 5 Alice can use only the additive 5 Evaluate 5
cipher on her computer to send
a message to a friend. She
thinks that the message is more
secure if she encrypts the
message two times, each time
with a different key. Is she
right? Defend your answer.
Hint: Apply concept of
additive cipher.
5 5 One of the attacks an intruder 5 Analyze 4
can apply to a simple cipher
like an additive cipher is called
the ciphertext attack. In this
type of attack, the intruder
intercepts the cipher and tries
to find the key and eventually
the plaintext. One of the
methods used in a cipher text
attack is called the brute-force
approach, in which the
intruder tries several keys and
decrypts the message until the
message makes sense. Assume
the intruder has intercepted the
cipher text
“UVACLYZLJBYL”. Try to
decrypt the message by using
keys beginning with 1 and
continuing until a plaintext
appears that makes sense.