On the Comparative Complexity of Algorithms for Constructing the Syndrome Trellis of a Linear Block Code
A. V. Trushkin
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.
PDF file (1201 kB)
Problems of Information Transmission, 2000, 36:2, 98–105
A. V. Trushkin, “On the Comparative Complexity of Algorithms for Constructing the Syndrome Trellis of a Linear Block Code”, Probl. Peredachi Inf., 36:2 (2000), 10–18; Problems Inform. Transmission, 36:2 (2000), 98–105
Citation in format AMSBIB
\paper On the Comparative Complexity of Algorithms for Constructing the Syndrome Trellis of a~Linear Block Code
\jour Probl. Peredachi Inf.
\jour Problems Inform. Transmission
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|