Convolutional decoding through a tracking problem

XX Congreso de Ecuaciones Diferenciales y Aplicaciones X Congreso de Matem´ atica Aplicada Sevilla, 24-28 septiembre 2007 (pp. 1–??) Convolutional decoding through a tracking problem Jos´ e Ignacio Iglesias Curto1,2, Uwe Helmke1 1Mathematisches Institut, Universit¨at Wrzburg. 2Dpto. de Matem´aticas, Universidad de Salamanca E-mails: [email protected],[email protected]. Resumen Convolutional codes can be regarded as discrete time linear systems. This relationship has been studied along decades, and concepts from both theories have found their counterparts into the other one. In this context, decoding of a received word can be interpreted as a tracking problem. This should allow to give practical decoding algorithms for convolutional codes. However, coding theory is usually studied over finite fields while optimal control problems have been considered over the real or complex fields. The solutions to these problems are not applicable as they make use of an Euclidean metric in which finite fields lack. We state a tracking problem over finite fields using the Hamming metric instead of a bilinear quadratic form, and we propose a solution via block decoding. In particular, we focus on the tracking problem associated to a convolutional decoding problem, which leads to a method for decoding general convolutional codes. Under some conditions, a bigger number of errors than half the minimum distance can be corrected. 1. Introduction Optimal control problems are usually considered over the fields of real or complex numbers. However there are problems that can be formulated in terms of linear systems defined over a finite field. Examples of that arise in coding theory, in particular in convolutional coding. It is a well known fact that a convolutional code can be interpreted in several ways as a linear dynamical system xt+1 =Axt+But yt=Cxt+Dut defined over a finite field. Accordingly several results from linear systems theory have found their counterparts in convolutional coding theory, leading to a few constructions of codes and a better understanding of their properties. 1 Jos´e Ignacio Iglesias Curto, Uwe Helmke In particular, we emphasize that the decoding process can be interpreted in terms of systems theory in at least two ways [4]. On the one hand, it can be viewed as a tracking problem, where the decoder should track the received message by the most probable codeword sent. On the other hand, it can be considered as a filtering problem, where the decoder is requested to filter the noise introduced by the channel. Here, we will focus on the first one. We consider well known optimal control problems over finite fields where we, as an initial step, transfer known results over infinite fields to problems posed over finite fields, for example those related with the construction and decoding of convolutional codes. In particular we will focus on a tracking problem and the decoding of general convolutional codes. In section 2 we consider a tracking problem. We first present the classical case and we discuss why it cannot be directly applied to the finite fields context. Then, we set the problem over a finite field for a finite input sequence and we present our solution. In section 3 we focus on the convolutional decoding process as a tracking problem (which will be addressed as an infinite process). A Receding Horizon solution will be applied to this problem. As a result, we obtain a decoding method for general convolutional codes. 2. The tracking problem over a finite field Consider a discrete-time linear system xt+1 =Axt+But yt=Cxt xt0=x0 (2.1) A classical tracking problem is stated in the following way: Given a sequence {˜yt}T t0, find an input sequence {ut}T t0that minimizes the cost function J(x0, u(·), T) = T X t=t0 [u> tRut+ (yt−˜yt)>Q(yt−˜yt)] with Rand Qpositive and nonnegative definite matrices respectively of the appropriate dimensions. This is a well known problem, studied over the real and complex numbers [1, 2]. However, its solution is not applicable for convolutional decoding. Convolutional codes are usually defined over a finite field F, while the solutions of tracking problems over infinite fields make use of an Euclidean inner product which is not defined over finite fields. Over finite fields the metric considered is the one induced by the Hamming distance. We restate the problem so that it makes sense over a finite field. For that, let’s consider the linear system (2.1), where A,B,Care constant matrices, xt∈Fn,ut∈Fk,yt∈Fp and Fis any finite field. Problem 2.1. Given a sequence {˜yt}T t0, find an input sequence {ut}T t0for the system (2.1) 2 Convolutional decoding through a tracking problem that minimizes the cost function J(x0, u(·), T) = T X t=t0 [w(Rut) + w(Q(yt−˜yt))] =w(QCx0−Q˜yt0) + T−1 X t=t0 [w(Rut) + w(QCxt+1 −Q˜yt+1)] + w(RuT). Here w(x) denotes the Hamming weight of the vector xand Qand Rare constant matrices of appropriate dimensions, Rwith maximum rank. Remark 2.2. In the classical tracking problem, the matrices Qand Rin the cost function are nonnegative and positive definite, respectively. This means that for a non-zero vector ut(resp. yt−˜yt), the corresponding term in cost function will always increase (resp. will not decrease) the sum. As the Hamming weight takes values in the non-negative integers (and in particular zero only for the zero vector), to have the same notion in our case, we should impose that Ru is non-zero for every non-zero vector u(i.e. Rhas maximum rank) while no condition is required on Q(yt−˜yt). A brute force solution given by checking all the possible sequences is infeasible unless Tis very small. To solve it efficiently, we note that the last term of the sum is minimized just with uT= 0, and we can write the cost function as J(x0, u(·), T) = w(QCx0−Q˜yt0) + T−1 X t=t0 [w(Rut) + w(QCxt+1 −Q˜yt+1)] =J(x0, u(·), T −1) + w(RuT−1) + w(QCxT−Q˜yT) As x0is known, the first term of the sum is fixed, J(x0, u(·), t0) = w(QCx0−Q˜yt0). So we are in a position to make use of a well-known optimality principle: Bellman’s optimality principle [3]: An optimal trajectory, has the property that at an intermediate point, no matter how it was reached, the rest of the trajectory must coincide with an optimal trajectory as computed from this intermediate point as the initial point. This allows to reduce the overall minimization problem to a sequence of single-stage minimizations of the expressions w(Rut) + w(QCxt+1 −Q˜yt+1). We have QCxt+1 =QCAxt+QCBut and we can group the known terms at time tas zt=QCAxt−Q˜yt+1. So, we can pose generically the single-stage minimization problem as: find a vector uthat minimizes the expression w(Ru) + w(QCBu +z). 3 Jos´e Ignacio Iglesias Curto, Uwe Helmke Let us now consider the vector and the matrix z0= (z1, . . . , zn,0,k . . ., 0)>B1=QCB R so that z0+B1u= (z+QCBu, Ru), and w(z0+B1u) = w(Ru) +w(QCBu +z). Then, the problem is equivalent to finding the vector of minimum weight in the coset {z0+B1u}u. Let us consider the block code generated by B1,CB1, and z0=e+B1vas a received word, with B1va codeword and ethe error. These cosets are equal {z0+B1u}u={e+B1(u+v)}w=u+v and the vector with minimum weight is e. So, finding the vector z0+B1uof minimum weight is equivalent to decode z0as a codeword from the code CB1. This can be done with an appropriate decoding algorithm. Note that in all iterations the code to consider (and as a result also the decoding algorithm) will be the same. We can summarize the solution process in the next algorithm. Algorithm 2.3. Calculate J(x0, u(·), t0) = w(QCx0−Q˜yt0). For every t,t0≤t < T •Use a block decoding algorithm to decode z0 t= (zt,0) as a codeword from the code CB1, obtaining vtas the information word. •Update ut=−vt,xt+1 =Axt+But,J(x0, u(·), t + 1) = J(x0, u(·), t) + w(Rut) + w(QCxt+1 −Q˜yt+1). The solution is {ut0, . . . , uT−1,0}and the optimal value J(x0, u(·), T ). We can just give an upper bound for the optimal value of the cost function, which will depend on the covering radius ρB1of the code CB1. Definition 2.4. The covering radius ρCof a code Cis the maximum distance from any vector of Fnto its nearest codeword. Theorem 2.5. Let ρB1be the covering radius of the code CB1and u∗an optimal solution to problem 2.1. Then the optimal cost is upper bounded as J(x0, u∗, T )≤(T−1)ρB1+w(QCx0−Q˜yt0). Proof: The proof is immediate. For any vector, including the vector z0that we decode at every step, there is a codeword in a distance less or equal than ρB1, and we can bound the cost at every time step by J(x0, u∗, t + 1) −J(x0, u∗, t) = min u{w(z0+B1u)}=w(e)≤ρB1. So after T−1 time instants we can give the bound J(x0, u∗, T )≤(T−1)ρB1+w(QCx0−Q˜yt0).  4 Convolutional decoding through a tracking problem 3. Convolutional decoding as a tracking problem Decoding is together with the construction of efficient codes the main task in coding theory, and in general a non-trivial objective. As explained in [4], the decoding of convolutional codes can be interpreted as a tracking problem. Applying the solution for the tracking problem over finite fields (over which codes are usually defined) we can give a decoding algorithm for general convolutional codes. Let us consider the generator matrix G(z) of a convolutional code. As shown in [4] we can divide it into G(z) = P(z)n−k×k Q(z)k×k so that degdetQ(z) = δ, the degree of the code. This leads to a controllable state space representation of the code as a linear system xt+1 =Axt+But yt=Cxt+Dut x0= 0 (3.1) with transfer function C(zId −A)−1B+D=P(z)Q(z)−1. Given a codeword c(z) = X t≥0 ctzteach vector coefficient can be divided into ct=yt ut. Decoding a received sequence {vt= (˜yt,˜ut)}consists of finding min c∈C {d(c, v)}=min (T X t=0 d(yt, y0 t) + d(ut, u0 t))=min (T X t=0 w(yt−˜yt) + w(ut−˜ut)). This can be thought as a tracking problem with cost function J(x0, u(·), T) = T X t=0 [w(ut−˜ut) + w(yt−˜yt)] = =J(x0, u(·), T −1) + w(uT−˜uT) + w(yT−˜yT). (3.2) In a practical convolutional decoding process, in order to save time, decoding can start before the whole information stream is received, which in practice results in considering it as an infinite process. To solve the corresponding problem we apply a Receding Horizon technique which consists on following iteratively these steps: we consider the initial (known) state xt. we solve an N-step finite horizon tracking problem, i.e., we find {ut+i}N i=0 which minimizes J(xt, u, N) = N X i=0 [w(ut+i−˜ut+i) + w(yt+i−˜yt+i)] 5 Jos´e Ignacio Iglesias Curto, Uwe Helmke we update our “decoded” input with {ut, . . . , ut+L}and our “decoded” output with {yt, . . . , yt+L}, and we get xt+L+1.Lwill depend on how many steps we can assure are decoded without errors. Step 2 represents the main problem to be solved. To consider a direct solution (instead of an iterative one) will give some information on how big should Lbe. Given xtwe want to find {ut, . . . , ut+N−1}that minimize N X i=0 [w(ut+i−˜ut+i) + w(yt+i−˜yt+i)] = w(zN) with zN= (yt+N−˜yt+N, ut+N−˜ut+N, . . . , yt−˜yt, ut−˜ut). We know that xt+i=Aixt+ i−1 X r=0 Ai−r−1But+r yt+i=Cxt+i+Dut+i. So the vector zNcan be written as zN=dwt,N +d BNut,N where dwt,N =                CANxt−˜yt+N −˜ut+N CAN−1xt−˜yt+N−1 −˜ut+N−1 . . . CAxt−˜yt+1 −˜ut+1 Axt−˜yt −˜ut                d BN=           D CB CAB . . . CAN−1B Id 0 0 0 0 0D CB . . . CAN−2B 0Id 0 0 0 · · · · · · · · · · · · · · · 0D Id           ut,N = (ut+N, ut+N−1, ut+N−2, . . . , ut). Sorting properly we have a vector wt,N +BNut,N with the same weight of zN, being wt,N =           CAN . . . C 0 . . . 0           xt−           ˜yt+N . . . ˜yt ˜ut+N . . . ˜ut           6 Convolutional decoding through a tracking problem BN=               D H0H1. . . HN−1 0D H0. . . HN−2 . . ........... . . . . .......H0 0. . . . . . 0D Id               with Hi=CAiB. The problem will be solved by decoding, with an appropriate block decoding algorithm, the vector wt,N as a codeword from the code generated by BN. The generator matrix, BN, is systematic so the check matrix of the code is H=         D H0H1. . . HN−1 0D H0. . . HN−2 −Id . . ........... . . . . .......H0 0. . . . . . 0D         . It is well-known that the minimum number of linear dependent columns of His the minimum distance of the code CB1, and this bounds the number of correctable errors that can occur in Ntime steps. The length of the receding horizon, N, and the number of steps to update, L, will depend on how many errors we are able to correct in the code generated by BN. Theorem 3.1. For a fixed N, being dthe minimum distance of the code CBNgenerated by BN, we can correct bd0 2cerrors (d0≥d) if every codeword of CBNwith weight ≤d0has zeros in the components from (N−L)(n−k)+1 till N(n−k)and from Nn −Lk + 1 till Nn. Proof: Recall that a decoding error happens if instead of the codeword sent, c, the decoding result is another codeword c0=c+ce, where the decoding error ceis also a codeword. In our case, as the generator matrix BNis systematic, the decoded codeword can be divided in an information part and a parity check part. The information part is actually a sequence of Ninputs of the solution for our tracking problem. As we will only update Lof these inputs, there is an admissible decoding error, as long as it happens in the last N−Linputs (corresponding to the first coordinates of the information word) which will not affect to the solution of our problem. An error only in the last N−Linputs corresponds to a decoding error codeword ce with non-zeros only in the components from 1 till (N−L)(n−k) and from N(n−k)+1 till Nn −Lk. So, all the codewords with support only in these components are admissible errors, and in particular, if every word with weight ≤d0is and admissible error then we can correct bd0 2cerror positions.  7 Jos´e Ignacio Iglesias Curto, Uwe Helmke We obtain a decoding algorithm for a general convolutional code with a state space representation (3.1). Algorithm 3.2. Fix the length of the receding horizon, N, and the update length L, according to Theorem 3.1. x0= 0,J(x0, u(·),0) = 0. For i > 0,(i−1)L < T , •Use a block decoding algorithm to decode wiL,N as a codeword from the code CBN, obtaining ui={uiL+1, . . . , uiL+N}as the information word. •Update the solution input uwith {uiL+1, . . . , u(i+1)L}. •Calculate xt+1 =Axt+But, yt=Cxt+Dutfor all iL+1 ≤t≤(i+1)L. •Update J(x0, u(·),(i+1)L) = J(x0, u(·), iL)+ L X i=0 [w(ut+i−˜ut+i)+w(yt+i−˜yt+i)]. The decoding output is the sequence {ct= (yt, ut)}, and the number of errors J(x0, u(·), T). 4. Conclusion We have posed a tracking problem over a finite field, modifying the cost function to be minimized, so that it considers the Hamming weight instead of an Euclidean metric. We gave a solution to this problem by using coding theory tools. This makes it possible to consider convolutional decoding as a tracking problem. We set the corresponding problem, whose solution gives a decoding method for general convolutional codes. Acknowledgments The first author has been partially supported for this work by fellowship A/06/12428 from DAAD. We want to thank Prof. Harald Wimmer for his valuable advice and helpful comments. Referencias [1] B.D.O. Anderson and J.B. Moore, Linear optimal control, Prentice-Hall, January 1971. [2] B.D.O. Anderson and J.B. Moore, Optimal control: Linear quadratic methods, Prentice-Hall, 1989. [3] R. Bellman, Dynamic programming, Princeton University Press, Princeton, NJ, 1957. [4] J. Rosenthal, Some interesting problems in systems theory which are of fundamental importance in coding theory, Proceedings of the 36th IEEE Conference on Decision and Control, 1997. 8