Advances in semiconductor device manufacturing technology, which have enabled reduced feature size and higher integration, have resulted in a gap between the defect level estimated at the design stage and that reported for fabricated devices. As one possible strategy to control test quality and cost, the authors have proposed weighted fault coverage estimation. In this study, we propose layout-aware, fast and compact test pattern set generation considering both bridge and open weighted fault coverages. The proposed scheme applies two-step test pattern generation where only second pattern set is reordered with fixed size of search window, achieving O(n) computational complexity. Compared to simple greedy-based reordering, the experimental results indicate that the proposed scheme with a 10% initial target fault size and a fixed small window size achieves approximately 100 times runtime reduction with further in exchange for about 5% pattern count increment.

Advances in semiconductor device manufacturing technology, which have enabled reduced feature size and higher integration, have resulted in a gap between the defect level estimated at the design stage and that reported for fabricated devices. As one possible strategy to accurately estimate defect level, the authors have proposed weighted bridge fault coverage estimation. In this study, we establish unified weighted fault coverage, which takes both bridge and open faults into account, and we propose fast and compact test pattern set generation. The proposed scheme applies two-step test pattern generation where only second pattern set is reordered with search window for speed-up. Compared to simple greedy-based reordering, the experimental results indicate that the proposed scheme with a 10% initial target fault size and a 10% window size achieves approximately 10 times processing time reduction in exchange for a 10% pattern count increment.

We propose a new method that uses a neural network, the Growing Hierarchical Self-Organizing Map (GHSOM), to analyze the DNS query log files. Due to the structure of the DNS query frequency, infected computers are easy to detect. Our experiment shows the different DNS query structure between healthy and infected computers.

Shrinking feature size and higher integration on semiconductor device manufacturing technology bring a problem of the gap between the defect level estimated at the design stage from the reported one for fabricated devices. In this study, as one possible strategy to accurately estimate the defect level, we discuss on fault coverage estimation with more accuracy for the given test pattern set. We consider the probability that intermediate voltage caused by bridge/open defects is translated into logic values 0/1 at any of successive nodes. For each possible pair of signal lines in a given layout data, we execute critical area analysis. On the basis of critical areas obtained, we calculate weighted probabilistic bridge fault coverage, considering frequency of occurrence of each fault.

In this paper we evaluate the effectiveness of cascaded triple modular redundancy (TMR) in terms of area-per-yield and defect level by applying to every stage of a pipelined processor. Considering a cascade of nine possible TMR stage architectures, we theoretically derive the area-per-yield on the basis of the given parameters of defect density and the number of stages. Also, assuming that a production test is independently applied for each module and voter in every stage and the pass/fail of a chip is determined on the basis of the test result, we theoretically derive the defect level for the given fault coverage. Numerical examples show that the application of cascaded TMR improves the area-per-yield and the defect level when manufacturing yield is low. In addition, some cases exist in which the number of stages minimize the area-per-yield or the defect level.

Some cloud storage services have recently introduced file versioning features by which more than one version of a file can be maintained. For providing file versioning with limited storage resources, it is essential to divide the resources among versions in accordance with the varied needs of numerous users. In this paper, we focus on applications in which newer versions of a file are more likely to be requested, which may be true in the case of many subscription services. We propose a new distributed data replication protocol supporting the file versioning feature. We also construct an analytical model that can derive an optimal allocation of the resources when the total number of replica nodes in a system and the distribution of the frequency of read requests for each version are given. In addition, we present some numerical examples obtained by simulations to show the good scalability and dependability of our system by assuming some realistic parameters.

We propose the fault model considering weak resistive opens inside the gate which might cause pattern-sequence-dependent and timing-dependent malfunction of the circuit. We assume the fixed observation interval for the signal transition, and derive the minimum resistance of intra-gate resistive opens to be detected as a fault by SPICE simulation. Based on the simulation results, we establish three fault models, that is, the one considering the location of the resistance, the one considering both the location and the resistance distribution, and the simplified one where str and stf faults considering the signal transition of the input ports are assumed. The coverage calculation for the primitive gates and small benchmark circuit reveals that the proposed models have more accuracy on the detection of weak open defects.

