The X neighbourhood


Co domain

Domain 1   ->   Co domain 1

The X neighborhood is a sister partitioning scheme to the one used in the Margolus neighbourhood. It exhibits very similar behaviour when used with appropriately translated automata. It has cells with 16 states, and uses information from neighbours in an 'X' configuration.

It is an isometric neightbourhood.

When implemented in hardware, it applies the same transformation to each cell on each clock tick - and requires no apparatus to implement an alternating partitioning grid.

It also has some corresponding drawbacks, however:

  • The X neighbourhood actually generates four causally independant sub-latices. Two of these share the same cells; so if a non-uniform automata is used, they must compute esstentially the same function.
  • Cells of the domain are more widely spaced than normal. This may mean that signals have to travel further, and the automata's update frequency may suffer as a consequence;
Unfortunately, any automaton that generates so many independent sub-lattices is rather problematical from the perspective of efficient hardware implementation.

More diagrams of this neighbourhood are available here.

There are partitioning schemes from the same family available with triangular geometry.

The automata may be generalised into three dimensions. Pictures of such automata are available here.

Tim Tyler | |