kmp算法畢業(yè)論文- 副本

1、本科畢業(yè)設(shè)計(jì)（2011屆）題 目KMP算法的FPGA實(shí)現(xiàn)學(xué) 院電子信息學(xué)院專 業(yè)集成電路設(shè)計(jì)與集成系統(tǒng)班 級(jí)07042211學(xué) 號(hào)07042240學(xué)生姓名褚小偉指導(dǎo)教師李訓(xùn)根完成日期2011年3月誠(chéng) 信 承 諾我謹(jǐn)在此承諾：本人所寫(xiě)的畢業(yè)論文KMP算法的FPGA實(shí)現(xiàn)均系本人獨(dú)立完成，沒(méi)有抄襲行為，凡涉及其他作者的觀點(diǎn)和材料，均作了注釋，若有不實(shí)，后果由本人承擔(dān)。 承諾人（簽名）： 年 月 日摘 要 隨著網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，所要檢測(cè)的數(shù)據(jù)包越來(lái)越多，單純的依靠軟件來(lái)檢測(cè)，越來(lái)越顯得力不從心。伴隨著FPGA技術(shù)的發(fā)展，在硬件上實(shí)現(xiàn)模式匹配，來(lái)提高網(wǎng)絡(luò)數(shù)據(jù)處理速度的需求越來(lái)越普遍。把搜索算法固化到F

2、PGA里，從而可以大大提高算法的速度，適應(yīng)科技的迅速發(fā)展。本文重點(diǎn)分析了幾種典型的模式匹配算法。包括：BF算法、KMP算法、BM算法、BMH算法、AC算法和AC-BM算法。另外文章還介紹了FPGA的的相關(guān)基本知識(shí)以及硬件描述語(yǔ)言的選擇。綜合考慮現(xiàn)有的比較成熟的模式匹配算法，并且追蹤國(guó)外基于FPGA技術(shù)來(lái)實(shí)現(xiàn)模式匹配的研究成果，認(rèn)為在硬件實(shí)現(xiàn)方面，KMP算法效率較高，結(jié)構(gòu)簡(jiǎn)單，可行性強(qiáng)，而且易于對(duì)主串進(jìn)行多模式的匹配，所以選其作為模式匹配硬件模塊的核心算法，通過(guò)硬線邏輯來(lái)進(jìn)一步提高串模式匹配的效率。本文KMP算法程序設(shè)計(jì)部分主要分為三個(gè)部分：模式串輸入、next函數(shù)的計(jì)算、字符串的匹配。具體情況

3、會(huì)在第四章中介紹。關(guān)鍵詞：模式匹配算法；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 match

4、ing 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 algo

5、rithm 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 algor

6、ithms 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.That's the reason why

7、 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, str

8、ing matching. The circumstances described in the fourth chapter.Key words：Pattern matching algorithm；KMP algorithm；FPGA目 錄第1章引言11.1研究背景11.2模式匹配算法的發(fā)展與研究現(xiàn)狀1第2章 模式匹配算法32.1模式匹配定義32.2單模式匹配334672.3多模式匹配7782.4影響模式匹配算法的因素9第3章FPGA基本的知識(shí)113.1FPGA簡(jiǎn)介113.2FPGA與CPLD的關(guān)系以及工作原理113.3硬件語(yǔ)言選擇12第4章KMP算法VerilogHDL實(shí)現(xiàn)144.1模式

9、串輸入144.2next函數(shù)的計(jì)算154.3字符串匹配194.4代碼通用性的驗(yàn)證22第5章結(jié)束語(yǔ)27致謝28附錄31第1章 引言1.1研究背景1在網(wǎng)絡(luò)處理中，模式匹配是指將分組各域進(jìn)行比特位的匹配處理。一般，模式匹配模塊有兩個(gè)輸入，一個(gè)是規(guī)則的模式表達(dá)式，另一個(gè)是分組域。它的輸出是輸入分組的各域是否與輸入模式的布爾值匹配。這類模式匹配的實(shí)質(zhì)還是字符串匹配，它的基本運(yùn)算就是從一個(gè)主字符串中找到某個(gè)特定模式串出現(xiàn)的位置。目前，串匹配算法一般是以模式串的長(zhǎng)度為掃描窗口大小，在窗口中使用不同的掃描策略來(lái)進(jìn)行匹配。假設(shè)模式串長(zhǎng)為m，主串長(zhǎng)為n，串匹配算法根據(jù)策略的不同，大致可以分為以下3類23：從前往后

10、匹配模式前綴的KMP算法，從后往前匹配模式后綴的BM算法及其各種變形，以及從后往前匹配模式前綴的RF算法等等。KMP4算法是從前往后進(jìn)行掃描，使用自動(dòng)機(jī)記住己匹配模式前綴的正文內(nèi)容，并依據(jù)這些內(nèi)容來(lái)確定是否已經(jīng)匹配成功。換句話說(shuō)，就是先對(duì)模式串進(jìn)行預(yù)計(jì)算，然后再與主串匹配，而且主串不需要回溯，它的時(shí)間復(fù)雜度比較好，一般是O(m+n)。BM5算法及其變形是在掃描窗口中從后往前進(jìn)行掃描，記住已匹配模式后綴的正文內(nèi)容，并依據(jù)這些內(nèi)容來(lái)進(jìn)行窗口移動(dòng)，這種方法雖然簡(jiǎn)單易行，但是時(shí)間復(fù)雜度比較差，最壞情況下為0(m+n)，所以當(dāng)串比較長(zhǎng)時(shí)，效率就會(huì)很低。RF算法等是在從后往前進(jìn)行掃描時(shí)，反向使用模式逆串的

11、后綴自動(dòng)機(jī)來(lái)匹配模式的前綴，這樣可以增大窗口移動(dòng)的距離，從而獲得更好的平均時(shí)間復(fù)雜度，達(dá)到理論最優(yōu)結(jié)果。該方法效率較高，但是比較復(fù)雜，硬件實(shí)現(xiàn)難度大。綜合考慮現(xiàn)有的比較成熟的模式匹配算法，認(rèn)為在硬件實(shí)現(xiàn)方面，KMP算法具有其他算法沒(méi)有的優(yōu)勢(shì)，所以本文選擇KMP算法作為研究的主要對(duì)象。1.2模式匹配算法的發(fā)展與研究現(xiàn)狀14BF算法是最早提出來(lái)的模式匹配算法，也是最簡(jiǎn)單的一個(gè)算法。該算法的最壞時(shí)間復(fù)雜度為O(M*N)。1970年，SACOOK從理論上證明了串匹配問(wèn)題可以在O(m+n)時(shí)間內(nèi)解決，同一年，Morris和Pratt仿照COOK的證明構(gòu)造了一個(gè)算法，隨后，Knuth對(duì)這個(gè)算法進(jìn)行了一些改

