In this paper we present a new class of one-dimensional cellular automata which does not have the design complexity of two dimensional cellular automata but achieves higher fault coverage than the two most commonly used maximal length linear finite state machines: linear hybrid cellular automata and linear feedback shift registers. This class of cellular automata is based on a five-cell neighbourhood, giving it a much richer transition structure, but still keeping the interconnection complexity very low. A recurrence relation is given to enable the efficient calculation of the characteristic polynomial. The effectiveness of the new cellular automata is investigated by using them as generators for built-in self-test of the ISCAS 85 and ISCAS 89 benchmark circuits. While the resulting fault coverage is never worse than using the traditional linear feedback shift register as the generator, in about half of the circuits the fault coverage is significantly improved, in some cases by more than 20%.

Reversible logic computing is a rapidly developing research area. Testing such circuits is obviously an important issue. In this paper, we consider a new fault model, labeled crosspoint faults, for reversible logic circuits. A randomized Automatic Test Pattern Generation algorithm targeting this specific kind of fault is introduced and analyzed. Simulation results show that the algorithm yields very good performance. The relationship between the crosspoint faults and stuck-at faults is also investigated. We show that the crosspoint fault model is a better fault model for reversible circuits since it dominates the traditional stuck-at fault model in most instances.

Four operations on switching functions are used to define a classification technique based on the autocorrelation function. The relationship between these classes and the well-known spectral classes is investigated, and a canonical representative for each class is proposed. It is thought that these classes will be of use in logic synthesis employing decision diagram representations for intermediate steps.

Summary form only given. Presents an heuristic algorithm TOP (Three-level Optimization of PLDs), targeting a three-level logic expression of type g/sub 1/ o g/sub 2/, where g/sub 1/ and g/sub 2/ are sum-of-products and "o" is a binary operation. Such an expression can be implemented by a three-level Programmable Logic Device (PLD) consisting of PLA 1 and PLA2, implementing the first two levels of logic, and a set of two-input logic expanders, implementing the third level. Each logic expander can be programmed to realize any function of two variables. PLDs of this type seem to give a good trade-off between the speed of a flat PLA and density of a multi-level network of PLAs. TOP chooses the functionality of the logic expanders so that the area of the PLAs is minimized.

S.M. Reddy (1972) showed that the binary circuits realizing Reed-Muller canonical form are easily testable. In this paper, we extend Reddy's result to multiple-valued logic circuits, employing more than two discrete levels of signal. The electronic fabrication of such circuits became feasible due to the recent advances in integrated circuit technology. We show that, in the multiple-valued case, several new phenomena occur which allow us to asymptotically reduce the upper bound on the number of tests required for fault detection, but make the generation of tests harder.

This paper introduces a new class of two-dimensional linear cellular automata and derives a number of their properties. A recursive relation is proved which enables the characteristic polynomial to be efficiently calculated, and minimal cost, maximal length generators of this type are listed for sizes up to 500. A theoretical analysis of the two vector transition properties of the cellular automata is given and it is shown that, for testing sequential faults over a set of standard benchmarks, the two-dimensional cellular automata perform, on average, better than one-dimensional linear hybrid cellular automata, and much better than linear finite shift registers.

The paper studies theoretical aspects of one dimensional linear hybrid cellular automata over a finite (Galois) field. General results concerning the characteristic polynomials of such automata are presented. A probabilistic synthesis algorithm for determining such a linear hybrid cellular automaton with a specific characteristic polynomial is given, along with empirical results and a theoretical analysis. Cyclic boundary cellular automata are defined and related to the more common null boundary cellular automate. An explicit similarity transform between a cellular automaton and its corresponding linear feedback shift register is derived.

This paper presents a method for the synthesis of a one-dimensional linear hybrid cellular automaton (CA) from a given irreducible polynomial. A detailed description of the algorithm is given, together with an outline of the theoretical background. It is shown that two CA exist for each irreducible polynomial, solving the previously open CA existence conjecture. An in-depth example of the synthesis is presented, along with timing benchmarks and an operation count. The algorithm solves the previously open problem of synthesizing CA for all practical applications.

For the original article see IEEE Trans. Computer-Aided Design, vol. 13, no. 11, p. 1319-32 (1994). In this paper, we prove that 3-RLMP and 4-RLMP, proposed by Farrahi and Sarrafzadeh in the aforementioned paper, are NP-complete.

