EE/Ma 127b Lecture 3March 30, 2007Copyrightc∞ 2007 by R. J. McElieceOutline• Convolutional Code Fundamentals• Generator Matrices for a Convolutional Code.• Canonical, Minimal, Systematic Generator Matrices• The Corresponding EncodersBlock Code Fundamentals• An (n, k) linear block code C is a k-dimensional sub-space of Fn.• A generator matrix G for C is a k × n matrix over Fwhose rowspace is C.• G can be used as an encoder: If u = (u1, . . . , uk) ∈ Fkis an information word, the corresponding codeword x =(x1, . . . , xn) ∈ Fnis given byx = uG.Convolutional Code Fundamentals• An (n, k) convolutional code is a k-dimensional sub-space of F (z−1)n.• Here F (z−1) is the field of rational functions (quotientsof polynomials) in the indeterminate z−1over F .• A generator matrix G for C is a k×n matrix over F (z−1)whose rowspace is C.• G(z) is called a polynomial generator matrix if the en-tries in G(z) are all polynomials.• Every convolutional code has polynomial generator ma-trices. (Proof?)Examples• Example: n = 2, k = 1. Here is a polynomial generatormatrix for a (2, 1) convolutional code over GF (2):G =°1 + z−1+ z−21 + z−2¢.• Here is another generator matrix for the same code:G0=°11+z−21+z−1+z−2¢.There are Lots of Possible Generator Matrices• If G is any generator matrix for C, any matrix G0whichis row-equivalent to G is also a generator matrix for C.• That is, G0can be obtained from G by a series of ele-mentary row operations, or equivalently,G0= UG,where U is a k × k nonsingular matrix over F (z−1).ExamplesG1(z) =√11+z−1+z−211+z−21+z−1+z−21+z−11+z−1+z−211+z−1+z−2z−1z−11z−1!.defines a (4, 2) convolutional code over GF (2). Clearingdenominators,G2(z) =µ1 1 + z−1+ z−21 + z−21 + z−1z−11 + z−1+ z−2z−21∂is a polynomial generator matrix for the same code.Some More GeneratorMatrices for the Same CodeG3=µ1 1 + z−1+ z−21 + z−21 + z−10 1 + z−1z−11∂G4=µ1 z−11 + z−100 1 + z−1z−11∂G5=µ1 + z−10 1 z−1z−11 + z−1+ z−2z−21∂G6=µ1 1 1 10 1 + z−1z−11∂G7=µ1 + z−10 1 z−11 z−11 + z−10∂G8=√1 011+z−1z−11+z−10 1z−11+z−111+z−1!A Good Question• Among all possible generator matrices, which ones arebest?• Canonical generator matrices.• Systematic generator matrices.• Minimal generator matricesGeneralizing the Definition of Degree• The degree of a vector of polynomials is the maximumdegree of any component. Example:deg°1 1 + z−1+ z−21 + z−21 + z−1¢= 2.• The degree of a polynomial matrix is the sum of therow degrees. Example:degµ1 1 + z−1+ z−21 + z−21 + z−10 1 + z−1z−11∂= 3.The Degree of a Convolutional Code• The degree of a convolutional code is the minimumdegree of any polynomial generator matrix for C.Notation. An (n, k) convolutional code whose degree ism is called an (n, k, m) convolutional code• A minimum degree polynomial generator matrix iscalled a canonical generator matrix.Canonical Generator Matrices• There are efficient algorithms for computing canonicalgenerator matrices. We will not cover this.• But there is an easy test for canonicity:Theorem. A polynomial generator matrix is canonicaliff it is basic and reduced .• Basic: The gcd of the k × k minors is 1.• Reduced: The indicator matrix G for the highest degreeterms in each row has rank k.Basic and/or Reduced?• Examples:G4=µ1 z−11 + z−100 1 + z−1z−11∂G5=µ1 + z−10 1 z−1z−11 + z−1+ z−2z−21∂G6=µ1 1 1 10 1 + z−1z−11∂G4is Basic but not reducedG4=µ1 z−11 + z−100 1 + z−1z−11∂.∆1,2= 1 + z−2, ∆1,3= z−1, . . . .G =µ0 1 1 00 1 1 0∂.G5is Reduced but not BasicG5=µ1 + z−10 1 z−1z−11 + z−1+ z−2z−21∂.∆1,2= 1 + z−3, ∆1,3= z−1+ z−2+ z−3, . . . .G =µ1 0 0 10 1 1 0∂.G6is Reduced and BasicG6=µ1 1 1 10 1 + z−1z−11∂.∆1,2= 1 + z−2, ∆1,3= z−1, . . . .G =µ1 1 1 10 1 1 0∂.Canonical generator Matrices are Not Unique• Example:G6=µ1 1 1 10 1 + z−1z−11∂G06=µ1 1 1 11 z−11 + z−10∂both canonical.Important Property I ofCanonical Generator Matrices“The Forney Indices”• If G(z) and G0(z) are two canonical generator matricesfor C, thendeg gi(z) = deg g0i(z) for i = 1, . . . , n,i.e., the list of row degrees is the same for any canonicalgenerator matrix.• These row degrees are called the Forney indices of thecode.Important Property I ofCanonical Generator Matrices• For Example,G6=µ1 1 1 10 1 + z−1z−11∂G06=µ1 1 1 11 z−11 + z−10∂The Forney indices are (0, 1).Important Property II ofCanonical Generator Matrices“The Predictable Degree Property”• If u(z) =°u1(z) · · · uk(z)¢is a vector of polynomi-als, and x(z) = u(z)G(z), i.e.,x(z) =X1≤i≤kui(z)gi(z)Thendeg x(z) = max1≤i≤k°deg ui(z) + deg gi(z)¢.• (Any reduced generator matrix has this property.)Important Property III ofCanonical Generator Matrices“Polynomial Out → Polynomial In”• If u(z)G(z) is a polynomial vector, then so is u(z).• (Any basic generator matrix has this property.)Examples• The following GM does not have the predictable degreeproperty.G =µ1 w 1 + w 00 1 + w w 1∂.• The following GM does not have the POPI property:G =°1 + w31 + w + w2+ w3¢.Important Properties ofCanonical Generator Matrices...• The set of row degrees is the same for any canonicalgenerator matrix.G6=µ1 1 1 10 1 + z−1z−11∂G06=µ1 1 1 11 z−11 + z−10∂These row degrees are called the Forney indices of thecode, in this case (0, 1).Important Properties ofCanonical Generator Matrices• The predictable degree property. Ifu(z) =°u1(z) · · · uk(z)¢,andG(z) =g1(z)...gk(z),u(z)G(z) =X1≤i≤kui(z)gi(z)deg u(z)G(z) = max1≤i≤k°deg ui(z) + deg gi(z)¢.The Realizability TheoremTheorem. An (n, k, m) convolutional code C possessesan encoder which uses exactly m delay elements . Noencoder for C has fewer than m memory elements.Definition. An encoder that uses exactly m memoryelements is called a minimal encoder.One Way to Construct a Minimal EncoderA minimal encoder can be realized via a canonical genera-tor matrix in the “obvious way” (direct form realization).(1 + z−1+ z−2, 1 + z−2)Canonical GeneratorMatrix → Minimal EncoderG6=µx1x2x3x4u11 1 1 1u20 1 + z−1z−11∂Non-Canonical GeneratorMatrix → Minimal EncoderG4=µx1x2x3x4u11 z−11 + z−10u20 1 + z−1z−11∂Systematic Generator