An Efficient Decoding Method of Sequence-Pair with Reduced Redundancy(Special Section on VLSI Design and CAD Algorithms)

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 2002-12-01

著者

• FUJIYOSHI Kunihiro

  Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology

• Kodama C

  Tokyo Univ. Agriculture & Technol. Koganei‐shi Jpn

• Kodama Chikaaki

  Department Of Electric And Electronic Engineering Tokyo University Of Agriculture & Technology

• Fujiyoshi Kunihiro

  Department Of Electrical And Electronic Engineering Tokyo University Of Agriculture & Technology

関連論文

• An Improved Method of Convex Rectilinear Block Packing Based on Sequence-Pair(Place and Routing)(VLSI Design and CAD Algorithms)
• The O-Sequence : Representation of 3D-Dissection
• An Efficient Decoding Method of Sequence-Pair with Reduced Redundancy(Special Section on VLSI Design and CAD Algorithms)
• A Graph Based Soft Module Handling in Floorplan(Floorplan and Placement, VLSI Design and CAD Algorithms)
• Minimizing the Number of Empty Rooms on Floorplan by Dissection Line Merge(Programmable Logic, VLSI, CAD and Layout, Recent Advances in Circuits and Systems-Part 1)
• Placement with Symmetry Constraints for Analog IC Layout Design Based on Tree Representation

スポンサーリンク