RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Guidelines for authors Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Probl. Peredachi Inf.: Year: Volume: Issue: Page: Find

 Probl. Peredachi Inf., 2000, Volume 36, Issue 2, Pages 10–18 (Mi ppi474)

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.

Full text: PDF file (1201 kB)
References: PDF file   HTML file

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

Bibliographic databases:
UDC: 621.391.15
Revised: 08.12.1999

Citation: 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
\Bibitem{Tru00} \by A.~V.~Trushkin \paper On the Comparative Complexity of Algorithms for Constructing the Syndrome Trellis of a~Linear Block Code \jour Probl. Peredachi Inf. \yr 2000 \vol 36 \issue 2 \pages 10--18 \mathnet{http://mi.mathnet.ru/ppi474} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=1763579} \zmath{https://zbmath.org/?q=an:0980.94035} \transl \jour Problems Inform. Transmission \yr 2000 \vol 36 \issue 2 \pages 98--105