EE/Ma 127b Lecture 4April 1, 2007Copyrightc∞ 2007 by R. J. McElieceOutline• The free distance of a convolutional code.• How to calculate dfreefor a particular convolutional code.• An upper bound on dfreefor an arbitrary (n, k, m) convo-lutional code.1The Free Distance of a Convolutional Code• A block code has a minimum distance:Definition. The minimum distance of an (n, k) linear blockcode is the minimum Hamming weight among all nonzerocodewords.• A convolutional code has a free distance.Definition. The free distance of a convolutional code is theminimum weight among all polynomial codewords.2Example 1• The (2, 1, 2) code, described by the generator matrixG =°1 + w + w21 + w2¢=°1 1¢+ w°1 0¢+ w2°1 1¢• The general polynomial codeword is a finite linear combi-nation ofG, wG, w2G, . . .3What is the Free Distance?• The general polynomial codeword is a finite linear combi-nation of the rows of the matrix below:1 1 w w w2w2w3w3u01 1 1 0 1 1u11 1 1 0 1 1u21 1 1 0 1 1u31 1 1 0 1 1...4Example 2• The (4, 2, 1) code described by the generator matrixG =µ1 1 1 10 1 + w w 1∂=µ1 1 1 10 1 0 1∂+ wµ0 0 0 00 1 1 0∂• The general polynomial codeword is a finite linear combi-nation ofg1, g2, wg1, wg2, w2g1, w2g2, . . .5What is the Free Distance ?• The general polynomial codeword is a finite linear combi-nation of the rows of the matrix below:1 1 1 1 w w w w w2w2w2w2u01 1 1 1u10 1 0 1 0 1 1 0u21 1 1 1u30 1 0 1 0 1 1 0u41 1 1 1u50 1 0 1...6An Algorithm for Finding the Free Distance of C• Start with a canonical generator matrix G(w) for C.• Using G(w), construct a state diagram for C• Label the edges in the state digram with the correspondingoutput weight.• Delete the “All–Zeros” edge.• Replace multiple edges with a single edge, whose label isthe min of the labels of the multiple edges.• dfreeis the weight of the shortest path from0 · · · 0to0 · · · 0.7Example 1: G =°1 + w + w21 + w2¢dfree= 58Example 2: G =µ1 1 1 10 1 + w w 1∂dfree= 49How large can the Free distance be?• Let C be an (n, k, m) convolutional code. How large candfreebe?• Let CLbe the set of polynomial codewords of C of degree≤ L. This is a binary linear code of length n(L + 1), anddimension δL.• Thus dfreecannot exceed the largest posssible minimumdistance for a (n(L + 1), δL) block code.• But what is δL?10Example 1: The (2, 1, 2) Code1 1 w w w2w2w3w3w4w41 1 1 0 1 11 1 1 0 1 11 1 1 0 1 11 1 1 0 1 1...• Here δ0= δ1= 0, δ2= 1, δ3= 2, δ4= 3, . . .11Example 2: The (4, 2, 1) Code.1 1 1 1 w w w w w2w2w2w21 1 1 10 1 0 1 0 1 1 01 1 1 10 1 0 1 0 1 1 01 1 1 10 1 0 1...• Here δ0= 1, δ1= 3, δ2= 5, . . .12The Hilbert Series for δLTheorem. If C is an (n, k, m) convolutional code with For-ney indices (e1, . . . , ek) and polynomial subcode dimensionsδ0, δ1, . . ., thenXL≥0δLtL=1(1 − t)2kXi=1tei.13Examples• The (2, 1, 2) code (Forney Index 2):t2(1 − t)2= t2+ 2t3+ 3t4+ · · ·• The (4, 2, 1) code (must have Forney indices (0, 1))::1 + t(1 − t)2= 1 + 3t2+ 5t3+ · · · .14ProofProof: Note that by the “polynomial out implies polyno-mial in” and “predictable degree” properties, gi(w)wjis abasis vector for CLiff deg gi+ j ≤ L, i.e., L ≥ ei+ j.ThereforeXL≥0δLtL=kXi=1Xj≥0(tei+j+ tei+j+1+ · · ·)=kXi=1Xj≥0tei+j1 − t=kXi=1tei(1 − t)215Corollary 1: An Explicit Formula for δLCorollary 1.δL=kXi=1max(L + 1 − ei, 0).Proof: By the negative binomial theorem, (1 − t)−2=Pj≥0(j+1)tj. Applying this to the Hilbert series, we obtain16Proof of Corollary 1, continued.XL≥0δLtL=kXi=1tei(1 − t)2=kXi=1Xj≥0(j + 1)tei+j=kXi=1Xj≥ei(j + 1 − ei)tj.Thus the coefficient of of tLin the Hilbert series isPki=1max(L + 1 − ei, 0), as advertised.17Corollary 2: A Useful Bound on δLCorollary 2.δL≥ (L + 1)k − m.Proof: Use max(x, 0) ≥ x, and e1+ · · · + ek= m inCorollary 1.18Finally, an upper bound on dfreeTheorem. If C is an (n, k, m) convolutional code,dfree≤ minL≥0∆((L + 1)n, (L + 1)k − m)),where ∆(n, k) is the largest possible minimum distance ofan (n, k) linear block code.Proof: CLis a ((L + 1)n, δL) block code, and so dfreeis ≤the minimum distance of the best ((L + 1)n, (L + 1)k − m)block code.19Example 1• (n, k, m) = (2, 1, 2).• (n(L + 1), k(L + 1) − m) = (2L + 2, L − 1).dfree≤ ∆(2, 0), ∆(4, 0), ∆(6, 1), ∆(8, 2), ∆(10, 3), . . .= 1, 1, 6, 5, 5, . . .• Therefore the (2, 1, 2) code with dfree= 5 is optimal.20Example 2• (n, k, m) = (4, 2, 1).• (n(L + 1), k(L + 1) − m) = (4L + 4, 2L + 1)dfree≤ ∆(4, 1), ∆(8, 3), . . .= 4, 4, . . .• Therefore the (4, 2, 1) code with dfree= 4 is
View Full Document