Design of Parallel Prefix Tree Based High Speed Scalable CMOS Comparator for converters

DOI : 10.17577/IJERTV3IS031783

Download Full-Text PDF Cite this Publication

Text Only Version

Design of Parallel Prefix Tree Based High Speed Scalable CMOS Comparator for converters

1 M. Gokilavani 2 P. Niranjana Devi 3 M. R. Shri Suvega

PG Scholar, Department of ECE, Indus College of Engineering, Coimbatore, India.

PG Scholar, Department of ECE, Akshaya College of

Engineering and Technology, Coimbatore, India.

PG Scholar, Department of ECE, Akshaya College of

Engineering and Technology, Coimbatore, India.

Abstract Comparator is a major fundamental element is most digital circuits. Energy efficient and high speed operation of comparators is needed for high speed digital circuits. Proposed 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. The proposed comparator design provides wide- range and high-speed operation using only conventional digital CMOS cells. This comparator design consists of maximum fan-in of five and maximum fan-out of four CMOS gates irrespective of the comparator bit-width which is a major benefit while scaling this design to higher bit-width operations. The main advantages of this design are high speed and power efficiency, maintained over a wide range. ModelSim simulation for a 16-b comparator shows a worst case input-output delay of 8.001 ns and a maximum power dissipation of 83 mW at 1GHz.

