KMP算法的FPGA实现-科技大学本科毕业设计.docx

本科毕业设计（2011届）题 目KMP算法的FPGA实现学 院电子信息学院专 业集成电路设计与集成系统班 级学 号学生姓名指导教师完成日期诚 信 承 诺我谨在此承诺：本人所写的毕业论文KMP算法的FPGA实现均系本人独立完成，没有抄袭行为，凡涉及其他作者的观点和材料，均作了注释，若有不实，后果由本人承担。 承诺人（签名）： 年 月 日摘 要 随着网络技术的迅猛发展，所要检测的数据包越来越多，单纯的依靠软件来检测，越来越显得力不从心。伴随着FPGA技术的发展，在硬件上实现模式匹配，来提高网络数据处理速度的需求越来越普遍。把搜索算法固化到FPGA里，从而可以大大提高算法的速度，适应科技的迅速发展。本文重点分析了几种典型的模式匹配算法。包括：BF算法、KMP算法、BM算法、BMH算法、AC算法和AC-BM算法。另外文章还介绍了FPGA的的相关基本知识以及硬件描述语言的选择。综合考虑现有的比较成熟的模式匹配算法，并且追踪国外基于FPGA技术来实现模式匹配的研究成果，认为在硬件实现方面，KMP算法效率较高，结构简单，可行性强，而且易于对主串进行多模式的匹配，所以选其作为模式匹配硬件模块的核心算法，通过硬线逻辑来进一步提高串模式匹配的效率。本文KMP算法程序设计部分主要分为三个部分：模式串输入、next函数的计算、字符串的匹配。具体情况会在第四章中介绍。关键词：模式匹配算法；KMP算法；FPGAABSTRACTWith the rapid development of network technology, have to text more and more packets. Thus, simply relying on software to detect becomes more and more inadequate.As the development of FPGA technology, its becomes increasingly popular to realize the pattern matching on hardware to meet the demand for the improvement of the processing speed of network data. Putting the search algorithm to the FPGA, which can greatly improve the speed of the algorithm, is adapt to the quick development of technology.This paper focuses on several typical patterns matching algorithm involving: BF algorithm, KMP algorithm, BM algorithm, BMH algorithm, AC algorithm and the AC-BM algorithm.Besides, this paper will also introduce the basic knowledge related to FPGA as well as the selection of the description language of hardware. Considering the current pattern matching algorithms which are relatively through and the reseaching findings from abroad of using FPGA to achieve pattern mactching, KMP has advantages of efficient arithmetic, simple organization, strong feasibility and easy multi-pattern macthing to primary string in realizing hardware.Thats the reason why choose it to be the core arithmetic of matching pattern and hardware module, which makes further improvement on effiency of pattern maching in string by via hard wire logic.This part of KMP Algorithm Programming is divided into three parts: the pattern string entered, next function calculation, string matching. The circumstances described in the fourth chapter.Key words：Pattern matching algorithm；KMP algorithm；FPGA目 录第1章引言11.1研究背景11.2模式匹配算法的发展与研究现状1第2章 模式匹配算法32.1模式匹配定义32.2单模式匹配32.2.1BF算法32.2.2KMP算法42.2.3BM算法62.2.4BMH算法72.3多模式匹配72.3.1AC算法72.3.2AC-BM算法82.4影响模式匹配算法的因素9第3章FPGA基本的知识113.1FPGA简介113.2FPGA与CPLD的关系以及工作原理113.3硬件语言选择12第4章KMP算法VerilogHDL实现144.1模式串输入144.2next函数的计算154.3字符串匹配194.4代码通用性的验证22第5章结束语27致谢28附录31第1章 引言1.1研究背景1在网络处理中，模式匹配是指将分组各域进行比特位的匹配处理。一般，模式匹配模块有两个输入，一个是规则的模式表达式，另一个是分组域。它的输出是输入分组的各域是否与输入模式的布尔值匹配。这类模式匹配的实质还是字符串匹配，它的基本运算就是从一个主字符串中找到某个特定模式串出现的位置。目前，串匹配算法一般是以模式串的长度为扫描窗口大小，在窗口中使用不同的扫描策略来进行匹配。假设模式串长为m，主串长为n，串匹配算法根据策略的不同，大致可以分为以下3类23：从前往后匹配模式前缀的KMP算法，从后往前匹配模式后缀的BM算法及其各种变形，以及从后往前匹配模式前缀的RF算法等等。KMP4算法是从前往后进行扫描，使用自动机记住己匹配模式前缀的正文内容，并依据这些内容来确定是否已经匹配成功。换句话说，就是先对模式串进行预计算，然后再与主串匹配，而且主串不需要回溯，它的时间复杂度比较好，一般是O(m+n)。BM5算法及其变形是在扫描窗口中从后往前进行扫描，记住已匹配模式后缀的正文内容，并依据这些内容来进行窗口移动，这种方法虽然简单易行，但是时间复杂度比较差，最坏情况下为0(m+n)，所以当串比较长时，效率就会很低。RF算法等是在从后往前进行扫描时，反向使用模式逆串的后缀自动机来匹配模式的前缀，这样可以增大窗口移动的距离，从而获得更好的平均时间复杂度，达到理论最优结果。该方法效率较高，但是比较复杂，硬件实现难度大。综合考虑现有的比较成熟的模式匹配算法，认为在硬件实现方面，KMP算法具有其他算法没有的优势，所以本文选择KMP算法作为研究的主要对象。1.2模式匹配算法的发展与研究现状14BF算法是最早提出来的模式匹配算法，也是最简单的一个算法。该算法的最坏时间复杂度为O(M*N)。1970年，SACOOK从理论上证明了串匹配问题可以在O(m+n)时间内解决，同一年，Morris和Pratt仿照COOK的证明构造了一个算法，随后，Knuth对这个算法进行了一些改进，在1976年，Knuth提出了第一个在线性时间内解决字符串的模式匹配算法，这个算法被称为KMP算法它的时间复杂度为O(m+n)。1977年，Boyer和Moore提出了另一个与KMP算法截然不同的却同样拥有线性时间复杂度的算法(BM算法)。BM算法在实际的模式匹配中，跳过了很多无用的字符，这种跳跃式的比较方式，使BM算法获得了极高的效率，特别是在大字符集上进行字符串的模式匹配时。在实际的应用中，BM算法比KMP算法更有效率。多模式匹配是另一个研究热点。Aho-Corasie算法(AC算法)是第一个在O(N)上解决这个问题的算法。AC算法可以被看作是KMP算法的更一般化形式。此后，BM算法跳跃的思想也被应用到了多模式匹配上，1979年CommentsWalter提出了一种新的多模式匹配算法，称为CW算法，这个算法将AC算法和BM算法的思想结合起来，获得了更好的执行效率。沿着AC算法这条路线，Crochemore等人将AC算法和DAWG结合，获得了一种新的算法，称为DAWG-MATCH。实验结果表明，该算法比Comments-Walter的算法更有效率。此外，人们还提搬了其它一些多模式匹配算法。1994年，Sun Wu和Manber提出了第一个基于过滤思想的多模式匹配算法。这个算法将过滤思想和BM思想结合起来，在实际的应用中获得了极其高的效率。实验表明，在Sun Sparcl0上，他们的算法可以于10秒内完成在15.8M的文本中搜索10000个模式的工作。在WM算法的基础上，Sun Wu和Manber实现了一个用于模糊匹配的工具agrep和一个文本检索的工具glimpse，在实际的应用中都获得了良好的效率。1996年，Robert Muth和Udi Manber给出了一个快速的多模式模糊匹配算法，这个算法也是基于过滤的思想，同时采用了两级散列的技术，从而获得了极高的执行效率，实验数据表明，该算法能在小于1秒的时间内完成在1M文本中对1000个模式的搜索和模糊匹配的过程。但是不幸的是，该算法只允许模式和文本子串之间存在1个不同点，这样的约束限制了该算法在实际中的应用。1999年，在数据压缩和位操作的思想上，Sun Kim和Yanggon Kim设计出了一个新的多模式匹配算法，实验证明，该算法比Sun Wu和Manber的算法有更好的表现，特别是在小字符集上。目前对模式匹配算法的研究一部分还停留在单模式匹配算法，而对多模式匹配算法的研究主要集中在算法的综述、测试以及对现有算法的一些相应改进上。这些改进的算法虽然也取得一定的成果，但是总体效果都不是很理想，主要是算法速度受限于模式的数目或者实现算法需要的空间消耗的内存太大。字符串的模糊匹配是近年来倍受关注的领域，模糊匹配允许在搜索时搜索出与模式有一些差别的文本中的字符串。在这个领域，有四条主要的技术路线：动态规划算法；自动机算法；过滤算法；位并行算法。由于这不是本文研究的主要内容，故不做详细介绍。第2章 模式匹配算法模式匹配分为单模式匹配和多模式匹配，一次在文本串中查找一个模式串出现的过程，称为单模式匹配。同时查找一个模式串集合中的所有模式串的出现的过程称为多模式匹配。本章主要讨论几种典型的单模式匹配算法和多模式匹配算法。2.1模式匹配定义字符串的模式匹配问题的形式化定义如下：在字符集上，给定一个长度为N的文本字符串T1N，以及一个长度为M的模式 字符串Pi1M。模式集数量用k来表示，模式集用P=pl，p2，pk来表示。如果对于l=S=N，存在TS+1S+M=Pi1M，则模式Pi在文本T的位置S处出现，即模式与文本匹配。字符串的模式匹配问题就是要寻找P在T中是否出现，以及出现的位置。例如：文本字符串T：Here is a beauterful picture模式字符串P：beauterful该例子显示需要在文本字符串T中搜索模式字符串P：“beauterful，通过搜索我们发现模式字符串P：“beauterful”出现在文本字符串T中第1l位，那么我们称模式字符串P与文本字符串T匹配成功。2.2单模式匹配2.2.1BF算法BF算法即Brute Force算法的缩写。是蛮力算法的意思，实际上是原理和逻辑最简单的算法这个算法在字符申规模较小的时候，还是能够取得较好的效益。BF算法就是把模式串和文本串的所有窗口逐一进行比较。如果当前字符相同而且模式串结束则匹配成功如果字符相同而模式串未结束就比较下一个字符：如果字符不相同，则窗口向后移动一个字符位置，模式串和新窗口从开始字符重新比较。对于文本字符串TlTkTjTm-k-1Tn模式字符串PlPiPm算法描述：(1)P和T从左端对齐，使得Pl与T1对齐；(2)从左到右匹配P与T的字符，直到出现不匹配的情况或是P已被完全匹配：(3)如果出现不匹配的情况，则将P右移一个字符，重新开始匹配；(4)重复上述过程，直到P被完全匹配，或P移到T的右端。每次模式串和某个窗口比较次数应该是0(m)，而窗口的个数是0（nm)个。因此算法最坏情况的时问复杂度是O(mn)。最坏情况的例子之一是文本串是某一相同字符的字符串而模式串也是这一字符的字符串。这种算法的缺陷是匹配过程中带有回溯，准确地说是当匹配不成功的时候，之前进行的匹配完全变为无效的,所有的比较需要从模式串首字符重新开始。BF算法的优点是不需要预处理。辅助的空间是常量，即只需要几个变量的临时存储区域。模式串和某个窗口内匹配的顺序是任意的，向左或者向右都是可以的。2.2.2KMP算法KMP算法是Knuth等人在BF算法的基础上提出来的。从本质上讲，KMP算法就是出现不匹配情况下带有智能指针初始化的BF算法。为了在不匹配时重新定位指针，KMP算法需要进行预处理算出一个Shift表来。基本思想：KMP算法利用已匹配成功部分的信息，即前缀(模式字符串中存在的相同子串)，可以使模式字符串向前推进若干个字符位置，而不只是一个字符，避免了重复比较，同时也实现了文本字符串指针的无回溯。要点是：我们能够通过预先对模式的分析获得知识，即如果在模式的位置l或2匹配失败则移动1个位置，如果在模式的位置3匹配失败则移动2个位置，如果在模式的位置4匹配失败则移动3个位置，以此类推。算法描述9：当模式匹配执行到比较字符Ti和Pi，其中l=i=n，l=j=m。(1)若Ti=Pj则继续往右作匹配检测，即对Ti+1和Pj+l；进行匹配检测。(2)若TiPj时则分两种情况进行讨论：第一种情况：若j=l，则对Ti+l和Pi进行匹配检测，即把模式和正文向右移动一位再从模式的第一个字符进行匹配。第二种情况：若lj=m，我们将试图在模式中找到一个合适位置再进行比较，我们把这个下标记做nextj。执行Ti和nextj的匹配，其中nextj的构造是算法的核心，约定如下：Nextj=-1,当j=0时Nextj=maxk|0kj且“P0 P1Pk-1”=“Pj-k Pj-k+1Pj-1”此集合不为空集Nextj=0，其他情况由于本文主讲的是KMP算法，估计我们举例详细说明，如主串为ababcabcacbab，模式串为abcac，匹配过程如下图2-1: 图2-1 一般情况下，假设主串为s0s1sn-1，模式串为p0p1pm-1，从上例的分析可知，为了实现改进算法，需要解决下述问题：当匹配过程中产生“失配”（即sipj）时，模式串“向右滑动”可行的距离有多远，换句话说，当主串中字符Si与模式中字符Pj “失配”（即比较不等）时，主串中字符Si（i指针不回溯）应与模式中哪个字符再比较？假设此时主串中字符Si应与模式中字符Pk（kj）继续比较，则模式中字符Pk前面k个字符的子串必须满足下列关系式（f-1），且不存在kk满足下列关系式（f-1）p0p1pk-1 = si-ksi-k+1si-1 (f-1) 图2-2模式串与主串的对应关系一当主串中字符Si与模式中字符Pj “失配”时，已经得到的“部分”匹配结果是：pj-kpj-k+1pj-1 = si-ksi-k+1si-1 (f-2)图2-3模式串与主串的对应关系二由（f-1）和（f-2）推得下列等式p0p1pk-1 = pj-kpj-k+1pj-1 (f-3)我们称p0p1pk-1为p0p1p2pj-2pj-1的前缀子串，pj-kpj-k+1pj-1为p0p1p2pj-2pj-1的后缀子串。若模式串中存在真子串p0p1pk-1= pj-kpj-k+1pj-1，且满足0k=distt，故相对BM算法具有一定的优越性。BMH算法预处理时间复杂度为O(m+o)，空间复杂度先0(o)，o是与Pattern、Text相关的有限字符集长度。查找阶段时间复杂度为O(mn)，在一般情况下，BMH算法比BM有更好的性能，它只使用了一个数组，简化了初始化过程。2.3多模式匹配2.3.1AC算法1975年，贝尔实验室的Alfred VAho和Margaret JCorasick提出了著名的多模式匹配算法一一AC自动机匹配算法(简称AC算法)。该算法最早被使用在图书馆的书目查询程序中，取得了很好的效果。AC算法描述（例如模式集SP=he，she，his，hers）：预处理阶段，模式树的各个节点作为状态，根节点作为初态，标签为模式的节点作为终态，利用转向函数g和失效函数f作为转移函数，将模式树扩展成一个树型有限自动机。见图2-4由模式树扩展所得的AC自动机M是1个6元组：M= (Q，g，f，qo，F)其中：(1)Q是有限状态集(模式树上的节点)；(2)是有穷的输入字符表(数据包中可能出现的所有字符)；(3)g是转移函数，该函数定义如下：g(S，a)：从当前状态S开始，沿着边上标签为a的路径所到的状态。假如(U，v)边上的标签为a，那么g(U，a)=v；如果根节点上出来的边上的标签没有a，则g(0，a)=O，即如果没有匹配的字符出现，自动机停留在初态；(4)f(不匹配时自动机的状态转移)也是转移函数，该函数定义如下：f(S)：当w是L(s)最长真后缀并且W是某个模式的前缀，那么f(S)就是以W为标签的那个节点；(5)qoQ是初态(根节点，标识符为0)；(6)F量Q是终态集(以模式为标签的节点集)。这样，在文本字符串中查找模式字符串的过程转化成在模式树中的查找过程。查找一个文本字符串T时从模式树的根节点开始，沿着以T中字符为标签的路径往下走：若自动机能够抵达终态v，则说明T中存在模式L(v)：否则不存在模式。图2-4 模式树AC算法模式匹配的时间复杂度是O(n)，并且与模式集中模式字符串的个数和每个模式字符串的长度无关。无论模式字符串P是否出现在文本字符串T中，T中的每个字符都必须输入状态机中，所以无论是最好情况还是最坏情况，AC算法模式匹配的时间复杂度都是0(n)，包括预处理时间在内，AC算法总时间复杂度是O(M+n)，其中M为所有模式字符串的长度总和。AC算法的查找效率明显高于BM算法。但是，AC算法在对文本字符串匹配的过程中没有跳跃，无法跳过不必要的比较，并且有限状态自动机算法是以空间换时间的经典算法，当模式集较大时可能产生内存膨胀问题。因此在实际的匹配过程中，AC算法不可能是性能最佳的搜索算法。2.3.2AC-BM算法AC-BM算法是在AhoCorasick算法的基础上，结合BoyerMoore算法的跳跃思想，产生的一种多模式匹配算法。在一般情况下，由于应用了BM算法的跳跃式思维，所以不需要对文本的每个字符进行匹配。在BM算法的基础上引入了AC算法，来提高匹配速度，跳过尽可能多的字符，在模式字符串较长和较短的情况下，该算法都具有很好的性能。AC-BM算法描述：设模式树中最短模式串的长度为L，第一次比较是从待匹配的文本字符串的末端向前取L个字符与模式树的根字符对齐，然后从树的根字符开始比较，当出现不匹配的字符时：(1)若目标字符不在任何模式串中，则模式树偏移量为L位；(2)移动到另一模式串前缀的下一位置；(3)将模式树移动到作为树中另一个模式后缀能够正确匹配目标串的某个前缀的下一个位置。要注意的是：AC-BM算法在移动过程中，模式树移动的偏移量不能超过最短模式串的长度L。我们设模式字符串集合中，字符串最小长度为minlen，最大长度为maxlen，待匹配文本长度为n，则在最优情况下，时间复杂度为O(nminlen)，在最坏情况下，时间复杂度为O(n*maxlen)。AC-BM算法结合多模式匹配AC和单模式匹配BM两种算法的优点，既可以同时匹配多个模式又可以跳过不必要的字符，因此相比其它模式匹配算法具有较高的性能和效率。2.4影响模式匹配算法的因素对于一个模式匹配算法来说，在实际应用中，最为关注的问题有以下几个方面1819：(1)正确性：即误判率和漏判率，这与模式的选择是密切相关的，如果模式的选择比较严格，那么误判率和漏判率一定会下降，但是过于严格的模式会影响识别的速度；同时过于简短的模式又会影响误判率和漏判率，所以要选择一个最优的折衷点。(2)速度：即时间复杂性，这是评价一个模式匹配算法的重要的标准之一。随着网络速度的提高，通常要求模式匹配能以线速率执行，特别是在一些实时性的系统中，对模式匹配的速度有很高的要求。一般情况下算法的时间复杂性，首先是预处理时间复杂性，其次是匹配过程中的时间复杂性，最后是最坏情况和最好情况下的时间复杂性，特别是最坏情况下的复杂性，是算法研究中的一个重要方面。而在上述三种情况的时间复杂性中，模式的因素都是一个不可缺少的原因。简洁有效的模式不仅可以降低预处理的时间复杂度，而且还能缩短匹配过程的时间，至于最坏和最好的时间复杂度，在很大程度上受控于模式的规模。所以若要提高算法的速度，提高模式的有效性是一个重要途径。(3)资源消耗：在模式的预处理阶段和模式匹配阶段，对内存的需求也是应用中关注的重要问题之一，尽管目前内存的容量提高了很多，但是庞大的内存占有量会减慢算法的速度，所以现在人们常常借助于硬件实现算法。第3章 FPGA的基本知识本章主要介绍FPGA的基本概念，FPGA与CPLD的关系，硬件描述语言的选择。3.1FPGA简介21FPGA（FieldProgrammable Gate Array），即现场可编程门阵列，它是在PAL、GAL、CPLD等可编程器件的基础上进一步发展的产物。它是作为专用集成电路（ASIC）领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点。目前以硬件描述语言（Verilog 或 VHDL）所完成的电路设计，可以经过简单的综合与布局，快速的烧录至 FPGA 上进行测试，是现代 IC 设计验证的技术主流。这些可编辑元件可以被用来实现一些基本的逻辑门电路（比如AND、OR、XOR、NOT）或者更复杂一些的组合功能比如解码器或数学方程式。在大多数的FPGA里面，这些可编辑的元件里也包含记忆元件例如触发器（Flipflop）或者其他更加完整的记忆块。 系统设计师可以根据需要通过可编辑的连接把FPGA内部的逻辑块连接起来，就好像一个电路试验板被放在了一个芯片里。一个出厂后的成品FPGA的逻辑块和连接可以按照设计者而改变，所以FPGA可以完成所需要的逻辑功能。 FPGA一般来说比ASIC（专用集成芯片） 的速度要慢，无法完成复杂的设计，而且消耗更多的电能。但是他们也有很多的优点比如可以快速成品，可以被修改来改正程序中的错误和更便宜的造价。厂商也可 能会提供便宜的但是编辑能力差的FPGA。因为这些芯片有比较差的可编辑能力，所以这些设计的开发是在普通的FPGA上完成的，然后将设计转移到一个类似 于ASIC的芯片上。另外一种方法是用CPLD（复杂可编程逻辑器件备）。3.2FPGA与CPLD的关系以及工作原理CPLD与FPGA的关系：早在1980年代中期，FPGA已经在PLD设备中扎根。CPLD和FPGA包括了一些相对大数量的可编辑逻辑单元。CPLD逻辑门的密度在几千到几万个逻辑单元之间，而FPGA通常是在几万到几百万。 CPLD和FPGA的主要区别是他们的系统结构。CPLD是一个有点限制性的结构。这个结构由 一个或者多个可编辑的结果之和的逻辑组列和一些相对少量的锁定的寄存器。这样的结果是缺乏编辑灵活性，但是却有可以预计的延迟时间和逻辑单元对连接单元高 比率的优点。而FPGA却是有很多的连接单元，这样虽然让它可以更加灵活的编辑，但是结构却复杂的多。 CPLD和FPGA另外一个区别是大多数的FPGA含有高层次的内置模块（比如加法器和乘法器）和内置的记忆体。一个因此有关的重要区别是很多新的FPGA支持完全的或者部分的系统内重新配置。允许他们的设计随着系统升级或者动态重新配置而改变。一些FPGA可以让设备的一部分重新编辑而其他部分继续正常运行。FPGA的工作原理：（1）采用FPGA设计ASIC电路(专用集成电路)，用户不需要投片生产，就能得到合用的芯片。 （2）FPGA可做其它全定制或半定制ASIC电路的中试样片。 （3）FPGA内部有丰富的触发器和IO引脚。 （4）FPGA是ASIC电路中设计周期最短、开发费用最低、风险最小的器件之一。 （5) FPGA采用高速CHMOS工艺，功耗低，可以与CMOS、TTL电平兼容。 可以说，FPGA芯片是小批量系统提高系统集成度、可靠性的最佳选择之一。 FPGA是由存放在片内RAM中的程序来设置其工作状态的，因此，工作时需要对片内的RAM进行编程。用户可以根据不同的配置模式，采用不同的编程方式。 加电时，FPGA芯片将EPROM中数据读入片内编程RAM中，配置完成后，FPGA进入工作状态。掉电后，FPGA恢复成白片，内部逻辑关系消失，因此，FPGA能够反复使用。FPGA的编程无须专用的FPGA编程器，只须用通用的EPROM、PROM编程器即可。当需要修改FPGA功能时，只需换一片EPROM即可。这样，同一片FPGA，不同的编程数据，可以产生不同的电路功能。因此，FPGA的使用非常灵活。FPGA有多种配置模式：并行主模式为一片FPGA加一片EPROM的方式；主从模式可以支持一片PROM编程多片FPGA；串行模式可以采用串行PROM编程FPGA；外设模式可以将FPGA作为微处理器的外设，由微处理器对其编程。 如何实现快速的时序收敛、降低功耗和 成本、优化时钟管理并降低FPGA与PCB并行设计的复杂性等问题，一直是采用FPGA的系统设计工程师需要考虑的关键问题。如今，随着FPGA向更高密 度、更大容量、更低功耗和集成更多IP的方向发展，系统设计工程师在从这些优异性能获益的同时，不得不面对由于FPGA前所未有的性能和能力水平而带来的 新的设计挑战。3.3硬件语言选择22Verilog HDL与VHDL是两种最常见的硬件描述语言，Verilog HDL与VHDL相比有以下一些优点：(1)可以用来进行各种层次的逻辑设计，也可以进行数字系统的逻辑综合、仿真验证和时序分析等。Verilog HDL适合算法级(Algorithm)、寄存器传输级(RTL)、逻辑级(Logic)、门级(Gate)和版图级(Layout)等各个层次的设计和描述。(2)VHDL偏重于标准化考虑，而Verilog HDL与EDA工具的结合更为紧密。VHDL是国际上第一个标准化的HDL语言(IEEE-1076)，是为了实现美国国防部VHSIC计划所推出的各个电子部件供应商具有统一的数据交换格式的要求。相比之下，Verilog HDL则是在全球最大的EDA/ESDA供应商Cadence公司的扶持下针对EDA工具开发的HDL语言。(3) 与VHDL相比，Verilog HDL的编程风格更加简洁明了，更接近高级计算机语言的语法形式。有鉴于此，本设计采用Verilog HDL语言作为硬件描述语言。第4章 KMP算法VerilogHDL实现本章主要介绍KMP算法的VerilogHDL实现设计过程，一些调试碰到的问题及解决方法。4.1模式串输入kmp算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特莫里斯普拉特操作（简称KMP算法）。KMP算法的关键是根据给定的模式串pattern定义一个next函数。next函数包含了模式串本身局部匹配的信息。为了用Verilog HDL实现KMP算法，我们需要在熟悉算法原理的基础上进行程序设计。KMP算法的原理已经在论文的第二章详细介绍过，这里就不再累述。图4-1模式串输入代码由于Verilog HDL语言不像C语言一样可以很方便的申请内存用于存放变量或者数据，而既然我们的工作是要进行字符串的查找，那么首先我们需要有两个字符串。如何存放这两个字符串？有两种方法：一种是将字符串存放在FPGA内部的存储器中，比如使用Quartus II自带的MegaWizard Plug-in Manger工具在FPGA内部定制一个RAM或者ROM存放字符串，或者直接定义一个数组，即使用FPGA的逻辑单元构造RAM用于存放字符串。当然后一种方式的代价会比较高，尤其是当FPGA的逻辑单元相对较少时，随意地挥霍这种宝贵的资源就不可取。对于本设计，由于我们只是需要验证算法，因此用作主串的字符串不需要很长（实际使用了一个长度为16的字符串），因此可以直接定义数组来存放这个字符串，这样做可以避免另外设计电路用于控制RAM的读取。另外一种方法是令字符串从外部通过引脚输入到FPGA中，然后再存放在FPGA的内部RAM中，采用这样的设计方式，字符串的内容可以很方便地改动，本设计中的模式串就采用这种方式从外部输入。首先我们需要设计一个模式串的输入接口，模式串输入的Verilog HDL代码如图4-1所示：我们的Verilog HDL开发环境为Quartus II 8.0 Wed Edition，Quartus II是一个功能强大的集成开发环境，支持从源代码编辑到仿真、布局布线和芯片烧录的全部功能。上述代码中，k是一个计数值，宽度为4位，表示当前输入的字符的个数，在复位时初始化为0。在每个时钟的上升沿，k递增1。p是一个位宽为8的端口，外部数据就从这个端口输入。在每个时钟的上升沿，p端口的值赋给patternk寄存器。因为模式串的长度是8，因此当计数值k7时就不再需要存储端口p的数据，但是为了显示模式串输入已经完成，必须给出一个提示信息，这个提示信息不需要输出到FPGA的外部，只需要提醒内部的相关检测机制就可以，wr_ed就是这个提示信息，并且将它定义为一个reg型的变量，位宽为1位。当k7时就令wr_ed为1，表示模式串已经全部输入。该部分的功能仿真结果见图4-2：图 4-2 模式串输入仿真结果其中pattern0pattern7是wire型的输出口连接到pattern0pattern7，这只是一组用于观测FPAG内部寄存器值的端口变量，而这一组端口变量对一设计本身并不是必需的，因此当模式串输入接口的设计完成以后，可以撤销这一组端口。从仿真结果中可以看出，当wr_ed变为1时，说明模式串应当已经输入到FPGA内部的数组中了，我们查看此时的pattern0pattern7可以发现，模式串确实已经输入到内部的数组中了，这与我们的设想吻合。4.2next函数的计算为了便于Verilog HDL程序设计，我们首先用C语言描述KMP算法。之所以先用C语言描述KMP算法，是因为Verilog HDL最为一种高级的硬件描述语言，与C语言的风格有许多类似之处，其中有许多语句，如if语句、case语句和C语言中的对应语句十分相似。如下所示是next函数的C语言代码，在Visual Studio 2008下编辑和调试代码。int* computeNext(const char* pattern)( int len , i, nextTemp; int *next ; assert(pattern !=NULL); len = strlen(pattern); if (len = 0) len =1; next = (int*)malloc(sizeof(int) * len ); for (i =1; i 7时，nextdone就会等于1，表示next函数已经计算完毕，可以进行后续的字符匹配工作了。nextdone的功能与模式串输入函数中的wr_ed具有类似的功能。上述代码的结构与用C语言编写的代码十分相似，这就说明我们在理解了算法原理的基础上，可以很方便的将C语言编写的代码改写成Verilog HDL语言。但是这两种语言还是有很大的区别的，与C语言不同，在Verilog HDL中是没有定义诸如char、int、float这样的数据类型，所有的数据类型都是二进制数据，数据的每一位只有0和1两种取值，我们无法定义一个数为char型或者float型。因此在表示负数的时候我们就会不能简单地赋值，而因当采用补码的形式表示，比如-1我们就可以表示成4b1111，在数字系统综合的过程中这个数值就会被认为是-1。这一点是Verilog HDL语言与高级计算机语言存在巨大差别的地方。接下来我们需要验证我们设计的代码功能是否正确，这是很容易验证的。我们首先在C语言代码中对一个模式串“abaabcac”计算next值，得到如图4-5的运算结果：图4-5 Visual C+下next计算结果由上图可见对于“abaabcac”这个字符串，next函数的计算结果是-1，0，0，1，1，2，0，1。另外我们还发现程序的运行结果提示在主串中找到的模式串的其实位置为-1，为什么呢？其实这是因为在这一次运行中我们设置的主串中没有包含一个有效的模式串，因此运行结果是找不到匹配的字符串，在这种情况下我们在控制台输出一个-1表示没有找到匹配的字符串。接下来我们来测试我们用Verilog HDL编写的代码功能是否正确。Quartus II中新建一个仿真波形文件，然后设置仿真模式为功能仿真（由于我们只是要验证电路的工作机制是否正确，因此只要选择功能仿真即可），然后将端口变量添加到仿真窗口中，设置时钟和其他输入变量，点击“Generate Functional Simulation Netlist”，生成功能仿真的仿真网表文件，然后运行仿真，仿真结果如图4-6所示：图4-6 next函数在Quartus II下的仿真结果由上图可见，当nextdone为1时，说明next函数已经计算完成，这个时候我们可以查看next数组的值，由于next0next7是一组线网型的端口变量，直接反映next数值的值，因此我们观查next0next7的值，发现其数值为-1、0、0、1、1、2、0、1。这个运算结果与C语言的运算结果是一致的，这说明我们设计的next函数状态机是完全正确的！4.3字符串匹配在设计完next函数的Verilog HDL实现之后，我们的设计的最核心部分已经完成了，接下来要做的工作就是根据next数组进行字符串的匹配操作。既然是字符串匹配，那么我们必然需要一个主串供我们查找，前面已经提到过FPGA中数据的存储方式，为了方便调用存储的数据，我们将主串存放在内部数组中，占用FPGA的片上逻辑单元，在系统复位时对数组中的值进行初始化。同样的，我们先来看字符串匹配的C语言代码如下int stringMatchKmp(const char* src, const char* target) int srcLen, targetLen; int i = 0, j = 0, index; int *next; assert(src != NULL & target !=NULL); srcLen = strlen(src); targetLen = strlen(target); next = computeNext(target); print(next, strlen(target) ); while (i srcL