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

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

3、會在第四章中介紹。關鍵詞：模式匹配算法；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模式匹配算法的發展與研究現狀1第2章 模式匹配算法32.1模式匹配定義32.2單模式匹配334672.3多模式匹配7782.4影響模式匹配算法的因素9第3章FPGA基本的知識113.1FPGA簡介113.2FPGA與CPLD的關系以及工作原理113.3硬件語言選擇12第4章KMP算法VerilogHDL實現144.1模式

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

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

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

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

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

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

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

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

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

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

19、問復雜度是O(mn)。最壞情況的例子之一是文本串是某一相同字符的字符串而模式串也是這一字符的字符串。這種算法的缺陷是匹配過程中帶有回溯，準確地說是當匹配不成功的時候，之前進行的匹配完全變為無效的,所有的比較需要從模式串首字符重新開始。BF算法的優點是不需要預處理。輔助的空間是常量，即只需要幾個變量的臨時存儲區域。模式串和某個窗口內匹配的順序是任意的，向左或者向右都是可以的。KMP算法是Knuth等人在BF算法的基礎上提出來的。從本質上講，KMP算法就是出現不匹配情況下帶有智能指針初始化的BF算法。為了在不匹配時重新定位指針，KMP算法需要進行預處理算出一個Shift表來。基本思想：KMP算法利

20、用已匹配成功部分的信息，即前綴(模式字符串中存在的相同子串)，可以使模式字符串向前推進若干個字符位置，而不只是一個字符，避免了重復比較，同時也實現了文本字符串指針的無回溯。要點是：我們能夠通過預先對模式的分析獲得知識，即如果在模式的位置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進行匹

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

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

23、部分”匹配結果是：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"，且滿足0<k<j,則當匹配過程中，主串中字

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

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

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

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

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

29、驗室的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

30、)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時從模式樹的

31、根節點開始，沿著以T中字符為標簽的路徑往下走：若自動機能夠抵達終態v，則說明T中存在模式L(v)：否則不存在模式。圖2-4 模式樹AC算法模式匹配的時間復雜度是O(n)，并且與模式集中模式字符串的個數和每個模式字符串的長度無關。無論模式字符串P是否出現在文本字符串T中，T中的每個字符都必須輸入狀態機中，所以無論是最好情況還是最壞情況，AC算法模式匹配的時間復雜度都是0(n)，包括預處理時間在內，AC算法總時間復雜度是O(M+n)，其中M為所有模式字符串的長度總和。AC算法的查找效率明顯高于BM算法。但是，AC算法在對文本字符串匹配的過程中沒有跳躍，無法跳過不必要的比較，并且有限狀態自動機算法是

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

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

34、比其它模式匹配算法具有較高的性能和效率。2.4影響模式匹配算法的因素對于一個模式匹配算法來說，在實際應用中，最為關注的問題有以下幾個方面1819：(1)正確性：即誤判率和漏判率，這與模式的選擇是密切相關的，如果模式的選擇比較嚴格，那么誤判率和漏判率一定會下降，但是過于嚴格的模式會影響識別的速度；同時過于簡短的模式又會影響誤判率和漏判率，所以要選擇一個最優的折衷點。(2)速度：即時間復雜性，這是評價一個模式匹配算法的重要的標準之一。隨著網絡速度的提高，通常要求模式匹配能以線速率執行，特別是在一些實時性的系統中，對模式匹配的速度有很高的要求。一般情況下算法的時間復雜性，首先是預處理時間復雜性，其次

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

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

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

38、供便宜的但是編輯能力差的FPGA。因為這些芯片有比較差的可編輯能力，所以這些設計的開發是在普通的FPGA上完成的，然后將設計轉移到一個類似 于ASIC的芯片上。另外一種方法是用CPLD（復雜可編程邏輯器件備）。3.2FPGA與CPLD的關系以及工作原理CPLD與FPGA的關系：早在1980年代中期，FPGA已經在PLD設備中扎根。CPLD和FPGA包括了一些相對大數量的可編輯邏輯單元。CPLD邏輯門的密度在幾千到幾萬個邏輯單元之間，而FPGA通常是在幾萬到幾百萬。 CPLD和FPGA的主要區別是他們的系統結構。CPLD是一個有點限制性的結構。這個結構由 一個或者多個可編輯的結果之和的邏輯組列和

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

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

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

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

