A branch and cut algorithm for finding the minimum distance of a linear block code

Author

Keha, Ahmet ; Duman, Tolga M.

Author_Institution

Ind. Eng. Dept., Arizona State Univ., Tempe, AZ

fYear

2008

fDate

6-11 July 2008

Firstpage

201

Lastpage

205

Abstract

We give a branch-and-cut algorithm for finding the minimum distance of a binary linear error correcting code. We give two integer programming (IP) models and study the convex hull of the single constraint relaxation of these IP models. We use the new inequalities as cuts in a branch-and-cut scheme. Finally, we report computational results based on low density parity check (LDPC) codes that demonstrate the effectiveness of our cuts.

Keywords

binary codes; block codes; convex programming; error correction codes; integer programming; linear codes; parity check codes; LDPC codes; binary linear error correcting code; branch and cut algorithm; constraint relaxation; convex hull; integer programming models; linear block code; low density parity check codes; AWGN; Additive white noise; Block codes; Digital communication; Error analysis; Error correction codes; Industrial engineering; Linear programming; Parity check codes; Protection; branch-and-cut; linear block codes; low density parity check codes; mixed-integer programming modeling;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Theory, 2008. ISIT 2008. IEEE International Symposium on

Conference_Location

Toronto, ON

Print_ISBN

978-1-4244-2256-2

Electronic_ISBN

978-1-4244-2257-9

Type

conf

DOI

10.1109/ISIT.2008.4594976

Filename

4594976