This letter presents an algorithm named SPM which generates test patterns for single stuck-at faults in synchronous sequential circuits based on a product machine traversal method. The new idea presented in this letter is partitioned image computation combined with a mixed breadth-first/depth-first search. Image computation is carried out in partitioned manner by substituting constant logical values to some input variables. This brings about significant reduction in storage requirement during image computation. A test generator based on SPM achieved 100% fault efficiency for the ISCAS'89 benchmark circuits with not more than 32 flip-flops.

In this paper we present a method to generate test sequences for stuck-at faults in sequential circuits which have distinguishing sequences. Since the circuit may have no distinguishing sequence, we use two design techniques for circuits which have distinguishing sequences. One is at state transition level and the other is at gate level. In our proposed method complete test sequence can be generated. The sequence consists of test vectors for the combinational part of the circuit, distinguishing sequences and transition sequences. The test vectors, which are generated by a combinational test generator, cause faulty staes or faulty output responses for a fault, and disinguishing sequences identify the differences between faulty states and fault free states. Transition sequences are necessary to make the state in the combinational vectors. And the distinguishing sequence and the transition sequence are used in the initializing sequence. Some techniques for shortening the test sequence is also proposed. The basic ideas of the techniques are to use a short initializing sequence and to find the order in concatenating sequences. But fault simulation is conducted so as not to miss any faults. The initializing sequence is obtained by using a distinguishing sequence. The efficiency of our method is shown in the experimental results for benchmark circuits.

Since the time required for testing logic circuits is proportional to the number of test vectors, the size of test sets as well as test generation time is one of the most important factors to be considered in test generation. The size of test sets becomes an essential issue, especially for scan designed circuits, because of the need to shift a test vector serially into the scan path. In this paper, we propose new methods of generating compact test sets to detect al the irredundant single stuck-at faults in combinational circuits. The proposed algorithms calculate a test function for each fault which corresponds to the set of all test vectors for the fault and generate a compact test set by analyzing the test functions. The analysis is based on finding a test vector which detects the largest number of remaining faults. Since our methods select a test vector among all the test vectors, represented by a test function, for a target fault, smaller test sets can be generated, in general, than that by conventional test set compaction methods. The experimental results show that the size of test sets generated by our method is about one-third as large as that without compaction.

We present algorithms for the optimization of sequential synchronous digital circuits using structural model, i.e. interconnections of combinational logic gates and synchronous registers. This approach contrasts traditional methods using state diagrams or transition tables and leveraging state minimization and encoding techniques. In particular, we model circuits by synchronous logic networks, that are weighted multigraphs representing interconnections of gates implementing scalar combinational functions. With this modeling style, area and path delays are explicit and their variation is easy to compute when circuit transformations are applied. Sequential logic optimization may target cycle-time or area minimization, possibly under area or cycle-time constraints. Optimization is performed by a sequence of transformations, directed to the desired goal. This paper describes the fundamental mechansms for transformations applicable to sequential circuits. We review first retiming and peripheral retiming techniques. The former method optimizes the position of the registers, while the latter repositions the registers to enlarge maximally the combinational region where combinational restructuring algorithms can be applied. We consider then synchronous algebraic and Boolean transformations, that blend combinational transformations with local retiming. Both classes of transformations require the representation of circuits by means of logic expressions with labeled variables, the labels representing discrete time-points. Algebraic transformations entail manipulation of time-labeled expressions with algebraic techniques. Boolean transformations exploit the properties of Boolean algebra and benefit from the knowledge of don't care conditions in the search for the best implementation of local functions. Expressing don't care conditions for sequential circuits is harder than for combinational circuits, because of the interaction of variables with different time labels. In addition, the feasibility of replacing a local function with another one may not always be verified by checking for the inclusion of the induced perturbation in local explicit don't care set. Indeed, the behavior of sequential circuits, that can be described appropriately by the relation between input and output traces, may require relational models to express don't care conditions. We describe a general formalism for sequential optimization by Boolean transformations, where the don't care conditions are expressed implicitly by synchronous recurrence equations. We present then an optimization method for this model, that can exploit degrees of freedom in optimization not possible for other methods, and hence providing solutions of possible superior quality. We conclude by summarizing the major features and limitations of optimization methods using structural models.