12、進(jìn)，在1976年，Knuth提出了第一個(gè)在線性時(shí)間內(nèi)解決字符串的模式匹配算法，這個(gè)算法被稱為KMP算法它的時(shí)間復(fù)雜度為O(m+n)。1977年，Boyer和Moore提出了另一個(gè)與KMP算法截然不同的卻同樣擁有線性時(shí)間復(fù)雜度的算法(BM算法)。BM算法在實(shí)際的模式匹配中，跳過(guò)了很多無(wú)用的字符，這種跳躍式的比較方式，使BM算法獲得了極高的效率，特別是在大字符集上進(jìn)行字符串的模式匹配時(shí)。在實(shí)際的應(yīng)用中，BM算法比KMP算法更有效率。多模式匹配是另一個(gè)研究熱點(diǎn)。Aho-Corasie算法(AC算法)是第一個(gè)在O(N)上解決這個(gè)問(wèn)題的算法。AC算法可以被看作是KMP算法的更一般化形式。此后，BM算法跳

13、躍的思想也被應(yīng)用到了多模式匹配上，1979年CommentsWalter提出了一種新的多模式匹配算法，稱為CW算法，這個(gè)算法將AC算法和BM算法的思想結(jié)合起來(lái)，獲得了更好的執(zhí)行效率。沿著AC算法這條路線，Crochemore等人將AC算法和DAWG結(jié)合，獲得了一種新的算法，稱為DAWG-MATCH。實(shí)驗(yàn)結(jié)果表明，該算法比Comments-Walter的算法更有效率。此外，人們還提搬了其它一些多模式匹配算法。1994年，Sun Wu和Manber提出了第一個(gè)基于過(guò)濾思想的多模式匹配算法。這個(gè)算法將過(guò)濾思想和BM思想結(jié)合起來(lái)，在實(shí)際的應(yīng)用中獲得了極其高的效率。實(shí)驗(yàn)表明，在Sun Sparcl0上，

14、他們的算法可以于10秒內(nèi)完成在15.8M的文本中搜索10000個(gè)模式的工作。在WM算法的基礎(chǔ)上，Sun Wu和Manber實(shí)現(xiàn)了一個(gè)用于模糊匹配的工具agrep和一個(gè)文本檢索的工具glimpse，在實(shí)際的應(yīng)用中都獲得了良好的效率。1996年，Robert Muth和Udi Manber給出了一個(gè)快速的多模式模糊匹配算法，這個(gè)算法也是基于過(guò)濾的思想，同時(shí)采用了兩級(jí)散列的技術(shù)，從而獲得了極高的執(zhí)行效率，實(shí)驗(yàn)數(shù)據(jù)表明，該算法能在小于1秒的時(shí)間內(nèi)完成在1M文本中對(duì)1000個(gè)模式的搜索和模糊匹配的過(guò)程。但是不幸的是，該算法只允許模式和文本子串之間存在1個(gè)不同點(diǎn)，這樣的約束限制了該算法在實(shí)際中的應(yīng)用。19

15、99年，在數(shù)據(jù)壓縮和位操作的思想上，Sun Kim和Yanggon Kim設(shè)計(jì)出了一個(gè)新的多模式匹配算法，實(shí)驗(yàn)證明，該算法比Sun Wu和Manber的算法有更好的表現(xiàn)，特別是在小字符集上。目前對(duì)模式匹配算法的研究一部分還停留在單模式匹配算法，而對(duì)多模式匹配算法的研究主要集中在算法的綜述、測(cè)試以及對(duì)現(xiàn)有算法的一些相應(yīng)改進(jìn)上。這些改進(jìn)的算法雖然也取得一定的成果，但是總體效果都不是很理想，主要是算法速度受限于模式的數(shù)目或者實(shí)現(xiàn)算法需要的空間消耗的內(nèi)存太大。字符串的模糊匹配是近年來(lái)倍受關(guān)注的領(lǐng)域，模糊匹配允許在搜索時(shí)搜索出與模式有一些差別的文本中的字符串。在這個(gè)領(lǐng)域，有四條主要的技術(shù)路線：動(dòng)態(tài)規(guī)劃算

16、法；自動(dòng)機(jī)算法；過(guò)濾算法；位并行算法。由于這不是本文研究的主要內(nèi)容，故不做詳細(xì)介紹。第2章 模式匹配算法模式匹配分為單模式匹配和多模式匹配，一次在文本串中查找一個(gè)模式串出現(xiàn)的過(guò)程，稱為單模式匹配。同時(shí)查找一個(gè)模式串集合中的所有模式串的出現(xiàn)的過(guò)程稱為多模式匹配。本章主要討論幾種典型的單模式匹配算法和多模式匹配算法。2.1模式匹配定義字符串的模式匹配問(wèn)題的形式化定義如下：在字符集上，給定一個(gè)長(zhǎng)度為N的文本字符串T1N，以及一個(gè)長(zhǎng)度為M的模式 字符串Pi1M。模式集數(shù)量用k來(lái)表示，模式集用P=pl，p2，pk來(lái)表示。如果對(duì)于l<=S<=N，存在TS+1S+M=Pi1M，則模式Pi在文本T

17、的位置S處出現(xiàn)，即模式與文本匹配。字符串的模式匹配問(wèn)題就是要尋找P在T中是否出現(xiàn)，以及出現(xiàn)的位置。例如：文本字符串T：Here is a beauterful picture模式字符串P：beauterful該例子顯示需要在文本字符串T中搜索模式字符串P：“beauterful"，通過(guò)搜索我們發(fā)現(xiàn)模式字符串P：“beauterful”出現(xiàn)在文本字符串T中第1l位，那么我們稱模式字符串P與文本字符串T匹配成功。2.2單模式匹配BF算法即Brute Force算法的縮寫(xiě)。是蠻力算法的意思，實(shí)際上是原理和邏輯最簡(jiǎn)單的算法這個(gè)算法在字符申規(guī)模較小的時(shí)候，還是能夠取得較好的效益。BF算法就是把

18、模式串和文本串的所有窗口逐一進(jìn)行比較。如果當(dāng)前字符相同而且模式串結(jié)束則匹配成功如果字符相同而模式串未結(jié)束就比較下一個(gè)字符：如果字符不相同，則窗口向后移動(dòng)一個(gè)字符位置，模式串和新窗口從開(kāi)始字符重新比較。對(duì)于文本字符串TlTkTjTm-k-1Tn模式字符串PlPiPm算法描述：(1)P和T從左端對(duì)齊，使得Pl與T1對(duì)齊；(2)從左到右匹配P與T的字符，直到出現(xiàn)不匹配的情況或是P已被完全匹配：(3)如果出現(xiàn)不匹配的情況，則將P右移一個(gè)字符，重新開(kāi)始匹配；(4)重復(fù)上述過(guò)程，直到P被完全匹配，或P移到T的右端。每次模式串和某個(gè)窗口比較次數(shù)應(yīng)該是0(m)，而窗口的個(gè)數(shù)是0（nm)個(gè)。因此算法最壞情況的時(shí)

