6.441-8 Channel capacity, binary symmetric and erasure channels

LECTURE 8 Last time: Elias codes • Slepian-Wolf • Compression: pulling it together • Lecture outline Channel capacity • Binary symmetric channels • Erasure channels • Maximizing capacity • Reading: Reading: Scts. 8.1-8.3.Channel capacityWe describe a channel by a set of transition probabilities Assume a discrete input alphabet X and a discrete output alphabet Y The transition probabilities are: PYnXn(ynxn)||for all n Let us first restrict ourselves to discrete memoryless channels (DMCs), for which nPY n|Xn(y|xn)= �ni=1 PY |X(y[i]|x[i]) The capacity of a DMC channel is defined as C = maxPX (x) I(X; Y ) We’ll see later why this capacity is actualll achievable when we study the coding theorem Channel capacityChannel capacity for a DMC is also for any n> 1 1 maxPXn(xn) I(Xn; Yn)n Indeed, max I(Xn; Yn)PXn(xn)= H(Yn) − H(Yn Xn) n�|n� i=1 n� H(Y [i]|Yi−1) − H(Y [i]X[i])|==1in�H(Y [i]) −H(Y [i]X[i])≤=|=1in�i=1I(X[i]; Y [i])i=1Channel capacityThe inequality can be met with equality if we take the Xs to be independent, because the Y s then are also independent Moreover, by taking the Xs to be IID, then we can maximize the last RHS if we select the PMF of X that maximizes each term of the sum Thus, capacity of a DMC is the maximum average mutual information Binary Symmetric Channel (BSC)I(X; Y )= H(Y ) − H(YX) = H(Y ) − � |PX(x)H(Y |X = x) x=0,1 =1 − H(�) where H(�)= −(� log(�) + (1 − �) log(1 − �))Binary Erasure Channel (BEC)E indicator variable that is 1 if there is an error and is 0 otherwise C = max I(X; Y )PX (x)= max (H(Y ) − H(YX))PX (x) |= max (H(Y, E) − H(YX))PX (x) |= max (H(E)+ H(YX)) PX (x) |E) − H(Y |Binary Erasure Channel (BEC) H(E)= H(�) H(YE)|= P (E = 0)H(YE = 0)+ P (E = 1)H(YE = 1)||= (1 − �)H(X) H(YX)= H(�)|Thus C = maxPX (x)(H(Y |E)) = 1 − � Symmetric channelsLet us consider the transition matrix T the |X |×|Y| matrix whose elements are PY |X(y|x) A DMC is symmetric iff the set of outpuut can be partitioned into subsets such that for all subsets the matrix T (using inpuut as rows and outputs as columns) has the property that within each partition the rows are permutations of each other and the columns are permutations of each other �Maximizing capacityA set of necessary and sufficient conditions on an input PMF to achieve capacity over a DMC is that I(X = k; Y )= C for all k s.t. PX(k) > 0 I(X = k; Y ) ≤ C for all k s.t. PX(k)=0 where I(X = k; Y )⎛⎝PY X(jk)||PX(i)PY PY X(jk) log |=�i∈X|X(ji)|j∈Y|C is the capacity of the channel⎞⎠Maximizing capacityWe use the following theorem for the proof:Let f(α) be a concave function of α = (α1, . . . , αm) over the region R when α is a probability vector. Assume that the partial derivatives ∂f(α) are defined and continu⊭αk ous over R with the possible exception that limαk→0 ∂f(α) is allowed to be +∞. Then a ∂αk necessary and sufficient condition on α to maximize f over R is that: ∂f(α) = λ ∀k s. t. αk > 0∂αk ∂f(α) ≤ λ for all other αk∂αk Maximizing capacityI(X; Y ) = � PX(k)PY X(jk)||k∈X ,j∈Y⎛ PY X(jk) ⎞ log ⎝�i∈X PX|(i)P|Y |X(j|i)⎠ thus ∂I(X;Y ) = I(X = k; Y ) − log(e)= λ∂PX (k) Note that = k; Y )I(X; Y )= �k∈X s.t.PX (k)>0 PX(k)I(X so C = �k∈X s.t.PX (k)>0 PX(k)I(X = k; Y ) since all the I(X = k; Y ) are the same and their convex combination is C, each of them individually is C Symmetric DMC capacityConsider BSC If we take the inputs to be equiprobable, then we maximize H(Y ) H(YX = k) is the same for k =0, 1|For symmetric DMC, capacity is achieved by having equiprobable inputs Check: for symmetric DMC selecting all the inputs equiprobable ensures that every output has the same probability all of the H(YX = k) are equal |since we have the same set of transition probability values, albeit over different outpuut �Symmetric DMC capacity Another view: I(X = k; Y )⎛ ⎜⎝⎞ ⎟⎠PY X(jk) �i∈X||PY X(j|k) log=|1 |X | PY X(ji)||j∈Ywithin a partition of outputs, each column of the T matrix is a permutation of each other column thus, all I(X = k; Y ) are the same DMC capacityWhat about channels that are not symmetriic All inputs may not be useful, but all outputs are For any capacity-achieving input probabilitty the output probabilities are all positive (for reachable outputs) For some PX(k) = 0 (which must exist for there to be 0 probability outputs) �PY X (jk)��j∈Y PY |X(j|k) log P|Y (j)|≤ C but if there is PY (j) = 0, then LHS is ∞ DMC capacityThe output probability vector that achieves capacity is unique and all input probability vectors that give rise to the output vector yield capacity. Because of concavity of mutual information in input probability, if two input probabilitiie were capacity-achieving, then any convve combination would also be capacity-achieving Take a random variable Z to represent the value of θ For all values of Z, I(X; Y ) are the same (corresponding to convex combinations of optimal input distributions), so Y and Z are independent, so the PMF of Y does not depend on Z and is unique. DMC capacityLet m be the smallest number of inputs that can be used with non-zero probability to achieve capacity and let X be such a set of inputs. Then, for output alphabet Y, m ≤ |Y| and the input probability to achieve capacity using inputs in X only is unique. Proceed by contradiction. The output probabillitie can be expressed as the solution of the |Y| equations PX(x)PY X(y�x∈X ||x)= PY (y)∀y ∈Y (how about�x∈X PX(x) = 1? Sum over all the ys) and there exists at least one valid such PX(x) DMC capacityIf m> then there is a homogeneous|Y|solution with m The sum of the elements of this homogeneeou solution is 0, hence we can pick a sum of the solution to the equations and of a homogeneous solution (that sum is also a solution) so that one element is 0, which contradicts the fact that m is minimum The same line of reasoning yields uniqueneess The equations cannot have a homogenneou solution by the above argument, so the solution must be unique. MIT OpenCourseWarehttp://ocw.mit.edu 6.441 Information Theory Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.