A way to speed up the Montgomery Multiplication by distributing the multiplier operand bits into${\mbi {k}}$partitions is proposed. All of them process in parallel and use an identical algorithm. Each partition executes its task in${\mbi {n/k}}$steps. Even though the computationstep operates in radix${\mbi {2^k}}$, the complexity is reduced by the use of a limited digit set. Experiments with a 90-nm cell library show that the hardware cost and its complexity have a linear growth according to the number of partitions. Besides the gain in speed, the proposal reduces power consumption for multiplication operands with 256, 512, 1024, and 2048 bits. The uniform treatment of partition hardware design enables the realization of a fault-tolerant hardware.

This paper proposes a new approach to speed up the Montgomery Multiplication by distributing the multiplier operand bits into k partitions that can process in parallel. Each partition executes in n/k steps. A computation step, although operating in radix 2k, has its complexity reduced by the use of a limited digit set. Experiments with a 90nm cell library show that the hardware cost and its complexity have a linear growth with the number of partitions. Besides the gain in speed, the approach provides 20% average reduction in energy consumption for multiplication operands with 256, 512, 1024, and 2048 bits.

The design of a component to perform parallel addition of multiple floating-point (FP) operands is explored in this work. In particular, a 3-input FP adder is discussed in more detail, but the main concepts and ideas presented in this work are valid for FP adders with more inputs. The proposed design is more accurate than conventional FP addition using a network of 2-operand FP adders and it may have competitive area and delay depending on the number of input operands. Implementation results of a 3-operand FP adder are presented to compare its performance to a network of 2-input FP adders.

Several arithmetic circuits use carry-save (CS) representation of signed numbers in one's complement or two's complement. However, arithmetic right shifts of the CS form may generate incorrect results. This work presents the problem and proposes a simple solution to keep the correct CS representation of signed numbers when arithmetic right-shift operations or sign extensions are required. The authors discuss why the problem does not occur in most of the traditional implementations of arithmetic circuits and also emphasize that it may happen for some types of arithmetic algorithm and arithmetic hardware design.

The use of online arithmetic was often proposed for hardware implementations of complex digital-signal processing (DSP) algorithms. However, several important issues in the design process of such algorithms using online arithmetic are rarely discussed in the literature. This paper presents these issues and provides a methodology to analyze the behavior of networks of online arithmetic modules performing serial computation over fixed-point numbers. The methodology is presented, applied in several examples, and finally used to design an efficient field programmable gate arrays implementation of the Levinson-Durbin algorithm in an application of the Yule-Walker power spectrum estimation. The methodology can be applied to other algorithms as well and it simplifies the task of designing and verifying a network of online modules. The experimental results show the advantages of online arithmetic in the design of complex DSP algorithms.

This paper presents a scalable architecture for the computation of modular multiplication, based on the Montgomery multiplication (MM) algorithm. A word-based version of MM is presented and used to explain the main concepts in the hardware design. The proposed multiplier is able to work with any precision of the input operands, limited only by memory or control constraints. Its architecture gives enough freedom to select the word size and the degree of parallelism to be used, according to the available area and/or desired performance. Design trade offs are analyzed in order to identify adequate hardware configurations for a given area or bandwidth requirement.

This paper presents the application of the Linear Sequential Array (LSA) organization to on-line division. The LSA method was originally developed for conventional digit-recurrence algorithms, but we apply it to the on-line division algorithm. The resulting architecture is a modular and fast pipelined structure which, due to a constant fan-out, makes the critical path delay, and consequently the clock cycle time, less sensitive to operand's precision. Such approach is particularly suitable for FPGA implementation for its modularity and reduced fanout. The basics of on-line division is presented, followed by the derivation of data dependencies and architecture according to the LSA design methodology. Experimental data is provided for both the LSA on-line divider design and standard online design, using 0.5 /spl mu/m CMOS ASIC and FPGA technologies.

We present a design of a high-radix on-line division suitable for long precision computations. The proposed scheme uses a quotient-digit selection function based on the residual rounding and scaling of the operands. The bounds on the number of cycles and the cycle time for radix 2/sup k/ and n-bit precision are obtained in terms of full-adder delays. The speedup with respect to radix 2 is greater than 3.3 for k/spl ges/6 and n/spl ges/64. The cost increases as a function of the radix. For the case r=64 and n=64, the increase in area with respect to r=2 is about 6.6 times plus a 512/spl times/10-bit table. The proposed scheme has been designed and verified using VHDL and a 1.2 /spl mu/m CMOS standard gate technology from MOSIS library.

This paper presents the organization of an arithmetic unit for variable long-precision (VLP) operands suitable for reconfigurable computing. The reconfigurable arithmetic coprocessor (RAC) cooperates with the host computer in the VLP tasks. The main design issues addressed in the paper are: (a) mapping of the most frequent and time consuming operations of the VLP arithmetic algorithms to RAG, and (b) design of VLP algorithms that allow reduced reconfiguration time between arithmetic operations. The VLP arithmetic algorithms proposed cover multiplication, division and square root. In this paper we present the main building blocks used in the VLP arithmetic circuits, show the similarities of each arithmetic operator and present area/time estimates of these circuits in Xilinx FPGAs.

This paper presents recent advances in the design of constant-time up/down counters in the general context of fast counter design. An overview of existing techniques for the design of long and fast counters reveals several methods closely related to the design of fast adders, as well as some techniques that are only valid for counter design. The main idea behind the novel up/down counters is to recognize that the only extra difficulty with an up/down (vs. up-only or down-only) counter is when the counter changes direction from counting up to counting down (and vice-versa). For dealing with this difficulty, the new design uses a "shadow" register for storing the previous counter state. When counting only up or only down, the counter functions like a standard up-only or down-only constant time counter, but, when it changes direction instead of trying to compute the new value (which typically requires carry propagation), it simply uses the contents of the shadow register which contains the exact desired previous value. An alternative approach for restoring the previous state in constant time is to store the carry bits in a Carry/Borrow register.

This paper presents the design of a fast binary counter for LUT FPGAs. The counter has a cycle time independent of the counter size. The key aspects of the design are described and applied to a 64-bit synchronous binary counter implemented in a XC4010 FPGA chip. Experimental results show that the counter can scale up to hundreds of bits while keeping a short cycle time.