19、問(wèn)復(fù)雜度是O(mn)。最壞情況的例子之一是文本串是某一相同字符的字符串而模式串也是這一字符的字符串。這種算法的缺陷是匹配過(guò)程中帶有回溯，準(zhǔn)確地說(shuō)是當(dāng)匹配不成功的時(shí)候，之前進(jìn)行的匹配完全變?yōu)闊o(wú)效的,所有的比較需要從模式串首字符重新開(kāi)始。BF算法的優(yōu)點(diǎn)是不需要預(yù)處理。輔助的空間是常量，即只需要幾個(gè)變量的臨時(shí)存儲(chǔ)區(qū)域。模式串和某個(gè)窗口內(nèi)匹配的順序是任意的，向左或者向右都是可以的。KMP算法是Knuth等人在BF算法的基礎(chǔ)上提出來(lái)的。從本質(zhì)上講，KMP算法就是出現(xiàn)不匹配情況下帶有智能指針初始化的BF算法。為了在不匹配時(shí)重新定位指針，KMP算法需要進(jìn)行預(yù)處理算出一個(gè)Shift表來(lái)?；舅枷耄篕MP算法利

20、用已匹配成功部分的信息，即前綴(模式字符串中存在的相同子串)，可以使模式字符串向前推進(jìn)若干個(gè)字符位置，而不只是一個(gè)字符，避免了重復(fù)比較，同時(shí)也實(shí)現(xiàn)了文本字符串指針的無(wú)回溯。要點(diǎn)是：我們能夠通過(guò)預(yù)先對(duì)模式的分析獲得知識(shí)，即如果在模式的位置l或2匹配失敗則移動(dòng)1個(gè)位置，如果在模式的位置3匹配失敗則移動(dòng)2個(gè)位置，如果在模式的位置4匹配失敗則移動(dòng)3個(gè)位置，以此類推。算法描述9：當(dāng)模式匹配執(zhí)行到比較字符Ti和Pi，其中l(wèi)=i=n，l=j=m。(1)若Ti=Pj則繼續(xù)往右作匹配檢測(cè)，即對(duì)Ti+1和Pj+l；進(jìn)行匹配檢測(cè)。(2)若TiPj時(shí)則分兩種情況進(jìn)行討論：第一種情況：若j=l，則對(duì)Ti+l和Pi進(jìn)行匹

21、配檢測(cè)，即把模式和正文向右移動(dòng)一位再?gòu)哪Ｊ降牡谝粋€(gè)字符進(jìn)行匹配。第二種情況：若l<j=m，我們將試圖在模式中找到一個(gè)合適位置再進(jìn)行比較，我們把這個(gè)下標(biāo)記做nextj。執(zhí)行Ti和nextj的匹配，其中nextj的構(gòu)造是算法的核心，約定如下：Nextj=-1,當(dāng)j=0時(shí)Nextj=maxk|0<k<j且“P0 P1Pk-1”=“Pj-k Pj-k+1Pj-1”此集合不為空集Nextj=0，其他情況由于本文主講的是KMP算法，估計(jì)我們舉例詳細(xì)說(shuō)明，如主串為ababcabcacbab，模式串為abcac，匹配過(guò)程如下圖2-1: 圖2-1 一般情況下，假設(shè)主串為s0s1sn-1，模式串

22、為p0p1pm-1，從上例的分析可知，為了實(shí)現(xiàn)改進(jìn)算法，需要解決下述問(wèn)題：當(dāng)匹配過(guò)程中產(chǎn)生“失配”（即sipj）時(shí)，模式串“向右滑動(dòng)”可行的距離有多遠(yuǎn)，換句話說(shuō)，當(dāng)主串中字符Si與模式中字符Pj “失配”（即比較不等）時(shí)，主串中字符Si（i指針不回溯）應(yīng)與模式中哪個(gè)字符再比較？假設(shè)此時(shí)主串中字符Si應(yīng)與模式中字符Pk（kj）繼續(xù)比較，則模式中字符Pk前面k個(gè)字符的子串必須滿足下列關(guān)系式（f-1），且不存在k'k滿足下列關(guān)系式（f-1）p0p1pk-1 = si-ksi-k+1si-1 (f-1) 圖2-2模式串與主串的對(duì)應(yīng)關(guān)系一當(dāng)主串中字符Si與模式中字符Pj “失配”時(shí)，已經(jīng)得到的“

23、部分”匹配結(jié)果是：pj-kpj-k+1pj-1 = si-ksi-k+1si-1 (f-2)圖2-3模式串與主串的對(duì)應(yīng)關(guān)系二由（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"，且滿足0<k<j,則當(dāng)匹配過(guò)程中，主串中字

24、符Si與模式中字符Pj比較不等時(shí)，僅需將模式向右滑動(dòng)至模式中第k個(gè)字符和主串中字符Si對(duì)齊，此時(shí)，模式中頭k個(gè)字符的子串"p0p1pk-1"必定與主串中字符Si之前長(zhǎng)度為k的子串"si-ksi-k+1si-1"相等。由此，匹配僅需從模式中Pk與主串中字符Si比較起繼續(xù)進(jìn)行。若令nextj=k,則nextj表明當(dāng)模式中第j個(gè)字符與主串中相應(yīng)字符“失配”時(shí)，在模式中需重新和主串中該字符進(jìn)行比較的字符的位置。由此就可以得出前面next函數(shù)的求值方法。KMP算法搜索階段在最壞的情況下時(shí)聞復(fù)雜度為O(n*m)，但在一般情況下，其實(shí)際的執(zhí)行時(shí)間近似于O(n+m)，S

25、hift表的存在需要額外的空間為O(m)。在大多數(shù)情況下，KMP算法并不比BF算法好很多，但KMP算法確保了線性，并且其擴(kuò)展性適合求解更難的問(wèn)題，尤其是因?yàn)镵MP算法不需要回溯，在處理從外設(shè)讀入的龐大文件時(shí)，這種特性很有價(jià)值。BM算法是由Boyer和Moore于1977年提出，該算法是目前應(yīng)用最為廣泛的單模式匹配算法。BM算法的一個(gè)最主要的特點(diǎn)是，在對(duì)字符串的匹配過(guò)程中，可以跳過(guò)很多無(wú)用的字符，即不對(duì)無(wú)用的字符進(jìn)行匹配。通過(guò)這種跳躍式的匹配，獲得了較高的執(zhí)行效率。有實(shí)驗(yàn)數(shù)據(jù)表明，BM算法的匹配速度大約是KMP算法的35倍。BM算法描述15：第一步：預(yù)處理，算法根據(jù)預(yù)先計(jì)算好的兩個(gè)數(shù)組將模式字符