We propose encoder-based comparator architecture to reduce hardware overhead of MBIST. Experimental results show the proposed architecture drastically reduce hardware overhead while maintaining the adaptability to the repair analysis.

Convolutional compactors offer a promising technique of compacting test responses. In this study the authors 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. The authors show the arrangement of the proposed compactors and the equivalent expression over GF (2). The authors 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, the authors evaluate a multi-weight arrangement of the proposed compactors for non-uniform X distributions

The authors have developed a scheme for scan-based BIST that can compress test stimuli and responses by more than 100 times. The scheme is based on a scan-BIST architecture, and combines four techniques: the invert-and-shift operation, run-length compression, scan address partitioning, and LFSR pre-shifting. The scheme achieved a 100times compression rate in environments where Xs do not occur without reducing the fault coverage of the original ATPG vectors. Furthermore, the masking logic was enhanced to reduce data for X-masking so that test data is still compressed to 1/100 in a practical environment where Xs occur. The scheme was applied to five real VLSI chips, and the technique compressed the test data by 100times for scan-based BIST

Maintaining the replicated data between nodes can improve the dependability of data. We propose a probabilistic trapezoid protocol for replicated data that combines this protocol with the concept of a probabilistic quorum system. We analyzed read availability, the latest version read availability and the average number of nodes accessed for the protocol. Our numerical evaluations demonstrated that it improves not only read availability but also latest version read availability. Furthermore, when the number of nodes is greater than 100, it could effectively reduce system load. We designed and implemented a file transfer protocol to replicate data. Experimental results proved that the trapezoid protocol could achieve better throughput than quorum system or grid protocol. Despite node failure, the probabilistic trapezoid protocol also achieved relatively better throughput.

Convolutional compactors offer a promising technique of compacting test responses that include unknown values. One drawback of this compaction technique is error masking, i.e., some errors appearing in the test responses cannot be detected due to mutual cancellation. In this work, we theoretically analyze error-masking probability. First, we apply weight distributions of binary linear error-correcting codes to derive the error-masking probability. We then present a fast calculation scheme for 4- and 6-error-masking probabilities. Numerical examples reveal that they are about the same as those obtained by Monte-Carlo simulations. We also analyze X-masking probability, that is, the probability that an error is masked by unknown values. We present tree-search-based calculation, as well as approximated value

In this paper, we discuss the application of a seed-selection procedure for LFSR-based BIST to multiple scan chains, combined with a phase shifter. We introduced the procedures for selecting seeds and arrangement of phase shifters under the restriction of limiting additional hardware overheads, and evaluated them in respect to the number of test patterns required to achieve 100% fault coverage. Experimental results shows that that the test length was reduced in comparison with cases in which phase shifters or seed-selection procedures were not applied, under condition where the number of EOR gates in the phase shifter were restricted.

Replicating data is a promising way of improving the dependability of large distributed systems. The hybrid data replication protocol combines concepts of the tree quorum protocol and grid protocol. We present an analytical evaluation of read/write availability for the generalized hybrid data replication protocol, which extends the arrangement of nodes into a more general form to improve write availability. The average number of nodes accessed for read/write operations is also analyzed under the assumption that nodes might fail. Equations are derived based on node availability p, and numerical examples are shown. We use computer simulations to estimate the throughput for read/write operations.

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 conventionally selected seeds 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.

A scheme for testing SRAMs is proposed with a tester circuit consisting of SRAM-based reconfigurable cells. We first show an approach to reduce the number of reconfigurable cells required for the tester circuit. We then propose a tester for a 4 Mbit SRAM with reconfigurable cells of 16 bit data SRAMs. We also report the implementation of the proposed circuit. Four 16 bit reconfigurable cells, each of which consists of an SRAM and two CPLDs, were implemented, and mounted on a board. We confirmed that the tester functions correctly by performing a marching test.

