发信人: cgl (老顽童), 信区: ECE
标  题: 数字逻辑功能提取器(8)
发信站: 紫 丁 香 (Mon Oct 12 15:14:48 1998), 转信

                四、功能块的匹配和替换

        功能块制作好以后，就有了一个样本，可以在输入的电路中
寻找同构的子电路，这个过程称为匹配。如果找到实例，功能块中的
每个器件和线网在输入网表中都会有对应的器件或线网，成之为对应
关系。匹配的算法是在样本网表和输入电路的网表中分别作“相同”
的遍历，所谓“相同”即两个当前器件或线网是否匹配。遍历过程中
两个当前器件或线网不匹配时则中止匹配过程，反之建立两个器件或
线网的对应关系，当整个样本网表都已遍历完且没有碰到不匹配，认
为找到一个实例。对输入电路处理一遍后可以找到所有实例。

1、功能块匹配算法：
        1.1、确定初始节点
        1.2、若初始节点为线网，进行线网匹配
        1.3、若初始节点为器件，进行器件匹配

1.2线网匹配算法：
        1、除边界线网外，线网连接数（一个器件的一个引脚为一个连
              接）是否一致；

        2、是否都是VDD或GND，VDD和GND不能和其它线网建立对应
             关系。
        3、若线网已建立对应关系，检查与当前线网对是否相符；
        4、把两个线网的对应关系推入匹配堆栈；
        5、线网所连每个器件是否匹配成功（1.3 ），若都成功返回两个
              线网匹配；
        6、反之从堆栈中弹出并撤消对应关系，返回不匹配。

1.3器件匹配算法：
        1、类型是否一致；
        2、若器件已建立对应关系，检查与当前器件对是否一致；
        3、 把两个器件的对应关系推入匹配堆栈；
        4、相同引脚所连的线网对是否匹配（1.2），若存在等价引脚组
             （如与门的几个  输入端），还要对组内引脚所连线网进行排
              列，看是否存在一个可能匹配。
        5、若存在一个可能匹配，返回两个器件匹配；
        6、反之 从堆栈中弹出并撤消对应关系，返回不匹配。

算法操作过程中用到一个数据结构匹配堆栈，匹配进行到某个线网或器
件时，先假定两个器件或线网可以匹配，把它们的匹配关系推入堆栈，继
续进行后面的遍历和匹配。后建立的对应关系若和以前的对应关系矛盾
（1.2.3和1.3.2），将不再遍历下去，而是从堆栈中弹出自己的对应关系并
回溯到上一节点（器件或线网），试验下一个可能组合（1.2.5和1.3.4）。

--

        老顽童

※ 来源:．紫 丁 香 bbs.hit.edu.cn．[FROM: wb502.hit.edu.cn]