Acceleration techniques have been incorporated into the generalized method of characteristics (GMC) to perform transient analysis of uniform transmission lines, for the special case when the transmission lines are driven by digital signals. These techinques have been proved to improve the simulation speed to a great extent when the analysis is carried out using iterative waveform relaxation method. It has been identified that the load impedance connected to the transmission line has a bearing on the efficiency of one of these acceleration techniques. Examples of an RLCG line terminated with linear loads as well as nonlinear loads are given to illustrate the advantage of incorporating these acceleration techniques.

In this paper, a new method of synthesizing multi-level logic circuits directly from binary decision diagrams (BDDs) is proposed. In the simple multiplexer implementation, the depth of the synthesized circuit was always O (n), where n is the number of input variables. The new synthesis method attempts to reduce the depth of circuits. The depth of the synthesized circuits is O (log n log w) where w is the maximum width of given BDDs. The synthesized circuits are 2-rail-input 2-rail-output logic circuits. The circuits have good testability; it is proved that the circuits are robustly path-delay fault testable and also totally self-checking for single stuck-at faults.

The authors developed new measuring system (Holographic Pattern Measuring System [HPMS]), which is composed of both techniques of holography and graphic image processing, was used to measure the vibrations of a printed circuit board (PCB) due to operation of a mounted electromagnetic relay on it. The clear vibration patterns were obtained. By using pattern analysis processor, quantitative vibration patterns of the PCB surface were observed. Both the vibration patterns and displacements were changed by edge fixing way of the PCB.

To improve measurement accuracy and speed, a switched-capacitor capacitance measurement circuit with the vernier scale is developed. Its process consists of a coarse measurement by charge-balancing A-D conversion and a fine measurement by single-slope A-D conversion. a prototype using discrete components confirms the principles of operation.

This review presents research topics and results on digital signal processing in the last twenty years in Japan. The main parts of the review consist of design and analysis of multidimensional digital filters, multiple-valued logic circuits and number systems for signal processing, and general purpose signal processors.

To realize next-generation high performance ULSI processors, it is a very important issue to reduce the critical delay path which is determined by a cascade chain of basic gates. To design highly parallel digital operation circuits such as an adder and a multiplier, it is difficult to find the optimal code assignment in the non-linear digital system. On the other hand, the use of the linear concept in the digital system seems to be very attractive because analytical methods can be utilized. To meet the requirement, we propose a new design method of highly parallel linear digital circuits for unary operations using the concept of a cycle and a tree. In the linear digital circuit design, the analytical method can be developed using a representation matrix, so that the search procedure for optimal locally computable circuits becomes very simple. The evaluations demonstrate the usefulness of the circuit design algorithm.

The test pattern generation for sequential circuits is more difficult than that for combinational circuits due to the presence of memory elements. Therefore we proposed a method for synthesizing sequential circuits with testability in the level of state transition table. The state transition table is augmented by adding extra two inputs so that it possesses a distinguishing sequence, a synchronizing sequence, and transfer sequences of short length. In this case the checking sequence which do a complete verification of the circuit can be test pattern. The checking sequence have been impractical due to the longer checking sequence required. However, in this paper, we have discussed the condition to reduce the length of checking sequence, then by using suitable state assignment codes sequential circuits with much shorter checking sequences can be realized. A heuristic algorithm of the state assignment which reduce the length of checking sequence is proposed and the algorithm and reduced checking sequence are presented with simple example. The state assignment is very simple with the state matrix which represents the state transition. Furthermore some experimental results of automated synthesis for the MCNC Logic Synthesis Workshop finite state machine benchmark set have shown that the state assignment procedure is efficient for reducing checking sequences.

This paper surveyed the research topics and results on nonlinear circuits and systems which have been achieved in Japan or by Japanese researchers (sometimes as co-authors) during the last 20 years. The particular emphasis is placed on the analysis of nonlinear resistive circuits and periodic dynamic circuits.

