We developed test data compression scheme for scan-based BIST, aiming to compress test stimuli and responses by more than 100 times. As scan-BIST architecture, we adopt BIST-Aided Scan Test (BAST), and combines four techniques: the invert-and-shift operation, run-length compression, scan address partitioning, and LFSR pre-shifting. Our scheme achieved a 100x compression rate in environments where Xs do not occur without reducing the fault coverage of the original ATPG vectors. Furthermore, we enhanced the masking logic to reduce data for X-masking so that test data is still compressed to 1/100 in a practical environment where Xs occur. We applied our scheme to five real VLSI chips, and the technique compressed the test data by 100x for scan-based BIST.

In this paper, we propose and analytically evaluate the use of punctured convolutional codes for recovering packets lost in multicast transmission. An independent erasure channel is assumed for packets transmission over a star topology. The analysis provides a method for determining the recoverability and the post-reconstruction receiving rate for a given convolutional code. We theoretically evaluate the effectiveness of the proposed approach taking into account two different parameters: the number of transmissions per packet and the number of packets needed to be sent to guarantee the reception of data. Finally, we compare the proposed approach with the scheme when parity packets are generated based on Reed-Solomon codes.

In this paper, we present a model for evaluating the effectiveness of (2, 1, m) convolutional-code-based packet-level FEC, under the condition of a limited buffer size in which the number of available packets is restricted for recovery. We analytically derive the post-reconstruction receiving rate, i.e., the probability that a lost packet is received or recovered before the buffer limit is reached. We show numerical examples of the analytical results and demonstrate that the buffer size at the same level as m gives sufficient recovery performance.

It is of great importane to make a recovery action to reconstruct the logical consistency of the databese on the occasion of a system failure. Such a recovery action consists of two operations. One is UNDO operation, which rolls back the effects of all incomplete transactions from the database, and the other is REDO operation, which reflects the results of all complete transactions in the databese. In general, we limit the amount of REDO operation by generating checkpoints, in which the results of a complete transactions(s) are collected in a safe place. In this paper, we discuss evaluation for a database recovery action with periodical checkpoint generations. A new model is proposed to evaluate the recovery action in a case where a failure rate of the system changes with time. The expected recovery time and the availability for one cycle are derived under the assumption of an arbitrary failure-time distribution. In particular, we obtain analytically the optimum checkpoint interval with the maximum availability in the case of an exponential distribution. We numerically calculate the above results by assuming Weibull distributions. We further discuss the numerical results in varying the parameters that we define in our model, and show the impact of these parameters on the recovery action.

We propose a technique of selecting seeds for the LFSR-based test pattern generators that are used in VLSI BISTs. By setting the computed seed as an initial value, target fault coverage, for example 100%, can be accomplished with minimum test length. We can also maximize fault coverage for a given test length. Our method can be used for both test-per-clock and test-per-scan BISTs. The procedure is based on vector representations over GF(2m), where m is the number of LFSR stages. The results indicate that test lengths derived through selected seeds are about sixty percent shorter than those derived by simple seeds, i.e. 0001, for a given fault coverage. We also show that seeds obtained through this technique accomplish higher fault coverage than the conventional selection procedure. In terms of the c7552 benchmark, taking a test-per-scan architecture with a 20-bit LFSR as an example, the number of undetected faults can be decreased from 304 to 227 for 10,000 LFSR patterns using our proposed technique.

In video conference systems over the Internet, audio and video data are often lost due to UDP packet losses, resulting in degradation of assurance. In this paper we describe a high-assurance video conference system applying the following two techniques: (1) packet loss recovery using convolutional codes, which improves the assurance of communication; and (2) Xcast, a multicast scheme that is designed for relatively small groups, reducing the bandwidth required for a multi-point conference. We added these functions to a GateKeeper (GK), a device used in conventional conference systems. Encoding/decoding and Xcast routing were then implemented as the upper layer for the UDP. We examined the functions of the system over the Internet in a multi-point conference between three sites around Tokyo, as well as a conference between Tokyo and Korea. We also investigated the effectiveness of the proposed system in experiments using an Internet simulator. Experimental results showed that the quality of received picture was improved in comparison with the case where no encoding schemes were applied.

An n-detection testing for stuck-at faults can be used not only for delay fault testing but also for detection of unmodeled faults. We have developed a hybrid BIST circuit; that is, a method consisting of a shift register with partial rotation and a procedure that selects test vectors from ATPG ones. This testing method can perform at-speed testing with high stuck-at fault coverage. During the at-speed testing, a subset of the ATPG vectors is input by using a low-speed tester. Computer simulations on ISCAS'85, ISCAS'89, and ITC'99 circuits are conducted for n = 1, 2, 3, 5, 10, and 15. The simulation results show that the amount of test vectors can be reduced to ranging from 52.3% to 0.9% in comparison with that of the ATPG vectors. As a result, the proposed method can reduce the cost of at-speed testing.

In this research, we investigated the reliability of a 1-out-of-2 system with two-stage repair comprising hardware restoration and data reconstruction modes. Hardware restoration is normally independently executed by two modules. In contrast, we assumed that one of the modules could omit data reconstruction by replicating the data from the module during normal operation. In this 1-out-of-2 system, the two modules mutually cooperated in the recovery mode. As a first step, an evaluation model using Markov chains was constructed to derive a reliability measure: “unavailability in steady state.” Numerical examples confirmed that the reliability of the system was improved by the use of two cooperating modules. As the data reconstruction time increased, the gains in terms of system reliability also increased.

