The Q*Bert neighbourhood

If the Margolus partitioning scheme may be seen as the result of super-imposing two planes containing rectangular girds, then the Q*Bert partitioning scheme can be seen as the result of doing this with two hexagonal meshes.

The two stages of the Q*Bert partitioning scheme

(t & 1) = 0

(t & 1) = 1
(t & 1) = 0    (t & 1) = 1 

Alternation

 

The operation (and virtues) of the Q*Bert neighbourhood are very similar to those of the Margolus neighbourhood.

Domain

Range
Domain 1   ->   Range 1
Domain 2   ->   Range 2

Universal computation

The neighbourhood supports universal computation with uniform automata - using a map similar to that of the "Billiard Ball Machine".

0 -> 0      7 -> 7     
1 -> 2      3 -> 3     
2 -> 4      5 -> 5     
4 -> 1      6 -> 6     

This map may be applied in one clock cycle. To get the mapping for the alternate clock cycle, all the above figures may be rotated through 180 degrees.

Size and packing

Its advantages over related neighbourhoods are mainy due to its ability to occupy space more effectively.

The Q*Bert neighbourhood typically needs three bits per cell, compared with four for the Margolus neighbourhood and six for the Star of David neighbourhood.

Three is the smallest number possible while retaining the ability to perform reversible universal computation.

Reversible automata with two states per partition are possible, but there are no such automata that can express non-linear boolean functions - and consequently none of them are capable of universal computation.

The size of the LUT required to implement a complete programmable Q*Bert neighbourhood is 48 bits (3x(2^3)x2).

The one required for a complete programmable Margolus neighbourhood is 128 bits (4x(2^4)x2) - less than half the size.

A Star of David neighbourhood automata requires 384 bits (6x(2^6)) for a complete programmable look-up-table.

Small size is not everything - Q*Bert-based systems will require more cells for some tasks than the equivalent when expressed in (say) the Margolus neighbourhood. However for the majority of applications which involve performing cmputations, the additional richness provided by a larger LUT seems likely to be wasted much of the time, doing the equivalent of transporting signals from one point to another. We believe the advantage of the smaller cells in terms of their smaller size and higher update frequency will commonly win out.

Finally the Q*Bert neighbourhood is essentially hexagonal - and there is a general additional efficiency of hexagonal packing schemes compared to rectangular ones - a matter I will not go into further here.

The Q*Bert neighbourhood has a fairly obvious extension into three dimensions.

Tim Tyler | tim@tt1.org | http://cell-auto.com/