Division and square root are fundamental operations required by most computer systems. They are commonly implemented in hardware using radix-4 recurrence, which produces a 2-bit result digit on each step. Unified digit selection logic chooses the next quotient or square root digit based on a residual and divisor or square root approximation. This paper presents the first derivation of digit selection constants for unified radix-4 recurrence division and square root.

This paper presents a new scheme for evaluating complex reciprocal and exponential functions in hardware. The proposed method utilizes a two-dimensional convolution algorithm to interpolate bivariate functions from tabulated function values in the complex domain. To reduce the memory requirements for lookup tables, the interpolation is decomposed into independent row and column computations, such that the same coefficient table can be shared. Three different interpolation kernels from degree-1 (linear) to degree-2 (quadratic Lagrange) and degree-3 (cubic Lagrange) are explored to find the optimal design parameters and the most acceptable trade-offs between performance and hardware resources. Moreover, a generic hardware architecture is designed to provide scalable implementation capabilities for computation precision and interpolation degree. To verify the proposed architecture, eight complex reciprocal and eight complex exponential design instances are implemented. The ASIC- and FPGA-based experimental results show that the proposed scheme can efficiently approximate the complex reciprocal and exponential functions with up to 16-bit precision, as well as achieve a considerable reduction of memory requirements compared with traditional bipartite and multipartite schemes. The proposed method is also applicable to other complex functions.

Power consumption is a critical aspect in today's mobile environment, while high-throughput remains a major design goal. To satisfy both low-power and high-throughput requirements, parallelism has been employed. In this paper we present an approach to reducing power dissipation in the design of sum-of-products operation by utilizing parallel hardware while maintaining high-throughput. The proposed design reduces about 46% of execution time with about 12% energy penalty compared to the ARM7TDMI-S multipliers in benchmark programs.

Minimizing the power dissipation of parallel multipliers is important for mobile digital signal processing. In this paper, we present an approach to reducing power dissipation in the design of parallel multipliers by utilizing voltage islands to exploit non-uniform arrival of inputs to the carry propagate adder. Our approach reduces up to approximately 20% of dynamic power dissipation with little delay penalty in a parallel multiplier of a tree type, and uses a fast simple adder instead of a hybrid adder.

Table lookup based function computation can significantly save energy consumption. However existing table lookup methods are mostly used in ASIC designs for some fixed functions. The goal of this paper is to enable table lookup computation in general-purpose processors, which requires adaptive lookup tables for different applications. We provide a complete design flow to support this requirement. We propose a novel approach to build the reconfigurable lookup tables based on emerging nonvolatile memories (NVMs), which takes full advantages of NVMs over conventional SRAMs and avoids the limitation of NVMs. We provide compiler support to optimize table resource allocation among functions within a program. We also develop a runtime table manager that can learn from history and improve its arbitration of the limited on-chip table resources among programs.

We present a new way of approximating the sine and cosine functions by a few table look-ups and additions. It consists in first reducing the input range to a very small interval by using rotations with "(M, p, k) friendly angles", proposed in this work, and then by using a bipartite table method ina small interval. An implementation of the method for 24-bit case is described and compared with CORDIC. Roughly, the proposed scheme offers a speedup of 2 compared with an unfolded double-rotation radix-2 CORDIC.

We present a novel design of a radix-16 combined unit for complex division and square root in fixed-point format. A new digit-recurrence algorithm with two-step operand prescaling is developed for complex square root to avoid postscaling of the result. A combined recurrence algorithm is generalized and a scalable hardware architecture is proposed. Designs with different operand precision are implemented in Altera Stratix-II FPGA and cost and performance are evaluated and compared with reference designs of complex division or square root implemented combined or separately. The results show advantages of the proposed combined design in cost and performance.

Photon mapping is a popular technique for high-quality image rendering. Compared to other global illumination techniques, it has promising potential to be accelerated towards real-time. In this paper we study the possibility of using application-specific accelerators for two key operations used in photon mapping: a tree search operation and a shader operation. The accelerators are implemented with online arithmetic to maximize throughput, while still providing practical power and area costs. Results indicate that the accelerators can provide significantly better power consumption versus a parallel implementation, and the overall throughput can be 100× faster than a software-only single-threaded implementation before becoming limited by bandwidth.

We propose algorithms and provide some related results that make it possible to implement decimal floating-point arithmetic on a processor that does not have decimal operators, using the available binary floating-point functions. In this preliminary study, we focus on round-to-nearest mode only. We show that several functions in decimal32 and dec-imal64 arithmetic can be implemented using binary64 and binaryl28 floating-point arithmetic, respectively. We discuss the decimal square root and some transcendental functions. We also consider radix conversion algorithms.