This paper presents a combinatorial method of evaluating the effectiveness of linear hybrid cellular automata (LHCA) and linear feedback shift registers (LFSR) as generators for stimulating faults requiring a pair of vectors. We provide a theoretical analysis and empirical comparisons to see why the LHCAs are better than the LFSRs as generators for sequential-type faults in a built-in self-test (BIST) environment. Based on the concept of a partner set, the method derives the number of distinct k-cell substate vectors which have 2/sup 2k/, 1/spl les/k/spl les/[n/2], transition capability for an n-cell LFSR and an n-cell LFSR with maximum length cycles. Simulation studies of the ISCAS85 benchmark circuits provide evidence of the effectiveness of the theoretical metric.>

Fast transforms for computing modulo-2 ring-sum canonical expansions of a Boolean function are described using Kronecker products of elementary Boolean matrices. These transforms unify and generalize existing ones in the literature. Previous algorithms which employ such transforms for finding a minimal fixed polarity expansion (FPE) are reviewed, analyzed, and extended to a minimal fixed basis expansion (FBE).>

It is shown how to construct a general linear hybrid cellular automaton (CA) such that it has a maximum length cycle, and how the aliasing properties of such automata compare with linear feedback shift registers (LFSRs) when used as signature analyzers. The construction is accomplished by formally demonstrating the isomorphism which binds this kind of CA to the LFSRs. Consequently, these CAs can be analyzed as linear machines. Linear algebraic techniques are then applied appropriately for the transformations, and a useful search algorithm is developed which, given an irreducible characteristic polynomial, finds a corresponding linear hybrid automaton. Such CAs are tabulated for all irreducible and primitive polynomials up to degree 16, plus a selection of others of higher degree. The behavior of a linear hybrid CA and that of its corresponding LFSR are similar-that is, they have the same cycle structure and only relabel the states. The aliasing properties, when they are used as signature analyzers, remain unchanged.>

A counting signature for multiple-output circuits is introduced. It implements both time compaction and space compaction, such that a single signature is derived for all outputs, using a simple scheme with suitable built-in implementation. It is shown that there exists testability criteria that show deterministically at design time, without full-fault simulation, whether a fault is testable by the signature. The computation of such criteria is straightforward, can be easily incorporated into a CAD system such that the testability results are directly available to the designer. The best current application of such a space-compacted signature is to PLAs (programmable logic arrays) and ROMs (read-only memories), where full testability of all single faults is achieved. Discussion, results, proofs, and examples are presented, including an initial comparison with multiple-input shift registers (MISRs).>

Syndrome testing is a simple and effective fault detection technique applicable to many general circuits. It is particularly useful in two-level circuits, such as programmable logic arrays (PLA's). For a multiple-output network, like PLA's, existing methods test the individual syndromes for each function, where a fault should be detectable in at least one output. This paper shows that the weighted sum of syndromes of all the outputs covers all single stuck-at-faults, bridging faults, and cross-point faults. Primary input faults are also covered except in one special case which requires some preventive design for testability. This results in the use of one test to cover all single faults.

A method is described for the derivation of fault signatures for the detection of stuck-at faults in single-output combinational networks. These signatures consist of a set of values derived from the network. Any single stuck-at fault causes at least one value to change. The fault signatures developed are a generalization of syndrome testing. The technique is developed in the Rademacher-Walsh spectral domain but is easily implemented using conters and basic gates.

A method is described for the derivation of fault signatures for certain classes or irredundant combinational networks. These signatures consist of a set of values derived from the network. Any stuck-at fault causes at least one of the values to change. The signatures provide complete fault detection for all single stuck-at faults. They are usually short and never contain more than n + 1 values for an n-input network.

A method is given for the evaluation of the Rademacher–Walsh spectra of the Boolean sum, product, and EXCLUSIVE-OR of two functions without reintroducing the Rademacher–Walsh transform. The results are derived using a general coding scheme and depend heavily upon the use of a dyadic convolution operation.

Three particular cell structures are defined for use in ternary cellular arrays. Universal arrays for both general and symmetric functions are considered and the optimum size is found. Both optimal and nonoptimal universal arrays are given for these cases as well as arrays for the sum and carry functions for a ternary full adder.