A tree search algorithm for low multiplicative complexity logic design

被引:2
作者
Tay, Jia Jun [1 ]
Wong, M. L. Dennis [2 ]
Wong, Ming Ming [3 ]
Zhang, Cishen [4 ]
Hijazin, Ismat [4 ]
机构
[1] Swinburne Univ Technol, Fac Engn Comp & Sci, Sarawak Campus, Sarawak, Malaysia
[2] Heriot Watt Univ Malaysia, Putrajaya, Malaysia
[3] Nanyang Technol Univ, Sch Comp Sci & Engn, Nanyang Ave, Singapore, Singapore
[4] Swinburne Univ Technol, Fac Sci Engn & Technol, Hawthorn, Vic, Australia
来源
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE | 2018年 / 83卷
关键词
Logic design; Multiplicative complexity; Function decomposition; Tree search algorithm; BOOLEAN FUNCTIONS; S-BOX; MINIMIZATION; CIPHER; AES;
D O I
10.1016/j.future.2018.01.063
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Low multiplicative complexity logic design is a useful heuristic to achieve low gate count implementation of logic circuit. In this work, we propose a deterministic approach based on the currently known lower and upper bounds of multiplicative complexity for logic minimization problems with not more than five inputs. The proposed tree search algorithm achieves circuit minimization through decomposition of Positive Polarity Reed-Muller expressions. This approach allows low multiplicative complexity logic design to be executed without the consistency issue associated with the randomized approach in the original algorithm. Experimental results show over 85% improvement in computation time compared to solving the same problems using the previous randomized approach. We also demonstrate that the quality of results produce by the proposed algorithm is comparable, and in some cases, better than the results reported in previous works using the same heuristic. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码:132 / 143
页数:12
相关论文
共 29 条
  • [1] Lightweight Hardware Architectures for the Present Cipher in FPGA
    Andres Lara-Nino, Carlos
    Diaz-Perez, Arturo
    Morales-Sandoval, Miguel
    [J]. IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS, 2017, 64 (09) : 2544 - 2555
  • [2] [Anonymous], PICCOLO ULTRALIGHTWE
  • [3] [Anonymous], 2017, NISTIR8114
  • [4] [Anonymous], 1986, TECHNICAL REPORT
  • [5] Banik S., 2015, P CRYPT EPRINT ARCH, V2015, P1142
  • [6] Bogdanov A, 2007, LECT NOTES COMPUT SC, V4727, P450
  • [7] BORGHOFF J, 2012, PROC INT CONF THEOR, V7658, P208
  • [8] On the multiplicative complexity of Boolean functions over the basis (Λ,⊕,1)
    Boyar, J
    Peralta, R
    Pochuev, D
    [J]. THEORETICAL COMPUTER SCIENCE, 2000, 235 (01) : 43 - 57
  • [9] Boyar J, 2012, IFIP ADV INF COMM TE, V376, P287
  • [10] Logic Minimization Techniques with Applications to Cryptology
    Boyar, Joan
    Matthews, Philip
    Peralta, Rene
    [J]. JOURNAL OF CRYPTOLOGY, 2013, 26 (02) : 280 - 312