3 不规则模块的翻转算法
    在SS解码算法中还需将模块翻转以获得更好地摆放位置。由于不规则模块被划分成许多小矩形，翻转时不能简单改变矩形的长宽顺序，而应结合模块区域连接序列进行整体翻转。不同于简单矩形模块只有0°和90°2种状态，而不规则模块要复杂得多，其中包括0°、90°、180°和270° 4种翻转状态，如图3所示。

3.1 180°翻转算法
    180°翻转情况相对较为简单，从图3中可看出180°翻转仅仅是在原始状态的基础上改变了划分的小矩形的上下位置关系，并没有改变这些小矩形的长宽数据，因此只需改变模块区域连接序列中对应组的顺序。设有模块区域连接序列：XXXX0ABCD0XXX0XXX0XXX，要使矩形组ABCD组成的模块进行180°翻转，只需将序列改变为XXXX0DCBA0XXX0XXX0XXX即可，如图4所示。

3.2 90°翻转算法
    90°翻转的情况较为复杂，不仅涉及到模块区域连接序列，而且由于其改变了小矩形的长宽数据，同时要改变模块数据序列。首先要对模块重新进行划分：
    (1)在原有模块数据序列中找出长度最小的模块，将其宽加上改组中所有模块宽度，作为一个新的小矩形。
    (2)找出原有模块数据序列中长度第2小的模块，将其长减去(1)中矩形的长作为其新的长度，其宽改为原来宽度加上改组中所有模块宽度再减去(1)中长度最小的模块的宽度。
    (3)重复以上步骤直至所有矩形被处理。
    (4)将修改过的模块数据序列中长宽数据对换。
    (5)修改模块区域连接序列使其与现在的模块数据序列相对应。
    模块90°翻转如图5所示。

3.3 270°翻转算法
    270°相当于在90°翻转的基础上再次180°翻转，因此只需在3.2节的基础运用3.1节的算法进行翻转即可。
    本文在SS序列算法的基础上进行了改进，使原有算法在只能进行简单矩形模块布图的基础上，可以对一些复杂的不规则模块进行布图，大大增加了SS算法的实用能力和处理复杂模块的能力，为将来集成电路布图的灵活多变打下了基础。本文提出了新的模块划分概念，并提出了模块区域连接算法、不规则模块翻转算法、模块区域连接序列等新的算法和概念。充实了SS序列算法，增加了SS序列算法的功能，大大改进了SS算法的实用性和处理复杂情况的应变能力。

上一页  [1] [2]