Title :
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
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!)2 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;
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
DOI :
10.1109/APCCAS.2000.913649
