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 gro up code has a well-defined state space Sigma(k) at each time k. Each c ode 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 sta te code defines an essentially unique minimal realization of C. The tr ellis diagram of C is defined by the state code of C and by labels ass ociated with each state transition. The set of all label sequences for ms 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 constructe d from certain sets of shortest possible code sequences, called granul es. The size of the state space Sigma(k) is equal to the size of the s tate space of this canonical encoder, which is given by a decompositio n 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 tha n or equal to v\F-j/F-j-1\(j), where F-0 subset of or equal to ... sub set of or equal to Fv is a normal series, the input chain of C. A grou p code C has a well-defined trellis section corresponding to any finit e interval, regardless of whether it is complete, For a linear time-in variant convolutional code over a field G, these results reduce to kno wn 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 b lock codes, lattices, time-varying convolutional codes, trellis codes, geometrically uniform codes and discrete-time linear systems.