Several New Generalized Linear- and Optimum-Time Synchronization Algorithms for Two-Dimensional Rectangular Arrays

We propose several new generalized synchronization algorithms for 2-D cellular arrays. Firstly, a generalized linear-time synchronization algorithm and its 14-state implementation are given. It is shown that there exists a 14-state 2-D CA that can synchronize any m × n rectangular array in m + n + max(r + s , m + n – r – s + 2) – 4 steps with the general at an arbitrary initial position (r, s),where 1 ≤ r ≤ m, 1 ≤ s ≤ n. The generalized linear-time synchronization algorithm is interesting in that it includes an optimum-step synchronization algorithm as a special case where the general is located at one corner. In addition, we propose a noveloptimum-time generalized synchronization scheme that can synchronize any m × n array in m+n+max (m, n)− min (r, m−r+1)− min (s, n−s+1)−1 optimum steps.