26、串向右移動(dòng)盡可能遠(yuǎn)的距離。計(jì)算Skip數(shù)組和Shift數(shù)組，分別代表BC規(guī)則和GS規(guī)則。第二步：從右向左逐個(gè)字符比較文本字符串和模式字符串，單個(gè)字符匹配則繼續(xù)比較。如果到達(dá)模式字符串的最左邊，則成功發(fā)生了匹配，輸出；如果發(fā)生字符失配，則轉(zhuǎn)第三步。第三步：取失配字符相應(yīng)的Skip數(shù)組和Shift數(shù)組中的數(shù)值最大的一個(gè)，作為移動(dòng)距離，將模式字符串右移。如果己到達(dá)文本字符串的末尾，則退出算法；否則轉(zhuǎn)回到第二步執(zhí)行。BM算法被設(shè)計(jì)成為在文本中搜索單一模式字符串的算法，在單一模式的字符串匹配算法中，BM算法一般被認(rèn)為是性能最佳的。而在內(nèi)容過(guò)濾和檢測(cè)中有很多種關(guān)鍵詞模式需要匹配，因此BM算法需要對(duì)每一種模

27、式分別進(jìn)行匹配。BM算法的預(yù)處理階段的時(shí)間空間復(fù)雜性是O(m+n)，查找階段的時(shí)間復(fù)雜性是O(mn)，查找非周期性模式時(shí)的最壞情況下比較次數(shù)是3n。BM算法最壞時(shí)間復(fù)雜度是O(mn)，最好時(shí)間復(fù)雜度是O(n)。對(duì)多模式字符串進(jìn)行匹配，直接采用BM算法的復(fù)雜度是O(kn)。BM算法需要預(yù)處理也需要輔助空問(wèn)邏輯上也相對(duì)比較復(fù)雜。但是整個(gè)算法執(zhí)行的效率相對(duì)較高。如果字符越多，效率越高。因此BM算法在漢字文本串匹配效率要高于英文文本串的匹配。它是對(duì)BM算法的改進(jìn)，思想是通過(guò)目標(biāo)串和模式串中字符的最后一個(gè)位置對(duì)應(yīng)字符的下一個(gè)字符來(lái)決定右移的字符個(gè)數(shù)。算法描述如下：(1)模式串從左向右移動(dòng)，匹配自右向左進(jìn)

28、行；(2)若匹配失敗發(fā)生在PjTi：，先根據(jù)BM算法計(jì)算出字符Ti的位移量，再比較下一個(gè)字符：如果下一個(gè)字符出現(xiàn)在模式串中，則移動(dòng)的距離通過(guò)模式串決定。否則，跳過(guò)該字符從下一個(gè)字符開(kāi)始重新比較。依次循環(huán)，直到匹配為止。可以看出，該算法的最壞情況即為BM算法的情況，即右移的字符個(gè)數(shù)N>=distt，故相對(duì)BM算法具有一定的優(yōu)越性。BMH算法預(yù)處理時(shí)間復(fù)雜度為O(m+o)，空間復(fù)雜度先0(o)，o是與Pattern、Text相關(guān)的有限字符集長(zhǎng)度。查找階段時(shí)間復(fù)雜度為O(mn)，在一般情況下，BMH算法比BM有更好的性能，它只使用了一個(gè)數(shù)組，簡(jiǎn)化了初始化過(guò)程。2.3多模式匹配1975年，貝爾實(shí)

29、驗(yàn)室的Alfred VAho和Margaret JCorasick提出了著名的多模式匹配算法一一AC自動(dòng)機(jī)匹配算法(簡(jiǎn)稱AC算法)。該算法最早被使用在圖書(shū)館的書(shū)目查詢程序中，取得了很好的效果。AC算法描述（例如模式集SP=he，she，his，hers）：預(yù)處理階段，模式樹(shù)的各個(gè)節(jié)點(diǎn)作為狀態(tài)，根節(jié)點(diǎn)作為初態(tài)，標(biāo)簽為模式的節(jié)點(diǎn)作為終態(tài)，利用轉(zhuǎn)向函數(shù)g和失效函數(shù)f作為轉(zhuǎn)移函數(shù)，將模式樹(shù)擴(kuò)展成一個(gè)樹(shù)型有限自動(dòng)機(jī)。見(jiàn)圖2-4由模式樹(shù)擴(kuò)展所得的AC自動(dòng)機(jī)M是1個(gè)6元組：M= (Q，g，f，qo，F(xiàn))其中：(1)Q是有限狀態(tài)集(模式樹(shù)上的節(jié)點(diǎn))；(2)是有窮的輸入字符表(數(shù)據(jù)包中可能出現(xiàn)的所有字符)；(3

30、)g是轉(zhuǎn)移函數(shù)，該函數(shù)定義如下：g(S，a)：從當(dāng)前狀態(tài)S開(kāi)始，沿著邊上標(biāo)簽為a的路徑所到的狀態(tài)。假如(U，v)邊上的標(biāo)簽為a，那么g(U，a)=v；如果根節(jié)點(diǎn)上出來(lái)的邊上的標(biāo)簽沒(méi)有a，則g(0，a)=O，即如果沒(méi)有匹配的字符出現(xiàn)，自動(dòng)機(jī)停留在初態(tài)；(4)f(不匹配時(shí)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移)也是轉(zhuǎn)移函數(shù)，該函數(shù)定義如下：f(S)：當(dāng)w是L(s)最長(zhǎng)真后綴并且W是某個(gè)模式的前綴，那么f(S)就是以W為標(biāo)簽的那個(gè)節(jié)點(diǎn)；(5)qoQ是初態(tài)(根節(jié)點(diǎn)，標(biāo)識(shí)符為0)；(6)F量Q是終態(tài)集(以模式為標(biāo)簽的節(jié)點(diǎn)集)。這樣，在文本字符串中查找模式字符串的過(guò)程轉(zhuǎn)化成在模式樹(shù)中的查找過(guò)程。查找一個(gè)文本字符串T時(shí)從模式樹(shù)的

31、根節(jié)點(diǎn)開(kāi)始，沿著以T中字符為標(biāo)簽的路徑往下走：若自動(dòng)機(jī)能夠抵達(dá)終態(tài)v，則說(shuō)明T中存在模式L(v)：否則不存在模式。圖2-4 模式樹(shù)AC算法模式匹配的時(shí)間復(fù)雜度是O(n)，并且與模式集中模式字符串的個(gè)數(shù)和每個(gè)模式字符串的長(zhǎng)度無(wú)關(guān)。無(wú)論模式字符串P是否出現(xiàn)在文本字符串T中，T中的每個(gè)字符都必須輸入狀態(tài)機(jī)中，所以無(wú)論是最好情況還是最壞情況，AC算法模式匹配的時(shí)間復(fù)雜度都是0(n)，包括預(yù)處理時(shí)間在內(nèi)，AC算法總時(shí)間復(fù)雜度是O(M+n)，其中M為所有模式字符串的長(zhǎng)度總和。AC算法的查找效率明顯高于BM算法。但是，AC算法在對(duì)文本字符串匹配的過(guò)程中沒(méi)有跳躍，無(wú)法跳過(guò)不必要的比較，并且有限狀態(tài)自動(dòng)機(jī)算法是

