Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Recursive VLSI - design and fractals

: Budach, L.

Sydow, A.:
Computational systems analysis - topics and trends
Amsterdam: North-Holland Publishing, 1992
ISBN: 0-444-89190-0
Aufsatz in Buch
Fraunhofer ISST ()
dimension; fractal; geometry; VLSI

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.