We propose a method of diagnosing any logical fault in combinational circuits through a repetition of the single fault-net location procedure with the aid of probing, called SIFLAP-G. The basic idea of the method has been obtained through an observation that a single error generated on a fault-net often propagates to primary outputs under an individual test even though multiple fault-nets exist in the circuit under test. Therefore, candidates for each fault-net are first deduced by the erroneous path tracing under the single fault-net assumption and then the fault-net is found out of those candidates by probing. Probing internal nets is done only for some of the candidates, so that it is possible to greatly decrease the number of nets to be probed. Experimental results show that the number seems nearly proportional to the number of fault-nets (about 35 internal nets per fault-net), but almost independent of the type of faults and the circuit size.

This paper describes the architecture and simulated performance of a proposed Integrated Memory Array Processor (IMAP). The IMAP is an LSI which integrates a large capacity memory and a one dimensional SIMD processor array on a single chip. The IMAP holds, in its on-chip memory, data which at the same time can be processed using a one dimensional SIMD processor integrated on the same chip. All processors can access their individual parts of memory columns at the same time. Thus, it has very high processor-memory data transfer bandwidth, and has no memory access bottleneck. Data stored in the memory can be accessed from outside of the IMAP via a conventional memory interface same as a VRAM. Since the SIMD processors on the IMAP are configured in a one dimensional array, multiple IMAPs could easily be connected in series to create a larger processor and memory configuration. To estimate the performance of such an IMAP, a system architecture and instruction set were first defined, and on the basis of those two, a simulator and an assembly language were then developed. In this paper, simulation results are presented which indicate the performance of an IMAP in both image processing and artificial neural network calculations.

A strictly nonblocking 88 matrix switch was designed and fabricated using silica-based planar lightwave circuits (PLC) on a silicon substrate. The average insertion loss was 11 dB in the TE mode and 11.3 dB in the TM mode. The average switch element extinction ratio was 16.7 dB in the TE mode and 17.7 dB in the TM mode. The accumulated crosstalk was estimated to be 7.4 dB in the TE mode and 7.6 dB in the TM mode. The driving power of the phase shifter required for switching was about 0.5 W and the polarization dependence of the switching power was 4%. The switching response time was 1.3 msec. The wavelength range with a switch extinction ratio of over 15 dB was 1.31 µm30 nm.

A method to analyze two-pattern test capabilities of autonomous test pattern generator (TPG) circuits for use in built-in self-testing are described. The TPG circuits considered here include arbitrary autonomous linear sequential circuits in which outputs are directly fed out from delay elements. Based on the transition matrix of a circuit, it is shown that the number of distinct transitions in a subspace of state variables can be obtained from rank of the submatrix. The two-pattern test capabilities of LFSRs, cellular automata, and their fast parallel implementation are investigated using the transition coverage as a metric. The relationships with dual circuits and reciprocal circuits are also mentioned.

In our recent work, a forward test generation method for sequential circuits by using a single time frame was proposed. In order to improve the effectiveness of the method, we introduced an extended mode which can handle the two time frames for a hard-to-test fault and a state escaping phase which can detect a sequence of unsuitable states for test generation. The experimental results show that the improved method is effective in generating higher coverage tests with a small number of tests.

The design of complex VLSI systems relies more and more heavily on scientific computing for numerical simulation and configuration/performance optimization. Especially, computer simulation is becoming a component of VLSI design methodology, for which a variety of computation evolutions have been accomplished for the past two decades. There are many different forms of simulation which are used for verification of VLSI design at various stages of the whole design process. They may be classified into functional or behavioral simulators, register transfer level (RTL) simulators, gate-level logic, or simply logic, simulators, timing simulator, circuit simulators, device simulator, and process simulators. Among these simulation tasks, a series of logic, timing, and circuit simulation is most strongly related to the design stage which deals with logic/electric waveform performance of VLSI circuits. This article surveys the state of the art of VLSI simulation, putting stress mainly on the domain of logic, timing, and circuit simulation, since the reader of the Transactions may be interested exclusively in this field.

In this letter, a practical functional test method is proposed for production tests of microprocessor based sequence controllers. In our method, a controller under test is determined as a faulty one if the outputs defined in the process flowchart can not be provided from the circuit.

This paper reviews the historical aspect of contributions on the theory of analysis and diagnosis of linear circuits, which have been made by Japanese researchers in these twenty years. On papers of diagnosis, those related to element-value solvability (or determinability) are mainly reviewed. Some important problems are suggested.