Options
1992
Book Article
Titel
Recursive VLSI - design and fractals
Abstract
It is shown that recursive techniques in VLSI-design lead in a very natural way to certain fractals which reflect the asymptotic geometric properties of the design if its degree of recursiveness tends to infinity. The major mathematical background behind this is a generalization of a technique introduced by Hutchinson. Let Gamma is equal (V,E,o,t) be a finite directed graph. A contraction functor over Gamma is a mapping S, which maps edges u e v of Gamma to contractions Se in a metric space (X,d). A family K is equal (Ku/u Epsilon V) of closed bounded sets of X is called to be an invariant with respect to S if the union of all Se(Kv) is equal to Ku. It is proved that - every recursive VLSI-design defines a contraction functor, - contraction functors admit invariants, - There is only a finite number of invariants to a given contraction functor, - invariants are fractals and their Hausdorff-dimension can be computed, - recursive algorithms can draw good approximations of invariants of co ntraction functors, - the results of Hutchinson can be obtained as a special case where Gamma has one node only.
Language
English