This paper reports a fault diagnosis scheme for very large scale integrated (VLSI) circuits. A special class of cellular automata (CA) referred to as multiple attractor CA (MACA) is employed for the design. State transition behavior of MACA has been analyzed to build a model that can efficiently classify the test responses of a VLSI circuit to diagnose its faulty subcircuit. The MACA-based model, in effect, provides an implicit storage for voluminous test response data and replaces the traditional fault dictionary used for diagnosis of VLSI circuits. The proposed diagnosis scheme employs significantly lesser memory to store the MACA parameters and performs faster diagnosis. Experimental results establish the efficiency of the model in respect of memory overhead, execution speed and percentage of diagnosis.

This paper reports an efficient design of test pattern generators (TPGs) for a chip having multiple cores. It is built around nonlinear cellular automata (CA) based pseudo-random pattern generator (PRPG). The modular and cascadable structure of proposed n-cell PRPG can be utilized to construct the (n+1)-cell PRPG without sacrificing the pseudo-randomness quality. The efficiency of such a scalable PRPG structure is demonstrated in designing the on-chip TPGs for a VLSI chip implementing multiple cores.

This work reports the design of a fool proof on-chip test pattern generator (TPG) for very large scale integration circuits. The TPG is designed to generate pseudorandom test patterns without a given prohibited pattern set (PPS). It ensures desired pseudorandom quality of the generated test patterns and maintains fault coverage close to the figures achieved with a conventional maximal length linear feedback shift register/cellular automaton (CA)-based TPG. The theory of vector subspace generated by a CA (Chaudhuri, 1997) has provided the foundation of this design. The proposed TPG does not incur any additional cost for the avoidance of PPS.

This paper reports a cellular automata (CA) based model of associative memory. The model has been evolved around a special class of CA referred to as generalized multiple attractor cellular automata (GMACA). The GMACA based associative memory is designed to address the problem of pattern recognition. Its storage capacity is found to be better than that of Hopfield network. The GMACA are configured with nonlinear CA rules that are evolved through genetic algorithm (GA). Successive generations of GA select the rules at the edge of chaos. The study confirms the potential of GMACA to perform complex computations like pattern recognition at the edge of chaos.

This paper reports an efficient BIST solution for VLSI circuits. The solution is based on an onchip Pseudo-Random Pattern Generator (PRPG). The test solution guarantees non-issuence of the test patterns declared prohibited to a CUT (Circuit Under Test). It has been developed around non-linear Cellular Automata (CA) and provides a linear time solution of designing an n-bit PRPG. Experimental results confirm the enhanced pseudo-random quality of the test patterns due to application of non-linear CA rules.

This paper reports the error correcting capability of an associative memory model built around the sparse network of cellular automata (CA). Analytical formulation supported by experimental results has demonstrated the capability of CA based sparse network to memorize unbiased patterns while accommodating noise. The desired CA are evolved with an efficient formulation of simulated annealing (SA) program. The simple, regular, modular, and cascadable structure of CA based associative memory suits ideally for design of low cost high speed online pattern recognizing machine with the currently available VLSI technology.

This paper reports the design of an on-chip Test Pattern Generator (TPG) for VLSI circuits that avoids generation of a given Prohibited Pattern Set (PPS). The design ensures desired pseudo-random quality of the test patterns generated while ensuring fault coverage close to the figures achieved with a typical Pseudo Random Pattern Generator (PRPG) designed around maximal length LFSR/CA. The theoretical framework of CA has provided the foundation of this work. A GA based evolution scheme is employed to achieve the desired TPG developed over the theory of cellular automata.

This paper reports an efficient technique of evolving Cellular Automata (CA) as an associative memory model. The evolved CA termed as GMACA (Generalized Multiple Attractor Cellular Automata), acts as a powerful pattern recognizer. Detailed analysis of GMACA rules establishes the fact that the rule subspace of the pattern recognizing CA lies at the edge of chaos — believed to be capable of executing complex computation.

This paper extends the theory of autonomous linear machines (LMs). The theory of the extension field has provided the foundation for the design of such machines referred to as Extended Linear Machines (ELM). An analytical framework has been reported to completely characterize the vector subspace generated by an ELM and also different variations of LMs having cyclic, as well as noncyclic vector subspaces. This formulation has resulted in a single algorithm that characterizes each of the vector subspaces in terms of cyclic and noncyclic subspaces. An ELM significantly reduces the computation time for characterizing the model and study of the behavior of the physical system compared to conventional binary linear machines.

