EQ-Sequences for Coding Floorplans

Hua-An ZHAO  Chen LIU  Yoji KAJITANI  Keishi SAKANUSHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A   No.12   pp.3233-3243
Publication Date: 2004/12/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Floorplan
Keyword: 
floorplan,  placement,  VLSI CAD,  Q-sequence,  

Full Text: PDF>>
Buy this Article




Summary: 
A floorplan specifies the layout of modules in very large scale integration (VLSI) design, and a new code, called the EQ-sequence, for representing a floorplan is presented in this paper. The EQ-sequence is based on a Q-sequence. The EQ-sequence can preserve the adjacent relationships of rooms on a floorplan, but the Q-sequence cannot. The algorithms for encoding, moving and decoding of an EQ-sequence are introduced. With the EQ-sequence, we can check whether two modules abut each other on a floorplan. It has been proved that any floorplan of n rooms is uniquely encoded by an EQ-sequence and any EQ-sequence is uniquely decoded to a floorplan, both in O(n) time.