Unit5
Information Theory
The meaning of the word “information” in Information Theory is the message or intelligence. The message may be an electrical message such as voltage , current or power or speech message or picture message such as facsimile or television or music message.
A source which produces these messages is called Information source.
Basics of Information System
Information system can be defined as the message that is generated from the information source and transmitted towards the receiver through transmission medium.
The block diagram of an information system can be drawn as shown in the figure.
Fig.1: Information system
Information sources can be classified into
Analog Information source such as microphone actuated by speech or a TV camera scanning a scene, emit one or more continuous amplitude electrical signals with respect to time.
Discrete Information source such as teletype or numerical output of computer consists of a sequence of discrete symbols or letters.
An analog information source can be transformed into discrete information source through the process of sampling and quantizing.
Key Takeaways:
Let us consider a zero memory space producing independent sequence of symbols with source alphabet
S = {S1,S2,S3………………Sq} with probabilities P = {P1,P2,P3……..Pq} respectively.
Let us consider a long independent sequence of length L symbols . This long sequence then contains
P1 L number of messages of type S1
P2L number of messages of type S2
……
……
PqL number of messages of type Sq.
We know that the self information of S1 = log 1/P1 bits.
Therefore
P1L number of messages of type S1 contain P1L log 1/P1 L bits of information.
P2L number of messages of type S2 contain P2L log 1/P2L bits of information.
Similarly PqL number of messages of type Sq contain PqL log 1/PqL bits of information.
The total selfinformation content of all these message symbols is given by
I total = P1L log 1/P1 + P2L log 1/P2 +……….+ PqL log 1/Pq bits.
I total = L log 1/Pi
Average selfinformation = I total /L
= log 1/Pi bits/msg symbol.
Average selfinformation is called ENTROPY of the source S denoted by H(s).
H(s)= log 1/Pi bits/message symbol.
Thus H(s) represents the average uncertainity or the average amount of surprise of the source.
Example
Let us consider a binary source with source alphabet S={S1,S2} with probabilities
P= {1/256, 255/256}
Entorpy H(s) = log 1/Pi
= 1/256 log 256 + 255/256 log 256/255
H(s) = 0.037 bits / msg symbol.
Example 2:
Let S = {S3,S4} with P’ = {7/16,9/16}
Then Entropy H(s’) = 7/16 log 16/7 + 9/16 log 16/9
H(s) = 0.989 bits/msg symbol.
Example 3:
Let S” = {S5,S6} with P” = {1/2,1/2}
Then Entropy H(S”) = ½ log2 2 + ½ log 2 2
H(S”) = 1 bits/msg symbol.
In this case the uncertainity is maximum for a binary source and becomes impossible to guess which symbol is transmitted.
Zero memory space:
It represents a model of discrete information source emitting a sequence of symbols from S= {S1,S2………………….. Sq} successive symbols are selected according to some fixed probability law and are statistically independent of one another. This means that there is no connection between any two symbols and that the source has no memory.Such type of source are memoryless or zero memory sources.
Information rate
Let us suppose that the symbols are emitted by the source at a fixed time rate “rs” symbols/sec. The average source information rate “Rs” in bits/sec is defined as the product of the average information content per symbol and the message symbol rate “rs”
Rs = rs H(s) bits/sec
Consider a source S={S1,S2,S3} with P={1/2,1/4,1/4}
Find
a) Self information
b) Entropy of source S
a) Self information of S1 = I1 = log 21/P1 = Log 2 2 = 1 bit
Self information of S2 = I2 = log 2 1/P2 = Log 2 4 = 2 bits
Self information of S3 = I3 = log 2 1/P3 = Log 2 4 = 2 bits
b) Average Information content or Entropy =
H(s) = Ii
= I1 P1 + I2 P2 + I3 P3
= ½(1) + ¼(2) + ¼ (2)
= 1.5 bits/msg symbol.
The collector volatge of a certain circuit lie between 5V and 12V.The voltage can take only these values 5,6,7,9,11,12 volts with the respective probabilities 1/6,1/3,1/12,1/12,1/6,1/6. This voltage is recorded with a pen recorder. Determine the average self information associated with the record in terms of bits/level.
Given Q = 6 levels. P= {1/6,1/3,1/12,1/12,1/6,1/6}
Average selfinformation H(s) = log 2 1/Pi
= 1/6 log 26 + 1/3 Log 23 + 1/12 log 2 12 + 1/12 log 2 12 + 1/6 Log 26 + 1/6 Log 26
H(s) = 2.418 bits/level
A binary source is emitting an independent sequence of 0s and 1s with probabilities p and 1p respectively. Plot entopy of source versus p.
The entropy of the binary source is given by
H(s) = log 1/Pi
= P1 log 1/P1 + P2 log 1/P2
= P log (1/P) + (1P) log 1/(1 P)
P=0.1 = 0.1 log(1/0.1) + 0.9 log(1/0.9)
= 0.469 bits/symbol.
At p=0.2
0.2 log(1/0.2) + 0.8 log(1/0.8)
= 0.722 bits/symbol.
At p=0.3
0.3 log(0.3) + 0.7 log(1/0.7)
= 0.881 bits/symbol.
At p=0.4
0.4 log(0.4) + 0.6 log(1/0.6)
= 0.971 bits/symbol.
At p=0.5
0.5 log(0.5) + 0.5 log(1/0.5)
= 1 bits/symbol.
At p=0.6
H(s) = 0.6 log (1/0.6) + 0.4 log(1/0.4)
H(s) = 0.971 biys/symbol
At p=0.7
0.7 log(1/0.7) + 0.3 log(1/0.3)
= 0.881 bits/symbol.
At p=0.8
0.8 log (1/0.8) +0.2 log(1/0.2)
0.722 bits/symbol
At p=0.9
0.9 log(1/0.9) + 0.1 log(1/0.1)
=0.469 bits /symbol.
Let X represent the outcome of a single roll of a fair die. What is the entropy of X?
Since a die has six faces , Probability of getting any number is 1/6.
Px = 1/6.
So entropy of X = H(X) = Px log 1/Px = 1/6 log 6 = 0.431 bits / msg symbol.
Find the entopy of the source in bits/symbol of the source that emits one out of four symbols A,B,C and D in a statistically independent sequences with probabilities ½,1/4,1/8 and 1/8 .
The entropy of the source is given by
H(s) = log 1/Pi
= Pa log 1/Pa + Pb log 1/Pb + Pc log 1/Pc + Pd log 1/Pd
= ½ log 2 2 + ¼ log 2 4 + 1/8 log 2 8 + 1/8 log 2 8
H(s) = 1.75 bits/msg symbol.
1 nat = 1.443 bits
1bit = 1/1.443 = 0.693 nats.
Entropy of the souce H(s) = 1.75 X 0.693 =
H(s) = 1.213 nats/symbol.
Properties
P = { P1,P2,P3………………….Pq} where q = no of source symbols as
H(s) = log (1/Pi) = bits/symbol.
The properties can be observed as :
The entropy function is continuous for every independent variable Pk in the interval (0,1) that is if Pk varies continuously from 0 to 1 , so does the entropy function.
The entropy function vanishes at both Pk = 0 and pk =1 that is H(s) = 0.
H[Pk,(1Pk)]= H[(1Pk),Pk]
The value of H(s) remains the same irrespective of the location of the probabilities.
If PA = { P1,P2,P3}
PB = { P2, P3,P1}
PC = { P3,P2,P1}
Then H(SA) = H(SB) = H(SC)
Let us consider the source with “q “ symbols S={S1,S2……… Sq} with probabilities P = {P1,P2,………Pq}.Then the entropy is given by
H(s) = log 1/Pi (1)
and we know that
P1 +P2 + P3 ……………. Pq = = 1
Let us now prove that
Log q – H(s) = ] log q  log (1/Pi) ](2)
= [ log q  log (1/Pi)](3)
= [ log qPi](4)
= [Log e q Pi] / [Log e 2 ](5)
Log q – H(s) = log 2 e ln qPi (6)
From the graph it is evident that the straight line y=x1 always lies above the logarithmic curve y = ln x except at x=1. Thus the straight line forms the tangent to the curve at x=1.
Therefor ln x ≤ x1
Multipling (1) on both sides we get
ln x ≥ 1x or ln 1/x ≥ 1x (7)
If X = 1/qp then ln qp ≥ 1 – 1/qp(8)
Multipling equation 2 both sides by Pi and taking summation we get for all i=1 to q we get
ln q Pi ≥ [ 1 – 1/qPi] (9)
Multiplying eq(3) by log 2 e we get
Log 2 e ln q Pi ≥ Log 2 e [ (10)
From equation (6 )
LHS of log q – H(s) and RHS of eq(6) is zero [ Since [ =0]
Therefore log q – H(s) = 0
Or H(s) ≤ log 2 q ; Suppose Pi 1/q =0 ; Pi = 1/q for all i=1,2,3………… q which satisfies then
H(s) max = log 2 q bits/msg symbol.
Mutual information is a quantity that measures a relationship between two random variables that are sampled simultaneously.
It measures how much information is communicated, on average, in one random variable about another.
For example, suppose X represents the roll of a fair 6sided die, and Y represents whether the roll is even (0 if even, 1 if odd). Clearly, the value of Y tells us something about the value of X and vice versa. That is, these variables share mutual information.
On the other hand, if X represents the roll of one fair die, and Z represents the roll of another fair die, then X and Z share no mutual information. The roll of one die does not contain any information about the outcome of the other die.
An important theorem from information theory says that the mutual information between two variables is 0 if and only if the two variables are statistically independent. The formal definition of the mutual information of two random variables X and Y , whose joint distribution is defined by
I(X;Y) = log P(x.y)/ P(x) P(y)
Mutual entropy is the entropy of a joint probability distribution, or a multivalued random variable. For example, one might wish to the know the joint entropy of a distribution of people defined by hair color C and eye color E, where C can take on 4 different values from a set C and E can take on 3 values from a set E.
If P(E, C) defines the joint probability distribution of hair color and eye color, then we write that their joint entropy is:
H(E, C) ≡ H(P(E, C)) = − ∑∑P(e, c) log P(e, c).
In other words, joint entropy is really no different than regular entropy. We merely have to compute Equation (1) over all possible pairs of the two random variables.
Example
Let X represent whether it is sunny or rainy in a particular town on a given day. Let Y represent whether it is above 70 degrees or below seventy degrees. Compute the entropy of the joint distribution P(X, Y ) given by
P(sunny, hot) = 0.5
P(sunny, cool) = 0.25
P(rainy, hot) = 0.25
P(rainy, cool) = 0
Solution:
Using the above equation
H(X, Y)= ( 0.5 log 0.5 + 0.25 log 0.25 +.25 log 0.25 +0)
= 1.5
Source emcoding is a process in which the output of an information source is converted into a rary sequence where r is the number of different symbols used in this transformation process . The functional block that performs this task in a communication system is called source encoder.
The input to the encoder is the symbol sequence emitted by the information source and the output of the encoder is rary sequence.
If r=2 then it is called the binary sequence
r=3 then it is called ternary sequence
r=4 then it is called quarternary sequence..
Let the source alphabet S consist of “q” number of source symbols given by S = {S1,S2…….Sq} . Let another alphabet X called the code alphabet consists of “r” number of coding symbols given by
X = {X1,X2………………………Xr}
The term coding can now be defined as the transformation of the source symbols into some sequence of symbols from code alphabet X.
The following steps indicate the Shannon’s procedure for generating binary codes.
Step 1:
List the source symbols in the order of nonincreasing probabilities
S = {S1,S2,S3……………………Sq} with P = {P1,P2,P3…………………..Pq}
P1 ≥P2 ≥P3 ≥………………….Pq
Step 2
Compute the sequences
= P1 +
= P2 + P1 = P2 +
P3+P2+P1 = P3 +
….. ……..
= Pq + Pq1 +…………+ P2 + P1 = Pq +
Step 3:
Determine the smallest integer value of “li using the inequality
2 li for all i=1,2,……………………q.
Step 4:
Expand the decimal number in binary form upto li places neglecting expansion beyond li places.
Step 5:
Remove the binary point to get the desired code.
Key Takeaways:
r=3 then it is called ternary sequence
r=4 then it is called quarternary sequence..
Example :
m 1  m 2  m 3  m 4  m 5 
1/8  1/16  3/16  ¼  3/8 
Step 1:
The symbols are arranged according to nonincraesing probabilities as below:
m 5  m 4  m 3  m 2  m 1 
3/8  ¼  3/16  1/16  1/8 
P 1  P 2  P 3  P 4  P 5 
The following sequences of are computed
= 0
P1 + = 3/8 + 0 = 0.375
= P2 + = ¼ + 0.375 = 0.625
= P3 + = 3/16 + 0.625 = 0.8125
= P4 + = 1/16 + 0.8125 = 0.9375
= P5 + = 1/8 + 0.9375 = 1
Step 3:
The smallest integer value of li is found by using
2 li ≥ 1/Pi
For i=1
2 l1 ≥ 1/P1
2 l1 ≥ 1/3/8 = 8/3 = 2.66
The samllest value ofl1 which satisfies the above inequality is 2 therefore l1 = 2.
For i=2 2 l2 ≥ 1/P2 Therefore 2 l2 ≥ 1/P2
2 l2 ≥ 4 therefore l2 = 2
For i =3 2 l3 ≥ 1/P3 Therefore 2 l3 ≥ 1/P3 2 l3 ≥ 1/ 3/16 = 16/3 l3 =3
For i=4 2 l4 ≥ 1/P4 Therefore 2 l4 ≥ 1/P4
2 l4 ≥ 8 Therefore l4 = 3
For i=5
2 l5 ≥ 1/P5 Therefore
2 l5 ≥ 16 Therefore l5=4
Step 4
The decimal numbers are expanded in binary form upto li places as given below.
= 0
0.375
0.375 x2 = 0.750 with carry 0
0.75 x 2 = 0.50 with carry 1
0.50 x 2 = 0.0 with carry 1
Therefore
(0.375) 10 = (0.11)2
= 0.625
0.625 X 2 = 0.25 with carry 1
0.25 X 2 = 0.5 with carry 0
0.5 x 2 = 0.0 with carry 1
(0.625) 10 = (0.101)2
= 0.8125
0.8125 x 2 = 0.625 with carry 1
0.625 x 2 = 0.25 with carry 1
0.25 x 2 = 0. 5 with carry 0
0.5 x 2 = 0.0 with carry 1
(0.8125) 10 = (0.1101)2
= 0.9375
0.9375 x 2 = 0.875 with carry 1
0.875 x 2 = 0.75 with carry 1
0.75 x 2 = 0.5 with carry 1
0.5 x 2 = 0.0 with carry 1
(0.9375) 10 = (0.1111)2
= 1
Step 5:
and l1 = 2 code for S1 00
=(0.011) 2 and l2 =2 code for S2  01
= (.101)2 and l3 =3 code for S3  101
= (.1101)2 and l4 =3 code for S  110
= (0.1111)2 and l5 = 4 code for s5  1111
The average length is computed by using
L =
= 3/8 x 2 + ¼ x 2 + 3/16 x 3 + 1/8 x 3 + 1/16 x 4
L= 2.4375 bits/msg symbol
The entropy is given by
H(s) = 3/8 log (8/3) + ¼ log 4 + 3/16 log 16/3 + 1/8 log 8 + 1/16 log 16
H(s) =2.1085 bits/msg symbol.
Code efficiency is given by
ηc = H(s)/L = 2.1085/2.4375 = 0.865
Percentage code effeciency = 86.5%
Code redundancy
R ηc = 1  ηc = 0.135 or 13.5%.
Huffmann Coding
First the source symbols are listed in the nonincreasing order of probabilities
Consider the equation
q = r + (r1 )
where q = number of source symbols
r = no of different symbols used in the code alphabet
The quantity is calculated and it should be an integer . If it is not then dummy symbols with zero probabilities are added to q to make the quantity ) an integer. To explain this procedure consider some examples.
Now Huffmann code is listed below:
Source Symbols  Pi  Code  Length (li) 
X1  0.4  1  1 
X2  0.2  01  2 
X3  0.2  000  3 
X4  0.1  0010  4 
X5  0.07  00110  5 
X6  0.03  00111  5 
Now Average length (L) = li
L = 0.4 x 1 + 0.2 x 2 + 0.2 x 3 + 0.1 x 4 + 0.07x 5 + 0.03 x 5
L = 2.3 bits/msg symbol.
Entropy H(s) = = log 1/Pi
0.4 log 1/0.4 + 0.2 log 1/0.2 + 0.1 log 1/0.1 + 0.07 log 1/0.07 + 0.03 log 1/0.03
H(s) = 2.209 bits /msg symbol.
Code effeciency = ηc = H(s) /L = 2.209/2.3 = 96.04%.
ShanonFano Coding Algorithm
ShanonFano Encoding procedure for getting a compact code with minimum redundancy is given below:
Applying Shannonfano encoding procedure
Average length L is given by
L =
= 0.4 x 1 + 0.2 x 3 + 0.2 x 3 + 0.1 x 3 + 0.07 x4 + 0.03 X 4
L = 2.3 bits/msg symbol.
Entropy
H(s) = log 1/Pi
0.4 log 1/0.4 + 2x 0.2 log 1/0.2 + 0.1 log 1/0.1 + 0.07 log 1/0.07 + 0.03 log 1/0.03
H(s) = 2.209 bits/msg symbol.
Code Efficiency = ηc = H(s) / L = 2.209/2.03 = 96.04%
Code Redundancy = R ηc = 1 ηc = 3.96%
You are given four messages X1 , X2 , X3 and X4 with respective probabilities 0.1,0.2,0.3,0.4
Average length L = li
= 0.4 x1 + 0.3 x 2 + 0.2 x 3 + 0.1 x3
L = 1.9 bits/symbol.
Entropy H(s) = log 1/Pi
= 0.4 log 1/0.4 + 0.3 log 1/0.3 + 0.2 log 1/0.2 + 0.1 log 1/0.1
H(s) = 1.846 bits/msg symbol.
Code efficiency ηc = H(s) / L = 1.846/1.9 = 97.15%
Code Redundancy = R ηc = 1 ηc = 2.85%
The code tree can be drawn
The probabilities of 0’s and 1’s in the code are found by using the
P(0)= 1/L no of 0’s in code xi) (Pi)
= 1/1.9 [ 3 x 0.1 + 2x 0.2 + 1x 0.3 + 0(0.4)]
P(0) = 0.5623
P(1) = 1/L no of 1’s in code xi) (Pi)
= 1/1.9 [ 0x0.1+1x0.2+1x0.+1x0.4]
P(1) = 0.4737
Fig. Discrete memory less channel
The channel capacity of a discrete memoryless channel is defined by:
Key Takeaways:
Hamming sphere
The Hamming sphere of radius ϵ centered on a vertex of the unit cube in Rn is the set of all vertices at a Hamming distance of at most ϵ from the given vertex.
A code of length is said to be perfect (or close packed or lossless) if there is an ϵ>0 such that:
The ϵ spheres centered on the codeword vertices are pairwise disjoint.
Each vertex of the n cube is contained in some ϵ sphere.
Hamming distance and Hamming bound
The Hamming weight w(c) of a code vector c is defined as the nonzero elements in the code vector. Consider a pair of code vector cl and c2 that have the same number of elements. The Hamming distance d(cl, c2) between them is defined as the number of positions in which their corresponding elements differ. The minimum distance of a linear block code is the smallest Hamming weight of the nonzero code vectors in the code. The Hamming distance t is the minimum number of bit positions by which code words for a particular code are different.
The Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the spherepacking bound or the volume bound from an interpretation in terms of packing balls in the Hamming metric into the space of all possible words. It gives an important limitation on the efficiency with which any errorcorrecting code can utilize the space in which its code words are embedded. A code that attains the Hamming bound is said to be a perfect code.
Relation between minimum distance and error detecting and correcting capability
Fig.: Hamming sphere, Hamming distance
Assume the 2'" code vectors were transmitted with equal probability, the decoder will choose the code vector which has the minimum Hamming distance to the received rcode vector as the final output, that is, if
the decoder will consider code vector ci, not cj, was transmitted. According to this strategy, if the code's minimum distance is equal to or greater than 2t+ 1, the decoder can detect and correct the error pattern with Hamming weight w(e) < t.
Thus, we can conclude that an (n, k) liner block code is able to correct all the error patterns with weight less than or equal to t if and only if
Encoding and syndrome decoding
In channel encoder a block of kmsg bits is encoded into a block of n bits by adding (nk) number of check bits as shown in figure.
Fig.: Channel encoder
A (n,k) block code is said to be a (n,k) linear block code if it satisfies the condition
Let C1 and C2 be any two code words belonging to a set of (n,k) block code
Then C1 C2 is also an nbit code word belonging to the same set of (n,k) block code.
A (n,k) linear block code is said to be systematic if kmsg bits appear either at the beginning or end of the code word.
Matrix Description of linear block codes:
Let the message block of kbits be represented as row vector called as message vector given by
[D] = {d1,d2………………dk}
Where d1,d2………………dk are either 0’s 0r 1’s
The channel encoder systematically adds(nk) number of check bits toform a (n,k) linear block code. Then the 2k code vector can be represented by
C = {c1,c2……………cn) (2)
In a systematic linear block code, the msg bits appear at the beginning of the code vector
Therefore ci=di for all I = 1 to k.(3)
The remaining nk bits are check bits. Hence eq (2) and (3) can be combined into
[C] = {C1,C2,C3……………………..Ck, Ck+1,Ck+2 ……………………Cn}
These (nk) number of check bits ck+1,Ck+2 ………………. Cn are derived from kmsg bits using predetermined rule below:
Ck+1 =P11d1 + P21 d2 +………………….+ Pk1dk
Ck+2 = P21 d1 + P22 d2 +………………….+ Pk2dk
……………………………………………………….
Ck+n = P1,nkd1+ P2,nk d2 + ……………………+ Pk,nkdk
where P11,P21 …………. Are either 0’s or 1’s addition is performed using modulo 2 arithmetic
In matrix form
[c1 c2………….cn] = [d1,d2…………………dn] [ 1 0 0 0 P11 P12 ……….P1nk]
0r [C] = [D] [G]
[G] = [Ik P](kxn)
Where Ik is the unit matrix of order ‘k’
[P] = parity matrix of order kx (nk)
I = denotes demarkation between Ik and P
The generator matrix can be expressed as
[G] = [P  Ik]
Associated with the generator matrix [G] another matrix order (nk) x n matrix is called the parity check matrix.
Given by
[H] = [ PT  I nk]
Where PT represents parity transpose matrix
Syndrome and error correction
Let us suppose that C=(C1,C2………………Cn) be a valid vector transmitted over a noisy communication channel belonging to a (n,k) linear block code.
Let R = {r1,r2,……………………. Rn} be the received vector. Due to noise in the channel vector r1,r2……………..rn may be different from c1,c2……………………….cn . The error vector or error pattern E is defined as the distance between R and C
E = RC or E = R+C
Example
For a systematic (6,3) linear block code the parity matrix P is given by
P =
R = [r1 r2 r3 r4 r5 r6]
Given n=6 and k=3 for (6, 3) block code
Since k=3 there are 23 = 8 message vectors given by
(000),(001),(010),(011),(100),(101),(110),(111)
The code vector is found by
[C]= [D][G]
[G] = {IkP]= [I3P]
1 0 0  1 0 1
0 1 0 0 1 1
0 0 11 1 0
C = [d1 d2 d3] 1 0 0  1 0 1
0 1 0 0 1 1
0 0 11 1 0
C= [d1,d2,d3,(d1+d3),(d2+d3),(d1+d2)]
Code name  Msg Vector  Code Vector For (6,3) liner block code 
 d 1 d 2 d3  d 1 d 2 d 3 d 1+d 3 d2 + d3 d1 + d2 