We present a design and implementation of a radix-4 complex division unit with prescaling of the operands. Specifically, we extend the treatment of the residual bound and errors due to the use of truncated redundant representation. The requirements for prescaling tables are simplified and a detailed specification of the table design is given. All principal components used in the design are described and the proposed optimizations are explained. The target platform for implementation was an Altera Stratix II FPGA for which we report timing and area requirements. For a precision of 36 bits, the implementation uses 1185 ALUTs, achieving a latency of 157 ns. The maximum clock frequency is 173.49 MHz.

We present a design of a radix-8 complex division for fixed-point operands suitable for FPGA implementation. The design, consisting of operands' prescaling and digit recurrence, shares logic resources and optimizes the use of 6-input LUTs of FPGA devices for efficient design. An optimized single table for prescaling factors is developed. The design is implemented in Altera Stratix-II FPGA for several operands precisions and compared in cost, latency and power with a design using non-shared resources and with an IP-based design. The results show advantages of the proposed design in cost, delay, and power.

In this paper we extend the domain of applicability of the E-method [7, 8], as a hardware-oriented method for evaluating elementary functions using polynomial and rational function approximations. The polynomials and rational functions are computed by solving a system of linear equations using digit-serial iterations on simple and highly regular hardware. For convergence, these systems must be diagonally dominant. The E-method offers an efficient way for the fixed-point evaluation of polynomials and rational functions if their coefficients conform to the diagonal dominance condition. Until now, there was no systematic approach to obtain good approximations to f over an interval [a, b] by rational functions satisfying the constraints required by the E-method. In this paper, we present such an approach which is based on linear programming and lattice basis reduction. We also discuss a design and performance characteristics of a corresponding implementation.

A hardware-oriented method for evaluating complex polynomials by solving iteratively a system of linear equations is proposed. Its implementation uses a digit-serial iterations on simple and highly regular hardware. The operations involved are defined over the reals. We describe a complex-to-real transform, a complex polynomial evaluation algorithm, the convergence conditions, and a corresponding design and implementation. The latency and the area are estimated for the radix-2 case. The main features of the method are: the latency of about m cycles for an m-bit precision; the cycle time independent of the precision; a design consisting of identical modules; and a digit-serial connections between the modules. The number of modules, each roughly corresponding to serial-parallel multiplier without a carry-propagate adder, is 2(n + I) for evaluating an n-th degree complex polynomial. The method can also be used to compute all successive integer powers of the complex argument with the same latency and a similar implementation cost.

Physics-based animation has enormous potential to improve the realism of interactive entertainment through dynamic, immersive content creation. Despite the massively parallel nature of physics simulation, fully exploiting this parallelism to reach interactive frame rates will require significant area to place the large number of cores. Fortunately, interactive entertainment requires believability rather than accuracy. Recent work shows that real-time physics has a remarkable tolerance for reduced precision of the significant in floating-point (FP) operations. In this paper, we describe an architecture with a hierarchical floating-point unit (FPU) that leverages dynamic precision reduction to enable efficient FPU sharing among multiple cores. This sharing reduces the area required by these cores, thereby allowing more cores to be packed into a given area and exploiting more parallelism.

We present a radix-2 online computational scheme for evaluating multinomials in a fixed-point number representation system. Its main advantage is that it can adapt to any evaluation graph representing the multinomial. Evaluation graphs are efficient representations of multinomials in a factored form. The proposed scheme maps subgraphs of the evaluation graph using linear-system operators. These operators transform the expressions represented by the subgraphs into systems of linear equations. The linear equations are then solved in an online, most-significant-digit-first fashion. The scheme produces, after an initial delay, one output digit per iteration for inputs within range. The iteration time is equal to the sum of the delays of a redundant adder, multiplexer, register and a selection unit and is independent of the size of the multinomial and the precision of the inputs/outputs. The initial delay is proportional to the diameter of the evaluation graph and the maximum number of children of any addition node in the graph. The proposed method lends itself to implementation using simple, highly regular hardware with serial interconnections between modules.

We propose a digit recurrence algorithm for division in real and complex number domains using a variable radix. The objective of the approach is to simplify the prescaling of the operands by using a suitable low radix, and switch to higher radices in the remaining iterations to reduce their number. The prescaling is used to allow a simple quotient digit selection by rounding of the residual. We discuss the algorithm, its implementation, and estimate its time and cost characteristics with respect to fixed high radix division algorithms.

