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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
Received: 29.12.1998
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


Linking options:
  • http://mi.mathnet.ru/eng/ppi474
  • http://mi.mathnet.ru/eng/ppi/v36/i2/p10

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:221
    Full text:87
    References:26

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020