Ca  0 0 0  0 0 0 0 0 0 
Cb  0 0 1  0 0 1 1 1 0 
Cc  0 1 0  0 1 0 0 1 1 
Cd  0 1 1  0 1 1 1 0 1 
Ce  1 0 0  1 0 0 1 0 1 
Cf  1 0 1  1 0 1 0 1 1 
Cg  1 1 0  1 1 0 1 1 0 
Ch  1 1 1  1 1 1 0 0 0 
The code vector is given by
c 1 = d1, c2 = d2, c3 = d3 c4 = d1 + d3 c5 = d2 + d3 c6 = d1 + d2
Since k=3 we require 3bit shift registers to move the message bits into it.
We have (nk) = 63 = 3.
Hence, we require 3modulo 2 adders and 6 segment commutators.
Fig.: 3modulo 2 adders and 6 segment commutators
For the (6,3) code matrix HT is given by
H T =
1  0  1 
0  1  1 
1  1  0 
1  0  0 
0  1  0 
0  0  1 
H T = [P/Ink] = [P/I3]
S= [s1 s2 s3] = [ r1 r2 r3 r4 r5 r6]
1  0  1 
0  1  1 
1  1  0 
1  0  0 
0  1  0 
0  0  1 
[S] = [S1 s2 s3] = (r1+r3+r4), (r2+r3+r5),(r1+r2+r6)
S1 = r1+r3+r4
S2 = r2+r3+r5
S3 = r1 +r2 +r6
Fig.: Syndrome calculation circuit
Error Detection and correction capability
For a systematic (6,3) linear block code the parity matrix P is given by
P = 1 0 1
0 1 1
1 1 0
For the recorded codevector R= [1 1 0 0 1 0] Detect and correct the single error that has occurred due to noise.
Given
P = 1 0 1
0 1 1
1 1 0
P T = 1 0 1
0 1 1
1 1 0
Parity check matrix [H] = [P T  I nk] = [ PT  I3]
1 0 1 1 0 0
0 1 1 0 1 0
1 1 0 0 0 1
H T = 1 0 1
0 1 1
1 1 0
1 0 0
0 1 0
0 0 1
S = [s1 s2 s3] = R HT= [ 11 00 10]1 0 1
0 1 1
1 1 0
1 0 0
0 1 0
0 0 1
[S]= [100] since s≠0 it represents error. Since [100] present in the 4th row of HT. So the error vector [E] = [0 0 0 1 0 0] the corrected vector is given by
C = R + E = [11 00 10][000100]
C = [110110] which is the valid code
Standard array and syndrome decoding
Syndrome decoding
An (8,4) binary linear block code is defined by systematic matrices
H =
1  0  0  0  0  1  1  1 
0  1  0  0  1  0  1  1 
0  0  1  0  1  1  0  1 
0  0  0  1  1  1  1  0 
G =
0  1  1  1  1  0  0  0 
1  0  1  1  0  1  0  0 
1  1  0  1  0  0  1  0 
1  1  1  0  0  0  0  1 
Consider two possible messages m1 = [0 1 1 0]
C1 = [0 1 1 0 0 1 10]
m2 = [1 0 1 1]
c2 = [01001011]
Suppose the error pattern e = [00000100] is added to both codewords
r1 = [01100010]
s1 = [1011]
r2 = [01001111]
s2 = [1011]
Both syndromes equal column 6 of H so decoder correct bit 6.
Standard array
Syndrome table decoding can also be described using the standard array. The standard array of a group code C is the coset decomposition of Fth with respect to the subgroup C.
0  c 2  c 3  ……  c M 
e 2  c 2 + e 2  c 3 + e 2 
 c M + e2 