In this paper, we present a library of floating-point arithmetic operators that can be dynamically reconfigured for either real-number or complex-number mode, and for which the precision is variable and is set prior to compilation. The library is compared to corresponding modules built using the Xilinx Alliance CORE library of floating-point arithmetic operators for the implementation of a unit that generates the inverse of a matrix. A significant lower cost and total cycle delay is demonstrated.

We present a high-performance low-power design of linear array multipliers based on a combination of the following techniques: signal flow optimization in [3:2] adder array for partial product reduction, left-to-right leapfrog (LRLF) signal flow, and splitting of the reduction array into upper/lower parts. The resulting upper/lower LRLF (ULLRLF) multiplier is compared with tree multipliers. From automatic layout experiments, we find that ULLRLF multipliers have similar power, delay, and area as tree multipliers for n/spl les/32. With more regularity and inherently shorter interconnects, the ULLRLF structure presents a competitive alternative to tree structures in the design of fast low-power multipliers implemented in deep submicron VLSI technology.

An architecture for the computation of logarithm, exponential, and powering operations is presented in this paper, based on a high-radix composite algorithm for the computation of the powering function (X/sup Y/). The algorithm consists of a sequence of overlapped operations: 1) digit-recurrence logarithm, 2) left-to-right carry-free (LRCF) multiplication, and 3) online exponential. A redundant number system is used and the selection in 1) and 3) is done by rounding except from the first iteration, when selection by table look-up is necessary to guarantee the convergence of the recurrences. A sequential implementation of the algorithm, with a control unit which allows the independent computation of logarithm and exponential, is proposed and the execution times and hardware requirements are estimated for single and double-precision floating-point computations. These estimates are obtained for radices from r=8 to r=1,024, according to an approximate model for the delay and area of the main logic blocks and help determining the radix values which lead to the most efficient implementations: r=32 and r=128.

We propose a split array multiplier organized in a left-to-right leapfrog (LRLF) structure with reduced delay compared to conventional array multipliers. Moreover, the proposed design shows equivalent performance as tree multipliers for n/spl les/32. An efficient radix-4 recoding logic generates the partial products in a left-to-right order. The partial products are split into upper and lower groups. Each group is reduced using [3:2] adders with optimized signal flows and the carry-save results from two groups are combined using a [4:2] adder. The final product is obtained with a prefix adder optimized to match the non-uniform arrival profile of the inputs. Layout experiments indicate that upper/lower split multipliers have slightly less area and power than optimized tree multipliers while keeping the same delay for n/spl les/32.

A high-radix composite algorithm for the computation of the powering function (X/sup Y/) is presented. The algorithm consists of a sequence of overlapped operations: (i) digit-recurrence logarithm, (ii) left-to-right carry-free (LRCF) multiplications, and (iii) online exponential. A redundant number system is used, and the selection in (i) and (iii) is done by rounding except from the first iteration, when selection by table look-up is necessary to guarantee the convergence of the recurrences. A sequential implementation of the algorithm is proposed, and the execution times and hardware requirements are estimated for single and double-precision floating-point computations, for radix r=128, showing that powering can be computed with similar performance as high-radix CORDIC algorithms.

We present a performance-driven programmable logic array mapping algorithm (PLAmap) for complex programmable logic device architectures consisting of a large number of PLA-style logic cells. The primary objective of the algorithm is to minimize the depth of the mapped circuit. We also develop several techniques for area reduction, including threshold control of PLA fanouts and product terms, slack-time relaxation, and PLA packing. We compare PLAmap with a previous algorithm TEMPLA (Anderson and Brown 1998) and a commercial tool Altera Multiple Array MatriX (MAX) + PLUS II (Altera Corporation 2000) using Microelectronics Center of North Carolina (MCNC) benchmark circuits. With a relatively small area overhead, PLAmap reduces circuit depth by 50% compared to TEMPLA and reduces circuit delay by 48% compared to MAX + PLUS II v9.6.

A high-radix digit-recurrence algorithm or the computation of the logarithm is presented in this paper. Selection by rounding is used in iterations j/spl ges/2, and selection by table in the first iteration is combined with a restricted digit-set for the second one, in order to guarantee the convergence of the algorithm. A sequential architecture is proposed. and the execution time and hardware requirements of this architecture are estimated, for a target precision of n=32 bits and a radix r=256. These estimates are obtained according to a rough model for the delay and area cost of the main logic blocks employed, and show the achievement of a speed-up by over 4 times with regard to a conventional radix-2 implementation with redundant arithmetic.

