Bounds to the treillis decoding complexity of linear block codes

V. V. Zyablov, V. R. Sidorenko

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)


Syndrome treillis is shown to be minimal. A simple proof of a lower bound to a code treillis nodes number is given. Complexity exponents bounds of maximal verisimilitude for soft decoding in a treillis is obtained. Though almost all codes satisfying the Varshamoff bound are at the upper complexity bound, the block codes obtained by cutting convolution codes have exponentially less complexity in a treillis. The hypothesis for exactitude of Varshamoff bound for binary codes being hold, the block codes decoding complexity is the minimal possible one.

Original languageEnglish
Pages (from-to)3-9
Number of pages7
JournalProblemy Peredachi Informatsii
Issue number3
Publication statusPublished - Jul 1993
Externally publishedYes


Dive into the research topics of 'Bounds to the treillis decoding complexity of linear block codes'. Together they form a unique fingerprint.

Cite this