The dynamics of group codes: state spaces, trellis diagrams, and canonical encoders

TLDR

A group code over a group G is a group of sequences whose state space at each time defines a minimal trellis realization, with state and label codes isomorphic, enabling a minimal canonical encoder from shortest sequences, and these results generalize convolutional code theory to arbitrary groups and various coding structures without requiring time invariance. The state space size of a group code equals that of its minimal canonical encoder, determined.

Abstract

A group code C over a group G is a set of sequences of group elements that itself forms a group under a component-wise group operation. A group code has a well-defined state space Sigma /sub k/ at each time k. Each code sequence passes through a well-defined state sequence. The set of all state sequences is also a group code, the state code of C. The state code defines an essentially unique minimal realization of C. The trellis diagram of C is defined by the state code of C and by labels associated with each state transition. The set of all label sequences forms a group code, the label code of C, which is isomorphic to the state code of C. If C is complete and strongly controllable, then a minimal encoder in controller canonical (feedbackfree) form may be constructed from certain sets of shortest possible code sequences, called granules. The size of the state space Sigma /sub k/ is equal to the size of the state space of this canonical encoder, which is given by a decomposition of the input groups of C at each time k. If C is time-invariant and nu -controllable, then mod Sigma /sub k/ mod = Pi /sub 1<or=j<or=v/ mod F/sub j//F/sub j-1/ mod /sup j/, where F/sub 0/ contained in ... contained in F nu is a normal series, the input chain of C. A group code C has a well-defined trellis section corresponding to any finite interval, regardless of whether it is complete. For a linear time-invariant convolutional code over a field G, these results reduce to known results; however, they depend only on elementary group properties, not on the multiplicative structure of G. Moreover, time-invariance is not required. These results hold for arbitrary groups, and apply to block codes, lattices, time-varying convolutional codes, trellis codes, geometrically uniform codes and discrete-time linear systems.<<ETX>>