2-D CA Variation With Asymmetric Neighborship for Pseudorandom Number Generation

Abstract

This paper proposes a variation of two-dimensional (2-D) cellular automata (CA) by adopting a simpler structure than the normal 2-D CA and a unique neighborship characteristic - asymmetric neighborship. The randomness of 2-D CA based on asymmetric neighborship is discussed and compared with one-dimensional (1-D) and 2-D CA. The results show that they are better than 1-D CA and could compete with conventional 2-D CA under certain array setting, output method, and transition rule. Furthermore, the structures of 2-D CA based on asymmetric neighborship were evolved using some multiobjective genetic algorithm. The evolved 2-D CA could pass DIEHARD tests with only 50 cells, which is less than the minimal number of cells (i.e., 55 cells) needed for neighbor-changing 1-D CA to pass DIEHARD. In addition, a refinement procedure to reduce the cost of 2-D CA based on asymmetric neighborship is discussed. The minimal number of cells found is 48 cells for it to pass DIEHARD. The structure of this 48-cell 2-D CA is identical to that of the evolved 10 * 5 2-D CA, except that 2 horizontal cells in the evolved 10 * 5 2-D CA are removed.