As the technology continuous to shrink, power consumption appears to be the main design parameter. Operation on low voltage negatively affects mainly the operation of on-chip memories, resulting in multiple malfunctioning memory cells. As a reaction many cache fault tolerance (CFT) mechanisms have been proposed targeting the mitigation of performance degradation. The challenge is to devise mechanisms that are tailored to the memory access patterns of the executing applications. In this work we initially investigate the impact of the granularity of cache line disabling scheme in the first level data caches. Based on our analysis, we propose a run time adaptive mechanism that is able to opt the cache (sub-)block taking into account the diverse memory characteristics of the application. The proposed mechanism is based on the widely used block (sub-block) disabling scheme, and dynamically selects the appropriate sub-block granularity during the execution of the applications. Our evaluation results reveal that the proposed dynamic approach is able to offer significant benefits over a faulty cache design with a monolithic (sub-)block granularity.

Aggressive dynamic voltage and frequency scaling is widely used to reduce the power consumption of microprocessors. Unfortunately, voltage scaling increases the impact of process variations on memory cells resulting in an exponential increase in the number of malfunctioning memory cells. As a result, various cache fault-tolerant (CFT) techniques have been proposed. In this work, we propose a new CFT technique which applies a systematic redistribution (permutation) of the cache blocks (assuming various block granularity levels) within the cache structure using the orthogonal Latin Square concept and taking as input the location of the malfunctioning cells in the cache array. The aim of the redistribution is twofold. First, to uniformly distribute the faulty blocks to sets and second, to gather the faulty subblocks to a minimum number of blocks, so as the fault free blocks are maximized. Our evaluation results using the benchmarks of SPEC2006 suite, 100 memory fault maps, and four percentages of malfunctioning cells show that our proposal exhibits strong capability to reduce cache performance degradation especially in situations with high percentages of faulty cells and compares favorably to already known techniques.

Dynamic voltage and frequency scaling (DVFS) is a commonly-used power-management technique. Unfortunately, voltage scaling increases the impact of process variations on memory cells reliability resulting in an exponential increase in the number of malfunctioning memory cells. In this work, we systematically investigate the behavior of branch target buffers (BTB) with faulty memory cells. Although being an intrinsically fault-tolerant unit (i.e., it does not affect correctness of the system), as we show in this work for several fault probabilities and core configurations, disabling the faulty parts of BTBs can damage the performance of the executing applications. To remedy the negative impact of malfunctioning BTB memory cells in contemporary BTB organizations, we present an ultra lightweight performance recovery mechanism. The proposed mechanism introduces minimal hardware overheads and practically-zero delays. Using cycle-accurate simulations, the benchmarks of SPEC2006 suite, a plethora of memory fault maps, and two fault probabilities corresponding to low supply voltages, we show the effectiveness of the proposed recovery mechanism.

Single event transient (SET) pulses are a significant cause of soft errors in a circuit. To cope with SET pulses, we propose a new storage cell that is able to operate either as a hard-edge or soft-edge flip-flop depending on the appearance or not of a transition in a time window. The efficiency of the proposed design with respect to the reduction of soft-errors coming from SET pulses was shown with extensive simulations.

Processor caches play a critical role in the performance of today"s computer systems. As technology scales, due to manufacturing defects and process variations a large number of cells in a cache is expected to be faulty. The number of faulty cells varies from die to die and in the field of the application depends on the operating conditions (e.g., supply voltage, frequency). Several techniques have been proposed to tolerate faults in caches. A drawback of the redundancy based techniques is that the amount of redundancy is decided at the design time targeting a maximum number of faults, so in cases of a small number of faults (e.g., in the nominal supply voltage in a system with DVS) only a part of the redundant resources is used. In this paper we propose a new reconfigurable-self adaptive fault tolerant cache scheme. The unique characteristic of our scheme is that it uses its resources for both the reduction of the misses caused by the faulty blocks as well as for the reduction of conflict misses, depending on the number of faults, their distribution in the cache, and the running application. Our experimental results for a wide range of scientific applications and a plethora of fault maps with different SRAM failure probabilities reveal that our proposal can achieve significant benefits.