In this paper we evaluate the effectiveness of using convolutional codes under a time limit for recovery as a method for packet loss recovery. We analyze the method's operation when a limitation on the number of received packets is substituted for the time limitation, and derive the probability for a lost packet being recovered before the arrival of the limiting number of succeeding packets. We also evaluate this probability in the results of simulation and estimate the buffer size required for a decoder. Moreover we apply this method in constructing a dependable videoconference system and observe the resulting improvement in QoS.

Developed a partially rotational scan (PRS) register used for the n-detection BIST (built-in self-test) that can detect not only delay faults but also unmodeled faults. The developed circuit consists of a shift register with partial rotation. Also presents a procedure for selecting test vectors from ATPG (automatic test pattern generation) ones. This testing method enables at-speed testing and the stuck-at fault coverage of n/spl times/100% by using subset of the ATPG vectors. And it drastically reduces the number of vectors input from an external low-speed tester. Computer simulations of stuck-at fault coverage are conducted on ISCAS'85, ISCAS'89, and ITC'99 circuits for detection times n of 1, 2, 3, 5, 10, and 15. They show that the compaction rates of the ATPG test vectors range from 52.4% (s713) to 0.9% (c499) of origin. This result demonstrates that the PRS register can accomplish low-cost, at-speed testing.

The ability of convolutional-code-based FEC to recover from packet losses over a channel subjected to burst erasure is evaluated. We analyze the maximum lengths of a burst packet loss that can be recovered. We assume that only one burst packet loss has occurred, and consider the recovery conditions for given lengths, that is, numbers of lost packets. We also present conditions for the generator matrices, which are used to encode and decode convolutional-code-based redundant packets. We then apply a packet loss model based on a two-state Markov chain and use computer simulation to examine the ability of our approach to recover packets lost in transmission over bursty erasure channels. We show that this ability changes with the constraint length of the applied code and with the generator matrix, and find conditions for a matrix to have high levels of ability. Finally, we apply our method to the transfer of graphic data over the Internet, and use convolutional codes in the recovery process.

A new method to recover packet losses (n, n-1, m) convolutional codes is proposed. The method is used to encode and decode packets transmitted over the Internet. An independent erasure channel is assumed for packets transmission. We then theoretically analyze the method ability to recover packet losses. The sufficient conditions are derived for packet losses that can be recovered. We evaluate the method using computer simulations, supplemented by comparisons with a simple parity method, which has the same redundancy. The results show that the proposed method has a superior performance.

Packet losses due to congested traffic conditions in the Internet leads to the investigation of the reliable delivery of data to multicast receivers. In this paper, we examine the technique based on FEC, using (n, k, m) convolutional codes to recover lost packets. We show that when the redundant packets are generated by convolutional codes, a receiver can tolerate a certain amount of packet loss and still be able to obtain all data without requiring retransmission. We evaluate the effectiveness of the proposed approach to perform the recovery of lost packets for multicast transmission taking into account two different parameters: the number of packets needed to be sent to guarantee the reception of data, and the number of transmissions. Finally, we compare the proposed approach with the scheme when parity packets are based on Reed-Solomon codes. We demonstrate that the use of parity generated by convolutional coding is more efficient at reducing bandwidth requirements and the number of transmissions from the source.

We have measured the packet loss ratio, its time dependency, and the frequency of burst packet losses in Internet end-to-end communications. To do this, we developed a tool that sends and receives UDP (User Datagram Protocol) packets. Our measurements showed that long burst losses are more likely when the packet loss ratio is high. We then examined two models for calculating the burst packet loss, an independent loss model and a Markov-chain model, to see whether they explain the packet loss characteristics we measured. They did not, so we developed a sine model, in which the packet loss probability depends on the time of day. Theoretical analysis and simulations showed that this model explains the characteristics of the burst packet losses that we measured.