32、以空間換時(shí)間的經(jīng)典算法，當(dāng)模式集較大時(shí)可能產(chǎn)生內(nèi)存膨脹問(wèn)題。因此在實(shí)際的匹配過(guò)程中，AC算法不可能是性能最佳的搜索算法。AC-BM算法是在AhoCorasick算法的基礎(chǔ)上，結(jié)合BoyerMoore算法的跳躍思想，產(chǎn)生的一種多模式匹配算法。在一般情況下，由于應(yīng)用了BM算法的跳躍式思維，所以不需要對(duì)文本的每個(gè)字符進(jìn)行匹配。在BM算法的基礎(chǔ)上引入了AC算法，來(lái)提高匹配速度，跳過(guò)盡可能多的字符，在模式字符串較長(zhǎng)和較短的情況下，該算法都具有很好的性能。AC-BM算法描述：設(shè)模式樹(shù)中最短模式串的長(zhǎng)度為L(zhǎng)，第一次比較是從待匹配的文本字符串的末端向前取L個(gè)字符與模式樹(shù)的根字符對(duì)齊，然后從樹(shù)的根字符開(kāi)始比較，

33、當(dāng)出現(xiàn)不匹配的字符時(shí)：(1)若目標(biāo)字符不在任何模式串中，則模式樹(shù)偏移量為L(zhǎng)位；(2)移動(dòng)到另一模式串前綴的下一位置；(3)將模式樹(shù)移動(dòng)到作為樹(shù)中另一個(gè)模式后綴能夠正確匹配目標(biāo)串的某個(gè)前綴的下一個(gè)位置。要注意的是：AC-BM算法在移動(dòng)過(guò)程中，模式樹(shù)移動(dòng)的偏移量不能超過(guò)最短模式串的長(zhǎng)度L。我們?cè)O(shè)模式字符串集合中，字符串最小長(zhǎng)度為minlen，最大長(zhǎng)度為maxlen，待匹配文本長(zhǎng)度為n，則在最優(yōu)情況下，時(shí)間復(fù)雜度為O(nminlen)，在最壞情況下，時(shí)間復(fù)雜度為O(n*maxlen)。AC-BM算法結(jié)合多模式匹配AC和單模式匹配BM兩種算法的優(yōu)點(diǎn)，既可以同時(shí)匹配多個(gè)模式又可以跳過(guò)不必要的字符，因此相

34、比其它模式匹配算法具有較高的性能和效率。2.4影響模式匹配算法的因素對(duì)于一個(gè)模式匹配算法來(lái)說(shuō)，在實(shí)際應(yīng)用中，最為關(guān)注的問(wèn)題有以下幾個(gè)方面1819：(1)正確性：即誤判率和漏判率，這與模式的選擇是密切相關(guān)的，如果模式的選擇比較嚴(yán)格，那么誤判率和漏判率一定會(huì)下降，但是過(guò)于嚴(yán)格的模式會(huì)影響識(shí)別的速度；同時(shí)過(guò)于簡(jiǎn)短的模式又會(huì)影響誤判率和漏判率，所以要選擇一個(gè)最優(yōu)的折衷點(diǎn)。(2)速度：即時(shí)間復(fù)雜性，這是評(píng)價(jià)一個(gè)模式匹配算法的重要的標(biāo)準(zhǔn)之一。隨著網(wǎng)絡(luò)速度的提高，通常要求模式匹配能以線速率執(zhí)行，特別是在一些實(shí)時(shí)性的系統(tǒng)中，對(duì)模式匹配的速度有很高的要求。一般情況下算法的時(shí)間復(fù)雜性，首先是預(yù)處理時(shí)間復(fù)雜性，其次

35、是匹配過(guò)程中的時(shí)間復(fù)雜性，最后是最壞情況和最好情況下的時(shí)間復(fù)雜性，特別是最壞情況下的復(fù)雜性，是算法研究中的一個(gè)重要方面。而在上述三種情況的時(shí)間復(fù)雜性中，模式的因素都是一個(gè)不可缺少的原因。簡(jiǎn)潔有效的模式不僅可以降低預(yù)處理的時(shí)間復(fù)雜度，而且還能縮短匹配過(guò)程的時(shí)間，至于最壞和最好的時(shí)間復(fù)雜度，在很大程度上受控于模式的規(guī)模。所以若要提高算法的速度，提高模式的有效性是一個(gè)重要途徑。(3)資源消耗：在模式的預(yù)處理階段和模式匹配階段，對(duì)內(nèi)存的需求也是應(yīng)用中關(guān)注的重要問(wèn)題之一，盡管目前內(nèi)存的容量提高了很多，但是龐大的內(nèi)存占有量會(huì)減慢算法的速度，所以現(xiàn)在人們常常借助于硬件實(shí)現(xiàn)算法。第3章 FPGA的基本知識(shí)本章

36、主要介紹FPGA的基本概念，F(xiàn)PGA與CPLD的關(guān)系，硬件描述語(yǔ)言的選擇。3.1FPGA簡(jiǎn)介21FPGA（FieldProgrammable Gate Array），即現(xiàn)場(chǎng)可編程門(mén)陣列，它是在PAL、GAL、CPLD等可編程器件的基礎(chǔ)上進(jìn)一步發(fā)展的產(chǎn)物。它是作為專用集成電路（ASIC）領(lǐng)域中的一種半定制電路而出現(xiàn)的，既解決了定制電路的不足，又克服了原有可編程器件門(mén)電路數(shù)有限的缺點(diǎn)。目前以硬件描述語(yǔ)言（Verilog 或 VHDL）所完成的電路設(shè)計(jì)，可以經(jīng)過(guò)簡(jiǎn)單的綜合與布局，快速的燒錄至 FPGA 上進(jìn)行測(cè)試，是現(xiàn)代 IC 設(shè)計(jì)驗(yàn)證的技術(shù)主流。這些可編輯元件可以被用來(lái)實(shí)現(xiàn)一些基本的邏輯門(mén)電路（比

