KMP算法的FPGA實現(xiàn)-科技大學本科畢業(yè)設計.docx

本科畢業(yè)設計（2011屆）題 目KMP算法的FPGA實現(xiàn)學 院電子信息學院專 業(yè)集成電路設計與集成系統(tǒng)班 級學 號學生姓名指導教師完成日期誠 信 承 諾我謹在此承諾：本人所寫的畢業(yè)論文KMP算法的FPGA實現(xiàn)均系本人獨立完成，沒有抄襲行為，凡涉及其他作者的觀點和材料，均作了注釋，若有不實，后果由本人承擔。 承諾人（簽名）： 年 月 日摘 要 隨著網(wǎng)絡技術的迅猛發(fā)展，所要檢測的數(shù)據(jù)包越來越多，單純的依靠軟件來檢測，越來越顯得力不從心。伴隨著FPGA技術的發(fā)展，在硬件上實現(xiàn)模式匹配，來提高網(wǎng)絡數(shù)據(jù)處理速度的需求越來越普遍。把搜索算法固化到FPGA里，從而可以大大提高算法的速度，適應科技的迅速發(fā)展。本文重點分析了幾種典型的模式匹配算法。包括：BF算法、KMP算法、BM算法、BMH算法、AC算法和AC-BM算法。另外文章還介紹了FPGA的的相關基本知識以及硬件描述語言的選擇。綜合考慮現(xiàn)有的比較成熟的模式匹配算法，并且追蹤國外基于FPGA技術來實現(xiàn)模式匹配的研究成果，認為在硬件實現(xiàn)方面，KMP算法效率較高，結構簡單，可行性強，而且易于對主串進行多模式的匹配，所以選其作為模式匹配硬件模塊的核心算法，通過硬線邏輯來進一步提高串模式匹配的效率。本文KMP算法程序設計部分主要分為三個部分：模式串輸入、next函數(shù)的計算、字符串的匹配。具體情況會在第四章中介紹。關鍵詞：模式匹配算法；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模式匹配算法的發(fā)展與研究現(xiàn)狀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實現(xiàn)144.1模式串輸入144.2next函數(shù)的計算154.3字符串匹配194.4代碼通用性的驗證22第5章結束語27致謝28附錄31第1章 引言1.1研究背景1在網(wǎng)絡處理中，模式匹配是指將分組各域進行比特位的匹配處理。一般，模式匹配模塊有兩個輸入，一個是規(guī)則的模式表達式，另一個是分組域。它的輸出是輸入分組的各域是否與輸入模式的布爾值匹配。這類模式匹配的實質還是字符串匹配，它的基本運算就是從一個主字符串中找到某個特定模式串出現(xiàn)的位置。目前，串匹配算法一般是以模式串的長度為掃描窗口大小，在窗口中使用不同的掃描策略來進行匹配。假設模式串長為m，主串長為n，串匹配算法根據(jù)策略的不同，大致可以分為以下3類23：從前往后匹配模式前綴的KMP算法，從后往前匹配模式后綴的BM算法及其各種變形，以及從后往前匹配模式前綴的RF算法等等。KMP4算法是從前往后進行掃描，使用自動機記住己匹配模式前綴的正文內容，并依據(jù)這些內容來確定是否已經(jīng)匹配成功。換句話說，就是先對模式串進行預計算，然后再與主串匹配，而且主串不需要回溯，它的時間復雜度比較好，一般是O(m+n)。BM5算法及其變形是在掃描窗口中從后往前進行掃描，記住已匹配模式后綴的正文內容，并依據(jù)這些內容來進行窗口移動，這種方法雖然簡單易行，但是時間復雜度比較差，最壞情況下為0(m+n)，所以當串比較長時，效率就會很低。RF算法等是在從后往前進行掃描時，反向使用模式逆串的后綴自動機來匹配模式的前綴，這樣可以增大窗口移動的距離，從而獲得更好的平均時間復雜度，達到理論最優(yōu)結果。該方法效率較高，但是比較復雜，硬件實現(xiàn)難度大。綜合考慮現(xiàn)有的比較成熟的模式匹配算法，認為在硬件實現(xiàn)方面，KMP算法具有其他算法沒有的優(yōu)勢，所以本文選擇KMP算法作為研究的主要對象。1.2模式匹配算法的發(fā)展與研究現(xiàn)狀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算法的思想結合起來，獲得了更好的執(zhí)行效率。沿著AC算法這條路線，Crochemore等人將AC算法和DAWG結合，獲得了一種新的算法，稱為DAWG-MATCH。實驗結果表明，該算法比Comments-Walter的算法更有效率。此外，人們還提搬了其它一些多模式匹配算法。1994年，Sun Wu和Manber提出了第一個基于過濾思想的多模式匹配算法。這個算法將過濾思想和BM思想結合起來，在實際的應用中獲得了極其高的效率。實驗表明，在Sun Sparcl0上，他們的算法可以于10秒內完成在15.8M的文本中搜索10000個模式的工作。在WM算法的基礎上，Sun Wu和Manber實現(xiàn)了一個用于模糊匹配的工具agrep和一個文本檢索的工具glimpse，在實際的應用中都獲得了良好的效率。1996年，Robert Muth和Udi Manber給出了一個快速的多模式模糊匹配算法，這個算法也是基于過濾的思想，同時采用了兩級散列的技術，從而獲得了極高的執(zhí)行效率，實驗數(shù)據(jù)表明，該算法能在小于1秒的時間內完成在1M文本中對1000個模式的搜索和模糊匹配的過程。但是不幸的是，該算法只允許模式和文本子串之間存在1個不同點，這樣的約束限制了該算法在實際中的應用。1999年，在數(shù)據(jù)壓縮和位操作的思想上，Sun Kim和Yanggon Kim設計出了一個新的多模式匹配算法，實驗證明，該算法比Sun Wu和Manber的算法有更好的表現(xiàn)，特別是在小字符集上。目前對模式匹配算法的研究一部分還停留在單模式匹配算法，而對多模式匹配算法的研究主要集中在算法的綜述、測試以及對現(xiàn)有算法的一些相應改進上。這些改進的算法雖然也取得一定的成果，但是總體效果都不是很理想，主要是算法速度受限于模式的數(shù)目或者實現(xiàn)算法需要的空間消耗的內存太大。字符串的模糊匹配是近年來倍受關注的領域，模糊匹配允許在搜索時搜索出與模式有一些差別的文本中的字符串。在這個領域，有四條主要的技術路線：動態(tài)規(guī)劃算法；自動機算法；過濾算法；位并行算法。由于這不是本文研究的主要內容，故不做詳細介紹。第2章 模式匹配算法模式匹配分為單模式匹配和多模式匹配，一次在文本串中查找一個模式串出現(xiàn)的過程，稱為單模式匹配。同時查找一個模式串集合中的所有模式串的出現(xiàn)的過程稱為多模式匹配。本章主要討論幾種典型的單模式匹配算法和多模式匹配算法。2.1模式匹配定義字符串的模式匹配問題的形式化定義如下：在字符集上，給定一個長度為N的文本字符串T1N，以及一個長度為M的模式 字符串Pi1M。模式集數(shù)量用k來表示，模式集用P=pl，p2，pk來表示。如果對于l=S=N，存在TS+1S+M=Pi1M，則模式Pi在文本T的位置S處出現(xiàn)，即模式與文本匹配。字符串的模式匹配問題就是要尋找P在T中是否出現(xiàn)，以及出現(xiàn)的位置。例如：文本字符串T：Here is a beauterful picture模式字符串P：beauterful該例子顯示需要在文本字符串T中搜索模式字符串P：“beauterful，通過搜索我們發(fā)現(xiàn)模式字符串P：“beauterful”出現(xiàn)在文本字符串T中第1l位，那么我們稱模式字符串P與文本字符串T匹配成功。2.2單模式匹配2.2.1BF算法BF算法即Brute Force算法的縮寫。是蠻力算法的意思，實際上是原理和邏輯最簡單的算法這個算法在字符申規(guī)模較小的時候，還是能夠取得較好的效益。BF算法就是把模式串和文本串的所有窗口逐一進行比較。如果當前字符相同而且模式串結束則匹配成功如果字符相同而模式串未結束就比較下一個字符：如果字符不相同，則窗口向后移動一個字符位置，模式串和新窗口從開始字符重新比較。對于文本字符串TlTkTjTm-k-1Tn模式字符串PlPiPm算法描述：(1)P和T從左端對齊，使得Pl與T1對齊；(2)從左到右匹配P與T的字符，直到出現(xiàn)不匹配的情況或是P已被完全匹配：(3)如果出現(xiàn)不匹配的情況，則將P右移一個字符，重新開始匹配；(4)重復上述過程，直到P被完全匹配，或P移到T的右端。每次模式串和某個窗口比較次數(shù)應該是0(m)，而窗口的個數(shù)是0（nm)個。因此算法最壞情況的時問復雜度是O(mn)。最壞情況的例子之一是文本串是某一相同字符的字符串而模式串也是這一字符的字符串。這種算法的缺陷是匹配過程中帶有回溯，準確地說是當匹配不成功的時候，之前進行的匹配完全變?yōu)闊o效的,所有的比較需要從模式串首字符重新開始。BF算法的優(yōu)點是不需要預處理。輔助的空間是常量，即只需要幾個變量的臨時存儲區(qū)域。模式串和某個窗口內匹配的順序是任意的，向左或者向右都是可以的。2.2.2KMP算法KMP算法是Knuth等人在BF算法的基礎上提出來的。從本質上講，KMP算法就是出現(xiàn)不匹配情況下帶有智能指針初始化的BF算法。為了在不匹配時重新定位指針，KMP算法需要進行預處理算出一個Shift表來?；舅枷耄篕MP算法利用已匹配成功部分的信息，即前綴(模式字符串中存在的相同子串)，可以使模式字符串向前推進若干個字符位置，而不只是一個字符，避免了重復比較，同時也實現(xiàn)了文本字符串指針的無回溯。要點是：我們能夠通過預先對模式的分析獲得知識，即如果在模式的位置l或2匹配失敗則移動1個位置，如果在模式的位置3匹配失敗則移動2個位置，如果在模式的位置4匹配失敗則移動3個位置，以此類推。算法描述9：當模式匹配執(zhí)行到比較字符Ti和Pi，其中l(wèi)=i=n，l=j=m。(1)若Ti=Pj則繼續(xù)往右作匹配檢測，即對Ti+1和Pj+l；進行匹配檢測。(2)若TiPj時則分兩種情況進行討論：第一種情況：若j=l，則對Ti+l和Pi進行匹配檢測，即把模式和正文向右移動一位再從模式的第一個字符進行匹配。第二種情況：若lj=m，我們將試圖在模式中找到一個合適位置再進行比較，我們把這個下標記做nextj。執(zhí)行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，從上例的分析可知，為了實現(xiàn)改進算法，需要解決下述問題：當匹配過程中產(chǎn)生“失配”（即sipj）時，模式串“向右滑動”可行的距離有多遠，換句話說，當主串中字符Si與模式中字符Pj “失配”（即比較不等）時，主串中字符Si（i指針不回溯）應與模式中哪個字符再比較？假設此時主串中字符Si應與模式中字符Pk（kj）繼續(xù)比較，則模式中字符Pk前面k個字符的子串必須滿足下列關系式（f-1），且不存在kk滿足下列關系式（f-1）p0p1pk-1 = si-ksi-k+1si-1 (f-1) 圖2-2模式串與主串的對應關系一當主串中字符Si與模式中字符Pj “失配”時，已經(jīng)得到的“部分”匹配結果是：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算法具有一定的優(yōu)越性。BMH算法預處理時間復雜度為O(m+o)，空間復雜度先0(o)，o是與Pattern、Text相關的有限字符集長度。查找階段時間復雜度為O(mn)，在一般情況下，BMH算法比BM有更好的性能，它只使用了一個數(shù)組，簡化了初始化過程。2.3多模式匹配2.3.1AC算法1975年，貝爾實驗室的Alfred VAho和Margaret JCorasick提出了著名的多模式匹配算法一一AC自動機匹配算法(簡稱AC算法)。該算法最早被使用在圖書館的書目查詢程序中，取得了很好的效果。AC算法描述（例如模式集SP=he，she，his，hers）：預處理階段，模式樹的各個節(jié)點作為狀態(tài)，根節(jié)點作為初態(tài)，標簽為模式的節(jié)點作為終態(tài)，利用轉向函數(shù)g和失效函數(shù)f作為轉移函數(shù)，將模式樹擴展成一個樹型有限自動機。見圖2-4由模式樹擴展所得的AC自動機M是1個6元組：M= (Q，g，f，qo，F(xiàn))其中：(1)Q是有限狀態(tài)集(模式樹上的節(jié)點)；(2)是有窮的輸入字符表(數(shù)據(jù)包中可能出現(xiàn)的所有字符)；(3)g是轉移函數(shù)，該函數(shù)定義如下：g(S，a)：從當前狀態(tài)S開始，沿著邊上標簽為a的路徑所到的狀態(tài)。假如(U，v)邊上的標簽為a，那么g(U，a)=v；如果根節(jié)點上出來的邊上的標簽沒有a，則g(0，a)=O，即如果沒有匹配的字符出現(xiàn)，自動機停留在初態(tài)；(4)f(不匹配時自動機的狀態(tài)轉移)也是轉移函數(shù)，該函數(shù)定義如下：f(S)：當w是L(s)最長真后綴并且W是某個模式的前綴，那么f(S)就是以W為標簽的那個節(jié)點；(5)qoQ是初態(tài)(根節(jié)點，標識符為0)；(6)F量Q是終態(tài)集(以模式為標簽的節(jié)點集)。這樣，在文本字符串中查找模式字符串的過程轉化成在模式樹中的查找過程。查找一個文本字符串T時從模式樹的根節(jié)點開始，沿著以T中字符為標簽的路徑往下走：若自動機能夠抵達終態(tài)v，則說明T中存在模式L(v)：否則不存在模式。圖2-4 模式樹AC算法模式匹配的時間復雜度是O(n)，并且與模式集中模式字符串的個數(shù)和每個模式字符串的長度無關。無論模式字符串P是否出現(xiàn)在文本字符串T中，T中的每個字符都必須輸入狀態(tài)機中，所以無論是最好情況還是最壞情況，AC算法模式匹配的時間復雜度都是0(n)，包括預處理時間在內，AC算法總時間復雜度是O(M+n)，其中M為所有模式字符串的長度總和。AC算法的查找效率明顯高于BM算法。但是，AC算法在對文本字符串匹配的過程中沒有跳躍，無法跳過不必要的比較，并且有限狀態(tài)自動機算法是以空間換時間的經(jīng)典算法，當模式集較大時可能產(chǎn)生內存膨脹問題。因此在實際的匹配過程中，AC算法不可能是性能最佳的搜索算法。2.3.2AC-BM算法AC-BM算法是在AhoCorasick算法的基礎上，結合BoyerMoore算法的跳躍思想，產(chǎn)生的一種多模式匹配算法。在一般情況下，由于應用了BM算法的跳躍式思維，所以不需要對文本的每個字符進行匹配。在BM算法的基礎上引入了AC算法，來提高匹配速度，跳過盡可能多的字符，在模式字符串較長和較短的情況下，該算法都具有很好的性能。AC-BM算法描述：設模式樹中最短模式串的長度為L，第一次比較是從待匹配的文本字符串的末端向前取L個字符與模式樹的根字符對齊，然后從樹的根字符開始比較，當出現(xiàn)不匹配的字符時：(1)若目標字符不在任何模式串中，則模式樹偏移量為L位；(2)移動到另一模式串前綴的下一位置；(3)將模式樹移動到作為樹中另一個模式后綴能夠正確匹配目標串的某個前綴的下一個位置。要注意的是：AC-BM算法在移動過程中，模式樹移動的偏移量不能超過最短模式串的長度L。我們設模式字符串集合中，字符串最小長度為minlen，最大長度為maxlen，待匹配文本長度為n，則在最優(yōu)情況下，時間復雜度為O(nminlen)，在最壞情況下，時間復雜度為O(n*maxlen)。AC-BM算法結合多模式匹配AC和單模式匹配BM兩種算法的優(yōu)點，既可以同時匹配多個模式又可以跳過不必要的字符，因此相比其它模式匹配算法具有較高的性能和效率。2.4影響模式匹配算法的因素對于一個模式匹配算法來說，在實際應用中，最為關注的問題有以下幾個方面1819：(1)正確性：即誤判率和漏判率，這與模式的選擇是密切相關的，如果模式的選擇比較嚴格，那么誤判率和漏判率一定會下降，但是過于嚴格的模式會影響識別的速度；同時過于簡短的模式又會影響誤判率和漏判率，所以要選擇一個最優(yōu)的折衷點。(2)速度：即時間復雜性，這是評價一個模式匹配算法的重要的標準之一。隨著網(wǎng)絡速度的提高，通常要求模式匹配能以線速率執(zhí)行，特別是在一些實時性的系統(tǒng)中，對模式匹配的速度有很高的要求。一般情況下算法的時間復雜性，首先是預處理時間復雜性，其次是匹配過程中的時間復雜性，最后是最壞情況和最好情況下的時間復雜性，特別是最壞情況下的復雜性，是算法研究中的一個重要方面。而在上述三種情況的時間復雜性中，模式的因素都是一個不可缺少的原因。簡潔有效的模式不僅可以降低預處理的時間復雜度，而且還能縮短匹配過程的時間，至于最壞和最好的時間復雜度，在很大程度上受控于模式的規(guī)模。所以若要提高算法的速度，提高模式的有效性是一個重要途徑。(3)資源消耗：在模式的預處理階段和模式匹配階段，對內存的需求也是應用中關注的重要問題之一，盡管目前內存的容量提高了很多，但是龐大的內存占有量會減慢算法的速度，所以現(xiàn)在人們常常借助于硬件實現(xiàn)算法。第3章 FPGA的基本知識本章主要介紹FPGA的基本概念，F(xiàn)PGA與CPLD的關系，硬件描述語言的選擇。3.1FPGA簡介21FPGA（FieldProgrammable Gate Array），即現(xiàn)場可編程門陣列，它是在PAL、GAL、CPLD等可編程器件的基礎上進一步發(fā)展的產(chǎn)物。它是作為專用集成電路（ASIC）領域中的一種半定制電路而出現(xiàn)的，既解決了定制電路的不足，又克服了原有可編程器件門電路數(shù)有限的缺點。目前以硬件描述語言（Verilog 或 VHDL）所完成的電路設計，可以經(jīng)過簡單的綜合與布局，快速的燒錄至 FPGA 上進行測試，是現(xiàn)代 IC 設計驗證的技術主流。這些可編輯元件可以被用來實現(xiàn)一些基本的邏輯門電路（比如AND、OR、XOR、NOT）或者更復雜一些的組合功能比如解碼器或數(shù)學方程式。在大多數(shù)的FPGA里面，這些可編輯的元件里也包含記憶元件例如觸發(fā)器（Flipflop）或者其他更加完整的記憶塊。 系統(tǒng)設計師可以根據(jù)需要通過可編輯的連接把FPGA內部的邏輯塊連接起來，就好像一個電路試驗板被放在了一個芯片里。一個出廠后的成品FPGA的邏輯塊和連接可以按照設計者而改變，所以FPGA可以完成所需要的邏輯功能。 FPGA一般來說比ASIC（專用集成芯片） 的速度要慢，無法完成復雜的設計，而且消耗更多的電能。但是他們也有很多的優(yōu)點比如可以快速成品，可以被修改來改正程序中的錯誤和更便宜的造價。廠商也可 能會提供便宜的但是編輯能力差的FPGA。因為這些芯片有比較差的可編輯能力，所以這些設計的開發(fā)是在普通的FPGA上完成的，然后將設計轉移到一個類似 于ASIC的芯片上。另外一種方法是用CPLD（復雜可編程邏輯器件備）。3.2FPGA與CPLD的關系以及工作原理CPLD與FPGA的關系：早在1980年代中期，F(xiàn)PGA已經(jīng)在PLD設備中扎根。CPLD和FPGA包括了一些相對大數(shù)量的可編輯邏輯單元。CPLD邏輯門的密度在幾千到幾萬個邏輯單元之間，而FPGA通常是在幾萬到幾百萬。 CPLD和FPGA的主要區(qū)別是他們的系統(tǒng)結構。CPLD是一個有點限制性的結構。這個結構由 一個或者多個可編輯的結果之和的邏輯組列和一些相對少量的鎖定的寄存器。這樣的結果是缺乏編輯靈活性，但是卻有可以預計的延遲時間和邏輯單元對連接單元高 比率的優(yōu)點。而FPGA卻是有很多的連接單元，這樣雖然讓它可以更加靈活的編輯，但是結構卻復雜的多。 CPLD和FPGA另外一個區(qū)別是大多數(shù)的FPGA含有高層次的內置模塊（比如加法器和乘法器）和內置的記憶體。一個因此有關的重要區(qū)別是很多新的FPGA支持完全的或者部分的系統(tǒng)內重新配置。允許他們的設計隨著系統(tǒng)升級或者動態(tài)重新配置而改變。一些FPGA可以讓設備的一部分重新編輯而其他部分繼續(xù)正常運行。FPGA的工作原理：（1）采用FPGA設計ASIC電路(專用集成電路)，用戶不需要投片生產(chǎn)，就能得到合用的芯片。 （2）FPGA可做其它全定制或半定制ASIC電路的中試樣片。 （3）FPGA內部有豐富的觸發(fā)器和IO引腳。 （4）FPGA是ASIC電路中設計周期最短、開發(fā)費用最低、風險最小的器件之一。 （5) FPGA采用高速CHMOS工藝，功耗低，可以與CMOS、TTL電平兼容。 可以說，F(xiàn)PGA芯片是小批量系統(tǒng)提高系統(tǒng)集成度、可靠性的最佳選擇之一。 FPGA是由存放在片內RAM中的程序來設置其工作狀態(tài)的，因此，工作時需要對片內的RAM進行編程。用戶可以根據(jù)不同的配置模式，采用不同的編程方式。 加電時，F(xiàn)PGA芯片將EPROM中數(shù)據(jù)讀入片內編程RAM中，配置完成后，F(xiàn)PGA進入工作狀態(tài)。掉電后，F(xiàn)PGA恢復成白片，內部邏輯關系消失，因此，F(xiàn)PGA能夠反復使用。FPGA的編程無須專用的FPGA編程器，只須用通用的EPROM、PROM編程器即可。當需要修改FPGA功能時，只需換一片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；外設模式可以將FPGA作為微處理器的外設，由微處理器對其編程。 如何實現(xiàn)快速的時序收斂、降低功耗和 成本、優(yōu)化時鐘管理并降低FPGA與PCB并行設計的復雜性等問題，一直是采用FPGA的系統(tǒng)設計工程師需要考慮的關鍵問題。如今，隨著FPGA向更高密 度、更大容量、更低功耗和集成更多IP的方向發(fā)展，系統(tǒng)設計工程師在從這些優(yōu)異性能獲益的同時，不得不面對由于FPGA前所未有的性能和能力水平而帶來的 新的設計挑戰(zhàn)。3.3硬件語言選擇22Verilog HDL與VHDL是兩種最常見的硬件描述語言，Verilog HDL與VHDL相比有以下一些優(yōu)點：(1)可以用來進行各種層次的邏輯設計，也可以進行數(shù)字系統(tǒng)的邏輯綜合、仿真驗證和時序分析等。Verilog HDL適合算法級(Algorithm)、寄存器傳輸級(RTL)、邏輯級(Logic)、門級(Gate)和版圖級(Layout)等各個層次的設計和描述。(2)VHDL偏重于標準化考慮，而Verilog HDL與EDA工具的結合更為緊密。VHDL是國際上第一個標準化的HDL語言(IEEE-1076)，是為了實現(xiàn)美國國防部VHSIC計劃所推出的各個電子部件供應商具有統(tǒng)一的數(shù)據(jù)交換格式的要求。相比之下，Verilog HDL則是在全球最大的EDA/ESDA供應商Cadence公司的扶持下針對EDA工具開發(fā)的HDL語言。(3) 與VHDL相比，Verilog HDL的編程風格更加簡潔明了，更接近高級計算機語言的語法形式。有鑒于此，本設計采用Verilog HDL語言作為硬件描述語言。第4章 KMP算法VerilogHDL實現(xiàn)本章主要介紹KMP算法的VerilogHDL實現(xiàn)設計過程，一些調試碰到的問題及解決方法。4.1模式串輸入kmp算法是一種改進的字符串匹配算法，由D.E.Knuth與V.R.Pratt和J.H.Morris同時發(fā)現(xiàn)，因此人們稱它為克努特莫里斯普拉特操作（簡稱KMP算法）。KMP算法的關鍵是根據(jù)給定的模式串pattern定義一個next函數(shù)。next函數(shù)包含了模式串本身局部匹配的信息。為了用Verilog HDL實現(xiàn)KMP算法，我們需要在熟悉算法原理的基礎上進行程序設計。KMP算法的原理已經(jīng)在論文的第二章詳細介紹過，這里就不再累述。圖4-1模式串輸入代碼由于Verilog HDL語言不像C語言一樣可以很方便的申請內存用于存放變量或者數(shù)據(jù)，而既然我們的工作是要進行字符串的查找，那么首先我們需要有兩個字符串。如何存放這兩個字符串？有兩種方法：一種是將字符串存放在FPGA內部的存儲器中，比如使用Quartus II自帶的MegaWizard Plug-in Manger工具在FPGA內部定制一個RAM或者ROM存放字符串，或者直接定義一個數(shù)組，即使用FPGA的邏輯單元構造RAM用于存放字符串。當然后一種方式的代價會比較高，尤其是當FPGA的邏輯單元相對較少時，隨意地揮霍這種寶貴的資源就不可取。對于本設計，由于我們只是需要驗證算法，因此用作主串的字符串不需要很長（實際使用了一個長度為16的字符串），因此可以直接定義數(shù)組來存放這個字符串，這樣做可以避免另外設計電路用于控制RAM的讀取。另外一種方法是令字符串從外部通過引腳輸入到FPGA中，然后再存放在FPGA的內部RAM中，采用這樣的設計方式，字符串的內容可以很方便地改動，本設計中的模式串就采用這種方式從外部輸入。首先我們需要設計一個模式串的輸入接口，模式串輸入的Verilog HDL代碼如圖4-1所示：我們的Verilog HDL開發(fā)環(huán)境為Quartus II 8.0 Wed Edition，Quartus II是一個功能強大的集成開發(fā)環(huán)境，支持從源代碼編輯到仿真、布局布線和芯片燒錄的全部功能。上述代碼中，k是一個計數(shù)值，寬度為4位，表示當前輸入的字符的個數(shù)，在復位時初始化為0。在每個時鐘的上升沿，k遞增1。p是一個位寬為8的端口，外部數(shù)據(jù)就從這個端口輸入。在每個時鐘的上升沿，p端口的值賦給patternk寄存器。因為模式串的長度是8，因此當計數(shù)值k7時就不再需要存儲端口p的數(shù)據(jù)，但是為了顯示模式串輸入已經(jīng)完成，必須給出一個提示信息，這個提示信息不需要輸出到FPGA的外部，只需要提醒內部的相關檢測機制就可以，wr_ed就是這個提示信息，并且將它定義為一個reg型的變量，位寬為1位。當k7時就令wr_ed為1，表示模式串已經(jīng)全部輸入。該部分的功能仿真結果見圖4-2：圖 4-2 模式串輸入仿真結果其中pattern0pattern7是wire型的輸出口連接到pattern0pattern7，這只是一組用于觀測FPAG內部寄存器值的端口變量，而這一組端口變量對一設計本身并不是必需的，因此當模式串輸入接口的設計完成以后，可以撤銷這一組端口。從仿真結果中可以看出，當wr_ed變?yōu)?時，說明模式串應當已經(jīng)輸入到FPGA內部的數(shù)組中了，我們查看此時的pattern0pattern7可以發(fā)現(xiàn)，模式串確實已經(jīng)輸入到內部的數(shù)組中了，這與我們的設想吻合。4.2next函數(shù)的計算為了便于Verilog HDL程序設計，我們首先用C語言描述KMP算法。之所以先用C語言描述KMP算法，是因為Verilog HDL最為一種高級的硬件描述語言，與C語言的風格有許多類似之處，其中有許多語句，如if語句、case語句和C語言中的對應語句十分相似。如下所示是next函數(shù)的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函數(shù)已經(jīng)計算完畢，可以進行后續(xù)的字符匹配工作了。nextdone的功能與模式串輸入函數(shù)中的wr_ed具有類似的功能。上述代碼的結構與用C語言編寫的代碼十分相似，這就說明我們在理解了算法原理的基礎上，可以很方便的將C語言編寫的代碼改寫成Verilog HDL語言。但是這兩種語言還是有很大的區(qū)別的，與C語言不同，在Verilog HDL中是沒有定義諸如char、int、float這樣的數(shù)據(jù)類型，所有的數(shù)據(jù)類型都是二進制數(shù)據(jù)，數(shù)據(jù)的每一位只有0和1兩種取值，我們無法定義一個數(shù)為char型或者float型。因此在表示負數(shù)的時候我們就會不能簡單地賦值，而因當采用補碼的形式表示，比如-1我們就可以表示成4b1111，在數(shù)字系統(tǒng)綜合的過程中這個數(shù)值就會被認為是-1。這一點是Verilog HDL語言與高級計算機語言存在巨大差別的地方。接下來我們需要驗證我們設計的代碼功能是否正確，這是很容易驗證的。我們首先在C語言代碼中對一個模式串“abaabcac”計算next值，得到如圖4-5的運算結果：圖4-5 Visual C+下next計算結果由上圖可見對于“abaabcac”這個字符串，next函數(shù)的計算結果是-1，0，0，1，1，2，0，1。另外我們還發(fā)現(xiàn)程序的運行結果提示在主串中找到的模式串的其實位置為-1，為什么呢？其實這是因為在這一次運行中我們設置的主串中沒有包含一個有效的模式串，因此運行結果是找不到匹配的字符串，在這種情況下我們在控制臺輸出一個-1表示沒有找到匹配的字符串。接下來我們來測試我們用Verilog HDL編寫的代碼功能是否正確。Quartus II中新建一個仿真波形文件，然后設置仿真模式為功能仿真（由于我們只是要驗證電路的工作機制是否正確，因此只要選擇功能仿真即可），然后將端口變量添加到仿真窗口中，設置時鐘和其他輸入變量，點擊“Generate Functional Simulation Netlist”，生成功能仿真的仿真網(wǎng)表文件，然后運行仿真，仿真結果如圖4-6所示：圖4-6 next函數(shù)在Quartus II下的仿真結果由上圖可見，當nextdone為1時，說明next函數(shù)已經(jīng)計算完成，這個時候我們可以查看next數(shù)組的值，由于next0next7是一組線網(wǎng)型的端口變量，直接反映next數(shù)值的值，因此我們觀查next0next7的值，發(fā)現(xiàn)其數(shù)值為-1、0、0、1、1、2、0、1。這個運算結果與C語言的運算結果是一致的，這說明我們設計的next函數(shù)狀態(tài)機是完全正確的！4.3字符串匹配在設計完next函數(shù)的Verilog HDL實現(xiàn)之后，我們的設計的最核心部分已經(jīng)完成了，接下來要做的工作就是根據(jù)next數(shù)組進行字符串的匹配操作。既然是字符串匹配，那么我們必然需要一個主串供我們查找，前面已經(jīng)提到過FPGA中數(shù)據(jù)的存儲方式，為了方便調用存儲的數(shù)據(jù)，我們將主串存放在內部數(shù)組中，占用FPGA的片上邏輯單元，在系統(tǒng)復位時對數(shù)組中的值進行初始化。同樣的，我們先來看字符串匹配的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