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.
