## Abstract

The existing design of reversible n-bit binary comparator that compares two n-bit numbers is a serial design [1] having the latency of O(n). In this work, we present a new reversible n-bit binary comparator based on binary tree structure that has the latency of O(log_{2}(n)). The reversible designs are based on a new reversible gate called the TR gate, the improved quantum cost of which is also derived in this work. In the proposed reversible binary tree comparator each node consists of a 2-bit reversible binary comparator that can compare two 2-bit numbers x(x_{i}, x_{i-1}) and y(y_{i}, y_{i-1}), to generate two 1-bit outputs Y and Z. Y will be 1 if x(x_{i}, x_{i-1})> y(y_{i}, y_{i-1}), and Z will be 1 if x(x_{i}, x_{i-1})<y(y_{i}, y _{i-1}). After careful analysis, we modified the logic equations of Y = x_{1}ȳ_{1} + kx_{0}ȳ_{0} and Z = x̄_{1}y_{1} + kx̄_{0}y_{0} to Y = x_{1}ȳ_{1} ⊕ kx_{0}ȳ_{0} and Z = x̄_{1}y_{1} ⊕ kx̄_{0}y_{0}, respectively. The replacement of + operator with ⊕ operator without affecting the functionality of the design helped us in reversible mapping of the equations of Y and Z on the third output of the TR gate which is R=AB̄ ⊕ C. Further, TR gate can also efficiently generate functions such as x_{0}ȳ_{0} and x̄_{0}y_{0}. In the proposed reversible binary comparator, the leaf nodes will consist of 2-bit reversible binary comparators. Each internal node (2-bit reversible binary comparator) of the binary tree receives the partial comparison results from the left and the right children and propagates the 2-bit output of the comparison to its parent. Finally, the root node which is also a 2-bit reversible binary comparator generates the 2-bit result of the comparison of the n-bit numbers x and y to evaluate whether x>y or x<y. The 2-bit result of the root node are passed to the reversible output circuit designed from a Toffoli gate and 4 NOT gates to generate three signals O_{0}(x<y), O_{1}(x>y) and O_{2}(x=y).

Original language | English |
---|---|

Title of host publication | 2010 10th IEEE Conference on Nanotechnology, NANO 2010 |

Pages | 1113-1116 |

Number of pages | 4 |

DOIs | |

State | Published - 2010 |

Event | 2010 10th IEEE Conference on Nanotechnology, NANO 2010 - Ilsan, Gyeonggi-Do, Korea, Republic of Duration: Aug 17 2010 → Aug 20 2010 |

### Publication series

Name | 2010 10th IEEE Conference on Nanotechnology, NANO 2010 |
---|

### Conference

Conference | 2010 10th IEEE Conference on Nanotechnology, NANO 2010 |
---|---|

Country/Territory | Korea, Republic of |

City | Ilsan, Gyeonggi-Do |

Period | 8/17/10 → 8/20/10 |

## ASJC Scopus subject areas

- Atomic and Molecular Physics, and Optics