DOC PREVIEW
CALTECH EE 127 - Lecture notes

This preview shows page 1-2-20-21 out of 21 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

CALTECH EE 127 - Lecture notes

Download Lecture notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?