Additive Cellular Automata: Theory and Applications, Volume 1(Practitioners)

This book presents an extensive survey and report of related research on important developments in cellular automata (CA) theory. The authors introduce you to this theory in a comprehensive manner that will help you understand the basics of CA and be prepared for further research. They illustrate the matrix algebraic tools that characterize group CA and help develop its applications in the field of VLSI testing. The text examines schemes based on easily testable FSM, bit-error correcting code, byte error correcting code, and characterization of 2D cellular automata. In addition, it looks into CA-based universal pattern generation, data encryption, and synthesis of easily testable combinational logic. The book covers new characterizations of group CA behavior, CA-based tools for fault diagnosis, and a wide variety of applications to solve real-life problems.

Table of Contents:
PREFACE. 1 INTRODUCTION. 1.1 Cellular Automata Applications. 1.2 Overview of the Book. 2 CA AND ITS APPLICATIONS: A BRIEF SURVEY. 2.1 Introduction. 2.2 Initial Phase of Development. 2.3 CA-Based Models. 2.3.1 CA as Parallel Language Recognizer. 2.3.2 Biological Applications of CA. 2.3.3 CA as Parallel and Image Processing Systems. 2.4 New Phase of Development. 2.4.1 Polynomial Algebraic Characterization of CA Behavior. 2.4.2 Matrix Algebraic Characterization of CA. 2.5 Other Developments Under the New Phase of Activities. 2.5.1 Probabilistic Analysis of CA Behavior. 2.5.2 CA-Based Models for Physical Systems. 2.5.3 CA Machines (CAMs). 2.5.4 Fractional Dimensions in CA. 2.6 Consolidation in the VLSI Era. 2.6.1 Pseudorandom Pattern Generation. 2.6.2 Pseudoexhaustive Test Pattern Generation. 2.6.3 Deterministic Test Pattern Generation. 2.6.4 Signature Analysis. 2.6.5 CALBO (Cellular Automata Logic Block Observer). 2.6.6 Error Correcting Codes. 2.6.7 Low-Cost Associative Memory. 2.6.8 Finite-State Machine (FSM) Synthesis. 2.6.9 Synthesis of Easily Testable Combinational Logic. 2.6.10 Mod-p Multiplier. 2.6.11 Pattern Classification. 2.6.12 General and Perfect Hashing. 2.6.13 Design of a CA-Based Cipher System. 2.6.14 Modeling Amino Acid and Protein Chain. 2.7 Summary. 3 GROUP CA CHARACTERIZATION. 3.1 Introduction. 3.2 Characterization of the State-Transition Behavior. 3.3 Group Properties of CA. 3.3.1 Cycle Set Characterization of Group CA. 3.3.2 Characterization of Group CA with Inverse State-Transition Function. 3.3.3 Correlation of Length of a CA and a Group Rule. 3.3.4 Isomorphism between a CA and an LFSR Generating Exhaustive Pattern. 3.4 A Class of Null Boundary Group CA. 3.5 Group Properties of Periodic Boundary CA (PBCA) with Rules 90 and 150. 3.6 Analysis of Intermediate Boundary CA (IBCA). 3.6.1 Maximum-Length IBCA Configurations. 3.7 Phase Shift of PN-Sequences Generated by CA. 3.8 Programmable CA (PCA). 3.9 Summary. 4 CHARACTERIZATION OF NONGROUP CA. 4.1 Introduction. 4.2 General Characterization of Linear Nongroup CA. 4.2.1 Uniformity of the Tree-Structure in the State-Transition Diagram of a Linear Nongroup CA. 4.2.2 Characterization of Cyclic States. 4.2.3 Characterization of States in a Tree. 4.2.4 Characterization of States in an -Tree ( 6D0). 4.3 Characterization of Linear Multiple-Attractor Cellular Automata. 4.3.1 Construction of Multiple-Attractor CA (MACA). 4.4 Characterization of Complemented Additive CA. 4.4.1 General Characterization of Cyclic Behavior. 4.5 Behavior of Complemented CA Derived from Multiple-Attractor Linear CA. 4.5.1 An Acyclic State as the Complement Vector. 4.5.2 A Nonzero Attractor as the Complement Vector. 4.6 Characterization of D1*CA. 4.7 Summary. 5 CA AS A UNIVERSAL PATTERN GENERATOR. 5.1 Introduction. 5.2 Pseudoexhaustive Pattern Generation. 5.2.1 Analysis of PN Sequences Generated by a Primitive Polynomial. 5.2.2 Vector Space Theoretic Characterization. 5.2.3 Identification of n;m/Code Space and Exhaustive Pattern Generation by an m-Space. 5.2.4 CA as Pseudoexhaustive Test Pattern Generator. 5.3 On-Chip Deterministic Test Pattern Generation. 5.3.1 Overview of the Scheme. 5.3.2 Selection of a Primitive Polynomial. 5.3.3 Selection of CA/LFSR Structures. 5.3.4 Generation of Test Patterns with Multiple Seeds. 5.4 Exhaustive Two-and Three-Pattern Generation Capability of a CA. 5.4.1 Generation of Two-Pattern Test Vectors. 5.4.2 Generation of Three-Pattern Test Vectors. 5.4.3 90=150 CA as Exhaustive Two-/Three-Pattern Generator. 5.4.4 CA Selection Strategy for Generation of a Given -Pattern Set. 5.4.5 Experimental Results. 5.5 Summary. 6 CA-BASED ERROR CORRECTING CODE. 6.1 Introduction. 6.2 Review of Error Correcting Codes. 6.2.1 Bit Error Correcting/Detecting Codes. 6.2.2 Byte Error Detecting/Correcting Codes. 6.3 Design of Random Bit Error Correcting Codes. 6.3.1 CA-Based Error Correcting Code (CAECC). 6.3.2 Decoding of CA-Based Error Correcting Code. 6.3.3 Complexity Analysis. 6.4 CA-Based Byte Error Correcting Code. 6.4.1 Generation of CA-SbEC-DbED Code. 6.4.2 Decoding Scheme. 6.4.3 Generation of CA-DbEL/DbEC Code. 6.4.4 Implementation--Design of DbEL Cell. 6.4.5 General Design Methodology. 6.4.6 t-Byte Error Locating Code. 6.4.7 Reduction of Decoding Time. 6.5 CA Array-Based Diagnosis of Board-Level Faults. 6.5.1 Board-Level Fault Diagnosis Using Cellular Automata Array. 6.5.2 Encoding Output Responses of the Chips for Space Compression. 6.5.3 Time Compression of Check Symbols. 6.5.4 Syndrome Generation. 6.5.5 Detecting the t Number of Faulty Chips out of N Chips. 6.5.6 Performance. 6.6 Summary. 7 DESIGN OF CA-BASED CIPHER SYSTEM. 7.1 Introduction. 7.1.1 Permutation Groups. 7.2 Permutation Representation of CA States. 7.2.1 Permutation Representation of CA Having Equal Cycles of Even Length. 7.3 Definition of Fundamental Transformations. 7.4 PCA-Based Block Cipher Scheme. 7.4.1 Number of Enciphering Functions. 7.5 Stream Cipher Strategy. 7.5.1 Key Stream Generators. 7.5.2 PCA-Based Stream Cipher Scheme. 7.6 Invulnerability of the Scheme. 7.6.1 Block Ciphers. 7.6.2 Stream Ciphers. 7.7 Summary. 8 GENERATION OF HASHING FUNCTIONS. 8.1 Introduction. 8.2 CA-Based Scheme for General Hashing. 8.2.1 Analysis of CA-Based Hashing Scheme. 8.2.2 Implementation and Experimental Results. 8.3 Perfect Hashing. 8.4 TPSA CA-Based Perfect Hashing Scheme. 8.4.1 CA-Based Perfect Hashing. 8.5 Performance Evaluation of CA-Based Perfect Hashing Scheme. 8.5.1 Performance Evaluation. 8.6 Summary. 9 CA-BASED TESTABLE LOGIC SYNTHESIS. 9.1 Introduction. 9.2 Extended Characterization of D1*CA. 9.3 Synthesis of Testable FSM. 9.3.1 State Encoding Strategy. 9.3.2 Testing Scheme. 9.3.3 Fault Coverage. 9.3.4 Experimental Results. 9.3.5 Comparison of Test Time and Design Effort. 9.4 BIST Structure for Testing Combinational Logic. 9.4.1 New Results on D1*CA Behavior. 9.5 CA-Based Distributed BIST. 9.6 Test Methodology. 9.6.1 Test Procedure. 9.6.2 Discussions on Fault Coverage. 9.7 Experimental Results. 9.7.1 Test Parallelism and Fault Diagnosis. 9.8 Summary. 10 THEORY AND APPLICATION OF TWO-DIMENSIONAL CA. 10.1 Introduction. 10.2 Introduction to Two-Dimensional Cellular Automata. 10.2.1 Basic Concepts. 10.2.2 Partitioning of the T Matrix. 10.2.3 Characterization of 2-D CA. 10.2.4 Cycle Length for RVN CA. 10.2.5 Calculation of Depth and Cycle Length for Nongroup RVN CA. 10.3 Parallel PRPG Using 2-D CA. 10.3.1 Generating Test Patterns of Any Desired Length. 10.3.2 Applications of 2-D CA as a BIST Structure. 10.3.3 Pseudorandom Testing of Combinational Logic Circuits. 10.4 Design of Pseudoassociative Memory Using Cellular Automata. 10.4.1 CA-Based Hashing Scheme. 10.4.2 The Hardware for Pseudoassociative Memory. 10.4.3 Simulation Results. 10.4.4 Estimation of Worst-Case Performance. 10.4.5 Design of a Pseudoassociative Memory Chip. 10.5 Summary. BIBLIOGRAPHY. INDEX. ABOUT THE AUTHORS.

