Vol.8, No 1, 2009 pp. 89 - 97
UDC
519.115.4 681.3.042
CALCULATION OF DYADIC CONVOLUTION TROUGH BYNARY DECISION DIAGRAM
Miloš M. Radmanović
Faculty of Electronic Engineering Niš, Serbia
Abstract.
Calculation of a function’s dyadic convolution coefficients is usually done by brute force method of the defining equation. This method requires time exponential in the number of function’s inputs to calculate each coefficient. In this paper, a method for more efficient calculation of a function’s convolution coefficients is presented. The method is based on Reduced Ordered Shared Binary Decision Diagram (ROSBDD) representations of the functions. Advantages and disadvantages of both methods are experimentally tested and discussed.
Key Words:
Boolean function, dyadic convolution, ROBDD, BDD package.
RAČUNANJE DIJADIČKE KONVOLUCIJE PREKO BINARNIH DIJAGRAMA ODLUČIVANJA
Za računanje diadičkih konvolucionih koeficijenata funkcija se obično koristii metooda iscrpljivanja korišćenjem definicije konvolucije. Za računanje jednog koeficijenta, vreme izvršavanja ove metode je eksponencijalno zavisno od broja ulaznih promenljivih funkcije. U ovom radu je predstavljen metod za efikasnije računanje konvucijonih koeficijenata funkcija. Metod je zasnovan na predstavljanju funkcije preko redukovanih uređenih razdeljenih binarnih dijagramima odlučivanja (ROSBDD). Prednosti i nedostaci oba metoda su eksperimentalno testirane i razmotrene.
Ključne reči:
Bulove funkcije, diadička konvolucija, ROBDD, BDD paket