Technology scaling leads to significant faulty bit rates in on-chip caches. In this work, we propose a methodology to mitigate the impact of defective bits (due to permanent faults) in first-level set-associative data caches. Our technique assumes that faulty caches are enhanced with the ability of disabling their defective parts at cache subblock granularity. Our experimental findings reveal that while the occurrence of hard-errors in faulty caches may have a significant impact in performance, a lot of room for improvement exists, if someone is able to take into account the spatial reuse patterns of the to-be-referenced blocks (not all the data fetched into the cache is accessed). To this end, we propose frugal PC-indexed spatial predictors (with very small storage requirements) to orchestrate the (re)placement decisions among the fully and partially unusable faulty blocks. Using cycle-accurate simulations, a wide range of scientific applications, and a plethora of cache fault maps, we showcase that our approach is able to offer significant benefits in cache performance.

Several dictionary-based input test data compression methods have been proposed for intellectual property (IP) cores testing. To increase the utilization of the dictionary entries some methods are based on the correction of some bits before the loading of the entries into the scan chains. The coordinates of the bits that should be corrected are sent by the automatic test equipment (ATE), hence, the number of corrections should be relatively small. In this paper we propose a new method which is based on the use of an auxiliary dictionary of minor size for storing masks. To this end, we give an algorithm for the suitable selection of the masks so that any one of them is used for on the fly bit-flipping of parts of many dictionary entries, before they are loaded into the scan chains. The efficiency of the proposed method is supported with extensive experimental results.

In this paper, we present a new test data compression method for intellectual property (IP) cores testing, based on the reuse of parts of dictionary entries. Two approaches are investigated: the static and the dynamic. In the static approach, the content of the dictionary is constant during the testing of a core, while in the dynamic approach the testing of a core consists of several test sessions and the content of the dictionary is different during each test session. The efficiency of the proposed method is supported with extensive simulation results and comparisons to already known test data compression methods suitable for IP cores testing.

The main disadvantage of LFSR-based compression is that it should be usually combined with a constrained ATPG process, and, as a result, it cannot be effectively applied to IP cores of unknown structure. In this paper, a new LFSR-based compression approach that overcomes this problem is proposed. The proposed method allows each LFSR seed to encode as many slices as possible. For achieving this, a special purpose slice, called stop-slice, that indicates the end of a seed's usage is encoded as the last slice of each seed. Thus, the seeds include by construction the information of where they should stop and, for that reason, we call them self-stoppable. A stop-slice generation procedure is proposed that exploits the inherent test set characteristics and generates stop slices which impose minimum compression overhead. Moreover, the architecture for implementing the proposed technique requires negligible additional hardware overhead compared to the standard LFSR-based architecture. The proposed technique is also accompanied by a seed calculation algorithm that tries to minimize the number of calculated seeds.

In this paper we present a new search method for test set embedding using an accumulator driven with an additive constant C. We formulate the problem of finding the location of a test pattern in the generated sequence in terms of a linear Diophantine equation with two variables, which is known to be solved quickly in linear time. We show that only one Diophantine equation needs to be solved per test set irrespective of its size. Next we show how to find the starting state, for a given constant C and test set T, such that the generated sequence can reproduce T with minimum length. Finally, we show that the best constant Copt(in terms of shortest test length) for the embedding of T using an accumulator of size n can be found in O(2ldrn+Fldr|T|) steps, instead of O(nldr2nldr|T|) steps of a previous approach, where F depends on the particular test set and can be significantly smaller than its worst case value of 2n-2. The value of F can also be further reduced while providing a guaranteed approximation bound of the shortest test length. Experimental results show the computational improvements.

Gating of the outputs of a portion of the scan cells (partial gating) has been recently proposed as a method for reducing the dynamic power dissipation during scan-based testing. We present a new systematic method for selecting, under area and performance design constraints, the most suitable for gating subset of scan cells as well as the proper gating value for each one of them, aiming at the reduction of the average switching activity during testing. We show that the proposed method outperforms the corresponding already known methods, with respect to average dynamic power dissipation reduction.

