Design and synthesis of improved reversible circuits using AIG- and MIG-based graph data structures

Reversible logic synthesis is one of the best suited ways which act as the intermediate step for synthesising Boolean functions on quantum technologies. For a given Boolean function, there are multiple possible intermediate representations (IRs), based on functional abstraction, e.g. truth table, de...

Full description

Saved in:
Bibliographic Details
Main Authors: Bandyopadhyay, Chandan, Das, Rakesh, Chattopadhyay, Anupam, Rahaman, Hafizur
Other Authors: School of Computer Science and Engineering
Format: Article
Language:English
Published: 2021
Subjects:
Online Access:https://hdl.handle.net/10356/151938
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
id sg-ntu-dr.10356-151938
record_format dspace
spelling sg-ntu-dr.10356-1519382021-07-19T11:15:22Z Design and synthesis of improved reversible circuits using AIG- and MIG-based graph data structures Bandyopadhyay, Chandan Das, Rakesh Chattopadhyay, Anupam Rahaman, Hafizur School of Computer Science and Engineering Engineering::Computer science and engineering Data Structures Graph Theory Reversible logic synthesis is one of the best suited ways which act as the intermediate step for synthesising Boolean functions on quantum technologies. For a given Boolean function, there are multiple possible intermediate representations (IRs), based on functional abstraction, e.g. truth table, decision diagrams or circuit abstraction, e.g. binary decision diagram (BDD), and-inverter graph (AIG) and majority inverter graph (MIG). These IRs play an important role in building circuits as the choice of an IR directly impacts on cost parameters of the design. In the authors' work, they are analysing the effects of different graphbased IRs (BDD, AIG and MIG) and their usability in making efficient circuit realisations. Although applications of BDDs as an IR to represent large functions has already been studied, here they are demonstrating a synthesis scheme by taking AIG and MIG as IRs and making a comprehensive comparative analysis over all these three graph-based IRs. In experimental evaluation, it is being observed that for small functions BDD gives more compact circuits than the other two IRs but when the input size increases, then MIG as IR makes substantial improvements in cost parameters as compared with BDD by reducing quantum cost by 39% on an average. Along with the experimental results, a detailed analysis over the different IRs is also included to find their easiness in designing circuits. 2021-07-19T11:15:22Z 2021-07-19T11:15:22Z 2019 Journal Article Bandyopadhyay, C., Das, R., Chattopadhyay, A. & Rahaman, H. (2019). Design and synthesis of improved reversible circuits using AIG- and MIG-based graph data structures. IET Computers and Digital Techniques, 13(1), 38-48. https://dx.doi.org/10.1049/iet-cdt.2017.0097 1751-8601 https://hdl.handle.net/10356/151938 10.1049/iet-cdt.2017.0097 2-s2.0-85060135798 1 13 38 48 en IET Computers and Digital Techniques © 2018 The Institution of Engineering and Technology. All rights reserved.
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic Engineering::Computer science and engineering
Data Structures
Graph Theory
spellingShingle Engineering::Computer science and engineering
Data Structures
Graph Theory
Bandyopadhyay, Chandan
Das, Rakesh
Chattopadhyay, Anupam
Rahaman, Hafizur
Design and synthesis of improved reversible circuits using AIG- and MIG-based graph data structures
description Reversible logic synthesis is one of the best suited ways which act as the intermediate step for synthesising Boolean functions on quantum technologies. For a given Boolean function, there are multiple possible intermediate representations (IRs), based on functional abstraction, e.g. truth table, decision diagrams or circuit abstraction, e.g. binary decision diagram (BDD), and-inverter graph (AIG) and majority inverter graph (MIG). These IRs play an important role in building circuits as the choice of an IR directly impacts on cost parameters of the design. In the authors' work, they are analysing the effects of different graphbased IRs (BDD, AIG and MIG) and their usability in making efficient circuit realisations. Although applications of BDDs as an IR to represent large functions has already been studied, here they are demonstrating a synthesis scheme by taking AIG and MIG as IRs and making a comprehensive comparative analysis over all these three graph-based IRs. In experimental evaluation, it is being observed that for small functions BDD gives more compact circuits than the other two IRs but when the input size increases, then MIG as IR makes substantial improvements in cost parameters as compared with BDD by reducing quantum cost by 39% on an average. Along with the experimental results, a detailed analysis over the different IRs is also included to find their easiness in designing circuits.
author2 School of Computer Science and Engineering
author_facet School of Computer Science and Engineering
Bandyopadhyay, Chandan
Das, Rakesh
Chattopadhyay, Anupam
Rahaman, Hafizur
format Article
author Bandyopadhyay, Chandan
Das, Rakesh
Chattopadhyay, Anupam
Rahaman, Hafizur
author_sort Bandyopadhyay, Chandan
title Design and synthesis of improved reversible circuits using AIG- and MIG-based graph data structures
title_short Design and synthesis of improved reversible circuits using AIG- and MIG-based graph data structures
title_full Design and synthesis of improved reversible circuits using AIG- and MIG-based graph data structures
title_fullStr Design and synthesis of improved reversible circuits using AIG- and MIG-based graph data structures
title_full_unstemmed Design and synthesis of improved reversible circuits using AIG- and MIG-based graph data structures
title_sort design and synthesis of improved reversible circuits using aig- and mig-based graph data structures
publishDate 2021
url https://hdl.handle.net/10356/151938
_version_ 1707050432921075712