e 3  c 2 + e3  c 3 + e 3 
 cM + e3 
……. 




e N  c 2 + eN  c 3 + eN 
 c M + e N 
The first row is the code C with zero vector in the first column
Every other row is coset
The ntuple in the first column is called the coset leader
We usually choose the coset leader o be the most plausible error pattern example the error pattern of smallest weight.
Example
G =
0  1  1  1  0  0 
1  0  1  0  1  0 
1  1  0  0  0  1 
H =
1  0  0  0  1  1 
0  1  0  1  0  1 
0  0  1  1  1  0 
The standard array has 6 coset leaders of weight 1 and weight 2.
000000  001110  010101  011011  100011  101101  110110  111000 
000001  001111  010100  011010  100010  101100  110111  111001 
000010  001100  010111  111001  100001  101111  110100  111010 
000100  001010  010001  011111  100111  101001  110010  111011 
001000  000110  011101  010011  101011  100101  111110  110000 
010000  011110  000101  001011  110011  111101  100110  101000 
100000  101110  110101  111011  000011  001101  010110  011000 
001001  000111  011100  010010  101010  100100  111111  110001 
Standard array decoding
An (n,k) LBC over GF (Q) has M = Q k codewords.
Every ntuple appears exactly once in the standard array. Therefore, the number of rows N satisfies
MN = Q n  N = Q nk
All vectors in a row of the standard array have the same syndrome.
Thus, there is one to one correspondence between the rows of the standard array and Q nk syndrome values.
Decoding using the standard array is simple
Decode the sense word r to the codeword at the top of the column that contains r.
The decoder subtracts the coset leader from the received vector to obtain estimated codeword.
The decoded region for codeword is the column headed by that codeword.
Fig.: Codeword
Encoder and decoder for systematic cyclic codes
In systematic form the first three bits are check bits and the last 4 bits are message bits. The check bits are obtained by from the remainder polynomial R(x)
R(x) = x nk D(x) / g(x)
Let D = [ 1 1 0 1] D(x) = 1 +x3
x nk D(x) = x 74 (1 + x3) = x3 + x6
R(x) = x3 + x6 / x3 + x + 1
R(x) = x + x2
R = [0 1 1]
The code vector V is given by [0 1 1 1 0 0 1]
The other systematic code vector can be formed by
Message  Code Vector 
0000  0000000 
0001  1010001 
0010  1110010 
0011  0100011 
0100  0110100 
0101  1100101 
0110  1000110 
0111  0010111 
1000  1101000 
1001  0111001 
1010  0011010 
1011  1001011 
1100  1011100 
1101  0001101 
1110  0101110 
1111  1111111 
Encoding for cyclic codes
In order to obtain remainder polynomial R(x) we have to perform division of xnk D(x) by the generator polynomial g(x). This division can be accomplished using the dividing circuit consisting of feedback shift register as shown in the figure.
Fig.: Feedback shift register
Symbols Used
Operation:
Design an encoder for the (7,4) binary cyclic code generated by
g(x) = g0 + g1 + g2 x2 + …………………..+ gnk x nk
Here for (7,4) cyclic code given
g(x) = 1 + x + x3
Comparing (1) and (2) we get
g 0 =1, g1 =1, g2 = 0, g3 = 1
With these values the design requires 3 flipflops R0,R1,R2, the two modulo2 adders and connection from the output of the gate to R0 and to the first modulo2 adder.
Fig.: Modulo2 adder
For the message D = [1 0 01] the shift register contents are
No of shifts  Input D  Shift Register Contents  Remainder bits R 
Initialization; Switch S is in position 1 and gate is turned ON 
 0 0 0   
