The Stored Unibit Transfer (SUT) encoding has been recently proposed as a redundant high-radix encoding for each of the channels of a Residue Number System (RNS) that can improve the efficiency of Binary Signed Digit (BSD)-encoded RNS. However, a residue-to-binary (reverse) converter for it has not yet been reported in the open literature. In this paper we introduce SUT-RNS reverse converters for two different moduli sets, that is, for the 3-moduli {2^n-1, 2^n, 2^n+1} and for the 4-moduli {2^n-1, 2^n, 2^n+1, 2^(2n)+1} sets. The area and delay costs of the proposed converters are shown to be less than those required by the corresponding RNS converters for the BSD encoding. In the 4-moduli set case, the converters' costs are shown to be close to those of the corresponding converters for the binary encoding

Two architectures for modulo 2n+1 adders are introduced in this paper. The first one is built around a sparse carry computation unit that computes only some of the carries of the modulo 2n+1 addition. This sparse approach is enabled by the introduction of the inverted circular idempotency property of the parallel-prefix carry operator and its regularity and area efficiency are further enhanced by the introduction of a new prefix operator. The resulting diminished-1 adders can be implemented in smaller area and consume less power compared to all earlier proposals, while maintaining a high operation speed. The second architecture unifies the design of modulo 2n± 1 adders. It is shown that modulo 2n+1 adders can be easily derived by straightforward modifications of modulo 2n-1 adders with minor hardware overhead.

The diminished-one representation has been proposed for RNS-based systems with moduli of the 2n+1 forms as an encoding that is more efficient than the normal representation in the arithmetic processing units. However, its use necessitates a two-step reverse conversion, in which a diminished-to-normal conversion is first performed before the final residue-to-binary conversion resulting in performance loss. In this paper we introduce efficient modulo 2n+1 adders, sub tractors and multipliers that accept diminished-one operands at their inputs and derive normal operands at their outputs, that is, we embed the diminished-to-normal conversion within the arithmetic processing. Experimental results show that the proposed one-step approach is more efficient in terms of delay.

Multi-moduli architectures are very useful for reconfigurable digital processors and fault-tolerant systems that are based on the Residue Number System (RNS). In this paper we propose two architectures for multi-moduli squaring that support the most common moduli cases in RNS channels, that is, 2n-1, 2nand 2n+1. The proposed architectures are based on the modified Booth encoding of the input operand for deriving the required partial products and on Dadda adder trees for their addition. Experimental results show that the proposed squarers offer significant savings in area compared to previous proposals while a small improvement in delay is achieved in most cases as well.

The contribution of this paper is twofold. We firstly show that an augmented diminished-1 adder can be used for the modulo 2n+1 addition of two n-bit operands in the weighted representation, if it is driven by operands whose sum has been decreased by 1. This scheme outperforms solutions that are based on the use of binary adders and/or weighted modulo 2n+ 1 adders in both area and delay terms. We then apply this scheme in the design of residue generators (RGs) and multi-operand modulo adders (MOMAs). The resulting arithmetic components remove at least a whole parallel adder out of the critical path of the currently most efficient proposals. Experimental results indicate savings of more than 30% in execution time and of approximately 19% in implementation area when the proposed architectures are used.

A new effective built-in self-test (BIST) scheme for non- restoring array dividers (NADs) is proposed, that offers more than 99% cell fault coverage in all NADs of practical use. Moreover, it can be implemented in small hardware and can apply all its test vectors within 128 clock cycles. A version of the proposed scheme for power critical applications is also exploited.

A new modulo 2n+1 multiplier architecture is proposed for operands in the normal representation. The novel architecture is derived by showing that all required correction factors can be merged into a single constant one and by treating this, partly as a partial product and partly by the final parallel adder. The proposed architecture utilizes a total of (n+1) partial products, each n bits wide and is built using an inverted end-around-carry, carry-save adder tree and a final parallel adder.

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.

Squarers modulo M are useful design blocks for digital signal processors that internally use a residue number system and for implementing the exponentiators required in cryptographic algorithms. In these applications, some of the most commonly used moduli are those of the form 2/sup n/ + 1. To avoid using (n + 1)-bit circuits, the diminished-1 number system can be effectively used in modulo 2/sup n/ + 1 arithmetic applications. In this paper, for the first time in the open literature, we formally derive modulo 2/sup n/ + 1 squarers that adopt the diminished-1 number system. The resulting implementations are built using only full- or half-adders and a final diminished-1 adder and can therefore be pipelined straightforwardly.

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.

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 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.

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.

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.

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.

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.