THE DYNAMICS OF GROUP CODES - STATE-SPACES, TRELLIS DIAGRAMS, AND CANONICAL ENCODERS

A group code C over a group G is a set of sequences of group elements that itself forms a group under a componentwise group operation. A group code has a well-defined state space Sigma(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(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 v-controllable, then \Sigma(k)\ = II1 less than or equal to j less than or equal to v\F-j/F-j-1\(j), where F-0 subset of or equal to ... subset of or equal to Fv 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.