An analysis of the tradeoffs between area and speed for a sequential implementation of a high-radix recurrence for logarithm computation is presented in this paper The high-radix algorithm is outlined and a sequential architecture is proposed, with the use of selection by rounding of the digits and redundant representation. Estimates of the execution time and total area are obtained for n = 16, 32 and 64 bits of precision and for radix values from r = 8 to r = 1024. An analysis of the tradeoffs between area and speed is presented, showing that the most efficient implementations are obtained for radices r = 256 for 16, 32 bit and r = 128 for 64 bit computations.

In this paper we present a performance-driven mapping algorithm, PLAmap, for CPLD architectures which consist of a large number of PLA-style logic cells. The primary goal of our mapping algorithm is to minimize the depth of the mapped circuit. Meanwhile, we have successfully reduced the area of the mapped circuits by applying several heuristic techniques, including threshold control of PLA fanouts and product terms, slack-time relaxation, and PLA-packing. We compare our PLAmap with a recently-published algorithm TEMPLA [1] and a commercial tool, Altera's MAX+PLUS II [16]. Experimental results on various MCNC benchmarks show that overall TEMPLA uses 8 to 11% less area at the cost of 96 to 106% more mapping depth, and MAX+PLUS II uses 12% less area but 58% more delay compared with our mapper.

We present a project to design, implement and use online arithmetic (M.D. Ercegovac and T. Lang, 1988) modules for reconfigurable hardware suitable for signal processing tasks. The project involves: (i) design, implementation and evaluation of a library of parameterized macros for primitive and composite/variable precision arithmetic (Underground); (ii) development of a high-level design environment for facilitating design of FPGA-oriented arithmetic-intensive structures (BigSky); and (iii) experiments with the system.

The development of communications services for distributed applications that are both well-structured (layered) and efficient can be difficult. This paper presents a C++ framework which promotes the development of reusable components that can be combined to implement communications services. These flexible services can be built without incurring an unacceptable performance cost. The basic abstractions in the framework are presented, followed by a discussion of more specific services for unstructured binary messages. Then, the performance impact of the framework is analyzed using a simple test application. The framework is shown to have a minimal overhead that is independent of message size.

The aim of this paper is to accelerate division, square root, and square root reciprocal computations when the Goldschmidt method is used on a pipelined multiplier. This is done by replacing the last iteration by the addition of a correcting term that can be looked up during the early iterations. We describe several variants of the Goldschmidt algorithm, assuming 4-cycle pipelined multiplier, and discuss obtained number of cycles and error achieved. Extensions to other than 4-cycle multipliers are given. If we call G/sub m/ the Goldschmidt algorithm with m iterations, our variants allow us to reach an accuracy that is between that of G/sub 3/ and that of G/sub 4/, with a number of cycle equal to that of G/sub 3/.

This paper deals with the computation of reciprocals, square roots, inverse square roots, and some elementary functions using small tables, small multipliers, and, for some functions, a final "large" (almost full-length) multiplication. We propose a method, based on argument reduction and series expansion, that allows fast evaluation of these functions in high precision. The strength of this method is that the same scheme allows the computation of all these functions. We estimate the delay, the size/number of tables, and the size/number of multipliers and compare with other related methods.

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.

Many modern multimedia applications such as image and video processing are characterized by a unique combination of arithmetic and computational features: fixed-point arithmetic, a variety of short data types, high degree of instruction-level parallelism, strict timing constraints, and high computational requirements.Computationally intensive algorithms usually boost device's power dissipation which is often key to the efficiency of many communications and multimedia applications.Although recently virtually all general-purpose processors have been equipped with multiprecision operations, the current generation of behavioral synthesis tools for application-specific systems does not utilize this power/performance optimization paradigm.In this paper, we explore the potential of using multiple precision arithmetic units to effectively support synthesis of low-power application-specific integrated circuits.We propose a new architectural scheme for collaborate addition of sets of variable precision data.We have developed a novel resource allocation and computation assignment methodology for a set of multiple precision arithmetic units.The optimization algorithms explore the trade-off of allocating low-width bus structures and executing multiple-cycle operations.Experimental results indicate strong advantages of the proposed approach.

This paper presents on-line arithmetic structures tailored for use in the FFT and DCT. Due to their small size, several of these modules can be connected together to form larger, more powerful blocks. The digit-serial nature of on-line arithmetic allows valuable pin resources to feed a larger number of arithmetic units than in the conventional case. Additionally, the resolution of the most significant digit first a property of on-line arithmetic allows subsequent calculations to occur at a much earlier stage. As such, performance of the FFT and DCT benefit over conventional and traditional digit-serial FPGA implementations.

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.