KeywordsCMOS comparator, digital circuit, higher bit- width, high fan-in, high fan-out, parallel prefix tree structure


    A high speed comparator is a very basic and useful arithmetic component of digital systems. Comparators are key design element for a wide range of applications like parallel testing, signature analyzer, built- in self- test measurements, graphics and image/signal processing. The design of high-speed, low power, and area-efficient comparators has received a great deal of attention, since, as is well known, comparison is a fundamental operation in almost all digital processors. Even though comparator logic design is straightforward, the extensive use of comparators in high-performance systems places a great importance on performance and power consumption optimizations. There are several approaches to designing CMOS comparators, each with different operating speed, power consumption, and circuit complexity.

    1. Comparator Designing Approaches

      One can implement the comparator by flattening the logic function directly. This approach is only suitable for comparators with short inputs. For the comparators with longer inputs, circuit complexity increases drastically, and the operating speed is degraded accordingly. Another way to designing the comparator is employing a parallel adder. In this approach, the adder becomes the major factor limiting the operating speed. Other comparator designs improve scalability and reduce comparison delays using a hierarchical prefix tree structure composed of 2-b comparators. These structures require log2 N comparison levels, with each level consisting of several cascaded logic gates. However, the delay and area of these designs may be prohibitive for comparing wide operands.

      To improve the speed and reduce power consumption, several designs rely on pipelining and power- down mechanisms to reduce switching activity with respect to the actual input operands bit values. One design uses all-N transistor (ANT) circuits to compensate for high fan- in with high pipeline throughput. A 64-b comparator requires only three pipeline cycles using a multiphase clocking scheme. However, such a clocking scheme may be unsuitable for high-speed single-cycle processors because of several heavily loaded global clock signals that have high-power transition activity. Additionally, race conditions and a heavily constrained clock jitter margin may make this design unsuitable for wide-range comparators. Other architectures use a multiplexer-based structure to split a 64-b comparator into two comparator stages, the first stage consists of eight modules performing 8-b comparisons and the modules outputs are input into a priority encoder and the second stage uses an 8-to-1 multiplexer to select the appropriate result from the eight modules in the first stage. This architecture uses two-phase domino clocking to perform both stages in a single clock cycle. Since operations occur on the rising and falling clock edges, this further limits the operating speed and jitter margin and makes the design highly susceptible to race conditions.

    2. Parallel Prefix Tree Based Design of Comparator

    To overcome some of the drawback present in the above designs (such as higher power consumption, multicycle computation, unsuitable custom structures for scaling, irregular VLSI structures, and irregular transistor geometry sizes), parallel prefix structure based comparator design provides fast, scalable, wide range, and power efficient algorithm. This architecture is designed with standard CMOS cells.

    Fig. 1. Block diagram of the proposed comparator architecture

    The comparison resolution module is a novel MSB-to- LSB parallel prefix tree structure that performs the bitwise comparison of two N bit operands (A & B) entered into the comparator. The parallel structure encodes the bitwise comparison results to two N bit buses called left bus and right bus. The bitwise comparison of equal bits sets 0 in both the buses. If the bitwise comparison of unequal bits occur, any of the buses (A or B) sets to 1 and the bitwise comparison stops immediately by setting 0 in the remaining bits present in the buses. The decision module produces the result of comparison of the input operands based on the signals from the left and right buses. The possible results from the decision module are (i) both are equal (A= B), (ii) A is greater than B (A>B), (iii) A is lesser than (A<B).

    Fig. 2. An example for 8-bit comparison using parallel prefix tree

    Let the two 8-bit binary numbers be A and B. A = 0101 1101 and B = 0110 1001. In the first step, a parallel prefix tree structure generates the encoded data on the left bus and right bus for each pair of corresponding bits from A and B. In this example, A7 = 0 and B7 = 0 encodes as left7 = right7 = 0, A6 = 1, and B6 = 1 encodes as left6 = right6 = 0, and A5 = 0 and B5 = 1 encodes left5 = 0 and right5=1. At this point, since the bits are unequal, the comparison terminates and a final comparison decision can be made based on the first three bits evaluated. The parallel prefix structure forces all bits of lesser significance on each bus to 0, regardless of the remaining bit values in the operands. In the second step, the OR-networks perform the bus OR- scans, resulting in 0 and 1, respectively, and the final comparison decision is A < B.




    The entire structure is formed with a comparison resolution module along with a decision module. The comparison resolution module of 16-bit comparator design is partitioned into five hierarchical prefixing sets. Each set or group of cells produces outputs that serve as inputs to the next set in the hierarchy, with the exception of set 1, whose outputs serve as inputs to several sets. The decision module is formed with simple OR and NOR gates.

    Set 1 compares the N-bit operands A and B bit-by-bit, using a single level of N -type cells. The -ype cells provide a termination flag Dk to cells in sets 2 and 4, indicating whether the computation should terminate. The

    Fig. 3.Implementation datails of the scalable comparator architecture

    computation function of these cells is described in eqn.1, (where 0 k N 1)

    Set 2 consists of 2-type cells, which combine the termination flags for each of the four -type cells from set 1 (each 2-type cell combines the termination flags of one 4-b partition) using NOR-logic to limit the fan-in and fan- out to a maximum of four. The function produced by these cells is given in equ.2.

    Set 3 consists of 3-type cells, which are similar to

    2-type cells, but can have more logic levels, different inputs, and carry different triggering points. A 3-type cell provides no comparison functionality; the cells sole purpose is to limit the fan-in and fan-out regardless of operand bit width. For 0 m N/4 1, there is a total of N/4 3-type cells per level, with cell function and number of levels given in eqns.3.and 4.

    Set 4 consists of -type cells, whose outputs control the select inputs of -type cells (two-input multiplexors) in set 5, which in turn drive both the left bus and the right bus. For an -type cell and the 4-b partition to which the cell belongs, bitwise comparison outcomes from set 1 provide information about the more significant bits in the cells – type cells, which compute for (0 k N 1), function given in eqn. 5.

    Set 5 consists of N -type cells (two-input, 2-b-wide multiplexers). One input is (Ak, Bk) and the other is hardwired to 00. The select control input is based on the -type cell output from set 4. We define the 2-b as the left-bit code (Ak) and the right-bit code (Bk), where all left-bit codes and all right-bit codes combine to form the

    left bus and the right bus, respectively. The -type cells computation function is described in eqn.6


    Final result of the comparator is produced by the decision module. Thus by feeding the results produced by the left and right buses to the NOR and OR gates of the decision module.

    The result of the decision module as follows:

    1. Left bus = 1 and right bus =0, then A>B.

    2. Left bus = 0 and right bus =1, then B>A.

    3. Left bus = 0 and right bus =0, then A=B.




    Proposed comparator architecture follows the same existing comparator architecture except the additional inverters present in the input and output terminals of the sets used in the comparison resolution module. Logically the functions done by the sets present in the comparison resolution module of both the existing and proposed designs are same. But the proposed comparator design eliminates the use of extra inverters; hence it supports energy efficient operation with improved performance. Ignorence of such inverters in the proposed design reduces the computational complexity, area and power consumption. Also the logic functions done by the logic cells used in the proposed design is easy to understand because of the elimination of the logical inverters. Hence the proposed arcitecture supports all the VLSI features.


    Comparator operations are simulated using ModelSim software and the power, time and area constraints are analyzed with the help the Xilinx software. The comparison results of both designs are tabulted.

    1. Power, Speed and Area Analysis of Existing Design

      Existing design is simulated usind Xilinx software. Comparator is simulated for 1GHz operation. Power, area and timing delay analysis are shown in the following figures.

      Fig. 4. Power consumption of the existing design

      Fig. 5. Input-output delay of the existing design

      Fig. 6. No. of transistors used in the existing design

    2. Power, Speed and Area Analysis of Proposed Design

      Proposed comparator design is simulated inXilinx software. Results for 1GHz operation are shown in the following figures.

      Fig. 7. Power consumption of the proposed design

      Fig. 8. Input-output delay of the proposed design

      Fig. 9. No. of transistors used in the existing design

    3. Comparison of Simulation Results

    Both the existing and proposed designs are simulated and their power, timing and area results are presented. From the simulation results comparison of the existing and proposed designs it is clearly seen that while comparing with the existing design, the proposed design supports low power, high speed and less area operation over a wide range.





    Existing Design

    Proposed Design




    88 mW



    Transistor Count