43、e)和版圖級(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算

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

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

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

47、口，外部數據就從這個端口輸入。在每個時鐘的上升沿，p端口的值賦給patternk寄存器。因為模式串的長度是8，因此當計數值k>7時就不再需要存儲端口p的數據，但是為了顯示模式串輸入已經完成，必須給出一個提示信息，這個提示信息不需要輸出到FPGA的外部，只需要提醒內部的相關檢測機制就可以，wr_ed就是這個提示信息，并且將它定義為一個reg型的變量，位寬為1位。當k>7時就令wr_ed為1，表示模式串已經全部輸入。該部分的功能仿真結果見圖4-2：圖 4-2 模式串輸入仿真結果其中pattern0pattern7是wire型的輸出口連接到pattern0pattern7，這只是一組用于

48、觀測FPAG內部寄存器值的端口變量，而這一組端口變量對一設計本身并不是必需的，因此當模式串輸入接口的設計完成以后，可以撤銷這一組端口。從仿真結果中可以看出，當wr_ed變為1時，說明模式串應當已經輸入到FPGA內部的數組中了，我們查看此時的pattern0pattern7可以發現，模式串確實已經輸入到內部的數組中了，這與我們的設想吻合。4.2next函數的計算為了便于Verilog HDL程序設計，我們首先用C語言描述KMP算法。之所以先用C語言描述KMP算法，是因為Verilog HDL最為一種高級的硬件描述語言，與C語言的風格有許多類似之處，其中有許多語句，如if語句、case語句和C語言

49、中的對應語句十分相似。如下所示是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 < len; i+) ( nextTemp = nexti-1; while (patt

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

51、執行nextTemp=nextnextTemp，并且接下來繼續進入過程3；否則跳過這一步進入過程4；（4）令nexti=nextTemp+1，回到過程1；圖4-3 next函數狀態圖事實上我們可以用一個狀態圖表述上述過程如圖4-3這張狀態轉移圖的內容與上述的C語言代碼的流程是完全一致的，有了這個狀態圖，我們就可以編寫一個狀態機，來實現next函數。具體代碼如圖4-4圖4-4 next函數的計算在上述的代碼中nextdone是一個內部標志位，它在另一個always塊中執行這樣的功能：當next函數中的counter_i>7時，nextdone就會等于1，表示next函數已經計算完畢，可以進

52、行后續的字符匹配工作了。nextdone的功能與模式串輸入函數中的wr_ed具有類似的功能。上述代碼的結構與用C語言編寫的代碼十分相似，這就說明我們在理解了算法原理的基礎上，可以很方便的將C語言編寫的代碼改寫成Verilog HDL語言。但是這兩種語言還是有很大的區別的，與C語言不同，在Verilog HDL中是沒有定義諸如char、int、float這樣的數據類型，所有的數據類型都是二進制數據，數據的每一位只有0和1兩種取值，我們無法定義一個數為char型或者float型。因此在表示負數的時候我們就會不能簡單地賦值，而因當采用補碼的形式表示，比如-1我們就可以表示成4b1111，在數字系統綜

53、合的過程中這個數值就會被認為是-1。這一點是Verilog HDL語言與高級計算機語言存在巨大差別的地方。接下來我們需要驗證我們設計的代碼功能是否正確，這是很容易驗證的。我們首先在C語言代碼中對一個模式串“abaabcac”計算next值，得到如圖4-5的運算結果：圖4-5 Visual C+下next計算結果由上圖可見對于“abaabcac”這個字符串，next函數的計算結果是-1，0，0，1，1，2，0，1。另外我們還發現程序的運行結果提示在主串中找到的模式串的其實位置為-1，為什么呢？其實這是因為在這一次運行中我們設置的主串中沒有包含一個有效的模式串，因此運行結果是找不到匹配的字符串，在

54、這種情況下我們在控制臺輸出一個-1表示沒有找到匹配的字符串。接下來我們來測試我們用Verilog HDL編寫的代碼功能是否正確。Quartus II中新建一個仿真波形文件，然后設置仿真模式為功能仿真（由于我們只是要驗證電路的工作機制是否正確，因此只要選擇功能仿真即可），然后將端口變量添加到仿真窗口中，設置時鐘和其他輸入變量，點擊“Generate Functional Simulation Netlist”，生成功能仿真的仿真網表文件，然后運行仿真，仿真結果如圖4-6所示：圖4-6 next函數在Quartus II下的仿真結果由上圖可見，當nextdone為1時，說明next函數已經計算完成

55、，這個時候我們可以查看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); pr