Using Combinatorial Optimization To Design Good Unit-memory Convolutional Codes

A new method to design good unit-memory convolutional codes is presented. It is based on the decomposition of the original problem into two easier subproblems, which can be formulated as optimization problems and solved by new efficient heuristic search algorithms. The efficacy of the new method is demonstrated by a table containing 33 new unit-memory convolutional codes (n, k) with 5 ≤ k ≤ 8, rates R = k/n between 1/4 and 7/9, and complete memory (M = k), as well as 12 new linear block codes. Most of the new codes found have maximum free distance.3931100110