Modern image and video processing applications are characterized by a unique combination of arithmetic and computational features: fixed point arithmetic, a variety of short data types, high degree of instruction-level parallelism, strict timing constraints, high computational requirements, and high cost sensitivity. The current generation of behavioral synthesis tools does not address well this type of application. In this paper we explore the potential of using multiple precision arithmetic units to effectively support implementation of image and video processing applications as application specific integrated circuits. A new architectural scheme for collaborate addition of sets of variable precision data is proposed as well as an allocation and assignment methodology for multiple precision arithmetic units. Experimental results indicate the strong advantages of the proposed approach.

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.

We investigate variable-precision classification (VPC) for speeding vector quantization (VQ). VPC evaluates bit-serially, from the most significant bit. When the magnitude of the error due to the unevaluated bits is less than the absolute magnitude of the discriminant, we can classify without processing the remaining bits. A proof shows that as the operand precision increases, the average necessary precision becomes asymptotically independent of the operand precision, VPC makes the complexity of the L(2) norm equivalent to the L(1) norm. In VQ of real images, on average, the codevector element's precision necessary for classification was under four bits. We implemented binary classification circuitry using VPC and conventional approaches. The key modules were designed and their performance estimated assuming 1.0-mum gate array technology. The implementations could search binary pruned trees at the television quality video rate. When the overall execution time is important, VPC more than halves the computational complexity.

We present an approach to reducing the average number of signal transitions (T,,) in the design of sign-detection and comparison of magnitudes. Our approach reduces T/sub av/ from 21n/8 (n-operand precision in bits) to 4.5 in the case of iterative implementation, and from about n to roughly k+n/2/sup k-1/ in the tree network implemented with k-bit modules. We also discuss comparison of small numbers. The approach is applicable to other arithmetic problems.>

A division algorithm in which the quotient-digit selection is performed by rounding the shifted residual in carry-save form is presented. To allow the use of this simple function, the divisor (and dividend) is prescaled to a range close to one. The implementation presented results in a fast iteration because of the use of carry-save forms and suitable recodings. The execution time is calculated and several convenient values of the radix are selected. Comparison with other dividers for radices 2/sup 9/ to 2/sup 18/ is performed using the same assumptions.>

A division algorithm in which the quotient-digit selection is performed by rounding the shifted residual in carry-save form is presented. To allow the use of this simple function, the divisor (and dividend) is prescaled to a range close to one. The implementation presented results in a fast iteration because of the use of carry-save forms and suitable recodings. The execution time is calculated, and several convenient values of the radix are selected. Comparison with other high-radix dividers is performed using the same assumptions.>

The flexibility of field programmable gate arrays (FPGAs) can provide arithmetic-intensive programs with the benefits of custom hardware but without the high cost of custom silicon implementations. Efficient mappings are key to fast arithmetic implementations on FPGAs. A process for developing such mappings with lookup table based FPGAs is explored. The development process is illustrated with SRT division and the Xilinx XC4010 FPGA. With this mapping process a linear sequential array design that avoids the common problem of large fanout delay in the critical path is created. This approach has a cycle time that is independent of precision, yet it requires approximately the same number of logic blocks as a conventional implementation.>

The design of MAMACG, a software tool for automatically mapping an important class of matrix algorithms into mesh array computational graphs, is described. MAMACG is a concrete realization of the multimesh graph (MMG) method, implemented in Elk, a dialect of LISP with built-in X-graphics capabilities.>

In vector quantization (VQ) with fast search techniques, the storage available limits the number of codevectors used in VQ. Variable precision representation (VPR) is a simple codebook compression scheme. VPR for each vector y stores the number e(y), the number of leading bits which are zero in all elements, and avoids storing those leading bits. When storing the difference of codevectors in a binary tree structured VQ codebook, VPR can save from 24% to 44% in storage. Storing the codevector difference removes the redundancy between similar codevectors. Also as the mean square error of the VQ encoder is lowered, on the average, the difference becomes smaller and yields to better compression. To process vectors in VPR format, the operator uses a bit-serial, element-parallel scheme to evaluate the inner product. The operator's throughput can be increased by replicating its core.>

In implementations of operations based on digit-recurrence algorithms such as division, left-to-right multiplication and square root, the result is obtained in digit-serial form, from most significant digit to least significant. To reduce the complexity of the result-digit selection and allow the use of redundant addition, the result-digit has values from a signed-digit set. As a consequence, the result has to be converted to conventional representation, which can be done on-the-fly as the digits are produced, without the use of a carry-propagate adder. The authors describe three ways to modify this conversion process so that the result is rounded. The resulting operation is fast because no carry-propagate addition is needed. The schemes described apply also to online arithmetic operations.>

