Computing extensions of linear codes using a greedy algorithm

Abstract

This paper deals with the problem of increasing the minimum distance of a linear code by adding one or more columns to the generator matrix. We present a simple greedy algorithm which surprisingly yields many codes improving the previously known lower bounds on the minimum distance. We also discuss variations of the algorithm that succeed when the greedy algorithm is not feasible or fails. © 2012 IEEE.