Design of a C-testable booth multiplier using a realistic fault model

A Booth multiplier is the most widely used type of multiplier. In this article, the testability issues involved in its design are discussed. In contrast to previous work, the fault model includes not only node stuck-at faults, but also transistor stuck-open and stuck-close faults. Moreover, as a result of adopting a hierarchical testability approach, the designed Booth multiplier turns out to be fully C-testable. To achieve this C-testability, only three additional controllable inputs are required, which results in a negligible area and delay overhead.Currently with Alcatel Bell Telephone.     

A C-testable carry-free divider

In this paper, the design of a C-testable, high-performance carry-free array divider is presented. A radix-2 redundant number based carry-free divider is considered and is modified to make it C-testable, i.e., it can be exhaustively tested using a constant number of test vectors irrespective of its word-length. Previous C-testable designs considered dividers which used carry-propagate adders/subtractors. These dividers are slow because of their O(W²) computation time (where W is the word-length of the divider). High-performance carry-free dividers use carry-free redundant arithmetic adders/subtractors. Due to this feature, they have O(W) computation time. The on-the-fly converter used by carry-free dividers to convert the redundant quotient to two's-complement form is shown to be not C-testable. It is modified to be linear-testable (in word-length) instead of exponential time required for exhaustive testing of all possible combinations at its inputs. We conclude that the number of test vectors needed is 99 for C-testing of the divider array and (3W+10) for linear testing of the converter. The hardware overhead required to make the divider C-testable and the on-the-fly converter linear testable is also shown to be nominal     

Testability Properties of Divergent Trees

The testability of a class of regular circuits calleddivergent trees is investigated under a functional fault model. Divergent trees include such practical circuits as decoders anddemultiplexers. We prove that uncontrolled divergent trees aretestable with a fixed number of test patterns (C-testable) if andonly if the module function is surjective. Testable controlled treesare also surjective but require sensitizing vectors for errorpropagation. We derive the conditions for testing controlleddivergent trees with a test set whose size is proportional to thenumber of levels p found in the tree (L-testability). By viewing a tree as overlapping arrays of various types, we also deriveconditions for a controlled divergent tree to be C-testable. Typicaldecoders/demultiplexers are shown to only partially satisfy L- andC-testability conditions but a design modification that ensuresL-testability is demonstrated.     

Built-in self-test (BIST) design of high-speed carry-free dividers

This paper presents the built-in self-test (BIST) design of a C-testable high-speed carry-free divider which can be fully tested by 72 test patterns irrespective of the divider size. Using a graph labeling scheme, the test patterns, expected outputs, and control signals can be represented by sets of labels and generated by a simple circuitry. As a result, test patterns can be easily generated inside chips, responses to test patterns need not to be stored, and use of expensive test equipment is not necessary. Results show that the hardware cost for generating such labels is virtually constant irrespective of the circuit size. For the BIST design of a 64 b C-testable divider, its hardware overhead is less than 5%     

Design-for-testability and fault-tolerant techniques for FFT processors

In this paper, we first propose a novel design-for-testability approach based on M-testability conditions for module-level systolic fast Fourier transform (FFT) arrays. Our M-testability conditions guarantee 100% single-module-fault testability with a minimum number of test patterns. Based on this testable design, fault-tolerant approaches at the bit level and the multiply-subtract-add (MSA) module level are proposed, respectively. If the reconfiguration is performed at the bit level, then the FFT/sub BIT/ network is constructed. Two types of reconfiguration schemes (Type-I FFT/sub MSA/ and Type-II FFT/sub MSA/) are proposed at the MSA module level. Since both the design for testability (DFT) and the design for yield (DFY) issues are considered at the same time for all these proposed approaches, the resulting architectures are simpler as compared with previous works. The reliability of the FFT system increases significantly. The hardware overhead is low-about 12% and 1/2N for the FFT/sub BIT/ network and the Type-II FFT/sub MSA/ network, respectively. An experimental chip is also implemented to verify our approaches. Reliabilities and hardware overhead are also evaluated and compared with previous works.     

On Concurrent Detection of Errors in Polynomial Basis Multiplication

The detection of errors in arithmetic operations is an important issue. This paper discusses the detection of multiple-bit errors due to faults in bit-serial and bit-parallel polynomial basis (PB) multipliers over binary extension fields. Our approach is based on multiple parity bits. Experimental results presented here show that due to an increase in the number of parity bits, the area overhead tends to increase linearly, but the probability of error detection approaches unity fairly quickly, e.g., for eight parity bits. In bit-serial implementation of a GF(2¹⁶³) PB multiplier using eight parity bits, the area overhead and the probability of error detection are 10.29% and 0.996, respectively. This is achieved without any increase in the computation time of the GF(2¹⁶³) PB multiplier     

Design of C-testable DCVS binary array dividers