A new high-speed and low-power comparator architecture is presented which is composed of standard CMOS cells. This architecture eliminates the drawbacks of several existing architectures such as high power consumption, multicycle computation, irregular VLSI structures. From the simulation results it is clearly noted that the proposed architecture provides improved time response and reduced power consumption. Scalin this design into higher bit-width would be very simple because this design uses constant fan-in and fan-out values irrespective of bit-width. Most of the digital systems and signal processing applications require energy efficient, high speed comparators for optimized operation. Similar to comparator analog to digital converter (ADC) is also a fundamental element in digital systems. In future, usage of this high speed comparator in analog to digital converter will improve the performance of the digital systems.


  1. H. Suzuki, C. H. Kim, and K. Roy, (2007) Fast tag comparator using diode partitioned domino for 64-bit microprocessor, IEEE Trans. Circuits Syst. I, vol. 54, no. 2, pp.

  2. D. V. Ponomarev, G. Kucuk, O. Ergin, and K. Ghose, (2004),

    Energy efficient comparators for superscalar datapaths, IEEE Trans. Comput., vol. 53, no. 7, pp. 892904.

  3. C.-C. Wang, P.-M. Lee, C.-F. Wu and H.-L. Wu, (2003) High fan- in dynamic CMOS comparators with low transistor count, IEEE Trans. Circuits Syst. I, vol. 50, no. 9, pp. 12161220.

  4. SN7485 4-bit Magnitude Comparators, Texas Instruments, Dallas, TX, 1999.

  5. C.-H. Huang and J.-S. Wang, (2003) High-performance and power- efficient CMOS comparators, IEEE J. Solid-State Circuits, vol. 38, no. 2, pp. 254262.

  6. H.-M. Lam and C.-Y. Tsui, (2006), High-performance single clock cycle CMOS comparator, Electron. Lett., vol. 42, no. 2, pp. 7577.

  7. M. D. Ercegovac and T. Lang, (1995), Sign detection and comparison networks with a small number of transitions, in Proc. 12th IEEE Symp. Comput. Arithmetic,pp. 5966.

  8. H.-M. Lam and C.-Y. Tsui, (2007), A mux-based high-performance single-cycle CMOS comparator, IEEE Trans. Circuits Syst. II, vol. 54, no. 7, pp. 591595.

  9. S. Perri and P. Corsonello, (2008), Fast low-cost implementation of singleclock- cycle binary comparator, IEEE Trans. Circuits Syst. II, vol. 55, no. 12, pp. 12391243.

  10. F. Frustaci, S. Perri, M. Lanuzza, and P. Corsonello, (2012),

    Energy-efficient single-clock-cycle binary comparator, Int. J. Circuit Theory Appl., vol. 40, no. 3, pp. 237246.

  11. Y. Sheng and W. Wang, (2008), Design and implementation of compression algorithm comparator for digtal image processing on component, in Proc. 9th Int. Conf. Young Comput. Sci., pp. 1337 1341.

  12. B. Parhami, Efficient hamming weight comparators for binary vectors based on accumulative and up/down parallel counters, IEEE Trans.Circuits Syst., vol. 56, no. 2, pp. 167171, Feb. 2009.

  13. J. D. Bruguera and T. Lang, Multilevel reverse most-significant carry computation, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 9, no. 6, pp. 959962, Dec. 2001.

  14. J. Hensley, M. Singh, and A. Lastra, (2005), A fast, energy- efficient z-comparator, in Proc. ACM Conf. Graph. Hardw, pp. 41 44.

  15. J.-Y. Kim and H.-J. Yoo, Bitwise competition logic for compact digital comparator, in Proc. IEEE Asian Solid-State Circuits Conf., Nov. 2007, pp. 5962.

Leave a Reply