COMPACT XOR-BI-DECOMPOSITION FOR LATTICES OF BOOLEAN FUNCTIONS

Bernd Steinbach, Christian Posthoff

DOI Number
10.2298/FUEE1802223S
First page
223
Last page
240

Abstract


Bi-Decomposition is a powerful approach for the synthesis of multi-level combinational circuits because it utilizes the properties of the given functions to find small circuits, with low power consumption and low delay. Compact bi-decompositions restrict the variables in the support of the decomposition functions as much as possible. Methods to find compact AND-, OR-, or XOR-bi-decompositions for a given completely specified function are well known.

Lattices of Boolean Functions significantly increase the possibilities to synthesize a minimal circuit. However, so far only methods to find compact AND- or OR-bidecompositions for lattices of Boolean functions are known. This gap, i.e., a method to find a compact XOR-bi-decomposition for a lattice of Boolean functions, has been closed by the approach suggested in this paper.


Keywords

synthesis, combinational circuit, lattice of Boolean functions, XOR-bi-decomposition, Boolean Differential Calculus, derivative operations.

Full Text:

PDF

References


D. Bochmann, F. Dresig, and B. Steinbach. “A New Decomposition Method for Multilevel Circuit Design”. In: Proceedings of the Conference on European Design Automation. EDAC ’91. Amsterdam, The Netherlands: IEEE Computer Society, 1991, pp. 374–377.

T. Le. “Testbarkeit kombinatorischer Schaltungen - Theorie und Entwurf”. written in German, English title: Testability of Combinational Circuits - Theory and Design. PhD thesis. TU Karl-Marx-Stadt, Germany, 1989.

C. Posthoff and B. Steinbach. Logic Functions and Equations – Binary

Models for Computer Science. Dordrecht, The Netherlands: Springer, 2004.

B. Steinbach and C. Posthoff. Boolean Differential Calculus. Synthesis Lecturers on Digital Circuits and Systems 52. San Rafael, CA, USA: Morgan & Claypool, 2017.

A. Mishchenko, B. Steinbach, and M. Perkowski. “An Algorithm for Bidecomposition of Logic Functions”. In: Proceedings of the 38th Annual Design Automation Conference. DAC ’01. Las Vegas, Nevada, USA: ACM,

, pp. 103–108.

B. Steinbach. “Vectorial Bi-Decompositions of Logic Functions”. In: Proceedings of the Reed-MullerWorkshop 2015. RM 4.Waterloo, Canada, 2015.

B. Steinbach and C. Posthoff. “Vectorial Bi-Decompositions for Lattices of Boolean Functions”. In: Proceedings of the 12th International Workshops on Boolean Problems. IWSBP. Freiberg, Germany: Freiberg University of Mining and Technology, 2016, pp. 93–104.

A. Thayse. “Boolean Differential Calculus”. In: Philips Research Reports 26 (1971). R 764, pp. 229–246.

M. Davio and A. Thayse. “Boolean Differential Calculus and its Application to Switching Theory”. In: IEEE Transactions on Computes 22.4 (1973), pp. 409–420.

B. Steinbach and C. Posthoff. Logic Functions and Equations - Examples and Exercises. Springer Science + Business Media B.V., 2009.

B. Steinbach and C. Posthoff. “Boolean Differential Calculus - Theory and Applications”. In: Journal of Computational and Theoretical Nanoscience 7.6 (2010), pp. 933–981.

B. Steinbach and C. Posthoff. “Boolean Differential Calculus”. In: Progress in Applications of Boolean Functions. Synthesis Lecturers on Digital Circuits and Systems 26. San Rafael, CA, USA: Morgan & Claypool, 2010, pp. 55–78.

T. Sasao and J. Butler. “On Bi-Decompositions of Logic Functions”. In: 6th International Workshop on Logic & Synthesis. IWLS. Granlibakken Resort - Tahoe City, CA, USA, 1997, pp. 1–6.

M. Choudhury and K. Mohanram. “Bi-Decomposition of Large Boolean Functions Using Blocking Edge Graphs”. In: 2010 IEEE/ACM International Conference on Computer-Aided Design. ICCAD. 2010, pp. 586–591.

D. Cheng and X. Xu. “Bi-Decomposition of Logical Mappings via Semi-

Tensor Product of Matrices”. In: Automatica 49.7 (2013), pp. 51–76.

B. Steinbach. “Generalized Lattices of Boolean Functions Utilized for Derivative Operations”. In: Materiały konferencyjne KNWS’13. KNWS ’13. Łag ´ow, Poland, 2013, pp. 1–17.

B. Steinbach. “Derivative Operations for Lattices of Boolean Functions”. In: Proceedings of the Reed-Muller Workshop 2013. RM ’13. Toyama, Japan, 2013, pp. 110–119.

B. Steinbach and A. Wereszczynski. “Synthesis of Multi-Level Circuits Using EXOR-Gates”. In: IFIP WG 10.5 - Workshop on Applications of the

Reed-Muller Expansion in Circuit Design. Chiba - Makuhari, Japan, 1995,

pp. 161–168.

B. Steinbach. “XBOOLE - A Toolbox for Modelling, Simulation, and Analysis of Large Digital Systems”. In: Systems Analysis and Modelling Simulation 9.4 (1992), pp. 297–312.

B. Steinbach and M.Werner. “XBOOLE-CUDA - Fast Calculations of Large Boolean Problems on the GPU”. In: Problems and New Solutions in the Boolean Domain. Ed. by B. Steinbach. Newcastle upon Tyne, UK: Cambridge Scholars Publishing, 2016, pp. 117–149.


Refbacks

  • There are currently no refbacks.


ISSN: 0353-3670 (Print)

ISSN: 2217-5997 (Online)

COBISS.SR-ID 12826626