Aliasing estimations for cellular automata (CA) and linear feedback shift registers (LFSR) data compactors are presented. As data compaction is a heavily relied on technique for built-in self-test (BIST) the results should be of practical, as well as theoretical interest. Aliasing estimation techniques for multiple-input data compactors are considered. In particular, exact and approximate computation techniques are developed and discussed for CA and LFSR registers. Aliasing estimates for CA and LFSR structures are provided for the ISCAS-85 benchmark circuits for single stuck-at and single delay faults.>

The authors demonstrate that one-dimensional (1-D) cellular automata (CA) form the basis of efficient VLSI architectures for computations involved in the Monte Carlo simulation of the two-dimensional (2-D) Ising model. It is shown that the time-intensive task of importance sampling the Ising configurations is expedited by the inherent parallelism in this approach. The CA architecture further provides a spatially distributed set of pseudorandom numbers that are required in the local nondeterministic decisions at the various sites in the array. The novel approach taken to random-number generation can also be applied to a variety of other highly nondeterministic algorithms from many fields, such as computational geometry, pattern recognition, and artificial intelligence.>

A variation on a built-in self-test technique is presented that is based on a distributed pseudorandom number generator derived from a one-dimensional cellular automata (CA) array. The cellular automata-logic-block-observation circuits presented are expected to improve upon conventional design for testability circuitry such as built-in logic-block operation as a direct consequence of reduced cross correlation between the bit streams that are used as inputs to the logic unit under test. Certain types of circuit faults are undetectable using the correlated bit streams produced by a conventional linear-feedback-shift-register (LFSR). It is also noted that CA implementations exhibit data compression properties similar to those of the LFSR and that they display locality and topological regularity, which are important attributes for a very large-scale integration implementation. It is noted that some CAs may be able to generate weighted pseudorandom test patterns. It is also possible that some of the analysis of pseudorandom testing may be more directly applicable to CA-based pseudorandom testing than to LFSR-based schemes.>

The computational complexity measures introduced here are motivated by the trend to higher VLSI integration levels (rather than increased chip area) to accomplish solutions to larger problem instances. It seems that the increase in the computational power of VLSI circuits can be mainly attributed to the reduction in the minimum feature size rather than to an increase in the chip area. In view of this, we present a constant area perspective and consider the discrete Fourier transform and related problems in a VLSI model that has λand T as its resources. Advantages of the mesh algorithm over the shuffle-exchange algorithm in the computation time for the DFT are shown to arise from an upper bound on current density in the wires, which we suggest must be considered in any VLSI grid model.

This correspondence presents a linear systolic array for the implementation pf digital signal processing systems based upon matrix- vector multiplication algorithms where the matrix elements can be computed from their row and column indexes. Haar, Walsh, and the discrete Fourier transforms are solved using this approach. The method presented enables the n2 matrix elements to be computed in situ directly from the 2n matrix indexes. Thus, performance comparable to known systolic matrix-vector multipliers is achieved using only constant I/O bandwidth, rather than O(n) bandwidth required in the more general case. A generalized method is given for the development of recursively formed matrices and specifically the VLSI implementation of the Haar and Walsh transforms.

The study of one-dimensional cellular automata exhibiting group properties is presented. The results show that only a certain class of cellular automata rules exhibit group characteristics based on rule multiplication. However, many other of these automata reveal groups based on permutations of their global states. It is further shown how these groups may be utilized in the design of modulo arithmetic units. The communication properties of cellular automata are observed to map favorably to optimal communication graphs for VLSI layouts. They exploit the implementation medium and properly address the physical limits on computational structures. Comparisons of cellular automata-based modulo arithmetic units with other VLSI algorithms are presented using area-time complexity measures.