37、如AND、OR、XOR、NOT）或者更復(fù)雜一些的組合功能比如解碼器或數(shù)學(xué)方程式。在大多數(shù)的FPGA里面，這些可編輯的元件里也包含記憶元件例如觸發(fā)器（Flipflop）或者其他更加完整的記憶塊。 系統(tǒng)設(shè)計(jì)師可以根據(jù)需要通過(guò)可編輯的連接把FPGA內(nèi)部的邏輯塊連接起來(lái)，就好像一個(gè)電路試驗(yàn)板被放在了一個(gè)芯片里。一個(gè)出廠后的成品FPGA的邏輯塊和連接可以按照設(shè)計(jì)者而改變，所以FPGA可以完成所需要的邏輯功能。 FPGA一般來(lái)說(shuō)比ASIC（專用集成芯片） 的速度要慢，無(wú)法完成復(fù)雜的設(shè)計(jì)，而且消耗更多的電能。但是他們也有很多的優(yōu)點(diǎn)比如可以快速成品，可以被修改來(lái)改正程序中的錯(cuò)誤和更便宜的造價(jià)。廠商也可 能會(huì)提

38、供便宜的但是編輯能力差的FPGA。因?yàn)檫@些芯片有比較差的可編輯能力，所以這些設(shè)計(jì)的開(kāi)發(fā)是在普通的FPGA上完成的，然后將設(shè)計(jì)轉(zhuǎn)移到一個(gè)類似 于ASIC的芯片上。另外一種方法是用CPLD（復(fù)雜可編程邏輯器件備）。3.2FPGA與CPLD的關(guān)系以及工作原理CPLD與FPGA的關(guān)系：早在1980年代中期，F(xiàn)PGA已經(jīng)在PLD設(shè)備中扎根。CPLD和FPGA包括了一些相對(duì)大數(shù)量的可編輯邏輯單元。CPLD邏輯門(mén)的密度在幾千到幾萬(wàn)個(gè)邏輯單元之間，而FPGA通常是在幾萬(wàn)到幾百萬(wàn)。 CPLD和FPGA的主要區(qū)別是他們的系統(tǒng)結(jié)構(gòu)。CPLD是一個(gè)有點(diǎn)限制性的結(jié)構(gòu)。這個(gè)結(jié)構(gòu)由 一個(gè)或者多個(gè)可編輯的結(jié)果之和的邏輯組列和

39、一些相對(duì)少量的鎖定的寄存器。這樣的結(jié)果是缺乏編輯靈活性，但是卻有可以預(yù)計(jì)的延遲時(shí)間和邏輯單元對(duì)連接單元高 比率的優(yōu)點(diǎn)。而FPGA卻是有很多的連接單元，這樣雖然讓它可以更加靈活的編輯，但是結(jié)構(gòu)卻復(fù)雜的多。 CPLD和FPGA另外一個(gè)區(qū)別是大多數(shù)的FPGA含有高層次的內(nèi)置模塊（比如加法器和乘法器）和內(nèi)置的記憶體。一個(gè)因此有關(guān)的重要區(qū)別是很多新的FPGA支持完全的或者部分的系統(tǒng)內(nèi)重新配置。允許他們的設(shè)計(jì)隨著系統(tǒng)升級(jí)或者動(dòng)態(tài)重新配置而改變。一些FPGA可以讓設(shè)備的一部分重新編輯而其他部分繼續(xù)正常運(yùn)行。FPGA的工作原理：（1）采用FPGA設(shè)計(jì)ASIC電路(專用集成電路)，用戶不需要投片生產(chǎn)，就能得到合

40、用的芯片。 （2）FPGA可做其它全定制或半定制ASIC電路的中試樣片。 （3）FPGA內(nèi)部有豐富的觸發(fā)器和IO引腳。 （4）FPGA是ASIC電路中設(shè)計(jì)周期最短、開(kāi)發(fā)費(fèi)用最低、風(fēng)險(xiǎn)最小的器件之一。 （5) FPGA采用高速CHMOS工藝，功耗低，可以與CMOS、TTL電平兼容。 可以說(shuō)，F(xiàn)PGA芯片是小批量系統(tǒng)提高系統(tǒng)集成度、可靠性的最佳選擇之一。 FPGA是由存放在片內(nèi)RAM中的程序來(lái)設(shè)置其工作狀態(tài)的，因此，工作時(shí)需要對(duì)片內(nèi)的RAM進(jìn)行編程。用戶可以根據(jù)不同的配置模式，采用不同的編程方式。 加電時(shí)，F(xiàn)PGA芯片將EPROM中數(shù)據(jù)讀入片內(nèi)編程RAM中，配置完成后，F(xiàn)PGA進(jìn)入工作狀態(tài)。掉電后

41、，F(xiàn)PGA恢復(fù)成白片，內(nèi)部邏輯關(guān)系消失，因此，F(xiàn)PGA能夠反復(fù)使用。FPGA的編程無(wú)須專用的FPGA編程器，只須用通用的EPROM、PROM編程器即可。當(dāng)需要修改FPGA功能時(shí)，只需換一片EPROM即可。這樣，同一片F(xiàn)PGA，不同的編程數(shù)據(jù)，可以產(chǎn)生不同的電路功能。因此，F(xiàn)PGA的使用非常靈活。FPGA有多種配置模式：并行主模式為一片F(xiàn)PGA加一片EPROM的方式；主從模式可以支持一片PROM編程多片F(xiàn)PGA；串行模式可以采用串行PROM編程FPGA；外設(shè)模式可以將FPGA作為微處理器的外設(shè)，由微處理器對(duì)其編程。 如何實(shí)現(xiàn)快速的時(shí)序收斂、降低功耗和 成本、優(yōu)化時(shí)鐘管理并降低FPGA與PCB并行

42、設(shè)計(jì)的復(fù)雜性等問(wèn)題，一直是采用FPGA的系統(tǒng)設(shè)計(jì)工程師需要考慮的關(guān)鍵問(wèn)題。如今，隨著FPGA向更高密 度、更大容量、更低功耗和集成更多IP的方向發(fā)展，系統(tǒng)設(shè)計(jì)工程師在從這些優(yōu)異性能獲益的同時(shí)，不得不面對(duì)由于FPGA前所未有的性能和能力水平而帶來(lái)的 新的設(shè)計(jì)挑戰(zhàn)。3.3硬件語(yǔ)言選擇22Verilog HDL與VHDL是兩種最常見(jiàn)的硬件描述語(yǔ)言，Verilog HDL與VHDL相比有以下一些優(yōu)點(diǎn)：(1)可以用來(lái)進(jìn)行各種層次的邏輯設(shè)計(jì)，也可以進(jìn)行數(shù)字系統(tǒng)的邏輯綜合、仿真驗(yàn)證和時(shí)序分析等。Verilog HDL適合算法級(jí)(Algorithm)、寄存器傳輸級(jí)(RTL)、邏輯級(jí)(Logic)、門(mén)級(jí)(Gat

43、e)和版圖級(jí)(Layout)等各個(gè)層次的設(shè)計(jì)和描述。(2)VHDL偏重于標(biāo)準(zhǔn)化考慮，而Verilog HDL與EDA工具的結(jié)合更為緊密。VHDL是國(guó)際上第一個(gè)標(biāo)準(zhǔn)化的HDL語(yǔ)言(IEEE-1076)，是為了實(shí)現(xiàn)美國(guó)國(guó)防部VHSIC計(jì)劃所推出的各個(gè)電子部件供應(yīng)商具有統(tǒng)一的數(shù)據(jù)交換格式的要求。相比之下，Verilog HDL則是在全球最大的EDA/ESDA供應(yīng)商Cadence公司的扶持下針對(duì)EDA工具開(kāi)發(fā)的HDL語(yǔ)言。(3) 與VHDL相比，Verilog HDL的編程風(fēng)格更加簡(jiǎn)潔明了，更接近高級(jí)計(jì)算機(jī)語(yǔ)言的語(yǔ)法形式。有鑒于此，本設(shè)計(jì)采用Verilog HDL語(yǔ)言作為硬件描述語(yǔ)言。第4章 KMP算

