|
Haar Spectral Transform Decision Diagrams
with Exact Algorithm for Minimization of the Number of
Paths
Radomir S. Stankovic, Milena Stankovic, Jaakko Astola*, Karen Egiazarian*
Dept. of Computer Science, Faculty of Electronics, 18 000 Nis, Yugoslavia
TICSP, Tampere University of Technology, Tampere, Finland
mstankovic@elfak.ni.ac.yu, *jta@cs.tut.fi
Abstract
In this paper, we briefly discuss the Haar spectral diagrams (HSDs). Then, we define
the Haar transform decision diagrams (HSTDDs). We show that the exact algorithm
by Karpovsky for minimization of the number of non-zero coeÆcients in the Haar
spectrum can be used for minimization of the number of paths and the number of
nodes in HSTDs. This research was motivated by the following issues.
- Decision diagrams (DDs) are a data structure permitting representation of large
discrete functions efficiently in terms of space and time. The optimization of DD
representation for a given function is an important issue in applications of DDs.
The optimization of DDs aims at the reduction of some basic characteristics of
a DD, for example, the number of nodes (size of the DD), the number of levels
(depth of the DD), the number of paths. However, most of the minimization
algorithms are heuristic. The exact algorithms perform checking of all possible
combinations of parameters permitting reduction of a characteristic of the DD.
- There is apparent a renewed considerable interest in application of discrete Haar
transform in logic design and related areas.
|