Analyzing 1,000 faulty 1 Mb SRAM chips that were randomly selected from a single manufacture, we found 251 stuck-at cell faults, 5 stuck-at bit-line faults, 1 stuck-at word-line fault, 46 neighborhood-pattern-sensitive faults, and other kinds of faults. Under the condition that I/sub dd/=4.5 I; temperature=70/spl deg/C, and load capacity C/sub L/=30 pF, we detected margin faults in 460 chips. Because the actual fault data for SRAM chips is rarely reported, the data in this manuscript are very useful and should be of practical importance.

To develop better ROM BIST techniques we first experimentally surveyed cell faults, word-line faults, bit-line faults, delay faults and other types of faults occurring in 1,000 faulty mask ROM chips. We found that most of the stuck-at faults were within a single mat. We then theoretically analyzed the aliasing probability for a mask ROM containing a fault or faults within a single mat. To experimentally evaluate BIST aliasing errors we implemented six MISRs on a custom board and observed actual aliasing errors. The experimentally measured aliasing probabilities agreed with the probabilities derived theoretically. No aliasing error occurred for the 16-stage, 8-input MISR.

The aliasing error performance of a signature register is measured by the maximum values of the aliasing error probabilities for certain ranges of the bit-error rate (and those of the test length). Based on these measures, we evaluate the performances of all the single input signature registers whose feedback polynomials are primitive polynomials of degree 16 and generator polynomials of the double-error-correcting BCH codes of the same degree. When the degree of the feedback polynomial is large, say 32, it is computationally hard to obtain the exact aliasing probability. But we observe that the numbers of codewords with large weights in the corresponding code dominate the maximum value of the aliasing probabilities. By computing the numbers of codewords of large weights, we find primitive polynomials of degree 32 whose maximum value of the aliasing probabilities is very large for some test lengths. The error performance of an LFSR with any BCH polynomial of degree m for the test length 2/sup m/2/-2 is shown to be very good by deriving the formula for the weight distribution of the corresponding code.>

The aliasing probability is theoretically analyzed for a mask ROM containing a word/bit-line fault or faults within a mat. Analysis of 1000 faulty mask ROM chips revealed cell faults, word-line faults, bit-line faults, delay faults and other types. For these chips, the BIST aliasing errors were experimentally examined. Six MISRs were implemented on a custom board, and aliasing errors were actually observed. The best of the six is shown to be the 16-stage, 8-input MISR with no aliasing error.>

Presents new principles for online monitoring in the context of multiprocessors (especially massively parallel processors) and then focuses on the effect of the aliasing probability on the error detection process. In the proposed test architecture, concurrent testing (or online monitoring) at the system level is accomplished by enforcing the run-time testing of the data and control dependences of the algorithm currently being executed on the parallel computer. In order to help in this process, each message contains both source and destination addresses. At each message source, the sequence of destination addresses of the outgoing messages is compressed on a block basis. At the same time, at each destination, the sequence of source addresses of all incoming messages is compressed, also on a block basis. Concurrent compression of the instructions executed by the PEs is also possible. As a result of this procedure, an image of the data dependences and of the control flow of the currently running algorithm is created. This image is compared, at the end of each computational block, with a reference image created at compilation time. The main results of this work are in proposing new principles for the online system-level testing of multiprocessor systems, based on signaturing and monitoring the data dependences together with the control dependences, and in providing an analytical model and analysis for the address compression process used for monitoring the data routing process.>

The aliasing error performance of signature registers is measured by the maximum values of the aliasing error probabilities for certain ranges of the bit-error rate (and those of the test length). Based on these measurements, the authors evaluate the performances of all the single input signature registers whose feedback polynomials are primitive polynomials of degree 16 and generator polynomials of the double-error-correcting BCH codes of the same degree. When the degree of the feedback polynomial is large (e.g. 32), it is computationally hard to obtain the exact value of the aliasing probability. But the authors observe that the numbers of codewords with large weights in the corresponding code determine the maximum value of the aliasing probabilities in the range 0>

Recently D.K. Pradhan, S.K. Gupta and M.G. Karpovsky (1990) affirmed that the codes generated by (x- alpha )(x- beta ) were not Reed-Solomon, where alpha and beta were roots of the distinct primitive polynomials of degree m. It was assumed that beta = alpha /sup 8/, where s-1 and 2/sup m/-1 were mutually prime. The authors show that under the above assumption the respective codes are Reed-Solomon codes.>

