A Cutting-Plane Method Based on Redundant Rows for Improving Fractional Distance

作者：Miwa Makoto^*; Wadayama Tadashi; Takumi Ichi

来源：IEEE Journal on Selected Areas in Communications, 2009, 27(6): 1005-1012.

DOI：10.1109/JSAC.2009.090818

• Linear codes
• Golay codes
• Linear programming decoding
• Fractional distance

Decoding performance of linear programming (LP) decoding is closely related to geometrical properties of a fundamental polytope: fractional distance, pseudo codeword, etc. In this paper, an idea of the cutting-plane method is employed to improve the fractional distance of a given binary parity-check matrix. The fractional distance is the minimum weight (with respect to l(1)-distance) of nonzero vertices of the fundamental polytope. The cutting polytope is defined based on redundant rows of the parity-check matrix. The redundant rows are codewords of the dual code not yet appearing as rows in the parity-check matrix. The cutting polytope plays a key role to eliminate unnecessary fractional vertices in the fundamental polytope. We propose a greedy algorithm and its efficient implementation based on the cutting-plane method. It has been confirmed that the fractional distance of some parity-check matrices are actually improved by using the algorithm.

• 出版日期2009-8