In recent years, there has been an increasing demand for efficient and reliable digital data transmission and storage systems. This demand has been accelerated by the emergence of large-scale high-speed data networks for the exchange, processing and storage of digital information in the commercial, governmental and military spheres. A merging of communications and computer technology is required in the design of these systems. A major concern of the system design is the control of errors so that the data can be reliably reproduced. In 1948, Shannon demonstrated in a landmark paper that by proper encoding of the information, errors induced by a noisy channel or storage medium can be reduced to any desired level without sacrificing the rate of information transmission or storage, as long as the information rate is less than the capacity of the channel. Since Shannon ’s work much effort has been expended on the problem of devising efficient encoding and decoding methods for error control in a noisy environment. Recently, linear Programming (LP) decoding, as an approximation to Maximum Likelihood (ML) decoding, was proposed by Feldman et al. ML certification, a solid theoretic foundation and the capability to be used for all binary linear codes, are the main properties that have made LP decoding of great interest since its introduction by Feldman. Since the complexity of Feldman’s first formulation for LP decoding increases exponentially with the degree of the check nodes in the Tanner graph of the code, it has only been used for low-density parity-check (LDPC) codes thus far. Recently, Yang et al. suggested a new LP decoder with polynomial complexity. This allows the practical use of LP decoders for non-LDPC codes. Attempts have been made to eliminate the use of a general LP solver by using iterative algorithms. Also replacing several receiver components (e.g. demodulator, channel equalizer and decoder) by one linear programming unit has been proposed. These developments make LP decoding an important candidate for future implementation. On the other hand, many observations suggest similarities between the performance of LP and message passing methods. Hence LP decoder with its solid theoretic foundation can be used to make prediction on the performance of message passing algorithms. In this research, different aspects of LP decoders are investigated. Then by using the idea of Feldman in relaxing an integer programming problem to obtain a linear programming one, in his approach towards achieving the LP decoder, we introdu