1  1  1 1 0   
2  0  01 1   
3  0  111   
4  1  011   
Switch moves to position 2 and gate is turned OFF 



5  X  0 0 1  1 
6  X  0 0 0  1 
7  X  0 0 0  0 
For the message D = [d0,d1,d2,d3] = [1 0 1 1] the shift register contents are shown below.
No of shifts  Input (D)  Shift Register Contents  Remainder bits 
Gate is turned ON 
 0 0 0 

1  1  1 1 0 

2  1  1 0 1 

3  0  1 0 0 

4  1 


Gate is turned OFF 



5  X  0 1 0  0 
6  X  0 0 1  0 
7  X  0 0 0  1 
Syndrome calculation of cyclic codes
Let us suppose that the code vector ‘V’ is transmitted over a noisy communication channel. The received vector ‘Z’ may or may not be the transmitted codevector. Ion of the decoder is to determine the transmitted code vector based on the received vector.
The decoder first tests whether or not the received vector is a valid codvector by calculating the syndrome of the received vector.
If the syndrome is zero then the received vector polynomial is divisible by the generator polynomial and the received vector is a valid code vector. The decoder accepts the received vector Z(x) as the transmitted code vector.
A nonzero syndrome vector indicates that transmission errors have occurred, the syndrome S(x) of the received vector Z(x) is the remainder resulting from dividing z(x) by g(x)
z(x)/g(x) = Q(x) +s(x)/g(x)
where Q(x) is the quotient polynomial. The syndrome S(x) is a polynomial of degree nk1.
If E(x) is the error pattern caused by the channel
E(x) = g(x) [Q(x) + D(x) ] + S(x)
Fig.: Syndrome output
A (nk) syndrome calculation circuit for (n,k) cyclic code
The syndrome calculation is carried out as below:
The register is first initialized with gate2 turned on and gate1 OFF. The received vector Z is entered into the shift register.
After the entire received vector is shifted into the shift register the contents of the register will be syndrome. Now gate2 is turned OFF and gate1 ON and the syndrome vector is shifted out of the register. The circuit is ready for processing the next received vector.
Cyclic codes are extremely suitable for error detection.
Fig.: Syndrome decoder
The decoder operates on the received vector digit by digit until the entire received vector is shifted out of the buffer.
At the end of the decoding operation errors will have to corrected if they correspond to n error pattern built into the detector and the syndrome register will contain all 0’s then an uncorrectable error pattern has been detected.
Example:
For a (7,4) cyclic code received vector Z(x) = 1110101 and the generator polynomial g(x) = 1+x+x3. Draw the syndrome calculation circuit and correct the single error in the received vector.
The generator polynomial is given by
1+x+x3 (1)
Now comparing eq(1) with
g(x) = g0+g1+g2 x2 + g3 x3
The coefficient g0=1,g1=1,g2=0,g3=1.
With these values the circuit requires only 3 flip flops (s0,s1,s2) representing the syndrome bits two modulo2 adders.
Fig: Syndrome decoder with 3 flip flops
Syndrome calculator for (7, 4) cyclic code.
Number of shifts  Input Z(x)  Shift register contents  Comments 
Initialization gate1oFF and gate2 ON 
 000  Shift register contents are cleared 