A new statistical test data compression method that is suitable for IP cores of an unknown structure with multiple scan chains is proposed in this paper. Huffman, which is a well-known fixed-to-variable code, is used in this paper as a variable-to-variable code. The precomputed test set of a core is partitioned into variable-length blocks, which are, then, compressed by an efficient Huffman-based encoding procedure with a limited number of codewords. To increase the compression ratio, the same codeword can be reused for encoding compatible blocks of different sizes. Further compression improvements can be achieved by using two very simple test set transformations. A simple and low-overhead decompression architecture is also proposed.

In this paper, a new leading-zero counter (or detector) is presented. New boolean relations for the bits of the leading-zero count are derived that allow their computation to be performed using standard carry-lookahead techniques. Using the proposed approach various design choices can be explored and different circuit topologies can be derived for the design of the leading-zero counting unit. The new circuits can be efficiently implemented either in static or in dynamic logic and require significantly less energy per operation compared to the already known architectures. The integration of the proposed leading-zero counter with the leading-zero anticipation logic is analyzed and the most efficient combination is identified. Finally, a simple yet efficient technique for handling the error of the leading-zero anticipation logic is also presented. The energy-delay behavior of the proposed circuits has been investigated using static and dynamic CMOS implementations in a 130-nm CMOS technology.

Various compression methods have been proposed for tackling the problem of increasing test-data volume of contemporary, core-based systems. Despite their effectiveness, most of the approaches that are based on classical codes (e.g., run-lengths, Huffman) cannot exploit the test-application-time advantage of multiple-scan-chain cores, since they are not able to perform parallel decompression of the encoded data. In this paper, we take advantage of the inherent parallelism of Huffman decoding and we present a generalized multilevel Huffman-based compression approach that is suitable for cores with multiple scan chains. The size of the encoded data blocks is independent of the slice size (i.e., the number of scan chains), and thus it can be adjusted so as to maximize the compression ratio. At the same time, the parallel data-block decoding ensures the exploitation of most of the scan chains' parallelism. The proposed decompression architecture can be easily modified to suit any Huffman-based compression scheme.

Selective Huffman coding has recently been proposed for efficient test- data compression with low hardware overhead. In this paper, we show that the already proposed encoding scheme is not optimal and we present a new one, proving that it is optimal. Moreover, we compare the two encodings theoretically and we derive a set of conditions which show that, in practical cases, the proposed encoding always offers better compression. In terms of hardware overhead, the new scheme is at least as low-demanding as the old one. The increased compression efficiency, the resulting test-time savings, and the low hardware overhead of the proposed method are also verified experimentally.

A new test-data compression method suitable for cores of unknown structure is introduced in this paper. The proposed method encodes the test data provided by the core vendor using a new, very effective compression scheme based on multilevel Huffman coding. Each Huffman codeword corresponds to three different kinds of information, and thus, significant compression improvements compared to the already known techniques are achieved. A simple architecture is proposed for decoding the compressed data on chip. Its hardware overhead is very low and comparable to that of the most efficient methods in the literature. Moreover, the major part of the decompressor can be shared among different cores, which reduces the hardware overhead of the proposed architecture considerably. Additionally, the proposed technique offers increased probability of detection of unmodeled faults since the majority of the unknown values of the test sets are replaced by pseudorandom data generated by a linear feedback shift register

Single or multibit subword permutations are useful in many multimedia and cryptographic applications. Several specialized instructions have been proposed to handle the required data rearrangements. In this paper, we examine the hardware implementation of the powerful permutation instruction group (GRP). The design of the proposed permutation unit is based on the functionality of sorting networks. Two variants of the sorter-based GRP unit are introduced and analyzed and their energy-delay behavior is investigated using static CMOS implementations in a 130-nm CMOS technology.

Domino CMOS circuits are an option for speeding up critical units. An inherent problem of Domino logic is that under specific input conditions the charge redistribution between parasitic capacitances at internal nodes of a circuit can violate the noise margins and cause erroneous responses at the output. The dominant solution to this problem is the multiple precharging of the gate's internal nodes. However, the added precharge transistors are not testable for stuck-open faults. Undetectable stuck-open faults at these transistors may cause noise margins reduction and consequently may affect the reliability of the circuit since its operation in the field will be sensitive to environmental factors such as noise. In this paper, we propose new multiple precharging design schemes that enhance Domino circuits' testability with respect to transistor stuck-open and stuck-on faults

