Abstract
It is known that equivalent linear block codes may have different minimal trellis structures. The minimum complexity among all minimal trellis structures of equivalent codes is defined as the trellis complexity of the class of equivalent codes. Sharper lower bounds for trellis complexity are derived when more information about the infrastructure of codes is supplied. These bounds serve as a starting specification for a search algorithm to find optimal permutations under which the permuted codes achieve the trellis complexity. A simple application to the class of equivalent binary [17, 9] quadratic residue codes finds the trellis complexity is five.