Decoding LDPC codes in MIMO systems with linear programming

Proceedings of the 10th WSEAS International Conference on SYSTEMS, Vouliagmeni, Athens, Greece, July 10-12, 2006 (pp348-351) Decoding LDPC Codes in MIMO Systems with Linear Programming Carlos Herrera, Iván Dérpich, Ismael Soto Departamento de Ingeniería Industrial Universidad de Santiago de Chile Av. Ecuador 3769, Santiago CHILE Abstract The aim of this paper is to formulate a new strategy to decoding Low Density Parity Check Codes suitable for Multiple Input Multiple Output communication systems using Integer Linear Programming. Also a comparison of the performance with a Single Input Single Output is presented. Key-Words: Linear codes - Linear programming - MIMO systems 1 Introduction Motivated by the recent contributions made in the field of the application of linear programming techniques to decoding linear error correcting codes exposed in [1], [2], [3], the object of this work will be to investigate the application of this technique in a MIMO (multiple input - multiple output) systems. In reference [1], the authors propose an algorithm based on a linear programming relaxation as an alternative to the ML algorithm, denominated Maximum Likelihood Decoding Problem addressing the decoding of LDPC codes as the central subject of their work.. For decoding of LDPC codes, they exposed the necessity of the linear programming relaxation, given the NP-hard nature of the ML decoding problem. The LDPC code representation is expressed by a factor graph or Tanner graph. For the problem solution the particular structure of the Tanner graph is used, where the variable nodes represent the code bits and the check nodes express the problem restrictions. The main idea is to construct a polytope that represents the words of the code exactly, of this form makes sure that any integer solution of the problem will be a solution of the algorithm ML in a MIMO infrastructure. 2 Preview The LDPC codes were proposed by Gallager [4] in 1962 and in principle they were ignored, mainly because they had very high computation rqueriments, reason why other codes mainly were considered. In the '90, these codes were rediscovered by many investigators and from that moment to the present time they have received a lot attention, which had mainly to his capacity to simplify the decoding process, for the present standards of computation capacity. A LDPC code, is a binary code of blocks, that is characterized by a parity check matrix H. This matrix has the characteristic of being sparse, which means that the number of ones is very small with respect to the number of zeros that contains. The rows of H represents parity check equations and the columns code bits. If the number of Proceedings of the 10th WSEAS International Conference on SYSTEMS, Vouliagmeni, Athens, Greece, July 10-12, 2006 (pp348-351) rows and columns is constant, LDPC code is called regular, otherwise the code is irregular. Generally the irregular codes have a better performance [5]. LDPC codes contain of the order of thousands elements. in the case correspond to variable nodes and check nodes. The Tanner graph of the Hamming code (7,4) displayed previously corresponds to the graph shown in fig 1: 2.2 H matrix construction If we give for example an hamming code (7,4), which have a code rate r= 4 7 , where r=k n , the generator matrix G of this code is: 1 0 G= 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 In order to obtain a codified word we applied the following relation: c=cod x =xG , where c correspond to our codified word. The generating matrix G we can express like G=IP , where I is the identity matrix, therefore the H matrix we can T obtained for H=P I , H for a Hamming code (7,4) correspond: 1 0 H= 0 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 Moreover, for a valid codeword c , T c H 0 , with which we will be able to decide if a word belong or not to the code. It is important to indicate that the sums for the codification as for the parity checking must be executed in algebra module 2. 2.3 Factor graph A linear binary code represented by a parity check matrix H, can be represented by a factor graph or Tanner graph. This graph is a bipartite graph, and has two types of nodes that Fig.1: Tanner graph for Hamming(7,4). 3 Problem formulation In order to formulate the problem of linear programming that allow decoding is necessary to define some elements. A polytope that allow us decode a “local codeword” c j,S considers a set variable nodes f i :i N j corresponds to the variable nodes i incident to check node j . Also we must consider a set which S N j corresponds to the subsets of even module incident nodes. For each subset of variable nodes of even module corresponding to the check node j we will have f i 1 if i S and f i 0 if i S , fixing the remaining nodes arbitrarily. In addition, to group each one of these subsets we will define a set E j S N j : S par . Moreover, S E j we introduce a auxiliar variable w j,s , that will be an indicator that an local codeword is asociated or not to a particular subset of variable nodes S . Is necessary to make notice that variable w j, is present for each check node. Proceedings of the 10th WSEAS International Conference on SYSTEMS, Vouliagmeni, Athens, Greece, July 10-12, 2006 (pp348-351) 3.1 Polytope construction For the polytope construction we consider the following constraint: channel with probability p , own cost function is : i 1. Local check consistence constraint j J,S E j i w j,S 1 2. Local polytope constraint S E j ,S (2) v i 3. Integer f i constraint i I fi 0,1 (3) 4. Integer w j,S constraint j J,S E j w j,S 0 (8) yi 1 ln p 1 p , we Rescaling with obtain 1 si yi 1 that i i 1 si yi 0 . 4 Results w j,S = f i IxJ yi (1) S Ej This constraint show that every check node j , only can satisfied for a particular setting S . i,j 1 p p p ln 1 p ln 0,1 (4) j J, Moreover, we have that define Q j polytope how: In Figure 2 correspond to simulation results, the blue line represent the performance of a decoder in SISO system, while in red the application of ILP decoding to a MIMO system. This simulation consider ILP problem as the possible alternatives of solutions. Since in MIMO systems we can consider the problem how the selection of more than one signal. In a system with two transmitting antennas and two receiving antennas, we can consider that four different signals are received. Qj f,w : 1,2,3y 4 hold (5) Therefore, since Q the intersection of j J , then all Q j local polytopes decoding problem with ILP is: min i f i s.a f ,w Q i (6) Where i is a linear cost function, which constructed with a posteriori probability of own received codeword. i ln Pr yi yi 0 Pr yi yi 1 (7) 3.2 BSC Channel If we consider an binary symmetric Fig.2: Comparison of the performance of a SISO against a MIMO system. 4 Conclusions In this paper a new formulation for the decoding a LDPC suitable for MIMO channel using ILP has been achieved. This allows the optimization of the Proceedings of the 10th WSEAS International Conference on SYSTEMS, Vouliagmeni, Athens, Greece, July 10-12, 2006 (pp348-351) communication channel as one entity. This is not useful to find in the communication area, where every component is optimized one by one. It can be conclude that the performance of LDPC in a MIMO channel is better that a SISO system as the probability of the error in a BSC channel increase. ACKNOWLEDGMENT The authors would like to thank PBCT CONICYT ACT 11/04 - Chile, for their financial support. 5 References [1]Feldman J., Decoding ErrorCorrecting Codes via Linear Programming, Ph.D. Thesis 2003, Massachussets Institute of Technology. [2]Candence E., Tao T., Decoding by linear programming, 2004, University of California. [3]Mohammad H., Taghavi N. Siegel P., Adaptative Linear Programming Decoding, 2006, University of California, San Diego. [4]Gallager R., Low-density paritycheck codes, Monograph, M.I.T. Press, 1963. [5]Abrantes S., Decodificacao iterativa de códigos LDPC por transferencia de mensagens em gáficos de factores, Facultad de Engenharia, Univesridade do Porto, Portugal. [4]Shannon C., A Mathematical Theory of Communication, The Bell System Technical Journal, Vol. 27, pp. 379–423, 623–656, Js, 1963.