LP DECODER AND INTEGRAL SOLUTION CALCULATION METHOD AND PROGRAM FOR LINEAR CODE

摘要

PROBLEM TO BE SOLVED: To efficiently output an integral solution when using linear programming in implementing an LP decoder.

SOLUTION: A relaxation problem of maximum likelihood decoding of a linear code is solved by linear programming. With regions (slice regions) into which a feasible region is equally divided at constant intervals ε from an optimum value of a resultant objective function f to an appropriate value (for example, an initial value of f), it is determined in order whether or not each divided slice region includes a vertex of a hypercube. If the region includes such a vertex, coordinates x of the included vertex are output as an integral solution, and otherwise, a resultant nonintegral solution at the time is stored in storage means. If there is no integral solution even after all the slice regions are scanned, such solutions stored in the storage means by the time are output.

COPYRIGHT: (C)2013,JPO&INPIT