Exploring NSRT Diagram for Scalable Synthesis of TACA
Suvadip Hazra and Mamata Dalui
Cellular Automata (CAs) are considered as a powerful mathematical modelling tool that is becoming more popular in scientific research and simulations. The potential of CAs to represent a broad range of physical, natural, and real-world events has grabbed the attention of researchers from a wide range of domains. Three-neighbourhood one-dimensional Cellular Automaton (CA) has a wide range of applications in a variety of disciplines, including VLSI design and testing, error-correcting codes, generation of test patterns, generation of hash functions and cryptographic encryption schemes, among others. The two-state three-neighbourhood CA has been investigated in this work. A graph-based tool called the Next State RMT Transition Diagram (NSRTD) is delineated for analysing the state transition behaviour of CA with fixed points. A methodology using the NSRTD has been explored for synthesising a particular class of irreversible CA known as Single Length Cycle Two Attractor CA (TACA), having only two fixed points. Further, the proposed methodology has been extended for scalable synthesis of TACA, wherein we have considered synthesis of an (n + 1)-length TACA from an existing configuration of n-length TACA and an (n + m)-length TACA from an existing configuration of n-length and m-length TACA.
Keywords: Cellular automata, TACA, NSRTD