EE/Ma 127b Lecture 2March 28, 2007Copyrightc∞ 2007 by R. J. McElieceOutline• Introduction to Convolutional Encoders•Circuit Diagrams•State Diagrams•Trellis Diagrams•State Space Representation1Block Codes — Review• Encoder for an (n, k) block code C:u[1], u[2], . . . →Encoder→ x[1], x[2], . . . .• Here u[1], u[2], . . . is a sequence of k-dimensional infor-mation blocks of length k, and x[1], x[2], . . . is the corre-sponding sequence of n-dimensional code blocks wherex[i] = u[i]G,G being a k × n generator matrix for C.2Convolutional Encoding — Introduction• Encoder for an (n, k, m) convolutional code C.u[1], u[2], . . . →Encoder→ x[1], x[2], . . . .• u[1], u[2], . . . is a sequence of k-dimensional informationblocks , and x[1], x[2], . . . is the corresponding sequence ofn-dimensional code blocks .• The encoder also contains an m-dimensional memoryregister s[i]: Here s[i] = 0 for i ≤ 0.3Convolutional Encoding — State-Space Dynamics• There exists 4 matrices A, B, C, D such that• For i = 0, 1, . . .s[i + 1] = s[i]A + u[i]Bx[i] = s[i]C + u[i]DA : m × mB : k × mC : m × nD : k × n.4Example 1: FIR (2, 1, 2) Convolutional Encoders1[i + 1] = u[i]s2[i + 1] = s1[i]x1[i] = u[i] + s1[i] + s2[i]x2[i] = u[i] + s2[i]5Example 1, Continued.(s1[i + 1], s2[i + 1]) = (0, s1[i]) + (u[i], 0)(x1[i], x2[i]) = (s1[i] + s2[i], s2[i]) + (u[i], u[i])A =µ0 10 0∂, B =°1 0¢C =µ1 01 1∂, D =°1 1¢6Example 2: (2, 1, 2) encoder with feedback(s1[i + 1], s2[i + 1]) = (s1[i] + s2[i] + u[i], s1[i])(x1[i], x2[i])) = (u[i], s1[i] + u[i]).7Example 2, Continued.(s1[i + 1], s2[i + 1]) = (s1[i] + s2[i] + u[i], s1[i])(x1[i], x2[i])) = (u[i], s1[i] + u[i]).s[i + 1] = s[i]A + u[i]Bx[i] = s[i]C + u[i]DA =µ1 11 0∂, B =°1 0¢C =µ0 10 0∂, D =°1 1¢8Solving the State-Space Equations• “Time Domain” State-Space equations:s[i] = 0 for i ≤ 0s[i + 1] = s[i]A + u[i]B for i ≥ 0x[i] = s[i]C + u[i]D• z-Transforms:S(z) =Xi≥0s[i]z−iU (z) =Xi≥0u[i]z−iX(z) =Xi≥0x[i]z−i9Solving the State-Space Equations• Transforming the State-Space equations:s[i + 1] = s[i]A + u[i]B⇓zS(z) = S(z)A + U (z)Bx[i] = s[i]C + u[i]D⇓X(z) = S(z)C + U (z)D.10Summary• “Time Domain” State-Space equations:s[i + 1] = s[i]A + u[i]Bx[i] = s[i]C + u[i]D• “Frequency Domain” State-Space Equations:zS(z) = S(z)A + U (z)BX(z) = S(z)C + U (z)D.11Solving the State-Space EquationszS(z) = S(z)A + U (z)BX(z) = S(z)C + U (z)D.⇓S(z) = U (z)B(zIm− A)−1X(z) = U (z)°B(zIm− A)−1C + D¢• ThereforeG(z) = B(zIm− A)−1C + D.is the generator matrix corresponding to (A, B, C, D).12Example 1, a deeper lookA =µ0 10 0∂, B =°1 0¢C =µ1 01 1∂, D =°1 1¢B(zIm− A)−1C + D = (details omitted)=°1 + z−1+ z−21 + z−2¢13Example 2, a deeper lookA =µ1 11 0∂, B =°1 0¢C =µ0 10 0∂, D =°1 1¢14B(zIm− A)−1C + D = (details omitted)=°11+z21+z+z2¢=°11+z−21+z−1+z−2¢15Summary: The Two Encoders are Equivalent!G(z) =°1 + z−1+ z−21 + z−2¢.G(z) =°11+z−21+z−1+z−2¢16Outline• Convolutional Code Fundamentals• Generator Matrices for a Convolutional Code.• Canonical, Minimal, Systematic Generator Matrices17Block Code Fundamentals• An (n, k) linear block code C is a k-dimensional subspaceof Fn.• A generator matrix G for C is a k ×n matrix over F whoserowspace 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.18Convolutional Code Fundamentals• An (n, k) convolutional code is a k-dimensional subspaceof F (z−1)n.• Here F (z−1) is the field of rational functions (quotients ofpolynomials) 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 entriesin G(z) are all polynomials.• Every convolutional code has polynomial generator ma-trices. (Proof?)19Examples• 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¢.20There 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 elemen-tary row operations, or equivalently,G0= UG,where U is a k × k nonsingular matrix over F (z−1).21ExamplesG1(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.22Some More Generator Matrices 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!23A Good Question• Among all possible generator matrices, which ones arebest?• Canonical generator matrices.• Systematic generator