Unit-5

Information Theory

5.1 Measure of information

 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:

5.2 Entropy

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 self-information 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 self-information = I total /L

=    log 1/Pi  bits/msg symbol.

Average self-information 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 self-information 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 1-p 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) + (1-P) 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,(1-Pk)]= H[(1-Pk),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=x-1 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 ≤ x-1

Multipling (-1) on both sides we get

-ln x ≥ 1-x or ln 1/x ≥ 1-x -------------------(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.

5.3 Mutual information

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 6-sided 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)

5.4 Mutual entropy

Mutual entropy is the entropy of a joint probability distribution, or a multi-valued 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

5.5 Source encoding (Shannon-Fano, Huffman)

Source emcoding is a process in which the output of an information source is converted into a r-ary 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 r-ary 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.

Shannon’s encoding algorithm

The following steps indicate the Shannon’s procedure for generating binary codes.

Step 1:

List the source symbols in the order of non-increasing 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 + Pq-1 +…………+ 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 :

Apply Shannon’s encoding (binary algorithm) to the following set of messages and obtain code efficiency and redundancy.

Step 1:

The symbols are arranged according to non-incraesing probabilities as below:

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 non-increasing order of probabilities

Consider the equation

q = r + (r-1 )

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.

Q. Given the messages X1,X2,X3,X4,X5 and X6 with respective probabilities of 0.4,0.2,0.2,0.1,0.07 and 0.03. Construct a binary code by applying Huffman encoding procedure . Determine the efficiency and redundancy of the code formed.

Now Huffmann code is listed below:

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%.

Shanon-Fano Coding Algorithm

Shanon-Fano Encoding procedure for getting a compact code with minimum redundancy is given below:

Q. Given are the messages X1,X2,X3,X4,X5,X6 with respective probabilities 0.4,0.2,0.2,0.1,0.07 and 0.03. Construct a binary code by applying Shannon-fano encoding procedure . Determine code effeciency and redundancy of the code.

 Applying Shannon-fano 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

5.6 Shannon’s channel capacity theorem

Fig. Discrete memory less channel

The channel capacity of a discrete memoryless channel is defined by:

Key Takeaways:

5.7 Introduction to error correction and detection

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 sphere-packing 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 error-correcting 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

5.8 Linear block codes

Encoding and syndrome decoding

In channel encoder a block of k-msg bits is encoded into a block of n bits by adding (n-k) 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 n-bit code word belonging to the same set of (n,k) block code.

A (n,k) linear block code is said to be systematic if k-msg bits appear either at the beginning or end of the code word.

Matrix Description of linear block codes:

Let the message block of k-bits 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(n-k) 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 n-k bits are check bits. Hence eq (2) and (3) can be combined into

[C] = {C1,C2,C3……………………..Ck, Ck+1,Ck+2 ……………………Cn}

These (n-k) number of check bits ck+1,Ck+2 ………………. Cn are derived from k-msg bits using predetermined rule below:

Ck+1 =P11d1 + P21 d2 +………………….+ Pk1dk

Ck+2 = P21 d1 + P22 d2 +………………….+ Pk2dk

……………………………………………………….

Ck+n = P1,n-kd1+ P2,n-k d2 +  ……………………+ Pk,n-kdk

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 ……….P1n-k]

0r [C] = [D] [G]

[G] = [Ik |P](kxn)

Where Ik is the unit matrix of order ‘k’

[P] = parity matrix of order kx (n-k)

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 (n-k) x  n matrix is called the parity check matrix.

Given by

[H] = [ PT | I n-k]

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 = R-C 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] = {Ik|P]= [I3|P]

1  0   0 | 1   0   1

0  1   0 |0    1    1

0  0   1|1     1     0

C = [d1    d2    d3]   1  0   0 | 1   0   1

0  1   0 |0    1    1

0  0   1|1     1     0

C= [d1,d2,d3,(d1+d3),(d2+d3),(d1+d2)]

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 (n-k) = 6-3 = 3.

Hence, we require 3-modulo 2 adders and 6 segment commutators.

Fig.: 3-modulo 2 adders and 6 segment commutators

For the (6,3) code matrix HT is given by

H T   =

H T = [P/In-k] = [P/I3]

S= [s1 s2 s3] = [ r1 r2 r3 r4 r5 r6]

[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 code-vector 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 n-k] = [ 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 =

G =

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.

The first row is the code C with zero vector in the first column

Every other row is coset

The n-tuple 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 =

H =

The standard array has 6 coset leaders of weight 1 and weight 2.

Standard array decoding

An (n,k) LBC over GF (Q) has M = Q k codewords.

Every n-tuple appears exactly once in the standard array. Therefore, the number of rows N satisfies

MN = Q n --- N = Q n-k

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 n-k 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

5.9 Cyclic codes (systematic, non-systematic)

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 n-k D(x) / g(x)

Let D = [ 1 1 0 1]          D(x) = 1 +x3

x n-k D(x) = x 7-4 (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

Encoding for cyclic codes

In order to obtain remainder polynomial R(x) we have to perform division of xn-k 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 + …………………..+ gn-k x n-k

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 modulo-2 adders and connection from the output of the gate to R0 and to the first modulo-2 adder.

Fig.: Modulo-2 adder

For the message D = [1 0 01] the shift register contents are

For the message D = [d0,d1,d2,d3] = [1 0 1 1] the shift register contents are shown below.

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 code-vector. 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 cod-vector 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 non-zero 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 n-k-1.

 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 (n-k) 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 co-efficient 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 modulo-2 adders.

Fig: Syndrome decoder with 3 flip flops

Syndrome calculator for (7, 4) cyclic code.

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 seven-single error patterns and their corresponding syndromes are as follows.

5.10 Convolution coding and decoding

Convolution codes

      Encoder contains memory

      At any given time, the n-outputs depend on the k-inputs 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 finite-state shift register.

The encoder of a binary convolutional code may be viewed as a finite state machine that consists of M-stage (k bits) shift registers with prescribed connections to n modulo-2 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 k-bit input sequence is n-bits.

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 M-stage 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 Ex-OR gate or modulo -2-adder

k= m + 1= 3 + 1 = 4

k= 1-bit message at a time. = 1-bit 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 3-bit 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 modulo-2 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.