This paper reports a general methodology and a computer-aided design (CAD) tool (BECAS 1.0) for synthesis of linear analog functions with a network of operational transconductance amplifiers (OTAs). Efficient analog circuits have been synthesized with the CAD tool and reported along with the simulation results. SPICE simulated results of the synthesized circuit match closely with those derived theoretically from the input transfer function. A first-order low-pass filter employing a minimum number of OTAs is used in the design as the basic building block. The number of OTAs employed to realize an analog function can be minimized in the optimization phase of the synthesis algorithm.

This paper introduces the concept of hierarchical cellular automata (HCA). The theory of HCA is developed over the Galois extension field GF(2(pqr..)), where each cell of the CA can store and process a symbol in the extension field GF (2(pqr..)). The hierarchical field structure of GF(2(pqr..)) is employed for design of an HCA-based test pattern generator (HCATPG). The HCATPG is ideally suited for testing very large scale integration circuits specified in hierarchical structural description. Experimental results establish the fact that the HCATPG achieves higher fault coverage than that which could be achieved with any other test structures. The concept of percentile improvement in fault coverage is introduced to have a realistic assessment of fault coverage achieved with the proposed RCATPG.

This paper presents an efficient BIST solution for VLSI circuit testing based on GF(2p) CA (Cellular automata on an extended Galois Field). The novel architecture of GF(2p)) CA permits the BIST structure to be highly customized to the circuit under test (CUT). A methodology has been proposed to optimize the design of GF(2p) CA structure to maximize the fault coverage in a given CUT. In addition, an innovative scheme based on logic folding is presented to reduce the BIST overhead and make it more effective for large circuits.

This paper uses the hierarchical structure of a VLSI circuit to design an efficient diagnosis scheme. A special class of non-group GF(2/sup p/) CA referred to as multiple attractor cellular automata (MACH) is introduced to diagnose the faulty block of a circuit under test (CUT). The scheme employs significantly lesser memory and performs faster diagnosis than the existing methods reported so far. Experimental results validate the efficiency of the proposed scheme in terms of diagnostic resolution and execution speed along with significant reduction of memory.

This paper presents a recursive technique for generation of pseudoexhaustive test patterns. The scheme is optimal in the sense that the first 2/sup k/ vectors cover all adjacent k-bit spaces exhaustively. It requires substantially less hardware than the existing methods and utilizes the regular, modular, and cascadable structure of local neighborhood Cellular Automata (CA), which is ideally suited for VLSI implementation. In terms of XOR gates, this approach outperforms earlier methods by 15 to 50 percent. Moreover, test effectiveness and hardware requirements have been established analytically, rather than by simple simulation and logic minimization.

At very high frequencies, the major potential of asynchronous circuits is absence of clock skew and, through that, better exploitation of relative timing relations. This paper presents Fsimac, a gate-level fault simulator for stuck-at and gate-delay faults in asynchronous sequential circuits. Fsimac not only evaluates combinational logic and typical asynchronous gates such as Muller C-elements, but also complex domino gates, which are widely used in high-speed designs. Our algorithm for desecting feedback loops is designed so as to minimize the iterations for simulating the unfolded circuit. We use min-max timing analysis to compute the bounds on the signal delays. Stuck-at faults are detected by comparing logic values at the primary outputs against the corresponding values in the fault-free design. For delay faults, we additionally compare min-max rime stamps for primary output signals. Fault coverage reported by Fsimac for pseudo-random tests generated by Cellular Automata show some very good results, but also indicate test holes for which more specific patterns are needed. We intend to deploy Fsimac for designing more effective CA-BIST.

This paper reports the use of a class of cellular automata for the testing and diagnosis of faults in analog circuits. The use of the scheme is explained with reference to the testing of OTA based circuits.

A novel scheme for board level fault diagnosis based on cellular automata array (CAA) is presented. In the proposed diagnosis scheme, the output responses of the chips are encoded by applying the strategy of CA-based byte error correcting code. The encoded response symbols for different test vectors are compressed to a signature. The decoding scheme of byte error correcting code is subsequently employed to detect the faulty chips on the board. The CAA-based design for the fault diagnosis strategy results in a simple and modular test structure that is well suited for VLSI implementation. The scheme can be applied for testing and diagnosis of multichip modules (MCMs) as well.

This reply emphasizes the point that the regular, modular, cascadable structure of local neighborhood CA can be employed for building low cost cipher system hardware. This cost effective engineering solution can achieve desired level of security with larger size CA.