Clocked differential cascode voltage switch (DCVS) circuits are dynamic CMOS circuits that have the advantage of being protected against test-set invalidation due to circuit delays and timing skews. The problem of testing nonrestoring and restoring DCVS binary array dividers is discussed. It is shown that a DCVS nonrestoring array divider can be made C-testable with only four or five vectors. These vectors detect all the detectable single stuck-at, stuck-open, and stuck-on faults in the circuit. The additional hardware required to achieve C-testability for an n×n nonrestoring array divider only consists of n-1 two-input XOR gates and one control input. It is also shown that a restoring DCVS binary array divider can be made C-testable with only six vectors, which also detect all the detectable single stuck-at, stuck-open, and stuck-on faults in the circuit. The hardware overhead required for the C-testable design of the n×n restoring array divider consists of n two-input XOR gates and one control input     

Multidimensional systolic arrays for the implementation of discreteFourier transforms

This paper presents an efficient technique for using a multidimensional systolic array to perform the multidimensional discrete Fourier transform (DFT). Extensions of the multidimensional systolic array suitable for fast Fourier transform (FFT) computations such as the prime-factor computation or the 2ⁿ-point decomposed computation of the one-dimensional (1-D) discrete Fourier transform are also presented. The essence of our technique is to combine two distinct types of semisystolic arrays into one truly systolic array. The resulting systolic array accepts streams of input data (i.e., it does not require any preloading), and it produces output data streams at the boundary of the array. No networks for intermediate spectrum transposition between constituent transforms are required. The systolic array has regular processing elements that contain a complex multiplier accumulator and a few registers and multiplexers. Simple and regular connections are required between the PEs     

A Ring Architecture Strategy for BIST Test Pattern Generation

This paper presents a new effective Built-In Self Test (BIST) scheme that achieves 100% fault coverage with low area overhead, and without any modification of the circuit under test (CUT), i.e., no test point insertion. The set of patterns generated by a pseudo-random pattern generator, e.g. a Linear Feedback Shift Register (LFSR), is transformed into a new set of patterns that provides the desired fault coverage. To transform these patterns, a ring architecture composed by a set of masks is used. During on-chip test pattern generation, each mask is successively selected to map the original pattern sequence into a new test sequence. We describe an efficient algorithm that constructs a ring of masks from the test cubes provided by an automatic test pattern generator (ATPG) tool. Moreover, we show that rings of masks are implemented very easily at low silicon area cost, without requiring any logic synthesis tool; a combinational mapping logic corresponding to the masks is placed between the LFSR and the CUT, together with a looped shift register that acts as a mask selecting circuit. Experimental results are given at the end of the paper, demonstrating the effectiveness of the proposed approach in terms of area overhead, fault coverage and test sequence length. Note that this paper is an extended version of [1].     

On the design of fast, easily testable ALU's

A design methodology for implementing fast, easily testable arithmetic-logic units (ALUs) is presented. Here, we describe a set of fast adder designs, which are testable with a test set that has either &thetas;(N) complexity (Lin-testable) or &thetas;(1) complexity (C-testable), where N is the input operand size of the ALU. The various levels of testability are achieved by exploiting some inherent properties of carry-lookahead addition. The Lintestable and C-testable ALU designs require only one extra input, regardless of the size of the ALU. The area overhead for a high-speed 64-bit Lintestable ALU is only 0.5%     

Concurrent error detection and fault location in an FFTarchitecture

A new approach for concurrent error detection in a homogeneous architecture for the computation of the complex N-point fast Fourier transform (FFT) in radix-2 is presented. The proposed approach is based on the relationship between cell computations. It is proved that 100% probability of detection is possible. Overhead issues for hardware and timing are addressed. It is proved that hardware overhead for concurrent error detection is 50% compared to a fault-intolerant complex two-point implementation. A modest time overhead is encountered for error detection and fault location. Error detection can be accommodated online and on a component basis (multiplier or adder/subtractor): full fault location is accomplished by a roving technique. The proposed technique can be efficiently accommodated in a homogeneous layout. A two-phase reconfiguration policy for the proposed architecture is presented. It is proved that switching and routing overhead is modest, while reliability is significantly improved over previous approaches     

Circuit-Level Design Approaches for Radiation-Hard Digital Electronics

In this paper, we present a novel circuit design approach for radiation hardened digital electronics. Our approach is based on the use of shadow gates, whose task it is to protect the primary gate in case it is struck by a heavy cosmic ion. We locally duplicate the gate to be protected, and connect a pair of diode-connected transistors (or diodes) between the outputs of the original and shadow gates. These transistors turn on when the voltages of the two gates deviate during a radiation strike. Our experiments show that at the level of a single gate, our circuit structure has a delay overhead about 1.76% on average, and an area overhead of 277%. At the circuit level, however, we do not need to protect all gates. We present a methodology to selectively protect specific gates of the circuit in a manner that guarantees radiation tolerance for the entire circuit. With this methodology, we demonstrate that at the circuit level, the average delay overhead is about 3% and the average placed-and-routed area overhead is 28%, compared to an unprotected circuit (for delay mapped designs). We also propose an improved circuit protection algorithm to reduce the area overhead associated with our approach. With this approach for circuit protection, the area and delay overheads are further lowered.      

Design for Testability Using State Distances