Subword permutations are useful in many multimedia and cryptographic applications. Specialized instructions have been added to the instruction set of general-purpose processors to efficiently implement the required data rearrangements. In this paper, the design of a new energy-delay efficient subword permutation unit is examined. The proposed architecture has been derived by mapping the functionality of one of the most powerful permutation instructions (GRP) to a new enhanced linear sorting network. The introduced subword permutation unit is fast and achieves significant area and energy reductions compared to previous implementations. Also its regularity and its reduced wiring enables efficient VLSI implementations. The efficiency of the proposed architecture has been validated using static CMOS implementations in a standard performance 130nm CMOS technology

In this paper we introduce a new test-data compression method for IP cores with unknown structure. The proposed method encodes the test data provided by the core vendor using a new, very effective compression scheme based on multilevel Huffman coding. Specifically, three different kinds of information are compressed using the same Huffman code, and thus significant test data reductions are achieved. A simple architecture is proposed for decoding on-chip the compressed data. Its hardware overhead is very low and comparable to that of the most efficient methods in the literature. Additionally, the proposed technique offers increased probability of detection of unmodeled faults since the majority of the unknown values of the test set are replaced by pseudorandom data generated by an LFSR.

In this paper we show first that finding the location of a test vector in the sequence generated by an accumulator driven with an odd additive constant C is equivalent to the solution of a linear Diophantine equation with two variables. The latter equation is known to be solved fast in linear time. We then show that only one Diophantine equation needs to be solved per test set irrespective of the number of patterns in it. The finding of the locations of all patterns of a given test set T in the sequence generated under a constant C is done in O(n+ | T |) steps instead of O(n middot |T|) steps of a previous approach. Next we present a method which, given a test set T, and an odd constant C, finds the seed in the sequence generated under C that can reproduce all patterns of T in minimum length. We use this optimum technique to search for the best constant C' (in terms of short test length) in a randomly generated subset. Experimental results show the potential of the approach for test set embedding

Bit and subword permutations are useful in many multimedia and cryptographic applications. New shift and permute instructions have been added to the instruction set of general-purpose microprocessors to efficiently implement the required data permutations. In this paper, the design of a high speed bit permutation unit is examined. The proposed architecture has been derived by mapping the functionality of one of the most powerful bit permutation instructions (GRP) to a new enhanced bitonic sorting network. The proposed design achieves delay reductions more than 20% when compared with previously presented solutions, while its regularity enables efficient VLSI implementations

Arithmetic-function modules, which are available in many circuits, can be utilized to generate test patterns and compact test responses. An accumulator-based scheme along with a procedure to find maximum-length nonlinear sequences for bit-serial test-pattern generators is proposed. The proposed scheme achieves good fault coverage with low hardware overhead and short test sequences

Parallel-prefix adders offer a highly efficient solution to the binary addition problem and are well-suited for VLSI implementations. A novel framework is introduced, which allows the design of parallel-prefix Ling adders. The proposed approach saves one-logic level of implementation compared to the parallel-prefix structures proposed for the traditional definition of carry lookahead equations and reduces the fanout requirements of the design. Experimental results reveal that the proposed adders achieve delay reductions of up to 14 percent when compared to the fastest parallel-prefix architectures presented for the traditional definition of carry equations.

In this work, we propose a new algorithm for designing diminished-1 modulo 2/sup n/+1multipliers. The implementation of the proposed algorithm requires n + 3 partial products that are reduced by a tree architecture into two summands, which are finally added by a diminished-1 modulo 2/sup n/+1 adder. The proposed multipliers, compared to existing implementations, offer enhanced operation speed and their regular structure allows efficient VLSI implementations.

In this paper we propose a new Test Pattern Generator (TPG) for the detection of realistic faults occurring in CMOS nanometer technologies. The proposed TPG compares favorably to the corresponding already known TPGs with respect to the fault coverage obtained by test sequences of the same length. Another advantage of the proposed TPG is that the same TPG can be used for testing more than one modules in a SOC.