44、法VerilogHDL實(shí)現(xiàn)本章主要介紹KMP算法的VerilogHDL實(shí)現(xiàn)設(shè)計(jì)過(guò)程，一些調(diào)試碰到的問(wèn)題及解決方法。4.1模式串輸入克努特莫里斯普拉特操作（簡(jiǎn)稱KMP算法）。KMP算法的關(guān)鍵是根據(jù)給定的模式串pattern定義一個(gè)next函數(shù)。next函數(shù)包含了模式串本身局部匹配的信息。為了用Verilog HDL實(shí)現(xiàn)KMP算法，我們需要在熟悉算法原理的基礎(chǔ)上進(jìn)行程序設(shè)計(jì)。KMP算法的原理已經(jīng)在論文的第二章詳細(xì)介紹過(guò)，這里就不再累述。圖4-1模式串輸入代碼由于Verilog HDL語(yǔ)言不像C語(yǔ)言一樣可以很方便的申請(qǐng)內(nèi)存用于存放變量或者數(shù)據(jù)，而既然我們的工作是要進(jìn)行字符串的查找，那么首先我們需要有

45、兩個(gè)字符串。如何存放這兩個(gè)字符串？有兩種方法：一種是將字符串存放在FPGA內(nèi)部的存儲(chǔ)器中，比如使用Quartus II自帶的MegaWizard Plug-in Manger工具在FPGA內(nèi)部定制一個(gè)RAM或者ROM存放字符串，或者直接定義一個(gè)數(shù)組，即使用FPGA的邏輯單元構(gòu)造RAM用于存放字符串。當(dāng)然后一種方式的代價(jià)會(huì)比較高，尤其是當(dāng)FPGA的邏輯單元相對(duì)較少時(shí)，隨意地?fù)]霍這種寶貴的資源就不可取。對(duì)于本設(shè)計(jì)，由于我們只是需要驗(yàn)證算法，因此用作主串的字符串不需要很長(zhǎng)（實(shí)際使用了一個(gè)長(zhǎng)度為16的字符串），因此可以直接定義數(shù)組來(lái)存放這個(gè)字符串，這樣做可以避免另外設(shè)計(jì)電路用于控制RAM的讀取。另外一

46、種方法是令字符串從外部通過(guò)引腳輸入到FPGA中，然后再存放在FPGA的內(nèi)部RAM中，采用這樣的設(shè)計(jì)方式，字符串的內(nèi)容可以很方便地改動(dòng)，本設(shè)計(jì)中的模式串就采用這種方式從外部輸入。首先我們需要設(shè)計(jì)一個(gè)模式串的輸入接口，模式串輸入的Verilog HDL代碼如圖4-1所示：我們的Verilog HDL開(kāi)發(fā)環(huán)境為Quartus II 8.0 Wed Edition，Quartus II是一個(gè)功能強(qiáng)大的集成開(kāi)發(fā)環(huán)境，支持從源代碼編輯到仿真、布局布線和芯片燒錄的全部功能。上述代碼中，k是一個(gè)計(jì)數(shù)值，寬度為4位，表示當(dāng)前輸入的字符的個(gè)數(shù)，在復(fù)位時(shí)初始化為0。在每個(gè)時(shí)鐘的上升沿，k遞增1。p是一個(gè)位寬為8的端

47、口，外部數(shù)據(jù)就從這個(gè)端口輸入。在每個(gè)時(shí)鐘的上升沿，p端口的值賦給patternk寄存器。因?yàn)槟Ｊ酱拈L(zhǎng)度是8，因此當(dāng)計(jì)數(shù)值k>7時(shí)就不再需要存儲(chǔ)端口p的數(shù)據(jù)，但是為了顯示模式串輸入已經(jīng)完成，必須給出一個(gè)提示信息，這個(gè)提示信息不需要輸出到FPGA的外部，只需要提醒內(nèi)部的相關(guān)檢測(cè)機(jī)制就可以，wr_ed就是這個(gè)提示信息，并且將它定義為一個(gè)reg型的變量，位寬為1位。當(dāng)k>7時(shí)就令wr_ed為1，表示模式串已經(jīng)全部輸入。該部分的功能仿真結(jié)果見(jiàn)圖4-2：圖 4-2 模式串輸入仿真結(jié)果其中pattern0pattern7是wire型的輸出口連接到pattern0pattern7，這只是一組用于

48、觀測(cè)FPAG內(nèi)部寄存器值的端口變量，而這一組端口變量對(duì)一設(shè)計(jì)本身并不是必需的，因此當(dāng)模式串輸入接口的設(shè)計(jì)完成以后，可以撤銷這一組端口。從仿真結(jié)果中可以看出，當(dāng)wr_ed變?yōu)?時(shí)，說(shuō)明模式串應(yīng)當(dāng)已經(jīng)輸入到FPGA內(nèi)部的數(shù)組中了，我們查看此時(shí)的pattern0pattern7可以發(fā)現(xiàn)，模式串確實(shí)已經(jīng)輸入到內(nèi)部的數(shù)組中了，這與我們的設(shè)想吻合。4.2next函數(shù)的計(jì)算為了便于Verilog HDL程序設(shè)計(jì)，我們首先用C語(yǔ)言描述KMP算法。之所以先用C語(yǔ)言描述KMP算法，是因?yàn)閂erilog HDL最為一種高級(jí)的硬件描述語(yǔ)言，與C語(yǔ)言的風(fēng)格有許多類似之處，其中有許多語(yǔ)句，如if語(yǔ)句、case語(yǔ)句和C語(yǔ)言

