# Convolution codes I

Convol1.txt — Plain Text, 11 KB (12042 bytes)

## File contents

Convolution codes ================= Convolution codes are defined via their encoder which is a device for transforming input messages to code words being sent. Unlike in the case of block codes as we have seen them, the output, i.e., the sent message is a function not only of the current input, but also of earlier inputs. Often, the data sent at time t does not depend on all previous messages at times 0,...,t, but only on messages at times t, t-1, t-2, ..., t-M+1 for some fixed M called the *length of influence*. Moreover, convolution codes are still linear in the sense that if C(xs) denotes the encoding of an infinite sequence xs=x1,x2,... of inputs then C is a linear map on the vector space of infinite sequence (of 0s and 1s in the (typical) case of GF(2)). The main advantage of convolution encoders is their simple implementation. Unfortunately, their theory is not as advanced as for block codes; convolution codes with good error correction properties are found by exhaustive search and are tabulated. A (non-recursive) *convolution encoder* is determined by three parameters (n,k,M) where n and k are the sizes of the output and input per clock interval and M is the length of influence. In many cases one has k=1. In order to store the last M inputs which as we said determine the output the convolution encoder needs M shift registers capable of holding k bits each or M*k simple shift registers. The n output bits are a linear function of the last M inputs and are computed using appropriate additions modulo 2 implemented as XOR gates. n schliesslich ist die Zahl der pro Zeiteinheit gesendeten Ausgangsbits. The quotient r = k/n is the *rate* of the encoder; it must always be less than 1. Example for k=1, n=2 (r=1/2), M=2 --------->x1 | ---->(+)<---- | | | | u--o->[D]-o->[D]-o | | | | | | ---->(+)<---- | --------->x2 u is the input, x1 and x2 represent the output. Shift registers are denoted [D] ("delay") and (+) is addition modulo 2 (XOR). Finally, o represents a wire junction. If u(l), x1(l), x2(l) are the signal u,x1,x2 at time l then x1(l) = u(l) + u(l-2) x2(l) = u(l) + u(l-1) + u(l-2) Example: u = (1 0 0 1 1 ...) x1 = (1 0 1 1 1 ...) x2 = (1 0 1 1 0 ...) Formal power series ------------------- An entire signal is conveniently represented as a formal power series in the unknown D ("delay"), thus x1 = x1(0) + x1(1)D + x1(2)D^2 + ... One then has x1 = u * g1 x2 = u * g2 where g1 = 1 + D^2 and g2 = 1 + D + D^2 and where * is the product of power series: x * y = z(0) + z(1)D + z(2)D^2 + ... + z(k)D^k + ... where z(k) = sum_{i=0}^k x(i) y(k-i). Here, the sequence z is known as the *convolution* of sequences x and y, thus convolution of sequences corresponds to product of power series. As already mentioned convolution codes are usually defined through their encoder. Nevertheless, it is again sometimes useful to also regard the code as its set of codewords and without the encoder. Definition (formal power series): Let F be a field and D a variable. The ring F[[D]] of *formal power series comprises infinite sequences xs=(x_0,x_1,x_2,x_3,...), where x_i:F, though of and usually written as a power series x_0 + x_1*D+x_2*D^2+... They are added and multiplied according to the usual rules. The ring of polynomials F[D] is then a subring of F[[D]] consisting of those sequences xs for which x_k=0 for almost all k. Lemma: A polynomial p : k[D] is invertible in k[[D]] if and only if p(0)=/=0. Proof: W.l.o.g. let p(0)=1 (otherwise apply lemma to p/p(0)). One has 1 / p = 1 / (1 - (1-p)) = 1 + (1-p) + (1-p)^2 + (1-p)^3 + (1-p)^4 + ... (***) Now (1-p) is a multiple of D since (1-p)(0)=0 (no constant term). As a result, (1-p)^k has no powers of D less than k and one can expand (***) in terms of powers of D ("multiply out"). [] Example: p=1+D 1/p = 1 + (1-p) + (1-p)^2 + .. = 1 - D + D^2 - D^3 + D^4 Non example: p=D 1/p = 1 + (1-D) + (1-2D+D^2) + (1-3D+3D^2-D^3) + ... = ???? Remark: one can also consider the ring of formal Laurent series which also allow finitely many negative powers of D. This ring is actually a field, i.e., all elements other than 0 are invertible. Generator matrices for convolution codes ---------------------------------------- We can group the polynomials describing a convolution encoder into an nxk matrix, thus a column vector in the case k=1. The n-tuple of formal power series representing the output is then obtained as the product of the input (formal power series) with that matrix which is therefore called *generator matrix* by analogy with the situation for block codes. Example: the generator matrix of the convolution encoder given above is ( 1+D^2 ) G1 = ( ) (1+D+D^2) Example: The convolution encoder for the following generator matrix (1+D^2+D^3) G2 = ( ) ( 1+D+D^3 ) is ---------->(+)-->(+)--> | | | ----o->[D]-o-[D]-o-[D]-o | | | ---->(+)-------->(+)--> If one multiplies a generator matrix from the right with an invertible (in GF(2)[[D]]) matrix then one get another generator matrix and hence another convolution encoder which, however, generates the same code. The association input <-> code word becomes different but the error correction properties remain the same. Example: multiplying G1 from the right with 1+D yields (1+D+D^2+D^3) G3 = ( ) ( 1 + D^3 ) The matrices G1 and G3 describe the same convolution code but different encoders for that code. Unlike G1 the generator matrix G3 is *catastrophic* (technical term) in the sense that there exists an input of infinite weight, here (1 1 1 1 1 ...) =^= 1/(1+D), which is mapped to a codeword of finite weight here auf ein Codewort von endlichem Gewicht, hier (1+D^2,1+D+D^2) =^= (10100000..., 111000000....). Proposition: An n x 1 generator matrix is catastrophic iff its polynomials have a common irreducible factor different from D. Proof: Let g_1..g_n be the polynomials in the generator matrix. If g=/=D is a factor as in the statement of the proposition then g(0)=/=0 (if g(0)=0, then D divides g so by irreducibility g would be =D). Thus, g is invertible and the (infinite) input corresponding to that inverse yields a codeword of finite weight. Conversely, if a:GF(2)[[D]] \ GF(2)[D] is an input of infinite weight with finite codeword then let p_1,...,p_n be the polynomials corresponding to the (finite) codeword. One then has g_i*a = p_i for i=1..n thus D^u * a = s/t for appropriate coprime polynomials s and t where u:N and t(0)=/=0 (begin with s=g_1, t=p_1, cancel common factors and multiply by D "until" t(0)=/=0). Also, t cannot be constant for otherwise a would be finite. Now, any irreducible factor u of t (which cannot be D!) must divide g_i because D^u g_i s = p_i * t. [] One should avoid catastrophic generator matrices as they lead to problems with decoding. We conclude this section with an example of a (3,2,1)-convolution code: u1 x1 -------o---------------- u2 | x2 --o--------------------- | | | o-[D]- | | | x3 | ----(+)--------- | | ---- -[D]- Its generator matrix is (1 0) (0 1) (1+D D) Multiplication with (1 0) (subtracting the first column from the second) yields (1 1) the following alternative generator matrix (1 0) (0 1) (1 D) whose encoder needs one shift register less. Recursive convolution encoders ------------------------------ A recursive convolution encoder feeds some of its output back into the entry of its shift registers via an appropriate XOR logic. Example: --------------------------------> x1 | ----------->(+)--->(+)----> x2 | | | | u--o-(+)-o->[D]-o->[D]-o->[D]-o ^ | | |--------(+)<----------- Here we have: x1=u x2=(D^2+D^3)*s s=u + (D+D^3)*s with s representing the signal at the end of the first shift register. Rearranging yields: (1+D+D^3)*s = u s = 1/(1+D+D^3)*u x2 = (D^2+D^3)/(1+D+D^3) * u Notice that the denominator is indeed invertible. A non-invertible denominator could only occur with "short circuits", i.e., an XOR gate with delayless feedback. We thus have a generator matrix with rational entries, i.e., entries in GF(2)[[D]] rather than GF(2)[D]. ( 1 ) G4 = ( ) ( (D^2+D^3)/(1+D+D^3) ) As before, the code generated remains unchanged upon multiplication from the right with an invertible matrix. In particular, for every recursive convolution encoder there is a non-recursive one that generates the same code. In this example it is given by ( 1+D+D^3 ) G5 = ( ) ( D^2+D^3 ) Unlike the above recursive encoder this one is no longer "systematic" in the sense that the input is part of the output. Notice that this was the case for the recusive encoder. Conversely, using recursion, i.e., feedback, it is possible to convert any non-systematic convolution encoder into a systematic, albeit recursive, one. In the example ( 1+D^2 ) G1 = ( ) (1+D+D^2) this would be ( 1 ) G6 = ( ) (1+D+D^2 / (1+D^2)) -----------------------> | --->(+)-->(+)----> | | | | -o-(+)-o-[D]-o-[D]-o ^ | |<------------- Systematic convolution encoders are more suitable for certain applications. In particular, the *turbo codes* introduced in the 90s which can be regarded as the interleaved concatenation of two convolution codes rely on systematic convolution codes and thus use recursive encoders. Free distance of a convolution code ----------------------------------- Just as in the case of block codes the minimal weight of a codeword is a measure for the quality of a convolution code. Since convolution codes are linear it is clear that errors of smaller weight than that minimum can at least be detected. Definition (free distance): The free distance of a convolution code is the Hamming-weight of the lightest codeword. One can read off the free distance from a statechart representing a corresponding encoder as a Mealy machine, i.e., a finite automaton with output. For the generator matrix G1 this machine looks as follows: 0/00 ----- \ V [00] 0/11 ^ \ 1/11 / \ / 1/00 \ / -----> V [01] [10] ^ <----- / \ 0/01 / 0/10 \ / 1/10 \ V [11] / ^ ---- 1/01 The free distance then is the least weight of a finite path from [00] back to itself. Such a path is given by 11 01 11 of weight 5 and it corresponds to the input 1 0 0. It is easy to see that there is no lighter such path and thus this code has free distance 5. If the encoder is not catastrophic this method is guaranteed to find the free distance for the input leading to the minimum weight codeword must then be finite hence captured by the abovedescribed search. On the other hand, the catastrophic code given by (1+D) (1+D) has free distance 2 because 11 00 00 00 00 00 00 00 00 is output upon input 1 1 1 1 1 1 1... . No finite input can generate this output or any other of weight 2. Free distance is related to the quality of a convolutional code but does not have quite the same significance as for block codes because in practice coding is stopped after a finite amount of time and the encoding is restarted.

Document Actions