The lectures of this course are based on the first 11 chapters of Prof. Raymond Yeung’s textbook entitled Information Theory and Network Coding (Springer 2008). This book and its predecessor, A First Course in Information Theory (Kluwer 2002, essentially the first edition of the 2008 book), have been adopted by over 60 universities around the world as either a textbook or reference text. At the completion of this course, the student should be able to: 1) Demonstrate knowledge and understanding of the fundamentals of information theory. 2) Appreciate the notion of fundamental limits in communication systems and more generally all systems. 3) Develop deeper understanding of communication systems. 4) Apply the concepts of information theory to various disciplines in information science.
Chapter 7 - Section 7.1 A
Loading...
From the course by The Chinese University of Hong Kong
Information Theory
8 ratings
From the lesson
Chapter 7 Discrete Memoryless Channels - Part 1
Meet the Instructors
Prof. Raymond W. YeungChoh-Ming Li Professor of Information Engineering, and Co-Director, Institute of Network Coding
Chapter 7, Discrete Memoryless Channels.
[BLANK_AUDIO]
In this chapter, we will introduce two equivalent
models of a Discrete Memoryless Channel, or DMC.
We will discuss how to communicate reliably, through a DMC.
The capacity of a DMC.
[BLANK_AUDIO]
Shannon's channel coding theorem, both achievability and converse.
[BLANK_AUDIO]
The capacity of a DMC, in the presence of feedback.
[BLANK_AUDIO]
And finally, the separation theorem for source coding and channel coding.
We start with an informal discussion. First let
us take a look at the binary symmetric channel, or BSC.
[BLANK_AUDIO]
The BSC is the simplest channel model, with input
alphabet X equals {0,1}, and output alphabet Y equals
{0,1}. The parameters specifying the BSC,
epsilon, is called the crossover probability.
[BLANK_AUDIO]
The idea is that if we input a 0 to the channel, then with
probability 1 minus epsilon, we receive 0, and we call this a correct reception.
And with probability epsilon, we receive a 1, and we call this a crossover.
Likewise, if we input an 1, we will
receive 1, with probability 1 minus epsilon, and receive
0, with probability of epsilon.
[BLANK_AUDIO]
For this reason, epsilon is called the crossover probability.
That is, the probability that what we receive, is
not the same as what we input to the channel.
[BLANK_AUDIO]
Let us now take a look at a very simple code.
[BLANK_AUDIO]
For the sake of our discussion, assume that epsilon is strictly less than 0.5.
[BLANK_AUDIO]
We are going to transmit 2 possible messages, A and B, through the channel.
[BLANK_AUDIO]
In the first coding scheme, which we call Coding Scheme 1,
we encode A to 0, and B to 1, that is if
the message is A, then we transmit 0 through the channel, and
if the message is B, then we transmit 1 through the channel.
[BLANK_AUDIO]
For decoding, if the received symbol is equal
to 0, then we decode it to the message
A, and if the symbol received is equal to 1, then we decode it to the message B.
[BLANK_AUDIO]
A decoding error occurs if and only if a crossover occurs.
For example, if the message is A and we transmit a 0, and the received symbol
is 1, that is a crossover occurs, then we would decode incorrectly.
Therefore, the probability of error is
exactly equal to epsilon, the crossover probability.
[BLANK_AUDIO]
Now let us take a look at a more elaborate code, called a repetition code.
[BLANK_AUDIO]
For the simple code that we have looked at, the error
probability is equal to epsilon, which is not necessarily a small quantity.
To improve reliability, we use the BSC n times for a large n.
[BLANK_AUDIO]
Let N_0, denotes the number of zeros
received at output of the channel, after n transmissions.
And let N_1 denote the number of
ones received, at channel output, after n transmissions.
[BLANK_AUDIO]
Let us now look at the second coding scheme, called Coding Scheme 2.
In this coding scheme, the message A is encoded to a sequence of n 0's.
And the message B, is encoded to a sequence of n 1's.
[BLANK_AUDIO]
Decoding of this scheme is as follows: If N_0 is greater than N_1,
that is, there are more 0's received than 1's, then we decode to the message A.
On the other hand, if N_1 is greater than N_0, that is the number of 1 received,
is greater than the number of 0 received, then we decode to message B.
[BLANK_AUDIO]
If the message is A, by the weak law of large numbers,
N_0 would be approximately equal to n times one minus epsilon,
where 1 minus epsilon, is the probability of no crossover,
and N_1 would be approximately equal to n times epsilon,
with probability tends to 1, as n tends to infinity.
[BLANK_AUDIO]
Then N_0, would be greater than N_1,
with high probability, because epsilon is less than 0.5.
[BLANK_AUDIO]
Therefore, coding scheme 2 would decode correctly, with
probability tends to 1, if the message is A,
and similarly, if the message is B.
However, the coding rate of this code, which is equal to 1 over n
times log 2, because we used the channel n times to complete the transmission,
would tends to 0, as n tends to infinity.
In other words, the amount of information that can be transmitted per
use of the channel, would tends to 0, as n tends to infinity.
[BLANK_AUDIO]
Therefore, with Coding Scheme 2, while we can
make the scheme more and more reliable, by using
a larger and larger n, the coding rate
would become smaller and smaller and approach 0.
[BLANK_AUDIO]
In section 7.1, we define the discrete memoryless channel, and its capacity.
[BLANK_AUDIO]
We first introduce the 1st definition of a discrete memoryless channel.
[BLANK_AUDIO]
Such a channel has input random variable X
that takes values in a discrete alphabet X,
an output random variable Y that takes values in discrete output alphabet Y.
[BLANK_AUDIO]
The channel is specified by a transition matrix p(y|x) from X to Y.
And input-output relation is given by, the probability that
the input is x and the output is y,
is equal to, the probability that the input is x, times p(y|x).
[BLANK_AUDIO]
A BSC with crossover probability is a special case of a discrete channel.
With transition matrix p(y|x), such that
the diagonal elements, are equal to 1 minus epsilon,
and off diagonal elements are equal to epsilon.
[BLANK_AUDIO]
Definition 7.1 is the formal definition for Discrete Channel 1.
Let X and Y be discrete alphabets, and p(y|x)
be a transition matrix from X to Y.
A discrete channel p(y|x) is a single input, single output system,
with input random variable X taking values in X and output random variable
taking values in Y, such that the probability that X equals x,
and Y equals y, is equal to the probability that X
equals x times p(y|x), for all possible (x,y) pairs.
[BLANK_AUDIO]
We now introduce the next definition for a
discrete channel, which we call discrete channel 2.
[BLANK_AUDIO]
For such a channel, the input random variable X takes values in discrete
alphabet X, and output random variable Y, takes values in discrete alphabet Y.
[BLANK_AUDIO]
There is a noise variable Z, that takes values in discrete alphabet Z.
We assume that the noise variable Z,
is independent of the input random variable X.
[BLANK_AUDIO]
Alpha is a function that maps the input alphabet X,
and the noise alphabet Z, to the output alphabet Y.
[BLANK_AUDIO]
The channel is specified by the pair alpha Z.
[BLANK_AUDIO]
And the input output relation, is given by Y, the output random variable,
is equal to alpha of X, the input variable, and Z, the noise variable.
[BLANK_AUDIO]
Definition 7.2 is the formal definition of Discrete Channel 2.
Let X, Y, and Z be discrete alphabets.
Let alpha maps X times Z to
Y, and Z be a random variable, taking values in Z,
called the noise variable. A discrete channel alpha Z,
is a single input single output system,
with input alphabet X and output alphabet Y.
For any input random variable X,
the noise variable Z is independent of X, and the output random
variable Y is given by Y equals alpha of X and Z.
[BLANK_AUDIO]
We have introduced 2 definitions of a discrete
channel, namely discrete channel 1 and discrete channel 2.
And now we're going to show that these 2 definitions are indeed equivalent.
[BLANK_AUDIO]
First, if a channel can be modelled as a discrete channel 2, then it can also
be modelled as a discrete channel 1, and
this is obvious because, given a discrete channel 2,
specified by alpha and Z, we can simply
compute the transition matrix p(y|x)
and that would be a discrete channel 1,
which is equivalent to the given discrete channel 2.
[BLANK_AUDIO]
We now show that a discrete channel 1, can also be modelled as a discrete channel 2.
[BLANK_AUDIO]
The construction is as follows. First, for every input symbol
small x, define Z_x with the alphabet Z_x equals
Y, the output alphabet, such that the probability that Z_x
is equal to y, is equal to p(y|x),
where p(y|x) is the transition
probability of the given discrete channel 1.
Assume that the variables Z_x, for all x
are mutually independent, and also independent of the input variable X.
[BLANK_AUDIO]
Now define the noise variable Z, as the collection
of all Z_x, where x is an input symbol.
[BLANK_AUDIO]
Let the output variable Y, be Z_x if the input X is equal to small x.
In other words, the output chooses Z_x if the input is x.
Then the output variable Y is a function
of the input variable, and the noise variable.
So that we can write Y equals alpha of X comma Z.
[BLANK_AUDIO]
Now, we check that the discrete channel 2 so constructed,
is in fact equivalent to the given discrete channel 1.
Consider the probability that X is equal to x and Y is equal to y.
This is equal to the probability that X is equal to x, times
the probability that Y is equal to y, given X is equal to x.
[BLANK_AUDIO]
Now given that the input variable is small x, the output
variable Y, the output variable Y is equal to Z_x.
So this is equal to the probability that X is equal to x, times the
probability that Z_x, is equal to y, given X is equal to x.
[BLANK_AUDIO]
Because we assume that Z_x is independent of the input
variable X, we can drop the conditioning on X equals x.
And finally, the probability that Z_x is equal to y, by construction, is equal
to p(y|x). And so, we see that the discrete channel
2 that we have constructed, is indeed, the discrete channel 1, specified by
the transition matrix p(y|x).
[BLANK_AUDIO]
Definition 7.3 is about the equivalence of 2 discrete channels, one specified
as a discrete channel 1, and the other one specified by a discrete channel 2.
It says that 2 discrete channels p(y|x), and alpha Z,
defined on the same input alphabet X and output alphabet Y, are equivalent,
if the probability alpha of input small x, and noise
variable Z, is equal to an output symbol y, is equal to p(y|x),
for all x and y.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
