A branch and cut algorithm for finding the minimum distance of a linear block code
- Resource Type
- Conference
- Authors
- Keha, Ahmet; Duman, Tolga M.
- Source
- 2008 IEEE International Symposium on Information Theory Information Theory, 2008. ISIT 2008. IEEE International Symposium on. :201-205 Jul, 2008
- Subject
- General Topics for Engineers
Communication, Networking and Broadcast Technologies
Signal Processing and Analysis
Distance measurement
Parity check codes
Block codes
IP networks
Linear programming
Upper bound
Generators
mixed-integer programming modeling
branch-and-cut
linear block codes
low density parity check codes
- Language
- ISSN
- 2157-8095
2157-8117
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.