A new defect-tolerant design technique for mask ROMs is proposed. In the proposed technique a Reed-Solomon code with distance three is utilized. A built-in circuit can repair a defect or defects within a word. The overhead area of the defect-tolerant circuits is estimated to be about 1% for a 4 M-bit mask ROM with eight outputs.>

Presents new principles for online monitoring in the context of multiprocessors (especially massively parallel processors) and then focuses on the effect of the aliasing probability on the error detection process. In the proposed test architecture, concurrent testing (or online monitoring) at the system level is accomplished by enforcing the run-time testing of the data and control dependences of the algorithm currently being executed on the parallel computer. In order to help in this process, each message contains both source and destination addresses. At each message source, the sequence of destination addresses of the outgoing messages is compressed on a block basis. At the same time, at each destination, the sequence of source addresses of all incoming messages is compressed, also on a block basis. Concurrent compression of the instructions executed by the PEs is also possible. As a result of this procedure, an image of the data dependences and of the control flow of the currently running algorithm is created. This image is compared, at the end of each computational block, with a reference image created at compilation time. The main results of this work are in proposing new principles for the online system-level testing of multiprocessor systems, based on signaturing and monitoring the data dependences together with the control dependences, and in providing an analytical model and analysis for the address compression process used for monitoring the data routing process. >

Design techniques that can improve the aliasing probabilities of signature circuits for VLSI BIST (built-in self-test) are presented. The proposed techniques are based on the binary weight distributions of error-correcting codes over GF(2) and GF(2/sup m/). The technique considered for calculating the aliasing probability of signature circuits is appropriate for a vector supercomputer. Some of the calculations were done using the S810 supercomputer. The vectorization ratio of the program was 99.885% for an MISR (multiple-input signature register) with 16 inputs and for test length n=100-105. >

The aliasing probabilities of multiple-input signature registers (MISR) with m inputs for a 2/sup m/-ary symmetric channel, where each of the (2/sup m/-1) possible errors is equally likely, are analyzed. For this error model, the aliasing probabilities of MISRs are analyzed using the weight distributions of maximum-distance-separable (MDS) codes. The results show that the aliasing probabilities over the 2/sup m/-ary symmetric channel do not depend on the polynomials that characterize the MISRs. That is, for the 2/sup m/-ary symmetric channel, the aliasing probability of an MISR based on a primitive polynomial is exactly the same as one based on a nonprimitive one. In addition, it is observed that the aliasing probabilities, P/sub al/ (n), as a function of test length n, are monotonous for error probabilities p=0.2, 0.4, and 0.8. The aliasing probabilities of multiple MISRs based on Reed-Solomon codes are analyzed again for the 2/sup m/-ary symmetric channel, using the weight distributions of Reed-Solomon codes, which are MDS codes.>

A stack cache scheme in combination with a general register set is presented as an alternative to the register file. Two cache memories, a 1-K byte code cash and a four-entry cache for branch instructions, are also embedded to accelerate the pipeline stream. This scheme has been implemented and evaluated on a 32-bit microprocessor, the Hitachi H32/200, based on TRON (The Real-time Operating system Nucleus) specifications. This processor contains 730 K transistors in 1.0- mu m CMOS. It performs 6 to 7 MIPS (million instruction per second) at a 20-MHz clock rate.>

A novel signature analysis method for LSI testing using multiple-input signature registers (MISRs) is presented. First, the double-bit and triple-bit error-detecting probabilities are analyzed theoretically in the case in which a single MISR defined by a primitive polynomial is used for a signature circuit. Second, to enhance the capability of detecting multiple errors contained in testing patterns, signature circuits are proposed that use multiplexed MISRs based on Reed-Solomon codes. It is proved that d-times multiplexed MISR can detect up to d symbol errors. Third, to reduce the amount of testing time, other signature circuits are proposed that use bit-width compression based on random error-detecting codes and multiplexed MISRs.>