您当前所在位置: 首页 > 学者

孙晓明

  • 12浏览

  • 0点赞

  • 0收藏

  • 0分享

  • 0下载

  • 0评论

  • 引用

期刊论文

Structured Decomposition for Reversible Boolean Functions

暂无

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2019,39(10):2410 - 242 | 2019年07月16日 | 10.1109/TCAD.2019.2928974

URL:https://ieeexplore.ieee.org/document/8764360

摘要/描述

Reversible Boolean function (RBF) is a one-to-one function which maps n-bit input to n-bit output. Reversible logic synthesis has been widely studied due to its connection with low-energy computation as well as quantum computation. In this paper, we give a structured decomposition for even RBFs. Specifically, for n ≥ 6, any even n-bit RBF can be decomposed to 7 blocks of (n-1)-bit RBF, where 7 is a constant independent of n and the positions of these blocks have a large degree of freedom. Moreover, if the (n-1)-bit RBFs are required to be even as well, we show for n ≥ 10, even n-bit RBF can be decomposed to 10 even (n - 1)-bit RBFs. In short, our decomposition has block depth 7 and even block depth 10. Our result improves Selinger's work in block depth model, by reducing the constant from 9 to 7 and from 13 to 10, when the blocks are limited to be even. We emphasize that our setting is a bit different from Selinger's work. In Selinger's constructive proof, each block is placed in one of two specific positions and thus the decomposition has an alternating structure. We relax this restriction and allow each block to act on arbitrary (n - 1) bits. This relaxation keeps the block structure and provides more candidates when choosing the positions of blocks.

关键词:

学者未上传该成果的PDF文件,请等待学者更新

我要评论

全部评论 0

本学者其他成果

    同领域成果