EE/Ma 127b Lecture 9April 16, 2007Copyrightc∞ 2007 by R. J. McElieceOutline• Fundamental Paths in Convolutional Codes• The Transfer Matrix Method for Counting Paths in Di-graphs• Bhatacharaya Union Bounds for Viterbi Decoding1EE/Ma 127b Lecture 15May 10, 2004Copyrightc 2004 by R. J. McElieceOutline• Fundamental Paths in Convolutional Codes• The Transfer Matrix Method for Counting Paths in Di-graphs• Bhattacharyya Union Bounds for Viterbi Decoding1Fundamental Code Paths• Acodepath starting and ending at state A (the all-zerosstate), but not involving the all-zeros loop, is called a fun-damental path,orF -path.0 01 0110 100110100101001112Weight Analysis of Convolutional Codes• How many F -paths of (output) weight W are there?ABCD221001113Weight Analysis of Convolutional Codes• We better get rid of the loop of weight 0 at A.ABCD22101114A Useful Trick• Even better, let’s split the initial vertex A:AABCD 12110215Counting the F -paths by Weight• Here we go:AABCD 1211021waW00102030405162......?6A General Problem: Weighted Path Enumeration in a Digraph1231• A digraph (V,E), V = {v1,...,vp}, E = {e1,...,eq}.• Each edge e ∈ E has an initial vertex init(e) ∈ V and afinal verex fin(e) ∈ V .7Weighted Digraphs123223• Each edge has a weight w(e).• The weight of a path Γ = e1e2···enis the product ofthe edge labels: w(Γ) = w(e1) ···w(en).8The Fundamental Problems• Given a weighted digraph, calculateφi,j[n]=Γw(Γ),where the sum is over all paths of length n from vito vj.• Also calculateφi,j=n≥0φi,j[n],the sum of the weights of all paths from vito vj.9The Transfer Matrix Method• Define the p × p adjacency matrix A =(Ai,j)byAi,j=ew(e),where the sum is over all edges e such that init(e)=viandfin(e)=vj.1232231231 0232 1103 12010The Geometry → Algebra TheoremTheorem. For any n ≥ 0, the (i, j)th entry of the matrixAnis φi,j[n]Proof: φi,j[n]=the flow from v1[0] to vj[n].v1v2v301234511The Transfer Matrix Method• Define the p × p transfer matrix F :F =(I − A)−1Theorem.[F ]i,j=n≥0φi,j[n]=φi,j.Proof:I + A + A2+ ···=(I − A)−1.12Solution to the Fundamental Problems• Given a weighted digraph:φi,j[n]=Γw(Γ) = [An]i,j.• Also:φi,j=n≥0φi,j[n]=[F ]i,j,whereF =(I − A)−1.13Back to Convolutional Codes.AABCD 1211021• We want path weights to be the sum of the labels, notthe product!14A Simple Trick.A1BCDxx2x2xx1xA0• Now the path weight = xW, where W is the Hammingweight of the path.15AVariation on the Theme.A0A1BCDx zx2 zx2 zx zx zzx z• Now the path weight = xWzL, where W is the Hammingweight of the path, and L is the length of the path.16Another Variation on the Theme.A0A1BCDx y x2 x2yx y x y x • Now the path weight = xWyV, where W is the outputHamming weight of the path, and V is the input Hammingweight of the path.17Summary• Let’s denote by Φ the sum of the weights of all fundamen-tal paths.Φ(x):ifthe weight is xW.Φ(x, z):ifthe weight is xWzL.Φ(x, y):ifthe weight is xWyV....18An Example of Φ(x)A1BCDxx2x2xx1xA0A(x)=bcdb 0 xxc 0 xxd 100.19Doing the MathI3− A(x)=1 −x −x01− x −x−10 1.(I3− A(x))−1=11 − 2x1 − xx xx 1 − xx1 − xx1 − x[(I3− A(x))−1]b,d=x1 − 2x20Output Weight EnumerationA1BCDxx2x2xx1xA0Φ(x)=x4x1 − 2x=x51 − 2x= x5+2x6+4x7+ ···• Therefore there are 2W −5paths of weight W , for W ≥ 5.21Application: First Branch Error Probability1232112PE,1≤WaWγw,=Φ(γ)where aW=numberofF -paths of output weight W .22An Example of Φ(x, z)A0A1BCDx zx2 zx2 zx zx zzx zA(x, z)=bc db 0 xz xzc 0 xz xzdz00.23Doing the MathI3− A(x, z)=1 −zx −zx01− zx −zx−z 01.(I3−A(x, z))−1=11 − xz − xz21 − xz xz xzxz21 − xz2xzz − xz2xz21 − xz[(I3− A(x, z))−1]b,d=xz1 − xz − xz224Output Weight - Length EnumerationA0A1BCDx zx2 zx2 zx zx zzx zΦ(x, z)=x4z2xz1 − xz − xz2=x5z31 − xz − xz2=x5z31 − xz(1 + z)= x5z3+ x6(z4+ z5)+x7(z5+2z6+ z7)+···25Application: Branch Error ProbabilityLetΦ(x, z)=W,LAW,LxWzL.Then∂Φ(x, z)∂zz=1=W,LLAW,LxW=WbWxw.where bW= total length of all F -paths of output weight W .26Application: Branch Error Probability1232112LetΦ1(x)=∂Φ(x, z)∂zz=1ThenPE≤ Φ1(γ)=WbWγw,27An Example of Φ(x, y)A0A1BCDx y x2 x2yx y x y x A(x, y)=bcdb 0 xy xc 0 xy xdy00.28Doing the MathI3− A(x, y)=1 −xy −x01− xy −x−y 01....[(I3− A(x, y))−1]b,d=x1 − 2xy29Output Weight – Input Weight EnumerationA0A1BCDx y x2 x2yx y x y x Φ(x, y)=x4yx1 − 2xy=x5y1 − 2xy= x5y +2x6y2+4x7y3+ ···30Application: Bit Error ProbabilityLetΦ(x, y)=W,VAW,VxWyV.Then∂Φ(x, y)∂yy=1=W,VVAW,VxW=WcWxw.where cW= total input weight of all F -paths of outputweight W .31Application: MLD Bit Error Probability1232112Pb≤1k∂Φ(x, y)∂yx=γy=1=WcWγw=Φ2(γ),where cW=(1k) times the total input weight of the F -pathsof output weight W .32SummaryΦ(x)=x51 − 2x= x5+2x6+4x7+8x8+ ···Φ1(x)=3x5− 3x6(1 − 2x)2=3x5+9x5+24x7+60x8+ ···Φ2(x)=x5(1 − 2x)2= x5+4x6+12x7+32x8+ ···For W ≥ 5;aW=2W −5bW=2W −5(3W − 9)/2cW=2W −5(W −