In the domain of combinational logic synthesis, logic minimization plays a vital role in determining the area and performance of the synthesized circuit. Logic minimization based on AND-OR decomposition of functions is a well studied area. However, minimization based on AND-XOR decomposition has received relatively lesser attention. Since many real-life combinational functions are XOR dominated, a logic minimizer producing efficient AND-XOR decomposition can lead to more efficient realization of such circuits. The computer-aided design tool KGPXORMIN presented in this paper is a multilevel AND-XOR minimizer which outperforms the scheme reported by Saul (1991) by 45.77% in the literal count metric. In general, most of the real-life and benchmark circuits are a combination of OR and XOR logic. In order to have area efficient realization, we need to have an efficient minimizer capable of judicious use of OR and XOR gates. An integrated tool KGPMIN has been developed which combines the AND-XOR minimizer KGPXORMIN and well-known AND-OR minimizer MISII. Depending on the measure of dominance of OR and XOR logic, it switches from one minimizer to the other during the decomposition phase. By judicious switching from one minimizer to the other, on the average, KGPMIN outperforms MISII by 64.08% in literal count and 45.16% in absolute gate area for the MCNC combinational logic benchmarks. It also outperforms KGPXORMIN by 17.46% in literal count and 34.32% in gate area. The number of levels of the circuits synthesized with KGPMIN can be found to be comparable with the figures arrived at from the application of MISII.

Analytical study of three neighbourhood two state per cell Cellular Automata (CA) behaviour is a comparatively recent phenomenon. A wide variety of applications have been developed utilizing the elegant structure of group CA. In this paper some of the characterizations of the state transition behaviour of non-group CA are reported. These results are subsequently utilized to develop an efficient parallel scheme for image compression. The experimental results confirms compression ratio of the CA based scheme is of the same order as that of JPEG coding.

The paper reports some of the interesting properties and relationships of a nongroup cellular automata (CA) and its dual. A special class of nongroup cellular automata denoted as D1*CA is analytically investigated. Based on such analysis, D1*CA has been proposed as an ideal test machine which can be efficiently embedded in a finite state machine to enhance the testability of the synthesized design. A state encoding algorithm has been formulated to embed the D1*CA based test machine in the synthesized FSM while minimizing the hardware overhead. The unique state transition properties of D1*CA are then used in designing an easy testing scheme for the FSM. Experiments on FSM benchmarks have shown that the scheme achieves 100% coverage of all single stuck at faults at the cost of hardware overhead and circuit delay that are comparable, if not better, to that incurred for scan path based designs. However, the major advantage of the scheme is the significant reduction of test time overhead due to integration of an embedded test machine in the design at the synthesis phase.

Specific inherent advantages of AND-XOR networks have encouraged researchers to look for efficient minimization and synthesis tools for their realization. Among several canonical representations of AND-XOR networks, the most easily testable one is the fixed polarity Consistent Generalized Reed Muller (CGRM) form. In this paper, a Genetic Algorithm (GA) formulation of the problem of finding the polarity of the variables resulting in minimum number of product terms has been proposed. The quality of the solution obtained and the high rate of convergence have established the effectiveness of the genetic algorithm in solving this particular NP-hard problem. Further, the inherent parallelism of genetic algorithm makes the proposed scheme an ideal candidate for solving the problem in a multiprocessor environment.

Considerable interest has been recently generated in the study of Cellular Automata (CA) behavior. Polynomial and matrix algebraic tools are employed to characterize some of the properties of null/periodic boundary CA. Some other results of group CA behavior have been reported based on simulation studies. This paper reports a formal proof for the conjecture-there exists no primitive characteristic polynomial of 90/150 CA with periodic boundary condition. For generation of high quality pseudorandom patterns, it is necessary to employ CA having primitive characteristic polynomial. There exist two null boundary CA for every primitive polynomial. However, for such Cs the quality of pseudorandomness suffers in general, particularly in the regions around the terminal cells because of null boundary condition. In this background, a new concept of intermediate boundary CA has been proposed to generate pseudorandom patterns that are better in quality than those generated with null boundary CA. Some interesting properties of intermediate boundary CA are also reported.

The design of a cellular automata (CA) based byte error correcting code analogous to an extended Reed-Solomon code has been proposed by Chowdhury et al. (1982, 1985). This code has the same restrictions on error correction as that of an extended R-S code. A new design scheme has been reported for parallel implementation of the CA based SbEC/DbED and DbEC/DbED code that is analogous to the conventional R-S code. Both the encoder and decoder of this code can be efficiently implemented with an array of CA (CAA) with high throughput. The design is ideally suited for high speed memory systems built with byte organized RAM chips. Extension of the scheme to detect/correct a larger number of byte errors has also been reported. Throughput of the decoder to handle tbyte errors (t/spl les/4) can be found to be substantially better than that of a conventional R-S decoder. The proposed decoder provides a simple, modular and cost effective design that is ideally suited for VLSI implementation.