A scheme for the singular value decomposition (SVD) problem, based on online arithmetic, is discussed. The design, using radix-2 floating-point online operations, implemented in the LSI HCMOS gate-array technology, is compared with a compatible conventional arithmetic implementation. The preliminary results indicate that the proposed online approach achieves a speedup of 2.4-3.2 with respect to the conventional solutions, with 1.3-5.5 more gates and more than 6 times fewer interconnections.>

Several modifications to the CORDIC method of computing angles and performing rotations are presented: (1) the use of redundant (carry-free) addition instead of a conventional (carry-propagate) one; (2) a representation of angles in a decomposed form to reduce area and communication bandwidth; (3) the use of on-line addition (left-to-right, digit-serial addition) to replace shifters by delays; and (4) the use of online multiplication, square root, and division to compute scaling factors and perform the scaling operations. The modifications improve the speed and the area of CORDIC implementations. The proposed scheme uses efficiently floating-point representations. The application of the modified CORDIC method to matrix triangularization by Givens' rotations and to the computation of the singular value decomposition (SVD) are discussed.>

A systematic derivation of a radix-4 square-root algorithm using redundant residual and result is presented. Unlike other similar schemes it does not use a table lookup or PLA for the initial step, resulting in a simpler implementation without any time penalty. The scheme can be integrated with division and incorporates an on-the-fly conversion and rounding of the result, thus eliminating a carry-propagate step to obtain the final result. The result-digit selection uses 3 bits of the result and 7 bits of the estimate of the residual.>

A radix-4 division algorithm with operands scaling is proposed. The algorithm uses a recurrence with redundant addition (carry-save or signed-digit) and combines simple scaling with a quotient-selection function that depends only on the estimate of the partial remainder and is independent of the divisor. The scheme results in a significant speedup with respect to both the radix-2 and radix-4 without scaling.>

Conventional schemes for fast multiplication accumulate the partial products in redundant form (carry-save or signed-digit) and convert the result to conventional representation in the last step. This step requires a carry-propagate adder which is comparatively slow and occupies a significant area of the chip in a VLSI implementation. A report is presented on a multiplication scheme (left-to-right, carry-free, LRCF) that does not require this carry-propagate step. The LRCF scheme performs the multiplication most-significant bit first and produces a conventional sign-and-magnitude product (most significant n bits) by means of an on-the-fly conversion. The resulting implementation is fast and regular and is very well suited for VLSI. The LRCF scheme for general radix r and a radix-4 signed-digit implementation are presented.>

An online multiply-add module that allows high filter sampling rates when used to implement the direct form II second-order filter structure is described. Important characteristics of online arithmetic are that it produces most significant digit first and that its digit cycle time is independent of the data wordlength. These features not only permit high-speed filtering, but also allow the elimination of all nonlinear oscillation in the filter without affecting the sampling rate, and effectively eliminate scaling of the filter's input data. The derivation of the online multiply-add algorithm and its hardware design using a 1.5- mu m CMOS standard cell library are presented. A method for eliminating nonlinear oscillations by increasing the filter's working precision is described.>

A systematic derivation of a radix-4 square root algorithm using redundance in the partial residuals and the result is presented. Unlike other similar schemes, the algorithm does not use a table-lookup or programmable logic array (PLA) for the initial step. The scheme can be integrated with division. It also performs on-the-fly conversion and rounding of the result, thus eliminating a carry-propagate step to obtain the final result. The selection function uses 4 b of the result and 8 b of the estimate of the partial residual.>

In division and square root implementation based on digit-recurrence algorithms, the result is obtained in digit-serial form, from most significant digit to least significant. To reduce the complexity of the result-digit selection and to allow the use of redundant addition, the result-digit has values from a signed-digit set. As a consequence, the result has to be converted to conventional representation. This conversion can be done on-the-fly as the digits are produced, without the use of a carry-propagate adder. The authors describe how to modify this conversion process so that the result is rounded. The resulting operation is faster than what is done conventionally because no carry-propagate addition is needed. Three rounding methods that differ in the rounding error and the hardware and time required are described.>

A gate array implementation of a radix-2 floating-point online division algorithm is presented. The design requires 111 equivalent gates per bit and has a cycle time of 24 ns. For 8-b exponent and 24-b mantissa, the design requires 2497 equivalent gates and can fit on an LSI Logic LL9320P chip with a utilization factor 78%.>

A radix-4 divider can potentially achieve a speedup of two with respect to a radix-2 implementation by halving the number of steps. However, the complicated quotient-digit selection function increases the critical path and almost eliminates the speedup. The authors present an implementation of a scheme that scales the divisor close to unity, making the quotient-selection function independent of the divisor. They show a gate-array implementation that achieves a speedup of 1.5 with respect to the radix-2 case, doubling the number of gates. The speedup achieved is still considerably lower than the theoretical maximum of twice.>

