Search

© 2015 Springer Science+Business Media New York Many circuit design applications rely on an intermediate sequence to carry a decision to the next circuit stage. The decision may be carried by a weighted pattern of N bits, with the weights being selected in a way that optimizes the circuit implementation or some aspect of performance. For example, when the weights are consecutive powers of 2 beginning with 1 = 20, we have the standard binary representation. As another example, when all the weights are 1, we have the unary representation that encodes a value k by k asserted bits and N–k unasserted bits (a weight-k bit vector of length N). In this paper, we present the design of a circuit that screens a unary representation to verify that the represented value falls between preset lower and upper limits l and u, passing through any string that represents a value in the interval [l, u] and outputting the all-0 s bit pattern otherwise. Our mixed analog–digital circuit implementation, based on switched-capacitor arrays, provides a decision output within a clock cycle of 4 ns for 16-bit unary representation, when realized with 0.15 μm TSMC technology. The latter results were obtained with normal, per-bit capacitance of 200 fF and single-clock-cycle operation. As an added benefit, our filtering circuit can form the basis for designing a cost-effective Hamming decoder circuit.

Balanced ternary number representation and arithmetic, based on the symmetric radix-3 digit set {-1, 0, +1}, has been studied at various times in the history of computing. Among established advantages of balanced ternary arithmetic are representational symmetry, favourable error characteristics and rounding by truncation. In this study, we show an additional advantage: that of lower-error truncated multiplication with the same relative cost reduction as in truncated binary multipliers.

The hypercubic family of interconnection networks, encompassing the hypercube and its derivatives and variants, has a wide range of applications in parallel processing. Various problems in general complex networks can be addressed by choosing a hypercubic network as a skeleton. In this paper, we provide insight into why hypercubic networks are suitable as network skeletons and discuss a mapping scheme to take advantage of the symmetry of such networks for developing efficient algorithms.

Amdahl's performance law is a useful conceptual and pedagogical tool for imparting key ideas about performance limits and the importance of balanced system design to students and practitioners in the field. The weakest-link maxim of reliability engineering can be expressed in terms of an identical formula, giving it a quantitative basis and thus making it more convincing. Calling it 'Amdahl's reliability law' stresses the fact that it follows directly from Amdahl's speedup formula.

We present a new comparator design featuring wide-range and high-speed operation using only conventional digital CMOS cells. Our comparator exploits a novel scalable parallel prefix structure that leverages the comparison outcome of the most significant bit, proceeding bitwise toward the least significant bit only when the compared bits are equal. This method reduces dynamic power dissipation by eliminating unnecessary transitions in a parallel prefix structure that generates the N-bit comparison result after [log 4N]+[log16N]4 CMOS gate delays. Our comparator is composed of locally interconnected CMOS gates with a maximum fan-in and fan-out of five and four, respectively, independent of the comparator bitwidth. The main advantages of our design are high speed and power efficiency, maintained over a wide range. Additionally, our design uses a regular reconfigurable VLSI topology, which allows analytical derivation of the input-output delay as a function of bitwidth. HSPICE simulation for a 64-b comparator shows a worst case input-output delay of 0.86 ns and a maximum power dissipation of 7.7 mW using 0.15-μ TSMC technology at 1 GHz. © 2012 IEEE.

The existence of parallel node-disjoint paths between any pair of nodes is a desirable property of interconnection networks, because such paths allow tolerance to node and/or link failures along some of the paths, without causing disconnection. Additionally, node-disjoint paths support high-throughput communication via the concurrent transmission of parts of a message. We characterize maximum-sized families of parallel paths between any two nodes of alternating group networks. More specifically, we establish that in a given alternating group network AN n , there exist n−1 parallel paths (the maximum possible, given the node degree of n−1) between any pair of nodes. Furthermore, we demonstrate that these parallel paths are optimal or near-optimal, in the sense of their lengths exceeding the internode distance by no more than four. We also show that the wide diameter of AN n is at most one unit greater than the known lower bound D+1, where D is the network diameter.