The average distance between states is proposed as a new testabilitymeasure for finite state machines (FSMs). Also proposed is theconcept of center state to reduce distances in FSMs. This testfunction embedding technique has been shown to improve thetestability of sequential circuits with minimal overhead. Anoverview of several design-for-testability (DFT) andsynthesis-for-testability (SFT) methods for sequential circuits willalso be given in this paper. Experimental results have shown thatthe DFT approach is more advantageous than the SFT approach toimplement our test function. The contribution of this paper is toanalyze the trade-offs between several aspects of DFT and SFTtechniques.     

Optical wireless localization

In this paper, we explore the possibility of using directionality of free-space-optical (a.k.a. optical wireless) communications for solving the 3-D localization problem in ad-hoc networking environments. Range-based localization methods either require a higher node density (i.e., at least three other localized neighbors must exist) than required for assuring connectedness or a high-accuracy power-intensive ranging device such as a sonar or laser range finder which exceeds the form factor and power capabilities of a typical ad-hoc node. Our approach exploits the readily available directionality information provided by a physical layer using optical wireless and uses a limited number of GPS-enabled nodes, requiring a very low node density (2-connectedness, independent of the dimension of space) and no ranging technique. We investigate the extent and accuracy of localization with respect to varying node designs (e.g., increased number of transceivers with better directionality) and density of GPS-enabled and ordinary nodes as well as messaging overhead per re-localization. Although denser deployments are desirable for higher accuracy, our method still works well with sparse networks with little message overhead and small number of anchor nodes (as little as 2). We also present a proof-of-concept prototype of our FSO-based localization techniques and show the validity of our approach even with three transceivers per node.     

Easily Testable Cellular Carry Lookahead Adders

Cellular Carry Lookahead (CLA) adders are systematically implemented in arithmetic units due to their regular, well-balanced structure. In terms of testability and with respect to the classical Cell Fault Model (CFM), cellular CLA adders have poor testability by construction. Design-for-testability (DFT) modifications for cellular CLA adders have been proposed in the literature providing complete CFM testability making the adders either level-testable or C-testable. These designs impose significant area and performance overheads. In this paper, we propose DFT modifications for cellular CLA adders to achieve complete CFM testability with special emphasis on the minimum impact in terms of area and performance. Complete CFM testability is achieved without adding any extra inputs to the adder, with very small area and performance overheads, thus providing a practical solution. The proposed DFT scheme requires only 1 extra output and it is not necessary to put the circuit in a special test mode, while the earlier schemes require the addition of 2 extra inputs to set the circuit in test mode. A rigorous proof of the linear-testability of the adder is given and a sufficient linear-sized test set is provided that guarantees 100% CFM fault coverage. Surprisingly, the size of the proposed linear-sized test set is, in most practical cases, comparable or even smaller than a logarithmic-sized test set proposed in the literature.     

A DFT Technique for Testing High-Speed Circuits with Arbitrarily Slow Testers

This paper presents a design for testability (DFT) technique for testing high-speed circuits with a low-speed test mode clock. With this technique, the test mode clock frequency can be reduced with virtually no lower limit. Even with the reduced speed requirement on the automatic test equipment (ATE), our method facilitates the test of the rated-speed timing and allows performance binning. A CMOS implementation of the DFT hardware with 50 ps timing accuracy is presented. To demonstrate the effectiveness of the technique we designed a 16-bit, 1.4 GHz pipelined multiplier as a test vehicle. Simulations using a test clock frequency much lower than the rated clock frequency show that delay faults of sizes as small as 50 ps are detected and that the new test technique provides correct performance binning.     

阵列乘法器通路时延故障的内建自测试

阵列乘法器因高度集成和高速运行,容易受到时延故障的困扰.该文对阵列乘法器的通路时延故障提出了一种用累加器实现的以单跳变序列作为测试序列的内建自测试方案.已有的理论和实践表明采用单跳变测试序列比多跳变序列具有更高的测试鲁棒性.同时,该文的测试方案在测试通路覆盖率和测试向量数之间做到了兼顾.仿真结果表明这种单跳变测试序列具有高测试通路覆盖率.此外,测试生成通过系统已有累加器的复用可节省硬件成本开销.     

Error-Efficient Approximate Multiplier Design using Rounding Based Approach for Image Smoothing Application

We propose a novel, error-efficient approximate multiplier (EEAM), which is based on a rounding-based approach (RBA). Multiplication is performed using rounding, shift, and add operations. We round the input operands to the nearest power of two using RBA. The modified inputs are processed by an arithmetic block (AB), which consists of addition, subtraction, and shifter blocks. The proposed approximate multiplier has input operands whose widths range from 8-bit to 32-bits. We simulated the proposed multiplier by using Vivado and MATLAB. The proposed multiplier is also synthesized using the Cadence RTL compiler, and compared to prior approximate multiplier proposals, EEAM’s delay and energy consumption are about of 22% and 57% better than the best known approximate multipliers. We also show that the proposed approximate multiplier’s worst-case error, mean error distance, mean relative error distance, and normalized error distance are about 3%, 44%, 45%, and 13% improvement over existing approximate multipliers. Finally, we used the proposed approximate multiplier in an image smoothing filter., For this application, we observed that our multiplier provides higher PSNR and SSIM than any prior approximate multiplier.