Search

A parallel decimal multiplier with improved performance is proposed in this paper by exploiting the properties of three different binary coded decimal (BCD) codes, namely the redundant BCD excess-3 code (XS-3), the overloaded decimal digit set (ODDS) code and the BCD-4221/5211 code. The signed-digit radix-10 recoding is used to recode the BCD multiplier to the digit set [-5, 5] from [0, 9]. The redundant BCD XS-3 code is adopted to generate the multiplicand multiples in a carry-free manner. The XS-3 coded partial products (PPs) are converted to ODDS PPs to fit binary partial product reduction (PPR). In this paper, a regular decimal PPR tree using ODDS and BCD-4221/5211 codes is proposed; it consists of a binary PPR tree block, a non-fixed size BCD-4221 counter block and a BCD-4221/5211 PPR tree block. The decimal carry-save algorithm based on BCD-4221/5211 is used in the PPR tree to obtain high performance multipliers. Moreover, an improved PPG circuit and an improved parallel prefix/carry-select decimal adder are proposed to further improve the performance of the proposed multipliers. Analysis and comparison using the 45 nm technology show that the proposed decimal multipliers are faster and require less hardware area than previous designs found in the technical literature. [ABSTRACT FROM PUBLISHER]

In this paper, we develop a segment tree data structure for solving dynamic table lookup problems. The proposed dynamic segment tree (DST) uses all of the distinct end points of ranges as the keys based on a new range end point scheme. The new end point scheme generates fewer end points than the traditional end point scheme. DST is implemented as a balanced binary search tree augmented with a range set in each mode. The performance of accessing and updating the ranges stored in each node is improved by an efficient range set data structure that combines the priority queue and the interval tree. Based on the proposed data structures, the time complexities of search, insertion, and deletion in a set of N arbitrary ranges are O(logN), O(logN × log Max), and O(Max × logN × log Max), respectively, where Max is the maximum number of ranges covering any address. In practical routing tables, Max is a small constant (six for the routing tables we tested). The memory requirement for DST is O(N log N). The experimental results using real Internet Protocol version 4 (lPv4) routing tables show that both the OST and prefix binary tree on binary tree (PBOB) by Lu et al. (2004) perform much better than the multiway range tree (MRT) by Warkhede et al. (2004) and prefix in B-tree (PIBT) by Lu et al. (2005) in terms of update speed and memory consumption, but DST performs much better than PBOB and a little slower than MRT and PIBT in terms of search speed. [ABSTRACT FROM AUTHOR]

In this work, we present a radix-10 division unit that is based on the digit-recurrence algorithm. The previous decimal division designs do not include recent developments in the theory and practice of this type of algorithm, which were developed for radix-2k dividers. In addition to the adaptation of these features, the radix-10 quotient digit is decomposed into a radix-2 digit and a radix-5 digit in such a way that only five and two times the divisor are required in the recurrence. Moreover, the most significant slice of the recurrence, which includes the selection function, is implemented in radix-2, avoiding the additional delay introduced by the radix-10 carry-save additions and allowing the balancing of the paths to reduce the cycle delay. The results of the implementation of the proposed radix-10 division unit show that its latency is close to that of radix-16 division units (comparable dynamic range of significands) and it has a shorter latency than a radix-10 unit based on the Newton-Raphson approximation. [ABSTRACT FROM AUTHOR]