2/sup n/-1 is one of the most commonly used moduli in residue number systems. In this paper, we propose a new method for designing modified Booth modulo 2/sup n/-1 multipliers, which, for even values of n, require one less partial product than the already known. CMOS implementations reveal that the proposed multipliers compared to earlier solutions offer savings up to 28.7 percent and up to 29.3 percent in the implementation area and execution delay, respectively.

Modulo 2/sup n/+1 adders find great applicability in several applications including RNS implementations and cryptography. In this paper, we present two novel architectures for designing modulo 2/sup n/+1 adders, based on parallel-prefix carry computation units, the first architecture utilizes a fast carry increment stage, whereas the second is a totally parallel-prefix solution. CMOS implementations reveal the superiority of the resulting adders against previously reported solutions in terms of implementation area and execution latency.

In this paper, a new reseeding architecture for scan-based built-in self-test (BIST), which uses a linear feedback shift register (LFSR) as test pattern generator, is proposed. Multiple cells of the LFSR are utilized as sources for feeding the scan chain of the circuit under test in different test phases. The LFSR generates the same state sequence in all phases, keeping that way the implementation cost low. A seed-selection algorithm is furthermore presented that, taking advantage of the multiphase architecture, manages to significantly reduce the number of the required seeds for achieving complete (100%) fault coverage. The proposed technique can be used either in a full BIST implementation or in a test-resource partitioning scenario, since the test-data storage requirements on the tester are very low. When a full BIST implementation is preferable, the multiphase architecture can also be combined with a dynamic reseeding scheme that uses combinational logic instead of a ROM in order to perform the reseedings. This way the implementation area of the BIST circuitry is further reduced. Experimental results demonstrate the advantages of the proposed LFSR reseeding approach over the already known reseeding techniques.

We reveal the cyclic nature of idempotency in the case of modulo 2/sup n/-1 addition. Then based on this property, we derive for each n, a family of minimum logic depth modulo 2/sup n/-1 adders, which allows several trade-offs between the number of operators, the internal wire length, and the fanout of internal nodes. Performance data, gathered using static CMOS implementations, reveal that the proposed architectures outperform all previously reported ones in terms of area and/or operation speed.

In this paper a novel reseeding architecture for scan-based BIST, which uses an LFSR as TPG, is proposed. Multiple cells of the LFSR are utilized as sources for feeding the scan chain in different test phases. The LFSR generates the same state sequence in all phases, keeping that way the implementation cost low. Also, a dynamic reseeding scheme is adopted for further reducing the required hardware overhead. A seed-selection algorithm is moreover presented that, taking advantage of the multi-phase architecture, manages to reduce the number of the required seeds for achieving complete (100 %) fault coverage. Experimental results demonstrate the superiority of the proposed LFSR reseeding approach over the already known reseeding techniques.

In this paper we present a new pseudorandom BIST scheme for high-speed adders. Under this scheme an adder is simultaneously used as a test pattern generator and as a response compactor during its own testing. The main advantages of the proposed scheme, compared to prior methods, are minimal performance penalty, small hardware overhead and the benefits of at-speed testing.

We present new design methods for modulo 2/sup n//spl plusmn/1 adders. We use the same select-prefix addition block for both modulo 2/sup n/-1 and diminished-one modulo 2/sup n/+1 adder design. VLSI implementations of the proposed adders in static CMOS show that they achieve an attractive combination of speed and area costs.

Modulo 2/sup n/ -1 adders as fast as n-bit 2's complement adders have been recently proposed in the open literature. This makes a residue number system (RNS) adder with channels based on the moduli 2/sup n/, 2/sup n/ - 1, and any other of the form 2/sup k/ - 1, with k < n, faster than RNS adders based on other moduli. We formally derive a parametric, with respect to the adder size, test set, for parallel testing of the channels of an RNS adder based on moduli of the form 2/sup n/, 2/sup n/ - 1, 2/sup k/ - 1, 2/sup l/ - 1, ..., with l < k < n. The derived test set is reusable; it can be used for any value of n, k, l, ..., regardless of the implementation library used and is composed of n/sup 2/ + 2 test vectors. A test-per-clock BIST scheme is also proposed that applies the derived test vectors within n/sup 2/ + 2n cycles. Static CMOS implementations reveal that the proposed BIST offers 100 percent postcompaction fault coverage and an attractive combination of test time and implementation area compared to ROM and FSM-based deterministic BIST or LFSR-based pseudorandom BIST.

