Additive Cellular Automata Theory and Applications, Volume 1

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

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

ISBN: 9780818677175 | 0818677171
Cover: Paperback
Copyright: 7/11/1997

Buy New

Print on Demand: 2-4 Weeks. This item cannot be cancelled or returned.

$98.71

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.

PREFACE

xxi

1 INTRODUCTION

(5)

1.1 Cellular Automata Applications

(1)

1.2 Overview of the Book

(2)

2 CA AND ITS APPLICATIONS: A BRIEF SURVEY

(20)

2.1 Introduction

(1)

2.2 Initial Phase of Development

(1)

2.3 CA-Based Models

(2)

2.3.1 CA as Parallel Language Recognizer

(1)

2.3.2 Biological Applications of CA

(1)

2.3.3 CA as Parallel and Image Processing Systems

(1)

2.4 New Phase of Development

(7)

2.4.1 Polynomial Algebraic Characterization of CA Behavior

(3)

2.4.2 Matrix Algebraic Characterization of CA

(1)

2.5 Other Developments Under the New Phase of Activities

(2)

2.5.1 Probabilistic Analysis of CA Behavior

(1)

2.5.2 CA-Based Models for Physical Systems

(1)

2.5.3 CA Machines (CAMs)

(1)

2.5.4 Fractional Dimensions in CA

(1)

2.6 Consolidation in the VLSI Era

(7)

2.6.1 Pseudorandom Pattern Generation

(1)

2.6.2 Pseudoexhaustive Test Pattern Generation

(1)

2.6.3 Deterministic Test Pattern Generation

(2)

2.6.4 Signature Analysis

(1)

2.6.5 CALBO (Cellular Automata Logic Block Observer)

(1)

2.6.6 Error Correcting Codes

(1)

2.6.7 Low-Cost Associative Memory

(1)

2.6.8 Finite-State Machine (FSM) Synthesis

(1)

2.6.9 Synthesis of Easily Testable Combinational Logic

(1)

2.6.10 Mod-p Multiplier

(1)

2.6.11 Pattern Classification

(1)

2.6.12 General and Perfect Hashing

(1)

2.6.13 Design of a CA-Based Cipher System

(1)

2.6.14 Modeling Amino Acid and Protein Chain

(1)

2.7 Summary

(1)

3 GROUP CA CHARACTERIZATION

(30)

3.1 Introduction

(1)

3.2 Characterization of the State-Transition Behavior

(2)

3.3 Group Properties of CA

(9)

3.3.1 Cycle Set Characterization of Group CA

(1)

3.3.2 Characterization of Group CA with Inverse State-Transition Function

(1)

3.3.3 Correlation of Length of a CA and a Group Rule

(2)

3.3.4 Isomorphism between a CA and an LFSR Generating Exhaustive Pattern

(1)

3.4 A Class of Null Boundary Group CA

(3)

3.5 Group Properties of Periodic Boundary CA (PBCA) with Rules 90 and 150

(1)

3.6 Analysis of Intermediate Boundary CA (IBCA)

(6)

3.6.1 Maximum-Length IBCA Configurations

(4)

3.7 Phase Shift of PN-Sequences Generated by CA

(4)

3.8 Programmable CA (PCA)

(2)

3.9 Summary

(2)

4 CHARACTERIZATION OF NONGROUP CA

(40)

4.1 Introduction

(2)

4.2 General Characterization of Linear Nongroup CA

(11)

4.2.1 Uniformity of the Tree-Structure in the State-Transition Diagram of a Linear Nongroup CA

(3)

4.2.2 Characterization of Cyclic States

(1)

4.2.3 Characterization of States in a Tree

(1)

4.2.4 Characterization of States in an -Tree ( 6D0)

(2)

4.3 Characterization of Linear Multiple-Attractor Cellular Automata

(9)

4.3.1 Construction of Multiple-Attractor CA (MACA)

(5)

4.4 Characterization of Complemented Additive CA

(3)

4.4.1 General Characterization of Cyclic Behavior

(3)

4.5 Behavior of Complemented CA Derived from Multiple-Attractor Linear CA

(6)

4.5.1 An Acyclic State as the Complement Vector

(3)

4.5.2 A Nonzero Attractor as the Complement Vector

(2)

4.6 Characterization of D1*CA

(8)

4.7 Summary

(1)

5 CA AS A UNIVERSAL PATTERN GENERATOR

(41)

5.1 Introduction

(1)

5.2 Pseudoexhaustive Pattern Generation

(20)

5.2.1 Analysis of PN Sequences Generated by a Primitive Polynomial

(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

Please wait while the item is added to your bag...

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Additive Cellular Automata Theory and Applications, Volume 1

Summary

Author Biography

Table of Contents

Supplemental Materials