Characterization of a special class of nongroup CA termed as D1*CA has been proposed previously (1993) along with its application for synthesis of easily testable FSM. This paper extends application of the D1*CA as an ideal test machine for testing combinational logic (CL) blocks and registers of a circuit. Such a test machine can be conveniently embedded in the data path synthesis phase around the function realized by a CL block and the register feeding the input data to the CL. In the normal mode of operation, the register and the CL realize the intended function. During testing, the D1*CA runs in autonomous mode generating the test vectors and also accumulating test responses. It is sufficient to observe the response only from the leftmost CA cell with aliasing error probability approaching zero value. Experiments conducted on CL benchmarks confirm 100% fault coverage of all stuck-at faults in CL and its associated lines. It does not incur any test generation and test application overheads. Further, test parallelism can be achieved through simultaneous testing of multiple combinational modules in a chip. The scheme provides a cost effective alternative to scan path.

The present paper reports a novel scheme for designing fast retrieval memory system using cellular automata. In essence, the proposed scheme implements the concept of hashing in hardware. This makes possible the design of low-cost high-capacity memory systems with limited content addressability as an option. The efficiency of the scheme has been verified through extensive simulation studies of the hardwired hashing function built around 1D and 2D linear cellular automata (CA).>

This paper reports a novel approach for designing byte error-correcting codes using cellular automata (CA). A simple scheme for generation and decoding of single-byte error-correcting and double-byte error-detecting codes, referred to as CA-SbEC-DbED, is presented. Extension of the scheme to locate/correct larger number of information byte errors has been also included. The encoding and decoding algorithms have been designed with the help of a linear operator that can be conveniently realized with a maximum length group CA. The regular, modular and cascadable structure of CA can be economically built with VLSI technology. Compared to the existing architecture of the Reed-Solomon decoder chip, CA-based implementation of the proposed decoding scheme provides a simple cost effective solution.>

A new scheme for designing error detecting and error correcting codes around cellular automata (CA) is reported. A simple and efficient scheme for generating SEC-DED codes is presented which can also be extended for generating codes with higher distances. A CA-based hardware scheme for very fast decoding (and correcting) of the codewords is also reported.>

This paper deals with the theory and application of Cellular Automata (CA) for a class of block ciphers and stream ciphers. Based on CA state transitions certain fundamental transformations are defined which are block ciphering functions of the proposed enciphering scheme, These fundamental transformations are found to generate the simple (alternating) group of even permutations which in turn is a subgroup of the permutation group, These functions are implemented with a class of programmable cellular automata (PCA) built around rules 51, 153, and 195. Further, high quality pseudorandom pattern generators built around rule 90 and 150 programmable cellular automata with a rule selector (i.e., combining function) has been proposed as running key generators in stream ciphers, Both the schemes provide better security against different types of attacks. With a simple, regular, modular and cascadable structure of CA, hardware implementation of such schemes idealy suit VLSI implementation.>

A novel scheme for utilizing the regular structure of three neighborhood additive cellular automata (CAs) for pseudoexhaustive test pattern generation is introduced. The vector space generated by a CA can be decomposed into several cyclic subspaces. A cycle corresponding to an m-dimensional cyclic subspace has been shown to pseudoexhaustively test an n-input circuit (n>or=m). Such a cycle is shown to supply a (m-1) bit exhaustive pattern including the all-zeros (m-1)-tuple. Schemes have been reported specifying how one or more subsets of (m-1) cell positions of an n-cell CA can be identified to generate exhaustive patterns in an m-dimensional cyclic subspace.>

The authors present a novel scheme for state assignment based on the premise that there is a strong correlation between the FSM (finite state machine) characteristics and the state assignment technique to be used. Based on the nature of the FSM, one of four state assignment schemes is selected by the system. The selection of one of these techniques is done automatically by the system. An option is provided to further optimize the generated solution using simulated annealing. Results on MCNC benchmarks indicate that the flexible methodology for state assignment leads to area and delay values that are better in most cases than those obtained by using existing state assignment schemes.>

One of the techniques used to tackle the increasing complexity of testing VLSI circuits is to incorporate built-in self-test (BIST) structures. However, incorporation of such BIST structures calls for increased area overhead due to additional logic gates and interconnections. It is very important to keep this area overhead to a minimum. The authors present a simple graph model of the area overhead minimization problem, for circuits into which BIST modifications are to be incorporated. Although the graph model does not account for a mixed type of BIST structure usage, it can be extended to include them at the cost of increased complexity.>