On the comparative complexity of algorithms for constructing the syndrome trellis of a linear block code (Q1582940)

The paper focuses on the complexity of an algorithm for constructing an arbitrary fixed linear block code trellis. The author evaluates the lower bound of complexity of constructing such a trellis, proving its dependence on the number of trellis edges. He also proves that the proposed algorithm is asymptotically optimal for the minimal syndrome trellis of a linear block code. In order to obtain base vectors of linear spaces, he uses parity-check matrices. For minimizing the number of operations when constructing the syndrome trellis, it is desirable to address the vertices at each level. The author uses the structure of each vertex set as a linear space and considers the elements of this space.