Explore
For Enterprise
Join for Free
Log In

Arts et humanités
Business
Informatique
Science des données
Technologies de l'information
santé
Mathématiques et logique
Développement personnel
Sciences physiques et ingénierie
Sciences sociales
Apprentissage des langues
Diplômes
Certificats

Explorez l'intégralité de Coursera

Parcourir
Rechercher
For Enterprise
Connexion
Inscrivez-vous gratuitement

Chapter 7 - Section 7.1 A

Loading...

Théorie de l'information

Université chinoise de Hong Kong

4.7 (20 notes) | 5K étudiants inscrits

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.

Visualiser le programme de cours

Avis

4.7 (20 notes)

5 stars
16 ratings
4 stars
2 ratings
3 stars
1 ratings
1 star
1 ratings

À partir de la leçon

Chapter 7 Discrete Memoryless Channels - Part 1

Chapter 7 - Section 7.1 A14:54

Chapter 7 - Section 7.1 B18:42

Enseigné par

Prof. Raymond W. Yeung
Choh-Ming Li Professor of Information Engineering, and Co-Director, Institute of Network Coding

Transcription

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.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play

Coursera
À propos
Direction
Carrières
Catalogue
Certificats
Certificats MasterTrack™
Diplômes
For Enterprise
For Government

Communauté
Learners
Partners
Developers
Beta Testers
Translators

Se connecter
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Blog Tech

Plus
Conditions
Confidentialité
Aide
Accessibilité
Presse
Contact
Répertoire
Filiales