IEICE TRANSACTIONS on Fundamentals
An Efficient Decoding Method of Sequence-Pair with Reduced Redundancy
Summary :
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(n2) 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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
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(n2) 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(n2) 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(n2) 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 -
English
