Additive Cellular Automata: Theory and Applications, by Parimal Pal Chaudhuri, Dipanwita Roy Chowdhury, Sukumar Nandi, and Santanu Chattopadhyay PREFACE Research in the field of VLSI design was initiated at the Computer Science and Engineering Department of the Indian Institute of Technology (IU), Kharagpur, India, in the mid-1980s. One of the major emphases for this research group was VLSI testing, specifically the design of on-chip Built-ln-Self-Test (BIST) structures to enhance the testability of VLSI circuits. In the very early stage of its activities. the research group made the following major observations: (a) The VLSI design community always prefers to have simple, regular, and modular building blocks to realize a complex function. (b) In the era of submicron technology, an interconnection on the silicon floor is likely to behave more like a device rather than as a simple signal path. (c) Linear Feedback Shift Register (LFSR) is normally used as the basic BIST structure for testing digital circuits. LFSR has been widely studied in the last few decades, and excellent analytical tools based on polynomial algebra are available to characterize its behavior. However, it is not modular or cascadable. and it has an irregular and nonlocal interconnection structure. Given this background, the research group looked for a simple, regular, modular, and cascadable structure with a local neighborhood-as an alternative to LFSR. The two-state-per-cell, three-neighborhood cellular automata (CA) is identified to be an ideal structure supporting all these requirements. On further scrutiny, it is observed that there exists no analytical tool to characterize its state-transition behavior. This has motivated us to undertake exhaustive study of CA behavior in order to formulate an elegant matrix algebraic tool that will completely characterize its behavior and develop a wide variety of applications. Six Ph.D. theses that encompassed all the related research works were completed under my supervision from 1988 to 1995. This book provides a comprehensive report of all of these research materials. some of which have already been published as research papers in international journals and conferences. Full-scale research thrust was initiated around 1987-88 to develop the theory and applications of CA. Dr. Aloke Kumar Das completed his Ph.D. thesis entitled 'Theory and Applications of Cellular Automata for Built-In-Self-Test Structure." Matrix algebraic tools were developed to characterize group CA and develop its applications in the field of VLSI testing. CA-based schemes for generation of pseudorandom and pseudoexhaustive patterns were developed, and work on a CA-based signature analyzer was initiated as well. This research laid the foundation for subsequent work. Another researcher, Dr. Susanta Misra. carried forward the application of CA as BIST structure supporting both test generation and signature analyzer in his thesis "Theory and Application of Additive Cellular Automata for easily testable VLSI circuit design." Dr. Misra also initiated the research in the field of CA-based finite-state machine (FSM) synthesis, in collaboration with another research scholar, Dr. Biswadip Mitral who did his Ph.D. thesis work in the field of "Synthesis of Testable VLSI Designs from High-Level Specifications." The next phase of activities was initiated with the research work of Dr. Dipanwita Roy Chowdhury in her thesis entitled "Theory and Applications of Additive Cellular Automata for Reliable and Testable VLSI Circuit Design." Dr. Chowdhury concentrated on developing schemes for CA-based easily testable FSM, bit-error correcting code, byte error correcting code, and characterization of two-dimensional CA. At approximately the same time, Dr. Sukumar Nandi initiated his research work in the field of CA-based universal pattern generation, data encryption, and synthesis of easily testable combinational logic. His Ph.D. thesis, "Additive Cellular Automata: Theory and Application for Testable Circuit Design and Data Encryption," also covered new characterizations of group CA behavior and CA-based tools for fault diagnosis. In all of the aforementioned research works, nongroup CA were not studied in detail. The exhaustive study of nongroup CA behavior was undertaken by Dr. Santanu Chattopadhyay in his Ph.D. thesis entitled "Some Studies on Theory and Applications of Additive Cellular Automata" He also extended CA applications in the fields of hashing function generation, multiple byte error correcting code, and board-level fault diagnosis. In their M.Tech. theses (1995-1996) Subhasish Mitra and Arindam Majumdar extended the theory for characterizing GF(2q) CA and developed the GF(22) CA-based model for amino acids. Subhasish also refined the earlier work in the field of testable synthesis. The current ongoing work deals with a CA-based model for (i) amino acid and protein chain, and (ii) fractals. Dr. Swagata Dasgupta and Dr. Dipanwita Roy Chowdhury are currently doing research in these areas at IIT Kharagpur. Dr. Santanu Chattopadhyay, currently a faculty member of the Department of Computer Science and Technology at Bengal Engineering College (a Deemed University), is further extending the research in the field of CA. In 1993-94 we prepared the first version of the manuscript for this book. Since then further interesting developments have occurred in the field of CA theory and applications. All these new results will be published in Volume 2 of Additive Cellular Automata: Theory and Applications. Dr. Dipanwita Roy Chowdhury, Dr. Sukumar Nandi, and Dr. Santanu Chattopadhyay, the three members of the research team, are the coauthors of this book. In addition, a large number of undergraduate and postgraduate students have contributed substantially to the research work for developing CA theory and applications. Notable among them are Saugata Basu, Supratik Chakrabarty, B. Vamsi, Manjit Ray, and Sumit Roy. who joined this research group and completed their undergraduate projects during the period 1990 to 1994. Supratik Chakrabarty completed his undergraduate project in 1993 and made excellent contributions. Professor Indranil Sengupta, a faculty member of the Computer Science and Engineering Department of IIT Kharagpur has always come forward to help us in this research work. A large number of other faculty members in the department provided inspiration and encouragement for the activities of this group as well. Notable among them are Professors A.K. Majymdar, S.C. De Sarkar, D. Sarkar, A. Basu, S. Ghosh. S.P. Pal, P.P. Chakrabarty, P.P. Das, T.K. Dey, A. Pal, and P. Bhattacharya. I convey my sincere thanks to all of the students and faculty members whose help was essential to carry forward the research work reported in this book. It is also necessary to acknowledge the financial support received from the Department of Electronics (DOE), Government of India, for the sponsored research projects. Two DOE of ficials, Dr. U.P. Phadke and Dr. S.P. Uttam, were extremely helpful and provided excellent support that enabled us to make such an extensive research in the theory and applications of CA in the past eight years. I would also like to express my thanks to Intel Corporation and Mr. Manpreet S. Khaira of Intel Corporation (and my ax-student from IIT Kharag,pur) for inviting me as a Visiting Faculty at Intel in 1997. This has greatly facilitated the proofreading and final correction of the manuscript of this book. Finally, I would like to convey my sincere thanks and appreciation for the untiring support and encouragement that this research group received from my wife, Dr. Jayasree Pal Chaudhuri (a medical officer at I1T Kharagpur B C Roy Technology Hospital). P. Pal Chaudhuri 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 Pattern3.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 a-Tree (a ~ 0) 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 a-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 Coda 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 Steam 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 Dl*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