Additive Cellular Automata Theory and Applications, Volume 1

by Chaudhuri, Parimal Pal; Chowdhury, Dipanwita Roy; Nandi, Sukumar; Chattopadhyay, Santanu

• ISBN13: 9780818677175
• ISBN10: 0818677171
• Edition: 1st
• Format: Paperback
• Copyright: 1997-07-11
• Publisher: Wiley-IEEE Computer Society Pr

Summary

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.

Author Biography

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.

Table of Contents

PREFACE	xxi
1 INTRODUCTION	1	(5)
1.1 Cellular Automata Applications	3	(1)
1.2 Overview of the Book	4	(2)
2 CA AND ITS APPLICATIONS: A BRIEF SURVEY	6	(20)
2.1 Introduction	6	(1)
2.2 Initial Phase of Development	6	(1)
2.3 CA-Based Models	7	(2)
2.3.1 CA as Parallel Language Recognizer	7	(1)
2.3.2 Biological Applications of CA	8	(1)
2.3.3 CA as Parallel and Image Processing Systems	8	(1)
2.4 New Phase of Development	9	(7)
2.4.1 Polynomial Algebraic Characterization of CA Behavior	13	(3)
2.4.2 Matrix Algebraic Characterization of CA	16	(1)
2.5 Other Developments Under the New Phase of Activities	16	(2)
2.5.1 Probabilistic Analysis of CA Behavior	16	(1)
2.5.2 CA-Based Models for Physical Systems	17	(1)
2.5.3 CA Machines (CAMs)	17	(1)
2.5.4 Fractional Dimensions in CA	18	(1)
2.6 Consolidation in the VLSI Era	18	(7)
2.6.1 Pseudorandom Pattern Generation	18	(1)
2.6.2 Pseudoexhaustive Test Pattern Generation	19	(1)
2.6.3 Deterministic Test Pattern Generation	19	(2)
2.6.4 Signature Analysis	21	(1)
2.6.5 CALBO (Cellular Automata Logic Block Observer)	22	(1)
2.6.6 Error Correcting Codes	22	(1)
2.6.7 Low-Cost Associative Memory	23	(1)
2.6.8 Finite-State Machine (FSM) Synthesis	23	(1)
2.6.9 Synthesis of Easily Testable Combinational Logic	23	(1)
2.6.10 Mod-p Multiplier	24	(1)
2.6.11 Pattern Classification	24	(1)
2.6.12 General and Perfect Hashing	24	(1)
2.6.13 Design of a CA-Based Cipher System	24	(1)
2.6.14 Modeling Amino Acid and Protein Chain	25	(1)
2.7 Summary	25	(1)
3 GROUP CA CHARACTERIZATION	26	(30)
3.1 Introduction	26	(1)
3.2 Characterization of the State-Transition Behavior	27	(2)
3.3 Group Properties of CA	29	(9)
3.3.1 Cycle Set Characterization of Group CA	33	(1)
3.3.2 Characterization of Group CA with Inverse State-Transition Function	34	(1)
3.3.3 Correlation of Length of a CA and a Group Rule	35	(2)
3.3.4 Isomorphism between a CA and an LFSR Generating Exhaustive Pattern	37	(1)
3.4 A Class of Null Boundary Group CA	38	(3)
3.5 Group Properties of Periodic Boundary CA (PBCA) with Rules 90 and 150	41	(1)
3.6 Analysis of Intermediate Boundary CA (IBCA)	42	(6)
3.6.1 Maximum-Length IBCA Configurations	44	(4)
3.7 Phase Shift of PN-Sequences Generated by CA	48	(4)
3.8 Programmable CA (PCA)	52	(2)
3.9 Summary	54	(2)
4 CHARACTERIZATION OF NONGROUP CA	56	(40)
4.1 Introduction	56	(2)
4.2 General Characterization of Linear Nongroup CA	58	(11)
4.2.1 Uniformity of the Tree-Structure in the State-Transition Diagram of a Linear Nongroup CA	63	(3)
4.2.2 Characterization of Cyclic States	66	(1)
4.2.3 Characterization of States in a Tree	67	(1)
4.2.4 Characterization of States in an -Tree ( 6D0)	67	(2)
4.3 Characterization of Linear Multiple-Attractor Cellular Automata	69	(9)
4.3.1 Construction of Multiple-Attractor CA (MACA)	73	(5)
4.4 Characterization of Complemented Additive CA	78	(3)
4.4.1 General Characterization of Cyclic Behavior	78	(3)
4.5 Behavior of Complemented CA Derived from Multiple-Attractor Linear CA	81	(6)
4.5.1 An Acyclic State as the Complement Vector	82	(3)
4.5.2 A Nonzero Attractor as the Complement Vector	85	(2)
4.6 Characterization of D1*CA	87	(8)
4.7 Summary	95	(1)
5 CA AS A UNIVERSAL PATTERN GENERATOR	96	(41)
5.1 Introduction	96	(1)
5.2 Pseudoexhaustive Pattern Generation	97	(20)
5.2.1 Analysis of PN Sequences Generated by a Primitive Polynomial	98	(5)
5.2.2 Vector Space Theoretic Characterization	103	(4)
5.2.3 Identification of n;m/Code Space and Exhaustive Pattern Generation by an m-Space	107	(6)
5.2.4 CA as Pseudoexhaustive Test Pattern Generator	113	(4)
5.3 On-Chip Deterministic Test Pattern Generation	117	(10)
5.3.1 Overview of the Scheme	117	(1)
5.3.2 Selection of a Primitive Polynomial	118	(2)
5.3.3 Selection of CA/LFSR Structures	120	(3)
5.3.4 Generation of Test Patterns with Multiple Seeds	123	(4)
5.4 Exhaustive Two-and Three-Pattern Generation Capability of a CA	127	(9)
5.4.1 Generation of Two-Pattern Test Vectors	128	(1)
5.4.2 Generation of Three-Pattern Test Vectors	129	(1)
5.4.3 90=150 CA as Exhaustive Two-/Three-Pattern Generator	130	(2)
5.4.4 CA Selection Strategy for Generation of a Given -Pattern Set	132	(2)
5.4.5 Experimental Results	134	(2)
5.5 Summary	136	(1)
6 CA-BASED ERROR CORRECTING CODE	137	(65)
6.1 Introduction	137	(1)
6.2 Review of Error Correcting Codes	138	(8)
6.2.1 Bit Error Correcting/Detecting Codes	138	(5)
6.2.2 Byte Error Detecting/Correcting Codes	143	(3)
6.3 Design of Random Bit Error Correcting Codes	146	(23)
6.3.1 CA-Based Error Correcting Code (CAECC)	146	(11)
6.3.2 Decoding of CA-Based Error Correcting Code	157	(11)
6.3.3 Complexity Analysis	168	(1)
6.4 CA-Based Byte Error Correcting Code	169	(17)
6.4.1 Generation of CA-SbEC-DbED Code	169	(3)
6.4.2 Decoding Scheme	172	(5)
6.4.3 Generation of CA-DbEL/DbEC Code	177	(4)
6.4.4 Implementation--Design of DbEL Cell	181	(2)
6.4.5 General Design Methodology	183	(1)
6.4.6 t-Byte Error Locating Code	184	(1)
6.4.7 Reduction of Decoding Time	185	(1)
6.5 CA Array-Based Diagnosis of Board-Level Faults	186	(15)
6.5.1 Board-Level Fault Diagnosis Using Cellular Automata Array	187	(3)
6.5.2 Encoding Output Responses of the Chips for Space Compression	190	(2)
6.5.3 Time Compression of Check Symbols	192	(1)
6.5.4 Syndrome Generation	192	(1)
6.5.5 Detecting the t Number of Faulty Chips out of N Chips	192	(6)
6.5.6 Performance	198	(3)
6.6 Summary	201	(1)
7 DESIGN OF CA-BASED CIPHER SYSTEM	202	(17)
7.1 Introduction	202	(3)
7.1.1 Permutation Groups	204	(1)
7.2 Permutation Representation of CA States	205	(1)
7.2.1 Permutation Representation of CA Having Equal Cycles of Even Length	206	(1)
7.3 Definition of Fundamental Transformations	206	(2)
7.4 PCA-Based Block Cipher Scheme	208	(3)
7.4.1 Number of Enciphering Functions	210	(1)
7.5 Stream Cipher Strategy	211	(6)
7.5.1 Key Stream Generators	212	(3)
7.5.2 PCA-Based Stream Cipher Scheme	215	(2)
7.6 Invulnerability of the Scheme	217	(1)
7.6.1 Block Ciphers	217	(1)
7.6.2 Stream Ciphers	217	(1)
7.7 Summary	218	(1)
8 GENERATION OF HASHING FUNCTIONS	219	(23)
8.1 Introduction	219	(2)
8.2 CA-Based Scheme for General Hashing	221	(8)
8.2.1 Analysis of CA-Based Hashing Scheme	222	(2)
8.2.2 Implementation and Experimental Results	224	(5)
8.3 Perfect Hashing	229	(1)
8.4 TPSA CA-Based Perfect Hashing Scheme	230	(9)
8.4.1 CA-Based Perfect Hashing	232	(7)
8.5 Performance Evaluation of CA-Based Perfect Hashing Scheme	239	(2)
8.5.1 Performance Evaluation	239	(2)
8.6 Summary	241	(1)
9 CA-BASED TESTABLE LOGIC SYNTHESIS	242	(32)
9.1 Introduction	242	(1)
9.2 Extended Characterization of D1*CA	243	(1)
9.3 Synthesis of Testable FSM	244	(12)
9.3.1 State Encoding Strategy	246	(2)
9.3.2 Testing Scheme	248	(4)
9.3.3 Fault Coverage	252	(1)
9.3.4 Experimental Results	253	(2)
9.3.5 Comparison of Test Time and Design Effort	255	(1)
9.4 BIST Structure for Testing Combinational Logic	256	(7)
9.4.1 New Results on D1*CA Behavior	256	(7)
9.5 CA-Based Distributed BIST	263	(4)
9.6 Test Methodology	267	(2)
9.6.1 Test Procedure	268	(1)
9.6.2 Discussions on Fault Coverage	269	(1)
9.7 Experimental Results	269	(4)
9.7.1 Test Parallelism and Fault Diagnosis	271	(2)
9.8 Summary	273	(1)
10 THEORY AND APPLICATION OF TWO-DIMENSIONAL CA	274	(40)
10.1 Introduction	274	(1)
10.2 Introduction to Two-Dimensional Cellular Automata	274	(14)
10.2.1 Basic Concepts	274	(3)
10.2.2 Partitioning of the T Matrix	277	(1)
10.2.3 Characterization of 2-D CA	278	(2)
10.2.4 Cycle Length for RVN CA	280	(4)
10.2.5 Calculation of Depth and Cycle Length for Nongroup RVN CA	284	(4)
10.3 Parallel PRPG Using 2-D CA	288	(11)
10.3.1 Generating Test Patterns of Any Desired Length	294	(1)
10.3.2 Applications of 2-D CA as a BIST Structure	295	(2)
10.3.3 Pseudorandom Testing of Combinational Logic Circuits	297	(2)
10.4 Design of Pseudoassociative Memory Using Cellular Automata	299	(14)
10.4.1 CA-Based Hashing Scheme	300	(3)
10.4.2 The Hardware for Pseudoassociative Memory	303	(2)
10.4.3 Simulation Results	305	(2)
10.4.4 Estimation of Worst-Case Performance	307	(5)
10.4.5 Design of a Pseudoassociative Memory Chip	312	(1)
10.5 Summary	313	(1)
BIBLIOGRAPHY	314	(13)
INDEX	327	(12)
ABOUT THE AUTHORS	339