Coding Theory

On the Comparative Complexity of Algorithms for Constructing the Syndrome Trellis of a Linear Block Code

A. V. Trushkin


Abstract: We consider the question of the complexity of an algorithm for constructing a block code trellis, as distinct from the complexity of the trellis itself. We state that a lower bound on the complexity of constructing a trellis is determined by the total number of its edges. We show that for the minimal (syndrome) trellis of a linear block code, a simple (but not described earlier) algorithm is asymptotically optimal. The algorithm employs the parity-check matrix in the echelon form and addresses the vertices of the trellis at every level in the basis of the corresponding linear space, which is isomorphic to the space of partial syndromes of the parity-check matrix.

UDC: 621.391.15

Received: 29.12.1998
Revised: 08.12.1999

 English version: Problems of Information Transmission, 2000, 36:2, 98–105

Bibliographic databases:

• 
•