【硕士论文】新型PLD解析算法的研究与实现.pdf

《【硕士论文】新型PLD解析算法的研究与实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、哈尔滨工程大学硕士学位论文新型PLD解析算法的研究与实现姓名：邢松寅申请学位级别：硕士专业：计算机应用技术指导教师：马光胜20000201哈尔滨_【程大学硕士学位论文摘要，本论文主要研究的是对大中规模的可编程逻辑器件的解析问题。{刁i论是对于大规模的可编程逻辑器件还是对于小规模的可编程逻辑器件，如果采用反向逻辑设计法来对其解析，主要问题就是如何能够找到一种快速和耗费更少系统资源的算法来对待解析电路进行数据采集。进行数据采集有两个关键问题：一个是如何得到时序电路的有效状态网络，另“’个是在建立状态

2、网络之后如何依据这个有效状态网络进行状态问的路径导出和状态驱动。运用现有的解析算法，其中包括谢红和王馨遮等在此问题上的解决方法，其基本思路就是利用可编程逻辑器件的可解性理论得出的：满足规范设计的时序型电路其有效状态图构成一+强连通图。利用此结论，就可将解析算法归纳为强连通图的遍历和搜索问题。但实际的情况并没有如此简单。应有传统的强连通图的遍历和搜索对解析一些小规模的逻辑电路还能凑效。对于中大规模的逻辑器件，理论上也是可行的，但是由于传统方法的时空复杂度与大解析电路的规模呈指数级增长。因此，在实际

3、当中是根本不可行的。卜√。本论文在总结了前人的算法基础之上，利用图论中的基础理论，存进行数据采集的过程中，不按照常规方法生成有效状态的强连通图，而是生成其强连通子图即生成其状态网络的思想。并且在此基础之上，引用～种基于环的方法来保存生成的状态网络，而非采用已有的存储图的常规数据结构，例如邻接表和邻接矩阵的方法来保存状态网络，采用这种方法和数据结构，大大降低了存储的需求。同时，基于此种保存环来生成状态网络的方法，本文还提出了一种路径的导出算法和状态驱动算法。采用这种算法可在程序设计中运用回溯和递归

4、的方法来方便地实现状态间的驱动，从而最终用一种新的算法解决了未知时序电路的数据采集，为中大规模可编程逻辑器件的解析提供了可能性。除此以外，本论文还分析和介绍了可编程逻辑器件的解析原理、可解性以及可编程逻辑解析系统的硬件系统模型和软件系统模型及其相关的逻辑综合方面的内容。关键词：PLD解析；解析系统；数据采集；状态网络；状态驱动；解析原理：测试生成；；一；；；；一．墅堡兰堡奎兰l坠兰耋堡!：圣；；；；一；；；；；；ABSTRACTInthispaper，theproblemofthelargesc

5、alePLDdecryptionisdiscussed．WhateveritisthelargescaleorsmallscalePLD，ThekeytechnologyofdecryptionistogetaalgorithmwhichcancollectthedecryptedPLD’Sdatawithfasterspeedandlessmemory．Thetraditionaldecryptionalgorithmutilizesthebasictheoryofdecryption，its

6、umsupthedecryptionalgorithmtographtraversalandsearchproblem．AlthoughthealgorithmcanbeusetodecryptsmallscalePLDcircuit，butwhenitwasusedtodecryptlargescalePLDcircuit，itwillnottakeineffect，forit’StimeandspacecomplexityrisesharplycomparetothePLD’Sscale．S

7、ousingthetraditionalmethod，itisnotfeasibleinthepracticality．Inthispaper,Wedonotusingthetraditionalmethodtogeneratethevalidstategraphwhichisacompletegraph．Basingonthegraphtheoretics，wecangeneratethecompletegraph’SsubgraphthatWecalledstatenetwork．Diffe

8、ringtothetraditionaldatestucturewhichusetostoregraph，suchasadjacencymatrixoradjacencylist．WeciteanewalgorithmandanefficientdatastructurewecalledcycletOstoreandgeneratethesubgraphorstatenetwork．Atthesametime，weputforwordanewapproachwhichcanbeusetodriv