Additive Cellular Automata: Theory and Applications, Volume 1

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.