The quarter-state sequence (Q-sequence) to represent the floorplan and applications to layout optimization

Author

Sakanushi, K. ; Kajitani, Yoji

Author_Institution

Dept. of Commun. & Integrated Syst., Tokyo Inst. of Technol., Japan

fYear

2000

fDate

2000

Firstpage

829

Lastpage

832

Abstract

A new data structure “Q-sequence” for representing a floorplan of n rooms is proposed. The Q-sequence is a concatenation of room names and two kinds of positional symbols, totally of length 3n. It is shown that encoding of a given floorplan and decoding to a floorplan are both possible in a linear time of n. An exact counting formula of distinct floorplans is given. Numerical estimation shows that the number is only slightly larger than that of a slicing structure, and far smaller than (n!)² which is the size of the packing solution space by the sequence-pair representation

Keywords

VLSI; circuit layout CAD; circuit optimisation; data structures; decoding; encoding; integrated circuit layout; sequences; Q-sequence data structure; VLSI layout optimization; decoding; floorplan encoding; floorplan representation; positional symbols; quarter-state sequence; Communications technology; Data structures; Decoding; Encoding; Integrated circuit interconnections; Routing; Stochastic processes; Upper bound; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 2000. IEEE APCCAS 2000. The 2000 IEEE Asia-Pacific Conference on

Conference_Location

Tianjin

Print_ISBN

0-7803-6253-5

Type

conf

DOI

10.1109/APCCAS.2000.913649

Filename

913649