Invertible linear automataLinear cellular automataLinear cellular automata are those automata whose dependency on neighbouring cells is always viaXOR, or XNOR. The state at
any subsequent time period may be expressed as some
linear function of the initial state.Linear cellular automata are a subset of linear finite state machines - for which there are a number of existing theoretical results of relevance to invertability.
Modelling the transition function with a matrixSince the contributions from dependent cells can be simply added together, the transition function of linear finite state machines may be expressed as a matrix,A and a fixed vector
V.
The current state is represented by a vector. To
perform the transition function, the current state is
multiplied by the matrix, and then the fixed vector,
ResultsIf the matrix is non-singular - i.e. it has a non-zero determinant, then the corresponding FSM is invertible. This fact results in a relatively simple test for reversibility - and in a concrete method for constructing the inverse of the transition rule of a given FSM.
There is a "primitive polynomial" corresponding to the
transition function, whose coefficients may be found by
computing
If this polynomial is primitive, then the
whole FSM will exhibit behaviour with a period equal to
NotesVery frequently, the inverse of a linear cellular automaton is found to require a much larger neighbourhood than the original automaton.It has been proven that every maximal-period linear FSM with a single output has an exact equivalent in the form of some maximal-period LFSR.
|