On viewing block codes as finite automata

Abstract

Block codes are viewed from a formal language theoretic perspective. It is shown that properties of trellises for subclasses of block codes called rectangular codes follow naturally from the Myhill Nerode theorem. A technique termed subtrellis overlaying is introduced with the object of reducing decoder complexity. Necessary and sufficient conditions for trellis overlaying are derived from the representation of the block code as a group, partitioned into a subgroup and its cosets. The conditions turn out to be simple constraints on coset leaders. It is seen that overlayed trellises are tail-biting trellises for which decoding is generally more efficient than that for conventional trellises. Finally, a decoding algorithm for tail-biting trellises is described, and the results of some simulations are presented.