With increasing Internet traffic congestion, the provision of reliable transmission and packet loss recovery continues to be of substantial importance. In this paper, we analyze a new recovery method using punctured convolutional codes, demonstrating the simplicity and efficiency of the proposed method for the recovery of lost packets. The analysis provides a method for determining the recoverability and the post-reconstruction receiving rate for a given convolutional code. The exact expressions for calculating the recovery rate are derived for a number of convolutional codes and the (2, 1, m) punctured convolutional code. Where packet loss probabilities are in the range typically found in Internet transmissions, the convolutional code-based method delivers superior performance over the traditional parity method with the same redundancy.

This paper discusses distributed checkpointing with logging for practical applications running with limited resources. We present a discrete time model evaluating the total expected overhead per event where the number of available checkpoints that each process can hold is finite. The rollback distance is also bound to some finite interval in many actual applications. Therefore, the recovery overhead for the checkpointing scheme is described by using a truncated geometric distribution as the rollback distance distribution. Although it is difficult to analytically derive the optimal checkpoint interval, which minimizes the total expected overhead, substituting other simple probabilistic distributions instead of the truncated geometric distribution enables us to do this explicitly. Numerical examples obtained through simulations are presented to show that we can achieve almost minimized total overhead by using the new models and analyses.

An approach is proposed for constructing a dependable server cluster composed only of server nodes with all nodes running the same algorithm. The cluster propagates an IP multicast address as the server address, and clients multicast requests to the cluster. A local proxy running on each client machine enables conventional client software designed for unicasting to communicate with the cluster without having to be modified. Evaluation of a prototype system providing domain name service showed that a cluster using this technique has high dependability with acceptable performance degradation.

This paper discusses hybrid state saving for applications in which processes should create checkpoints at constant intervals and can hold a finite number of checkpoints. We propose a reclamation technique for checkpoint space, that provides effective checkpoint time arrangements for a rollback distance distribution. Numerical examples show that when we cannot use the optimal checkpoint interval due to the system requirements, the proposed technique can achieve lower expected overhead compared to the conventional technique without considering the form of the rollback distance distribution.

A computing system, which plays an important role in our society, should be operated with high reliability and performance. A multisystem is one of the typical fault-tolerant computing systems, and is widely used in our society because of its high reliability and performance. In this paper we discuss a multisystem composed of two processors and buffer(s), and evaluate the system taking account of the reliability, performance and computational demands simultaneously. We propose two models for the system from the viewpoint of job assignment. Applying Markov renewal and queuing theories, we obtain the reliability/performance measures for each model. Using the numerical results of our models, we compare two models and show the impact of job assignment on the evaluation measures based on our numerical examples.

The partially rotational scan (PRS) technique greatly reduces the amount of data needed for n-detection testing. It also enables at-speed testing using low-speed testers. We designed tester intellectual properties (tester IP) with PRS for Viper and COMET II processors. When PRS was applied to a Viper processor, we obtained test data that provided the same fault coverage as with a set of automatic test pattern generation (ATPG) test vectors, although the amount of test data was 16% that of the ATPG. When the PRS technique was applied to a COMET II processor with full-scan design, we obtained test data that provided the same fault coverage as with a set of ATPG test vectors, although the amount of test data was 10% that of the ATPG. We also estimated hardware overhead and test time.

This paper presents a practical fault model for delay testing, called a multiple-threshold gate-delay fault model, to obtain high quality tests that guarantee the detection of delay faults for various extra-delays. Fault efficiencies for multiple thresholds of the extra-delay are introduced as a coverage metric that describes the quality of tests. Our approach guarantees that each gate-delay fault is tested on the path that is almost the longest one passing through the faulty line by using two-pattern tests with pattern-independent timing. We present the procedures of the path selection, fault simulation, and the test generation, where the path-status graph technique is used as not to rely on the enumeration of paths. Experimental results for benchmark circuits demonstrate that the proposed metric gives useful information that transition fault efficiency cannot, and that the proposed test generation can achieve high fault efficiencies for multiple-threshold gate-delay faults.

Convolutional compactors offer a promising technique of compacting test responses. In this study we expand the architecture of convolutional compactor onto a Galois field in order to improve compaction ratio as well as reduce X-masking probability, namely, the probability that an error is masked by unknown values. While each scan chain is independently connected by EOR gates in the conventional arrangement, the proposed scheme treats q signals as an element over GF(2q), and the connections are configured on the same field. We show the arrangement of the proposed compactors and the equivalent expression over GF(2). We then evaluate the effectiveness of the proposed expansion in terms of X-masking probability by simulations with uniform distribution of X-values, as well as reduction of hardware overheads. Furthermore, we evaluate a multi-weight arrangement of the proposed compactors for non-uniform X distributions.

In this paper, we propose a scheme for test data reduction which uses broadcaster along with bit-flipping circuit. The proposed scheme can reduce test data without degrading the fault coverage of ATPG, and without requiring or modifying the arrangement of CUT. We theoretically analyze the test data size by the proposed scheme. The numerical examples obtained by the analysis and experimental results show that our scheme can effectively reduce test data if the care-bit rate is not so much low according to the number of scan chains. We also discuss the hybrid scheme of random-pattern-based flipping and single-input-based flipping.

This paper presents a new deterministic built-in test scheme using a neighborhood pattern generator (NPG) to guarantee complete fault efficiency with small test-data storage. The NPG as a decoding logic generates both a parent pattern and deterministic child patterns within a small Hamming distance from the parent pattern. A set of test cubes is encoded as a set of seeds for the NPG. The proposed method is practically acceptable because no impact on a circuit under test is required and the design of the NPG does not require the results of test generation. We also describe an efficient seed generation method for the NPG. Experimental results for benchmark circuits demonstrate that the proposed method can significantly reduce the storage requirements when compared with other deterministic built-in test methods.