Boolean logic optimization in majority-inverter graphs
US10380309B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 1, 2015 |
| Grant date | Aug 13, 2019 |
| Priority date | — |
| Expiry date | Jun 1, 2035 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/327
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
We present a Boolean logic optimization framework based on Majority-Inverter Graph (MIG). An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented edges. Current MIG optimization is supported by a consistent algebraic framework. However, when algebraic methods cannot improve a result quality, stronger Boolean methods are needed to attain further optimization. For this purpose, we propose MIG Boolean methods exploiting the error masking property of majority operators. Our MIG Boolean methods insert logic errors that strongly simplify an MIG while being successively masked by the voting nature of majority nodes. Thanks to the data-structure/methodology fitness, our MIG Boolean methods run in principle as fast as algebraic counterparts. Experiments show that our Boolean methodology combined with state-of-art MIG algebraic techniques enable superior optimization quality. For example, when targeting depth reduction, our MIG optimizer transforms a ripple carry adder into a carry look-ahead one. Considering the set of IWLS'05 (arithmetic intensive) benchmarks, our MIG optimizer reduces by 17.98% (26.69%) the logic network depth while also enhanc…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.