Extended Boolean algebra for asynchronous quasi-delay-insensitive logic

• Published in: IET circuits, devices & systems devices & systems, 2020-11, Vol.14 (8), p.1201-1213
• Main Authors: Tran, Linh Duc, Chi Pham, Thanh, Kavehei, Omid, Burton, Peter C.M, Matthews, Glenn I
• Format: Article
• Language: English
• Subjects: Algebra; algebraic extension; asynchronous circuits; asynchronous quasi‐delay‐insensitive logic; Boolean; Boolean algebra; Circuits; complete EDA tool support; Conversion tables; Custom design; C‐elements; Data models; delays; Design analysis; digital logic design; dual‐threshold logic; explicit design; expression simplification; extended Boolean algebra; Flow mapping; gate mapping; Hysteresis; hysteretic logic gates; Latches; Logic; Logic circuits; logic description; Logic design; logic gates; mature industrial EDA tool support; Muller C‐element; named completion; NCL; nonconventional hysteretic threshold gates; Null convention logic; null convention logic gates; Operators (mathematics); Power; QDI circuits; QDI design styles; QDI elements; QDI logic; quasidelay‐insensitive circuits; quasidelay‐insensitive logic; Research Article; synchronous paradigms; Threshold gates; Threshold logic; truth tuple
• ISSN: 1751-858X; 1751-8598
• DOI: 10.1049/iet-cds.2020.0062

Asynchronous quasi-delay-insensitive (QDI) circuits have recently become an active research area in digital logic design. In contrast with synchronous paradigms, QDI approaches utilise threshold gates with hysteresis, such as Muller C-element and null convention logic (NCL) gates. However, there are no existing methods to explicitly describe these hysteretic logic gates in Boolean algebra. Therefore, in this study, the authors extend the Boolean algebra with two novel operators, named completion and truth tuple, to enable explicit expressions for all QDI elements such as C-elements, NCL, NCL+, latches and several non-conventional hysteretic threshold gates that they call dual-threshold logic. In addition, they develop a set of 16 laws and theorems for these new operators to create a complete novel algebraic extension for QDI logic. It is demonstrated that the authors' extended algebra is a complete approach for explicit design and analysis of QDI circuits, including logic description, equation formation from truth table, expression simplification and conversion, and even gate mapping and corresponding CMOS implementation. They also provide an analysis and solution for netlist corruption problems during the synthesis process of existing QDI design flows, as well as a complete design example using the extended Boolean algebra with different QDI design styles.