| We consider the problem of finding good linear block codes with simple trellis structures. State complexity is used to measure trellis complexity. For a given state complexity, we show how to expurgate a maximum distance separable code, keeping the dimension of the code as large as possible, and the effective length as short as possible. For a given value of code length, minimum Hamming distance and state complexity S, two greedy algorithms are used to produce trellis-oriented generator matrices. By puncturing optimal convolutional codes, good binary linear block codes of fixed state complexity can also be constructed. A class of binary linear block codes with S = 2 is found. We show that no codes with the same parameters can have smaller S. Some good binary linear block codes with S = 3 and S = 4 are also presented. |
