理论计算机科学电子笔记253（2010）57-70www.elsevier.com/locate/entcsBDD优化在可逆逻辑与量子逻辑罗伯特·威尔1 Rolf Drechsler2不来梅大学计算机科学学院德国摘要近年来，可逆逻辑与量子逻辑的综合已成为一个热门的研究课题。然而，大多数合成方法是有限的，因为它们依赖于要合成的函数的真值表表示。基于BDD的合成是一种替代方法。 在这里，可逆或量子电路是从二元决策图（BDD）给出的函数中导出的，通过分别用级联的To量子门或基本量子门来替换BDD的所有节点。 因此，该方法的应用不受函数真值表的限制，而是受（更有效的）BDD表示的限制。此外，存在可以利用的用于BDD的许多优化技术在这项工作中，我们评估了三种优化方法的效果BDD（即共享节点，复杂，段边，和先进的排序）上产生的可逆和量子电路。我们详细描述的调整，必须做的，以支持这些优化合成，并讨论可能的改进和缺点。在一个案例研究中，效果进行了实验评估。结果表明，应用这些优化技术可以显著减小电路（相对于门和线）在大多数情况下。关键词：综合，可逆电路，量子电路，二元决策图1引言可逆和量子逻辑[10，1，20]在低功耗设计[10]，量子计算[15]，光学计算[4]，DNA计算[1]和纳米技术[13]等领域有应用。由于可逆和量子电路的合成与传统设计显著不同（例如，不允许扇出和反馈），近年来，它已成为一个热门的研究领域然而，许多合成方法是有限的。 已经提出了精确（参见例如[7，23]）以及启发式（参见例如[18，11，6，12但两者都只能用于相对较小的功能。精确的方法达到其极限，1电子邮件：rwille@informatik.uni-bremen.de2电子邮件：drechsler@uni-bremen.de1571-0661© 2010 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2010.02.00658R. 维勒河Drechsler/Electronic Notes in Theoretical Computer Science 253（2010）57包含6个以上变量的函数[23]，而启发式方法可以最多可以合成30个变量的函数[6]。此外，通常需要大量的运行时来实现这些结果。这些限制主要是由底层技术造成的。现有的合成方法通常依赖于要合成的函数的真值表（或类似的描述，如置换）（例如[18，14]）。但是，即使使用更紧凑的数据结构，如BDD [9]，正极性Reed-Muller展开[6]或Reed-Muller谱[12]，也可以观察到相同的限制，因为它们都应用类似的策略（即选择可逆门，使得所选择的函数表示成为恒等式）。作为替代，在[21]中引入了一种新的合成方法，可以处理更大的功能。 在这里，可逆或量子电路 是从BDD [3]给出的函数中导出的，通过分别用级联的T0量子门或基本量子门替换BDD的所有节点。因此，综合方法不受函数真值表的限制，而是受（更有效的）BDD表示的限制。然而，由于BDD已经开发了许多优化技术（例如共享节点[3]，补边[2]和重新排序策略，如筛选[17]），因此显然也可以将这些优化用于可逆和量子逻辑的合成。但这需要新的方法来从BDD导出电路在这项工作中，我们描述了一个改进的BDD为基础的综合方法，支持共享节点，补充边缘，和不同的顺序BDD为基础的可逆和量子逻辑的综合，并讨论可能的改进和缺点。在一个案例研究中，我们评估这些优化方法对电路尺寸的影响。事实证明，在大多数情况下，应用这些优化技术会导致电路明显变小论文的其余部分结构如下：第2节提供了可逆和量子逻辑以及BDD的基础知识。然后，在第3节中，简要回顾了[21第4节描述了新的基于BDD的合成方法，该方法支持共享节点、互补边和重新排序，用于基于BDD的可逆和量子逻辑的合成。 最后，在第5节中，对这些优化技术在最终电路上的效果进行了实验评估，而本文在第6节中进行了总结。2预赛为了保持论文的独立性，本节简要回顾了可逆逻辑和量子逻辑的基本概念。 我们还描述了BDD的基本知识， 作为基础数据结构的综合方法。2.1可逆逻辑一个逻辑函数是可逆的，如果它将每个输入赋值映射到一个唯一的输出赋值。这样的函数必须具有相同数量的输入和输出变量X：= {x1，.，x n}。由于扇出和反馈是不允许的，R. 维勒河Drechsler/Electronic Notes in Theoretical Computer Science 253（2010）5759| |||{}联系我们| ⟩|⟩|⟩|⟩|⟩⊕c输出和––0c 在abc输出和-–(a) 带To量子门（b）带基本量子门Fig. 1. 实现全加器的两种电路在逻辑中，实现可逆功能的电路是可逆门的级联。可逆门具有形式g（C，T），其中C={x，1，.，x ik}是控制线的集合，并且T= x j1，.， 其中CT=是目标线的集合。C可以是空的。 在所有控制线满足所需控制条件的情况下，对目标线应用门操作。控制线和未连接的线总是通过门不变。在文献中，已经介绍了几种类型的可逆门。除了Fredkin门[5]和Peres门[16]），（多控制）To Estuoli门[20]被广泛使用。每一个T0-T1门具有一个目标线xj，其被反转i，所有控制线被分配为1。也就是说，多个受控的To-100 oli门映射（x1，...，xj，.，xn）到（x1，...，x i1x i2···x ikx j，.，x n）。量子电路借助基本量子门实现功能。量子电路本质上是可逆的，并且操纵量子比特而不是纯粹的逻辑值。两个纯逻辑状态的量子比特的状态可以表示为α0 +β 1，其中0和1分别表示纯逻辑状态0和1，α和β是复数，使得α2+β2= 1。最常见的基本量子门是非门（单个量子比特被反转），受控非（CNOT）门（如果单个控制量子比特为1，则目标量子比特被反转），受控V门（也称为非的平方根，因为两个连续的V操作等同于反转）和受控V+门（执行V门的逆操作，因此也是非的平方根）。例2.1图1（a）显示了一个全加器的一个T-S门实现。该电路有四个输入（常数输入0，进位Cin，以及求和命令a和b），四个输出（进位Cout和求和以及两个垃圾输出），并由四个To Tosholi门组成因此，每个To_Escololi门的控制线由·表示，而目标线由表示。图1（b）中描绘了通过基本量子门实现相同功能的电路。该电路具有相同的输入和输出，但总共由六个门组成。这种表示法类似于ToEscheroli电路，不同之处在于目标线是相对于特定的门类型来表示的。更确切地说，V盒用于表示受控V门，V+盒用于表示受控V+门。非门和CNOT门的符号与T0-CNOT门的符号相同0c 在ab60R. 维勒河Drechsler/Electronic Notes in Theoretical Computer Science 253（2010）57→→∈2.2二元决策图布尔函数f：BnB可以用二元决策图（Binary Decision Diagram，BDD）表示[3]。BDD是一个有向无环图G=（V，E），其中Shannon分解f=xi fxi=0+xi fxi=1（1≤i ≤n）在每个节点v ∈ V中执行。函数f xi=0和f xi=1是f的余因子。在下文中，表示fxi=0（fxi=1）的节点由low（v）（high（v））表示，而xi称为选择变量。如果每个变量在从根节点到终端节点的每条路径上最多遇到一次，则BDD被称为自由。一个BDD被称为有序的，如果所有的变量在所有这样的路径上都以相同的顺序遇到在下文中，为了简洁起见，有序二元决策图被称为BDD。BDD的大小k由节点数定义在过去，已经开发了几种优化BDD尺寸的技术。特别是共享节点[3]允许显着减少。也就是说，如果节点V具有多于一个的前驱节点。 特别地，函数f：BnBm（即具有多于一个输出的函数）可以使用共享节点来更复杂地表示。如果应用补边[2]，则可以实现进一步的减少。这使得一个函数的表示以及它的否定只由一个节点。此外，BDD的大小很大程度上取决于其输入变量的选择顺序[3]。3BDD合成在本节中，我们简要回顾了[21]中介绍的基于BDD的可逆和量子逻辑的综合。这为本文的其余部分提供了基础，其中详细讨论了BDD优化技术在综合方法中的应用。每种综合方法的目的是确定给定布尔函数的电路实现。众所周知，布尔函数可以有效地用BDD表示[3]。具有BDDG=（V，E），可逆网络可以通过遍历BDD并将每个节点V V替换为可逆门的级联来导出。门的相应级联取决于节点v的后继者。表1分别提供了针对BDD节点的所有可能场景的请注意，如果其中一个边沿为低（v），则需要附加（恒定）线或高（V）导致终端节点。 这是因为可逆性，在合成可逆逻辑时确保。作为示例，考虑具有high（v）=0的节点v（表1的第二行）。在不失一般性的情况下，相应真值表的前三行可以嵌入表2（a）中描述的可逆性。然而，由于f在最后一行是0，所以整个函数的可逆嵌入是不可能的。 因此，需要增加一行以使相应的取代可逆（参见表2（b））3.3由于同样的原因，也不可能分别保留低（v）或高（v）的值R. 维勒河Drechsler/Electronic Notes in Theoretical Computer Science 253（2010）5761表1可逆/量子电路的BDD节点替换BDD敬基诺利电路量子电路fxi0/ \1// \低（f）高（f）xi高（f）低（f）Xi–Fxi高（f）低（f）xif–fxi0/ \1// \低（f）00F0FXiXiXiXi低（f）低（f）低（f）低（f）fxi0/ \1// \低（f）10F0FXiXiXiXi低（f）低（f）低（f）低（f）fxi0/ \1// \0高（f）0xi高（f）fxi高（f）0xi高（f）fxi高（f）fxi0/ \1// \1个高（f）1xi高（f）fxi高（f）1xi高（f）fxi高（f）fxi0/ \1// \1 01F1FXiXiXiXifxi0/ \1// \0 10F0FXiXiXiXi基于这些替换，可以制定一种在可逆逻辑或量子逻辑中综合布尔函数的方法：首先，创建要综合的函数f的BDD。这可以使用最先进的BDD包（例如CUDD [19]）有效地完成。接下来，通过深度优先搜索遍历所得到的BDDG=（V，E对于每个节点v∈V，添加如表1所示的级联在表1的第一行中描述的替换中。62R. 维勒河Drechsler/Electronic Notes in Theoretical Computer Science 253（2010）57→表2（部分）节点v的真值表，其中high（v）= 0(a) w/o add. line（b）with additional line（无附加线）Xi低（f）F–0Xi低（f）FXi低（f）000000000001110011011001010010110？011011fJ/0x12F1x1x2x3x4\1fJJ0fx100g0/ \1// \0/\1x2x2// \0 1 1 0(a) BDD（b）生成电路图二. f=x1<$x2的BDD和To-1000回路到电路。例3.1考虑图2（a）中的BDD。 将表1中给出的替换应用于BDD的每个节点，得到图2（b）中所示的To Bundoli网络。其结果是，电路综合实现给定的功能f。由于BDD的每个节点仅由级联的门代替，因此所提出的方法相对于BDD中的节点数具有线性最坏情况的4利用BDD优化当前最先进的BDD包（例如CUDD [19]）利用几种优化技术来构建小尺寸的BDD。在本节中，我们将描述如何将这些技术应用于所提出的基于BDD的合成。 效果 在下一节中考虑对所得可逆或量子电路的这些优化。4.1共享节点如果一个节点v有多个前趋节点，那么v被称为共享节点。共享节点的应用几乎在所有的BDD包中都很常见。共享节点可用于多次表示子公式，而无需重建整个子图。特别地，函数f：BnBm（即具有多于一个输出的函数）可以使用共享节点来更复杂地表示R. 维勒河Drechsler/Electronic Notes in Theoretical Computer Science 253（2010）57630xi低（ f ）高（f）fxi低（f）高（f）0xi低（ f ）高（f）fxi低（f）高（f）(a) （b）量子门级联图3.第三章。没有终端作为后继的共享节点的替换联系我们f1xi 1/0f2xxi 1高（f2）0xi低（f1）gf1xi低（f1）低（f）fj高（f）xjxj1人j/0\12高（f'）g低（f'）f2低（fJ）高（fJ）(a) BDD（b）生成电路图四、用于共享BDD的To Escheroli电路然而，为了使用共享节点，必须保留相应节点的输出值，直到不再需要它为止。为了确保这一点，需要具有恒定输入的附加电路线。考虑到表1中描绘的替换，这是针对所有节点v的情况，其中边低（v）或高（v）之一导致终端节点。在此，保留输入的所有值（特别是分别为高（v）或低（v））。但是，正如上面已经提到的，这对于一般情况是不可能的（表1的第一行）。这里，至少保留一个值（即来自select变量的值）。因此，需要对没有终端作为后继者的共享节点进行修改替换。图3（a）和图3（b）分别显示了可逆电路和量子电路的一种可能替代除了额外的（恒定）电路线，这需要一个额外的门与表1的替换相比。 相比之下，使用这种替换，不再需要表示其选择变量的标识的节点的级联。 在这种情况下，节点可以由与图1所示相同的电路线表示。输入本身。这现在是可能的，因为可以保留表示节点的电路线的值。示例4.1在图4（a）中，示出了包括共享节点FJ由于节点FJ的值被使用两次（由节点f1和f2使用），所以如图3（a）中所描绘的附加线（图4（b）中的线2）和级联的门被应用于替换节点f1。然后，fJ的值仍然可用，使得可以应用节点f2的替换图4（b）给出了最终电路。64R. 维勒河Drechsler/Electronic Notes in Theoretical Computer Science 253（2010）57表3可逆/量子电路中BDD节点的补边替换BDD敬基诺利电路量子电路f f f\/十月0/。 1// \低（f）高（f）1F1FXiXiXiXi低（f）低（f）低（f）低（f）高（f）高（f）高（f）高（f）fxi0/。 1// \低（f）高（f）xi高（f）低（f）Xi–Fxi高（f）低（f）xif–fxi0/。 1// \低（f） 01F1FXiXiXiXi低（f）低（f）低（f）低（f）fxi0/。 1// \低（f） 11F1FXiXiXiXi低（f）低（f）低（f）低（f）fxi0/。 1/z\G1F1FXiXiXiXiGGGG4.2补边如果应用补边[2]，则可以实现BDD大小的进一步减小。特别地，这允许仅通过单个节点来表示函数及其求反。如果应用互补边缘，则其连接节点的输出值变为反转。为了在我们的合成方法中支持补边，必须确定新的替换，其考虑到补边的反转。表3显示了在我们的合成方法中使用的所得级联。请注意，补集必须仅在节点的低边缘处考虑。在高边缘处具有补数的节点可以容易地被在低边缘处具有补数的相应节点替换。在某些情况下，与没有互补边的取代相比，这导致更大的级联（特别是对于Togloboli级联）。在第5节中详细讨论了可能的BDD减少（或不减少）可以在多大程度上补偿这一点。R. 维勒河Drechsler/Electronic Notes in Theoretical Computer Science 253（2010）57654.3BDD订购它已被证明，变量的顺序有很大的影响的大小[3]的结果。在过去，已经提出了几种方法来实现良好的排序（例如筛选[17]）或确定确切的结果[8]。所有这些技术可以直接应用于我们的合成方法，不需要进一步调整已经引入的取代。使用这些优化技术（即共享节点，互补边和重新排序），在下一节中，将考虑它们如何分别对所产生的To卷积或量子电路进行优化。5实验研究在本节中，我们将研究相应优化技术的效果对于BDD最小化的结果可逆或量子电路。 为此，我们在BDD包CUDD [19]的顶部用C++实现了所提出的合成方法，并在启用或禁用相应技术的情况下合成了电路。作为基准，我们使用RevLib [22]提供的函数（包括以前用于评估现有可逆合成方法的大多数函数）以及LGSynth包（用于评估不可逆合成的基准套件）。所有实验都是在具有1GB内存的AMD Athlon 3500+上进行的。5.1共享节点为了研究共享节点的效果，我们扩展了CUDD，以便可以禁用或启用共享节点的应用程序（这是通过操纵唯一表来完成的）。然后，适当地应用表1和图3结果总结见表4。 前两列给出了基准的名称（NAME）以及主要输入和输出（PI/PO）。然后，电路线（L线）的数量，到多个门（T。（ GATES）或基本量子门（QUA. Gates），以及针对纯方法（W/OS共享节点）和利用共享节点的 方 法 （具有S共享节点）给出了合成方法的运行时间（以CPU秒为单位）。我们可以清楚地得出结论，共享节点的应用可以更好地实现可逆和量子逻辑。线的数量和门的数量都可以显著减少。特别是，对于线的数量，这可能是不明显的，因为需要额外的线来支持共享节点（见4.1节）。 但由于共享节点也减少了对于终端节点（其也需要额外的线路），该效应被补偿。66R. 维勒河Drechsler/Electronic Notes in Theoretical Computer Science 253（2010）57表4选择共享节点功能无共享节点共享节点名名Pi/PO线T的。加特斯QUA。加特斯时间线T的。加特斯QUA。加特斯时间REV LIB FUN cTIONS3 17 63/3122252 <0.01102050 <0.014 49 74/42151123 <0.011845114 <0.014mod5 84/191336 <0.0191336 <0.01aj-e11 814/42046114 <0.011945113 <0.01铝95/1153073 <0.01142972 <0.01decod24-enable 323/4101035 <0.019930 <0.01解码24 102/47721 <0.017721 <0.01前1823/381331 <0.0181331 <0.01Fredkin 33/35616 <0.015616 <0.01graycode6 116/649135327 <0.01162045 <0.01ham3 283/31119470.01101846 <0.01中文（简体）7/775231595 <0.013688224 <0.01hwb5 135/536105277 <0.013291238 <0.01hwb6 146/668239618 <0.0153167437 <0.01hwb7 157/7136526 1353 <0.0184284744 <0.01hwb8648/8277 1132 29030.02129456 1195 <0.01米勒53/391843 <0.0181538 <0.01微型铝844/2122157 <0.01112052 <0.01mod5d2 175/53178188 <0.011942102 <0.01一二三273/3101647 <0.01101440 <0.01佩雷斯43/381437 <0.017924 <0.01简体中文3/291638 <0.0181537 <0.01简体中文5/33185212 <0.012049130 <0.01简体中文7/386301730 <0.0138105272 <0.01简体中文8/4194679 16500.0152140373 <0.01sym6 636/123571260.01173483 <0.01sym9 719/1104325724 <0.013579201 <0.01LGS合成函数9sym9/1104325724 <0.013579201 <0.01BW5/281253819350.0197286747 <0.01rd848/4117419 10530.0150138367 <0.01sqrt88/444114242 <0.013284188 <0.01表314/14841 2586 71400.03 689 2143 59240.02异或55/1174098 <0.01101948 <0.015.2补边CUDD软件包支持补边，可以轻松禁用和启用。为了进行比较，我们从两个BDD合成电路，无补边的BDD（用表示，带COM pL. EDGES 和W/OCOM pL. 边缘，分别）。在后一种情况下，只要后继由互补边连接，就应用表3BDDR. 维勒河Drechsler/Electronic Notes in Theoretical Computer Science 253（2010）5767表5补边的提取功能不含C ompL。EDGES与COM pL。EDGES名名Pi/PO线T的。加特斯QUA。加特斯时间线T的。加特斯QUA。加特斯时间REV LIB FUN cTIONS3 17 63/3102050 <0.0181733 <0.014 49 74/41845114 <0.01164597 <0.014mod5 84/191336 <0.0181637 <0.01aj-e11 814/41945113 <0.011643105 <0.01铝95/1142972 <0.01112553 <0.01decod24-enable 323/49930 <0.0191433 <0.01解码24 102/47721 <0.0161123 <0.01前1823/381331 <0.0171432 <0.01Fredkin 33/35616 <0.015616 <0.01graycode6 116/6162045 <0.01111515 <0.01ham3 283/3101846 <0.0161222 <0.01中文（简体）7/73688224 <0.01185082 <0.01hwb5 135/53291238 <0.012785201 <0.01hwb6 146/653167437 <0.0146157377 <0.01hwb7 157/784284744 <0.0174276665 <0.01hwb8648/81294561195 <0.01116442 1067 <0.01米勒53/381538 <0.0181639 <0.01微型铝844/2112052 <0.01102249 <0.01mod5d2 175/51942102 <0.01122849 <0.01一二三273/3101440 <0.0191635 <0.01佩雷斯43/37924 <0.015711 <0.01简体中文3/281537 <0.0161019 <0.01简体中文5/32049130 <0.01133475 <0.01简体中文7/338105272 <0.012573162 <0.01简体中文8/452140373 <0.0134104229 <0.01sym6 636/1173483 <0.01142969 <0.01sym9 719/13579201 <0.012762153 <0.01LGS合成函数9sym9/13579201 <0.012762153 <0.01BW5/2897286747 <0.0191317732 <0.01夹9/51725971544 <0.01152584 13970.01cordic23/2761774480.02531092650.02ex5p8/6327668016760.02233706 15200.02PDC16/40648 207448440.12631 2109 48030.12rd848/450138367 <0.0133103226 <0.01苏人解16/46567 1422 37530.09 559 172837990.09sqrt88/43284188 <0.013087183 <0.01表314/14689 2143 59240.02 686 241359260.01异或55/1101948 <0.01688 <0.0168R. 维勒河Drechsler/Electronic Notes in Theoretical Computer Science 253（2010）57类型应用共享节点，因为它们的应用已被证明是有益的（见上文）。结果在表5和4中给出。按照第5.1节所述对色谱柱进行标记。即使在某些情况下，表示具有互补边的节点的级联更大（参见第4.2节），也可以观察到电路尺寸的改进（参见例如RD8470、9sym或CORDIC）。但特别是对于LGSynth功能，当互补边沿被禁用时，通常更好地实现To Besoli电路的结果（例如，参见seq、spla或表3）。这里，较大的级联显然不能通过互补边缘优化来补偿。相比之下，对于量子电路，在几乎所有情况下，都可以在启用互补边缘的情况下获得更好的实现。 有原因也就是说，在几乎所有情况下，具有互补边的节点的量子级联与不具有互补边的节点的相应级联具有相同的大小（分别参见表1、图3和表3）。 因此，可以充分利用互补边缘的优点（即，创建较小BDD的可能性），而没有相应栅极替换变得更大的缺点。5.3BDD订购为了评估BDD排序对所得电路大小的影响，考虑了三种技术：（1）由要合成的函数中的主输入的出现给出的排序（由OORIGINAL表示），（2）通过筛选实现的优化排序[17]（由SIFTING表示），以及（3）确保BDD最小的精确排序[8]（由EXA cT表示）。 同样，所有创建的BDD都利用共享节点。此外，在该评估中启用互补边沿。在应用我们的合成方法之后，电路尺寸如表6所示。同样，列的标记如第5.1节所述。结果表明，电路的排序对电路规模有很强的影响。特别是对于LGSynth函数，通过精确排序可以实现最佳结果。但作为缺点，这需要更长的运行时间。除此之外，在本评估中，还可以找到一些示例，表明BDD的优化并不总是导致更小的电路（例如，参见ham7 29或hwb 7 15，其中使用朴素排序实现了最佳结果）。但在大多数情况下，都观察到了改善。与以前的工作相比，首次可以合成具有30个以上变量6结论和今后的工作在本文中，我们描述和评估决策图的优化技术也可以用于基于BDD的可逆和量子逻辑的合成。我们考虑了共享节点，互补边，以及排序策略，并提出了门级联需要支持这些方法。 在一项病例研究中评估了这些技术对电路尺寸的影响。在大多数情况下，BDD优化也会导致电路尺寸的改善4与表4相比，还考虑了无法使用没有共享节点方法。R. 维勒河Drechsler/Electronic Notes in Theoretical Computer Science 253（2010）5769表6变量排序功能原始O西夫廷EXA cT名名Pi/PO线T的。加特斯QUA。加特斯时间线T的。加特斯QUA。加特斯时间线T的。加特斯QUA。加特斯时间REV LIB FUN cTIONS3 17 63/381733 <0.0171729 <0.0171729 <0.014 49 74/4164597 <0.01154292 <0.01154292 <0.014mod5 84/181637 <0.017818 <0.017818 <0.01aj-e11 814/41643105 <0.011642960.01153884 <0.01铝95/1112553 <0.017922 <0.017922 <0.01decod24-enable 323/491433 <0.0191433 <0.0191433 <0.01解码24 102/461123 <0.0161123 <0.0161123 <0.01前1823/371432 <0.015717 <0.015717 <0.01Fredkin 33/35616 <0.015616 <0.015616 <0.01graycode6 116/6111515 <0.011115150.01111515 <0.01ham3 283/361222 <0.01714270.0171427 <0.01中文（简体）7/7185082 <0.012161107 <0.0121611070.01hwb5 135/52785201 <0.0128882050.0128882050.01hwb6 146/646157377 <0.0146159375 <0.01461593750.01hwb7 157/774276665 <0.0173281653 <0.01762786580.01hwb8648/8116442 1067 <0.01112449 1047 <0.0111444010510.03米勒53/381639 <0.0181639 <0.0181639 <0.01微型铝844/2102249 <0.01102043 <0.01102043 <0.01mod5d2 175/5122849 <0.01112030 <0.01112030 <0.01一二三273/391635 <0.0191635 <0.0191635 <0.01佩雷斯43/35711 <0.015711 <0.015711 <0.01简体中文3/261019 <0.01610190.0161019 <0.01简体中文5/3133475 <0.01133475 <0.01133475 <0.01简体中文7/32573162 <0.012573162 <0.012573162 <0.01简体中文8/434104229 <0.0134104229 <0.0134104229 <0.01sym6 636/1142969 <0.01142969 <0.01142969 <0.01sym9 719/12762153 <0.012762153 <0.012762153 <0.01LGS合成函数9sym9/12762153 <0.012762153 <0.0127621530.01BW5/2891317732 <0.0187307693 <0.0184306667 <0.01夹9/5152584 13970.0166228508 <0.01571853920.04cordic23/2531092650.02521012470.0350952376.90ex5p8/63233706 15200.0220664713880.02 206647 13880.06PDC16/40631 2109 48030.12619 208047810.13619 2087 485066.38rd848/433103226 <0.01331032260.0133103226 <0.01苏人解16/46559 1728 37990.09489 170943720.09 483 1687 432286.92sqrt88/43087183 <0.013076179 <0.012771173 <0.01表314/14686 2413 59260.01554 198846790.02529 1873 45079.88异或55/1688 <0.01688 <0.01688 <0.0170R. 维勒河Drechsler/Electronic Notes in Theoretical Computer Science 253（2010）57在未来的工作中，我们计划调整的优化技术的合成目的相对于预期的电路尺寸，而不是BDD的大小。 例如，在重新排序期间使用的成本函数应该为此目的进行修改。除此之外，还应考虑其他分解引用[1] 贝内特角H、计算的逻辑可逆性，IBM J。Res. Dev17（1973），pp.525-532[2] 布雷斯，K.，R. Rudell和R. Bryant，BDD包的有效实现，在：设计自动化会议。，1990年，第40比45[3] 布莱恩特河， 基于图的布尔函数操作算法，IEEE Trans. 35（1986），pp. 677-691[4] 库肯德尔河和D. R. Andersen，可逆光学计算电路，光学快报12（1987），pp. 542-544[5] Fredkin ，E. F.和T. To Escheroli ，Conservative logic， International Journal of Theoretical Physics21（1982），pp. 219-253[6] 古普塔，P.，A. Agrawal和N. Jha，An algorithm for synthesis of reversible logic circuits，IEEETrans. on CAD25（2006），pp. 2317-2330[7] Hung，W.，X.宋，G. Yang，J. Yang和M. Perkowski，通过符号可达性分析使用一组量子门的多输出布尔函数的最佳合成。，IEEE Trans.on CAD25（2006），pp. 1652-1663年。[8] 郑山W.，T.- S. Kim和F.陈文辉，一种新的BDD排序算法，载于《计算机辅助设计与集成电路国际会议》，1993年，第10 - 11页。252-256[9] Kerntopf，P.，可逆逻辑综合的一种新的启发式算法，在：设计自动化会议。，2004，pp. 834-837[10] Landauer，R.，计算过程中的不可逆性和热生成，IBM J. Res. Dev. 5（1961年）， p. 183.[11] Maslov，D.，G. W. Dueck和D. M. Miller，To Escheroli network synthesis with templates，IEEE Trans.on CAD24（2005），pp. 807-817[12] Maslov，D.，G. W. Dueck和D. M.米勒，技术用于可逆的合成到多个网络，ACM Trans.电子系统设计自动化12（2007）。[13] 梅克尔河C.的方法，可逆电子逻辑使用开关，纳米技术4（1993年），页。21比40[14] 米勒，D。M.，D. Maslov和G. W. Dueck，基于变换的可逆逻辑综合算法，在：设计自动化会议。，2003，pp. 318-323[15] Nielsen，M.和I.庄，[16] Peres，A.，Reversible Logic and Quantum Computers，Phys. Rev. A（1985），pp. 3266-3276。[17] 鲁德尔河，有序二元决策图的动态变量排序，在：42比47[18] Shende，V. V.，A. K.普拉萨德岛L.马尔可夫和J.P.Hayes，可逆逻辑电路的综合，IEEE Trans. 第22卷（2003年），页。710-722[19] Somenzi，F.，[20] 对特罗波利来说，可逆计算，在：W。de Bakker和J. van Leeuwen，编辑，Automata，Languages andProgramming，Springer，1980 p. 632.[21] 维勒河和R. Drechsler，基于BDD的大型函数可逆逻辑综合，在：设计自动化会议。，2009年。[22] 威尔河，D. 格罗斯湖托伊伯湾W. Dueck和R.Drechsler，RevLib：可逆函数和可逆电路的在线资源，在：Int'l Symp。多值逻辑，2008年，pp。 220 -225，RevLib可在http：//www.revlib.org上获得。[23] 威尔河，H. M.勒湾，加-地W. Dueck和D. Große
我的内容管理
展开
