EFFICIENT CALCULATION OF THE AUTOCORRELATION OF BOOLEAN FUNCTIONS WITH THE LARGE NUMBER OF VARIABLES

Miloš Radmanović, Radomir Stanković, Claudio Moraga

DOI Number
-
First page
597
Last page
609

Abstract


The autocorrelation of a Boolean function is animportant mathematical concept with various applications. It is a kernel ofmany algorithms with essential applications whose efficiency is directlylimited by the time and space complexity of methods for computing theautocorrelation. These limitations, in this paper, can be overcome by computingthe autocorrelation through Shared Multi-Terminal Binary Decision Diagram(SMTBDD) that are a data structure allowing compact representations of largeBoolean functions. The computation is performed in the spectral domain byexploiting the Wiener-Khinchin theorem and the fast calculation algorithm throughSMTBDDs. It is necessary to develop a specialized decision diagram package withall the standard BDD operations that support fast calculation algorithm throughdecision diagrams and dynamically resizable terminal nodes allows to deal withlarge integers that appear in computing the autocorrelation coefficients. Anexperimental evaluation over benchmarks, confirmed favorably the efficiency ofthe proposed data structure and related algorithms.

Full Text:

PDF

References


M. G. Karpovsky, Finite Orthogonal Series in the Design of Digital Devices, New York: Wiley, 1976.

M. G. Karpovsky, R. S. Stanković, and J. T. Astola, “Spectral Techniques for Design and Testing of Computer Hardware”, In Proc. 1st Int. Workshop on Spectral Techniques and Logical Design for Future Digital Systems, pp. 9-43, 2000.

J. E. Rice, and J. C. Muzio, “On the Use of Autocorrelation Coefficients in the Identification of Three-level Decompositions”, In Proc. IEEE/ACM Int. Workshop on Logic Synthesis, pp. 187-191, 2003.

O. Keren, I. Levin, and R. S. Stanković, “Linearization of Logical Functions Defined by a Set of Orthogonal Terms - Theoretical Aspects”, Automation and Remote Control, vol. 72, no. 3, pp. 615-625, 2011.

O. Keren, and I. Levin, “Linearization of Multi-Output Logic Functions by Ordering of the Autocorrelation Values”, Facta Univ. Ser.: Elec. Energ., vol. 20, No. 3, pp. 479-498, Dec. 2007.

J. E. Rice, M. Serra, and J. C. Muzio, “The Use of Autocorrelation Coefficient for Variable Ordering for ROBDDs”, In Proc. Int. Workshop on Applications of Reed-Muller Expansion in Circuit Design, pp.185-196, 1999.

M. G. Karpovsky, R. S. Stanković, and J. T. Astola, “Reduction of Sizes of Decision Diagrams by Autocorrelation Functions”, IEEE Trans. on Computers, vol. 52, no. 5, pp. 592-606, 2003.

O. Keren, “Reduction of Average Path Length in Binary Decision Diagrams by Spectral Methods”, IEEE Trans. on Computers, vol. 57, no. 4, pp. 520-531, 2008.

O. Keren, I. Levin, and R. S. Stanković, “Determining the Number of Paths in Decision Diagrams by Using Autocorrelation Coefficients”, IEEE Trans. on CAD of Integrated Circuits and Systems, vol. 30, no. 1, pp. 31-44, 2011.

M. G. Karpovsky, and E. S. Moskalev, “Utilization of Autocorrelation Functions for Realization of Systems of Logical Functions”, Automation and Remote Control, vol. 31, no. 2, pp. 243-250, 1970.

R. Ebendt, G. Fey, and R. Drechsler, Advanced BDD Optimization, Netherlands: Springer, 2005.

J. E. Rice, and J. C. Muzio, "Methods for Calculating Autocorrelation Coefficients", In Proc. 4th Workshop on Boolean Problems, pp. 69-76, 2000.

