This paper describes a method for the efficient computation of the total autocorrelation for large multiple-output Boolean functions over a Shared Binary Decision Diagram (SBDD). The existing methods for computing the total autocorrelation over decision diagrams are restricted to single output functions and in the case of multiple-output functions require repeating the procedure k times where k is the number of outputs. The proposed method permits to perform the computation in a single traversal of SBDD. In that order, compared to standard BDD packages, we modified the way of traversing sub-diagrams in SBDD and introduced an additional memory function kept in the hash table for storing results of the computation of the autocorrelation between two subdiagrams in the SBDD. Due to that, the total amount of computations is reduced which makes the method feasible in practical applications. Experimental results over standard benchmarks confirm the efficiency of the method.
Miloš RADMANOVIC
University of Ni s
Radomir S. STANKOVIC
University of Ni s
Claudio MORAGA
European Centre for Soft Computing,Technical University of Dortmund
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Miloš RADMANOVIC, Radomir S. STANKOVIC, Claudio MORAGA, "Computation of the Total Autocorrelation over Shared Binary Decision Diagrams" in IEICE TRANSACTIONS on Fundamentals,
vol. E97-A, no. 5, pp. 1140-1143, May 2014, doi: 10.1587/transfun.E97.A.1140.
Abstract: This paper describes a method for the efficient computation of the total autocorrelation for large multiple-output Boolean functions over a Shared Binary Decision Diagram (SBDD). The existing methods for computing the total autocorrelation over decision diagrams are restricted to single output functions and in the case of multiple-output functions require repeating the procedure k times where k is the number of outputs. The proposed method permits to perform the computation in a single traversal of SBDD. In that order, compared to standard BDD packages, we modified the way of traversing sub-diagrams in SBDD and introduced an additional memory function kept in the hash table for storing results of the computation of the autocorrelation between two subdiagrams in the SBDD. Due to that, the total amount of computations is reduced which makes the method feasible in practical applications. Experimental results over standard benchmarks confirm the efficiency of the method.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1140/_p
Copy
@ARTICLE{e97-a_5_1140,
author={Miloš RADMANOVIC, Radomir S. STANKOVIC, Claudio MORAGA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Computation of the Total Autocorrelation over Shared Binary Decision Diagrams},
year={2014},
volume={E97-A},
number={5},
pages={1140-1143},
abstract={This paper describes a method for the efficient computation of the total autocorrelation for large multiple-output Boolean functions over a Shared Binary Decision Diagram (SBDD). The existing methods for computing the total autocorrelation over decision diagrams are restricted to single output functions and in the case of multiple-output functions require repeating the procedure k times where k is the number of outputs. The proposed method permits to perform the computation in a single traversal of SBDD. In that order, compared to standard BDD packages, we modified the way of traversing sub-diagrams in SBDD and introduced an additional memory function kept in the hash table for storing results of the computation of the autocorrelation between two subdiagrams in the SBDD. Due to that, the total amount of computations is reduced which makes the method feasible in practical applications. Experimental results over standard benchmarks confirm the efficiency of the method.},
keywords={},
doi={10.1587/transfun.E97.A.1140},
ISSN={1745-1337},
month={May},}
Copy
TY - JOUR
TI - Computation of the Total Autocorrelation over Shared Binary Decision Diagrams
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1140
EP - 1143
AU - Miloš RADMANOVIC
AU - Radomir S. STANKOVIC
AU - Claudio MORAGA
PY - 2014
DO - 10.1587/transfun.E97.A.1140
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2014
AB - This paper describes a method for the efficient computation of the total autocorrelation for large multiple-output Boolean functions over a Shared Binary Decision Diagram (SBDD). The existing methods for computing the total autocorrelation over decision diagrams are restricted to single output functions and in the case of multiple-output functions require repeating the procedure k times where k is the number of outputs. The proposed method permits to perform the computation in a single traversal of SBDD. In that order, compared to standard BDD packages, we modified the way of traversing sub-diagrams in SBDD and introduced an additional memory function kept in the hash table for storing results of the computation of the autocorrelation between two subdiagrams in the SBDD. Due to that, the total amount of computations is reduced which makes the method feasible in practical applications. Experimental results over standard benchmarks confirm the efficiency of the method.
ER -