About the Author :
Parimal Pal Chaudhuri received a B.E. degree in electrical engineering in 1963 from Bengal Engineering College, Sibpur--one of the oldest pioneering engineering institutes in India. From 1963 to 1975 he was associated with IBM World Trade Corporation. Subsequently, he switched over to academia and started his career at Indian Institute of Technology (IIT), Kharagpur. In 1979 he received his Ph.D. degree. Dipanwita Roy Chowdhury received B.Tech. and M.Tech. degrees in computer science from the University of Calcutta, India, in 1987 and 1989, respectively. She received a Ph.D. degree from Indian Institute of Technology, Kharagpur, India, in 1994. Chowdhury received the prestigious Young Scientist Award of the Indian National Science Academy in 1994 for her outstanding research contributions. She served as an Assistant Professor in the Computer Science and Engineering Department of Regional Engineering college, Durgapur, India, in 1995. She is currently associated with IIT Kharagpur as a Visiting Faculty. Her research interests include fault-tolerant computing, synthesis for teastability, and the theory and application of Cellular Automata in various fields. Sukumar Nandi received his B.Sc. (hons) degree in physics in 1984, B.Tech. in instrumentation engineering in 1987, and M.Tech. in computer science in 1989. all from Calcutta University, India. He received a Ph.D. degree from IIT Kharagpur in 1995. From 1989 to 1990 he served at Birla Institute of Technology, Mesra, India, as a faculty member. Currently he is an Assistant Professor at Indian Institute of Technology, Guwahati, Assam, India. His research interests include error-correcting codes, data encryption, design for testability, and Cellular Automata. Santanu Chattopadhyay received his B.E. degree in computer science and technology in 1990 from Bengal Engineering College, Sibpur, India. He received his M.Tech and Ph.D. degrees from the Computer Science and Engineering Department of IIT Kharagpur in 1992 and 1996, respectively. He is currently associated as a faculty member with the Computer Science and Technology Department of Bengal Engineering College, an autonomous engineering university. He has continued a full-scale research thrust in VLSI design, and in the theory and applications of Cellular Automata in diverse fields.