In this paper, we present a new LFSR reseeding scheme for scan-based BIST, suitable for circuits with random-pattern-resistant faults. The proposed scheme eliminates the need of a ROM for storing the seeds since the reseedings are performed dynamically by inverting some selected bits of the LFSR register. A time-to-market efficient algorithm is also presented for selecting the reseeding points in the test sequence, as well as a proper seed at each point. This algorithm targets complete fault coverage and minimization of the resulting test length and hardware overhead. Experimental results on ISCAS '85 and ISCAS '89 benchmark circuits demonstrate the advantages of this new LFSR reseeding approach in terms of area overhead and test application time.

This paper presents two new design methodologies for modulo 2/sup n/+1 addition in the diminished-one number system. The first design methodology leads to carry look-ahead, whereas the second to parallel-prefix adder implementations. VLSI realizations of the proposed circuits in a standard-cell technology are utilized for quantitative comparisons against the existing solutions. Our results indicate that the proposed carry look-ahead adders are area and time efficient for small values of n, while for the rest values of n the proposed parallel-prefix adders are considerably faster than any other already known in the open literature.

The partition of the inputs of a circuit under test (CUT) into groups of compatible inputs reduces the size of a test pattern generator and the length of the test sequence for built-in self-test (BIST) applications. In this paper, a new test-per-clock BIST scheme is proposed which is based on multiple input partitions. The test session consists of two or more phases, and a new grouping is applied during each test phase. Using the proposed method a CUT can be tested at-speed and complete fault coverage (100%) is achieved with a small number of test vectors and small area overhead. Our experiments show that the proposed technique compares favorably to the already known techniques.

We present a new methodology for designing modulo 2/sup n/+1 adders with operands in the diminished-one number system. The proposed methodology leads to parallel-prefix adder implementations. Both an analytical model and VLSI implementations in a standard-cell technology are utilized for comparing the adders designed following the proposed methodology against the existing solutions. Our results indicate; that the proposed parallel-prefix adders are considerably faster than any other already known in the open literature and as fast as the corresponding modulo 2/sup n/ and modulo 2/sup n/-1 adders.

In this paper we present a novel reseeding technique for accumulator-based Test Pattern Generation suitable for circuits with hard-to-detect faults. Storing the seeds is not necessary since the seeds are generated on-the-fly by inverting the logic value of some of the bits of the accumulator's register. The proposed technique achieves complete fault coverage with shorter test sequences and requires less hardware for its implementation than the corresponding already-known techniques. Furthermore, our technique does not affect the system performance since the logic required for its implementation is not inserted in the critical path. 1.

Summary form only given. A new Built-in Self Test (BIST) scheme is presented that can be used for both off-line production or periodic testing of delay faults as well as for concurrent detection of faults causing signal delays in the field. The scheme is based on the I/sub DDT/ monitoring of the outputs of the circuit under test (CUT). The proposed scheme has minimal impact on the performance and silicon area of the design since the same response verifier circuit is used for both off-line and concurrent detection of errors in the field.

In this paper we show that an accumulator can be modified to behave as a Non-Linear Feedback Shift Register suitable for test response compaction. The hardware required for this modification is less than that required to modify a register to a Multiple Input Linear Feedback Shift Register, MISR. We show with experiments on ISCAS'85, ISCAS'89 benchmark circuits and various types of multipliers that the post-compaction fault coverage obtained by the proposed scheme is higher than that of the already known accumulator based compaction schemes and in most cases identical to that achieved using a MISR.

A novel parallel-prefix architecture for high speed module 2/sup n/-1 adders is presented. The proposed architecture is based on the idea of recirculating the generate and propagate signals, instead of the traditional end-around carry approach. Static CMOS implementations verify that the proposed architecture compares favorably with the already known parallel-prefix or carry look-ahead structures.

