Design of linear block codes with fixed state complexity

摘要

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.