We demonstrate the structural invertibility of all reversible one- and
two-dimensional cellular automata. More precisely, we prove that ever
y reversible two-dimensional cellular automaton can be expressed as a
combination of four block permutations, and some shift-like mappings.
Block permutations are very simple functions that uniformly divide con
figurations into rectangular regions of equal size and apply a fixed p
ermutation on all regions.