Error-trellises for convolutional codes - Part I: Construction

An error-trellis is a directed graph that represents all the sequences belo nging to the coset which contains the symbol-by-symbol detected version of a given received sequence. A modular construction of error-trellises for an (n, k) convolutional code over GF(q) is presented. The trellis is designed on the basis of partitioning the scalar check matrix of the code into subm atrices of l rows, accompanied with a corresponding segmentation of the syn drome. The value of the design parameter l is an essentially unconstrained multiple of n - k. For all the cosets of the code, the sections of the erro r-trellis are drawn from a collection of only q(l) modules; the module for each section is determined by the value of the associated syndrome segment. In case the construction is based on a basic polynomial check matrix, eith er canonical or noncanonical, then the error-trellis is minimal in the sens e that sigma less than or equal to mu, where sigma is the dimension of the state space of the trellis and mu is the constraint length of a canonical g enerator matrix for the code, For basic check matrices with delay-free colu mns, the inequality reduces to sigma = mu.