An integrated radix-2 on-line algorithm for computing rotation factors for matrix transformations is presented. The inputs and outputs are in parallel form, conventional 2's complement, floating-point representation. The exponents are computed using conventional arithmetic while the significands are processed using on-line algorithms. The conventional result is obtained by using an on-the-fly conversion scheme. The rotation factors are computed in 9+n clock cycles for n -bit significands. The clock period is kept small by the use of carry-save adder schemes. The implementation and performance of the algorithm are discussed.

We present an on-line algorithm for radix-4 floating point division. The divisor is first transformed in to a range such that the quotient digits are computed as a function of the scaled partial remainder only.

An algorithm to convert redundant number representations into conventional representations is presented. The algorithm is performed concurrently with the digit-by-digit generation of redundant forms by schemes such as SRT division. It has a step delay roughly equivalent to the delay of a carry-save adder and simple implementation. The conversion scheme is applicable in arithmetic algorithms such as nonrestoring division, square root, and on-line operations in which redundantly represented results are generated in a digit-by-digit manner, from most significant to least significant.

A division algorithm with a simple selection of quotient digits including prediction is possible if the divisor is restricted to a suitable range. The conditions that the divisor must satisfy to have the quotient digit qi+1predicted while computing Ri+1are determined. Some implementation considerations are also given.

A functional (applicative) hardware description language (FHDL), capable of dealing with both the sequential and combinational systems is discussed. The language supports multi-level executable specifications and interpretation of functional specifications as implementations at a given level of primitives. That is, the FHDL specifications are symbolically interpreted to produce structural representations (implementations) of hardware algorithms. The symbolic interpreter presently implements the specification of hardware algorithms at the gate level. The FHDL allows definition of function attributes, such as delay and number of logic level so that the performance characteristics of implementations can be obtained during simulation.

Binary tree network architectures are applicable in the design of hierarchical computing systems and in specialized high-performance computers. In this correspondence, the reliability and fault tolerance issues in binary tree architecture with spares are considered. Two different fault-tolerance mechanisms are described and studied, namely: 1) scheme with spares; and 2) scheme with performance degradation. Reliability analysis and estimation of the fault-tolerant binary tree structures are performed using the interactive ARIES 82 program. The discussion is restricted to the topological level, and certain extensions of the schemes are also discussed.

A higher-radix division algorithm with simple selection of quotient digits is described. The proposed scheme is a combination of the multiplicative normalization used in the continued-product algorithms and the recursive division algorithm. The scheme consists of two parts: in the first part, the divisor and the dividend are transformed into the range which allows the quotient digits to be selected by rounding partial remainders to the most significant radix-r digit in the second part. Since the selection requires only the most significant part of the partial remainder, limited carry-propagation adders can be used to form the partial remainders. The divisor and dividend transformations are performed in three steps using multipliers of the form 1 + skr−kas in the continued product algorithm. The higher radix of the form r = 2k, k=2,4,8,…, can be used to reduce the number of steps while retaining the simple quotient selection rules.

In this article we describe a derivation and an algorithm for on-line multiplicative normalization of fractions. The algorithm is a variation of the continued product normalization algorithm and it is used for on-line evaluation of elementary functions.

The properties of redundant number system in significand (mantissa) representation are studied and the range of redundant significand is derived. From the range of the redundant significand and the absolute error of on-line operations, the MRRE (maximum relative representation error) is defined and analyzed for floating-point on-line addition and multiplication.

In this correspondence a systematic derivation of an on-line square root algorithm is presented. The algorithm operates on variables represented in the normalized radix r floating-point system in a digit-by-digit fashion with an on-line delay of 1. The approach used in deriving the square root algorithm is described in detail. The basic characteristics of hardware-level implementation are also discussed.

A gate level design of a digit-slice on-line arithmetic unit is presented. This unit is designed as a set of basic modules, Processing Elements (PE), each of which operates on a single digit of the operands and the results. It is capable of executing four basic operations of addition/subtraction, multiplication and division in an on-line manner. The results are generated during the digit-serial input of the operands, beginning always with the most significant digit. A general (with respect to radix) analysis of the cost and speed of the proposed unit is also given.

