Bounds on Complexity of Trellis Decoding of Linear Block Codes

It is shown that the syndrome trellis [1,2] is minimal. A simple proof of the lower bound on the number of nodes of the minimal trellis is given. Asymptotic bounds on the complexity of soft maximum likelihood trellis decoding are proposed.
It is shown that virtually all codes meet the upper complexity bound. Nevertheless the block codes, constructed by termination of convolutional codes, have smaller trellis decoding complexity. The complexity is minimal if the Varshamov–Gilbert bound is tight for binary codes.