1  1  100 

2  0  010 

3  1  101 

4  0  100 

5  1  110 

6  1  111 

7  1  001  Indicates error 
8  0  110 

9  0  011 

10  0  111 

11  0  101 

12  0  100  Endof shifting operation 
The received vector is 1110101
Since we got 100 at the 12th shift the th bit counting from right is in error.
Error vector E =0010000
Corrected vector V = Z + E = 1110101 + 0010000
V = 1100101
Circuit Implementation of cyclic code
Fig.: Circuit Implementation of cyclic code
Consider the decoding of (7,4) cyclic code generated by g(x) = 1+x+x3 . This code has minimum distance 3 and is capable of correcting any single error. The sevensingle error patterns and their corresponding syndromes are as follows.
Convolution codes
Encoder contains memory
At any given time, the noutputs depend on the kinputs at that time and m previous input blocks.
Convolution coding is an alternative to block coding of digital messages. It can offer higher coding gain.
It generates by parsing the information sequence to be transmitted through linear finitestate shift register.
The encoder of a binary convolutional code may be viewed as a finite state machine that consists of Mstage (k bits) shift registers with prescribed connections to n modulo2 adders and a multiplier that serialized the outputs of the address.
If L = length of input message sequence (in bits) then coded output length C = n(L+M) bits.
Fig.: Convolution Coder
The input data to the encoder which is assumed binary is shifted into and along the shift register k bits at a time. The number of output bits for each kbit input sequence is nbits.
Code rate is given as Rc = k / n. The parameter k is called the constraint length(k) of convolution code. It is defined as the number of shifts over which a single message bit can influence the encoder output.
In an encoder with Mstage shift register the memory of the encoder equls M message bits and k = m+1 shifts which are required for message bits to enter the shift registers and pop out.
Hence, the constraint length of the encoder is k =m + 1 bits.
Consider a binary convolutional encoder with constraint length k=1 and n=3 as shown in the figure with rate 1/3.
Here m =3 = no of shift register stages.
n= 3 no of ExOR gate or modulo 2adder
k= m + 1= 3 + 1 = 4
k= 1bit message at a time. = 1bit shift register.
Code rate = Rc = k/n = 1/3
Fig.: Binary convolutional encoder
Suppose the number of outputs of the function generator polynomial that generate each 3bit output sequence as 1,2 and 3. Similarly, the number each corresponding function generator.
Since at the first stage (m1) is connected to the first generator function polynomial the generator is
g 1 = [1 0 0]
g1(x) = 1.
The second generator is connected to stage 1 (m1) and stage 3(m3)
g 2 = [1 0 1]
g2 = 1 + x 2
g3 = [1 1 1]
Generator for this code = [ 100, 101, 111]
The output of modulo2 adders are C1,C2 and C3
C1 = m(x) g1(x)
C2 = m(x) g2(x)
C3 = m(x) g3(x)
The codeword for convolutional encoder is
C = [ c1 c2 c3]
Fig.: Convolutional encoder
Here n = 3, m = 4, Length of data = 5
C = n(L+m) = 3(5+4) = 27 bits
Constraint length k = m + 1 = 5
The coded output c1,c2,c3 are
We assume that initially the shift register is clear. During the first shift
M1 = 1 M2 = M3=M4 = 0
C1 = s1 = 1
The coded output for tbis message bit is 111
C = 111 010 100 110 001 000 011 000 000
Advantages:
1.The decoding delay is small in convolutional codes since they operate o smaller blocks of data.
2. The storage hardware required by convolutional decoder is less since the block sizes are smaller.
Disadvantages:
1. Convolutional codes are difficult to analyze since their analysis is complex.
2. Convolutional codes are not developed much as compared to block codes.
References:
1. B.P. Lathi, “Modern Digital and Analog communication Systems”, 4th Edition, Oxford University Press, 2010.
2. Rishabh Anand, Communication Systems, Khanna Publishing House, Delhi.