On-line arithmetic is a special class of serial arithmetic where algorithms produce results with the most significant digit first during the serial input of the operands. Speedup of computations can be achieved by overlapping or pipelining successive operations with small delays. This paper describes the design and implementation of a simulator for on-line arithmetic algorithms. The simulator was designed primarily to serve as 1) an experimental tool for synthesis of on-line algorithms; 2) a performance evaluation tool of on-line arithmetic; 3) an on-line calculator in solving some problems involving linear and non-linear recurrences. The simulator evaluates arithmetic expressions given in a highly functional form. Presently, the set of operations supported include addition, subtraction, multiplication, division, and square root. Several examples are presented in this paper to illustrate the usage of the simulator. The simulator package is implemented in ‘C’ language on a VAX 11/780 system.

For effective application of on-line arithmetic to practical numerical problems, floating-point algorithms for on-line addition/subtraction and multiplication have been implemented by introducing the notion of quasi-normalization. Those proposed are normalized fixed-precision FLPOL (floating-point on-line) algorithms.

The properties of redundant number system in mantissa representation are studied and the range of the redundant mantissa is derived. From the range of the mantissa and the absolute error of on-line operations, the MRRE (maximum relative representation error) is defined and analyzed for redundant floating-point numbers.

An on-line algorithm for computing square roots in a radix 2, normalized floating-point number system with the redundant digit set {-1, 0, 1} is described. The algorithm has on-line delay of one and it is amenable for modular implementation. A systematic approach, used in deriving this algorithm, is presented in detail.

The organization and design of an arithmetic module (Basic Byte-Slice Module - BBM) is presented. A network of BBM's implements an efficient digit-by-digit method for fast evaluation of polynomial and rational functions. Verification of the BBM design, its feasibility in present LSI technologies and its performance are discussed. The proposed BBM is characterized by a small number of input/output terminals, a uniform internal structure, and simple control and inter-module communication requirements.

A parallel computational method, amenable for efficient hardware-level implementation, is described. It provides a simple and fast algorithm for the evaluation of polynomials, certain rational functions and arithmetic expressions, solving a class of systems of linear equations, or performing the basic arithmetic operations in a fixed-point number representation system. The time required to perform the computation is of the order of m carry-free addition operations, m being the number of digits in the solution. In particular, the method is suitable for fast evaluation of mathematical functions in hardware.

In this paper, on-line algorithms for division and multiplication are developed. It is assumed that the operands as well as the result flow through the arithmetic unit in a digit-by-digit, most significant digit first fashion. The use of a redundant digit set, at least for the digits of the result, is required.

This paper presents a recently discovered general computational method, amenable for efficient implementation in digital computing systems. The method provides a unique, simple and fast algorithm for solving many computational problems, such as the evaluation of polynomials, rational functions and arithmetic expressions, or solving a class of systems of linear equations, or performing the basic arithmetics. In particular, the method, is well suited for fast evaluation of commonly used, mathematical functions.

In this paper we are considering problems of division and multiplication in a computational environment in which all basic arithmetic algorithms satisfy "on-line" property: to generate jthdigit of the result it is necessary and sufficient to have argument(s) available up to the (j+δ)th digit, where the index difference 6 is a small positive constant. Such an environment, due to its potential to perform a sequence of operations in an overlapped fashion, could conveniently speed up an arithmetic multiprocessor structure or it could be useful in certain real-time applications, with inherent on-line properties. The on-line property implies a left-to-right digit-by-digit type of algorithm and consequently, a redundant representation, at least, of the results. For addition and subtraction such algorithms, satisfying on-line property, can be easily specified. Multiplication requires a somewhat more elaborate approach and there are several possible ways of defining an on-line algorithm. However, the existence of an on-line division algorithm is not obvious and its analysis appears interesting.

This paper describes a family of algorithms for evaluation of a class of elementary functions including division, logarithms, and exponentials. The main objective is to demonstrate the feasibility of higher radix implementations, in particular, radix 16, and to compare performance with radix 2. The emphasis is not on optimality of a single algorithm, but rather on the optimality of a class of algorithms. An attempt to implement a much wider class of functions than is presently done in arithmetic units is encouraged by the current level of digital technology and the existence of suitable algorithms. Besides the definitions of the algorithms, which are based on continued products and continued sums, details related to implementation are discussed.

This paper describes an approach for obtaining a class of similar algorithms for evaluation of some elementary functions. The main objective is to show feasibility of higher radix implementations, in particular radix 16, as they offer better performance than radix 2. The emphasis is not on optimality of a single algorithm but rather on the optimality of the whole class of algorithms. An attempt to implement a much wider class of functions than is done in conventional arithmetic units, would be encouraged by the present level of technology and by the existence of suitable algorithms. Besides the definitions of the algorithms, which are based on continued products (sums), some details related to implementation are discussed.