Invertible linear automata

Linear cellular automata

Linear cellular automata are those automata whose dependency on neighbouring cells is always via XOR, 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 matrix

Since 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, V is added. The resulting vector (considered modulo 2) is then interpreted as the new state.

Results

If 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.

When V is all-zero, There is a "primitive polynomial" corresponding to the transition function, whose coefficients may be found by computing |(Ix - A)| - where A is the matrix of the transition function, I is the identity matrix of the same size, and x is an unknown vector whose entries correspond to the coefficients of the polynomial to be found [and |M| = "the determinant of matrix M"].

If this polynomial is primitive, then the whole FSM will exhibit periodic behaviour, with a period equal to 2^n - 1 where n is the number of binary variables present. The all-zero state will map to itself - as in a LFSR.

Notes

Very 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.

Tim Tyler | tt@iname.com | http://cell-auto.com/