TY - GEN
T1 - Design of a comparator tree based on reversible logic
AU - Thapliyal, Himanshu
AU - Ranganathan, Nagarajan
AU - Ferreira, Ryan
PY - 2010
Y1 - 2010
N2 - 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(log2(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(xi, xi-1) and y(yi, yi-1), to generate two 1-bit outputs Y and Z. Y will be 1 if x(xi, xi-1)> y(yi, yi-1), and Z will be 1 if x(xi, xi-1)i, y i-1). After careful analysis, we modified the logic equations of Y = x1ȳ1 + kx0ȳ0 and Z = x̄1y1 + kx̄0y0 to Y = x1ȳ1 ⊕ kx0ȳ0 and Z = x̄1y1 ⊕ kx̄0y0, 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 x0ȳ0 and x̄0y0. 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 x0(x1(x>y) and O2(x=y).
AB - 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(log2(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(xi, xi-1) and y(yi, yi-1), to generate two 1-bit outputs Y and Z. Y will be 1 if x(xi, xi-1)> y(yi, yi-1), and Z will be 1 if x(xi, xi-1)i, y i-1). After careful analysis, we modified the logic equations of Y = x1ȳ1 + kx0ȳ0 and Z = x̄1y1 + kx̄0y0 to Y = x1ȳ1 ⊕ kx0ȳ0 and Z = x̄1y1 ⊕ kx̄0y0, 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 x0ȳ0 and x̄0y0. 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 x0(x1(x>y) and O2(x=y).
UR - http://www.scopus.com/inward/record.url?scp=79951837289&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79951837289&partnerID=8YFLogxK
U2 - 10.1109/NANO.2010.5697872
DO - 10.1109/NANO.2010.5697872
M3 - Conference contribution
AN - SCOPUS:79951837289
SN - 9781424470334
T3 - 2010 10th IEEE Conference on Nanotechnology, NANO 2010
SP - 1113
EP - 1116
BT - 2010 10th IEEE Conference on Nanotechnology, NANO 2010
T2 - 2010 10th IEEE Conference on Nanotechnology, NANO 2010
Y2 - 17 August 2010 through 20 August 2010
ER -