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

Facta Universitatis, Series: Electronics and Energetics

Radomir Stanković¹  Claudio Moraga²  Miloš Radmanović¹ 

[1] Faculty of Electrical Engineering, University of Niš, Niš, Serbia$$;European Centre for Soft Computing, Mieres, Spain, and Department of Computer Science, Technical University of Dortmund, Dortmund, Germany$$

关键词: BiCMOS technology;    Bipolar transistors;    Horizontal Current Bipolar Transistor;    Radio frequency integrated circuits;    Mixer;    High-voltage bipolar transistors.;   

DOI  :  

来源: University of Nis

【 摘 要 】

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.

【 授权许可】

Unknown