We observe that recruitment efforts aimed at alleviating the shortage of skilled workforce in computer engineering must be augmented with strategies for retaining and motivating the students after they have enrolled in our educational programmes. At the University of California, Santa Barbara, we have taken a first step in this direction by offering a required freshman seminar entitled "Ten Puzzling Problems in Computer Engineering". This one-unit pass/not-pass gateway course, which is graded based solely on attendance, introduces our students to some of the most challenging problems faced by computer engineers in their daily professional endeavors and at the frontiers of research. To accomplish this feat in a manner that is both understandable and appealing to freshmen, the problems are related to popular mathematical and logical puzzles. Each 1-hour class session begins by introducing the students to puzzles of a particular kind and letting them participate in formulating solutions. Historical context, background, and general solution methods for the puzzles are then discussed by the instructor, who finally proceeds to demonstrate how the puzzles and their solution strategies are related to real technical challenges in computer engineering. The new course, which has been offered twice already, is supported by a website containing complete lecture slides, class handouts, and reference information. (Contains 1 note, 1 table, and 11 figures.)

New counting-based methods for comparing the Hamming weight of a binary vector with a constant, as well as comparing the Hamming weights of two input vectors, are proposed. It is shown that the proposed comparators are faster and simpler, both in asymptotic sense and for moderate vector lengths, compared with the best available fully digital designs. These speed and cost advantages result from a more efficient population counting, as well as the merger of counting and comparison operations, via accumulative and up/down parallel counters. Index Terms--Column compression, comparator, Hamming distance, multioperand addition, parallel counter, population count.

The pruning schemes are described using a general algebraic construction based on commutative groups. The results have provided a general framework for synthesizing and exploring pruned interconnection networks that offer lower node degrees.

The various routing algorithms for perfect difference networks (PDNs) are demonstrated. The results state that algorithms developed for a complete network can be emulated by optimal slowdown on a PDN of the same size.

The network architecture in its basic and bipartite forms is presented and it is shown how the related multidimensional perfect difference networks (PDNs) can be derived. It is concluded that PDNs and their derivates constitute worthy additions to the repertoire of network designers and may offer additional design points that can be exploited by current and emerging technologies including wireless and optical interconnects.

We introduce the notion of two-valued digit (twit) as a binary variable that can assume one of two different integer values. Posibits, or simply bits, in {0, 1} and negabits in {--1, 0}, commonly used in two's-complement representations and (n, p) encoding of binary signed digits, are special cases of twits. A weighted bit-set (WBS) encoding, which generalizes the two's-complement encoding by allowing one or more posibits and/or negabits in each radix-2 position, has been shown to unify many efficient implementations of redundant number systems. A collection of equally weighted twits, including ones with noncontiguous values (e.g., {--1, 1} or {0, 2}), can lead to wider representation range without the added storage and interconnection costs associated with multivalued digit sets. We present weighted twit-set (WTS) encodings as a generalization of WBS encodings, examine key properties of this new class of encodings, and show that any redundant number system (e.g., generalized signed-digit and hybrid-redundant systems), including those that are based on noncontiguous and/or zero-excluded digit sets, is faithfully representable by WTS encoding. We highlight this broad coverage by a tree chart having WTS representations at its root and various useful redundant representations at its many internal nodes and leaves. We further examine how highly optimized conventional components such as standard full/half-adders and compressors may be used for arithmetic on WTS-encoded operands, thus allowing highly efficient and VLSI-friendly circuit implementations. For example, focusing on the WBS-like subclass of WTS encodings, we describe a twit-based implementation of a particular stored-transfer representation which offers area and speed advantages over other similar designs based on WBS and hybrid-redundant representations. Index Terms--Arithmetic unit, carry-free addition, computer arithmetic, digit set, hybrid redundancy, number representation, redundant number system, signed-digit number system, stored-transfer representation, weighted bit-set (WBS) encoding.