We present a new lower bound on the state-complexity of linearcodes, which includes all the existing bounds as special cases. For alarge number of codes this results in a considerable improvement uponthe DLP bound. Moreover, we generalize the new bound to nonlinear codes,and introduce several alternative techniques for lower bounding thetrellis complexity, based on the distance spectrum and othercombinatorial properties of the code. We also show how our techniquesmay be employed to lower bound the maximum and the total number ofbranches in the trellis. The asymptotic behavior of the new bound isinvestigated and shown to improve upon the known asymptotic estimates oftrellis complexity
展开▼