Testing of N/spl times/N Non-Restoring Cellular Array Dividers (NRCAD) with respect to path delay faults, is studied in this paper. Design modifications are proposed and a path selection method is suggested. We prove that the selected paths are Single Path Propagating Hazard Free Robustly Testable (SPP-HFRT) and that by measuring their delays the delay along any other path of the divider can be easily calculated. The number of selected paths is impressively small compared to all paths of the divider. The delay overhead of the modified design for all values of N is negligible, while the hardware overhead is small too. This is the first easily testable, with respect to path delay faults, NRCAD design in the open literature.

In this paper we show that the already known method of using multiplexers for making the inputs and outputs of the embedded blocks accessible by the primary ports of the integrated circuit (IC) can be used for path delay fault testing of the IC. We show that the testing of the IC for path delay faults can be reduced to the testing of each block. Intellectual property (IP) blocks are treated as black boxes. The number of circuit paths that must be tested is almost equal to the sum of the paths that must be tested for each block.

In this paper we present a method for path delay fault testing of multiplexer-based shifters. We show that many paths of the shifter are non-robustly testable and we give a path selection method so as all the selected paths to be robustly testable by 20*log/sub 2/n+2 test-vector pairs, where n is the length of the shifter. The propagation delay along all other paths is a function of the delays along the selected paths.

It is well known that the most common errors in VLSI circuits are unidirectional in nature. Many applications need protection against up to t unidirectional errors, while some others against burst unidirectional errors. Bose-Lin codes are systematic t-unidirectional error detecting codes while Bose codes are burst unidirectional error detecting codes. In this paper we propose a modular method for designing double output checkers for Bose-Lin and Bose codes. The proposed checkers are Totally Self Checking (TSC) with respect to a realistic fault model including stuck-at, transistor stuck-open, transistor stuck-on, resistive bridging faults and breaks. The method is applicable to every code information length and the checkers are very compact and fast.

Yield enhancement through the acceptance of partially good chips is a well-known technique. In this paper, we derive a yield model for single-chip VLSI processors with partially good on-chip cache. Also, we investigate how the yield enhancement of VLSI processors with on-chip CPU cache relates with the number of acceptable faulty cache blocks, the percentage of the cache area with respect to the whole chip area, and various manufacturing process parameters as defect densities and the fault clustering parameter. One of the main conclusions is that the maximum effective yield is achieved by accepting as good, caches with a very small number of faulty cache blocks. One of the main conclusions is that the maximum effective yield is achieved by accepting as good, processor chips containing caches with a very small number of faulty cache blocks.

In this paper a novel input vector monitoring concurrent BIST technique based on a RAM (R-CBIST) is presented. This technique compares favorably to the other input vector monitoring concurrent BIST techniques proposed so far with respect to the hardware overhead and the time required for the concurrent test to be completed (concurrent test latency). R-CBIST can be used in practice for exhaustive testing of ROMs since it results in small hardware overhead whereas no need to stop the ROM normal operation is required.

This paper presents a novel method for designing type-I and type-II single and double output TSC Berger code checkers taking into account a realistic fault model including stuck-at, transistor stuck-open, transistor stuck-on, resistive bridging faults and breaks. A benefit of the proposed type-I single and double output checkers is that all faults are testable by a very small set of code words the number of which does not increase with the information length, that is, the checkers are C-testable. The proposed double output checkers are two-times faster than the corresponding single output checkers, but require for their implementation twice as many transistors as the single output checkers. The proposed single output checkers are the first known TSC Berger code checkers in the open literature, while the type-I single output checkers are near optimal with respect to the number of the transistors required for their implementation. The checkers of this paper with either, single or double output are significantly more efficient, with respect to the implementation area and speed than the already known from the open literature Berger code checkers.

This paper presents a new simple and straightforward method for designing Self-Testing Embedded (STE) parity checkers. The building block is the two-input XOR gate. During normal, fault-free operation, each XOR gate receives all possible input vectors. The great advantage of the proposed method is that it is the only one that gives, in a simple and straightforward way, optimal STE realizations with respect to the cost (number of XOR gates) and the speed (number of XOR gate levels).

