The search functionality is under construction.

The search functionality is under construction.

The sequence-pair was proposed as a representation method of block placement to determine the densest possible placement of rectangular modules in VLSI layout design. A method of achieving bottom left corner packing in *O*(*n*^{2}) time based on a given sequence-pair of *n* rectangles was proposed using horizontal/vertical constraint graphs. Also, a method of determining packing from a sequence-pair in *O*(*n* log *n*) time was proposed. Another method of obtaining packing in *O*(*n* log log *n*) time was recently proposed, but further improvement was still required. In this paper, we propose a method of obtaining packing via the Q-sequence (representation of rectangular dissection) in *O*(*n*+*k*) time from a given sequence-pair of *n* rectangles with *k* subsequences called adjacent crosses, given the position of adjacent crosses and the insertion order of dummy modules into adjacent crosses. The position of adjacent crosses and insertion order of dummy modules can be obtained from a sequence-pair in *O*(*n*+*k*) time using the conventional method. Here, we prove that arbitrary packing can be represented by a sequence-pair, keeping the value of *k* not more than *n*-3. Therefore, we can determine packing from a sequence-pair with *k* of *O*(*n*) in linear time using the proposed method and the conventional method.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.12 pp.2785-2794

- Publication Date
- 2002/12/01

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)

- Category
- Physical Design

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Chikaaki KODAMA, Kunihiro FUJIYOSHI, "An Efficient Decoding Method of Sequence-Pair with Reduced Redundancy" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 12, pp. 2785-2794, December 2002, doi: .

Abstract: The sequence-pair was proposed as a representation method of block placement to determine the densest possible placement of rectangular modules in VLSI layout design. A method of achieving bottom left corner packing in *O*(*n*^{2}) time based on a given sequence-pair of *n* rectangles was proposed using horizontal/vertical constraint graphs. Also, a method of determining packing from a sequence-pair in *O*(*n* log *n*) time was proposed. Another method of obtaining packing in *O*(*n* log log *n*) time was recently proposed, but further improvement was still required. In this paper, we propose a method of obtaining packing via the Q-sequence (representation of rectangular dissection) in *O*(*n*+*k*) time from a given sequence-pair of *n* rectangles with *k* subsequences called adjacent crosses, given the position of adjacent crosses and the insertion order of dummy modules into adjacent crosses. The position of adjacent crosses and insertion order of dummy modules can be obtained from a sequence-pair in *O*(*n*+*k*) time using the conventional method. Here, we prove that arbitrary packing can be represented by a sequence-pair, keeping the value of *k* not more than *n*-3. Therefore, we can determine packing from a sequence-pair with *k* of *O*(*n*) in linear time using the proposed method and the conventional method.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_12_2785/_p

Copy

@ARTICLE{e85-a_12_2785,

author={Chikaaki KODAMA, Kunihiro FUJIYOSHI, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={An Efficient Decoding Method of Sequence-Pair with Reduced Redundancy},

year={2002},

volume={E85-A},

number={12},

pages={2785-2794},

abstract={The sequence-pair was proposed as a representation method of block placement to determine the densest possible placement of rectangular modules in VLSI layout design. A method of achieving bottom left corner packing in *O*(*n*^{2}) time based on a given sequence-pair of *n* rectangles was proposed using horizontal/vertical constraint graphs. Also, a method of determining packing from a sequence-pair in *O*(*n* log *n*) time was proposed. Another method of obtaining packing in *O*(*n* log log *n*) time was recently proposed, but further improvement was still required. In this paper, we propose a method of obtaining packing via the Q-sequence (representation of rectangular dissection) in *O*(*n*+*k*) time from a given sequence-pair of *n* rectangles with *k* subsequences called adjacent crosses, given the position of adjacent crosses and the insertion order of dummy modules into adjacent crosses. The position of adjacent crosses and insertion order of dummy modules can be obtained from a sequence-pair in *O*(*n*+*k*) time using the conventional method. Here, we prove that arbitrary packing can be represented by a sequence-pair, keeping the value of *k* not more than *n*-3. Therefore, we can determine packing from a sequence-pair with *k* of *O*(*n*) in linear time using the proposed method and the conventional method.},

keywords={},

doi={},

ISSN={},

month={December},}

Copy

TY - JOUR

TI - An Efficient Decoding Method of Sequence-Pair with Reduced Redundancy

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 2785

EP - 2794

AU - Chikaaki KODAMA

AU - Kunihiro FUJIYOSHI

PY - 2002

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E85-A

IS - 12

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - December 2002

AB - The sequence-pair was proposed as a representation method of block placement to determine the densest possible placement of rectangular modules in VLSI layout design. A method of achieving bottom left corner packing in *O*(*n*^{2}) time based on a given sequence-pair of *n* rectangles was proposed using horizontal/vertical constraint graphs. Also, a method of determining packing from a sequence-pair in *O*(*n* log *n*) time was proposed. Another method of obtaining packing in *O*(*n* log log *n*) time was recently proposed, but further improvement was still required. In this paper, we propose a method of obtaining packing via the Q-sequence (representation of rectangular dissection) in *O*(*n*+*k*) time from a given sequence-pair of *n* rectangles with *k* subsequences called adjacent crosses, given the position of adjacent crosses and the insertion order of dummy modules into adjacent crosses. The position of adjacent crosses and insertion order of dummy modules can be obtained from a sequence-pair in *O*(*n*+*k*) time using the conventional method. Here, we prove that arbitrary packing can be represented by a sequence-pair, keeping the value of *k* not more than *n*-3. Therefore, we can determine packing from a sequence-pair with *k* of *O*(*n*) in linear time using the proposed method and the conventional method.

ER -