发明创造名称：版图设计规则文件中图层关系的可视化分析方法
外观设计名称：
决定号：197339
决定日：2019-12-04
委内编号：1F275814
优先权日：
申请（专利）号：201410480676.5
申请日：2014-09-19
复审请求人：北京华大九天软件有限公司
无效请求人：
授权公告日：
审定公告日：
专利权人：
主审员：邓隽
合议组组长：赵小宁
参审员：张一良
国际分类号：G06F17/50
外观设计分类号：
法律依据：专利法第22条第3款
决定要点
：如果一项权利要求所要求保护的技术方案与作为最接近的现有技术的对比文件相比存在区别技术特征，并且现有技术中没有给出将上述区别技术特征应用到该对比文件以解决其存在的技术问题的启示，且该区别技术特征的引入使该权利要求的整体技术方案相对于现有技术而言具有有益的技术效果，那么该权利要求所要保护的技术方案具有突出的实质性特点和显著的进步，从而具备创造性。
全文：
本复审请求涉及申请号为201410480676.5，名称为“版图设计规则文件中图层关系的可视化分析方法”的发明专利申请（下称“本申请”）。申请人为北京华大九天软件有限公司。本申请的申请日为2014年09月19日，公开日为2016年03月23日。
经实质审查，国家知识产权局原审查部门于2019年01月09日发出驳回决定，以权利要求1-5不符合专利法第22条第3款规定的创造性为由驳回了本申请，其具体理由是：权利要求1-5相对于对比文件3（CN 1722144 A，公开日为2006年01月18日）、对比文件2（CN 103124279 A，公开日为2013年05月29日）以及本领域公知常识的结合不具备创造性。具体地：权利要求1与对比文件3的区别技术特征是：“（1）该可视化分析方法用于版图中；（2）由用户选择图层，以及生成可视化关系图的过程”。然而上述区别技术特征部分被对比文件2公开，部分属于本领域的公知常识，因此权利要求1的技术方案相对于对比文件3、对比文件2以及本领域公知常识的结合不具备创造性。从属权利要求2-5的附加技术特征部分被对比文件2公开，部分属于本领域的公知常识，因此也不具备创造性。
驳回决定所依据的文本为申请人于申请日2014年09月19日提交的说明书摘要、说明书第1-61段、说明书附图图1-7、摘要附图，2018年04月02日提交的权利要求第1-5项。驳回决定所针对的权利要求书如下：
“1、本发明提供一种版图设计规则文件中图层关系的可视化分析方法，其特征在于：首先解析设计规则文件，得到所有图层之间依赖关系，然后针对用户选择的一个或多个图层，获取与用户选择图层具有依赖关系的图层集合，最后以依赖关系集合中的图层为节点，以图层间的引用关系为边，进行布局布线处理，生成并画出可视化关系图；
所述布局布线操作，其步骤为：
第一步，对节点进行分层，计算边的跨度；
第二步，添加虚拟节点，使得所有边的跨度都变成1；
第三步，优化交叉边，调节各层内节点的相对位置；
第四步，计算节点的中心点坐标；
第五步，画出图形；
所述的添加虚拟节点，使得所有边的跨度都变成1，步骤为：
（a）添加初始虚拟节点：从上往下逐层遍历层内节点的节点输入边，若层Li中节点u的某条节点输入边e
（b）去除冗余虚拟节点：从上往下逐层遍历层内节点，若Li中节点u的节点输入边中存在着两条或多条边的输入节点为虚拟节点，则这些虚拟节点为冗余虚拟节点，合并成一个虚拟节点。
2、权利要求1所述的版图设计规则文件中图层关系的可视化分析方法，其特征在于，所述的对节点进行分层，计算边的跨度，步骤为：
将所有节点分为层艺L1，L2，…LN，有向边e
3、权利要求1所述的版图设计规则文件中图层关系的可视化分析方法，其特征在于，所述的优化交叉边，调节各层内节点的相对位置，步骤为：
（a）做有限轮次双向交替遍历层，对相邻两层做层内节点相对位置预调整；
（b）每次双向交替遍历一轮之后，分析调整前后的交叉点数，若减少则调整并继续遍历，否则就放弃该轮调整并停止优化。
4、权利要求3所述的版图设计规则文件中图层关系的可视化分析方法，其特征在于，所述的层内节点相对位置预调整，步骤为：
（a）根据层遍历的方向，相邻两层，其中一层为固定层，另一层为调整层；
（b）遍历调整层内的每一个节点，分析相邻两个节点位置交换前后的交叉点数是否减少，若减少则调整，否则不调整；
（c）重复遍历节点直到没有新的位置调整发生。
5、权利要求1所述的版图设计规则文件中图层关系的可视化分析方法，其特征在于，所述的计算节点的中心点坐标，步骤为：
根据节点高度、层间间距及层间边的数量，计算出每一层的Y坐标值；
X值计算先是求得基准层，基准层按照层内节点的相对位置给节点布X值，然后从基准层开始，分别向上和向下，做相邻两层的层参照布X值：
（a）求得基准层：遍历所有层，计算层内各节点宽度和最小节点间间距的总和，所有层中，这个总和值最大的层即为基准层；
（b）层参照布X值：以已布局层Li为参照层，当前层Li-1（向上）或Li 1（向下）按照一定的优先级遍历层内所有节点并计算X值；对于当前节点m，首先根据本层内已布局节点位置，预估当前层内节点m的布局范围，然后根据参照层Li层内节点的布局，计算当前层内节点m的理想布局点，最后以布局范围内距离理想布局点最近的点，作为节点X坐标。”
申请人（下称“复审请求人”）对上述驳回决定不服，于2019年03月04日向国家知识产权局提出了复审请求，同时修改了权利要求书，将权利要求2的全部特征加入权利要求1。复审请求人认为：（1）对比文件2涉及的是信息处理领域，其应用在资源信息系统，而本申请应用于集成电路版图设计，两者的技术领域不同。本申请所述的节点为集成电路设计规则文件中用户选择的具有依赖关系的图层，而对比文件2所述的节点为用户输入的资源节点。（2）本申请第一步对节点进行分层，计算边的跨度与对比文件2不同，对比文件2是为每个资源节点分配在资源层次上的位置，两者的技术手段不同。（3）在对比文件2中，如果存在依赖关系的两资源节点所处的层次之间的差距不为1，则两个资源所在层之间的各层上均增加一虚拟节点，使两资源节点通过该虚拟节点相连。本申请是根据节点输入边的跨度决定是否添加初始虚拟节点、去除冗余虚拟节点。而对比文件2是根据两资源节点所处的层次之间的差距决定增加虚拟节点，两者的构思不同。（4）本申请第二步中的“冗余虚拟节点”并不是重复的节点，而是需要一定的评定方式，通过去除冗余虚拟节点，能够得到简化之后的输出图。而对比文件2并没有公开具体的添加虚拟节点的方法，以及去除冗余虚拟节点的步骤，也不存在相应的技术启示。（5）对比文件2的技术方案是通过排序方法，利用所定义的“重心值”排序后进行交叉点的优化。本申请的技术方案是采用线性遍历并通过判定相邻节点交换前后交叉点个数的变化来进行交叉点的优化，无需进行排序。本申请的上述技术手段相比于对比文件2的技术手段更加高效。
复审请求时新修改的权利要求书如下：
“1、一种版图设计规则文件中图层关系的可视化分析方法，其特征在于：首先解析设计规则文件，得到所有图层之间依赖关系，然后针对用户选择的一个或多个图层，获取与用户选择图层具有依赖关系的图层集合，最后以依赖关系集合中的图层为节点，以图层间的引用关系为边，进行布局布线处理，生成并画出可视化关系图；
所述布局布线操作，其步骤为：
第一步，对节点进行分层，计算边的跨度；
第二步，添加虚拟节点，使得所有边的跨度都变成1；
第三步，优化交叉边，调节各层内节点的相对位置；
第四步，计算节点的中心点坐标；
第五步，画出图形；
所述第一步，进一步包括：将所有节点分为层艺L1，L2，…LN，有向边e
所述第二步进一步包括：
（a）添加初始虚拟节点：从上往下逐层遍历层内节点的节点输入边，若层Li中节点u的某条节点输入边e
（b）去除冗余虚拟节点：从上往下逐层遍历层内节点，若Li中节点u的节点输入边中存在着两条或多条边的输入节点为虚拟节点，则这些虚拟节点为冗余虚拟节点，合并成一个虚拟节点。
2、权利要求1所述的版图设计规则文件中图层关系的可视化分析方法，其特征在于，所述的优化交叉边，调节各层内节点的相对位置，步骤为：
（a）做有限轮次双向交替遍历层，对相邻两层做层内节点相对位置预调整；
（b）每次双向交替遍历一轮之后，分析调整前后的交叉点数，若减少则调整并继续遍历，否则就放弃该轮调整并停止优化。
3、权利要求2所述的版图设计规则文件中图层关系的可视化分析方法，其特征在于，所述的层内节点相对位置预调整，步骤为：
（a）根据层遍历的方向，相邻两层，其中一层为固定层，另一层为调整层；
（b）遍历调整层内的每一个节点，分析相邻两个节点位置交换前后的交叉点数是否减少，若减少则调整，否则不调整；
（c）重复遍历节点直到没有新的位置调整发生。
4、权利要求1所述的版图设计规则文件中图层关系的可视化分析方法，其特征在于，所述的计算节点的中心点坐标，步骤为：
根据节点高度、层间间距及层间边的数量，计算出每一层的Y坐标值；
X值计算先是求得基准层，基准层按照层内节点的相对位置给节点布X值，然后从基准层开始，分别向上和向下，做相邻两层的层参照布X值：
（a）求得基准层：遍历所有层，计算层内各节点宽度和最小节点间间距的总和，所有层中，这个总和值最大的层即为基准层；
（b）层参照布X值：以已布局层Li为参照层，当前层Li-1（向上）或Li 1（向下）按照一定的优先级遍历层内所有节点并计算X值；对于当前节点m，首先根据本层内已布局节点位置，预估当前层内节点m的布局范围，然后根据参照层Li层内节点的布局，计算当前层内节点m的理想布局点，最后以布局范围内距离理想布局点最近的点，作为节点X坐标。”
经形式审查合格，国家知识产权局于2019年03月29日依法受理了该复审请求，并将其转送至原审查部门进行前置审查。
原审查部门在前置审查意见书中认为：（1）对于复审请求人陈述的上述区别（1），对比文件2所要解决的技术问题是如何处理节点间资源的信息使得资源间依赖关系更直观，这与本申请所要解决的技术问题一致，因此在面对本申请所要解决的技术问题时，本领域技术人员有动机从相似或相近的技术领域去寻找相应的方法，因此对比文件2给出了技术启示。（2）对于复审请求人陈述的上述区别（2）-（4），权利要求1中是以依赖关系集合中的图层为节点，以图层间的引用关系为边，而对比文件2公开了获取节点之间的依赖关系，根据依赖关系为节点分配层次的位置关系，即相当于对节点进行分层，层次之间的差距即相当于边的跨度。对比文件2还公开了根据资源节点所在层次之间的差距是否为1来决定是否增加虚拟节点，即相当于根据边的跨度来添加虚拟节点。而在对比文件2公开增加虚拟节点的前提下，删除冗余节点是本领域的惯用技术手段。（3）对于复审请求人陈述的上述区别（5），对比文件2公开了通过遍历的方式对节点位置进行位置调整，并根据交叉点个数的变化来进行优化，其为了优化精确还公开了重心值排序后进行交叉点的优化，而为了节省计算量以达到计算高效的效果，由对比文件2公开的内容，本领域技术人员能够想到不进行排序，仅依据交叉点个数的变化来进行优化。综上所述，修改后的权利要求仍不具备创造性，因而坚持原驳回决定。
随后，国家知识产权局成立合议组对本案进行审理。
经过充分阅卷并合议，合议组认为本案事实已经清楚，可以作出审查决定。
二、决定的理由
1、 审查文本的认定
复审请求人在提出复审请求时修改了权利要求书，形成新的权利要求第1-4项。经审查，所作的修改符合专利法第33条和专利法实施细则第61条第1款的规定。本复审请求审查决定所依据的文本为：申请日2014年09月19日提交的说明书摘要、说明书第1-61段、说明书附图图1-7、摘要附图，2019年03月04日提交的权利要求第1-4项。
2、 具体理由的阐述
专利法第22条第3款规定：“创造性，是指与现有技术相比，该发明具有突出的实质性特点和显著的进步，该实用新型有实质性特点和进步”。
如果一项权利要求所要求保护的技术方案与作为最接近的现有技术的对比文件相比存在区别技术特征，并且现有技术中没有给出将上述区别技术特征应用到该对比文件以解决其存在的技术问题的启示，且该区别技术特征的引入使该权利要求的整体技术方案相对于现有技术而言具有有益的技术效果，那么该权利要求所要保护的技术方案具有突出的实质性特点和显著的进步，从而具备创造性。
本复审决定引用的对比文件与驳回决定所引用的对比文件相同，即：
对比文件2：CN 103124279 A，公开日为2013年05月29日；
对比文件3：CN 1722144 A，公开日为2006年01月18日，并作为与本申请最接近的现有技术。
（2-1）权利要求1具备专利法第22条第3款规定的创造性。
权利要求1请求保护一种版图设计规则文件中图层关系的可视化分析方法。对比文件3公开了一种设计和制造LSI的系统和方法，其中具体公开了如下技术特征（参见说明书第1页第11-24行，第5页第17-24行）：设计者通过在计算机上定义的多个布图层中设置希望的图案结构的数据来进行LSI设计。数据库10具有布图层定义文件11和设计规则文件12，布图层定义文件11表示在工作存储器20上建立的多个布图层21的定义，设计规则文件12表示多个布图层21的设计规则，所述设计规则详细定义了每个布图层21的最小图案尺寸和最小间隔尺寸以及布图层21之间的位置关系（相当于解析设计规则文件，得到所有图层之间的依赖关系）。
由此可以看到，权利要求1与对比文件3的区别技术特征在于：针对用户选择的一个或多个图层，获取与用户选择图层具有依赖关系的图层集合，以依赖关系集合中的图层为节点，以图层间的引用关系为边，进行布局布线处理，生成并画出可视化关系图；所述布局布线操作，其步骤为：第一步，对节点进行分层，计算边的跨度；所述第一步进一步包括：将所有节点分为层艺L1，L2，…LN，有向边e
基于上述区别技术特征，权利要求1的技术方案实际要解决的技术问题是：如何对版图进行布局布线处理并画出可视化关系图。
对于上述区别技术特征，对比文件2公开了一种资源信息的输出方法和系统，其中具体公开了如下技术特征（参见说明书第0014-0051段，说明书附图图1-4）：步骤101，获取每个资源节点与系统中其他资源节点在资源上的依赖关系；步骤102，为所述每个资源节点分配在资源层次的位置（相当于对节点进行分层，将所有节点分为层艺L1，L2，…LN），其中位于第i 1个层次的资源节点的资源依赖位于层次为小于或等于第i个的资源节点的资源；步骤103，获取存在依赖关系的两资源节点所处的层次之间的差距为1的一组资源节点，如果存在依赖关系的两资源节点所处的层次之间的差距不为1（隐含公开计算边的跨度），则在两个资源所在层之间的各层上均增加一虚拟节点（相当于添加初始虚拟节点，使得所有边的跨度都变成1，以及若层Li中节点u的某条节点输入边e
由此可见，在对比文件2中，没有公开：（1）针对用户选择的一个或多个图层，获取与用户选择图层具有依赖关系的图层集合，以依赖关系集合中的图层为节点，以图层间的引用关系为边，进行布局布线处理；（2）去除冗余虚拟节点：从上往下逐层遍历层内节点，若Li中节点u的节点输入边中存在着两条或多条边的输入节点为虚拟节点，则这些虚拟节点为冗余虚拟节点，合并成一个虚拟节点；以及（3）调节各层内节点的相对位置，计算节点的中心点坐标。事实上，对比文件3为了实现减少校验满足设计规则所需的时间和电子束（EB）数据转换处理所需的时间，其所采用的方案的重点在于提供适合于图形转换处理的布图数据，因而其方案需要使用布图层定义文件和设计规则文件来对布图数据进行规则化处理，正是由于使用布图层定义文件和设计规则文件来对布图数据进行规则化处理以提供适合图形转换处理的数据，从而解决了减少校验满足设计规则所需的时间和电子束（EB）数据转换处理所需的时间的技术问题。这与本申请中根据图层之间的依赖关系绘制可视化关系图以帮助用户分析、优化版图图层之间的逻辑结构的思想是完全不同的。因此，对比文件3中没有给出明确的技术指引或教导，使得本领域技术人员在对比文件3的基础上进行改进以形成本申请的根据图层之间的依赖关系绘制可视化关系图以帮助用户分析、优化版图图层之间的逻辑结构的技术方案。另外，对比文件2应用于信息处理领域，其公开的步骤101中，获取的是资源节点之间在资源上的依赖关系，即对比文件2所针对的对象是资源节点；而本申请应用于半导体集成电路版图的自动化设计，针对的对象是版图图层而非资源节点，需要获取的是图层之间的依赖关系而非资源节点之间的依赖关系，采用依赖关系集合中的图层为节点而并非采用信息资源节点作为节点，并且采用图层间的引用关系为边而非资源节点间的依赖关系为边。可见，本申请和对比文件2涉及的技术领域不同，所针对的对象也不同。进而，在本申请的方案中，由于添加虚拟节点会导致存在交叉边，使生成的可视化关系图中的引用关系复杂，因此需要去除由于交叉边导致的冗余虚拟节点以得到简化的可视化关系图，从而使得用户容易分析版图图层之间的逻辑结构。由于对比文件2未公开去除冗余虚拟节点，从而也就不存在简化可视化关系图以便于用户分析版图图层之间的逻辑结构的技术启示。而添加初始虚拟节点和去除冗余虚拟节点作为一个整体，对本申请权利要求1的技术方案至关重要，需要结合其实际所带来的效果整体进行考量，不应被割裂理解和看待，也不能被简单认定为本领域技术人员的公知常识或者容易想到的手段。最后，在对比文件2中，采用基于重心排序的算法对层次中的节点位置进行排序以确保交叉点个数最少；而在本申请的方案中，优化交叉边采用的是调整各层内节点的相对位置的方式，具体是以遍历的方式对相邻两层做层内节点相对位置预调整并分析调整前后的交叉点数，根据所述交叉点数的变化判断是否继续遍历或放弃；即本申请优化交叉边以减少交叉点个数不采用对节点位置排序的方式，与对比文件2所采取的排序方式不同。同时，在对比文件2中，由于采用重心排序的算法来减少交叉点，对所述重心的计算依据的是横向索引之和和邻层节点个数，而在本申请的方案中，计算的是节点的中心点坐标，所述节点中心点坐标的含义和计算方式与上述重心的含义和计算方式均不同，因此，本领域技术人员根据对比文件2公开的重心的定义，无法得到计算节点中心点坐标的技术启示。
综上所述，权利要求1请求保护的技术方案实现了根据图层之间的依赖关系绘制可视化关系图以帮助用户分析、优化版图图层之间的逻辑结构的有益的技术效果。因此，权利要求1请求保护的技术方案相对于对比文件3、对比文件2以及本领域公知常识的结合，对本领域技术人员而言是非显而易见的，具有突出的实质性特点和显著的进步，从而具备专利法第22条第3款规定的创造性。
（2-2）权利要求2-4具备专利法第22条第3款规定的创造性。
从属权利要求2-4直接或间接引用权利要求1，因此，当权利要求1相对于对比文件3、对比文件2以及本领域公知常识的结合具体创造性时，从属权利要求2-4也具备专利法第22条第3款规定的创造性。
3、 对原审查部门驳回决定和前置审查意见书中相关意见的评述
针对原审查部门的意见（参见案由部分），合议组认为：
第一，对比文件3为了实现减少校验满足设计规则所需的时间和电子束（EB）数据转换处理所需的时间，该方案的重点在于提供适合于图形转换处理的布图数据，因而该方案需要使用布图层定义文件和设计规则文件来对布图数据进行规则化处理，正是由于使用布图层定义文件和设计规则文件来对布图数据进行规则化处理以提供适合图形转换处理的数据，从而解决了减少校验满足设计规则所需的时间和电子束（EB）数据转换处理所需的时间的技术问题。这与本申请中根据图层之间的依赖关系绘制可视化关系图以帮助用户分析、优化版图图层之间的逻辑结构的思想是完全不同的。因此，除非对比文件3中给出明确的技术指引或教导，否则本领域技术人员难以想到将对比文件3进行改进以形成本申请的根据图层之间的依赖关系绘制可视化关系图以帮助用户分析、优化版图图层之间的逻辑结构的技术方案。
第二，对比文件2应用于信息处理领域，其公开的步骤101中，获取的是资源节点之间在资源上的依赖关系，即对比文件2所针对的对象是资源节点；而本申请应用于半导体集成电路版图的自动化设计，针对的对象是版图图层而非资源节点，需要获取的是图层之间的依赖关系而非资源节点之间的依赖关系，采用依赖关系集合中的图层为节点而并非采用信息资源节点作为节点，并且采用图层间的引用关系为边而非资源节点间的依赖关系为边；即本申请和对比文件2涉及的技术领域不同，所针对的对象也不同。也就是说，在面对本申请所要解决的技术问题时，本领域技术人员无法从对比文件2获得解决该技术问题的技术启示。
第三，在本申请的方案中，由于添加虚拟节点会导致存在交叉边，使生成的可视化关系图中的引用关系复杂，因此需要去除由于交叉边导致的冗余虚拟节点以得到简化的可视化关系图，从而使得用户容易分析版图图层之间的逻辑结构。由于对比文件2未公开去除冗余虚拟节点，从而也就不存在简化可视化关系图以便于用户分析版图图层之间的逻辑结构的技术启示。此外，添加初始虚拟节点和去除冗余虚拟节点作为一个整体，对本申请权利要求1的技术方案至关重要，需要结合其实际所带来的效果整体进行考量，不应被割裂理解和看待，也不能被简单认定为本领域技术人员的公知常识或者容易想到的手段。
第四，在对比文件2中，采用基于重心排序的算法对层次中的节点位置进行排序以确保交叉点个数最少；而在本申请的方案中，优化交叉边采用的是调整各层内节点的相对位置的方式，具体是以遍历的方式对相邻两层做层内节点相对位置预调整并分析调整前后的交叉点数，根据所述交叉点数的变化判断是否继续遍历或放弃；即本申请优化交叉边以减少交叉点个数不采用对节点位置排序的方式，与对比文件2所采取的排序方式不同。同时，在对比文件2中，由于采用重心排序的算法来减少交叉点，对所述重心的计算依据的是横向索引之和和邻层节点个数，而在本申请的方案中，计算的是节点的中心点坐标，所述节点中心点坐标的含义和计算方式与上述重心的含义和计算方式均不同，因此，本领域技术人员根据对比文件2公开的重心的定义，无法得到计算节点中心点坐标的技术启示。
综上所述，本申请权利要求1-4相对于上述现有证据具备创造性，符合专利法第22条第3款的规定。本复审决定仅针对驳回理由及证据进行审查，至于本申请是否还存在其他缺陷，均留待后续程序继续审查。
根据上述事实和理由，本案合议组依法作出以下审查决定。
三、决定
撤销国家知识产权局于2019年01月09日对本申请作出的驳回决定，由国家知识产权局原审查部门以本复审请求审查决定所依据的文本为基础继续进行审查，即：
复审请求人于申请日2014年09月19日提交的说明书摘要、说明书第1-61段、说明书附图图1-7、摘要附图，2019年03月04日提交的权利要求第1-4项。
如对本复审决定不服，根据专利法第41条第2款的规定，复审请求人可以自收到本决定之日起三个月内向北京知识产权法院起诉。
郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