In this paper we give a systematic method to design self-exercising (SE) self testing k-order comparators. The k-order comparator is defined as a combinational circuit that compares two operands and decides if these differ in less than k bits. According to this definition the usual equality comparator is the 1st-order comparator. Also in this paper we discuss the applicability of the k-order comparators in the implementation of (k-1)-EC/AUED, (k-1)-EC/d-ED/AUED, (k-1)-EC/d-UED and (k-1)-EC/d-ED/f-UED codes as well as in the design of a fault tolerant cache memory and broadcast networks.

Built-In Self-Test (BIST) techniques constitute an attractive and practical solution to the difficult problem of testing VLSI circuits and systems. Among the BIST techniques the Comparative Concurrent BIST (C-BIST) has various advantages since it provides for off-line test generation, when it is desirable, and thus accomplishes a mixed on-line/off-line BIST scheme. However, in C-BIST when the test sequence is long, the time required for all the test vectors to appear among the normal inputs to the circuit (test latency) is significantly long. Modifications of the C-BIST technique have been proposed in order to reduce the test latency. In this paper we propose a new C-BIST technique termed windowed-CBIST (w-CBIST) for test latency reduction. The proposed technique is shown to be significantly more efficient from the previous methods with respect to test latency and hardware overhead.

In this paper we give the fundamental theory for testing one or two-dimensional Iterative Logic Arrays (ILAs) with respect to realistic faults requiring two-pattern or generally n-pattern tests. We give conditions so that C-testability and linear-testability are preserved. According to our approach the extensive work made for ILAs under the Cell Fault Model can be easily used to derive an efficient test set of an ILA for more realistic faults.

Paschalis et al. (1988) have given a structured method to design TSC m-out-of-2m code checkers suitable for VLSI implementation. In this correspondence we give sufficient conditions so that the method previously given can be used to design checkers for classes of m-out-of-n codes with n/spl ne/2m.>

In this paper a new method to design totally self-checking (TSC) checkers for a class of Borden codes is given and their applicability is discussed. The TSC checkers designed in this paper are impressively more efficient, with respect to implementation cost and speed, than the corresponding checkers hitherto proposed in the literature.>

The fundamental theory of t-error correcting, k-error detecting, and d-unidirectional error detecting codes with d>k>t (t-EC/k-ED/d-UED codes) is presented. The authors give a family of methods for designing systematic t-EC/k-ED/d-UED codes, with d>k>t, and they reveal the methods which give the more efficient, with respect to redundancy, codes for the various values of t, k, and d. The error detection and correction algorithm is also presented.>

The fundamental theory of t-error correcting/d-error-detecting (d>t) and all-unidirectional-error-detecting (t-EC/d-ED/AUED) codes is given. A method for the construction of systematic t-EC/d-ED/AUED codes is presented. The encoding/decoding algorithms for these codes and their implementation are described.>

A method is proposed that is based on the partitioning of the input code variables into two sections, each section representing the binary form of a number Z/sub 1/ and Z/sub 2/, respectively. For a code with check base A=2/sup m/-1, two m-bit end-around carry adder trees calculate the modulo m residue of Z/sub 1/ and Z/sub 2/, while a totally self-checking (TSC) translator maps the output of the pair of trees onto m-variable two-rail code. A TSC two-rail checker maps the m-variable two-rail code onto one-out-of-two code. The checkers present significant improvement in the implementation cost, number of gate levels, and reliability over TSC checkers previously proposed in the literature.>

A design method of totally self-checking (TSC) m-out-of-2m code checkers is presented. The design is composed basically of two full-adder/half-adder trees, each summing up the ones received on m input lines, and a k-variable two-pair two-rail code tree that compares the outputs of the two-adder tree. The only modules used are full-adders, half-adders, and two-variable TSC two-rail code checkers. This method is well suited for VLSI MOS implementation and, compared to previous methods, it results in significant circuit cost reduction and smaller test set, without sacrificing performance. Also, the proposed design has the advantages of a modular design.>

In this paper we give methods for the construction of systematic t-random error correcting and all unidirectional error detecting codes. Also we give the encoding/decoding algorithms and discuss their implementation.