Garbage-Free Reversible Multiplication and Division View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-08-22

AUTHORS

Torben Ægidius Mogensen

ABSTRACT

We present a circuit design for garbage-free reversible multiplier. Given inputs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A,\,B$$\end{document} and R, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0\le B < 2^m$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0\le Rcircuit outputs A and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P = A\cdot B+R$$\end{document}. Applied in reverse, the circuit takes as input A and P, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0 More... »

PAGES

253-268

Book

TITLE

Reversible Computation

ISBN

978-3-319-99497-0
978-3-319-99498-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-99498-7_18

DOI

http://dx.doi.org/10.1007/978-3-319-99498-7_18

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1106294866


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/10", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Technology", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1005", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Communications Technologies", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "DIKU, University of Copenhagen, Universitetsparken 5, 2100, Copenhagen O, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.5254.6", 
          "name": [
            "DIKU, University of Copenhagen, Universitetsparken 5, 2100, Copenhagen O, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mogensen", 
        "givenName": "Torben \u00c6gidius", 
        "id": "sg:person.016655503425.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016655503425.67"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2018-08-22", 
    "datePublishedReg": "2018-08-22", 
    "description": "We present a circuit design for garbage-free reversible multiplier. Given inputs \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$A,\\,B$$\\end{document} and R, where \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$0\\le B < 2^m$$\\end{document} and \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$0\\le R
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-99498-7_18'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-99498-7_18'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-99498-7_18'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-99498-7_18'


 

This table displays all metadata directly associated to this object as RDF triples.

91 TRIPLES      23 PREDICATES      51 URIs      44 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-99498-7_18 schema:about anzsrc-for:10
2 anzsrc-for:1005
3 schema:author Nb8b81422e2d34c0bafdb653730cc3b93
4 schema:datePublished 2018-08-22
5 schema:datePublishedReg 2018-08-22
6 schema:description We present a circuit design for garbage-free reversible multiplier. Given inputs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A,\,B$$\end{document} and R, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0\le B < 2^m$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0\le R<A<2^n$$\end{document}, the circuit outputs A and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P = A\cdot B+R$$\end{document}. Applied in reverse, the circuit takes as input A and P, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0<A<2^n$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0\le P< 2^mA$$\end{document}, and outputs A, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$B = P/A$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R = P\%A$$\end{document}. The circuit uses a total of two ancilla bits.The circuit is constructed as a sequence of m modified ripple-carry adders and comparators, both of which have O(n) gate delay, so the multiplier has O(\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m\times n$$\end{document}) gate delay, but this can be improved to O(\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m\times \log (n)$$\end{document}) by using a modified carry-lookahead adder and an O(\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\log (n)$$\end{document}) comparator, both of which are described in the paper. The cost of reducing the gate delay to O(\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m\times \log (n)$$\end{document}) is O(n) added ancilla bits and a larger gate count.
7 schema:editor Nd1808ee72d2e4a88b092f612b5d39b53
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Na3c58d3925d64cd2b4327c28e1d8dbbc
12 schema:keywords Garbage-Free Reversible Multiplication
13 Reversible Multiplication
14 adder
15 ancilla bits
16 bits
17 carry-lookahead adder
18 circuit
19 circuit design
20 comparator
21 cost
22 counts
23 delay
24 design
25 division
26 gate count
27 gate delay
28 input
29 input A
30 large gate count
31 multiplication
32 multipliers
33 paper
34 reverse
35 ripple-carry adder
36 sequence
37 total
38 schema:name Garbage-Free Reversible Multiplication and Division
39 schema:pagination 253-268
40 schema:productId N35426c697bc14ef2ab1599623879c972
41 N565323d629554810876be3e7de5ad1b4
42 schema:publisher N33981e4509c44e59bc435e16d8dd97b2
43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106294866
44 https://doi.org/10.1007/978-3-319-99498-7_18
45 schema:sdDatePublished 2021-11-01T18:48
46 schema:sdLicense https://scigraph.springernature.com/explorer/license/
47 schema:sdPublisher N0a14ba8b8b5f4c928e60be14f94ea5cc
48 schema:url https://doi.org/10.1007/978-3-319-99498-7_18
49 sgo:license sg:explorer/license/
50 sgo:sdDataset chapters
51 rdf:type schema:Chapter
52 N0a14ba8b8b5f4c928e60be14f94ea5cc schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 N33981e4509c44e59bc435e16d8dd97b2 schema:name Springer Nature
55 rdf:type schema:Organisation
56 N33b2acd4fb8f4f3ab581144fd9d5ce7d schema:familyName Ulidowski
57 schema:givenName Irek
58 rdf:type schema:Person
59 N35426c697bc14ef2ab1599623879c972 schema:name doi
60 schema:value 10.1007/978-3-319-99498-7_18
61 rdf:type schema:PropertyValue
62 N3816484af1e947aa91c91d66842b49bf rdf:first N33b2acd4fb8f4f3ab581144fd9d5ce7d
63 rdf:rest rdf:nil
64 N565323d629554810876be3e7de5ad1b4 schema:name dimensions_id
65 schema:value pub.1106294866
66 rdf:type schema:PropertyValue
67 Na3c58d3925d64cd2b4327c28e1d8dbbc schema:isbn 978-3-319-99497-0
68 978-3-319-99498-7
69 schema:name Reversible Computation
70 rdf:type schema:Book
71 Nb8b81422e2d34c0bafdb653730cc3b93 rdf:first sg:person.016655503425.67
72 rdf:rest rdf:nil
73 Nc5e6b2c2e8824371aba8abe34162e69c schema:familyName Kari
74 schema:givenName Jarkko
75 rdf:type schema:Person
76 Nd1808ee72d2e4a88b092f612b5d39b53 rdf:first Nc5e6b2c2e8824371aba8abe34162e69c
77 rdf:rest N3816484af1e947aa91c91d66842b49bf
78 anzsrc-for:10 schema:inDefinedTermSet anzsrc-for:
79 schema:name Technology
80 rdf:type schema:DefinedTerm
81 anzsrc-for:1005 schema:inDefinedTermSet anzsrc-for:
82 schema:name Communications Technologies
83 rdf:type schema:DefinedTerm
84 sg:person.016655503425.67 schema:affiliation grid-institutes:grid.5254.6
85 schema:familyName Mogensen
86 schema:givenName Torben Ægidius
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016655503425.67
88 rdf:type schema:Person
89 grid-institutes:grid.5254.6 schema:alternateName DIKU, University of Copenhagen, Universitetsparken 5, 2100, Copenhagen O, Denmark
90 schema:name DIKU, University of Copenhagen, Universitetsparken 5, 2100, Copenhagen O, Denmark
91 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...