6.441 Transmission of Information April 4, 2005Lecture 13Lecturer: Madhu Sudan Scribe: Shaili JainThe lecture intro has been taken from Chung Chan’s notes.1 Break Up of Things We’ve SeenWe briefly summarize what we have seen so far in this course.1.1 Phase I: The Tools• Entropy• Mutual Information• AEP1.2 Phase II: Exercise in Compression• Source Coding and AEP• Kraft’s Inequality• Shannon, Huffman, Lempel-Ziv Coding1.3 Phase III• Channel Coding• Channel Capacity– Conditional probability distribution between X and Y models the channel– We used the ideas of random codign and maximum likelihood decoding– Joint AEP lets us say that we can get arbitrarily close to the channel capacity– Coding Theorem: For any discrete memoryless channel with capacity C, ∀R < C, there existsan encoding from {0, 1}Rn→ Xn, such that Perr= P rm∈{0,1}Rn,Channel[D(Channel(E(m)) 6=m] → 0– Converse: If R > C, then Perr→ 12 Error ExponentIn this lecture we show how to compute the error exponent over a binary symmetric channel using arandom code ensemble and using maximum likelihood decoding (the same as minimum distance decodingin this case).The general idea behind this lecture is based on the following facts: The probability of error of adiscrete memoryless channel decays exponentially with n for a fixed rate below capacity. As n becomeslarge, the error exponent is representative of the quality of the code. Computing the error exponentturns out to be easier and more insightful than computing the probability of error exactly.For the binary symmetric channel that has capacity, C = 1−H(p), we can write the error probabilityas follows: P r[Yn= w] ≥ pn= 2−n log1p13-1Our goal is to come up with a general expression, where we conclude for any transmission Perr>2−nEc(R), where Ec(R) is the error exponent. We are interested in how the error exponent Ec(R) behaves.If Ec(R) = 0, then we know that the channel is virtually useless. On the other hand, if Ec(R) = ∞,then the channel is perfect. We know that Ec(R) ≤ logc1p, ∀R > 0, ∀ encoding, ∀ decoding (for thebinary symmetric channel).Today we study lower bounds for the error exponent for a random code ense mble.Random Code For every m ∈ {0, 1}Rnpick E(m) uniformly and independently at random from{0, 1}n.Decoding Scheme We use Maximum Likelihood Decoding (MLD). Given y, output m that maximizesP r[y received|E(m) is transmitted].The channel c apacity for a binary symmetric channel is C = 1 − H(p).If R < C, then we know that R < 1 − H(p)Hence H(p) < 1 − R and p < H−1(1 − R).Let PR= H−1(1 − R).Clearly, PR> p, so we can choose a τ such that p < τ < PR.Type I error: 4(E(m), y) ≥ τ n (This is the number of errors in transmission).Pr[Type I error] → 0Type I I error: ∃ m06= m such that 4(E(m0), y) < τ · n, where 4 denotes distance. (This is thecase where y is to “close” to a codeword E(m0)).Pr[Type II error] → 0 provided that H(τ ) + R < 1We want a formula of the form:P r[Error with MLD of Random Code] ≤ 2−(...)·n2.1 Maximum Likelihood DecodingP r[y received|E(m) transmitted] = pd(1 − p)n−dLet 4(y, x) = the number of coordinates where x and y differ. Let d = 4(y, E(m)). The maximumlikelihood decoding method chooses the message m such that 4(y, E(m)) is minimized.Clearly, the MLD algorithm is unsuccessful if ∃m06= m such that 4(y, E(m0)) < 4(y, E(m))Now consider the following scenario: ∃τ, m0such that 4(y, E(m0)) ≤ τ n ≤ 4(y, E(m)). Notice thatthe first inequality denotes a Type II e rror and the second inequality denotes a Type I error.maxτ[P r[4(y, E(m0)) ≤ τ n ≤ 4(y, E(m)))]] ≤ P r[Decoding Error]≤ Σnτ n=0[4(y, E(m0)) ≤ τ n ≤ 4(y, E(m))]≤ (n + 1)maxτ{P r[4(y, E(m0)) ≤ τ n ≤ 4(y, E(m))]}Hence we analyze the expression: P r[4(y, E(m0)) ≤ τ n ≤ 4(y, E(m)))].P r[Type I error] = P r[4(y, E(m)) ≥ τ n] = Σni=τ nnipi(1 − p)n−i≈nτnpτ n(1 − p)n(1−τassuming that τ > p= 2−D(p||τ )nP r[Type II error] = 1 − (1 −2H(τ )n2n)2Rn−113-2Fix m0, P r[4(E(m0), y) ≤ τ n] =2H(τ )·n2nP r[Type II error] ≈ 1 − 1 + 2Rn·2H(τ )n2nsince R + H(τ ) < 1. Thus we can write the probability of a Type II error as:P r[Type II error ≈ 2−(1−H(τ )−R)·nP r[Type I and Type II error = P r[Type I error] · P r[Type II error]≈ 2−[D(τ ||p+1−H(τ )−R]·nNotice that 1 − H(τ) = D(τ ||12), so we can writeP r[Type I and Type II error] ≈ 2−[D(τ ||p)+D(τ ||12)−R]·nConclusion For a random code and maximum likelihood dec oding, Perr= 2−ERCE(R)·n, where ERCEwas derived to b e :ERCE(R) = minp≤τ ≤PR{D(τ||p) + D(τ ||12) − R}Which choice of τ ∈ (p, PR) minimizes D(τ ||p) + D(τ ||12)?We can find this by solving the following equation: D0(τ||p) = −D0(τ||12). We find that in this case,τ1−τ=√p√1−p. We find that whenτ1−τ=√p√1−p, D(τ||p) + D(τ ||12) = 1 − log(1 + 2pp(1 − p).A good reference for today’s lecture is a paper by Barg and Forney entitled “Random co des: Minimumdistances and error exponents” in IEEE Transactions on Information Theory in Sept