M. Radmanović, R. Stanković, and C. Moraga, “Analysis of Decision Diagram based Methods for the Calculation of the Dyadic Autocorrelation”, Int. Journal of Systemics, Cybernetics and Informatics, pp.11-19, July 2007.

R. S. Stanković, M. Bhattacharaya, and J. T. Astola, “Calculation of Dyadic Autocorrelation Through Decision Diagrams”, In Proc. European Conf. Circuit Theory and Design (ECCTD’01), pp. 28-31, 2001.

G. Janssen, “A Consumer Report on BDD Packages”, In Proc. 16th Symposium on Integrated Circuits and Systems Design, pp. 217-223, 2003.

E. M. Clarke, K. L. McMillan, X. Zhao, and M. Fujita, “Spectral Transforms for Extremely Large Boolean Functions”, In Proc. IFIP WG 10.5 Workshop on Applications of the Reed-Muller Expression in Circuit Design, pp. 86-90, 1993.

K. S. Brace, R. L. Rudell, and R. E. Bryant, “Efficient Implementation of a BDD Package”, In Proc. 27th Design Automation Conf., pp. 40-45, 1990.

G. Janssen, “Design of a Pointerless BDD Package”, In Proc. 10th Int. Workshop on Logic and Synthesis, pp. 310-315, 2001.

M. Thornton, and R. Drechsler, “Spectral Decision Diagrams Using Graph Transformations”, In Proc. Design, Automation and Test in Europe Conf. and Exhibition, pp. 713-717, 2001.

F. Somenzi, “Efficient Manipulation of Decision Diagram”, Int. Journal on Software Tools for Technology Transfer, vol. 3, no. 2, pp. 171-181, 2001.

S. N. Yanushkevich, D. M. Miller, V. P. Shmerko, and R. S. Stanković, Decision Diagram Techniques for Micro- and Nanoelectronic Design Handbook, CRC Press, 2006.

T. Sasao, and M. Fujita, Representations of Discrete Functions, Boston: Kluwer Academic Publishers, 1996.

P. Dziurzanskii, V. P. Shmerko, and S. N. Yanushkevich, “Representation of Logical Circuits by Linear Decision Diagrams with Extension to Nanostructures”, Automation and Remote Control, vol. 65, no. 6, pp. 920-937, 2004.

D. Grobe and R. Drechsler, “BDD-based Verification of Scalable Designs”, Facta Univ. Ser.: Elec. Energ., vol. 20, No. 3, pp. 367-379, Dec. 2007.

E. M. Clarke, M. Fujita, P. C. McGeer, K. McMillan, J. C. Yang, and X. Zhao, “Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure For Matrix Representation", in Proc. Int. Workshop on Logic Synthesis, vol. 6a, pp. 1-15, 1993.

R. S. Stanković, and B. Falkowski, “Spectral Transform Calculation through Decision Diagrams”, VLSI Design, vol. C-14, no.1, pp. 5-12, 2002.

G. D. Hachtel, and F. Somenzi, Logic Synthesis and Verification Algorithms, Norwell : Kluwer Academic Publishers, 1996.

J. V. Sanghavi, R. K. Ranjan, R. K., Brayton, and A. Sangiovanni-Vincentelli, A., “High Performance BDD Package By Exploiting Memory Hierarchy”, In Proc. 33rd IEEE/ACM Design Automation Conference (DAC’96), pp. 635-640, 1996.

H. Hasan Babu, and T. Sasao, “Shared Multi-Terminal Binary Decision Diagrams for Multiple-Output Functions”, IEICE Trans. on Fundamentals, vol. E81-A, no. 12, pp. 2545-2553, 1998.

F. Brglez, “The benchmark archives at CBL - ACM/SIGDA benchmarks”, Nort Carolina State University, 2011, http://www.cbl.ncsu.edu/benchmarks.

R. Rudell, Espresso Misc. Reference Manual Pages, Berkeley University of California, 1993.


Refbacks

  • There are currently no refbacks.


ISSN: 0353-3670 (Print)

ISSN: 2217-5997 (Online)

COBISS.SR-ID 12826626