6.441-12 Strong coding theorem, error exponents

LECTURE12 Last time: Strong coding theorem • Revisiting channel and codes • Bound on probability of error • Error exponent • Lecture outline Error exponent behavior • Expunging bad codewords• Error exponent positivity• Strong coding theorem • �Last time Ecodebooks[Pe,m] ≤ 2−N(E0(ρ,PX (x))−ρR) for E0(ρ, PX(x)) ⎡⎣⎤⎦1+ρ1� PX(x)PY X (yix)1+ρ− log=|⎛ ⎜⎝|y xNWe need to: get rid of the expectation over codes • by throwing out the worst half of the codes Show that the bound behaves well (ex₭ ponent is −Nα for some α> 0) Relate the bound to capacity • ⎞ ⎟⎠Error exponentDefine Er(R) = max0≤ρ≤1 maxPX (E0(ρ, PX(x)) −ρR) then Ecodebooks[Pe,m] ≤ 2−NEr(R)Ecodebooks,messages[Pe] ≤ 2−NEr(R)For a BSC: Expunge codewords The new Pe,m is bounded as follows: Pe,m 2.2−NEr(max0≤ρ≤1 maxPX (E0(ρ,PX (x))−ρlog(2M)))= N =2.2−NEr(max0≤ρ≤1 maxPX (E0(ρ,PX (x))−Nρ −ρlog(M)))N 4.2−NEr(max0≤ρ≤1 maxPX (E0(ρ,PX (x))−ρlog(M )))≤ 4.2−NEr(R) N = Now we must consider positivity. Let PX(x) be such that I(X; Y ) > 0, we’ll show that the behavior of Er is: Error exponent positivityWe have that: 1. E0(ρ, PX(x)) > 0, ∀ρ> 0 2. I(X; Y ) ≥ ∂E0(ρ,PX (x)) > 0, ∀ρ> 0∂ρ 3. ∂2E0(ρ,PX (x)) ≤ 0, ∀ρ> 0 ∂ρ2 We can check that I(X; Y )= ∂E0(ρ,PX (x)) ∂ρ |ρ=0 then showing 3 will establish the LHS of 2 Showing the RHS of 2 will establish 1 Let us show 3 Error exponent positivityTo show concavity, we need to show that∀ρ1,ρ2 ∀θ ∈ [0, 1]E0(ρ3, PX(x))≥ θE0(ρ1, PX(x)) + (1 − θ)E0(ρ2, PX(x))for ρ3= θρ1+ θρ2We shall use the fact thatθ(1+ρ1) (1−θ)(1+ρ2)+ =1 1+ρ3 1+ρ3 and H¨older’s inequality: �1 �x �1 �1−x �j cjdj ≤ �j cjx �j cj 1−x Let us pick θ(1+ρ3) θ cj = PX(j) 1+ρ3 PY X(kj)1+ρ3 (1−θ)(1+rho|2) |1−θ dj = PX(j) 1+ρ3 PY X(kj)1+ρ3 ||θ(1 + ρ1) x = 1+ ρ3 �Error exponent positivity Proof continued 1 PX(j)PY X(kj)1+ρ3 ||j∈Xθ(1+ρ1)1+ρ3≤× ⎛⎝⎛⎝⎞⎠1+ρ1� PX(j)PY |X(k|j)1 j∈X (1−θ)(1+ρ2)1+ρ3⎞⎠1+ρ2� PX(j)PY |X(k|j)1 j∈X ⇒⎛⎝⎞⎠1+ρ3||1+ρ3� PX(j)PY X(kj)1 j∈X⎛⎝⎛⎝≤×⎞⎠θ(1+ρ1)1+ρ1� PX(j)PY |X(k|j)1 j∈X 1+ρ2� PX(j)PY |X(k|j)1 j∈X ⎞⎠(1−θ)(1+ρ2)��Error exponent positivity Proof continued ⎛⎝⎞⎠1+ρ3||1+ρ3� PX(j)PY X(kj)1 ⇒k∈Yj∈X⎛⎝⎞⎠θ(1+ρ1)1+ρ1� PX(j)PY X(k|j)1 ≤×|k∈Y � PX(j)PY |X(k|j)1+1 ρ2 ⎛⎝j∈X⎞⎠(1−θ)(1+ρ2)j∈X�⎣⎡⎢k∈Y ⎤ ⎥⎦θ⎛⎝⎞⎠(1+ρ1)1+ρ1� PX(j)PY X(k|j)1 ≤|j∈X⎡ ⎢⎣⎤ ⎥⎦(1−θ)⎛⎝⎞⎠(1+ρ2)||1+ρ2� PX(j)PY X(kj)1 ×j∈X��Error exponent positivity Proof continued k∈Y ⎛ ⎜⎝⎞ ⎟⎠⎛⎝⎞⎠1+ρ31+ρ3� PX(j)PY X(kj)1 − log||j∈X 1+ρ1� PX(j)PY X(kj)1⎛⎝⎞ ⎟⎠⎞⎠(1+ρ1)≥−θ log⎛ ⎜⎝||k∈Y⎛⎝1+ρ2� PX(j)PY X(kj)1 j∈X⎞ ⎟⎠⎞⎠(1+ρ2)− (1 − θ)|⎛ ⎜⎝|j∈X⇒ E0(ρ3, PX) ≥ θE0(ρ1, PX) + (1 − θ)E0(ρ2, PX) so E0 is concave! Error exponent positivity Proof continued Hence, extremum, if it exists, of E0(ρ, PX)−∂E0(ρ,PX )ρR over ρ occurs at ∂ρ = R, which implies that ∂E0(ρ,PX ) ∂E0(ρ,PX )= I(X; Y )∂ρ |ρ=1 ≤ R ≤|ρ=0∂ρ is necessary for Er(R, PX) = max0≤ρ≤1[E0(ρ, PX)−ρR] to have a maximum We have now placed mutual information somewhere in the expression Critical rate is RCR is defined as ∂E0(ρ,PX ) ∂ρ |ρ=1 Error exponent positivityProof continued From ∂E0(ρ,PX )= R∂ρ we obtain ∂R = ∂2E0(ρ,PX ) ∂ρ ∂ρ2 Hence ∂R < 0, R decreases monotonically ∂ρ from C to RCR We can write Er(R, PX)= E0(ρ, PX) − ρ∂E0(ρ,PX ) ∂ρ for Er(R, PX)= E0(ρ, PX) − ρR (ρ allows parametric relation)then∂Er(R,PX ) ∂2E0(ρ,PX )= −ρ> 0∂ρ ∂ρ2 Error exponent positivity Proof continuedTaking the ratio of the derivatives, ∂Er(R,PX )=∂R −ρ Er(R, PX) is positive for R 0 ∂R2 ∂ρ2 thus Er(R, PX) is convex and decreasing in R over RCR