It Reference
It Reference
Source Coding
Not everything that can be counted counts, and not everything that counts can be counted.
Albert Einstein (1879-1955)
learning objectives
LO 5 & ' (
areas of source coding.
captured and uploaded on social media sites with just a click of a button.
12 ° Information Theory, Coding and Cryptography
!
world it is the " # $ % &
(the omnipresent bits) that hold the information by the mere way they sit next to one another.
' %*+/
Information Theory—a theory that was initiated by one man, the
American Electrical Engineer Claude E. Shannon, whose ideas appeared in the article “The Mathematical
Theory of Communication” in the Bell System Technical Journal %*+/" !
interpreted to include the messages occurring in any of the standard communications media, such as telephone,
radio, or television, and the signals involved in electronic computers, electromechanical systems, and other
data-processing devices. The theory is even applicable to the signals appearing in the nerve networks of
humans and other animals.
The chief concern of information theory is to discover mathematical laws governing systems designed to
communicate or manipulate information. It sets up quantitative measures of information and of the capacity
of various systems to transmit, store, and otherwise process information. Some of the problems treated are
0 0
for separating the wanted information, or signal, from the extraneous information, or noise. Another problem
is the setting of upper bounds on what it is possible to achieve with a given information-carrying medium
" 1 2 !
0 3
!
DNA regions (genotypes) responsible for particular traits (phenotypes).
The boundaries of information theory are quite fuzzy. The theory overlaps heavily with
communication theory but is more oriented toward the fundamental limitations on the
processing and communication of information and less oriented toward the detailed operation
of the devices employed.
In this chapter
We will start with an intuitive understanding of information and link uncertainty to information.
) ' ( ( ( ( * + (
( #, 1.
- / ' & / (
0 / ) ' ( / #, 2.
) '
! " # $ % #
#, 3.
- / ' ' ( ( (
) ' ' ( ) '
1 & #, +
! ' ' 0 ( ' & '
( ( 2
34"5 ' 0 #, 5.
Source Coding ° 13
3 !
any information. It is a sure-shot thing. Everybody knows that the sun rises from the East and the
probability of this happening again is almost unity (“Making predictions is risky, especially when it
involves the future.” - N. Bohr). Sentence (B) appears to carry more information than sentence (A).
3 ! 3 $
(unless the maintenance people are at work again). The last sentence probably made you read it over twice.
This is because it has never snowed in Delhi, and the probability of a snowfall is very low. It is interesting to
note that the amount of information carried by the sentences listed above have something to do with the
probability of occurrence of the events stated in the sentences. And we observe an inverse relationship.
Sentence (A), which talks about an event which has a probability of occurrence very close to 1 carries almost
no information. Sentence (C), which has a very low probability of occurrence, appears to carry a lot of
information (made us read it twice to be sure we got the information right!). The other interesting thing to
note is that the length of the sentence has nothing to do with the amount of information it conveys. In fact,
sentence (A) is the longest of the three sentences but carries the minimum information.
We will now develop a mathematical measure of information.
Ê 1 ˆ
I (xi) = log Á = – log P (xi) (1.1)
Ë P ( xi ) ˜¯
We note that a high probability event conveys less information than a low probability event. For an event
with P (xi) = 1, I (xi" 9 & vice versa), a
random variable with a higher degree of uncertainty contains more information. We will use this correlation
between uncertainty and information for physical interpretations throughout this chapter.
14 ° Information Theory, Coding and Cryptography
The units of I(xi) are determined by the base of the logarithm, which is usually selected as 2 or e.
When the base is 2, the units are in bits and when the base is e, the units are in nats (natural
" & £ P(xi) £ 1, I(xi) ≥ &! i.e., self-information is non-negative. The following two
examples illustrate why a logarithmic measure of information is appropriate.
Example 1.1 Consider a binary source which tosses a fair coin and produces an output equal to
% & ; ! P(1) = P &" 9 & < 3
of each output from the source is
I (xi) = – log2 P (xi) = – log2 & <" 9 % % >"
Indeed, we have to use only one bit to represent the output from this binary source (say, we use a 1
? & 3" @ ! 0
statistically independent, i.e., the source is memoryless. Consider a block of m binary digits. There are
2m possible m-bit blocks, each of which is equally probable with probability 2 –m. The self information
of an m-bit block is
I(xi) = – log2P(xi) = – log22 –m = m bits (1.3)
Again, we observe that we indeed need m bits to represent the possible m-bit blocks. Thus, this
logarithmic measure of information possesses the desired additive property when a number of source
outputs are considered as a block.
Example 1.2 Consider a discrete, memoryless source (source C) that generates two bits at a
time. This source comprises two binary sources (sources A and B) as mentioned in Example 1.1, each
source contributing one bit. The two binary sources within the source C are independent. Intuitively, the
information content of the aggregate source (source C) should be the sum of the information contained
in the outputs of the two independent sources that constitute this source C. Let us look at the infor-
mation content of the outputs of source C 3 G&&! &%! %&! %%H!
a probability P(C) = P(A)P(B" 9 & <" & <" 9 & ><! A and B are independent. The
information content of each output from the source C is
I(C) = – log2 P(xi)
= – log2 & ><" 9 > % +"
We have to use two bits to represent the output from this combined binary source. Thus, the logarithmic
measure of information possesses the desired additive property for independent events.
Next, consider two discrete random variables X and Y with possible outcomes xi, i = 1, 2, …, n. and yj,
j = 1, 2, …, m respectively. Suppose we observe some outcome Y = yj and we want to determine the amount
of information this event provides about the event X = xi, i = 1, 2, …, n, i.e., we want to mathematically
represent the mutual information. We note the two extreme cases:
(i) X and Y are independent, in which case the occurrence of Y = yj provides no information about
X = xi.
(ii) X and Y are fully dependent events, in which case the occurrence of Y = yj determines the
occurrence of the event X = xi.
#
P (X = xi | Y = yj) = P(xi | yj) (1.5)
divided by the probability P(X = xi) = P(xi). (1.6)
Source Coding ° 15
Ê P (xi | y j ) ˆ Ê P ( y j | xi ) ˆ
Therefore, I(xi ; yj) = log Á ˜ = log Á ˜ = I (yj ; xi" % *"
Ë P (xi ) ¯ Ë P( yj ) ¯
Example 1.3 Consider a binary symmetric channel (BSC) as shown in Fig. 1.1. A binary channel
0 Q % & 1–p
0 p 0
from the transmitter (Tx) to the receiver (Rx). It
makes an error occasionally, with probability p.
Tx Rx
#U X 2 % & vice-versa with
equal probability. Let X and Y be binary random
variables that represent the input and output of 1–p p
1 1
this BSC. Let the input symbols be equally likely, Channel
and the output symbols depend upon the input
Fig. 1.1 A binary symmetric channel.
according to the channel transition probabilities
are as follows:
P (Y 9 & Y X 9 &" 9 % Z p.
P (Y 9 & Y X = 1) = p.
P (Y = 1 | X = 1) = 1 – p.
P (Y = 1 | X 9 &" 9 p.
2 " 0 U X
is p. From the channel transition probabilities we have
16 ° Information Theory, Coding and Cryptography
This implies that having observed the output, we have no information about what was
transmitted. Thus, it is a useless channel. For such a channel, there is no point in observing
the received symbol and trying to make a guess as to what was sent. Instead, we can also
toss a fair coin at the receiver in order to estimate what was sent!
Suppose we have a channel where p 9 & % ; !
I(x&; y&) = I &\ &" 9 22(1 – p) = log2> & *" 9 & /+/
Example 1.4 Let X and Y be binary random variables that represent the input and output of
a binary channel shown in Fig. 1.2. Can you think 1 – p0
0 p1 0
of a real-life channel that has unequal crossover
% &_]
be equally likely, and the output symbols depend Tx Rx
upon the input according to the channel transition
probabilities: p
1 – p1 0
1 1
P(Y 9 & Y X 9 &" 9 % Z p& Channel
P(Y 9 & Y X = 1) = p1.
Fig. 1.2 A binary channel with asymmetric
P(Y = 1 | X = 1) = 1 – p1. probabilities.
P(Y = 1 | X 9 &" 9 p&
From the channel transition probabilities we have
P(Y 9 &" 9 P(X 9 &".P(Y 9 & Y X 9 &" [ P(X = 1).P(Y 9 & Y X = 1)
9 & < % Z p&" [ & < p1" 9 & < % Z p& [ p1)
and P(Y = 1) = P(X 9 &".P(Y = 1 | X 9 &" [ P(X = 1).P(Y = 1 | X = 1)
9 & < p&" [ & < % Z p1" 9 & < % Z p1 [ p&).
Source Coding ° 17
Suppose that we are at the receiver end and we want to comment about what was transmitted at the
transmitter, having observed what is received at the receiver. The mutual information about the occur-
rence of the event X 9 & 0 Y9& 0
Ê P (Y = 0| X = 0) ˆ Ê 1 - p0 ˆ Ê 2(1 - p0 ) ˆ
I(x&; y&) = I &\ &" 9 log 2 Á = log 2 Á = log 2 Á
Ë P (Y = 0) ˜¯ Ë 0.5(1 - p0 + p1) ˜¯ Ë 1 - p0 + p1 ˜¯
Ê P (Y = 0| X = 1) ˆ Ê 2 p1 ˆ
Similarly, I(x1; y&) = I %\ &" 9 log 2 Á ˜ = log 2 Á
Ë P (Y = 0) ¯ Ë 1 - p0 + p1 ˜¯
The conditional self-information can be interpreted as the self-information about the event
X = xi having observed the event Y = yj. Recall that both I(xi) ≥ 0 and I(xi | yj) ≥ 0. Therefore,
I(xi; yj) < 0 when I(xi) < I(xi | yj) and I(xi; yj) > 0 when I(xi) > I(xi | yj). Hence, mutual
information can be positive, negative or zero.
Example 1.5 Consider the BSC discussed in Example 1.3. The plot of the mutual information
I(x ; y ) versus the probability of error, p is given in Fig. 1.3.
It can be seen from Fig. 1.3 that I(x ; y ) is negative for p
follows. A negative mutual information implies that having observed Y = y , we must avoid choosing
X = x as the transmitted bit.
For p I(x ; y1) = I 22(p) = log2 ! "
This shows that the mutual information between the events X = x and Y = y1 is negative for p
For the extreme case of p = 1, we have
I(x ; y1) = I 22(p) = log22(1) = 1 bit
Fig. 1.3 The plot of the mutual information I(x0; y0) versus the probability of error, p.
18 ° Information Theory, Coding and Cryptography
The Average Mutual Information between two random variables X and Y is given by
n m n m P (xi , y j )
I(X; Y) = Â Â P (xi , yj ) I (xi ; yj ) = Â Â P (xi , yj ) log P (x ) P ( y )
i =1 j =1 i =1 j =1 i j
n m P ( y j | xi )
= Â Â P ( xi ) P ( yj | xi ) log P( yj )
i =1 j =1
m n P ( xi | yj )
= Â Â P ( yj ) P ( xi | yj ) log (1.13)
j =1 i =1 P ( xi )
For the case when X and Y are statistically independent, I(X; Y i.e., there is no average mutual
information between X and Y. An important property of the average mutual information is that I(X; Y) ≥
with equality if and only if X and Y are statistically independent.
When X represents the alphabet of possible output letters from a source, H(X) represents the average
information per source letter. In this case H(X) is called the entropy. The entropy of X can be interpreted
Ê 1 ˆ
as the expected value of log Á . The term entropy has been borrowed from statistical mechanics,
Ë P ( X ) ˜¯
where it is used to denote the level of disorder in a system. It is interesting to see that the Chinese character
for entropy looks like !
Ê 1 ˆ
We observe that since 0 £ P (xi ) £ 1 , log Á ≥ 8 H(X) ≥ .
Ë P( xi ) ˜¯
Example 1.6 Consider a discrete binary source that emits a sequence of statistically independent
/" + + # " " p or 1 with a probability 1 – p. The entropy of this binary
source is
Source Coding ° 19
1
H(X) = - Â P (xi ) log P (xi )
i =0
= – p log2(p) – (1 – p) log2(1 – p) (1.15)
The plot of the binary entropy function versus p
$ 9 6
' " $ 4 / + $ + 4
binary entropy function reaches its maximum value
for p i.e. # " :+ <
In general, it can be shown that the entropy of a
discrete source is maximum when the letters from
Fig. 1.4 The entropy function, H(X) = – p log2(p)
the source are equally probable.
– (1 – p) log2(1 – p).
speaks 60 words per minute and the average number of letters per word is 6. The average
number of letters spoken per second in this case is 6 letters per second. Assuming each letter
carries 1.25 bits of information, the information rate of an average speaker is 7.5 bits/second.
If each letter is represented by 5 bits, the bit rate of an average speaker is 30 bits/s. However, the typical data
rate requirement for speech is 32 kilobits/s!
INDUSTRIAL RELEVANCE
# '0 0 ( 6
0 ' 7 &08 ' ( ( ' ( 0
6 '
( 0 0 7 &08 ' ( 0
/ *9"#4+ # '0
: 12# 6; <==> ? 7 &08 1"#4 - 6, 6 - 57>@A 1"#4
?7== A?== B== 08 26: 7 &08 0 1"#489"#4
The Joint Entropy of a pair of discrete random variables (X, Y) with a joint distribution
p(x, y n m
H (X, Y) = - Â Â p ( xi , y j ) log p ( xi , yj ) (1.23)
i =1 j =1
Source Coding ° 21
H (X ) H (X |Y ) I (X; Y ) H (Y |X ) H (Y )
Fig. 1.5 The relationship between entropy and the mutual information.
In order to calculate the values of H(X|Y), we can make use of the following equalities:
P (xi , yj) = P (xi | yj) P( yj) = P ( yj | xi) P(xi V
22 ° Information Theory, Coding and Cryptography
Probability 1–p
q 0 0
p
Tx Rx
1–p p
1–q 1 1
Channel
Fig. 1.6 A binary symmetric channel (BSC) with input symbols probabilities equal to q and 1 – q.
The plot of H(X|Y) versus q is given in Fig. 1.7 with p as the parameter.
H(X/Y) I(X;Y)
1 1
p = 0.5 p = 0, 1
0.8 0.8
Fig. 1.7 The plot of the conditional entropy Fig. 1.8 The plot of the average mutual
H(X|Y) versus q. information I(X; Y) versus q.
The Average Mutual Information between two continuous random variables X and Y
!
p ( y | x) p ( x)
I(X;Y) = Ú Ú p ( x) p ( y | x) log
p ( x) p ( y )
dxdy $ %&
!
from discrete random variables to continuous random variables, but the concept and physical
interpretation cannot. The reason is that the information content in a continuous random variable
Source Coding ° 23
Again, it should be understood that there is no physical meaning attached to the above quantity. We
" # !
Ê p( x) ˆ
It can be interpreted as the expected value of log Á .
Ë q ( x) ˜¯
Example 1.9 Consider a Gaussian distribution p(x) with mean and variance given by (m1, s12),
and another Gaussian distribution q(x) with mean and variance given by (m2, s22). Using (1.33), we can
! 23 4
24 ° Information Theory, Coding and Cryptography
1 È s 2 Ê m - m1 ˆ Ês2ˆ˘
2
D(p|| q) = Í 12 + Á 2 ˜ - 1 - log 2 Á 12 ˜ ˙ $ *-
2 Ís 2 Ë s 2 ¯ Ë s 2 ¯ ˙˚
Î
The distance becomes zero when the two distributions are identical, i.e., m1 = m2 and s12 = s22. It is
interesting to note that when m1 π m2 , the distance is minimum for s12 = s22. This minimum distance is
given by 2
1 Ê m 2 - m1 ˆ
Dmin (p || q) = Á
2 Ë s 2 ˜¯
. 23 ! s12 Æ or s22 Æ , that is, if either of the distributions tends
to the Dirac delta.
The average mutual information can be seen as the relative entropy between the joint distribution, p(x, y),
and the product distribution, p(x)p(y), i.e.,
I (X; Y) = D (p(x, y) || p(x) p(y)) (1.35)
We note that, in general, D (p || q) π D (q || p). Thus, even though the relative entropy is a distance measure,
it does not follow the symmetry property of distances. To overcome this, another measure, called the Jensen
5 ! "
The Jensen Shannon Distance between two probability mass functions p(x) and q(x)
!
1 1
JSD (p || q) = D ( p || m) + D (q || m) (1.36)
2 2
1
where m = ( p + q ).
2
One can show that the relative entropy D(p || q) is convex in the pair (p, q), while the entropy function
H(p) is a concave function of p. The concavity of H(p) is also evident from observing the binary entropy
! " # $ % !
H (lp1 l) p2) ≥ lH(p1) ( l) H(p2) &
" & ' * " "*
is always larger. We also know from thermodynamics that mixing of two ideal gases of equal entropy results
in a gas with higher entropy due to the irreversible processes of expansion of the two gases! Again, consider
Source Coding ° 25
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO 1:
4 589 ! " : ; ; ? # ! S
entropy, H(X).
2. A source, X 0 * " " * !! ! / * S
P(xi) = 2-i, i = 1, 2, 3, …. What is the average self information, H(X ! @
3. Consider a geometrically distributed random variable X with P(xi) = p(1 – p)i-1, i = 1, 2, M
3, … What is the average self information, H(X ! @
$ 4 N identical unfair coins, with the probability of getting a head P(H) = p. S
Suppose these N unfair coins are tossed simultaneously and we are interested in the event
of getting at least one head.
B ! ! / * * / @
(ii) What happens when N Æ in (i). Explain what it physically means.
5. The following table shows the joint probability distribution of two random variables X M
and Y with respective values xi and yi. Calculate H(X), H(Y), H(X,Y), H(X | Y) and H(Y | X).
x1 x2 x3
y1 1/2 H H
y2 H H
6. Calculate the differential entropy, H(X), of the uniformly distributed random variable X S
with the pdf:
ÏÔa -1 (0 £ x £ a )
p(x) = Ì
ÔÓ 0 (otherwise)
Plot the differential entropy, H(X), versus the parameter a MaM 4
result.
# % % & #
S Simple: Level 1 and Level 2 Category
M Medium: Q / Q / $4 *
D % & # ' Level 5 and Level 6 Category
26 ° Information Theory, Coding and Cryptography
Note that the variable length code uses fewer numbers of bits simply because the letters appearing
more frequently in the pseudo sentence are represented with fewer numbers of bits.
\ * / ! 0 X " ~
Variable length code 2
% ! / ! "" 0! "
However there is a problem with VLC2. Consider the sequence of bits 0 1001 0001 which
is used to represent A BAD CAB in the second variable length coding scheme. We could
regroup the bits in a different manner to have [0] [10][0][1] [0][0][01] which translates
"# $# "# "# $# "# "# "# $#
for A BAAB AAAB ! Obviously there is a problem with the unique decoding of the code. We
have no clue where the codeword of one letter (symbol) ends and where the next one begins, since the
lengths of the codewords are variable. However, this problem does not exist with the VLC1. It can be seen
% & '* % + . So, as soon
as a sequence of bits corresponding to any one of the possible codewords is detected, we can declare that
symbol decoded. Such codes are called . There is no decoding delay in these codes.
If decoding delays are permitted, we may use in which the encoded string
could be generated by only one possible input string. However, one may have to wait until the entire
% ' & 4 * & 8 9 :? @
decodable code, hence not a code of any practical utility. The VLC1 is uniquely decodable, though less
economical in terms of bits per symbol.
28 ° Information Theory, Coding and Cryptography
A* +! ! ! " 0' * !
Such codes are also called Instantaneous Codes.
Our objective now is to devise a systematic procedure for constructing uniquely decodable, variable length
! 0! / " ! Q ! " *
0 * xi, i = 1, 2, …, L, occurring with probabilities P(xi), i = 1, 2, …, L. The average
" ! 0
L
R = Â ni P (xi ) $
i =1
where ni is the length of the codeword (in terms of number of bits) for the symbol xi .
. / % 0 1 # ' _ ! * 0! ! ' ! *!
with codewords having lengths n1 £ n2 £… nL * " 0' !
L
 2- n k
£ $$
k =1
codes. This process continues until the last codeword is assigned at the terminal node n = nL. Consider the
node of order j < L. The fraction of number of terminal nodes eliminated is
j L
 2- nk <  2- n k
£ $;
k =1 k =1
% / ! ! " 0' !
embedded in the full tree of nL nodes. The nodes that are elimi-
c1
nated are depicted by the dotted arrow lines leading on to them
0 0
We now prove the necessary condition. We observe that in
0
the code tree of the order n = nL, the number of terminal nodes
eliminated from the total number of 2n terminal nodes is 1 c2
0
L
 2n- n
0 c3
k
£ 2n $ 1
k =1 1 c4
This leads to n
L
 2- n k
£ $ Fig. 1.9 A binary tree of order nL.
k =1
\ ! * ' " " 0' ! / " M. For the proof we will have to
consider an M-ary tree instead of a binary tree. The inequality in this case would become
L
 M -n k
£ $
k =1
Source Coding ° 29
We now state and prove the noiseless Source Coding theorem, which applies to the codes that satisfy the
" 0' !
. 2 & ! ". ' Let X 589 0 "*
H(X) and the output symbols xk, k = 1, 2, …, L, occurring with probabilities P(xk), k = 1, 2, …, L. It is possible
! ! ! 0 " 0' ! / R 0 ^ *
Ê L ˆ
£ (log2 e) Á Â 2- nk - 1˜ £
Ë k =1 ¯
30 ° Information Theory, Coding and Cryptography
k =1 k =1
! " P (xk) < 2 –nk . Take
logarithm on both sides to get
log2 P(xk) < – nk
or nk < 1 – log2 P(xk)
On multiplying both sides by P(xk) and summing over 1 £ k £ L we obtain
L L Ê L ˆ
 P (xk ) nk <  P (xk ) Á -  P (xk )log 2 P ( xk )˜
Ë k =1 ¯
k =1 k =1
or R < H(X#
Thus, the upper bound is proved.
! $
the minimum number of bits required to represent the source symbols on an average must be at least equal
% & ! ! R = H(X) for a certain source X, we
must abandon further search because we cannot do any better. The theorem also tells us that a source with
higher entropy (uncertainty) requires, on an average, more number of bits to represent the source symbols in
!
% ! ! h£ !
of symbols leads to compression of data. Source coding is primarily used for compression of data (speech,
text, facsimile, image, video etc.).
Example 1.12 Consider a source X which generates four symbols with probabilities P(x1# + *
P(x2) + - P(x3) + P(x/) +
4
H(X) = - Â P (xk ) log 2 P (xk ) + 04* $
k =1
5 ! 6 7 &
codeword length, R is given by
4
R = Â nk P (xk ) + ' *# 8' -# -' # -' #+ 9 $
k =1
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO 2:
? $ ! S
6 8 8 -7
2. Suppose we have to assign binary codewords to N symbols, with each codeword satisfying S
! % $ & 6 8 - @ N7A
3. We would like to encode a sequence of symbols that come from an alphabet with d - M
symbols. We want to encode symbols a1, a2, and a3 using codewords that are three bits
long. We want to encode symbols a/, a5, …, ad - using codewords that are eight bits
long. What is the maximum value of d for which this will be possible, if the code must be
$ A
/ 5 L of an instantaneous D-ary code for a given random D
variable X can be bounded by L ≥ HD(X), where HD(X) is the source entropy. When will
A
If you have successfully solved the above problems,
! " # $
(iv) Continue the procedure until only one probability is left (and it should be 1 if your addition is right!).
This completes the construction of the Huffman tree.
symbol. While tracing back the route, read out the labels on the branches. This is the codeword for the
symbol.
The algorithm can be easily understood using the following example.
Example 1.13 Consider a DMS with seven possible symbols xi, i = 1, 2, …, 7 and the corre-
sponding probabilities P(x1 "# P(x2 "" P(x3 $% P(x& # P(x5 & P(x6) = '
and P(x7 $ * + /// / / + 0
tree (Fig. 1.12).
Symbol Probability Self Codeword
Information
x1 "# $ &"&&
x2 "" $ 8998 $
x3 $% ' %&"9 $$
x& # " :"%8 $$$
x5 & & %&"9 $$$$
x6 ' 8 %&"9 $$$$$
x7 $ % %&"9 111111
/ ;
symbol. For the sake of illustration we show the route for the symbol x& / // # /
/ * / $$$
The entropy of the source is found out to be
7
H(X) = - Â P (xk ) log 2 P (xk ) = 2.1152 bits
k =1
Fig. 1.12
and the average number of binary digits per symbol is calculated to be
7
R = Â nk P (xk )
k =1
$ "# < ' "" < " $% < & # <8 & <% ' <% $ ' $# /
/ / / h ' $$8'>' $# 9#&#
Source Coding ° 33
Example 1.14 This example shows that Huffman coding is not unique. Consider a DMS with
seven possible symbols xi, i = 1, 2, …, 7 and the corresponding probabilities P(x1 &% P(x2 "
P(x3 $' P(x& % P(x5 " P(x6 ' and P(x7 $
Fig. 1.13
$ &% < ' " < " $' < & % <8 " <% ' <% $ $ 99 /
/ / / h $ 9#:$>$ 99 99&
We shall now see that Huffman coding is not unique. Consider the combination of the two
smallest probabilities (symbols x6 and x7 / / ? " / / ?
next higher probability corresponding to the symbol x5. So, for the second step, we may
choose to put this combined probability (belonging to, say, symbol x6¢) higher than, or lower than, the
34 ° Information Theory, Coding and Cryptography
symbol x5 @ / // * + /
the combination of x6¢ and x5 / // % / / ? x&. We again
have a choice whether to put the combined probability higher than, or lower than, the symbol x&. Each
/ / A/ / / +/ + B
G/+ $ $& / / /// ?
probability of the combined symbols at a higher level.
Fig. 1.14 ! !
x2 " $ #"# 2
x5 " 8 8:9 $ $ 5
x6 ' 8 %&"9 $ 6
x7 $ % %&"9 $ $ 6
$ &% < ' " < " $' < & % <8 " <% ' <% $ $ 99 /
/ / / h $ 9#:$>$ 99 99& ? /
This also tells us that Huffman codes are not unique for a given set of probabilities.
Suppose we change the probabilities slightly and the new probabilities are given by P(x1 &'
P(x2 " P(x3 $8 P(x& # P(x5 " P(x6 ' and P(x7 $
Source Coding ° 35
7
The entropy of this source is H(X) = - Â P (xk ) log 2 P (xk ) ' 8%9 / 0 / +/
k =1
x1 &' 1.2515 1 1
x2 " $ #"# 2
x3 $8 ' #"# $ 3
x7 $ % %&"9 $$$$$ 6
We observe that in spite of the change in the probability values, the Huffman code is the same as
7
generated by Fig. 1.13. The average codeword length R = Â nk P (xk ) ' : / /
k =1
this code is h ' 8%9>' : 9::9. Intuitively, we can say that the codeword lengths, which must
/ + + A + / /// / /
the input signals.
Let us now carry out a similar exercise for another set of symbol probabilities as shown in the given
table.
Symbol Probability Self Codeword Codeword
Information Length
x1 1/2 1 1 1
x2 1 22 2 2
x3 1 23 3 $ 3
x5 1 25 5 $$$ 5
x6 1 26 6 $$$$ 6
x7 1 26 6 $$$$$ 6
36 ° Information Theory, Coding and Cryptography
B / +/ P / /
blocks of B symbols at a time. In this case the bounds of the source coding theorem becomes
BH(X) £ RB < BH(X < $ $ 8$
since the entropy of a B-symbol block is simply BH(X), and RB is the average number of bits per B-symbol
block. We can rewrite the bound as
RB 1
H(X) £ < H(X < (1.52)
B B
RB
where ∫ R is the average number of bits per source symbol.
B
Thus, R can be made arbitrarily close to H(X) by selecting a large enough block B.
Example 1.15 Consider the source symbols and their respective probabilities listed in the given
table.
Symbol Probability Self Information Codeword
x1 & $ "'$9 1
x2 "8 $ 8$&%
x3 '8 ' $
Example 1.16 Consider the source symbols and their respective probabilities listed in the table.
' '8 < " $8 < " $8 < " $ <" $ <& 9 <& % <
& % <& & " / /
fi R " >' $8 /
/ // h2 $ &:88 >$ 8 99 " B / + / + +
/ / / V0 / + " /
/ 0 / + / / h3 99"' X + / +
four letters at a time we see a further improvement (h& 99&%
Source Coding ° 39
È 1 ˘
Codes that use the codeword lengths of l(x) = Ílog are called Shannon Codes. Shannon codeword
Í P ( x) ˙˙
+ / Y / ? / /? . In this
section we will study another simple method for constructing uniquely decodable codes based on Shannon-
Fano-Elias encoding technique. It uses the Cumulative Distribution Function to allocate the codewords.
/ / / / / /
F(x) = Â P( z) (1.53)
z£ x
This implies that ÍÎ F ( x) ˙˚ l (x) lies within the step corresponding to x, and l(x / / / x.
–l(x)
The interval corresponding to any codeword is of length 2 . From (1.55) we see that this interval is less
È 1 ˘
than half the height of the step corresponding to x. Since we use l(x) = Ílog + 1 bits to represent x, the
Í P ( x) ˙˙
expected length of this code is
ÊÈ 1 ˘ ˆ
R = Â P ( x) l ( x) = Â P ( x) Á Ílog ˙ + 1 < H (X ) + 2
P ( x) ˙ ˜¯
(1.57)
x x ËÍ
Thus the Shannon-Fano-Elias coding scheme achieves codeword length within two bits of the entropy.
40 ° Information Theory, Coding and Cryptography
Example 1.17 Consider the D-adic distribution given in the following table.
È 1 ˘
Symbol Probability F(x) F ( x) F ( x) (binary) l(x) = Ílog ˙ +1 Codeword
Í P ( x) ˙
x1 1/2 2
x2 1 22 3
x3 1 23
x 1 23 1 1111
The entropy for this distribution is 1.75 bits. However, the average codeword length for the Shannon-
Fano-Elias coding scheme is 2.75 bits. It is easy to observe that if the last bit from all the codewords is
deleted, we get the optimal code (Huffman code). It is worthwhile to note that unlike in Huffman coding
! " #$
probabilities and redo the exercise.
È 1 ˘
Symbol Probability F(x) F ( x) F ( x) (binary) l(x) = Ílog ˙ +1 Codeword
Í P ( x) ˙
x1 1 22 3
x2 1/2 2
3
x3 12
x 1 23 1 1111
We observe that the codewords obtained from the Shannon-Fano-Elias coding procedure is not
unique. The average codeword length is again 2.75 bits. However, this time we cannot get the optimal
code simply by deleting the last bit from every codeword. If we do so, the code no longer remains a
!% & #' *+ *, - . #!
algorithm for encoding and decoding called Arithmetic Coding.
(a) 5 !% . - # # - # .-
are integers. The length matching may ascribe a codeword either longer than the self information
or shorter. The exact match is possible if and only if the self information is in integral number
of bits.
(b) 6# !% .
tree branches always take one bit. This is regardless of the fact whether the probabilities for
7 7 6 . 4 .
Source Coding ° 41
(– log28 99 ! 8: 28 99
- 4 8 ¥ ; ¥ 3.32). The Huffman code still
needs one bit for each decision.
/ - 6 4 . ! .
# - ' .- -
accordance with the probability of that symbol. The more likely symbols reduce the range by less, and thus
add fewer bits to the message.
Example 1.18 Let our alphabet consists of only three symbols A, B and C with probabilities of
occurrence P(A9 < P(B9 < P(C9 < = ! > 9
proportional to their probabilities, as depicted in step 1 of Fig 1.16. Thus, the variable A corresponds
> 9 B > 9 C > 9 ?
that the lengths of these intervals are proportional to their probabilities. Next, suppose the input symbol
stream is B A C A @ = ! B. This is nothing but choosing the corresponding interval, i.e.,
> 9 ?
of occurrence. So, for the second step (see Fig. 1.16), the variable A > 9
variable B > 9 C > 9 ' %
symbol to arrive after B is A / > 9 &
. > 9# A > 9 # B, and the
> 9 # C. Now we look at the next symbol to encode, which is C. This corresponds
> 9 A # A, we are left with the interval
> 9 & - # B A C A is any number that lies within this interval. To
complete this example, we can say that the arithmetic code for the sequence B A C A
Next consider the decoding at the receiver. The receiver needs to know a-priori, the probabilities of
A, B and C. So, it will also have an identical number line, partitioned into three segments, proportional
to the probabilities of A, B and C " . + 4
- A . B B - B. So the 1st decoded
symbol is B. Now we split the segment corresponding to B into three sub-segments proportional to the
probabilities of A, B and C (exactly as we did at the encoder side). Again we map the received number
! # A. The decoding is instantaneous. Mechanically, we proceed
% .- C 4 D& #
to have a stopping criterion, or a pre-decided protocol to do so.
Fig. 1.16 ! B A C A.
42 ° Information Theory, Coding and Cryptography
& - # # G % - # . % !%I
' # . E G E G ? % . %
. 0 # & # . - # !%
I
? # !
# # - 8 # %
- 9 ? % - # - # !%
phrase plus the new bit needed to create the new phrase. We will use parentheses and commas to separate
! J # & .I
8 98 98 98 98 98 98 98 9
Source Coding ° 43
6 I8 9 8 9 8
9 8 9 8 9 8 9@
& # I & .
for this example is given in Table 1.1. In this case we have not obtained any compression, our coded
string is actually longer! However, the larger the initial string, the more saving we get as we move along,
!% F - - - 6 # H
# - - # ! - - -
by the information content of the document.
11
111
The next question is what should be the length of the table. In practical application, regardless of the
# . $ & - . *
size of the dictionary. The encoder and decoder can update their dictionaries by periodically substituting the
less used phrases from their dictionaries by more frequently used ones.
INDUSTRIAL RELEVANCE
# $ ' 6 (
:-2C ( 6
( 0 ' ( A? 0 A / 0 '
: # $ ("
/ 0 0 >> ' 0
7<
44 ° Information Theory, Coding and Cryptography
The Graphics Interchange Format (GIF) is also based on Lempel-Ziv coding. In GIF, the image
! . - * .* & " - *H
coding is then applied to this string. However, the 2-D structure of the image is not used as an
& 5 ? 4V 85?V9 # - J *W # - .!
subtracting the pixel values of a row from the one above it, and then carrying out Lempel-Ziv coding on the
residual.
In the following section we will study another type of source coding scheme, particularly useful for
facsimile transmission and image compression.
INDUSTRIAL RELEVANCE
% ( ( 49C ( 6 49C (
' ( 49 4 0 ( (' (
0 ( ' ;, 6 49C (
umbrella name for several possible image compression methods and a means to identify which
0 6 49C 0 0 (
52! 34"5 4-5
= # 5A] - . -
and not those parts that store the color palette and image information such as number of lines, pixels per line,
! -
The basic scheme is as follows. If a string of pixels are identical in color value, encode them as a special
4 " byte which contains the count followed by a byte with the value of the repeated pixel. If the pixel is not
repeated, simply encode it as the byte itself. Such simple schemes can often become more complicated in
practice. Consider that in the above scheme, if all 256 colors in a palette are used in an image, then, we need
all 256 values of a byte to represent those colors. Hence if we are going to use just bytes as our basic code
G . . $ 7 . }
# . # . % -# $ 7 - -
size of pathological images instead of compressing them.
& - - 5A] # - # # - . *
drawings (which was the primary intended output of their software) would not use all 256
' . -J - - # # .
Images with more colors will also probably get good compression, just not quite as good, with this scheme.
1
2
3
: : :
BE
BF
46 ° Information Theory, Coding and Cryptography
+ 8 9 F .
- ! 8\'C 9 = #. $
. 6# \'C F . . $ & -
$ 7 . . - # 8# - 9 &
byte is then followed by the byte which represents the color. In fact, if we have a run of pixels of one of
.
reserved in this second, color code byte of a run coding byte pair.
6# # % % - . # ! %
then code additional runs of that pixel until we exhaust all pixels in the run. The next question is: how
- .# - D=
. - . & - # # -
appear as single pixels in the image and not part of runs, we expand the data by a factor of two. Luckily
this rarely happens!
6 % . # . ! -
of bits to accurately represent an analog source. Anything fewer will only be an approximate representation.
We can choose to use fewer and fewer bits for representation at the cost of a poorer approximation of the
original signal (rule of thumb: there is no free lunch!). Thus, quantization of the amplitudes of the sampled
signals results in data compression. We would like to study the distortion introduced when the samples from
the information source are quantized.
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO 3:
A W\'
(i) Determine the Huffman code for this source. S
It has been assumed here that the random process is stationary. Next, let a memoryless source have
a continuous output X and the quantized output alphabet X� . Let the probability density function of this
continuous amplitude be p(x) and per letter distortion measure be d ( x, x� ) , where x Œ and x� Œ X� . We next
introduce the rate distortion function which gives us the minimum number of bits per sample required to
.- !
The minimum rate (in bits/source output) required to represent the output X of the
memoryless source with a distortion less than or equal to D is called the Rate Distortion Function R(D),
!
R(D) = min I ( X ; X� ) 8 9
p ( x� | x ): E [ d (X , X� )] £ D
where I ( X ; X� ) is the average mutual information between X and X� . R(D) is also known as
the Information Rate 5 &
Rg(D) 2
0 D/s 2x
0 0.2 0.2 0.6 0.8 1
2
Fig. 1.17 " ! Rg(D) versus D/s x .
Source Coding ° 49
. There exists an encoding scheme that maps the source output into codewords such that for
any given distortion D, the minimum rate R(D9 - #!
with an average distortion that is arbitrarily close to D.
Thus, the distortion function for any source gives the lower bound on the source rate that is possible for a
given level of distortion.
The Distortion Rate Function for a discrete time, memoryless Gaussian source is
!
2
Dg(R) = 2 –2R s x (1.66)
Example 1.22 For a discrete time, memoryless Gaussian source, the distortion (in dB) as a
function of its variance can be expressed as
Dg(R) = – 6R ; s x2 (1.67)
Thus, the mean square distortion decreases at a rate of 6 dB/bit. In other words, each bit reduces the
% . # #
The rate distortion function of a discrete time, memoryless continuous amplitude source with zero mean
! s x2 with respect to the mean square error distortion measure D is upper bounded as
1
R(D) £ log 2 (s x2 /D) £ D £ s x2 8 9
2
This upper bound can be intuitively understood as follows. We have seen earlier that for a given variance,
the zero mean Gaussian random variable exhibits the maximum differential entropy attainable by any random
variable. Hence, for a given distortion, the minimum number of bits per sample required is upper bounded
by the Gaussian random variable.
& % F I= # F J D6 .
F J - -J - . D= !
questions in the next section.
In this section, we look at optimum quantizers design. Consider a continuous amplitude signal whose
amplitude is not uniformly distributed, but varies according to a certain probability density function, p(x). We
wish to design the optimum scalar quantizer that minimizes some function of the quantization error q = x� - x ,
where x� is the quantized value of x. The distortion resulting due to the quantization can be expressed as
D = Ú f ( x� - x) p ( x) dx 8 9
where f ( x� - x) is the desired function of the error. An optimum quantizer is one that minimizes
D by optimally selecting the output levels and the corresponding input range of each output
level. The resulting optimum quantizer is called the Lloyd-Max quantizer. For an L-level
quantizer the distortion is given by
L xk
D = ÂÚ f ( x�k - x) p ( x)dx 8 9
xk -1
k =1
50 ° Information Theory, Coding and Cryptography
The necessary conditions for minimum distortion are obtained by differentiating D with respect to {xk
and { x�k / # ## # . - # F
f ( x�k - xk ) = f ( x�k +1 - xk ), k = 1, 2, …, L – 1
xk (1.71)
Ú f ¢ ( x�k +1 - x) p ( x) dx , k = 1, 2, …, L
xk -1
For f (x) = x2, i.e., the mean square value of the distortion, the above equations simplify to
1
xk = ( x�k + x�k +1) , k = 1, 2, …, L – 1 (1.72)
2
xk
Úx k -1
( x�k - x) p ( x) dx < k = 1, 2, …, L
The non uniform quantizers are optimized with respect to the distortion. However, each quantized sample
is represented by equal number of bits (say, R 7 - 9 6 - #!
length coding. The discrete source outputs that result from quantization can be characterized by a set of
probabilities pk & #! 8 9
6 - # - # ## # -F J ! !% D, and
then compare the average number of bits required per sample.
Example 1.23 Consider an eight level quantizer for a Gaussian random variable. This problem
mean square error minimization, the values xk and x�k are listed in Table 1.3.
Table 1.3 Optimum quantization and Huffman coding.
x�k Huffman
Level, k xk P (xk)
Code
1 " #$% – 2.152 $
2 " & " '$$ #
3 " & " #& *
$ " *$&
5 & *$& 11
6 & #& *
7 #$% '$$ #
% 2.152 $
in the selection of symbols. It would, therefore, be interesting to calculate the average information content
of a symbol in a long message. Suppose, the source X uses M symbols s1, s2, …., sM with associated proba-
bilities of occurrences p1, p2, …., pM. In a long message of length N, the symbol si will occur piN times. The
Ê 1ˆ
information content of the ith symbol will be log 2 Á ˜ bits. Thus, the piN occurrences of si will contribute
Ë pi ¯
Ê 1ˆ
an information content of pi N log 2 Á ˜ bits. Therefore, for all the M symbols, the total contribution will be
Ë pi ¯
M
Ê 1ˆ
ITot = Â pi N log 2 Á ˜ bits (1.73)
i =1 Ë pi ¯
The average information per symbol for the source X is obtained by
ITot
M
Ê 1ˆ
H(X) = = Â pi log 2 Á ˜ @ #$:
N i =1 Ë pi ¯
0 8 > >
A simple extension of the source coding theorem tells us that nH(X: 0 ; > ;
describe n independent and identically distributed random variable, each with entropy H(X). But, in the real
world, we do encounter random variables that are dependent. What if the random variables form a stationary
8 C
A stochastic process is said to be stationary if the joint distribution of any subset of the
sequence of random variables is invariant with respect to shifts in time index, i.e.,
P(X1 = x1, X2 = x2,… Xn = xn) = P(X Dm = x1, X* D m = x2,… XnDm = xn) (1.75)
for every shift m and for all x1, x2,… xn ŒX.
Example 1.24 Suppose random variables X, Y and Z form a Markov chain and we denote it by
X Æ Y Æ Z. We observe from (1.77) that p(x, y, z) = p(x) p(y | x) p(z | y) = p(x, y) p(z |y). We can write
p(x, z | y) = p ( x, y, z ) = p ( x, y ) p ( z | y ) = p ( x | y ) p ( z | y ) @ #%:
p( y) p( y )
Thus, X Æ Y Æ Z implies X and Z are conditionally independent given Y. Also note that
XÆYÆZ ¤ZÆYÆX @ # :
52 ° Information Theory, Coding and Cryptography
Since, I(X; Y|Z) ≥ ; X Æ Y Æ Z implies I(X; Y) ≥ I(X; Z). This shows that processing of data (recall
Z = f(Y)) cannot improve the inferences that can be drawn from it. Manipulating the data (X) can only
increase our uncertainty about X. This is also known as the Data Processing Inequality.
We now revert back to the entropy rate of a stochastic process. If we have a sequence of n random
variables, it is interesting to explore how the entropy of the sequence grows with n. Entropy rate is used to
0>
Example 1.25 Let X1, X2, X3, … be independent and identically distributed (i.i.d.) random variables.
1 nH (X1)
In this case the entropy rate would be H(X) = lim H (X1 , X 2 , � X n ) = lim = H (X1) . Thus, the
n n n n
entropy rate of an i.i.d. source is the entropy any of its single symbols.
However, if X1, X2, X3, … form a sequence of independent but not identically distributed random
n
1 n
variables, then H (X1,X2,… Xn) = Â H (X i ) . Thus, the entropy rate is lim
n
 H (X i ) . If H (Xi) are
n i =1
i =1
unequal, it is possible to choose a sequence of distributions on X1, X2, X3, … such that the limit of
1 n
 H (X i ) does not exist.
n i =1
Example 1.26 Consider a two-state Markov chain with a probability transition matrix
È1 - p1 p1 ˘
P= Í ˙ @ %$:
Î p2 1 - p2 ˚
8 > %
Source Coding ° 53
For stationary distribution, the net probability distribution across any cut set in the state transition
graph should be zero. Let a and b be the stationary probabilities of the two states. Thus, the stationary
distribution is given by
p2 p1
a = and b = @ %&:
p1 + p 2 p1 + p 2
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO 4:
K P > 0 D
R (D) = min I (X , X� ) for Bernoulli distributed X for a given p.
2. Let a source S{XkQ > 8 Xk, such that H(Xk) = k for S
k ≥ 1. Find the entropy rate of this source.
3. Plot the rate distortion function for a Gaussian source. Verify that R(D) is non-increasing M
in D, R(D) is convex, R@ : £ H(X) and R(D: + 0 D ≥ Dmax.
1. High quality images are represented by very large data sets. A photographic quality image
$ 0 8 >
for extremely high compression ratios to make storage and transmission (particularly of
movies) practical.
2. Applications that involve imagery seem to be inherently linked to immediate human consumption,
and so need to be fast in execution on computers and in transmission. Television, movies, computer
graphical user interfaces, and the World Wide Web are examples of applications in which imagery
must be moved from storage or across some kind of distribution network very quickly for immediate
human intake.
3. Imagery has the quality of higher redundancy than we can generally expect in arbitrary data. For
example, a pair of adjacent horizontal lines in an image are nearly identical (typically), while, two
adjacent lines in a book have essentially no commonality.
8 88 > 0 8
technology available for the movement and storage of image data. The third factor indicates that compression
ratios will usually be quite high. The third factor also says that some special compression techniques may be
possible that will take advantage of the structure and properties of image data. The close relationship between
neighboring pixels in an image can be exploited to improve the compression ratios. This is very important for
the task of coding and decoding image data for real-time applications.
Another interesting point to note is that the human eye is very tolerant to approximation error in an image.
Thus, it may be possible to compress the image data in a manner in which the less important information
(to the human eye) can be dropped. That is, by trading off some of the quality of the image we might obtain
> lossy compression, as opposed to the lossless
compression techniques discussed earlier. This sentiment, however, can never be expressed with regards to,
; \] 8 88 >
0 > 0
Source Coding ° 55
INDUSTRIAL RELEVANCE
# ' ( 34"5
6 34"5 ( ?@ (
( ) E2 0 (
'
0 ( ' ) 0 F
here two methods that use entropy coding.
The two lossless JPEG compression options differ only in the form of the entropy code that is applied to
the innovations data. The user can choose to use either a Huffman code or an Arithmetic code.
We have seen earlier that Arithmetic code, like Huffman code, achieves compression by using
the probabilistic nature of the data to render the information with fewer bits than used in the
original data stream. Its primary advantage over the Huffman code is that it can come closer to
the Shannon entropy limit of compression for data streams that involve a relatively small alphabet. The
reason is that Huffman codes work best (highest compression ratios) when the probabilities of the symbols
can be expressed as fractions of powers of two. The Arithmetic code construction is not closely tied to these
particular values, as is the Huffman code. The computation of coding and decoding Arithmetic codes is more
0 P 00 8 & _ 88 0
Arithmetic codes over that obtained with Huffman coding.
Some compression can be achieved if we can predict the next pixel using the previous pixels. In this way
` 8 0 @ 00 : 0 8
The predictive process that is used in the lossless JPEG coding schemes to form the innovations data is also
P ; ; 8 } ; ;0 >
a line-by-line basis. The choice is made according to that prediction method that yields the best prediction
overall for the entire line.
There are eight prediction methods available in the JPEG coding standards. One of the eight (which is the
no prediction option) is not used for the lossless coding option that we are examining here. The other seven
may be divided into the following categories:
1. Predict the next pixel on the line as having the same value as the last one.
2. Predict the next pixel on the line as having the same value as the pixel in this position on the previous
line (that is, above it).
3. Predict the next pixel on the line as having a value related to a combination of the previous, above and
previous to the above pixel values. One such combination is simply the average of the other three.
The differential encoding used in the JPEG standard consists of the differences between the
actual image pixel values and the predicted values. As a result of the smoothness and general
redundancy of most pictures, these differences consists of a series of relatively small positive
56 ° Information Theory, Coding and Cryptography
and negative numbers that represent the small typical error in the prediction. Hence, the probabilities
associated with these values are large for the small innovation values and quite small for large ones. This is
exactly the kind of data stream that compresses well with an entropy code.
The typical lossless compression for natural images is 2:1. While this is substantial, it does not in general
solve the problem of storing or moving large sequences of images as encountered in high quality video.
where the input image is N pixels by M pixels, y(i, j) is the intensity of the pixel in row i and
column j, Y(k, l: 0 k and column l of the DCT matrix. All DCT
multiplications are real. This lowers the number of required multiplications, as compared to the
discrete Fourier transform. For most images, much of the signal energy lies at low frequencies, which appear
in the upper left corner of the DCT. The lower right values represent higher frequencies, and are often small
(usually small enough to be neglected with little visible distortion). The DCT is, unfortunately, computationally
very expensive and its complexity increases as O(N 2: 0 ; > 8 >
divided into blocks.
Z ~ > 8 ; 88 % %8 Y 0 > P ; 0
> *& *& 8 ; Y '* '* Y 0% %8
8 $8 Y 0 0 $
$ ;Y 0 ;0 0 8 > >
0 8 8 0 0 > 9 Y 88 0 0
DCT matrix has low frequency components and the lower right-corner the high frequency components (see
> : 8 0 0 !& % & . Its value is proportional to the average value
0 % % Y 08 6! & % & .
So far we have not obtained any reduction simply by taking the DCT. However, due to the nature of most
natural images, maximum energy (information) lies in low frequency as opposed to high frequency. We can
represent the high frequency components coarsely, or drop them altogether, without strongly affecting the
quality of the resulting image reconstruction. This leads to a lot of compression (lossy). The JPEG lossy
compression algorithm does the following operations:
1. First the lowest weights are trimmed by setting them to zero.
2. The remaining weights are quantized (that is, rounded off to the nearest of some number of discrete
code represented values), some more coarsely than others according to observed levels of sensitivity
of viewers to these degradations.
Source Coding ° 57
Now several lossless compression steps are applied to the weight data that results from the above DCT
8 ;0 > Y 0 ; 8
> > ; 0 Y 0%¥%8 P ; 8
0 0 > Y Y ` 0 00
0 0 Y 00
Y 0 ; 0 0 > 0
0 zig-zag > > * 8 8 0 >9 > >
is that we gradually move from the low frequency to high frequency, avoiding abrupt jumps in the values.
>9 > > > 0 }; 0 ] 0 P 00
coding.
Fig. 1.20 8 9 9 :9
The typically quoted performance for JPEG is that photographic quality images of natural
8 8 0 8 * *& K
@ ;0 8 8 : 0 8 > 0* 8
*'
P> @P : 0 0 * ¥ % 8 0 0
08 ; 8 >
B= * ¥ % ¥ ¥ + 4 @ :
Clearly, uncompressed video produces an enormous amount of data. Fortunately, digital video contains
a great deal of inherent redundancy, and it is suitable for compression. There are several lossy compression
techniques available for video compression, but there is a trade-off between computational time and quality
of the output. Some of the popular video compression standards and the corresponding application areas are
> $
INDUSTRIAL RELEVANCE
H.261 is an ITU-T video compression standard ' & ( B7 <G7 &0 2
0 ?B/ ( ( ( 26: 6 Video Coding Experts Group
*H9"5+ 6 0 ( ?BA I 0 &J ( 0 & '
0 & * G¥G + 6 ( 92! *<>? ¥ ?GG / +
K92! *ALB ¥ A77 / + H 7 ? = M 9 90 ( 6
0 ( 6
' G ¥ G ;96 ( ' 0 4
( 34"5 6
0 ( * + ' ?; 6
G¥G0 & 0 & " 0 & 0
I J * + I J *'
+ ?BA ' A@@= ' ' / '
' (' ?BA 0 0
?B< ' N F /0 14"5 ( Moving
Picture Coding Exports Group and encompasses a whole family of international standards for
the compression of audio and video digital data.
Source Coding ° 59
6 14"5
1. Reduction of the resolution: The human eye has a lower sensitivity to color than to intensity
@ C: 0 ; 0 -9 98
K9 98 0 8 0 0
than intensity information.
4. Quantization: We have seen in the case of JPEG compression that quantization is the primary
source of data loss. The human eye is more reactive to low frequencies than to high ones (again, is the
> 8 C: ; > 0 8 8
a zero entry thereby setting up the stage for run-length coding. Again, the quantized AC-terms are
stored in a zig-zag-manner with increasing frequency values.
The entropy
coding has two steps: Run Length Encoding (RLE) and Huffman coding. These have been discussed
earlier in the context of JPEG compression.
60 ° Information Theory, Coding and Cryptography
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO 5:
È0 0 0 1 1˘
Í0 1 1 0 1 ˙˙
Í
1. Consider an image represented by A = Í1 0 1 1 0˙ . Find its DCT. M
Í ˙
Í0 1 0 0 0˙
ÍÎ0 0 1 1 0˙˚
È6.77 4.31 2.19 1.56 0.21˘
Í4.02 2.44 1.83 0.31 0.01˙
Í ˙
2. Carry out quantization for the matrix given by A = Í2.26 2.09 0.43 0.02 0.002˙ . S
Í ˙
Í1.97 0.15 0.02 0.01 0 ˙
ÍÎ 0.03 0.04 0.02 0.01 0 ˙˚
Next perform the zig-zag encoding.
3. Perform run length coding on the sequence obtained after zig-zag coding in the previous S
question. NG
RATULATIONS
CO
Shannon was renowned for his eclectic interests and capabilities. A favorite story describes him juggling
while riding a unicycle down the halls of Bell Labs. He designed and built chess-playing, maze-solving,
` >> > 9 > }
by curiosity than usefulness. In his words “I just wondered how things were put together.”
0 0 8 0 ;
0 09 P 00 P 00
&* P 00 > ~ >;
is an extension of the Shannon-Fano-Elias coding technique, was developed by Rissanen and Pasco and
generalized by Rissanen and Langdon.
0 0 > > Y 8
8 # Z ] 8 ~ 8 8
0 KZ 8 > 0 > Z 0 @ 8
Interchange Format), developed by CompuServe, involves simply an application of the Lempel-Ziv-Welch
(LZW) universal coding algorithm to the image data. A more recent approach is to use quantum image
processing.
; 8 ; 0 0Z 0 ;8
*$; * 8 0 8 New York Times:
LEARNING OUTCOMES
Ê 1 ˆ
!Y The self information of the event X = xi is given by I(xi) = log Á = – log P(xi).
Ë P ( xi ) ˜¯
Ê P (xi | y j ) ˆ
Y The mutual information I(xi; yj) between xi and yj is given by I(xi; yj) = log Á .
Ë P (x ) ˜¯
i
Ê 1 ˆ
I(xi | yj) = log Á ˜ = – log P(xi | yj)
Ë P ( xi | y j ) ¯
Y The average mutual information between two random variables X and Y is given by I(X; Y) =
n m n m P (xi , yj )
  P (xi , yj ) I (xi , yj ) =   P (xi , yj ) log P (x ) P (y ) . For the case when X and Y are statistically
i =1 j =1 i =1 j =1 i j
62 ° Information Theory, Coding and Cryptography
!Y!I(xi; yj) = I(xi) – I(xi | yj) and I(X; Y) = H(X) – H(X|Y) = H(Y) – H(Y|X). Since I(X; Y) ≥ ; 8
H(X) ≥ H(X|Y).
!Y The joint entropy of a pair of discrete random variables (X, Y) with a joint distribution p(x, y:
n m
as H (X, Y) = - Â Â p ( xi , y j ) log p ( xi , y j ) .
i =1 j =1
Y The chain rule relating H(X), H(X, Y) and H(X|Y) is H(X, Y) = H(X: D H(Y|X).
!Y The relationship between entropy and mutual information can be expressed as
I(X; Y) = H(X) – H(X|Y) = H(Y) – H(Y|X).
Y The relationship between mutual information and joint entropy can be expressed as
I(X; Y) = H(X: D H(Y) – H(X, Y).
!Y!The average mutual information between two continuous random variables X and Y is given by
p ( y | x) p ( x)
I(X;Y) = Ú Ú p ( x) p ( y | x) log
p ( x) p ( y )
dxdy .
!Y The differential entropy of a continuous random variables X is given by H(X) = - Ú p ( x) log p ( x) dx.
!Y 8 Y] @]: 8 0 p(x)
Ê p ( x) ˆ
and q(x: D ( p || q) =  p( x) log ÁË q( x) ˜¯ .
x ŒX
!Y The Jensen Shannon distance between two probability mass functions p(x) and q(x:
1 1 1
JSD ( p || q ) = D ( p || m) + D (q || m) , where m = ( p + q ) .
2 2 2
Source Coding ° 63
Y 0 0 0 > >
L
n1 £ n2 £… nL 0 8 Â 2- n k
£ 0 0 8 >
k =1
H (X ) .
by h =
R
Y Let X 0 0 8 H(X). The source coding theorem
8 8 ; > >
R H(X) £ R < H(X: D 0 8 0
compression of data.
!Y The expected codeword length of Huffman code is bounded as R £ H ( X ) + 1 .
!Y The expected codeword length of Shannon-Fano-Elias code is bounded as R < H ( X ) + 2 .
!Y 8 0 9 9 > 8 0 > 0
> > > Y 8 >
0
Y In contrast to the Huffman coding scheme, the Lempel-Ziv technique is independent of the source
] 8 9 > > ; P 00
variable length code.
Y Run-length Encoding, or RLE is a technique used to reduce the size of a repeating string of characters.
8 > > 9 > > 88 8 0
Z ;-
Y Distortion implies some measure of difference between the actual source samples {xkQ
corresponding quantized value { x�k Q 9 is given by d ( xk , x�k ) = (xk – x�k )2.
p
In general a distortion measure may be represented as d ( xk , x�k ) = xk - x�k .
Ï0 if xk = x�k
!Y P > d ( xk , x�k ) = Ì .
Ó1 if xk π x�k
Y The minimum rate (in bits/source output) required to represent the output X of the memoryless
source with a distortion less than or equal to D is called the rate distortion function R(D:;
R(D) = min I ( X , X� ) , where I ( X , X� ) is the average mutual information between X and X� .
p ( x� | x ): E [d (X , X� )] £ D
!Y Some properties of rate distortion function: R(D) is non-increasing in D, R(D) is convex, R@ : £ H(X)
and R(D: + 0 D ≥ Dmax.
Y The distortion resulting due to the quantization can be expressed as D = Ú f ( x� - x) p ( x)dx , where
f ( x� - x) is the desired function of the error. An optimum quantizer is one that that minimizes D by
optimally selecting the output levels and the corresponding input range of each output level. The
resulting optimum quantizer is called the Lloyd-Max quantizer.
!Y A discrete stochastic process X1, X2 , … is said to be a Markov chain or a Markov process if, for n = 1,
2…
P(Xn D = xn D | Xn = xn, Xn –1 = xn –1,…, X1 = x1) = P(Xn D = xn D | Xn = xn)
for all x1, x2,… xn, xnD Œ X .
64 ° Information Theory, Coding and Cryptography
1
!Y The entropy rate of a stochastic process X is given by H(X) = lim H ( X1 , X 2 , � , X n ), provided the
n n
limit exists.
!Y For stationary Markov chain, the entropy rate is given by
1.5 The relationship between mutual information and joint entropy can be expressed as
(a) I(X; Y) = H(X) – H(Y: D H(X, Y) (b) I(X; Y) = H(X: D H(Y) – H(X, Y)
(c) I(X; Y) = H(X: D H(Y: D H(X, Y) (d) None of the above
1.6 The expected codeword length of Huffman code is bounded as
(a) R £ H ( X ) + 1 (b) R £ H ( X ) - 1
(c) R < H ( X ) + 1 (d) None of the above
# > 0 > 8 4 0 > C
(a) JPEG (b) H.263
(c) MPEG (d) All of the above
% > @: > C
(a) Lempel Ziv (b) Huffman
(c) Both a and b (d) None of the above
~ 0 > 8
(a) Huffman coding (b) Arithmetic coding
(c) Run-length coding (d) All of the above
9 8 >
(a) I-frames, P-frames and B-frames (b) Discrete Cosine Transformation (DCT)
(c) Quantization (d) Entropy coding
For interactive quiz with answers, scan the QR code given here
Or
Visit [Link]
& 0 ~ 8 C
PROBLEMS
M 1.1 Prove that the entropy for a discrete source is a maximum when the output symbols are equally
probable.
S 1.2 Prove the inequality ln x £ x – 1. Plot the curves y1 = ln x and y2 = x – 1 to demonstrate the validity
of this inequality.
M 1.3 Show that I(X; Y) ≥ K C
S $ ] X 0 0 88
(i) Find the entropy, Hf(X) if the coin is fair.
(ii) Next assume the coin to be unfair with p being the probability of getting a tail. Find the
entropy, Hu(X).
S & 0 0 0
@: Z C C
@ : > > 0 0 > > 0
P 00 0 C 8
M Y] 8 0 p(x) and q(x),
Ê p ( x) ˆ
given by D ( p || q ) =  p( x) log ÁË q( x) ˜¯ .
x ŒX
1
S % > ; X, given by P(X = n) = , where
An log 2 n
1
A=Â 2
and n = 2, 3, … , . Find the entropy, H(X).
n=2 n log n
S ] 88 0 p(xi) @ $: 8 p(x)i Dxi . Show that the expression
0 8 0 > @ ' : 8
0 P > d ( x, x� ) = Ï0, x = x� .
Ì
Ó1, x π x�
Source Coding ° 69
COMPUTER PROBLEMS
1.1 Write a program that performs Huffman coding, given the source probabilities. It should generate the
> > 0 Z 9 8
1.2 Modify the above program so that it can group together n source symbols and then generate the
P 00 > 0 h versus n for the following source symbol probabilities:
¡ &&; *&; * Q 0n 0 C 8
0 0 > 8 ¡ $&; *&; &; ; &Q
1.3 Write a program that executes the Lempel-Ziv algorithm. The input to the program can be the English
alphabets. It should convert the alphabets to their ASCII code and then perform the compression
Z 8 8 K > 8 > ; 8
achieved for the following strings of letters:
@: ] 8 9 > 8 > 0 8
(ii) The cat can not sit on the canopy of the car.
$ 8 > 8 0 ] > > @]: 0 >
output along with the compression ratio. What is the output of the program if the following sequence
is fed into it:
Now feed back the encoded output to the program, i.e., perform the RLE two times on the original
0 C
1.5 Suppose for a certain type of communication we only use three letters A, B and C. The probability
0 0 ¡ & '; *Q P ; 0 8
8 0 0 > @-: + *&; @-: + &; @: + '&;
@-: + &; @-: + &; @: + & ] P 00 Y
the bigrams as Pseudo Markov Huffman (PMH) code.
(i) Design a PMH code for this communication scenario which takes into consideration the bigrams
as well. Write a computer program that can take these probabilities as input and generate the PMH
code.
(ii) Write a program that performs arithmetic coding for this case and compare with the result of the
PMH code.
1.6 Write a program that takes in a 2n level gray scale image (n bits per pixel) and performs the following
operations:
@: - Y 8 % %8 Y
(ii) Performs DCT on each 0 % % Y
@ : § 0 > m > - @ -:;
m £ n.
(iv) Performs the zig-zag coding followed by run length coding.
(v) Performs Huffman coding on the bit stream obtained above (think of a reasonable way of calcu-
lating the symbol probabilities).
(vi) Calculates the compression ratio.
(vii) Performs the decompression (i.e., the inverse operation of the steps (v) back to (i)).
Perform image compression using this program for different values of m. Up to what value of m is
8 8 00 > > 8 > C
70 ° Information Theory, Coding and Cryptography
PROJECT IDEAS
Superinformation: ¦ 8 0 8 };
superinformation.
@: ¦ > >} 0 0 8
of occurrences are design parameters.
(ii) Divide the string into sub-blocks of size B.
(iii) For i th 9 Y; 8 ; Hi.
(iv) Find the histogram of Hi. Normalize this histogram to obtain a pdf.
(v) Find the entropy for this pdf. This is the superinformation (entropy of entropy) of the sequence.
(vi) Use the concept of superinformation on DNA sequences and see if you can segregate exons (coding
regions) from introns (non-coding regions).
3% & & % 7 ! ' The Morse Code for the English alphabet is given in Fig. 1.21.
@: > > 0 0 0
code.
@ : Z C 8
(iii) Compare Morse code with the Huffman code for the English alphabet.
Fig. 1.21
< " 3% & & = ! " (HEVC): Consider the HEVC standard, which is a successor to the
> @P * $4 9$: P 9 8
coding (CABAC) algorithm. CABAC has multiple probability modes for different contexts. It works
> 9 ;0 ;
an appropriate probability model to use. It then uses information from nearby elements to optimize
8 ; > 8 8 8
HEVC scheme using CABAC and perform encoding on simple binary images. Comment on your
results.
Channel Capacity
and Coding
Experimentalists think that it is a mathematical theorem while the mathematicians believe
it to be an experimental fact.
[On the Gaussian curve, remarked to Poincaré:]
Lippman, Gabriel (1845-1921)
learning objectives
LO 1
LO 2
LO 3
LO 4 !
LO 5 !
2.1 Introduction
In the previous chapter we saw that most of the natural
This chapter comes with a video
sources have inherent redundancies and it is possible
overview by the author. Scan here
to compress data by removing these redundancies.
to know more or
Compression is possible by different source coding Visit [Link]
etc.). These bits may be transmitted as they are (for baseband communications), or after modulation (for
passband communications). Unfortunately, all real-life channels are noisy (this is not so unfortunate for those
who make a living out of designing communication systems for noisy channels!). The term noise is used
to designate unwanted waves that tend to disturb the transmission and processing of the wanted signals in
Channel Capacity and Coding ° 73
communication systems. The sources of noise may be external to the system (e.g., atmospheric noise, man
generated noise etc.), or internal to the system (e.g., thermal noise, shot noise etc.). In effect, the bit stream
obtained at the receiver end is likely to be different from the bit stream that is transmitted. For the case
of passband communication, the demodulator processes the channel-corrupted waveform and reduces each
waveform to a scalar or a vector that represents an estimate of the transmitted data symbols. The detector,
which follows the demodulator, may decide on whether the transmitted bit is a 0 or a 1. This is called a hard
decision decoding. This decision process at the decoder is like a binary quantization with two levels. If there
are more than 2 levels of quantization, the detector is said to perform a soft decision decoding. In the extreme
case, no quantization is performed for soft decision decoding.
The use of hard decision decoding causes an irreversible loss of information at the receiver. Suppose the
modulator sends only binary symbols but the demodulator has an alphabet with Q symbols. Assuming the
use of the quantizer as depicted in Fig. 2.1 (a), we have Q = 8. Such a channel is called a Binary input Q-ary
output Discrete Memoryless Channel. The corresponding channel is shown in Fig. 2.1 (b). The decoder
performance depends on the location of the representation levels of the quantizers, which in turn depends on
the signal level and the noise power. Accordingly, the demodulator must incorporate automatic gain control
in order to realize an effective multilevel quantizer. It is clear that the construction of such a decoder is
Fig. 2.1 (a) Transfer characteristic of multilevel quantizer. (b) binary input Q-ary output discrete memoryless
channel.
There are three balls that a digital communication engineer must juggle: (i) the transmitted signal power
(ii) the channel bandwidth and (iii) the reliability of the communication system (in terms of the bit error rate).
Channel coding allows us to trade-off one of these commodities (signal power, bandwidth or reliability) with
respect to others. In this chapter, we will study how to achieve reliable communication in the presence of
noise. We shall ask ourselves questions like how many bits per second can be sent reliably over a channel of
a given bandwidth and for a given signal to noise ratio (SNR)? For that, we begin by studying a few channel
74 ° Information Theory, Coding and Cryptography
In this chapter
" # # ! $
%# & % & %
' % ' ' ( % ) %'
* $ % +( 1.
%# # ! #
" # , ! $ %$
" , % +( 2.
" # ,
" # # - - * +( 3.
%# # % - &
- " # , # . %
' ' ( '
* % +( 4.
/ % +( 5, # # ! )
Fig. 2.2 (a) A binary symmetric channel (BSC). (b) How an image might look after transmission through a
BSC.
This binary Discrete-input, Discrete-output channel is characterized by the set X = {0,1} of possible
inputs, the set Y = {0,1} of possible outputs and a set of conditional probabilities that relate the possible
outputs to the possible inputs. Let the noise in the channel cause independent errors in the transmitted binary
sequence with average probability of error p.
Then,
P(Y = 0| X = 1) = P(Y = 1| X = 0) = p
P(Y = 1| X = 1) = P(Y = 0| X = 0) = 1 – p (2.1)
Channel Capacity and Coding ° 75
Composite Channel
Fig. 2.3 A composite discrete-input, discrete-output channel formed by including the modulator and
demodulator/detector.
So far we have discussed a single channel with discrete inputs and discrete outputs. We can decouple
the modulator and the demodulator from the physical channel (as depicted in Fig. 2.3). Thus, the input to
the channel will be a waveform and the output of the channel will also be a waveform. These are called
Waveform Channels. Such channels are typically associated with a given bandwidth, W. Suppose, x(t) is a
bandlimited input to a waveform channel and y(t) is the output of the channel. Then,
y(t) = x(t) + n(t) (2.3)
where, n(t) is the additive noise.
It is also possible to realize multiple channels between the transmitter and receiver. Such channels can
be readily realized in wireless communication scenarios by using multiple antennas at the transmitter and
receiver. The four obvious combinations are as follows:
(i) Single Input Single Output
antenna both at the transmitter and receiver.
76 ° Information Theory, Coding and Cryptography
A wireless channel is time varying and the variable t is used to capture the time-varying nature of the
channel. If a signal sj(t) is transmitted from the jth transmit antenna, the signal received at the ith receive
antenna is given by
MT
yi (t ) = Â hi , j (t , t ) s j (t ) , i = 1, 2, … MR (2.5)
j =1
The input-output relation of a MIMO channel can be expressed succinctly in matrix notation as
y(t) = H(t, t) s(t) (2.6)
where, s(t) = [ s1 (t ) s2 (t ) sM T (t )]T and , y(t) = [ y1 (t ) y2 (t ) yM R (t )]T
Each link between a pair of transmitter and receiver can be independently represented as a
discrete memoryless channel.
We can also have Relay Channels where there is a source, a destination and intermediate relay
nodes. These relay nodes facilitate the communication between the source and the destination,
as shown in Fig. 2.5(a). There could be several ways to facilitate the transfer of information from the source
to the destination by hopping over the intermediate nodes. One possibility is that each relay node simply
! "
power. This protocol is known as Amplify-and-Forward #$ %# !" !
decode the received signal and then re-encodes the signal before forwarding it to the next relay node. The
processing of the signal at each relay node requires making a hard decision. This protocol is known as
Decode-and-Forward (DF) scheme.
So far we have considered only a single transmitter and a single receiver (though, each one of the trans-
mitters or receivers can have multiple antennas!). In real-life, there can be multiple senders and multiple
receivers (with each one having the possibility of multiple antennas!). Suppose M transmitters (say, mobile
phone users) want to communicate with a single receiver (say, the base station) over a common channel,
as depicted in Fig. 2.5 (b). This scenario is known as a Multiple Access Channel. We can also reverse
the scenario. Suppose a single transmitter (say, a low earth orbit satellite) wants to communicate with M
Channel Capacity and Coding ° 77
receivers (say, the home dish antennas) over a common channel, as shown in Fig. 2.5 (c). This is an example
of a Broadcast Channel.
Fig. 2.5 (a) Relay Channel. (b) Multiple Access Channel. (c) Broadcast Channel.
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO 1:
1. We would like to represent the wireless local area home network consisting of one access S
point and three laptops simultaneously connected to it. What types of channel model
should we use?
2. Graphically represent a binary channel with S
P(Y = 0| X = 1) = p, P(Y = 1| X = 0) = q, P(Y = 1|
X = 1) = 1 – p, P(Y = 0| X = 0) = 1 – q.
3. Consider the binary channel shown in Fig. 2.6. M
Let the a priori probabilities of sending the
Fig. 2.6
binary symbol be p0 and p1, where p0 + p1 = 1.
Find the a posteriori probabilities
P(X = 0|Y = 0) and P(X = 1|Y = 1).
4. Show that a cascade of n BSCs can be effectively represented as a single BSC. M
q -1 r -1 P( yi | x j )
I ( X ;Y ) = Â Â P( x j ) P( yi | x j ) log P( yi )
(2.7)
j =0 i =0
The channel transition probabilities P(yi|xj) are determined by the channel characteristics (primarily the
noise in the channel). However, the input symbol probabilities P(xj) are within the control of the discrete
channel encoder. The value of the average mutual information, I(X; Y), maximized over the set of input
symbol probabilities P(xj) is a quantity that depends only on the channel transition probabilities P(yi|xj)
(hence only on the characteristics of the channel). This quantity is called the
C = max I ( X ; Y )
P( x j )
q -1 r -1 P( yi | x j )
= max   P( x j ) P( yi | x j ) log (2.8)
P( x j )
j =0 i =0 P( yi )
The units of channel capacity is bits per channel use (provided the base of the logarithm is 2).
If the base of the logarithm is e, the units of capacity is in nats per channel use (coming from
the use of natural logarithm).
Channel Capacity and Coding ° 79
È1 - p p ˘
Thus the transition probability matrix is given by P = Í , and p is referred to as
the crossover probability. Î p 1 - p ˙˚
0.8
0.6
Capacity
0.4
0.2
0
0 0.2 0.4 0.6 0.8 1
Probability of error
The plot of the capacity versus p is given in Fig. 2.7. From the plot we make the following observations:
80 ° Information Theory, Coding and Cryptography
(i) For p = 0 (i.e., noise free channel), the capacity is 1 bit/use, as expected. Each time we use the
channel, we can successfully transmit 1 bit of information.
(ii) For p = 0.5, the channel capacity is 0, i.e., observing the output gives no information about the
input. It is equivalent to the case when the channel is broken. We can, might as well, discard the
channel and toss a fair coin in order to estimate what was transmitted.
(iii) For 0.5 < p < 1, the capacity increases with increasing p. In this case, we simply reverse the
positions of 1 and 0 at the output of the BSC.
(iv) For p > @ % %" !J K J! " ! @J P " %
" !K J %
(v) Since p is a monotonically decreasing function of SNR, the capacity of a BSC is a monotonically
increasing function of SNR.
" A discrete memoryless channel is said to be Symmetric if the rows of the channel
transition probability matrix are permutations of each other and the columns are permutations of each
other.
Channel Capacity and Coding ° 81
# A discrete memoryless channel is said to be Weakly Symmetric if the rows of the channel
transition probability matrix are permutations of each other and the column sums  p ( y | xi ) are equal.
For weakly symmetric channels, the capacity is given by xi
and this is obtained for uniform distribution on the input alphabet. Here |Y| represents the cardinality of Y.
Ê 1 1 1ˆ
C = log(3) - H Á , , ˜ = 0.1258 bits/use
Ë 2 6 3¯
Properties
We now list some properties of channel capacity.
1. C ≥ 0, since I(X; Y) ≥ 0.
2. C £ log|X|, since C = max I(X; Y) £ max H(X) = log|X|.
3. C £ log|Y|, since C = max I(X; Y) £ max H(Y) = log|Y|.
Having developed the notion of capacity of a channel, we shall now try to relate it to reliable communi-
cation over the channel. So far, we have only talked about bits that can be sent over a channel each time it is
used (bits/use). But, what is the number of bits that can be sent per second (bits/sec)? To answer this question
we introduce the concept of Channel Coding.
82 ° Information Theory, Coding and Cryptography
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO 2:
1. Find the capacity of the non-symmetric binary erasure channel shown in Fig. 2.9, where M
p0 and p1 are the a priori probabilities.
2. Find the capacity of the channel shown in Fig. 2.10. M
È1 - p 1- p p p ˘
Í 2 2 2 2 ˙
3. Determine the capacity of the channel given by P = Í ˙. S
Í p p 1- p 1- p ˙
ÍÎ 2 2 2 2 ˙˚
In order to achieve such high levels of reliability we have to resort to the use of Channel Coding. The
basic objective of channel coding is to increase the resistance of the digital communication system to channel
noise. This is done by adding redundancies in the transmitted data stream in a controlled manner.
In channel coding, we map the incoming data sequence to a channel input sequence. This encoding
procedure is done by the Channel Encoder. The encoded sequence is then transmitted over the noisy
channel. The channel output sequence at the receiver is inverse mapped to an output data sequence. This is
called the decoding procedure, and is carried out by the Channel Decoder. Both the encoder and the decoder
are under the designer’s control.
As already mentioned, the encoder introduces redundancy in a prescribed manner. The decoder exploits
this redundancy so as to reconstruct the original source sequence as accurately as possible. Thus, channel
coding makes it possible to carry out reliable communication over unreliable (noisy) channels. Channel
coding is also referred to as Error Control Coding. It is interesting to note here that the source coder reduces
improve reliability.
$ An Error Control Code for a channel, represented by the channel transition probability
matrix p(y|x), consists of:
(i) A message set {1, 2, … , M}.
(ii) An encoding function, X , which maps each message to a unique codeword, i.e., 1 Æ X (1) ,
n n
% A rate r is said to be achievable if there exists a coding scheme (n, k) such that the
maximal probability of error tends to 0 as n Æ . The (n, k) code may also be expressed as a (2nr, n) code
or a (M, n) code, where M = 2k = 2nr.
Let us now introduce the concept of time in our discussion. We wish to look at questions like
how many bits per second can we send over a given noisy channel with arbitrarily low bit error
rates? Suppose the discrete memoryless source has the source alphabet X and entropy H(X) bits
per source symbol. Let the source generate a symbol every Ts seconds. Then the average information rate of
H (X )
the source is bits per second. Let us assume that the channel can be used once every Tc seconds and
Ts
C
the capacity of the channel is C bits per channel use. Then the channel capacity per unit time is bits per
Tc
second. We now state Shannon’s second theorem known as the Noisy Channel Coding Theorem or simply
the Channel Coding Theorem.
The channel coding theorem is a very important result in information theory. The theorem
communication can be carried out over an unreliable (noisy) DMS channel. It should be noted
that the channel coding theorem tells us about the existence of some codes that can achieve
reliable communications in a noisy environment. Unfortunately, it does not give us the recipe to construct
these codes. Therefore, channel coding is still an active area of research as the search for better and better
Example 2.4 Consider a DMS source that emits equally likely binary symbols (p = 0.5) once
every Ts seconds. This entropy for this binary source is
H(p) = – p log2 p – (1 – p)log2(1 – p) = 1 bit
Channel Capacity and Coding ° 85
Example 2.5 Consider a binary symmetric channel (BSC) with a transition probability p = 10–2.
Such error rates are typical of wireless channels. We saw in Example 2.1 that for a BSC, the capacity is
given by
C = 1 + p log2 p + (1 – p)log2(1 – p)
By plugging in the value of p = 10–2 we obtain the channel capacity C = 0.919. From the previous
example we can conclude that there exists at least one coding scheme with the code rate r £ 0.919 which
will guarantee us a (non-zero) probability of error that is ‘as small as desired’. We mean it literally!
Example 2.6 Consider the repetition code in which each message bit is simply repeated n times,
where n is an odd integer. For example, for n = 3, we have the mapping scheme
0 Æ 000; 1 Æ 111
Similarly, for n = 5 we have the mapping scheme
0 Æ 00000; 1 Æ 11111
86 ° Information Theory, Coding and Cryptography
Note that the code rate of the repetition code with blocklength n is
1
r = (2.16)
n
The decoding strategy is as follows: If in a block of n received bits the number of 0’s exceeds the
number of 1’s, decide in favor of 0 and vice versa. This is also known as Majority Decoding. This also
answers the question why should n be an odd integer for repetition codes.
Let n = 2m + 1, where m is a positive integer. This decoding strategy will make an error if more than
m bits are in error, because in that case even if a 0 is encoded and sent, there will be more number of 1’s
in the received word. Let us assume that the a priori probabilities of 1 and 0 are equal. Then, the average
probability of error is given by
n
Ê nˆ
Pe = Â Á ˜ p i (1 - p ) n - i (2.17)
i = m +1 Ë i ¯
where p is the channel transition probability. The average probability of error for repetition codes for
different code rates is given in Table 2.2.
1 10–2
1/3 3 ¥ 10–4
1/5 10–6
1/7 4 ¥ 10–7
1/9 10–8
1/11 5 ¥ 10–10
probability of error. The decrease in the Pe is much more rapid than the decrease in the
code rate, ! "
and smaller Pe. Thus the repetition code exchanges code rate for message reliability. But
" arbitrarily
low probability of error. The theorem merely requires the code rate r to be less than the channel capacity,
# $ % r ª &'
# * + '
$ +& '& +&& '&&
information bits, …) and give us as small a Pe $ +&-20%/
1 # 3 4 5 3
6
Channel Capacity and Coding ° 87
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO 3:
1. Consider the binary channel shown in Fig. 2.11.
S
Let the a priori probabilities of sending the
binary symbol be p0 and p1, where p0 = p1 =
0.5. What is the maximum rate at which trans-
mission can be carried out over this channel
with arbitrarily low probability of error?
2. Consider a satellite hop channel shown in Fig. Fig. 2.11
M
2.12. The uplink can be modeled as a BSC with
crossover probability p while the downlink can be modeled as a BSC with crossover
probability q. Assuming the uplink channel and downlink channel are independent, draw
the capacity region for this satellite hop channel. Hint: Choose the two orthogonal axes as
r1 and r2 and mark a 2-D region where reliable communication is achievable.
Fig. 2.12
* A Gaussian Channel Zk
is a time discrete channel with output Yk,
at time k, which is the result of the sum
of the input Xk and the Gaussian noise Zk.
This noise is drawn from a Gaussian distribution with
mean zero and variance s 2. Thus, Yk = Xk + Zk, where Xk Yk
Zk ~ N(0, s 2). The noise Zk is independent of the input
Xk. The Gaussian Channel is shown in Fig. 2.13. Fig. 2.13 Gaussian channel.
7 3
!
that these random effects are independent and identically distributed and manifest
themselves as creating electrical disturbances in the communication circuit. Because of the
sum of these independent and identically distributed random effects is Gaussian from the central limit
theorem.
Consider a zero mean, stationary random process X(t) that is band limited to W hertz. Let Xk, k = 1, 2,..., K,
denote the continuous random variables obtained by uniform sampling of the process X(t) at the Nyquist rate
of 2W samples per second. These symbols are transmitted over a noisy channel which is also band-limited
to W Hertz. The channel output is corrupted by AWGN of zero mean and power spectral density (psd) N0/2.
Because of the channel, the noise is band limited to W Hertz. Let Yk, k = 1, 2,..., K, denote the samples of the
received signal. Therefore,
Yk = Xk + Nk, k = 1, 2, ..., K (2.18)
where Nk is the noise sample with zero mean and variance s2 =N0W. It is assumed that Yk, k = 1, 2,..., K, are
statistically independent. Since the transmitter is usually power-limited, let us put a constraint on the average
power in Xk:
E[ X k2 ] = P , k = 1, 2,..., K (2.19)
The information capacity of this band-limited, power-limited channel is the maximum of the mutual infor-
mation between the channel input Xk and the channel output Yk. The maximization has to be done over
all distributions on the input Xk that satisfy the power constraint of equation (2.19). Thus, the information
capacity of the channel (same as the channel capacity) is given by
C = max {I ( X ; Y ) | E[ X k2 ] = P} (2.20)
f Xk ( x)
1 Ê P ˆ
C= log 2 Á1 + bits per channel use (2.27)
2 Ë N 0W ˜¯
We are transmitting 2W samples per second, i.e., the channel is being used 2W times in one second.
Therefore, the information capacity can be expressed as
Ê P ˆ
C = W log 2 Á1+ bits per second (2.28)
Ë N 0W ˜¯
This basic formula for the capacity of the band-limited, AWGN waveform channel with a band-limited
# & KPQR ! & U
P
theorem, the Information Capacity Theorem. Since N 0W is the average noise power, SNR = .
Therefore, (2.28) can be succinctly expressed as C = W log (1 + SNR). N 0W
2
Example 2.7 Consider telephone channel with bandwidth 4 kHz and SNR ª 25 dB. Let us model
it as a band-limited and power-limited Gaussian channel.
SNR in dB is calculated as 10 log10(SNR). Hence, 25 dB SNR = 102.5 = 316.22.
The capacity of this channel is C = W log2(1 + SNR) = 4 × 103 log2(1 + 316.22) = 33,238 b/s.
If we increase the SNR by 1 dB (i.e., SNR ª 26 dB), the capacity increases to 34,563 b/s.
So, a 1 dB increase in SNR bought us roughly an additional 1325 b/s.
90 ° Information Theory, Coding and Cryptography
The ITU V.90 modem, that operates on the telephone line, provides a data rate of 33,600 b/s. Thus,
the ITU V.90 modem operates very close to the capacity of the channel! If the channel SNR is poor, a
lower data rate is used by the modem.
where P is the average transmitted power. This theorem is also called the &
The Information Capacity Theorem is one of the important results in information theory. In a
single formula one can see the trade off between the channel bandwidth, the average transmitted
power and the noise power spectral density. Given the channel bandwidth and the SNR the
channel capacity (bits/second) can be computed. This channel capacity is the fundamental limit
on the rate of reliable communication for a power-limited, band-limited Gaussian channel. It should be kept
in mind that in order to approach this limit, the transmitted signal must have statistical properties that are
Gaussian in nature. Note that the terms channel capacity and information capacity have been used
interchangeably.
Let us now derive the same result in a more intuitive manner. Suppose we have a coding scheme that
results in an acceptably low probability of error. Let this coding scheme take k information bits and encode
them into n bit long codewords. The total number of codewords is M = 2k. Let the average power per bit be
P. Thus the average power required to transmit an entire codeword is nP. Let these codewords be transmitted
2
over a Gaussian channel with the noise variance equal to s . The received vector of n bits is also Gaussian
2
with the mean equal to the transmitted codeword and the variance equal to ns . Since the code is a good one
2
(acceptable error rate), the vector lies inside a sphere of radius ns , centered on the transmitted codeword.
2 2
This sphere itself is contained in a larger sphere of radius n( P + s ) , where n( P + s ) is the average power
of the received vector.
This concept may be visualized as depicted in Fig. 2.14. There
is a large sphere of radius n( P + s 2 ) which contains M smaller
2
spheres of radius ns . Here M = 2k is the total number of
codewords. Each of these small spheres is centered on a codeword.
These are called the Decoding Spheres. Any received word lying
within a sphere is decoded as the codeword on which the sphere is
centered. Suppose a codeword is transmitted over a noisy channel.
Then there is a high probability that received vector will lie inside
the correct decoding sphere (since it is a reasonably good code). The
question arises: How many non-intersecting spheres can be packed
inside the large sphere? The more number of spheres one can pack,
Fig. 2.14 Visualization of the sphere
packing problem.
known as the Sphere Packing Problem.
Channel Capacity and Coding ° 91
The maximum number of non intersecting decoding spheres that can be packed inside the large sphere of
all possible received vectors is
( )
n/2
An Èn P + s 2 ˘ Ê Pˆ ( n / 2 )log 2 (1+ P / s 2 )
Î ˚ = Á1 + 2 ˜ = 2
M = (2.32)
n/2 Ë s ¯
An ÈÎns 2 ˘˚
1 Ê P ˆ
C= log 2 Á1 + 2 ˜ bits per channel use.
2 Ë s1 + s 22 ¯
Now, suppose Z2 is known to the receiver. In this case, the noise Z2 can be subtracted at the receiver,
thereby yielding the capacity
1 Ê Pˆ
C= log 2 Á1 + 2 ˜ bits per channel use.
2 Ë s1 ¯
1 Ê 4P ˆ
C= log 2 Á1 + 2 ˜ bits per channel use
2 Ë s1 + s 22 ¯
81
received signals
Y = aY1 + (1 – a)Y2
where 0 £ a £ 1. Thus we have
Y = a(X + Z1) + (1 – a)(X + Z2) = X + Z,
where Z = aZ1 + (1 – a)Z2. This is a Gaussian channel with received power = E[(X)2] = P. The total noise
power is given by
s 2 = a 2s12 + (1 - a ) s 22
2
ds 2
In order to maximize capacity, we must minimize the total noise power. Setting = 0 we obtain
da
s 22
a opt =
s12 + s 22
Channel Capacity and Coding ° 93
2 s12s 22
and the minimum total noise power s min = . Using this, we obtain the maximum capacity as
s12 + s 22
1 Ê P Pˆ
C¢ = log 2 Á1 + 2 + 2 ˜ bits per channel use
2 Ë s1 s 2 ¯
2 2
One can show that C ¢ ≥ C , with the condition for equality, s1 = s 2 . This implies that if the two
2 2
channels are not equally good ( s1 π s 2 ), one must use weighted combining in order to maximize
capacity.
In the previous example, equal power is transmitted over the two independent channels. In the case when
the channels are not equally good (or bad!), we do optimal combining. To do so, we need the Channel State
Information (CSI). Can we use the CSI at the transmitter to increase the capacity? We explore that exciting
option in the next section.
Yj = Xj + Zj (2.35)
2 X2 Y2
with Zi ~ N(0, s j ). The noise in each channel is assumed to be
independent. The total power constraint can be expressed as
k
E Â X 2j £ P (2.36) Zk
j =1
I ( X1 , X 2 ,… , X k ; Y1 , Y2 ,… , Yk )
Fig. 2.17 Parallel independent
C= max (2.37)
f ( x1 , x2 ,..., xk ), E [ X i2 ] £ P gaussian channels.
Since the uncertainty in the outputs {Y1 , Y2 ,… , Yk } , given the inputs { X1 , X 2 ,… , X k } , depends only on the
noise {Z1 , Z 2 ,… , Z k } , we can write
I ( X1 , X 2 ,… , X k ; Y1 , Y2 ,… , Yk )
= h (Y1 , Y2 ,… , Yk ) - h ( Z1 , Z 2 ,… , Z k | X1 , X 2 ,… , X k )
k
= h (Y1 , Y2 ,… , Yk ) - h ( Z1 , Z 2 ,… , Z k ) = h (Y1 , Y2 ,… , Yk ) - Â h ( Z i ) (2.39)
i =1
The last step follows from the assumption that the noise is independent of the input in the channel, and the
k
noise in each channel is independent. Using the fact that h (Y1 , Y2 ,… , Yk ) £ Â Yi , we have
i =1
I ( X1 , X 2 ,… , X k ; Y1 , Y2 ,… , Yk )
k k
£ Â h (Yi ) - Â h ( Zi )
i =1 i =1
k
1 Ê P ˆ
£ Â log Á1 + i2 ˜ (2.40)
i =1 2 Ë si ¯
k
2
where Pi = E[ X i ] and  Pi = P . For equality in the last step, Xi ~ N(0, Pi) for i = 1, 2, …, k. Maximizing
i =1
the power allocation in each channel in order to maximize the capacity, we obtain
Pi = (p - s i2 ) + such that
k
 (p - s i2 )+ = P (2.41)
i =1
+
Here, ( x)
Ï x if x ≥ 0
( x)+ = Ì (2.42)
Ó0 if x < 0
From (2.41), the optimal power allocation strategy can be visualized as follows. Channel
2
j can be assumed to be a solid block of height s j . All blocks (channels) are placed inside
a container, as shown in Fig. 2.18(a). We now pour water (power) into the container such
that the water level in the container rises to p, as depicted in Fig. 2.18(b). The water level
above each block (channel) indicates how much power is to be allocated to that channel. For
2 2
example, channel j with noise power s j gets (p – s j ) power allocated to it. Those blocks (channels) that
are above the water level p do not get any power allocated to them. Because of this physical analogy, this
algorithm is also known as the Water Filling or 0 1 2
Channel Capacity and Coding ° 95
(a) (b)
Channels Unused Power
channels allocation =p – s 2j
Level p
sk2 s k2
s 22 s 22
s12 2
sk–1 s12 2
sk–1
s j2 s 2j
Fig. 2.18
allocations.
Consider a Gaussian channel that is limited both in power and bandwidth. We wish to explore the limits of a
rate Rb which is equal to the capacity, C, of the channel, i.e., Rb = C. Suppose the energy per bit is Eb. Then
the average transmitted power is
P = EbRb = EbC (2.43)
Therefore, the channel capacity theorem for this ideal system can be written as:
C Ê E Cˆ
= log 2 Á1+ b ˜ (2.44)
W Ë N0 W ¯
This equation can be re-written in the following form:
Eb 2C W - 1
= (2.45)
N0 CW
Rb E
versus b is called the 3 4 5 , and
W N0
is given in Fig. 2.19. The ideal system is represented by the line Rb = C.
Eb
tends to the limiting value
N0
Eb
= ln 2 = 0.693 = – 1.6 dB (2.46)
N0 W
96 ° Information Theory, Coding and Cryptography
101
Rb/W
Shannon
Limit
100
10–1 Eb/N0
0 10 20 30 40 dB
Fig. 2.19
This value is called the Shannon Limit. It is interesting to note that the Shannon limit is a fraction. This
implies that for very large bandwidths, reliable communication is possible even for the case when the signal
power is less than the noise power! The channel capacity corresponding to this limiting value is
P
CW = log2e (2.47)
N0
"
(ii) The curve for the critical rate Rb = C is known as the Capacity Boundary. For the case Rb > C, reliable
communication is not guaranteed. However, for Rb < C, there exist some coding scheme which can
provide an arbitrarily low probability of error.
Rb Eb
# $ , and the
W N0
probability of error, Pe. Note that for designing any communication system the basic design parameters
are the bandwidth available, the SNR and the bit error rate (BER). The BER is determined by the
application and the quality of service (QoS) desired. The bandwidth and the power can be traded one
for the other to provide the desired BER.
% &
% " ' '*"
The information capacity theorem predicts the maximum amount of information that can be
transmitted through a given bandwidth for a given SNR. We see from Fig. 2.19 that acceptable
capacity can be achieved even for low SNRs, provided adequate bandwidth is available. We also
note that the capacity is a linear function of bandwidth and a logarithmic function of SNR. Thus the
optimum usage of a given bandwidth is obtained when the signals are noise-like (i.e., of large bandwidth) and
a minimal SNR is maintained at the receiver. This principle lies in the heart of any spread spectrum
communication system, like Code Division Multiple Access (CDMA). In the light of this theorem one can
justify why all the Third Generation (3G) mobile systems are CDMA based.
Channel Capacity and Coding ° 97
Let us model the MIMO channel described by (2.4) using the matrix H of dimension MR ¥ MT. Assuming the
average transmit symbol energy is Es, the sampled signal model can be expressed as
Es
y[k] = Hs[k] + n[k] (2.48)
MT
where y[k] is the received signal vector with dimension MR ¥ 1, s[k] is the transmit signal vector with
dimension MT ¥ 1 and n[k] is the MR ¥ 1 spatio-temporal zero mean, complex Gaussian white noise vector
with variance N0 in each dimension. This signal model is true for Frequency Flat Fading
channels. We can drop the time index k for clarity and write the above equation as
Es
y= Hs + n (2.49)
MT
The covariance matrix of s is given by
Rss = E{ssH} (2.50)
The superscript ‘H’ denotes the Hermitian operation. We make the assumptions that the channel, H,
is deterministic and known to the receiver. The Channel State Information (CSI) can be obtained at the
receiver using a pilot or training signals. The capacity of the MIMO channel is given by
Ê Es ˆ
C= max W log 2 det Á I M R + HRss H H ˜ bits per second (2.51)
Tr ( RSS )= M T Ë M N
T 0 ¯
where W is the bandwidth and I M R denotes the identity matrix of size MR. The condition Tr(Rss) = MT
constrains the total average energy transmitted over a symbol period.
If the channel is unknown to the transmitter, the vector s may be chosen such that Rss = I M T . This simply
means that the signals at the transmit antennas are independent and of equal power. The capacity of the
MIMO channel in this case is given by
r
Ê Es ˆ
C = W Â log 2 Á1 + li ˜ bits per second (2.52)
i =1 Ë M T N0 ¯
where r is the rank of the channel and li (i = 1, 2, …, r) are the positive eigenvalues of HHH. It is interesting
to observe that the capacity of the MIMO channel unknown to the transmitter comes out as the sum of r SISO
E
channels, each having power gain li (i = 1, 2, …, r) and equal transmit power, s . It can be interpreted as
MT
follows. The use of multiple transmit and receive antennas have opened multiple parallel data pipes between
the transmitter and receiver. The number of these scalar data pipes depends on the rank of H.
Next, consider a full-rank MIMO channel with MT = MR = M, so that r = M. The maximum capacity is
achieved when H is an orthogonal matrix, i.e., HHH = HHH. The capacity of this MIMO channel is given by
98 ° Information Theory, Coding and Cryptography
Ê E ˆ
C = WM log 2 Á1 + s ˜ bits per second (2.53)
Ë N0 ¯
The capacity of an orthogonal MIMO channel is simply M times the scalar channel capacity.
If the channel is known to the transmitter, the different scalar data pipes may be accessed
individually through processing at the transmitter and receiver. The basic idea is to allocate
variable energy across the different data pipes in order to maximize the mutual information. The
optimal energy can be found iteratively using the water pouring algorithm. The capacity of a
MIMO channel when the channel is known to the transmitter is necessarily greater than or equal to the
capacity when the channel is unknown to the transmitter.
INDUSTRIAL RELEVANCE
+ 0+ 1* 8 ¥ 2 ' '( # ,
4 ¥ 3 ' '( , + ' '(% -
! & 5
Multiple access channels are commonly found in the domain of cellular communications where several
mobile phone users try to access the same base station over a common channel. Similarly, a satellite receiver
with several independent ground weather stations constitutes a multiple access channel. We note that, in
addition to noise, there is interference generated by the multiple users (one user’s signal is someone else’s
interference!). In a classroom scenario, several students asking questions to the instructor at the same time
also tantamount to a multiple access channel. Clearly, if two students ask two different questions simultane-
of clever coding.
6 A discrete memoryless Multiple Access Channel with two senders and one receiver
can be characterized by three alphabets, X1, X2 and Y and a corresponding probability transition matrix
p(y| x1, x2).
Channel Capacity and Coding ° 99
Suppose, the rates of the two transmitters are r1 and r2 respectively. Let the two transmitters accessing the
common channel use two encoding functions, E1 and E2 in order to encode message sets M1 = 1, 2,… , 2 1{ nr
}
{ nr
}
and M2 = 1, 2,… , 2 2 into X1 and X2, i.e.,
E1: M1 Æ X1 and E2: M2 Æ X2 (2.54)
where n is the length of the encoded sequence Xi, i = 1, 2. The receiver needs to have a decoding function D
such that
D: Y Æ X1 ¥ X2 (2.55)
7 For a multiple access channel, a rate pair (r1, r2) is achievable if there exists codes
((2nr1 , 2nr2 ), n) such that the average probability of error Pe Æ 0.
For a multiple access channel, the Capacity Region is the closure of the set of achievable
rate pairs (r1, r2).
Example 2.10 Consider a multiple access channel with two independent senders and one receiver.
Suppose sender one has a binary symmetric channel with crossover probability p1, and sender two has
a binary symmetric channel with crossover probability p2. If the two channels are indeed independent,
then they experience no interference from each other (they could be using orthogonal frequencies). Thus,
sender one can send information at rate C1 = 1 – H(p1) and similarly, sender two can send information at
rate C2 = 1 – H(p2). The capacity region is shown in Fig. 2.20.
r1
1 – H( p1)
r2
1 – H( p1)
Fig. 2.20 The capacity region for independent binary symmetric channels.
100 ° Information Theory, Coding and Cryptography
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO 4:
1. A telephone channel has a bandwidth of 3000 Hz and the SNR = 20 dB. S
(i) Determine the channel capacity.
(ii) If the SNR is increased to 25 dB, determine the increased capacity.
2. Suppose a TV displays 30 frames/second. There are approximately 2 ¥ 105 pixels per M
frame, each pixel requiring 16 bits for color display. Assuming an SNR of 25 dB calculate
the bandwidth required to support the transmission of the TV video signal.
s2, the Gaussian random variable has the largest M
differential entropy attainable by any random variable.
1 2
(ii) Show that this entropy is given by log 2 (2p es ) .
2
4. Consider a channel consisting of two parallel AWGN channels with inputs X1, X2 and D
outputs
Y1 = X1 + Z1
Y2 = X2 + Z2
The noises Z1 and Z2 are independent and have variances s12 and s22 with s12 < s22.
However, we are constrained to use the same symbol on both channels, i.e. X1 = X2 = X,
where X is constrained to have power E[X 2] = P. Suppose at the receiver, we combine
the outputs to produce Y = Y1 + Y2 . What is the capacity C1 of channel with input X and
output Y ?
5. Consider two parallel channels with independent Gaussian noise Z1 and Z2 with variances D
s12 = 1 and s 22 = 2. The signal at the receiver is given by
Y1 = X1 + Z1
Y2 = X2 + Z2
2 2
The transmitter is subject to the power constraint E[ X1 + X 2 ] £ P.
Find and sketch the capacity C(P) of this channel as a function of P. What happens when
P becomes very small?
If you have successfully solved the above problems,
"
Since we are considering binary codes, cij is either a 0 or a 1. Let each bit of the codeword be mapped on
to a BPSK waveform so that the codeword may be represented as
n
si (t ) = Â sij p j (t ) , i = 1, 2, ...M (2.57)
i =1
where
ÏÔ E for cij = 1
sij = Ì (2.58)
ÔÓ - E for cij = 0
and E is the energy per code bit. The waveform si (t ) can then be represented as the n-dimensional vector
si = [ si1 si 2 ... sin ] , i = 1, 2, ...M (2.59)
We observe that this corresponds to a hypercube in the n-dimensional space. Let us now encode k bits of
information into an n bit long codeword, and map this codeword to one of the M waveforms. Note that there
are a total of 2k possible waveforms corresponding to the M = 2k different codewords.
Let the information rate into the encoder be R bits/sec. The encoder takes in k bits at a time and maps the
k-bit block to one of the M waveforms. Thus k = RT and M = 2k
D as follows:
n
D = dimensions/sec (2.60)
T
n = DT is the dimensionality of the space. The hypercube mentioned above has 2n = 2DT vertices. Of these,
we must choose M = 2RT to transmit the information. Under the constraint D > R, the fraction of vertices that
can be used as signal points is
2k 2 RT
F= = = 2- ( D - R )T (2.61)
2n 2 DT
For D > R, F Æ 0 as T . Since, n = DT, it implies that F Æ 0 as n . Designing a good coding
scheme translates to choosing M vertices out of the 2n vertices of the hypercube in such a manner that the
probability of error tends to zero as we increase n. We saw that the fraction F tends to zero as we choose
larger and larger n. This implies that it is possible to increase the minimum distance between these M signal
points as n . Increasing the minimum distance between the signal points would give us the probability
of error, Pe Æ 0.
There are (2n ) M distinct ways of choosing M out of the total 2n vertices. Each of these choices
corresponds to a coding scheme. For each set of M waveforms, it is possible to design a
communication system consisting of a modulator and a demodulator. Thus there are 2nM
communication systems, one for each choice of the M coded waveforms. Each of these
communication systems is characterized by its probability of error. Of course, many of these communication
systems will perform poorly in terms of the probability of error.
Let us pick one of the codes at random from the possible 2nM sets of codes. The random selection of this
mth codeword occurs with the probability
1
P({si }m ) = nM
(2.62)
2
Let the corresponding probability of error for this choice of code be Pe ({si }m ). Then the average proba-
bility of error over the ensemble of codes is
102 ° Information Theory, Coding and Cryptography
2nM 2nM
1
Pe = Â Pe ({si }m )P({si }m ) = 2nM Â Pe ({si }m ) (2.63)
m =1 m =1
We will next try to upper bound this average probability of error. If we have an upper bound on Pe , then
we can conclude that there exists at least one code for which this upper bound will also hold. Furthermore, if
Pe Æ 0 as n , we can surmise that Pe ({si }m ) Æ 0 as n .
Consider the transmission of a k-bit message X k = [ x1 x2 ...xk ] where xj is binary for j = 1,2,..., k. The
conditional probability of error averaged over all possible codes is
Pe ( X k ) = Â Pe ( X k ,{si }m )P({si }m ) (2.64)
all codes
where Pe ( X k ,{si }m ) is the conditional probability of error for a given k-bit message X k = [ x1 x2 ...xk ] , which
is transmitted using the code {si }m . For the mth code,
M
Pe ( X k ,{si }m ) £ Â P2 m ( sl , sk ) (2.65)
l =1
l πk
where, P2 m ( sl , sk ) is the probability of error for the binary communication system using signal vectors sl and
sk. to transmit one of two equally likely k-bit messages. Hence,
M
Pe ( X k ) £ Â Pe ({si }m )Â P2 m ( sl , sk ) (2.66)
all codes l =1
l πk
On changing the order of summation we obtain
M È ˘ M
Pe ( X k ) £ Â Í Â Pe ({si }m )P2 m ( sl , sk ) ˙ £ Â P2 ( sl , sk ) (2.67)
l =1 Î all codes ˚ l =1
l πk l πk
where P2 ( sl , sk ) represents the ensemble average of P2 m ( sl , sk ) over the 2nM codes. For additive white
Gaussian noise channel,
Ê d2 ˆ
P2 m ( sl , sk ) = Q Á lk
˜ (2.68)
ÁË 2 N 0 ˜¯
1 2
Under the assumption that all codes are equally probable, it is equally likely that the vector sl is any of the
2n vertices of the hypercube. Further, sl and sk are statistically independent. Hence, the probability that sl and
sk differ in exactly d places is
n
Ê 1 ˆ Ê nˆ
P(d ) = Á ˜ Á ˜ (2.71)
Ë 2¯ Ë d ¯
The expected value of P2 m ( sl , sk ) over the ensemble of codes is then given by
n Ê 2dE ˆ Ê 1 ˆ n Ê n ˆ Ê 2dE ˆ
P2 ( sl , sk ) =  P ( d )Q Á N ˜ = ÁË n ˜¯  ÁË d ˜¯ Q Á N ˜
Ë
(2.72)
d =0 0 ¯ 2 d =0 Ë 0 ¯
Recall that we need an upper bound on Pe , the average error probability. To obtain Pe we average Pe ( X k )
over all possible k-bit information sequences. Thus,
n n
È Ê -E ˆ ˘ È Ê -E ˆ ˘
1 1
Pe = Â Pe ( X k )P ( X k ) < M Í Á 1 + e N0 ˜ ˙ Â k
P ( X ) < M Í Á 1 + e N0 ˙
˜ (2.76)
Í2 Á ˜¯ ˙ Í 2 Á ˜¯ ˙
k
Î Ë ˚ k
Î Ë ˚
Ê -E ˆ
2
R0 = log 2 -E
= 1 - log 2 Á1 + e N0 ˜ (2.77)
ÁË ˜¯
N0
1+ e
The cutoff rate has the units of bits/dimension. Observe that 0 £ R0 £ 1 . The plot of R0 with respect to
SNR per dimension is given in Fig. 2.21.
104 ° Information Theory, Coding and Cryptography
0.9
0.8
0.7
0.6
R0 0.5
0.4
0.3
0.2
0.1
0
–10 –5 0 5 10
E/N0 (dB)
Fig. 2.21 Cutoff rate, R0, versus the SNR (in dB) per dimension.
Observe that
R R RT k
= = = = Rc (2.81)
D n /T n n
Here Rc represents the code rate. Hence the average error probability can be written in the following
instructive form
Pe < 2- n ( R0 - Rc ) (2.82)
From the above equation, we can conclude the following:
(i) For Rc < R0 the average probability of error Pe Æ 0 as n . Since by choosing large
values of n, Pe can be made arbitrarily small, there exist good codes in the ensemble (which
have the probability of error less than Pe ).
(ii) We observe the fact that Pe is the ensemble average. Therefore, if a code is selected at random, the
probability that its error Pe > a Pe is less than 1/a. This implies that there are no more than 10% of the
codes that have an error probability that exceeds 10 Pe . Thus, there are many good codes.
Channel Capacity and Coding ° 105
(iii) The codes whose probability of error exceed Pe are not always bad codes. The probability of error of
these codes may be reduced by increasing the dimensionality, n.
E
For binary coded signals, the cutoff rate, R0, saturates at 1 bit/dimension for large values of , say
N0
E
> 10 . Thus, to achieve lower probabilities of error one must reduce the code rate, Rc. Alternately, very
N0
large block lengths have to be used.
at high SNRs. For high SNR scenarios, non-binary coded signal sets should be used to achieve an increase
in the number of bits per dimension. Multiple-amplitude coded signal sets can be easily constructed from
non-binary codes by mapping each code element into one of the possible amplitude levels (e.g. PAM). For
random codes using M-ary multi-amplitude signals, it was shown by Shannon (in 1959) that
È 2˘ È Ê 2 ˆ˘
1Í E Ê Eˆ ˙ 1 Í 1Á Ê Eˆ ˙
R0* = 1+ - 1+ Á log 2 e + log 2 1+ 1+ Á ˜ (2.83)
2 Í N0 Ë N 0 ˜¯ ˙ 2 Í2 Á Ë N 0 ˜¯ ˜ ˙
ÍÎ ˙˚ ÍÎ Ë ¯ ˙˚
*
Let us now relate the cutoff rate R0 to the capacity of the AWGN channel, which is given by
Ê P ˆ
C = W log 2 Á1+ bits per second (2.84)
Ë N 0W ˜¯
where P is the average power and W is the channel bandwidth. The energy per code bit is equal to
PT
E= (2.85)
n
Recall that from the sampling theorem, a signal of bandwidth W may be represented by samples taken
at a rate 2W. Thus, in the time interval of length T there are n = 2WT samples. Therefore we may write
n
D = = 2W . Hence,
T
nE
P= = DE (2.86)
T
C C
Cn = = and substitute for W and P in (2.84) to obtain
2W D
Ê 1ˆ Ê Eˆ
Cn = Á ˜ log 2 Á1 + 2 ˜
Ë 2¯ Ë N0 ¯
Ê 1ˆ
= Á ˜ log 2 (1 + 2 Rcg b ) (2.87)
Ë 2¯
*
where g b is the SNR per bit and Rc is the code rate. The normalized capacity, Cn and cutoff rate, R0 , are
!
* E
(i) R0 < Cn for all values of . This is expected because Cn is the ultimate limit on the
N0
transmission rate R/D.
106 ° Information Theory, Coding and Cryptography
E *
(ii) For smaller values of , the difference between Cn and R0 is approximately 3 dB. This means that
N0 *
randomly selected, average power limited, multi-amplitude signals yield R0 within 3 dB of channel
capacity.
2.5
1.5
R0* and C n
1 Cn
R *0
0.5
0
–10 –5 0 5 10
E/N0 (dB)
*
Fig. 2.22 The normalized capacity, Cn and cutoff rate, R0 , for an AWGN channel.
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO 5:
( )
1. For a BSC, the cut-off rate is given by R0 = 1 - log 2 1 + 4 p (1 - p ) where p is the
S
crossover probability of the BSC.
(i) For what value of p is the cut-off rate minimum? What does it physically mean?
(ii) Plot the cut-off rate as a function of p.
2. Consider a communication system using antipodal signaling. The SNR is 20 dB. D
(i) Find the cutoff rate, R0.
(ii) We want to design a code which results in an average probability of error, Pe < 10-6.
What is the best code rate I can achieve?
(iii) What will be the dimensionality, n, of this code?
(iv) Repeat the earlier parts (i), (ii) and (iii) for an SNR = 5dB. Compare the results.
LEARNING OUTCOMES
!Y The conditional probability P (yi | xj) is called the channel transition probability and is denoted by pji.
The conditional probabilities {P (yi | xj)} that characterize a DMC can be arranged in the matrix form
P = [pji]. P is known as the probability transition matrix for the channel.
!Y
information in any single use of the channel, where the maximization is overall possible input
probabilities. That is,
q -1 r -1 P( yi | x j )
C = max I ( X ; Y ) = max   P( x j ) P( yi | x j ) log
P( x j ) P( x j )
j =0 i =0 P( yi )
Y The basic objective of channel coding is to increase the resistance of the digital communication system
to channel noise. This is done by adding redundancies in the transmitted data stream in a controlled
manner. Channel coding is also referred to as error control coding.
k
!Y The ratio, r = , is called the code rate. Code rate of any coding scheme is always less than unity.
n
Y A rate r is said to be achievable if there exists a coding scheme (n, k) such that the maximal probability
of error tends to 0 as n Æ . The (n, k) code may also be expressed as a (2nr, n) code or a (M, n) code,
where M = 2k = 2nr. All rates below capacity, C, are achievable.
!Y A Gaussian Channel is a time discrete channel with output Yk, at time k, which is the result of the sum
of the input Xk and the Gaussian noise Zk. This noise is drawn from a Gaussian distribution with mean
zero and variance s2.
!Y Let a DMS with an alphabet X have entropy H (X ) and produce symbols every Ts seconds. Let a
H (X ) C
DMC have capacity C and be used once every Tc seconds. Then, if £ , there exists a coding
Ts Tc
scheme for which the source output can be transmitted over the noisy channel and be reconstructed
108 ° Information Theory, Coding and Cryptography
with an arbitrarily low probability of error. This is the Channel Coding Theorem or the Noisy Coding
Theorem.
H (X ) C
Y For > , it is not possible to transmit information over the channel and reconstruct it with an
Ts Tc
arbitrarily small probability of error. The parameter is called the Critical Rate.
Ê P ˆ
!Y The information capacity of a SISO channel can be expressed as C = W log 2 Á 1+ bits per
Ë N 0W ˜¯
second. This is the basic formula for the capacity of the band-limited, AWGN waveform channel with
a band-limited and average power-limited input. This is the crux of the Information Capacity Theorem.
This theorem is also called the Channel Capacity Theorem.
!Y ! " #
Ê Es ˆ
C= max W log 2 det Á I M R + HRss H H ˜ bits per second
Tr(RSS )= M T Ë M T N0 ¯
where W is the bandwidth. The condition Tr(Rss) = MT constrains the total average energy transmitted
over a symbol period. Here the assumption is that the channel is known to the receiver.
Y If the channel is unknown to the transmitter, the capacity of the MIMO channel is given by
r
Ê Es ˆ
C = W Â log 2 Á1 + li ˜ bits per second
i =1 Ë M T N0 ¯
where r is the rank of the channel and li (i = 1, 2, …, r) are the positive eigen values of HHH.
!Y If the channel is known to the transmitter, the different scalar data pipes may be accessed individually
through processing at the transmitter and receiver. The optimal energy for each data pipe is found
iteratively using the water pouring algorithm.
Ê -E ˆ
2
!Y The cutoff rate R0 is given by R0 = log 2
-E
= 1 - log 2 Á1 + e N0 ˜ . The cutoff rate has the units of
ÁË ˜¯
N0
1+ e
bits/dimension. Note that 0 £ R0 £ 1. The average error probability in terms of the cutoff rate can be
- n ( R0 - Rc )
written as Pe < 2 . For Rc < R0 the average probability of error Pe Æ 0 as n .
2.1 The random and unpredictable electric signals from natural causes, both internal and external to the
system is ___________.
(a) Interference (b) Attenuation (c) Distortion (d) Noise
2.2 In an ideal channel, the crossover probability, p, is
(a) 1 (b) 0 (c) 0.5 (d) None of these
2.3 Relay Channels can use
(a) Amplify-and-Forward (AF) scheme
(b) Decode-and-Forward (DF) scheme
(c) Hybrid of AF and DF
(d) All of these
2.4 The Direct-to-Home (DTH) satellite channel is an example of
(a) Multiple access channel (b) Broadcast channel
(c) MIMO channel (d) None of these
2.5 The units of channel capacity is ‘bits per channel use’ provided the base of the logarithm is
(a) 10 (b) 2 (c) e (d) None of these
2.6 For a BSC with 0.5 < p < 1, the capacity
(a) increases with increasing p (b) decreases with increasing p
(c) increases with decreasing p (d) None of these
2.7 Channel capacity is a measure of
(a) Entropy
(b) Lower-bound on the maximum rate of information transfer
(c) The maximum rate at which information can be reliably transmitted over a channel.
(d) None of these
2.8 The capacity of a binary symmetric channel, given H(p) is the binary entropy function, is
(a) 1 – H(p) (b) H(p) – 1 (c) 1 – H(p)2 (d) H(p)
2.9 For M equally likely messages, the average amount of information H (in bits) is
(a) log10M (b) log2M (c) log10M 2 (d) M log10M
2.10 The capacity of Gaussian channel is
(a) C = 2W log2 (1 + SNR) bits/s (b) C = W log10(1 + SNR) bits/s
(c) C = W log2 (1 + SNR) bits/s (d) C = W(1 + SNR) bits/s
For interactive quiz with answers, scan the QR code given here
Or
Visit [Link]
110 ° Information Theory, Coding and Cryptography
2.1 Explain the difference between hard decision decoding and soft decision decoding.
2.2 Explain what is meant by a composite Discrete-input, Discrete-output channel.
2.3 What is a Multiple Input Multiple Output (MIMO) channel?
2.4 Why is the capacity of a BSC equal to zero for p = 0.5?
2.5 Suppose I have two parallel independent BSCs with crossover probabilities p and q. If I choose to send
two bits each time over these parallel channels, what will be my capacity?
2.6 List three properties of channel capacity.
2.7 What is the need for channel coding?
2.8 What is meant by achievability of a rate?
$%& ' %
2.10 What are the assumptions made in the Information Capacity Theorem?
2.11 Explain intuitively the Water Filling algorithm.
$%:$ @ Q U X
2.13 Explain why should the capacity of a MIMO channel, with the channel is known to the transmitter, be
necessarily greater than or equal to the capacity when the channel is unknown to the transmitter?
2.14 Explain what is meant by the Capacity Region for a multiple access channel?
2.15 What is the physical interpretation of the Cutoff Rate?
PROBLEMS
M 2.1 Consider the channels A, B and the cascaded channel AB shown in Fig. 2.23.
(i) Find CA the capacity of channel A.
(ii) Find CB the capacity of channel B.
(iii) Next, cascade the two channels and determine the combined capacity CAB.
(iv) Explain the relation between CA, CB and CAB.
Fig. 2.23
Channel Capacity and Coding ° 111
S 2.2 Consider a miniature keyboard with small keys. Whenever we intend to press any key, the two
adjacent keys also have equal probability of getting pressed. This is like a noisy keyboard. The
equivalent channel is depicted in Fig. 2.24. Find the capacity of this noisy channel with overlapping
outputs.
Fig. 2.24
M 2.3 Determine the channel capacity of the channel shown in Fig. 2.25.
Fig. 2.27
112 ° Information Theory, Coding and Cryptography
(i) For a given set of powers P0, . . . , Pn, what is the capacity of C of the multihop communication
system from node 0 to node n? Express your answer in terms of Ci .
(ii) Explain your answer in terms of the end-to-end data rate R.
D 2.6 Consider two binary symmetric channels with crossover probability p £ 1/2 operating in parallel
as shown in the Fig. 2.28. Here, for i Œ {1, 2}, the i th channel has input Xi, noise Zi and output
Yi = Xi ≈ Zi where Xi, Yi, Zi Œ {0, 1} and where ≈ denotes modulo-two addition. The noise in the
two channels is not independent and the noise pair (Z1, Z2) has the joint distribution PZ , Z ("1, "2)
1 2
given according to the following table, in which a is a parameter satisfying 0 £ a £ p.
X1 Y1 = X1 ≈ Z1
z2 = 0 z2 = 1
p–a Z1
z1 = 0 1 + a – 2p
z1 = 1 p–a a Z2
X2 Y2 = X2 ≈ Z2
Fig. 2.28
BSC Y1
BSC Y2
Fig. 2.29
Channel Capacity and Coding ° 113
(i) First consider only a single BSC. Let the input probability PX(0) be equal to q. Determine the
capacity of this single BSC.
(ii) Next consider diversity, with two independent BSCs. Assuming PX ~ ~%Z I (X; Y1, Y2).
M 2.9 Consider the discrete memoryless channel (Fig. 2.30) with source X = {0, 1} and an independent
on-off jammer, Z, such that P(Z = 0) = P(Z = a) = 0.5. Find the capacity of this channel.
D 2.10 Consider the multiplier channel, shown in Fig. 2.31, with Y = XZ, where the source X = {0, 1}. The
independent binary noise Z = {0, 1} is Bernoulli distributed, i.e., P(Z = 0) = 1 – a, and P(Z = 1) = a.
Find the capacity of this channel.
M 2.11 Next, reconsider the multiplier channel of Prob. 2.10 with the added advantage that the receiver
can observe Z, as depicted in Fig. 2.32. Find the capacity of this channel.
1–p
0 0
p
p
1 1
1–p
1
2 2
D 2.12 Consider a miltary scenario, where we have two independent BSCs at our disposal, with capacities
C1 and C2. In order to have an element of surprise for the enemy, sometimes BSC1 is used, and
sometimes BSC2 is used, but not both simultaneously. Find the capacity of this ‘surprise channel’.
Generalize the result if we had the luxury of K independent channels.
S 2.13 Calculate the capacity of the ternary channel given in Fig. 2.33.
S 2.14 Consider the fading channel, shown in Fig. 2.34, where V is a random variable representing
fading and Z is the additive noise. Both V and Z are independent. Suppose we have the luxury of
channel estimation, i.e., we know V. Show that the capacity with channel state information (CSI)
is necessarily greater than without CSI, i.e., I(X; Y | V) ≥ I(X; Y).
Fig. 2.34
S 2.15 Consider a binary erasure multiple access channel with two senders transmitting either a 1 or a 0.
The receiver computes Y = X1 + X2. Draw the capacity region for the binary erasure multiple access
channel.
114 ° Information Theory, Coding and Cryptography
S 2.16 Consider a binary orthogonal broadcast channel with two independent receivers. The channel
between the transmitter and receivers one and two can be modeled as a BSCs with crossover
probabilities p1 and p2 respectively. Draw the capacity region for this orthogonal broadcast channel.
COMPUTER PROBLEMS
2.1 Write a computer program that takes in the channel transition probability matrix and computes the
capacity of the channel.
$%$ # \ M-PSK, M = 2, 4, 8, 16 and 32, and
the probabilities of error: (a) Pe = 10-6 and (b) Pe = 10-8.
2.3 Write a program that implements the binary repetition code of rate 1/n, where n is an odd integer.
Develop a decoder for the repetition code. Test the performance of this coding scheme over a BSC
with the channel transition probability, p. Generalize the program for a repetition code of rate 1/n over
GF (q). Plot the residual Bit Error Rate (BER) versus p and q (make a 3-D mesh plot).
2.4 Write a program that can generate Capacity versus SNR plots for MT transmit antennas and MR receive
antennas.
(i) Generate plots for the combinations (MT, MR) = (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (3, 1).
(ii) Compare the capacity of a MISO and a SIMO channel. Comment.
(iii) If we have a total number of 4 antennas, which is the best solution: (1, 3), (2, 2) or (3, 1)? Justify.
PROJECT IDEAS
2.1 Cascade of Channels: Consider a system in which information is transmitted through a series of noisy
channels, with no processing allowed between successive channels. We wish to analyze a cascade of
channels.
(i) Given a set of n channels, how should the channels be ordered so as to give maximum overall
capacity?
(ii) How big a difference does ordering make? That is, what is the maximum difference between best
and worst or best and average performance?
(iii) What channels will have higher capacity when cascaded with themselves n times?
(iv) Express the channel transition probability matrix as P = QLQ-1, where Q is the matrix of eigen-
vectors of P and L is the diagonal matrix of eigenvalues. Now, the n-cascade will have the transition
n
probability matrix Pn with eigenvalues li . Relate the channel capacity of the n-cascade with |li|.
2.2 Image Transmission over Binary Channels: We wish to study how a degraded image looks after
passing through binary channels. Start with a binary image (black and white image) of your choice.
(i) Assume that this image is transmitted through a BSC with p = 10-2. Compare it with the original
image. Repeat with p = 10-1.
(ii) Assume that this image is transmitted through a Z-channel with p = 10-2. Compare it with the
original image. Repeat with p = 10-1.
Channel Capacity and Coding ° 115
(iii) Use the repetition code (n = 3) for error correction and then show the improvement in the above
two cases.
(iv) Repeat (i) and (ii) for a cascade of two channels.
2.3 Time Varying Binary Channels
(i) Suppose the crossover probability, p, of a BSC is time varying, and is distributed uniformly over
(p1, p2), i.e., p ~ U(p1, p2), p1 < p2. Find the capacity of this time varying BSC.
(ii) Use simulations to plot the capacity versus p1 for p2 = 0.5. Can you intuitively explain this plot?
(iii) Next, consider a Z channel with p ~ U(p1, p2), p1 < p2. Find the capacity of this time varying Z
channel.
2.4 Channel Model for Long Term Evolution (LTE)
When a wireless signal travels from a transmitter to a receiver it follows multiple paths. When these
copies of the same signal arrive at the receiver they are delayed and attenuated. A well-known technique
\ ^! ^ ! % \
channel thus performs the convolution operation on the transmitted signal. Suppose, the pedestrian
channel in 4G-LTE standard can be modeled using the following tap-delay line model.
Tap 1 2 3 4 5 6 7
Relative power (dB) 0.0 –1.0 –2.0 –3.0 –8.0 –17.2 –20.8
Q U %
(ii) What will the received signal look like if we transmit a pulse with pulsewidth (a) 10 ns, (b) 50 ns.
(iii) Assuming QPSK modulation, plot the BER vs. SNR curve for this channel. What role will the
symbol-rate play?
@ # %
1. Cover, Thomas M., and Joy A., Thomas. Elements of information theory, John Wiley & Sons, 2012.
2. Robert, Ash B., Information Theory. Dover Special Priced Titles, 2007.
PART - II
Error Control Coding (Channel Coding)
Chapter 3 Linear Block Codes for Error Correction
Chapter 4 Cyclic Codes
Chapter 5 Bose–Chaudhuri Hocquenghem (BCH) Codes
Chapter 6 Space–Time Codes
CHAPTER THREE
learning objectives
that will remain standing even through an earthquake, their computer counterparts have come up with
sophisticated techniques capable of counteracting the digital manifestations of Murphy’s Law (‘If anything
can go wrong, it will go’). Error correcting codes are a kind of safety net – the mathematical insurance
against the vagaries of an imperfect material world.
Error correcting codes, as the name suggests, are used for correcting errors when messages are trans-
mitted over a noisy channel or stored data is retrieved. The physical medium through which the messages
are transmitted is called a channel (e.g., a telephone line, a satellite link, a wireless channel used for mobile
120 ° Information Theory, Coding and Cryptography
communications etc.). Different kinds of channels are prone to different kinds of noise, which corrupt the data
being transmitted. The noise could be caused by lightning, human errors, equipment malfunctioning, voltage
surges, random motions of electrons in the receiver hardware, and so on. Because these error correcting codes
try to overcome the detrimental effects of noise in the channel, the encoding procedure is also called channel
coding. Error control codes are also used for accurate storage of information, for example storing data and
reading it from a compact disc (CD). In this case, the error could be due to a scratch on the surface of the
CD. The error correcting coding scheme will try to recover the original data from the corrupted one. The
motivation for the study of error control coding comes from the fact that nowadays a large volume of data is
being communicated daily and there exists an ever increasing need to communicate, store and retrieve data
with greater reliability.
The basic idea behind error correcting codes is to add a certain amount of redundancy to the message
prior to its transmission through the noisy channel. This redundancy, which basically consists of some extra
symbols, is added in a known manner. The encoded message, when transmitted through the channel, might
get corrupted due to noise in the channel. At the receiver, the original message can be recovered from the
corrupted one if the number of errors is within the limit for which the coding strategy has been designed. By
adding redundancy intelligently we can succeed in ‘fooling’ the random noise to some extent and diluting
its effect. The block diagram of a digital communication system is illustrated in Fig. 3.1. Note that the most
Example 3.1 Let us see how redundancy can help combat the effects of noise. The normal
language that we use to communicate (say, English) has a lot of redundancy built in it already. Consider
the following sentence (which may be thought of as being corrupted by noise – maybe the moths have
eaten portions of a written text!):
"# $%& '* +/ 0" +"$'/$"# /24 $
As we can see, there are lots of errors in this sentence. However, due to the familiarity with the language
we may probably guess that the original text would have looked something like:
+"# $%& '* +/ 0" +"$&'&/$+"# /24 & $
We have just now used an error correcting strategy that makes use of the in-built redundancy in the
English language to construct the original message from the corrupted one.
Information Channel
Modulator
Source Encoder
C
H
A
N Noise
N
E
L
User of Channel
Demodulator
Information Decoder
Fig. 3.1 Block diagram (and the principle) of a digital communication system. Here the source
coder/decoder block has not been shown.
Linear Block Codes for Error Correction ° 121
In this chapter
! " # " # #
! $ % 1.
& $ ' # ( # # !
% 2.
( ) # !
# * !! + #, # +, !
#! $ ! ! -+( ! % 3.
/ # ! ( #
! ! % 4.
+ = 8
used here as well as in the later chapters. LO 1
Understand the basics of
A word is a sequence of symbols. error control coding and the
process of encoding linear
block codes.
A code is a set of vectors called
The Hamming weight of a codeword (or any vector) is equal to the number of
non-zero elements in the codeword. The Hamming weight of a codeword c is denoted by w(c). The
Hamming distance between two codewords is the number of places by which the codewords differ.
The Hamming distance between two codewords c1 and c2 is denoted by d(c1, c2). It is easy to see that
d(c1, c2) = w (c1 – c2).
122 ° Information Theory, Coding and Cryptography
It is easy to show that the Hamming distance follows the three properties of a distance metric which are
as follows:
(i) d(c1, c2) ≥ 0 with equality if and only if c = c
(ii) d(c1, c2) = d(c2, c1).
(iii) d(c1, c2) ≥ d(c1, c3) + d(c2, c3). This is the triangle inequality.
Example 3.2 Consider a code C = {0100, 1111} which consists of two codewords i.e., 0100
and 1111. The Hamming weight w(0100) = 1 and w(1111) is 4. The Hamming distance between the two
codewords is 3 because they differ at the 1st, 3rd and 4th places. Observe that w(0100 – 1111) = w(1011)
= 3 = d(0100, 1111).
Example 3.3 For the code C = {01234, 43210}, the Hamming weight of each codeword is 4
and the Hamming distance between the codewords is 4 (because only the 3rd component of the two
codewords are identical while they differ at 4 places).
A block code
codewords is called the block length and is typically denoted by n. Thus, a code of block length n consists
of a set of codewords having n components.
Example 3.4 The code C = {00000, 10100, 11110, 11001} is a block code of block length equal
to 5. This code can be used to represent two-bit binary numbers which are as follows:
Here M = 4, k = 2 and n = 5. Suppose we have to transmit a sequence of 1’s and 0’s using the above
coding scheme. Let us say that the sequence to be encoded is 1 0 0 1 0 1 0 0 1 1.…
Code rate is always less than unity (code rate equal to one implies no coding at all!). The smaller the code
rate, the greater is the redundancy within the code, i.e., number of redundant symbols present per information
symbol is more in a codeword. A code with greater redundancy has the potential to detect and correct greater
number of symbols in error, as we shall soon see. However, a smaller code rate reduces the actual rate of
transmission of information.
INDUSTRIAL RELEVANCE
0 1 23% & % & !! 455 467
8 769 1 : # ;
The minimum distance of a code is the minimum Hamming distance between any two
codewords. If the code C consists of the set of codewords {ci, i = 0, 1 ... M – 1} then the minimum distance
of the code is given by d* = min d(ci, cj), i π j. An (n, k) code with minimum distance d* is sometimes
denoted by (n, k, d*).
The minimum weight of a code is the smallest weight of any non-zero codeword, and
is denoted by w*.
Note that if the sum of two codewords is another codeword, the difference of two codewords will also yield
a valid codeword. For example, if c1, c2 and c3 are valid codewords such that c + c = c then c – c = c .
Hence, it is obvious that the all-zero codeword must always be a valid codeword for a linear block code (self-
subtraction of a codeword).
124 ° Information Theory, Coding and Cryptography
For a linear code the minimum distance is equal to the minimum weight of the code, i.e.,
d* = w*.
Intuitive Proof: The distance dij between any two codewords ci and cj is simply the weight of the codeword
formed by ci – cj. Since the code is linear, the difference of two codewords results in another valid codeword.
" " " #$ " " "
Example 3.5 The code C = {0000, 1010, 0101, 1111} is a linear block code of block length
n = 4. This is a (4, 2) code. Observe that all the ten possible sums of the codewords
0000 + 0000 = 0000,0000 + 1010 = 1010,
0000 + 0101 = 0101,
0000 + 1111 = 1111,1010 + 1010 = 0000,
1010 + 0101 = 1111,
1010 + 1111 = 0101,0101 + 0101 = 0000,
0101 + 1111 = 1010 and
1111 + 1111 = 0000
are in C and the all-zero codeword is in C. The minimum distance of this code is d* = 2. In order to verify
the minimum distance of this linear code we can determine the distance between all pairs of codewords
Ê 4ˆ
(which is Á ˜ = 6 in number):
Ë 2¯
d(0000, 1010) = 2, d(0000, 0101) = 2, d(0000, 1111) = 4
d(1010, 0101) = 4, d(1010, 1111) = 2, d(0101, 1111) = 2
We observe that the minimum distance of this code is indeed 2.
Note that the code given in Example 3.4 is not linear because 1010 + 1111 = 0101 is not a valid codeword.
Even though the all-zero word is a valid codeword, it does not guarantee linearity. The presence of an
Example 3.6 Consider the simple parity-check codes. Given k information bits, they add one
additional parity bit so that the weight of the codeword is even. Clearly, the rate of the parity-check codes
Ê k ˆ Ê n - 1ˆ
is r = Á
Ë k + 1˜¯ ÁË n ˜¯
= , which tends to unity as n becomes very large (i.e., for large blocklengths). For
k = 4, we have
Information word Codeword
0000 00000
0001 00011
0010 00101
0011 00110
… …
… …
1111 11110
Linear Block Codes for Error Correction ° 125
The minimum weight w*= 2 (see for example the 2nd codeword). Hence d* = 2. It can detect one
error and cannot correct a single error. Thus, simple parity-check codes have good rates, but poor error
correcting capability.
In order to make the error correcting codes easier to use, understand and analyse, it is helpful to impose
some basic algebraic structure on them. As we shall soon see, it will be useful to have an alphabet in which
it is easy to carry out the basic mathematical operations such as addition, subtraction, multiplication and
division.
Example 3.7 Consider GF(4) with 4 elements {0, 1, 2, 3}. The addition and multiplication
tables for GF(4) are
126 ° Information Theory, Coding and Cryptography
+ 0 · 0
0 0 1 2 3 0 0 0 0 0
1 0 3 2 0 1 2 3
2 3 0 1 0 2 3 1
3 2 1 0 0 3 1 2
Each element has an additive inverse and a multiplicative inverse other than 0. It should be noted here
that the addition in GF(4) is not modulo 4 addition.
+ 0
0 0 1 2 3 4 5
1 2 3 4 5 0
2 3 4 5 0 1
3 4 5 0 1 2
4 5 0 1 2 3
5 0 1 2 3 4
· 0
0 0 0 0 0 0 0
0 1 2 3 4 5
0 2 4 0 2 4
0 3 0 3 0 3
0 4 2 0 4 2
0 5 4 3 2 1
See, for example, elements 2, 3 or 4 do not have multiplicative inverse. Hence, it is not a Field.
/ GF(qn), which is a set of n-tuples of elements from GF(q). Linear block codes
can be looked upon as a set of n-tuples (vectors of length n) over GF(q) such that the sum of two codewords
' ' "
code is a subspace of GF(qn).
Let S be a set of vectors of length n " GF(q). The set of all linear
combinations of the vectors of S is called the linear span of S and is denoted by <S>. The linear span is thus
a subspace of GF(qn), generated by S.
Given any subset S of GF(qn), it is possible to obtain a linear code C = <S> generated by S, consisting of
precisely the following codewords:
(i) All-zero word,
(ii) All words in S,
(iii) All linear combinations of two or more words in S.
Linear Block Codes for Error Correction ° 127
Example 3.9 Let S = {1100, 0100, 0011}. All possible linear combinations of S are
1100 + 0100 = 1000, 1100 + 0011 = 1111, 0100 + 0011 = 0111, 1100 + 0100 + 0011 = 1011.
Therefore, C = < S > = {0000, 1100, 0100, 0011, 1000, 1111, 0111, 1011}. The minimum distance of
this code is w(0100) = 1.
Example 3.10 Let S 7 89; ;9< GF(3). The addition and multiplication tables of
GF(3) = {0, 1, 2} are given by:
+ 0 1 2 0 1 2
0 0 1 2 0 0 0 0
1 1 2 0 1 0 1 2
2 2 0 1 2 0 2 1
È1 0 1 ˘ È1 0 1 ˘
c = [0 0] Í ˙ = [0 0 0], c = [0 1] Í ˙ = [0 1 0]
Î0 1 0 ˚ Î0 1 0 ˚
È1 0 1 ˘ È1 0 1 ˘
c = [1 0] Í ˙ = [1 0 1], c = [1 1] Í ˙ = [1 1 1]
Î0 1 0 ˚ Î0 1 0 ˚
Therefore, this generator matrix generates the code C = {000, 010, 101, 111}. We observe that this is a
(3, 2) code from the fact that the dimension of the generator matrix is 3 ¥ 2. The code rate r = 2/3.
Two q-ary codes are called equivalent if one can be obtained from the other by one or
both operations listed in the following:
(i) Permutation of the components.
(ii) Permutation of the position of the codeword.
Suppose a code containing M codewords are displayed in the form of an M ¥ n matrix, where the rows
represent the codewords, then operation (i) corresponds to the re-labelling of the symbols appearing in a
given column, and operation (ii) represents the rearrangements of the columns of the matrix.
Example 3.12 Consider the ternary code (a code whose components Œ {0, 1, 2}) of blocklength 3
Ï2 0 1
Ô
C = Ì1 2 0
Ô0 1 2
Ó
If we apply the permutation 0 Æ 2 , 2 Æ 1, 1 Æ 0 to column 2 and 1 Æ 2, 0 Æ 1, 2 Æ 0 to column
3 we obtain
Ï2 2 2
Ô
C = Ì1 1 1
Ô0 0 0
Ó
The code C is equivalent to a repetition code of length 3. Note that the original code is not linear, but
is equivalent to a linear code.
Linear Block Codes for Error Correction ° 129
Two linear q-ary codes are called equivalent if one can be obtained from the other by
one or both operations listed below:
(i) multiplication of the components by a non-zero scalar
(ii) permutation of the position of the codeword.
J K M 99 '
Two k ¥ n matrices generate equivalent linear (n, k) codes over GF(q) if one matrix can be
obtained from the other by a sequence of the following operations:
(i) Permutation of rows
(ii) Multiplication of a row by a non-scalar
(iii) Addition of a scalar multiple of one row to another
(iv) Permutation of columns
(v) Multiplication of any column by a non-zero scalar.
Proof: R
rows of the generator matrix. The operations merely modify the basis. The last two operations (which are
column operations) convert the matrix to one which will produce an equivalent code.
A generator matrix can be reduced to its Systematic Form (also called the standard form of
the generator matrix) of the type G = [ I | P] where I is a k ¥ k identity matrix and P is a k ¥ (n – k) matrix,
called the Parity Matrix.
Proof: The k rows of any generator matrix (of size k ¥ n) are linearly independent. Hence, by performing
elementary row operations and column permutations it is possible to obtain an equivalent generator matrix in
a row echelon form. This matrix will be of the form [I | P].
Example 3.13 Consider the generator matrix of a (4, 3) code over GF(3):
È0 1 2 1 ˘
Í ˙
G = Í1 0 1 0 ˙
ÍÎ1 2 2 1 ˙˚
Let us represent the ith row by ri and the jth column by rj. Upon replacing r3 by r3 – r1 – r2 we get (note
that in GF(3), –1 = 2 and –2 = 1 because 1 + 2 = 0, see table in Example 3.10)
È0 1 2 1 ˘
Í ˙
G = Í1 0 1 0 ˙
ÍÎ0 1 2 0˙˚
Next we replace r1 by r1 – r3 to obtain
È0 0 0 1 ˘
Í ˙
G = Í1 0 1 0 ˙
ÍÎ0 1 2 0˙˚
130 ° Information Theory, Coding and Cryptography
Finally, shifting c4 Æ c1, c1 Æ c2, c2 Æ c3 and c3 Æ c4 we obtain the standard form of the generator
matrix
È1 0 0 0 ˘ È1 0 0 0 ˘
Í ˙ Í ˙
G = Í0 1 0 1 ˙ = Í0 1 0 1 ˙ = [I | P]
ÍÎ0 0 1 2˙˚ ÍÎ0 0 1 2˙˚
V R " -
X "
Codewords are obtained simply by multiplying the input vector (uncoded word) by the generator matrix.
Is it possible to detect a valid codeword using a similar concept? The answer is yes, and such a matrix is
called the parity check matrix, H, for the given code. For a parity check matrix,
cHT = 0 (3.3)
where c is a valid codeword. Since c = iG, therefore, iGHT = 0. For this to hold true for all valid codewords,
we must have
GHT = 0 (3.4)
The size of the parity check matrix is (n – k) ¥ n. A parity check matrix provides a simple method of
detecting whether an error has occurred or not. If the multiplication of the received word (at the receiver) with
the transpose of H yields a non-zero vector, it implies that an error has occurred. This methodology, however,
will fail if the errors in the transmitted codeword exceeds the number of errors for which the coding scheme
> #$ cHT might help us not only to detect but also
to correct the errors under some conditions.
Suppose the generator matrix is represented in its systematic form G = [ I | P]. The matrix P is also called
the ' " *
H = [ – PT | I ] (3.5)
where PT represents the transpose of matrix P. This is because
È- P ˘
GHT = [ I | P] Í ˙ = 0 (3.6)
Î I ˚
Since the choice of a generator matrix is not unique for a code, the parity check matrix will not be unique.
Given a generator matrix G, we can determine the corresponding parity check matrix and vice-versa. Thus
the parity check matrix H can be used to specify the code completely.
Let us make the following interesting observation. Since a linear code, C, is a subspace of
GF(qn), it must have an orthogonal complement C ^. Since this orthogonal complement is a
subspace of GF(qn), it can also be used as a code. We call C ^ the dual of the code C. The
orthogonal complement C ^ has dimension n – k and these n – k basis vectors form the rows of
H. The orthogonality is obvious from (3.4). A code that is equal to its dual code is called a self-dual code. It
can also be observed from (3.6) that for a self-dual code, P must be a square matrix with PPT = I. It is also
obvious that (C ^) ^ = C.
Linear Block Codes for Error Correction ° 131
From (3.3) we observe that the vector c must have 1’s in such positions that the corresponding rows of HT
add up to the zero vector, 0. Now, we know that the number of 1’s in a codeword pertains to its Hamming
weight. Hence, the minimum distance d* of a linear block code is given by the minimum number of rows of
HT (or, the columns of H) whose sum is equal to the zero vector. This is true for binary linear block codes. For
the non-binary case, the columns of H, weighted by the codewords have to be considered. Thus it is easy to
determine the minimum weight of a code from the H matrix: The minimum weight of a code is w* if every
set of w*– 1 columns of H are linearly independent.
Example 3.14 For a (7, 4) linear block code the generator matrix is given by
È1 0 0 0 1 0 1˘
Í0 1 0 0 1 1 1 ˙˙
G=Í
Í0 0 1 0 0 1 0˙
Í ˙
Î0 0 0 1 0 1 0˚
È1 0 1˘
Í1 È1 1 0 0 ˘
1 1 ˙˙ Í ˙
the matrix P is given by Í and PT is given by Í0 1 1 1 ˙ . Observing the fact that – 1 = 1 for
Í0 1 0˙
Í ˙ ÍÎ1 1 0 0˙˚
Î0 1 0˚
the case of binary, we can write the parity check matrix as
H = [ – PT | I ]
È1 1 0 0 1 0 0 ˘
Í ˙
= Í0 1 1 1 0 1 0 ˙
ÍÎ1 1 0 0 0 0 1 ˙˚
Note that the columns 1, 5 and 7 of the parity check matrix, H, add up to the zero vector. Hence, for this
code, d* = 3.
The code C contains a non-zero codeword of Hamming weight w or less if and only if a
linearly dependent set of w columns of H exist.
Proof: Consider a codeword c Œ C. Let the weight of c be w which implies that there are w non-zero compo-
nents and (n – w) zero components in c. If we throw away the w zero components, then from the relation
CHT = 0 we can conclude that w columns of H are linearly dependent.
Conversely, if H has w linearly dependent columns, then a linear combination of most w columns is zero.
These w #$ w CHT = 0.
Example 3.15 The following is a (5, 2) systematic code over GF(3) with code rate r = 2/5.
Note that the total number of codewords is 3k = 32 = 9. Each codeword begins with the information
symbols, and has three parity symbols at the end. The parity symbols for the information word 01 are 121
in the above table. A generator matrix in the systematic form (standard form) will generate a systematic
code.
The minimum distance (minimum weight) of an (n, k) linear code is bounded as follows.
d* £ n – k + 1 (3.7)
This is known as the singleton bound. This holds for both binary and non-binary linear block
codes.
Proof: We can reduce all linear block codes to their equivalent systematic forms. A systematic code can have
one information symbol and (n – k) parity symbols. At most all the parity symbols can be non-zero, resulting
in the total weight of the codeword to be (n – k) + 1. Thus the weight of no codeword can exceed n – k + 1.
It should be pointed out that (3.7) gives only a bound on d*. It should not be used to determine the actual
" " " " " "
Having familiarised ourselves with the concept of minimum distance of a linear code, we shall now
explore how this minimum distance is related to the total number of errors the code can detect and possibly
correct. So we move over to the receiver’s end and take a look at the methods of decoding a linear block code.
Linear Block Codes for Error Correction ° 133
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO1:
È1 1 1 1 0 0 0 ˘
Í ˙
1. Consider the generator matrix G = Í0 1 1 0 1 0 1 ˙ . S
È1 1 0 1 0 0 0˘
Í0 1 1 0 1 0 0˙˙
4. Using the (7, 4) Hamming code given by G = Í encode the input S
Í0 0 1 1 0 1 0˙
message vectors m1 = 1111 and m2 = 1010. Í0 ˙
Î 0 0 1 1 0 1˚
È1 1 0 1 0 0 0˘ È1 1 0 1 0 0 0˘
Í0 1 1 0 1 0 0˙˙ Í0 1 1 0 1 0 0˙˙
5. Consider G = Í and G = Í . Are the two M
Í0 0 1 1 0 1 0˙ Í1 1 1 0 0 1 0˙
Í ˙ Í ˙
Î0 0 0 1 1 0 1˚ Î1 0 1 0 0 0 1˚
generator matrices G and G equivalent?
$ # - "- !
S Simple: Level 1 and Level 2 Category
M Medium: Level 3 and Level 4 Category
D "- 1 Level 5 and Level 6 Category
134 ° Information Theory, Coding and Cryptography
Example 3.16 For the code C = {000, 111} the minimum distance is 3. Therefore, error patterns
of weight 2 or 1 can be detected. This means that any error pattern belonging to the set {011, 101, 110,
001, 010, 100} will be detected by this code.
Next consider the code C = {001, 110, 101} with d * = 1. Nothing can be said regarding how many errors
this code can detect because d * – 1 = 0. However, the error pattern 010 of weight 1 can be detected by this
code. But it cannot detect all error patterns with weight one, e.g., the error vector 100 cannot be detected.
Next, let us look at the problem of error correction. The objective is to make the best possible guess
regarding the originally transmitted codeword after observing the received word. What could be a smart
decoding strategy? Since only one of the valid codewords must have been transmitted it is logical to conclude
that a valid codeword nearest (in terms of Hamming distance) to the received word must have been actually
transmitted. In other words, the codeword which resembles the received word most is assumed to be the
one that was sent. This strategy is called the Nearest Neighbour decoding, as we are picking the codeword
nearest to the received word in terms of the Hamming distance.
It may be possible that more than one codeword is at the same Hamming distance from the received word.
In that case the receiver can do one of the following:
(i) It can pick one of the equally distant neighbours randomly, or
(ii) Request the transmitter to re-transmit.
To ensure that the received word (that has at most t errors) is closest to the original codeword, and farther
from all other codewords, we must put the following condition on the minimum distance of the code
d * ≥ 2t + 1 (3.8)
Graphically, the condition for correcting t errors or less can be visualised from Fig. 3.2. Consider the
space of all q-ary n-tuples. Every q-ary vector of length n can be represented as a point in this space. Every
codeword can thus be depicted as a point in this space, and all words at a Hamming distance of t or less would
Linear Block Codes for Error Correction ° 135
lie within the sphere centred at the codeword and with a radius of t. If the minimum distance of the code is
d *, and the condition d * ≥ 2t + 1 holds good, then none of these spheres would intersect. Any received vector
R
any other codeword. We will call the spheres associated with each codeword its Decoding Sphere. Hence it
is possible to decode the received vector using the ‘nearest neighbour’ method without ambiguity.
Fig. 3.2 Words within the sphere of radius t and centred at c1 will be decoded as c1. For unambiguous
decoding, d * ≥ 2t + 1.
The condition d * ≥ 2t + 1 takes care of the worst case scenario. It may be possible, however, that the above
condition is not met but still it is feasible to correct t errors as is illustrated in the following example.
Example 3.17 Let consider the code C = {00000, 01010, 10101, 11111}. The minimum distance
d * = 2. Suppose the codeword 11111 was transmitted and the received word is 11110, i.e., t = 1 (one
" J
d(11110, 00000) = 4, d(11110, 01010) = 2
d(11110, 10101) = 3, d(11110, 11111) = 1
Using the nearest neighbour decoding we can conclude that 11111 was transmitted. Even though a single
error correction (t = 1) was done in this case, d * < 2t + 1 = 3. So, for certain scenarios, it is possible
to correct errors even when d* < 2t + 1. However, in many cases a single error correction may not be
possible with this code. For example, if 00000 was sent and 01000 was received,
d(01000, 00000) = 1, d(01000, 01010) = 1
d(01000, 10101) = 4, d(01000, 11111) = 4
& #
An incomplete decoder decodes only those received codewords that are clearly
closest to one of the codewords. In case of ambiguity, the decoder declares that the received word is
unrecognisable. The receiver is then requested to re-transmit. A complete decoder decodes every received
word, i.e., it tries to map every received word to some codeword, even if it has to make a guess.
Example 3.17 was that of a complete decoder. Such decoders may be used when it is better to have a good
guess rather than to have no guess at all. Many of the real life decoders are incomplete decoders. Usually they
send a message back to the transmitter requesting them to re-transmit.
Example 3.18 The International Standard Book Number (ISBN) is a linear block code of block
length n = 10 over GF(11). The symbols used are 0, 1, 2, …, 9, X. Instead of using the symbol ‘10’ ,
136 ° Information Theory, Coding and Cryptography
‘X’ is used in order to avoid confusion between ‘10’ and the case when ‘1’ is followed by a ‘0’, The ISBN
*
9
 (10 - i)ci = 0 calculated (mod 11) (3.9)
i =0
For example, consider the ISBN 0-07-048297-7. If we perform the check on this ISBN we get:
10 ¥ 0 + 9 ¥ 0 + 8 ¥ 7 + 7 ¥ 0 + 6 ¥ 4 + 5 ¥ 8 + 4 ¥ 2 + 3 ¥ 9 + 2 ¥ 7 + 1 ¥ 7 = 176 = 0 (mod 11)
Thus 0-07-048297-7 is a valid ISBN.
Since ISBN is a linear block code, the all-zero codeword is a valid codeword. Also, 1000000001 is a
valid ISBN. Thus the minimum weight of the code is d * = 2. Theoretically, it cannot correct any errors
and can detect a single error. However, suppose one of the digits of the ISBN gets smudged and we have
0-07-048e97-7. We can recover the erroneous digit, e, by solving (10 ¥ 0 + 9 ¥ 0 + 8 ¥ 7 + 7 ¥ 0 + 6 ¥
4 + 5 ¥ 8 + 4 ¥ e + 3 ¥ 9 + 2 ¥ 7 + 1 ¥ 7) mod 11 = 0. The solution of this equation with one unknown
yields e = 2. Thus, we have been able to correct a single error simply because we know the location of
the error digit.
INDUSTRIAL RELEVANCE
1( & ) ! # #
A receiver declares that an erasure has occurred (i.e., a received symbol has been erased)
when the symbol is received ambiguously, or the presence of an interference is detected during reception.
Example 3.19 Consider a binary pulse amplitude modulation (PAM) scheme where one is
represented by 5 volts and zero is represented by 0 volts. The noise margin is 1 volt, which implies that
at the receiver:
if the received voltage is between 4 volts and 5 volts fi the bit sent is 1,
if the received voltage is between 0 volt and 1 volts fi the bit sent is 0,
if the received voltage is between 1 volt and 4 volts fi an erasure has occurred.
Thus if the receiver received 2.9 volts during a bit interval, it will declare that an erasure has occurred.
A channel can be prone both to errors and erasures. If in such a channel t errors and r erasures occur, the
error correcting scheme should be able to compensate for the erasures and correct the errors as well. If r
erasures occur, the minimum distance of the code will become d * – r in the worst case. This is because, the
erased symbols have to be simply discarded, and if they were contributing to the minimum distance, this
distance will reduce. A simple example will illustrate the point. Consider the repetition code in which
0 Æ 00000
1 Æ 11111
*
Here d = 5. If r 7 ; '
0 Æ ??000
1 Æ ??111
Linear Block Codes for Error Correction ° 137
Let C be an (n, k) code over GF(q) and a be any vector of length n. Then the set
a + C = {a + x | x Œ C} (3.13)
is called a coset (or translate) of C. a and b are said to be in the same coset if (a – b) Œ C.
The vector having the minimum weight in a coset is called the coset leader. If there
are more than one vector with the minimum weight, one of them is chosen at random and is declared the
coset leader.
Example 3.20 Let C be the binary (3, 2) code with the generator matrix given by
È1 0 1 ˘
G= Í ˙
Î0 1 0 ˚
i.e., C = {000, 010, 101, 111}. The cosets of C are
000 + C = 000, 010, 101, 111,
001 + C = 001, 011, 100, 110.
Note that all the eight vectors have been covered by these two cosets. As we have already seen (in the
above theorem), if a + C is a coset of C and b Œ a + C, we have b + C = a + C. Hence all cosets have
been listed. For the sake of illustration we write down the following
010 + C = 010, 000, 111, 101,
011 + C = 011, 001, 110, 101,
100 + C = 100, 110, 001, 011,
101 + C = 101, 111, 000, 101,
110 + C = 110, 100, 011, 001,
111 + C = 111, 101, 010, 000.
It can be seen that all these sets are already covered.
Since two cosets are either disjoint or coincide (from Theorem 3.6), the set of all vectors, GF(q)n can
be written as
GF(q)n = C » (a1 + C ) » (a2 + C ) » » (at + C )
Where t = qn-k –1.
A standard array for an (n, k) code C is a qn-k ¥ qk array of all vectors in GF(q n) in
C (with 0 on the extreme left), and the other rows are the cosets
ai + C, each arranged in corresponding order, with the coset leader on the left.
Example 3.21 Consider the code C = {0000, 1011, 0101, 1110}. The corresponding standard
array is
Codewords Æ 0000 1011 0101 1110
1000 0011 1101 0110
0100 1111 0001 1010
0010 1001 0111 1100
≠
coset leader
Note that each entry is the sum of the codeword and its coset leader.
Let us now look at the concept of decoding (obtaining the information symbols from the received
codewords) using the standard array. Since the standard array comprises all possible words belonging to
GF(qn ' " ' &
received word is a valid codeword, it is concluded that no errors have occurred (this conclusion may be wrong
' ' "
to noise!). In the case when the received word, v, does not belong to the set of valid codewords, we surmise
that an error has occurred. The decoder then declares that the coset leader is the error vector, e, and decodes
the codeword as v – e. This is the codeword at the top of the column containing v. Thus, mechanically, we
decode the codeword as the one on the top of the column containing the received word.
Example 3.22 Suppose the code in the previous example C = {0000, 1011, 0101, 1110} is used
and the received word is v = 1101. Since it is not one of the valid codewords, we deduce that an error has
occurred. Next we try to estimate which one of the four possible codewords was actually transmitted. If
" ' " 999 Mrd column. The
topmost entry of this column is 0101. Hence the estimated codeword is 0101. Observe that:
d(1101, 0000) = 3, d(1101, 1011) = 2,
d(1101, 0101) = 1, d(1101, 1110) = 2
and the error vector e = 1000, the coset leader.
Codes with larger blocklengths are desirable (though not always; see the concluding remarks on this
chapter) because the code rates of larger codes perform closer to the Shannon limit. As we go to larger codes
(with larger values of k and n) the method of standard array will become less practical because the size of the
standard array (qn-k ¥ qk) will become unmanageably large. One of the basic objectives of coding theory is
& # "
scheme should be realisable both in terms of memory required as well as the computational load. Is it possible
to reduce the standard array? The answer lies in the concept of syndrome decoding, which we are going to
discuss next.
140 ° Information Theory, Coding and Cryptography
Suppose H is a parity check matrix of an (n, k) code. Then for any vector v Œ GF(q)n,
the vector
s = vHT (3.14)
is called the syndrome of v. The syndrome of v is sometimes explicitly written as s(v). It is called a
syndrome because it gives us the symptoms of the error, thereby helping us to diagnose the error. The size
of the s vector is 1 ¥ (n – k).
Two vectors x and y are in the same coset of C if and only if they have the same syndrome.
Proof: The vectors x and y belong to the same coset ¤ x + C = y + C
¤ x–yŒC
¤ (x – y)HT = 0
¤ xHT = yHT
¤ s(x) = s(y)
Thus there is a one-to-one correspondence between cosets and syndromes.
We can reduce the size of the standard array by simply listing the syndromes and the corresponding coset
leaders.
Example 3.23 We now extend the standard array listed in Example 3.21 by adding the syndrome
column.
The code is C = {0000, 1011, 0101, 1110}. The corresponding standard array is
Syndrome
Codewords – – – Æ 0000 1011 0101 1111 00
1000 0011 1101 0110 11
0100 1111 0001 1010 01
0010 1001 0111 1100 10
≠
Coset leader
The probability of error (or, the word error rate) Perr for any decoding scheme is the
probability that the decoder output is a wrong codeword. It is also called the Residual Error Rate.
Suppose there are M codewords (of length n) which are used with equal probability. Let the decoding be
done using a standard array. Let the number of coset leaders with weight i be denoted by ai. We assume that
the channel is a binary symmetric channel (BSC) with symbol error probability p. A decoding error occurs if
the error vector e is not a coset leader. Therefore, the probability of correct decoding will be
n
Pcor = Â a i p i (1 - p ) n -1 (3.15)
i =0
Hence, the probability of error will be
n
Perr = 1 - Â a i p i (1 - p ) n -1 (3.16)
i =0
Let us now consider m errors within the block length of n bits. We have seen that for a linear block code
Í1 * ˙
( )
with minimum distance d*, any number of errors up to Í d - 1 ˙ are always correctable. The probability of
Î 2 ˚
m errors in a block of n bits is
Ê nˆ
Pm, n = Á ˜ p m (1 - p ) n - m (3.17)
Ë m¯
where p is the probability of one bit in error. The codeword will be in error if more than t errors occur. Thus,
the probability of a codeword error is upper-bounded by
n
PM £ Â Pm, n (3.18)
m = t +1
The equality holds for the case of 2 & , which we shall study shortly. We also note that PM
cannot be less than the probability of erroneously decoding a transmitted codeword as another codeword
which is at a distance d *. That is
d* Ê d*ˆ m
PM ≥ Â Á ˜ p (1 - p )
d* -m
(3.19)
m = Íd * / 2˙ +1 Ë m ¯
Î ˚
We can obtain an upper-bound if we consider all the M – 1 other codewords. All these codewords are at a
distance of at least d *. Therefore, the union bound can be expressed as
d* Ê d*ˆ m
PM £ ( M - 1) Â Á ˜ p (1 - p )
d* -m
(3.20)
m = Íd * / 2˙ +1 Ë m ¯
Î ˚
142 ° Information Theory, Coding and Cryptography
Example 3.24 Consider the standard array in Example 3.21. The coset leaders are 0000, 1000,
0100 and 0010. Therefore a0 = 1 (only one coset leader with weight equal to zero), a1 = 3 (the remaining
three are of weight one) and all other ai = 0.
Therefore,
Perr = 1 – [(1 – p)4 + 3p(1 – p)3]
Recall that this code has four codewords, and can be used to send 2 bits at a time. If we did not perform
coding, the probability of error of the 2-bit message being received incorrectly would be
Perr = 1 – Pcor = 1 – (1 – p)2
Note that for p = 0.01, the word error rate (upon coding) is Perr = 0.0103, while for the uncoded case
Perr = 0.0199. So coding has almost halved the word error rate. The comparison of Perr for messages with
and without coding is plotted in Fig. 3.3. It can be seen that coding outperforms the uncoded case only for
p < 0.5 (guess why?). Note that the improvement due to coding comes at the cost of information transfer
rate. In this example, the rate of information transfer has been cut down by half as we are sending two
parity bits for every two information bits.
1
0.8
0.6
Without coding
Perr
0.4
With coding
0.2
0
0 0.2 0.4 0.6 0.8 1
p
Fig. 3.3 Comparison of Perr for coded and uncoded 2 bit messages.
Example 3.25 This example will help us visualise the power of coding. Consider a binary
symmetric channel with the probability of symbol error p = 10-7. Suppose 10 bit long words are being
transmitted without coding. Let the bit rate of the transmitter be 107 b/s, which implies that 106 words/s
are being sent. The probability that a word is received incorrectly is
Ê10ˆ 9 Ê10ˆ 8 2 Ê 10ˆ 7 3 Ê10ˆ 9
ÁË 1 ˜¯ (1 - p ) p + ÁË 2 ˜¯ (1 - p ) p + ÁË 3 ˜¯ (1 - p ) p + ... ª ÁË 1 ˜¯ (1 - p ) p ª10 words/s
-6
Therefore, in one second, 10-6 ¥ 106 = 1 word will be in error! The implication is that every second a
word will be in error and it will not be detected.
Next, let us add a bit of parity to the uncoded words so as to make them 11 bits long. The parity makes
all the codewords of even and thus ensures that a single bit in error will be detected. The only way that
Linear Block Codes for Error Correction ° 143
"
be computed as 1 – probability that less than two bits are in error. Therefore, the probability of word
error will be
Ê11ˆ
1 - (1 - p )11 - Á ˜ (1 - p )10 p ª 1 – (1 – 11p) – 11(1 – 10p)p = 110p2 = 11 ¥ 10–13
Ë 1¯
The new word rate will be 107/11 words/s because now 11 bits constitute one word and the bit rate is the
same as before. Thus in one second, (107/11) ¥ (11 ¥ 10–13) = 10–6 words will be in error. This implies
that, after coding, one word will be received incorrectly without detection every 106 seconds = 11.5 days!
So just by increasing the word length from 10 bits (coded) to 11 bits (with coding), we have been able to
obtain a dramatic decrease in the word error rate. For the second case, each time a word is detected to be
in error, we can request the transmitter to re-transmit the word. This strategy for retransmission is called
the Automatic Repeat Request (ARQ).
INDUSTRIAL RELEVANCE
&0 % ! ( 0&0< 58== 0>? 1 *
/ ) # */ > + !!
If we have a linear block (n, k, d * ) code we can either use it for error correction or for error detection
(typically combined with ARQ). Suppose we have a single error correcting code (d * = 3) and two errors occur
in the received word, then the syndrome in this case will be non-zero, indicating the presence of 1 or 2 errors.
However, it cannot tell whether it is a single error or a double error. At this stage, two mutually exclusive
actions can be taken. One strategy is to use the code as an error detecting tool and request for retransmission.
In this case we do not attempt to correct the error. The other (mutually exclusive) possibility is to assume that
to correct a single error might introduce a third error. Thus, the word after error correction may actually
contain three errors. If we try to calculate the syndrome for this wrongly ‘corrected’ word, the syndrome may
turn out to be zero! This is because the code can only detect up to two errors.
It is important to ask the following question: How much energy is saved because of channel coding?
The probability of error (Pe) curve versus the
100
Eb/N0 of a typical communication system is plotted in
It should be pointed out that after deploying an error control code, the energy per bit goes down
by a factor of the code rate. If Eb is the energy per bit for an uncoded system, the effective energy
per bit after error control coding will be Ec = (code rate) ¥ Eb. This is true for all LBCs.
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO2:
È1 1 0 1 0 0 0˘
Í0 1 1 0 1 0 0˙˙
1. Find the parity check matrix for the generator matrix G = Í . S
Í1 1 1 0 0 1 0˙
Give two realisations of the parity check matrix. Í ˙
Î1 0 1 0 0 0 1˚
2. Consider a (15, 11) LBC with S
È1 0 1 0 1 0 1 0 1 0 1 0 1 0 1˘
Í0 1 1 0 0 1 1 0 0 1 1 0 0 1 1˙˙
H= Í
Í0 0 0 1 1 1 1 0 0 0 0 1 1 1 1˙
Í ˙
Î0 0 0 0 0 0 0 1 1 1 1 1 1 1 1˚
(i) How many errors can it detect?
(ii) How many errors can it correct?
(iii) How many errors can it detect in the presence of r erasures?
3. Consider a (7, 1) repetition code. Let the raw error rate be p = 0.01. What is the probability M
of error after coding, i.e., the residual error rate? Can we apply this repetition code for a
video transfer application over wireless requiring a BER = 10-7 ?
È1 1 0 1 0 0 0 ˘
Í0 1 1 0 1 0 0 ˙
4. Consider a (7, 4) code with G = Í ˙ S
Í0 0 1 1 0 1 0 ˙
Í ˙
Î0 0 0 1 1 0 1 ˚
Determine whether the following received words are valid codewords:
(i) 0001101
(ii) 0110100
(iii) 1110000
(iv) 1111111
If you have successfully solved the above problems,
! " # $% & ' "- .
correctly decoded. If, however, larger than t errors occur, it will escape the sphere, thus resulting in an
incorrect decoding.
c2
t cM
t
c1 c3
t t
Fig. 3.5 The concept of spheres in GF(qn). The codewords of the code with d*(C) ≥ 2t + 1 are the centres of
these non-overlapping spheres.
Ê nˆ Ê nˆ Ê nˆ 2 Ê nˆ r
ÁË 0˜¯ + ÁË 1˜¯ (q - 1) + ÁË 2˜¯ (q - 1) + ... + ÁË r ˜¯ (q - 1) (3.21)
vectors.
Proof: Consider a vector u in GF(q n) and another vector v which is at a distance m from u. This implies that
the vectors u and v differ at exactly m places. The total number of ways in which m position can be chosen
Ê nˆ
from n positions is Á ˜ . Now, each of these m places can be replaced by (q – 1) possible symbols. This is
Ë m¯
because the total size of the alphabet is q, out of which one is currently being used in that particular position
in u. Hence, the number of vectors at a distance exactly m from u is
Ê nˆ Ê nˆ Ê nˆ 2 Ê nˆ r
ÁË 0˜¯ + ÁË 1˜¯ (q - 1) + ÁË 2˜¯ (q - 1) + ... + ÁË r ˜¯ (q - 1) (3.22)
146 ° Information Theory, Coding and Cryptography
Example 3.26 Consider a binary code (i.e., q = 2) and blocklength n = 4. The number of vectors
at a distance 2 or less from any codeword will be
Ê 4ˆ Ê 4ˆ Ê 4ˆ 2
ÁË 0˜¯ + ÁË 1˜¯ (1) + ÁË 2˜¯ (1) = 1 + 4 + 6 = 11
ÏÊ nˆ Ê nˆ Ê nˆ Ê nˆ ¸
M ÌÁ ˜ + Á ˜ (q - 1) + Á ˜ (q - 1) 2 + ... + Á ˜ (q - 1)t ˝ £ q n (3.23)
ÔÓË 0¯ Ë 1¯ Ë 2¯ Ë t¯ Ô˛
Proof: Suppose C is a q-ary (n, k) code. Consider spheres of radius t centred on the M codewords. Each
sphere of radius t has
Ê nˆ Ê nˆ Ê nˆ 2 Ê nˆ t
ÁË 0˜¯ + ÁË 1˜¯ (q - 1) + ÁË 2˜¯ (q - 1) + ... + ÁË t ˜¯ (q - 1)
vectors (Theorem 3.8). Since none of the spheres intersect, the total number of vectors for the M disjoint
ÏÊ nˆ Ê nˆ Ê nˆ 2 Ê nˆ t¸
spheres is M ÌÁ ˜ + Á ˜ (q - 1) + Á ˜ (q - 1) + ... + Á ˜ (q - 1) ˝ which is upper bounded by qn, the total
ÓÔË 0 ¯ Ë 1 ¯ Ë 2¯ Ë t ¯ ˛Ô
number of vectors of length n in GF(q)n.
This bound is called the Hamming Bound or the Sphere Packing Bound and it holds good for nonlinear
codes as well. For binary codes, the Hamming bound will become
ÏÊ nˆ Ê nˆ Ê nˆ Ê nˆ ¸
M ÌÁ ˜ + Á ˜ + Á ˜ + ... + Á ˜ ˝ £ 2n (3.24)
ÔÓË 0¯ Ë 1¯ Ë 2¯ Ë t ¯ Ô˛
ÏÊ nˆ Ê nˆ Ê nˆ Ê nˆ ¸
log q ÌÁ ˜ + Á ˜ (q - 1) + Á ˜ (q - 1) 2 + ... + Á ˜ (q - 1)t ˝ £ n - k (3.25)
ÓÔË 0¯ Ë 1¯ Ë 2¯ Ë t¯ ˛Ô
Linear Block Codes for Error Correction ° 147
For a perfect code there are equal radius disjoint spheres centred at the codewords which
!$
code! A t& !
One of the ways to search for perfect codes is to obtain the integer solutions for the parameters n, q, M
and t in the equation for Hamming bound. Some of the solutions found by exhaustive computer searches are
listed here.
S.N. n q M T
1 23 2 212 3
2 90 2 278 2
3 11 3 36 2
There are both binary and non-binary Hamming codes. Here, we shall limit our discussion to binary Hamming
codes. The binary Hamming codes have the property that
where m is any positive integer. For example, for m = 3 we have a (7, 4) Hamming code. The parity check
matrix, H, of a Hamming code is a very interesting matrix. Recall that the parity check matrix of an (n, k)
code has n – k rows and n columns. For the binary (n, k) Hamming code, the n = 2m – 1 columns consist of
all possible binary vectors with n – k = m elements, except the all zero vector.
148 ° Information Theory, Coding and Cryptography
Example 3.28 The generator matrix for the binary (7, 4) Hamming code is given by
È1 1 0 1 0 0 0˘
Í0 1 1 0 1 0 0˙˙
G= Í
Í0 0 1 1 0 1 0˙
Í ˙
Î0 0 0 1 1 0 1˚
The corresponding parity check matrix is
È1 0 1 1 1 0 0 ˘
Í ˙
H = Í0 1 0 1 1 1 0 ˙
ÍÎ0 0 1 0 1 1 1 ˙˚
Observe that the columns of the parity check matrix consist of (100), (010), (101), (110), (111), (011)
and (001). These seven are all the possible non-zero binary vectors of length three. It is quite easy to
generate a systematic Hamming code. The parity check matrix H can be arranged in the systematic form
as follows:
È1 1 1 0 1 0 0 ˘
Í ˙
H = Í0 1 1 1 0 1 0˙ = [ – PT | I ]
ÍÎ1 1 0 1 0 0 1 ˙˚
Thus, the generator matrix in the systematic form for the binary Hamming code is
È1 0 0 0 1 0 1˘
Í0 1 0 0 1 1 1˙˙
G = [ I | P] = Í
Í0 0 1 0 1 1 0˙
Í ˙
Î0 0 0 1 0 1 1˚
From the above example we observe that no two columns of H are linearly dependent (otherwise they
would be identical). However, for m > 1, it is possible to identify three columns of H that would add up to
zero. Thus, the minimum distance, d *, of an (n, k) Hamming code is equal to 3, which implies that it is a
single-error correcting code. Hamming codes are perfect codes.
By adding an overall parity bit, an (n, k) 'n+1, k) code with
d * = 4. On the other hand, an (n, k) Hamming code can be shortened to an (n – l, k – l) code by removing
l rows of its generator matrix G or, equivalently, by removing l columns of its parity check matrix, H. We can
; !
Let n = (qk – 1)/(q – 1). The (n, k) Hamming code over GF(q) is a code for which the
parity check matrix has columns that are pairwise linearly independent (over GF(q)), i.e., the columns are
a maximal set of pairwise linearly independent vectors.
Linear Block Codes for Error Correction ° 149
Example 3.29 Consider the (8, 4) extended Hamming code obtained from the binary (7, 4)
È1 1 1 1 1 1 1 1˘
Í0 0 0 0 1 1 1 1˙˙
Hamming code He = Í
Í0 0 1 1 0 0 1 1˙
Í ˙
Î0 1 0 1 0 1 0 1˚
Note that we have added a row of 1’s as the 1st row and introduced a column [1 0 0 … 0]T as the 1st
column in the original H matrix. The (8, 4) extended Hamming code has d * = 4. We further note that He
is also a generator matrix. Thus, the (8, 4) extended Hamming code is a self-dual code.
In general, any binary (n, k) code with minimum distance d *can be expanded to a (n + 1, k) code with
minimum distance d * + 1 by appending the sum of all the codeword components to make the overall parity
check. If an original codeword has an odd weight, the parity bit must be 1. Thus all codewords with weight
w*= d * become codewords of weight d * + 1. Hence, the minimum weight of the code goes up by one! The
È1 1 � 1 ˘
Í0 ˙
original parity check matrix, H, in its expanded avatar, would become Í ˙.
Í� H ˙
Í ˙
Î0 ˚
INDUSTRIAL RELEVANCE
( * !! " 1@@@ A84 6 (
An (r, s) Gallager code is a linear code with a check matrix H, satisfying the condition
that every column has r ones and every row has s ones.
The matrix has r = 2 ones in each column and s = 4 ones in each row. We cannot have any more
independent columns in this 5 ¥ 10 matrix because all the possible combinations of choosing two ones
Ê 5ˆ
out of t ! ! Á ˜ have been exhausted. Since the dimension
Ë 2¯
of the parity check matrix is (n – k) ¥ n, we have n = 10 and k = 5. We also observe that the last three
columns, i.e., 8 through 10 add up to the zero vector. Therefore, the minimum distance of this code is 3.
This is a (10, 2, 4) LDPC code.
LDPC codes can be constructed by using random constructions, algebraic constructions or a combination
of the two. A simple algorithm for random construction of LDPC codes is given below.
9 5 1 Set i = 1.
nr
9 5 1 Generate a random binary vector of length and Hamming weight r. This is the ith column of H.
s
9 5 1 If the weight of each row of H at this point is £ s, and the scalar product of each pair of columns is
£ 1, set i = i + 1. Else, go to step 2.
9 5 1 If i = n, stop. Else, go to step 2.
The random algorithm does not guarantee s ones in each row. Hence, we may generate irregular LDPC
codes by this method. To make the codes regular, suitable constraints have to be put in the algorithm.
An algorithm for algebraic construction of LDPC codes is given below.
r -1
9 5 1 Choose p > .
s -1
9 5 1 Construct a p ¥ p matrix from the identity matrix Ip by cyclically shifting its rows by one position to
the right.
È0 1 0 0 � 0 ˘
Í0 0 1 0 � 0 ˙
Í ˙
J = Í0 0 0 1 � 0 ˙ (3.29)
Í ˙
Í0 0 0 0 � 1 ˙
ÍÎ1 0 0 0 � 0˙˚
where J0 = Ip and the lth power of J is obtained from Ip by cyclically shifting its rows by l mod p positions
to the right. This matrix has exactly r ones in each column and s ones in each row. Thus it is a regular LDPC
code, by design.
In a regular LDPC code, each received codeword is checked by precisely r equations and every
check equation adds up precisely s code symbols. All linear codes, including LDPC codes, can
be represented using a 3 5
A Tanner graph is a graphical representation of the linear code based on the set of
check equations. It is a bipartite graph, which means it has two kinds of nodes: symbol nodes and check
nodes. Each symbol nodes are connected only to check nodes and each check node is connected only to
symbol nodes.
Each component of the codeword is represented in the Tanner graph by a symbol node. Hence, there are n
symbol nodes. Each check equation of the code is represented in the Tanner graph by a check node. Hence,
there are n – k check nodes. Each check node is connected by an edge to those symbol nodes that it checks.
An LDPC code can be decoded using a simple iterative ; ? 55 ' -' . This suboptimum
algorithm can be summarised in the following steps:
1. Perform hard decision decoding of the received symbols from the channel to form a binary vector v. If
we have the received word to start with, this step need not be performed. The vector v is n bit long.
2. Compute the syndrome s = vH T. Note that each component of v affects only s components of the
syndrome, s. If only a single bit is in error, only s syndrome components will be equal to 1.
J! ; K K n bits of v.
4. Flip those bits of v K!
5. Go back to step number 3. Keep iterating until either:
! $ K
b. A predetermined number of iterations is reached.
Q V !
However, for large block lengths, this sub-optimum algorithm works remarkably well.
Example 3.31 Let us consider the linear rate 1/3 code given by the following parity check matrix.
È1 1 1 0 0 0˘
Í1 0 0 1 1 0˙˙
H= Í (3.31)
Í0 1 0 1 0 1˙
Í ˙
Î0 0 1 0 1 1˚
Here n = 6, r = 3 and s = 2. This is not exactly an LDPC code since n is not large enough to yield a
sparse H matrix. The Tanner graph for this code is shown in Fig 3.6.
Suppose the received word is v = [0 0 1 0 0 0]. By performing syndrome calculation we obtain s = vHT
= [1 0 0 1], which is non-zero. Hence this is not a valid codeword. From the syndrome vector we note
that the parity checks that have failed are 1 and 4. This implies that there is an error among the symbols
connected to the check nodes 1 and 4 of the Tanner graph. We make the following observations:
152 ° Information Theory, Coding and Cryptography
INDUSTRIAL RELEVANCE
1@@@ A84 B= - $ 1 # - " 0 !!
+,
Optimal linear codes give the best distance property under the constraint of the block length. Most of the
optimal codes have been found by long computer searches. It may be possible to have more than one optimal
code for a given set of parameters n, k and d *. For instance there exist two different binary (25, 5, 10) optimal
codes
Linear Block Codes for Error Correction ° 153
An (n, n – r, d * d * £ r + 1.
d* £ n – k + 1
Substitute k = n – r to get
d* £ r + 1
Except the trivial repetition code, there are no binary MDS codes. However, we do have non-binary MDS
codes, for example the Reed Solomon codes, which we will study in Chapter 5. Some interesting properties
of MDS codes are:
q-ary (n, k) linear code is an MDS code if, and only if, the minimum non-zero weight of any
codeword is n – k + 1.
q-ary (n, k) linear code is an MDS code if, and only if, every set of n – k columns of a parity check
matrix is linearly independent.
d* 1
£ (1 - r ) + (3.32)
n n
where r is the code rate. For large values of block length, the factor 1/n can be neglected. Another upper
bound can be obtained directly from the Hamming bound expressed in (3.26). By dividing both sides of the
inequality by n and setting q = 2 for the binary case, we obtain
1 Ê t Ê nˆ ˆ
log 2 Á Â Á ˜ ˜ £ 1 - r (3.33)
n Ë i =0 Ë i ¯ ¯
Since the minimum distance, d *, and the error correcting capability, t, are related, the above relation is an
upper bound on d *. For any n, let t0 be the largest integer t for which (3.33) holds. Then, it can be shown that
as n , the ratio t/n cannot exceed t0/n, where t0/n
Êt ˆ
1- r = H Á 0 ˜ (3.34)
Ë n¯
The generalised Hamming bound can be written as
1 Ê t Ê nˆ iˆ
log q Á Â Á ˜ ( q - 1) ˜ £ 1 - r (3.35)
n Ë i =0 Ë i ¯ ¯
1 Ê qd * - 1 ˆ
Á - 1 - log q d * ˜ £ 1 - r (3.36)
n Ë q -1 ¯
A tighter upper bound on d* is due to Elias, and is given below in its asymptotic form.
d*
£ 2 A(1 - A) (3.37)
n
where
r = 1 + A log 2 A + (1 - A) log 2 (1 - A) , 0 £ A £ ½ (3.38)
Lower bounds also exist for d*. A lower bound on d*, based on a theorem proposed by Gilbert and
Varshamov Bound is given below.
d*
≥a (3.39)
n
where
r = 1 + a log 2 a + (1 - a ) log 2 (1 - a ) = 1 - H (a ), 0 £ a £ ½ (3.40)
Linear Block Codes for Error Correction ° 155
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO3:
1. Show that the binary (23, 12, 7) code is a perfect code. S
3. Consider a system without using error control coding, and allocating Eb energy per bit. S
What is the available energy per bit after using the LBCs given below? Also, what will be
the energy loss per bit (in dB) for each of the following cases?
(i) (7, 4) Hamming code.
(ii) (15, 11) Hamming code.
(iii) (3, 1) Repetition code.
(iv) Plot the performance of the (7, 4) Hamming code over AWGN channel keeping in
consideration the energy loss per bit due to coding.
4. Give the parity check matrix, H, for a (15, 11) Hamming code. From the parity check M
matrix determine how many errors can it correct?
5. The proposed spacecraft to Mars, Mangalyan X, would be sending colour photographs D
over a binary symmetric satellite channel that has a reliability of 0.999 and is subject
to randomly scattered noises. The spacecraft creates photographs using pixels of 128
different colours. Thus each colour is a codeword. The space mission would like the
probability of a pixel in the received image being assigned an incorrect colour to be less
than 0.0001. Determine the parameters (n, k, d *
could be used by the spacecraft.
6. Consider a linear code with distance d * = 3 and length n = 2x where x is a positive integer. M
Use the Hamming bound to show that an upper bound U on the number of codewords in
such a linear code is U = 22– x – 1.
transmissions possible. Space-time codes are coding techniques designed for multiple-antenna transmissions.
In particular, coding is performed by adding properly designed redundancy in both spatial and temporal
!" # $ $ % #
system, the symbol error rate (SER) for the system can be approximated by
c
Pe ª (3.41)
(Gc S )Gd
where S is the SNR and c !
channel. Gc (Gc ≥ 1) denotes the & '3 G
and d is the Diversity Order of the system. The diversity
gain/order determines the slope of an error rate curve plotted as a function of SNR, while the coding gain
determines the horizontal shift of the uncoded system error rate curve to the space-time coded error rate
curve obtained for the same diversity order. There are two main kinds of space-time coding schemes, namely,
space-time trellis codes (STTC) and space-time block codes (STBC). While STTC are designed to provide
both maximum coding and diversity gain, STBC provide only full diversity gain and zero or minimal coding
gain. Here we will study the STBC and return to STTC in Chapter 8.
The Alamouti scheme &''; $ !$ # <
transmit diversity for systems with two transmit antennas. Tarokh later generalised Alamouti’s transmit
diversity scheme to an arbitrary number of transmit antennas and presented more complex STBCs based on
orthogonal matrices. STBCs achieve Maximum Likelihood (ML) decoding through linear processing at
the receiver. Figure 3.7 shows the block diagram of the Alamouti space-time encoder.
# $ # >
Information
Source
h1
n1, n2 Channel
2b bits Tx 1 h
h1 Estimator 2
Signal {s1, s2} r1, r2 ML
Space-Time + h1 h2 ~ Detector
Constellation r1
Encoder
with 2b symbols h2
Tx 2 Combiner ~
r2
�s s�
C = � 1* *2� time
�–s2 s1�
space
To transmit b bits/cycle, we use a modulation scheme that maps one symbol from a constellation with 2b
symbols. The output of the mapper, { x1 , x2 }, is input to a space-time coding block. The encoding takes in
two time slots (the time axis) over two antenna elements (the space axis). In each encoding operation, the
encoder takes two symbols s1 and s2 and transmits according to the following coding strategy, depicted by
the matrix
È x1 x2 ˘
X =Í * ˙ (3.42)
Î- x2 x1* ˚
*
where x1 is the complex conjugate of x1 . During symbol period 1, antenna 1 and antenna 2 transmit x1 and
x2 respectively. For example, if symbols s1 and s2 are selected, we map x1 Æ s1 and x2 Æ s2 and obtain
È s1 s2 ˘
the codeword matrix as C = Í * ˙.
Î- s2 s1* ˚
Linear Block Codes for Error Correction ° 157
During symbol period 1, antenna 1 and antenna 2 transmit s1 and s2 respectively. During symbol period 2,
* *
antenna 1 and antenna 2 transmit -s2 and s1 respectively.
Note that
X H X = x1 + x2 ( 2 2
)I 2 (3.43)
(
r�1 = h1 + h2
2 2
)s + h n + h n
1
*
1 1
*
2 2
(3.47)
r� = ( h )s - h n + h n
2 2
2 1 + h2 2
*
1 2
*
2 1
Note that the receiver must have an estimate of h1 and h2 in order to implement the combining scheme.
The beauty of (3.47) is that r�1 depends only on s1, and not on s2. Similarly, r�2 depends only on s2, and not on
s1 " > #
(
x�1 = arg min r�1 - h1 + h2
x ŒS
2 2
)s (3.48)
= arg min r� - ( h )s
2 2
x�2 2 1 + h2
x ŒS
Ê N ˆ (3.49)
G T G = Á Â xi2 ˜ I N
Ë i =1 ¯
A real orthogonal design exists if and only if N = 2, 4 and 8. A Generalised Real Orthogonal Design is a
T ¥ N matrix with entries consisting of real elements drawn from ±x1, ±x2,…, ±xK such that
158 ° Information Theory, Coding and Cryptography
Ê K ˆ
G T G = Á Â xi2 ˜ I N (3.50)
Ë i =1 ¯
where IN is a N ¥ N identity matrix and K is a constant that represents the number of distinct symbols being
transmitted. A & 5- % ' - ' of size N is an N ¥ N matrix G with entries consisting of
* * *
complex elements drawn from ±x1, ±x2,…, ±xN and their conjugates ± x1 , ± x2 ,� , ± xN , or multiples of these
by j = -1 such that
Ê N 2ˆ
G H G = Á Â xi ˜ I N (3.51)
Ë i =1 ¯
where IN is a N ¥ N identity matrix. A complex orthogonal design exists if and only if N = 2 (the
Alamouti code). A Generalised & 5- % ' - ' is a T ¥ N matrix G with complex
* * *
elements drawn from 0, ± x1 , ± x1 , ± x2 , ± x2 ,� , ± xK , ± xK , or multiples of these by
j = -1 such that
Ê K 2ˆ
G H G = k Á Â xi ˜ I N (3.52)
Ë i =1 ¯
where IN is a N ¥ N identity matrix and k is a constant.
Some examples of real orthogonal design are
È x1 - x2 ˘
X2 = Í ˙ (3.53)
ÍÎ x2 x1 ˙˚
for N = 2 transmit antennas and
È x1 - x2 - x3 - x4 ˘
Íx x1 x4 - x3 ˙˙
X4 = Í
2
(3.54)
Í x3 - x4 x1 x2 ˙
Í ˙
Î x4 x3 - x2 x1 ˚
for N = 4 transmit antennas.
Like in Alamouti scheme, ML decoding is accomplished in orthogonal STBCs through linear processing
at the receiver because of the orthogonality of the transmission matrices. STBCs will be covered in greater
detail in Chapter 6.
INDUSTRIAL RELEVANCE
0 ! " ! !!
1@@@ A84 B= - $ @30 "
Linear Block Codes for Error Correction ° 159
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO4:
È x1 x2 ˘
1. Show that the generator matrix, G2 = Í ˙ , corresponds to a real orthogonal S
ÍÎ- x2 x1 ˙˚
design. What is interesting about this generator matrix?
È x1 x2 x3 x4 ˘
Í- x x1 - x4 x3 ˙˙
2. Does the generator matrix, G4 = Í 2 , correspond to a real M
Í - x3 x4 x1 - x2 ˙
orthogonal? Why/why not? Í ˙
Î- x4 - x3 x2 x1 ˚
3. What kind of design does the following generator matrix represent: M
È x1 x2 x3 ˘
Í ˙
Í- x2 x1 - x4 ˙
G=Í ˙ ? What is the rate of the code?
Í - x3 x4 x1 ˙
Í- x - x x2 ˙˚
Î 4 3
È x1 - x2* - x3* 0 ˘
Í ˙
Íx x1* 0 x3* ˙
G=Í 2 ˙ ? What is interesting about this STBC scheme?
Í x3 0 x1* - x2* ˙
Í0 - x3 x2 x1 ˙˚
Î
If you have successfully solved the above problems,
! " # $% & ' "- .
capacity”. Shannon predicted the existence of good channel codes, but did not tell how to construct them.
Since then the search for good codes is on. Shannon’s seminal paper can be accessed from the site#.
!
work on linear codes was extended by Golay (whose codes will be studied in the following chapter). Golay
also introduced the concept of perfect codes. Non-binary Hamming codes were developed by Golay and
" $ % & ' + 7 +
some of the best known codes are the ones discovered by sheer genius, rather than exhaustive searches.
According to Shannon’s theorem, if C(p) represents the capacity (see Chapter 1 for further details) of
a binary symmetric channel with probability of bit error equal to p, then for arbitrarily low probability of
symbol error we must have the code rate R < C(p). Even though the channel capacity provides an upperbound
on the achievable code rate (R = k/n), evaluating a code purely against channel capacity may be misleading.
The block length of the code, which translates directly into the delay, is also an important parameter. Even
if a code performs far from capacity, it may be possible that it is the best code possible of the same rate and
length. It has been observed that as we increase the block length of the codes, the bounds on the code rate
are closer to the channel capacity as opposed to the codes with smaller blocklengths. However, longer block-
lengths imply longer delays for decoding. This is because we cannot begin the decoding of a codeword until
we have received the entire codeword. The maximum delay allowable is limited by practical constraints. For
example, in mobile radio communications, packets of data are restricted to fewer than 200 bits. In these cases
codewords with very large blocklengths cannot be used.
Low Density Parity Check (LDPC) codes were introduced by Gallager in his doctoral thesis in 1963. They
were rediscovered after three decades in 1990s and have become part of several wireless standards today. The
use of multiple antennas is also rapidly becoming popular in wireless communications. Transmit diversity
techniques are being currently integrated with 4G wireless standards. Space time coding was introduced by
! $ ; " 7 $ >> ! @ ' > '
block code to provide full transmit diversity for systems with two transmit antennas.
LEARNING OUTCOMES
# [Link]
Linear Block Codes for Error Correction ° 161
È x1
x2 ˘
Y The orthogonal code matrix of the Alamouti scheme is given by X = Í * ˙.
x1* ˚
Î- x2
Y A real orthogonal design of size N is an N ¥ N matrix G = G (x1, x2,… xN), with entries consisting of
Ê N ˆ
real elements drawn from ±x1, ±x2,…, ±xN such that GT G = Á Â xi2 ˜ I N where IN is a N ¥ N identity
matrix. Ë i =1 ¯
Y A generalised real orthogonal design is a T ¥ N matrix with entries consisting of real elements drawn
Êk ˆ
from ±x1, ±x2,…, ±xk such that G T G = Á Â xi2 ˜ I N where IN is a N ¥ N identity matrix and k is a
Ë i =1 ¯
constant that represents the number of distinct symbols being transmitted.
Y A complex orthogonal design of size N is an N ¥ N matrix G with entries consisting of complex
* * *
elements drawn from ±x1, ±x2,…, ±xN and their conjugates ± x1 , ± x2 ,� , ± xN , or multiples of these by
Ê N 2ˆ
j = -1 such that G H G = Á Â xi ˜ I N where IN is a N ¥ N identity matrix.
Ë i =1 ¯
Y A generalised complex orthogonal design is a T ¥ N matrix G with complex elements drawn
from 0, ± x1 , ± x1* , ± x2 , ± x2* ,� , ± xk , ± xk* , or multiples of these by j = -1 such that
Êk 2ˆ
G H G = k Á Â xi ˜ I N where IN is a N ¥ N identity matrix and k is a constant.
Ë i =1 ¯
For interactive quiz with answers, scan the QR code given here
Or
Visit [Link]
3.7 Find a set of 16 binary words of length 7 such that each pair of words is at least at a Hamming distance
of 3.
3.8 For the binary repetition code of length 5, determine the G and the H matrix.
3.9 Which of the following is not a valid Hamming code: (255, 247), (2047, 2035) and (4095, 4083)?
3.10 What happens if two errors occur in a received word using (7, 4) Hamming code?
3.11 What does a zero syndrome vector signify?
U Y Z \Z; O^ VK \Z; _
3.13 Are all odd-length binary repetition codes perfect codes?
È1 0 0 1 1 ˘
Í ˙
3.14 For the code given by G = Í0 1 0 1 2˙ over GF(4), what is the minimum distance, d *? Is this
ÍÎ0 0 1 1 3˙˚
code a perfect code?
3.15 Is the binary Hamming (15, 11) code perfect?
PROBLEMS
S 3.1 Show that C = {0000, 1100, 0011, 1111} is a linear code. What is its minimum distance?
M 3.2 Construct, if possible, binary (n, k, d *) codes with the following parameters:
(i) (6, 1, 6)
(ii) (3, 3, 1)
(iii) (4, 3, 2)
M 3.3 Consider the following generator matrix over GF(2).
È1 0 1 0 0 ˘
Í ˙
G = Í1 0 0 1 1 ˙
ÍÎ0 1 0 1 0˙˚
(i)
Generate all possible codewords using this matrix.
(ii)
Find the parity check matrix, H.
(iii)
Find the generator matrix of an equivalent systematic code.
(iv)Construct the standard array for this code.
(v)What is the minimum distance of this code?
(vi)How many errors can this code detect?
(vii)Write down the set of error patterns this code can detect.
(viii)How many errors can this code correct?
(ix)What is the probability of symbol error if we use this encoding scheme? Compare
it with the uncoded probability of error.
(x) Is this a linear code?
Linear Block Codes for Error Correction ° 165
È2 4 2 2 4 4˘
Í0 0 3 0 1 1 ˙˙
D 3.16 Consider the generator matrix over GF(5), G = Í . Find the parity check
Í3 1 4 0 4 0˙
Í ˙
Î2 3 4 1 1 1˚
matrix, H.
M 3.17 Let C be a binary perfect code of length n with minimum distance 7. Show that n = 7 or n = 23.
S 3.18 Consider a linear binary code C and a vector u œ C. Show that C » (u + C) is also a linear code.
S 3.19 Let rH denote the code rate for the binary Hamming code. Determine lim rH .
k
S 3.20 Show that a (15, 8, 5) code does not exist.
S 3.21 Does a ternary double-error correcting perfect code exist? Explain.
M 3.22 Check whether the following STBC code is orthogonal:
È x1 - x2* - x3* 0 ˘
Í ˙
G = Í x2 x1* 0 - x3* ˙
Í ˙
ÍÎ x3 0 x1* x2* ˙˚
È x1 x2 x3 x4 ˘
Í- x x1 - x4 x3 ˙˙
Í 2
Í - x3 x4 x1 - x2 ˙
Í ˙
Í- x4 - x3 x2 x1 ˙
G=Í *
x x2* x3* x4* ˙
Í 1 ˙
Í - x* x1* - x4* x3* ˙
Í 2 ˙
Í - x3* x4* x1* - x2* ˙
Í * ˙
ÍÎ- x4 - x3* x2* x1* ˙˚
Linear Block Codes for Error Correction ° 167
COMPUTER PROBLEMS
U ' ' & 7 $ + GF(2), given the
generator matrix for the code.
UY 7 + ' & 7 $ + GF(q).
3.3 Show by simulations that if a binary (15, 11) Hamming code is used on a channel that makes two
errors then the output of the decoder is always wrong. What can you say about (2m – 1, 2m – 1 – m)
Hamming code in general?
3.4 Write a computer program to exhaustively search for all the perfect code parameters n, q, M and t in
the equation for the Hamming bound. Search for 1 ≥ n ≥ 200, 2 ≥ q ≥ 11.
2m - 1
3.5 Write a computer program for a universal binary Hamming encoder with rate m . The program
2 -1- m
should take as input the value of m and a bit-stream to be encoded. It should then generate an encoded
bit-stream. Develop a program for the decoder also. Now, perform the following tasks.
(i) Write an error generator module that takes in a bit stream and outputs another bit-stream after
inverting every bit with probability p, i.e., the probability of a bit error is p.
(ii) For m = 3, pass the Hamming encoded bit-stream through the above-mentioned module and then
decode the received words using the decoder block.
(iii) Plot the residual error probability (the probability of error after decoding) as a function of p.
Note that if you are working in the range of BER = 10-r, you must transmit on the order of
10r+2 bits (why?).
(iv) Repeat your simulations for m = 5, 8 and 15. What happens as m .
3.6 Write a computer program to generate a (20, 3, 4) LDPC code using:
(i) the random construction method,
(ii) the algebraic construction method.
Compare the two.
3.7 Write a computer program to generate a table of Hamming distances between all pairs of codewords
for a given Hamming code. The table would be of size (2k + 1) ¥ (2k + 1). The 1st row and 1st column
should list out all the valid codewords. All the other entries in this table will be Hamming distances.
;' J & O^ VK
3.8 Generate another table of size (2k + 1) ¥ (2k + 1) which shows that sum of each pair of codeword also
+ @ 7 7 ;'
this exercise for the (15, 11) Hamming code.
3.9 You are given 12 gold coins, of which 1 is a counterfeit (weighs either more or less than a genuine gold
coin). You have a beam balance at your disposal. Write a program that uses the parity-check matrix of
a (12, 9) LBC over GF(3) in order to detect the counterfeit coin with three weighings.
3.10 Write a computer program to search for orthogonal STBCs with N > 2.
PROJECT IDEAS
3.1 4 " 9! $@&1 Simulate a wireless communication system consisting of a
Channel Encoder, a Fading Channel and a Decoder. The aim of the project is to evaluate the performance
of an (2m – 1, 2m – 1 – mK " + & ;' ' +
the following for a range of SNRs:
168 ° Information Theory, Coding and Cryptography
Cyclic Codes
learning objectives
LO 1 Recall the knowledge of polynomials, which will come handy in studying cyclic codes.
LO 2 Know how to generate cyclic codes and to represent cyclic codes using generator
polynomials and generator matrices.
LO 3 Describe some popular cyclic codes.
LO 4 Explain how to implement cyclic codes using circuits.
!
low-complexity encoding and decoding algorithms.
In this chapter
!" 1.
Next, we will learn how to generate cyclic codes using operations on polynomials. Since cyclic
codes form a sub-class of linear block codes, we will study the matrix description of cyclic codes.
# $ $ %
!" 2.
& ' ( ) -
( *()(+ !" 3.
&
/ !" 4.
4.2 Polynomials
" # $ #
LO 1 %
Recall the knowledge of
polynomials, which will
A code C is if
come handy in studying (i) C is a linear code, and,
cyclic codes. (ii) any cyclic shift of a codeword is also a codeword, i.e., if the
codeword a0a1…an –1 is in C then an –1a0…an–2 is also in C.
Example 4.1 The binary code C = {0000, 0101, 1010, 1111} is a cyclic code.
However C2 = {0000, 0110, 1001, 1111} is not a cyclic code, but is equivalent & -
changing the third and the fourth components of C2 yield C .
The (5, 2) linear code C = {00000, 01101, 11010, 10111} is also not cyclic. The second codeword
when cyclic-shifted to the left gives the third codeword. However, another left-shift does not yield a
valid codeword.
A is a mathematical expression
f(x) = f0 + f1x + … + fmxm (4.1)
where the symbol x f0, f1, … fm are the elements of GF(q).
! fm & fm π 0, then m is called the degree of the polynomial,
and is denoted by deg f(x).
Cyclic Codes ° 171
A polynomial is called
Example 4.2 f(x) = 3 + 7x + x3 + 5x4 + x6 is a monic polynomial over GF(8). The degree of this
/ & x6 is 1.
3 4 6
g(x) = 1 + x + x + x + 3x is not a monic polynomial over GF9:* x6 is not
unity.
Polynomials play an important role in the study of cyclic codes, the subject of this chapter. Let F[x] be the
set of polynomials in x GF(q). Different polynomials in F[x] can be added, subtracted
and multiplied in the usual manner. F[x] is an example of an algebraic structure called a ring
' 9 ; <> ? <* F[x@
because polynomials of degree greater than zero do not have a multiplicative inverse. It can be seen that if
f(x), g(x) Œ F[x], then deg (f(x)g(x)) = deg f(x) + deg g(x). However, deg (f(x) + g(x)) is not necessarily
max{deg f(x), deg g(x*E ' f(x) and g(x), over GF(2) such that
f(x) = 1 + x2 and g(x) = 1 + x + x2. Then, deg (f(x) + g(x)) = deg (x) = 1. This is because, in GF(2), 1 + 1 = 0,
and x2 + x2 = (1 + 1) x2 = 0.
Example 4.3 Consider the polynomials f(x) = 2 + x + x2 + 2x4 and g(x) = 1 + 2x2 + 2x4 + x5 over
GF(3). Then,
f(x) + g(x) = (2 + 1) + x + (1 + 2)x2 + (2 + 2)x4 + x5 = x + x 4 + x5.
f(x) ◊ g(x) = (2 + x + x2 + 2x4)(1 + 2x2 + 2x4 + x5)
= 2 + x + (1 + 2.2)x2 + 2x3 + (2 + 2 + 2.2)x4 + (2 + 2)x5
+ (1 + 2 + 1)x6 + x7 + 2.2x8 + 2x9
= 2 + x + (1 + 1)x + 2x + (2 + 2 + 1)x4 + (2 + 2)x5
2 3
+ (1 + 2 + 1)x6 + x7 + x8 + 2x9
= 2 + x + 2x2 + 2x3 + 2x4 + x5 + x6 + x7 + x8 + 2x9
G GF(3).
x+1 q(x)
b(x) x2 + x + 1 x3 + x + 1 a(x)
x3 + x2 + x
x2 + 1
x2 + x + 1
x r(x)
Thus, a(x) = (x + 1) b(x) + x. Hence, we may write a(x) = q(x) b(x) + r(x), where q(x) = x + 1 and
r(x) = x. Note that deg r(x) < deg b(x).
Let f(x* ' F[x]. Two polynomials, g(x) and h(x) in F[x] are said to
be f(x), depicted by
g(x) ∫ h(x) (mod f(x))
if g(x) – h(x) is divisible by f(x).
Next, let us denote F[x]/f(x) as the set of polynomials in F[x] of degree less than deg f(x), with addition
and multiplication carried out modulo f(x* %
(i) If a(x) and b(x) belong to F[x]/f(x), then the sum a(x) + b(x) in F[x]/f(x) is the same as in F[x]. This is
because deg a(x) < deg f(x), deg b(x) < deg f(x) and therefore deg (a(x) + b(x)) < deg f(x).
(ii) The product a(x)b(x* $ f(x) to which a(x)b(x)
(multiplication being carried out in F[x]) is congruent modulo f(x).
F[x]/f(x) is called the ring of polynomials (over F[x]) modulo f(x* Q <R
'
Cyclic Codes ° 173
Example 4.8 Consider the ring F[x]/(x2 + x K M* GF(2). This ring will have
polynomials with highest degree = 1. This ring contains qn = 22 = 4 elements (each element is a
polynomial). The elements of the ring will be 0, 1, x and x + 1. The addition and multiplication tables
can be written as follows.
Table 4.1 F [x]/(x2 + x + 1)
+ 0 1 x x+1 0 1 x x+1
0 0 1 x x+1 0 0 0 0 0
1 1 0 x+1 x 1 0 1 x x+1
x x x+1 0 1 x 0 x x+1 1
x+1 x+1 x 1 0 x+1 0 x+1 1 x
Next, consider F[x]/(x2 K M* GF(2). The elements of the ring will be 0, 1, x and x + 1. The
addition and multiplication tables can be written as follows.
Table 4.2 Addition and multiplication tables for the ring F[x]/(x2 + 1)
+ 0 1 x x+1 0 1 x x+1
0 0 1 x x+1 0 0 0 0 0
1 1 0 x+1 x 1 0 1 x x+1
x x x+1 0 1 x 0 x 1 x+1
x+1 x+1 x 1 0 x+1 0 x+1 x+1 0
A polynomial f(x) in F[x] is said to be if f(x) = a(x) b(x), where a(x), b(x) are
elements of F(x) and deg a(x) and deg b(x) are both smaller than deg f(x). If f(x) is not reducible, it is called
. A monic irreducible polynomial of degree at least one is called a .
174 ° Information Theory, Coding and Cryptography
It is helpful to compare a reducible polynomial with a positive integer that can be factorised into a product
of prime numbers. Any monic polynomial in f(x* $
monic polynomials (prime polynomials). One way to verify a prime polynomial is by trial and error, testing
! $ U '
(i) A polynomial f(x) has a linear factor (x – a) if and only if f(a) = 0 where a
(ii) A polynomial f(x) in F[x] of degree 2 or 3 over GF(q) is irreducible if, and only if f(a) π 0 for all a in
GF(q).
9 * V xn – 1 = (x – 1)(xn–1 + xn–2 + … + x +1). The second factor may be further reducible.
Proof:
(i) If f(x) = (x – a)g(x), then obviously f(a) = 0. On the other hand if f(a) = 0, by division algorithm,
f(x) = q(x)(x – a) + r(x), where deg r(x) < deg (x – a) = 1. This implies that r(x) is a constant. But,
since f(a) = 0, r(x) must be zero, and therefore, f(x) = q(x)(x – a).
(ii) A polynomial of degree 2 or 3 over GF(q) will be reducible if and only if it has at least one linear factor.
The result (ii) then directly follows from (i). This result does not necessarily hold for polynomials of
degree more than 3. This is because it might be possible to factorise a polynomial of degree 4 or higher
into a product of polynomials, none of which are linear, i.e., of the type (x – a).
* 9 * 9x – 1) is a factor of (xn –1). By carrying out long division of (xn –1) by (x –1) we obtain
(xn – 1 + xn – 2 + … + x + 1).
Example 4.9 Consider f(x) = x3 –1 over GF(2). Using (iii) of Theorem 4.1 we can write
x3 –1 = (x – 1)(x2 + x K M* ! G Y
term, p(x) = (x2 + x + 1).
p(0) = 0 + 0 + 1 = 1, over GF(2)
p(1) = 1 + 1 + 1 = 1, over GF(2)
Therefore, p(x) cannot be factorised further (from (ii)).
Thus, over GF(2), x3 – 1 = (x – 1)(x2 + x + 1).
Next, consider f(x) = x3 – 1 over GF(3).
x3 –1 = (x – 1)(x2 + x + 1). Again, let p(x) = (x2 + x + 1)
p(0) = 0 + 0 + 1 = 1, over GF(3)
p(1) = 1 + 1 + 1 = 0, over GF(3)
p(2) = 2.2 + 2 + 1 = 1 + 2 + 1 = 1, over GF(3)
; p(1) = 0, from (i) we have (x – 1) as a factor of p(x).
Thus, over GF(3), x3 –1 = (x – 1)(x – 1) (x – 1).
Example 4.10 Consider the polynomial p(x) = x3 + x + 1 over GF9>* ; p(0) π 0 and p(1) π 0,
the polynomial is irreducible in GF9>* ; p(x) is a prime polynomial. Here we have
n = 3, so we can use p(x* >3 = 8 elements, i.e., GF9:* !
will be 0, 1, x, x + 1, x2, x2 + 1, x2 + x, x2 + x + 1, which are all possible polynomials of degree less than
nq< & 9 ' *
Having developed the necessary mathematical tools, we now resume our study of cyclic codes. We now
' f(x) = xn – 1 for the remainder of the chapter. We also denote F[x]/f(x) by Rn. Before we proceed, we make
%
(i) xn = 1 (mod xn – 1). Hence, any polynomial, modulo xn – 1, can be reduced simply by
replacing xn by 1, xn+1 by x and so on.
(ii) A codeword can uniquely $
of elements. We can use a polynomial to represent the locations and the values of all the
' c0c1c2…cn-1 can be represented by the
polynomial c(x) = c0 + c1x + c2x2 + … cn–1xn–1. Thus,
c = c0c1c2…cn–1 ´ c0 + c1x + c2x2 + … cn–1xn–1 = c(x)
As another example, the codeword over GF(8), c = 207735 can be represented by the polynomial
c(x) = 2 + 7x2 + 7x3 + 3x4 + 5x5.
(iii) Multiplying any polynomial by x corresponds to a single cyclic right-shift of the codeword elements.
More explicitly, in Rn, by multiplying c(x) by x we get
x◊c(x) = c0x + c1 x2 + c2x3 + … cn–1xn = cn-1 + c0x + c1x2 + c2x3 + … cn–2xn–1
176 ° Information Theory, Coding and Cryptography
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO 1:
GF(3). S
! S
follow the addition and multiplication rules for the ring.
(i) (2x + 1) + (4x + 5) + (3x + 3)
(ii) (2x + 1)2
(iii) (4x + 3)(x + 5)
" # x15 – 1 over GF(2). S
!" " #
$% & '
$ " "
S ( ) Level 1 and Level 2 Category
M * ) Level 3 and Level 4 Category
D " ) Level 5 and Level 6 Category
Cyclic Codes ° 177
# * which can be
used to construct the cyclic code.
Proof:
$% * g(x) and h(x) are monic polynomials in C of smallest degree. Then g(x) – h(x) is also in
C, and has a smaller degree. If g(x) π h(x), then a suitable scalar multiplier of g(x) – h(x) is monic, and
is in C, and is of smaller degree than g(x). This gives a contradiction.
(ii) Let a(x) Œ C. Then, by division algorithm, a(x) = q(x)g(x) + r(x), where deg r(x) < deg g(x). But
r(x) = a(x) – q(x)g(x) Œ C * * &
However, the degree of g(x) must be the minimum among all codewords. This can only be possible
if r(x) = 0 and a(x) = q(x)g(x). Thus, a codeword is obtained by multiplying the generator polynomial
178 ° Information Theory, Coding and Cryptography
g(x) with the polynomial q(x% # ! GF(q), here are qk distinct codewords possible.
These codewords correspond to multiplying g(x) with the qk distinct polynomials, q(x), where
deg q(x) £ (k – 1).
(iii) By division algorithm, xn – 1 = q(x)g(x) + r(x), where deg r(x) < deg g(x) or r(x) = {(xn – 1) – q(x)g(x)}
modulo (xn – 1) = – q(x)g(x). But – q(x)g(x) Œ C because we are multiplying the generator polynomial
by another polynomial, – q(x). Thus, we have a codeword r(x) whose degree is less than that of g(x).
This violates the minimality of the degree of g(x), unless r(x) = 0, which implies xn – 1 = q(x)g(x), i.e.,
g(x) is a factor of xn – 1.
The last part of the theorem gives us the recipe to obtain the generator polynomial for a cyclic code. All we
have to do is to factorise xn ; * E ! *
codewords of blocklength n simply by factorising xn – 1.
+ ) A cyclic code C may contain polynomials other than the generator polynomial which
also generates C. But the polynomial with the minimum degree is called the generator polynomial.
+ ) The degree of g(x) is n – k (this will be shown later).
A simple encoding rule to generate the codewords from the generator polynomial is
c(x) = i(x)g(x) (4.6)
where i(x) is the information polynomial, c(x) is the codeword polynomial and g(x) is the generator polynomial.
We have seen already that there is a one-to-one correspondence between a word (vector) and a polynomial.
The error vector can also be represented as the error polynomial, e(x). Thus, the received word at the receiver,
after passing through a noisy channel can be expressed as
v(x) = c(x) + e(x) (4.7)
Cyclic Codes ° 179
Example 4.13 Consider the generator polynomial g(x) = x3 + x + 1 for a binary cyclic code
(i.e., over GF(2)) of block length n = 7. The codewords and the corresponding codeword polynomials
are listed in Table 4.4. It is clear from the table that the minimum weight of this code is 3. This is, in
fact, the (7, 4) Hamming code. Observe how every codeword is a cyclic shift of some other codeword.
c c(x)
0000000 0
0001011 x3 + x + 1
0010110 x4 + x2 + x
0011101 x4 + x3 + x2 + 1
0100111 x5 + x2 + x + 1
0101100 x5 + x3 + x2
0110001 x5 + x4 + 1
0111010 x5 + x4 +x3 + 1
1000101 x6 + x2 + 1
1001110 x6 + x3 + x2 + x
1010011 x6 + x4 + x + 1
1011000 x6 + x4 + x3
1100010 x6 + x5 + x
1101001 x6 + x5 + x3 + 1
1110100 x6 +x5 + x4 + x2
1111111 x6 +x5 + x4 + x3 + x2 + x + 1
Example 4.14 Consider the generator polynomial g(x) = x2 + 1 for ternary cyclic codes (i.e., over
GF(3)) of block length n = 4. Here we are dealing with cyclic codes, therefore, the highest power of
g(x) is n – k n = 4, k * $F % '
will be a total of qk = 32 = 9 code words. The information polynomials and the corresponding code word
polynomials are listed in Table 4.5.
180 ° Information Theory, Coding and Cryptography
It can be seen that the cyclic shift of any code word results in another valid code word. By observing
! $ JK
with the minimum Hamming weight = 2). Therefore, this code is capable of detecting one error and
correcting zero errors.
Observing the fact that the codeword polynomial is divisible by the generator polynomial, we can
detect * *
with cyclic codes that are a subset of LBCs, we can use the all-zero codeword to illustrate this point
without loss of generality.
Assume that g(x) = x2 + 1 and the transmitted codeword is the all-zero codeword. Therefore, the
received word is the error polynomial, i.e.,
v(x) = c(x) + e(x) = e(x) (4.9)
È g0 g1 ... gr 0 0 0 ... 0˘
Í0 g0 g1 ... gr 0 0 ... 0 ˙˙
Í
G = Í0 0 g0 g1 ... gr 0 ... 0 ˙ k = (n – r) rows (4.10)
Í ˙
Í : : : ˙
ÍÎ 0 0 0 0 0 g0 g1 ... g r ˙˚
n columns
Proof: The (n - r) rows of the matrix are obviously linearly independent because of the echelon form of
the matrix. These (n – r) rows represent the codewords g(x), xg(x), x2g(x), …, xn–r–1g(x). Thus, the matrix can
generate these codewords. Now, to prove that the matrix can generate all the possible codewords, we must
show that every possible codeword can be represented as linear combinations of the codewords g(x), xg(x),
x2g(x), …, xn–r–1g(x).
We know that if c(x) is a codeword, it can be represented as
c(x)= q(x)◊g(x)
for some polynomial q(x c(x) < n (because the length of the codeword is n), it follows
that the degree of q(x) < n – r. Hence,
Thus, any codeword can be represented as a linear combination of g(x), xg(x), x2g(x), …, xn–r–1g(x). This
proves that the matrix G is indeed the generator matrix.
We also know that the dimensions of the generator matrix is k ¥ n. Therefore, r = n – k, i.e., the
degree of g(x) is n – k. Note that the generator matrix has an interesting structure because it is
constant along the diagonal. Such a matrix is called a Toeplitz matrix.
x4 – 1 = (x – 1)(x3 + x2 + x + 1) = (x – 1) (x + 1)(x2 + 1)
Thus all the divisors of x4 x – 1), (x + 1), (x2 + 1), (x – 1)◊(x + 1) = (x2 – 1), (x – 1) ◊(x2 + 1)
= (x – x + x +1), (x + 1) ◊(x + 1) = (x + x2 + x +1) and (x4 – 1). We know that all these factors of x4 – 1
3 2 2 3
! " #$ % "
with n = (qr – 1)/(q –1) and k = (qr –1)/(q –1) – r, where r is an integer ≥ 2. Therefore, a (4, 2) ternary
Hamming code exists, but it is not a cyclic code.
g(x) (n, k) d* G
1 (4, 4) 1 [I4]
(x – 1) (4, 3) 2 È-1 1 0 0˘
Í 0 -1 1 0˙
Í ˙
ÍÎ 0 0 -1 1 ˙˚
(x + 1) (4, 3) 2 È1 1 0 0 ˘
Í0 1 1 0 ˙
Í ˙
ÍÎ0 0 1 1˙˚
(x2 + 1) (4, 2) 2 È1 0 1 0 ˘
Í0 1 0 1 ˙
Î ˚
È-1 0 1 0˘
(x2 – 1) (4, 2) 2 Í 0 -1 0 1 ˙
Î ˚
(x3 + x2 + x + 1) (4, 1) 4 [1 1 1 1]
(x4 – 1) (4, 1) 0 [0 0 0 0]
The parity check polynomial can be used to generate another cyclic code since it is a factor of
xn – 1 and is called the dual code of C.
Example 4.16 Consider the generator polynomial g(x) = x3 + 1 for the (9, 6) binary cyclic codes.
The parity check polynomial can be found by simply dividing x9 – 1 by g(x).
Thus h(x) = (x9 – 1) / (x3 + 1) = x6 + x3 + 1.
Therefore, the dual code of g(x) = x3 + 1 is h(x) = x6 + x3 + 1.
5** C is a cyclic code with the parity check polynomial h(x) = h0 + h1x + …+ hkxk, then the parity
check matrix of C is given by
n columns
We observe that H & * ; ' $ cHT = 0. Therefore, iGHT = 0 for any information
T T
vector, i. Hence, GH = 0. We further have s = vH where s is the syndrome vector and v is the received word.
È1 1 0 1 0 0 0˘
Í0 1 1 0 1 0 0˙˙
G= Í
Í0 0 1 1 0 1 0˙
Í ˙
Î0 0 0 1 1 0 1˚
The parity check polynomial h(x) is (x – 1)(x3 + x2 + 1) = (x4 + x2 + x +1). And the corresponding
parity check matrix is
184 ° Information Theory, Coding and Cryptography
È1 0 1 1 1 0 0 ˘
Í ˙
H = Í0 1 0 1 1 1 0 ˙
ÍÎ0 0 1 0 1 1 1 ˙˚
The minimum distance of this code is 3, and this happens to be the (7, 4) Hamming code. Thus, the
binary (7, 4) Hamming code is also a cyclic code with a generator polynomial g(x) = (x3 + x + 1).
5** * i(x) = (x2 + x + 1). This corresponds to the
information word [1 1 1 0]. The corresponding codeword polynomial will be simply
c(x) = i(x)g(x) = (x2 + x + 1) (x3 + x + 1) = x5 + x4 + 1
This corresponds to the codeword [1 0 0 0 1 1 0].
We can verify the validity of the codeword polynomial by computing
s(x) = c(x)h(x) = (x5 + x4 + 1) (x4 + x2 + x +1) mod (x7 – 1)
= x9 + x8 + x7 + x2 + x + 1 mod (x7 – 1)
= (x2 + x + 1) (x7 – 1) mod (x7 – 1) = 0
B % 5 D–E % * % DFE - %
codes, i.e., over GF(2).
. An (n, k) / 1 is a linear block code such that, for some m coprime with
n, the polynomial xmc(x) calculated mod xn – 1 is a codeword polynomial if c(x) is a valid codeword
polynomial.
È1 1 1 0 1 1 0 0 0 0 0 1˘
Í0 0 1 1 1 1 0 1 1 0 0 0 ˙˙
G= Í
Í0 0 0 0 0 1 1 1 1 0 1 1˙
Í ˙
Î0 1 1 0 0 0 0 0 1 1 1 1˚
Here m = 3 because the cyclic shift of any row of G by three places produces another row of the
matrix.
The unused symbols in a shortened code are always set to zero and are not transmitted. The receiver
re-inserts the zeroes prior to decoding. Thus, even though the code is no longer cyclic, the same encoder and
decoder can be used after the zeroes have been taken care of.
Example 4.19 Consider the (7, 4) Hamming code, which is also a cyclic code. We form a
shortened (5, 3) code as follows. The two leading bits in the codeword are set to zero, followed by two
information bits and the same three parity bits. The minimum distance of the shortened code is also 3,
making it a single error correcting code.
K %5 5 %5 7 ' * %
communications channel, fading results in burst errors. When errors occur at a stretch, as
opposed to random errors, we term them as 4 .
Example 4.20 L
be
c=0100011101010000101101
! " #
b=0000011011011110000000
# " "
channel. Here the length of the burst is 10 bits, however, not all the ten locations are in error.
If we are constructing codes for channels more prone to burst errors of length t (as opposed to an arbitrary
pattern of t ' " " $ )
e(x) = xi.b(x) (4.14)
where e(x) is a polynomial of degree £ t – 1 and b(x) is the burst pattern. xi marks the starting location of the
burst pattern within the codeword being transmitted.
A code designed for correcting a burst of length t + +
s(x) = Rg(x)[e(x)] (4.15)
is different for each polynomial representing a burst of length t.
Example 4.21 /or a binary code of block length n = 15, consider the generator polynomial
g(x) = x6 + x3 + x2 + x + 1
This code is capable of correcting bursts of length 3 or less. To prove this we must show that all the
syndromes corresponding to the different burst errors are distinct. The different burst errors are
186 ° Information Theory, Coding and Cryptography
" C
+ % " D EF
bursts of length t or less must have at least 2t + + G # 6 4 .
In the next three sections, we will study three different sub-classes of cyclic codes. Each sub-class has a
$ K
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO 2:
/ " + " + " S
GF(2).
M / " :N 8' + GF(2). List all the codewords. S
5. Consider the generator polynomial g(x) = (x3 + x + 1) for a (7, 3) cyclic code over GF(2). D
Let the received vector r(x) = (x + x2 + x4+ x5+ x6). Calculate the syndrome polynomial
for r(x) and all its cyclic shifts.
!" " #
$% & '
1
0.9
0.8
0.7
0.6
0.5
0.4 t
2 3 4 5 6 7 8 9 10
Fig. 4.1
The degree of g(x) = n – k = 8. The block length is the smallest integer n such that g(x) divides
xn – 1. After trial and error we get n V 8 # / :8 MN'
g(x) = x8 + x6 + x5 + x3 + x + 1. This code can correct up to bursts of length 3. The code rate of this code
NN $ " + g(x) = x6 + x3 + x2 + x + 1 which has a code rate
of only 0.6.
/ $ t # +/ : m = t)
for different values of t /" W
188 ° Information Theory, Coding and Cryptography
(n, k) t
(9, 4) 2
(35, 27) 3
(105, 94) 4
(279, 265) 5
(693, 676) 6
(1651, 1631) 7
(3825, 3802) 8
INDUSTRIAL RELEVANCE
The Automatic Link Establishment *0!1+ 2& 3040
5 *67 86+ '
Cyclic Codes ° 189
Let an error E occur when T is transmitted over a noisy channel. The received word is given by
V=T+E (4.25)
-/- # # V is completely divisible by P. This translates to the
case when E is completely divisible by P (because T is divisible by P).
Example 4.24 Let the message D = 1010001101, i.e., k = 10 and the pattern, P = 110101. The
# 7-< # n 7-<
7 $ " D5 (left shift by 5 and pad with 5 zeroes). This yields
25D = 101000110100000
Next divide the resulting number by P = 110101. By long division, we obtain Q = 1101010110 and
R = 01110. The remainder is added to 25 D to obtain
T = 101000110101110
T is the transmitted codeword. If no errors occur in the channel, the received word, when divided by
P, will yield 0 as the remainder.
Example 4.25 Let P(x) = x16 + x15 + x2 + 1. This P(x) acts as the generator polynomial. Let the
message to encode be D(x) = x13 + x + 1.
< n – k = degree of P(x ! " D(x) by x16.
x16D(x) = x19 + x17 + x16
Divide x16 D(x) by P(x) to obtain
R(x) = x15 + x5 + x4 + x3 + 1
The codeword will be
T(x) = x16 D(x) + R(x)
= (x19 + x17 + x16) + (x15 + x5 + x4 + x3 + 1)
= x19 + x17 + x16 + x15 + x5 + x4 + x3 + 1
Cyclic Codes ° 191
Example 4.26 <uppose the transmitted codeword undergoes a single-bit error. The error
polynomial E(x) can be represented by E(x) = xi, where i determines the location of the single-bit error.
If P(x) contains two or more terms, E(x)/P(x) can never be zero. Thus all the single errors will be caught
-/-
Example 4.27 <uppose two isolated errors occur, i.e., E(x) = xi + x j, i > j. Alternately,
E(x) = x j(xi–j + 1). If we assume that P(x) is not divisible by x #! # $
double errors is that P(x) does not divide xk + 1 for any k up to the maximum value of i – j (i.e., the frame
$ 7 " x15 + x14 + 1 will not divide xk + 1 for any value of k below 32,768.
Example 4.28 <uppose the error polynomial has an odd number of terms (corresponding to an
odd number of errors). An interesting fact is that there is no polynomial with an odd number of terms
that has x + 1 as a factor if we are performing binary arithmetic (modulo 2 operations). By making
(x + 1) as a factor of P(x), we can catch all errors consisting of odd number of bits (i.e., we can detect
# # " J
Another interesting feature of CRC codes is its ability to detect burst errors. A burst error of
length k can be represented by xi(xk–1 + xk–2 + … + 1), where i determines how far from the
right end of the received frame the burst is located. If P(x) has an x0 term, it will not have an xi
as a factor. So, if the degree of (xk–1 + xk–2 + … + 1) is less than the degree of P(x), the
remainder can never be zero. Therefore, a polynomial code with r check bits can detect all
burst errors of length £ r. If the burst length is r + 1, the remainder of the division by P(x) will be zero if
and only if the burst is identical to P(x). Now, the 1st ! " #
intermediate bits can be 1 or 0. Therefore, the exact matching of the burst error with the polynomial P(x)
depends on the r – 1 intermediate bits. Assuming all combinations are equally likely, the probability of a miss
1
is r -1 . One can show that when error bursts of length greater than r + 1 occur, or several shorter bursts
2 1
occur, the probability of a bad frame slipping through is r .
2
INDUSTRIAL RELEVANCE
()($96 $ $ Synchronous Transmission Standards.
()($7: '4/ ()($;7 <4" High-Level Data Link
Control *2=!(+ $ $
< " > 4 > *<4"+ ()($;7 1(/0$8?6
part of the European Computer Manufacturers Association *1(/0+
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO 3:
- -/- P(x) = x16 + x15 + x2 X 7 " S
determine how many odd number of errors it can detect? Also comment on the detection
capability for double errors.
D - -/- P(x) = x16 + x15 + x2 + 1. Let the message polynomial be M
D(x) = x + x + x + x + x8 + x5 + x2 + x X 7
14 13 11 10 " $ codeword
polynomial, T(x - -/- O ^
R - -/-? P(x) = x16 + x15 + x2 + 1. What can be the largest size of the M
codeword (in bytes) that can detect double errors ?
M - DM D `7 jW<W # W > ; M
Establishment with g(x) = x11 + x9 + x7 + x6 + x5 + x X " $$
matrix, G24 and the table of weights of different codewords.
!" " #
$% & '
Fig. 4.2 Circuit elements used to construct encoders and decoders for cyclic codes.
a b c
+ +
We next focus on the multiplication of an arbitrary polynomial a(x) by g(x). Let the polynomial g(x) be
represented as
g(x) = gLxL +… + g1x + g0 (4.29)
the polynomial a(x) be represented as
a(x) = akxk +… + a1x + a0 (4.30)
the resultant polynomial b(x) = a(x)g(x) be represented as
+ b(x)
+ + + +
gL gL – 1 gL–2 gL–3 g1 g0
a(x)
Fig. 4.6 !
g(x) = x8 + x6 + x5 + x3 + x + 1.
Example 4.32 Consider the systematic encoding process for the cyclic (7, 3) code using
g(x) = x4 + x3 + x2 &' * -/
encoding is done in two steps.
Switch 1
+ + + Information bits
B A
Switch 2
Encoded bits
We can also use a shift register circuit for dividing an arbitrary polynomial, a(x /# % ! # "
g(x). We assume here that the divisor is a monic polynomial. We already know how to factor out a scalar in
order to convert any polynomial to a monic polynomial. The division process can be expressed as a pair of
B D Q(r)(x) and R(r)(x / B ! # " " ! # "
rth recursion step, with the initial conditions Q(0)(x) = 0 and R(0)(x) = a(x B
be written as
Q(r)(x) = Q(r–1)(x) + R(n-r)xk–r
R(r)(x) = R(r–1)(x) – R(n-r)xk–rg(x) (4.32)
where R(n–r) ! " ! # " Fr G '
arbitrary polynomial a(x /# % ! # " g(x H ? n shifts,
B ! "
the shift register implementation of a decoder is very simple. The contents of the shift register can be checked
for all entries to be zero after the division of the received polynomial by the generator polynomial. If even a
single memory unit of the shift register is non-zero, an error is detected.
+ + + +
+ +
Example 4.34 The circuit for dividing by g(x) = x4 + x2 & ' 'K
+ +
Fig. 4.10 Circuit realisation for dividing by g(x) = x4 + x2 + 1.
Example 4.35 The shift register circuit for dividing by g(x) = x8 + x6 + x5 + x3 + x + 1 is given in
''
x x2 x3 x4 x5 x6 x7 x8
+ + + + +
!
a buffer. It is subjected to divide-by-g(x) operation. As we have seen, the division can be carried out very
# /# " "! ! /
(pre-computed) syndromes. This set of syndromes corresponds to the set of correctable error patterns. If a
syndrome match is found, the error is subtracted out form the received word. The corrected version of the
received word is then passed on to the next stage of the receiver unit for further processing. This kind of a
decoder is known as the * N '<
Received word
+ n – k stage shift register
Error word –1
+ Corrected word
Learning Review
YOU ARE NOW READY TO ATTEMPT THE FOLLOWING QUESTIONS LINKED TO LO 4:
1. Design a circuit for error detection for the binary cyclic (7, 3) code using M
g(x) = x4 + x3 + x2 + 1
2. P " ! # " 'Q M
! !' : ' ! ! : < >?@
in order to read in the information bits during the 1st !< : '
! : < >A@ /
next three shifts.
Switch 1
+ + Information bits
B A
Switch 2
Encoded bits
Fig. 4.13
!" " #
$% & '
structure formation in the code and (ii) the existence of elegant mathematical tools based on polynomials
!"#
The work on cyclic codes was further developed by Peterson and Kasami. Pioneering work on the minimum
$ % !&' *
+ $ , $ + , - /
chapter. It was soon discovered that almost all the LBCs discovered earlier could be converted to cyclic.
0 * !"! 1
2 2 + +
1949.
Cyclic Codes ° 199
5 0 + 6
!&' 7 8 +6 : +6 %
LEARNING OUTCOMES
Y A polynomial is a mathematical expression f(x) = f0 + f1x + … + fmxm, where the symbol x is called the
f0, f1, … fm are the elements of GF(q fm is called the
7 fm π 0, then m is called the degree of the polynomial, and is denoted by deg f(x) ◊
*
Y The division algorithm states that, for every pair of polynomial a(x) and b(x) π 0 in F[x], there exists a
- q(x + - + r(x), the remainder, such that a(x) = q(x) b(x) + r(x),
where deg r(x) < deg b(x). The remainder is sometimes also called the residue, and is denoted by
Rb(x)[a(x)] = r(x).
Y
(i) Rf(x)[a(x) + b(x)] = Rf(x)[a(x)] + Rf(x)[b(x)], and
(ii) Rf(x)[a(x) ◊ b(x)] = Rf(x){Rf(x)[a(x)] ◊Rf(x)[b(x)]}
where a(x), b(x) and f(x) are polynomials over GF(q).
Y A polynomial f(x) in F[x] is said to be reducible if f(x) = a(x) b(x), where a(x), b(x) are elements of f(x)
and deg a(x) and deg b(x) are both smaller than deg f(x). If f(x) is not reducible, it is called irreducible.
A monic irreducible polynomial of degree at least one is called a prime polynomial.
!Y The ring F[x]/f(x f(x) is a prime polynomial in F[x].
!Y A code C in Rn is a cyclic code if and only if C
(i) a(x), b(x) Œ C fi a(x) + b(x) Œ C,
(ii) a(x) Œ C and r(x) Œ Rn fi a(x)r(x) Œ C.
!Y 1
(i) Take a polynomial f(x) in Rn.
(ii) Obtain a set of polynomials by multiplying f(x) by all possible polynomials in Rn.
(iii) The set of polynomials obtained as above corresponds to the set of codewords belonging to a
cyclic code. The block length of the code is n.
!Y Let C be a (n, k) non-zero cyclic code in Rn. Then,
/ - g(x) of the smallest degree in C,
(ii) the cyclic code C consists of all multiples of the generator polynomial g(x) by polynomials of
degree k – 1 or less.
(iii) g(x) is a factor of xn – 1.
(iv) The degree of g(x) is n – k.
!Y 1 + C, with generator polynomial g(x) = g0 + g1x + …+ grxr of degree r, the generator
matrix of given by
200 ° Information Theory, Coding and Cryptography
È g0 g1 ... gr 0 0 0 ... 0˘
Í0 g0 g1 ... gr 0 0 ... 0 ˙˙
Í
G= Í0 0 g0 g1 ... gr 0 ... 0 ˙ k = (n – r) rows
Í ˙
Í : : : ˙
ÍÎ 0 0 0 0 0 g0 g1 ... g r ˙˚
n columns
!Y 1 + C, with the parity check polynomial h(x) = h0 + h1x + …+ hkxk, then the parity check
matrix is given by
n columns
!Y xn – 1 = h(x)g(x), where, g(x) is the generator polynomial and h(x) is the parity check polynomial.
!Y An (n, k - F 0 m, co-prime with n, the polynomial
xmc(x) calculated mod xn – 1 is a codeword polynomial if c(x) is a valid codeword polynomial.
!Y An (n, k) linear code is called a proper shortened cyclic code if it is obtained by deleting m consecutive
places from an (n + m, k + m) cyclic code.
!Y * 1 G GF(q) with the generator polynomial
g(x) = (x2t–1 – 1)p(x), where p(x) is a prime polynomial over GF(q) whose degree m is not smaller than
t and p(x) does not divide x2t–1 J 0 1 n such that
g(x) divides xn J * 1 t or less.
!Y The generator polynomial of the 2
g1(x) = (x11 + x10 + x6 + x5 + x4 + x2 + 1), or
g2(x) = (x11 + x9 + x7 + x6 + x5 + x + 1).
!Y The generator polynomial of the 2
g1(x) = (x5 + x4 – x3+ x2 – 1), or
g2(x) = (x5 – x3 – x2– x – 1).
!Y S % 1 k-bit block of bits the (n, k %
encoder generates (n – k 0 - 1 5
!Y 5 U
- G
suited for such operations.
Cyclic Codes ° 201
V 1 +
(a) xn+1 + 1 (b) xn – 1 (c) xn /2 (d) x2n/3
VW 1 + X
(a) Rf(x)[a(x) + b(x)] = Rf(x)[a(x)] + Rf(x)[b(x)], and
(b) Rf(x)[a(x) ◊b(x)] = Rf(x){Rf(x)[a(x)] ◊ Rf(x)[b(x)]}
(c) Both (a) and (b)
(d) None of the above
4.3 Which of the following is true?
(a) A ring F[x]/f(x f(x) is a monic polynomial in F[x]
(b) A ring F[x]/f(x f(x) is a prime polynomial in F[x]
(c) A ring F[x]/(f(x ^ f(x) is a prime polynomial in F[x]
(d) None of the above
4.4 A code C in Rn is a cyclic code if and only if C
(a) a(x), b(x) Œ C fi a(x) + b(x) Œ C
(b) a(x) Œ C and r(x) Œ Rn fi a(x)r(x) Œ C
(c) Both (a) and (b)
(d) None of the above
4.5 The degree of g(x) is
(a) n – k + 1 (b) n + k + 1 (c) n – k – 1 (d) n – k
4.6 n
If x – 1 = h(x)g(x), where, g(x) is the generator polynomial, then the parity check polynomial would
be
(a) h(x) (b) g(x)h(x) (c) xn (d) x – 1
4.7 An (n, k) linear code is called a proper shortened cyclic code if it is obtained by deleting m consecutive
places from an
(a) (n – m, k + m) cyclic code (b) (n + m, k – m) cyclic code
(c) (n + m, k + m) cyclic code (d) None of the above
4.8 Which of the following is capable of correcting any combination of three or fewer random errors in a
block of 23 bits?
, 5 ,
% 2
202 ° Information Theory, Coding and Cryptography
For interactive quiz with answers, scan the QR code given here
Or
Visit [Link]
PROBLEMS
S V : + - G X
(i) {0000, 0110, 1100, 0011, 1001} over GF(2).
(ii) {00000, 10110, 01101, 11011} over GF(2).
(iii) {00000, 10110, 01101, 11011} over GF(3).
(iv) {0000, 1122, 2211} over GF(3).
(v) The q-ary repetition code of length n.
M 4.2 Construct the addition and multiplication table for
(i) F[x]/(x2 ^ G GF(2).
(ii) F[x]/(x2 ^ G GF(3).
: G X
S 4.3 Answer the following for polynomials over GF &
(i) How many distinct second-degree monic polynomials of the form x2 + ax + b (b π 0) exist?
(ii) How many distinct polynomials of the form (x q a)(x q b) exist?
S 4.4 List out all the irreducible polynomials over
(i) GF(2) of degrees 1 to 5.
(ii) GF(3) of degrees 1 to 3.
S V" 1 0 " 1
S V& 5 xn – 1 is a product of r distinct irreducible polynomials over GF(q). How many cyclic
codes of block length n over GF(q) exist? What can you comment on the minimum distance of
these codes?
S V# 1 x8 – 1 over GF(3).
(ii) How many ternary cyclic codes of length 8 exist?
, - j / X
M 4.8 Let the polynomial
g(x) = x10 + x8 + x5 + x4 + x2 + x + 1
be the generator polynomial of a cyclic code over GF(2) with block length 15.
1 G.
1 0 / H.
(iii) How many errors can this code detect?
(iv) How many errors can this code correct?
(v) Write the generator matrix in the systematic form.
D 4.9 Consider the polynomial
g(x) = x6 + 3x5 + x4 + x3 + 2x2 + 2x + 1
(i) Is this a valid generator polynomial for a cyclic code over GF(4) with block length 15?
1 0 / H.
(iii) What is the minimum distance of this code?
(iv) What is the code rate of this code?
(v) Is the received word v(x) = x8 + x5 + 3x4 + x3 + 3x + 1 a valid codeword?
204 ° Information Theory, Coding and Cryptography
S 4.10 Is g(x) = x10 + x7 + x6 + x4 + x2 + 1 a valid generator polynomial for a binary cyclic code with
n = 21? Why/why not?
M 4.11 Consider a binary cyclic code with n = 15 and a generator polynomial given by g(x) = x8 + x7 + x6
+ x4 ^ 1 h(x) and the parity check matrix.
D 4.12 An error vector of the form xi + xi+1 in Rn | 5
generated by the generator polynomial g1(x) = (x – 1)gH(x) is capable of correcting all double
adjacent errors, where gH(x) is the generator polynomial of the binary Hamming code.
S 4.13 Determine the burst error correction length for the cyclic code represented by the following
generator polynomial
g(x) = x13 + x10 + x7 + x6 + x5 + x4 + x2 + 1
S V V 5 0 1 n = LCM(2t – 1, qm – 1).
S V " 5 g(x) = (x11 + 1)(x6 + x ^ G 1 :
burst error correction length for this code?
S V & 5 G g(x) = x14 + x11 + x9 + x5 + x2 + 1 is capable of correcting a burst
error of length 5 or less.
S V # 5 n – k can detect a
fraction 1 – 2 – (n – k) + 1 of all burst patterns of length (n – k) + 1.
M 4.18 Design the shift register encoder and the Meggitt decoder for the code generated in Problem 4.9.
M 4.19 The code with the generator polynomial g(x) = (x23 + 1)(x17 + x3 + 1) is used for error-detection and
256
(i) How many random errors can this code correct?
(ii) How many burst errors can this code correct?
M V W' W+ W 2 G g(x) = x11 + x9 + x7 + x6 + x5 + x + 1.
row of the generator matrix for this code will be [1 0 1 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0]. The
WF 1
M 4.21 Consider a binary cyclic code with the generator polynomial g(x) and block length n.
(i) If (x + 1) is a factor of g(x), show that all codewords must be of even weight.
(ii) If (x + 1) is not a factor of g(x) and n is odd, show that the code must contain the all-one
codeword 111….1.
COMPUTER PROBLEMS
4.4 Consider g(x) = (x + 1)(xa + xb + 1). Let the codeword length, n, be a design parameter. Write a
a, b} such that g(x) has good double error detection capability
for large n.
V" : "+ W# 1 7
correct bursts of length 3 or less. What happens when you try to decode a received word with a burst
VX : !V#+ !V'j 1
What is the burst error correction length for this code?
4.6 Write a computer program to search for cyclic Hamming codes over GF(5). Is there a cyclic Hamming
code of block length n "& G 2 1 X
V# 7UUU j'W & %
g(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1.
(i) What error patterns can this code detect?
(ii) What is the burst error correction length for this code?
PROJECT IDEAS
4.1 : & ( ; < & )5
2 + 1 2 | G
W+ W 2 +& 2 G F
% 5 + G 5%
(i) probability of word error,
(ii) probability of bit error,
(iii) probability of undetected codeword error.
4.2 6 ) Consider a cyclic code with the generator polynomial g(x g(x)
as g ( x) = x g (1 x ).
* n-k
1 , G g(x) = x3 + x + 1.
*
5 g ( x) is also cyclic.
*
5 g(x) and g ( x) are the same.
G % G
g1(x) = (x11 + x10 + x6 + x5 + x4 + x2 + 1) and
g2(x) = (x11 + x9 + x7 + x6 + x5 + x + 1)
4.3 * ) Design a Meggitt Decoder that can handle both binary and ternary cyclic codes.
Comment on the computational complexity of this decoder. Assuming realistic values for each circuit
operation (addition, multiplication, comparison, shift register operation etc.) in mJ per operation, give
the average energy estimate for decoding (in mJ/bit).
4.4 = "& & ) Make a table of the weights of different codewords and how
/
$ W+ W 2
+& 2
$ "+ W# 1
G $ !V#+ !V'j 1
206 ° Information Theory, Coding and Cryptography