49、中的對(duì)應(yīng)語(yǔ)句十分相似。如下所示是next函數(shù)的C語(yǔ)言代碼，在Visual Studio 2008下編輯和調(diào)試代碼。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 < len; i+) ( nextTemp = nexti-1; while (patt

50、erni-1 !=patternnextTemp && nextTemp !=-1 ) ( nextTemp = nextnextTemp; ) nexti = nextTemp +1; ) return next;)代碼的功能即實(shí)現(xiàn)對(duì)next值的計(jì)算。下面我們將詳細(xì)說(shuō)明如何根據(jù)C語(yǔ)言代碼編寫(xiě)Verilog HDL代碼，實(shí)現(xiàn)KMP算法。仔細(xì)觀測(cè)上述代碼，我們會(huì)發(fā)現(xiàn)這個(gè)函數(shù)其實(shí)可以分解為四個(gè)步驟：（1）i的值遞增1；（2）令nextTempnexti-1；（3）判斷patterni-1!=patternnextTemp&&nextTemp!=-1是否成立，若成立則

51、執(zhí)行nextTemp=nextnextTemp，并且接下來(lái)繼續(xù)進(jìn)入過(guò)程3；否則跳過(guò)這一步進(jìn)入過(guò)程4；（4）令nexti=nextTemp+1，回到過(guò)程1；圖4-3 next函數(shù)狀態(tài)圖事實(shí)上我們可以用一個(gè)狀態(tài)圖表述上述過(guò)程如圖4-3這張狀態(tài)轉(zhuǎn)移圖的內(nèi)容與上述的C語(yǔ)言代碼的流程是完全一致的，有了這個(gè)狀態(tài)圖，我們就可以編寫(xiě)一個(gè)狀態(tài)機(jī)，來(lái)實(shí)現(xiàn)next函數(shù)。具體代碼如圖4-4圖4-4 next函數(shù)的計(jì)算在上述的代碼中nextdone是一個(gè)內(nèi)部標(biāo)志位，它在另一個(gè)always塊中執(zhí)行這樣的功能：當(dāng)next函數(shù)中的counter_i>7時(shí)，nextdone就會(huì)等于1，表示next函數(shù)已經(jīng)計(jì)算完畢，可以進(jìn)

52、行后續(xù)的字符匹配工作了。nextdone的功能與模式串輸入函數(shù)中的wr_ed具有類似的功能。上述代碼的結(jié)構(gòu)與用C語(yǔ)言編寫(xiě)的代碼十分相似，這就說(shuō)明我們?cè)诶斫饬怂惴ㄔ淼幕A(chǔ)上，可以很方便的將C語(yǔ)言編寫(xiě)的代碼改寫(xiě)成Verilog HDL語(yǔ)言。但是這兩種語(yǔ)言還是有很大的區(qū)別的，與C語(yǔ)言不同，在Verilog HDL中是沒(méi)有定義諸如char、int、float這樣的數(shù)據(jù)類型，所有的數(shù)據(jù)類型都是二進(jìn)制數(shù)據(jù)，數(shù)據(jù)的每一位只有0和1兩種取值，我們無(wú)法定義一個(gè)數(shù)為char型或者float型。因此在表示負(fù)數(shù)的時(shí)候我們就會(huì)不能簡(jiǎn)單地賦值，而因當(dāng)采用補(bǔ)碼的形式表示，比如-1我們就可以表示成4b1111，在數(shù)字系統(tǒng)綜

53、合的過(guò)程中這個(gè)數(shù)值就會(huì)被認(rèn)為是-1。這一點(diǎn)是Verilog HDL語(yǔ)言與高級(jí)計(jì)算機(jī)語(yǔ)言存在巨大差別的地方。接下來(lái)我們需要驗(yàn)證我們?cè)O(shè)計(jì)的代碼功能是否正確，這是很容易驗(yàn)證的。我們首先在C語(yǔ)言代碼中對(duì)一個(gè)模式串“abaabcac”計(jì)算next值，得到如圖4-5的運(yùn)算結(jié)果：圖4-5 Visual C+下next計(jì)算結(jié)果由上圖可見(jiàn)對(duì)于“abaabcac”這個(gè)字符串，next函數(shù)的計(jì)算結(jié)果是-1，0，0，1，1，2，0，1。另外我們還發(fā)現(xiàn)程序的運(yùn)行結(jié)果提示在主串中找到的模式串的其實(shí)位置為-1，為什么呢？其實(shí)這是因?yàn)樵谶@一次運(yùn)行中我們?cè)O(shè)置的主串中沒(méi)有包含一個(gè)有效的模式串，因此運(yùn)行結(jié)果是找不到匹配的字符串，在

54、這種情況下我們?cè)诳刂婆_(tái)輸出一個(gè)-1表示沒(méi)有找到匹配的字符串。接下來(lái)我們來(lái)測(cè)試我們用Verilog HDL編寫(xiě)的代碼功能是否正確。Quartus II中新建一個(gè)仿真波形文件，然后設(shè)置仿真模式為功能仿真（由于我們只是要驗(yàn)證電路的工作機(jī)制是否正確，因此只要選擇功能仿真即可），然后將端口變量添加到仿真窗口中，設(shè)置時(shí)鐘和其他輸入變量，點(diǎn)擊“Generate Functional Simulation Netlist”，生成功能仿真的仿真網(wǎng)表文件，然后運(yùn)行仿真，仿真結(jié)果如圖4-6所示：圖4-6 next函數(shù)在Quartus II下的仿真結(jié)果由上圖可見(jiàn)，當(dāng)nextdone為1時(shí)，說(shuō)明next函數(shù)已經(jīng)計(jì)算完成

55、，這個(gè)時(shí)候我們可以查看next數(shù)組的值，由于next0next7是一組線網(wǎng)型的端口變量，直接反映next數(shù)值的值，因此我們觀查next0next7的值，發(fā)現(xiàn)其數(shù)值為-1、0、0、1、1、2、0、1。這個(gè)運(yùn)算結(jié)果與C語(yǔ)言的運(yùn)算結(jié)果是一致的，這說(shuō)明我們?cè)O(shè)計(jì)的next函數(shù)狀態(tài)機(jī)是完全正確的！4.3字符串匹配在設(shè)計(jì)完next函數(shù)的Verilog HDL實(shí)現(xiàn)之后，我們的設(shè)計(jì)的最核心部分已經(jīng)完成了，接下來(lái)要做的工作就是根據(jù)next數(shù)組進(jìn)行字符串的匹配操作。既然是字符串匹配，那么我們必然需要一個(gè)主串供我們查找，前面已經(jīng)提到過(guò)FPGA中數(shù)據(jù)的存儲(chǔ)方式，為了方便調(diào)用存儲(chǔ)的數(shù)據(jù)，我們將主串存放在內(nèi)部數(shù)組中，占用FPGA的片上邏輯單元，在系統(tǒng)復(fù)位時(shí)對(duì)數(shù)組中的值進(jìn)行初始化。同樣的，我們先來(lái)看字符串匹配的C語(yǔ)言代碼如下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); pr