期刊名称：Facta universitatis - series: Electronics and Energetics
印刷版ISSN：0353-3670
电子版ISSN：2217-5997
出版年度：2015
卷号：28
期号：4
页码：597-609
DOI：10.2298/FUEE1504597R
出版社：University of Niš
摘要：The autocorrelation of a Boolean function is an important mathematical concept with various applications. It is a kernel of many algorithms with essential applications whose efficiency is directly limited by the time and space complexity of methods for computing the autocorrelation. These limitations, in this paper, can be overcome by computing the autocorrelation using a Shared Multi-Terminal Binary Decision Diagram (SMTBDD) which is a data structure allowing compact representations of large Boolean functions. The computation is performed in the spectral domain by exploiting the Wiener-Khinchin theorem and the fast calculation algorithms through SMTBDDs. It is necessary to develop a specialized decision diagram package with all the standard BDD operations that supports a fast calculation algorithms through decision diagrams with dynamically resizable terminal nodes. It allows to deal with large integers that appear in computing the autocorrelation coefficients. An experimental evaluation over benchmarks favorably confirms the efficiency of the proposed data structure and related algorithm.
