Authors: Janković, Dragan
Stanković, Radomir 
Drechsler, Rolf
Title: Decision diagram method for calculation of pruned Walsh transform
Journal: IEEE Transactions on Computers
Volume: 50
Issue: 2
First page: 147
Last page: 157
Issue Date: 1-Jan-2001
Rank: M21
ISSN: 0018-9340
DOI: 10.1109/12.908990
Abstract: 
Discrete Walsh transform is an orthogonal transform often used in spectral methods for different applications in signal processing and logic design. FFT-like algorithms make it possible to efficiently calculate the discrete Walsh spectrum. However, for their exponential complexity, these algorithms are practically unsuitable for large functions. For this reason, a Binary Decision Diagram (BDD) based recursive method for Walsh spectrum calculation has been introduced in 4. A disadvantage of this algorithm is that the resulting Multi-Terminal Binary Decision Diagram (MTBDD) representing the Walsh spectrum for f can be large for some functions. Another disadvantage turns out if particular Walsh coefficients are to be computed separately. The algorithm always calculates the entire spectrum and, therefore, it is rather inefficient for applications where a subset of Walsh spectral coefficients, i.e., the pruned Walsh spectrum, is required. In this paper, we propose another BDD-based method for Walsh spectrum calculation adapted for application where the pruned Walsh spectrum is needed. The method takes advantage of the property that, for most switching functions, the size of a BDD for f is usually quite a bit smaller than the size of the MTBDD for the Walsh spectrum. In our method, a MTBDD representing the Walsh spectrum is not constructed. Instead, two additional fields are assigned to each node in the BDD for the processed function f. These fields are used to store the results of intermediate calculations. Pairs of spectral coefficients are calculated and stored in the fields assigned to the root node. Therefore, the calculation complexity of the proposed algorithm is proportional to the size of the BDD for f whose spectrum is calculated. Experimental results demonstrate the efficiency of the approach.
Keywords: BDD | Logic synthesis | Pruned spectrum | Spectral techniques | Walsh
Publisher: IEEE

Show full item record

SCOPUSTM   
Citations

17
checked on Dec 2, 2024

Page view(s)

13
checked on Dec 1, 2024

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.