Sequential Functions and Linear Sequential Machines

The``state´´ of a sequential machine is interpreted as the sequence-to-sequence input-output mapping performed by the machine. Such mappings have been called sequential functions. This concept of state is applied to the theory of binary linear sequential machines. The modulo-2 adders are assumed to have an inherent delay t^d¿0, and the effects of initial conditions are considered. The pertinent results from the algebra of delay polynomials are summarized, and the state structure of linear sequential functions is outlined. It is shown that every retrospective linear sequential function can be realized using only unit-delay modulo-2 adders, and bounds are derived on the minimum realizable delay between input and output.