An-Najah Staff

In this thesis we investigate the application of Linear Programming LP relaxation to the problem of decoding an error-correcting code. LP relaxation is a standard technique in approximation algorithms and operation research, and it is used to find good suboptimal solution to very difficult optimization problems. The method of a posteriori probability and iterative decoding algorithm is used to decode product codes (a special type of turbo codes). We investigate a program using Matlab to make computations to our algorithm. The logistic distribution with variance one is used. We compare the results of our computations to those of other authors; we find that our results are the best all over the others. The LP method has its place in the generic turbo code, which is made up of asset of simpler" trellis-based" codes, we formulate the LP for a single trellis-based code as a min-cost flow problem, using the trellis as a directed flow. We extend this formulation to any turbo codes by applying constraints between the LP variables used in each component code. One of the most advantages for LP decoding is that whenever the decoder output a result it is guaranteed to be the optimal solution, the most likely (ML) information sent over the channel, we refer to this property as the ML certificate property.