FPGA雙三次插值縮放演算法

『壹』 用FPGA實現圖像處理演算法有前途嗎

有，很多時候使用者不希望圖像處理佔用大量的CPU時間，如果用FPGA實現圖像處理，那麼就可以將圖像處理部分在前端的數字晶元上實現，也就是可以在攝像機上完成很多工作

『貳』 在FPGA上快速實現MD5演算法的新方法論文

在FPGA上快速實現MD5演算法的新方法論文

摘 要 文章介紹了一種在FPGA上快速實現MD5演算法的新方法，給出了優化設計的原理、實現的具體方法及其重要模塊的設計實現方案。

關鍵詞 MD5；FPGA；Verilog語言；集成電路；關鍵路徑

1 引言

隨著電子商務和網路通信的發展，網路信息安全的重要性越來越顯著，信息加密、數字簽名、數據的完整性認證、身份驗證等成為信息安全領域的重要內容。MD5演算法本身是為數字簽名應用而設計的，隨後也應用在信息驗證技術當中。作為應用最廣泛的安全散列演算法，MD5演算法的高效實現就成為研究的需要，MD5演算法本身可以採用軟體實現，但其性能受到處理器件性能的制約不能滿足網路通信帶寬日益增長的要求，因而通過硬體實現高速MD5 運算就成為需要。

2 MD5演算法介紹

MD5 演算法可以對任何長度不超過 264二進制位的消息產生128 位的單向散列消息摘要輸出， RFC1321 標准中的MD5 演算法主要步驟如下：

在一些初始化處理後，MD5以512位分組來處理輸入文本，每一分組又劃分為16個32位子分組。演算法的輸出由四個32位分組組成，將它們級聯形成一個128位散列值。

（1）附加填充比特：填充消息使其長度恰好為一個比512位的倍數僅小64位的數。即對報文進行填充使報文的長度(比特數)與448模512同餘。填充方法是附一個1在消息後面接所要求的多個比特0。

（2）附加長度值：在其後附上64位的消息長度（填充前）。如果消息長度大於 264，僅使用該長度的低64比特。這樣，該域包含的長度值為初始長度模264 的值。

這兩步的作用是使消息長度恰好是512位的整數倍（演算法的其餘部分要求如此），同時確保不同的消息在填充後不相同。

（3）初始化寄存器：四個32位初始化變數為：

它們也被稱為鏈接變數（chaining variable）

（4）進行演算法的主循環：這一步是演算法的核心，它是一個包含四個大循環的64步函數，四個大循環結構相同，但每次使用的邏輯函數不同，每一個大循環由對512比特的16步操作組成，即每16步為一輪大循環。

每次操作如下(設 Ai+1、Bi+1 、Ci+1 、Di+1 為第 +1個時鍾周期時打入寄存器的值)：

以一下是每輪中用到的四個非線性函數（每輪一個）。

常數ti可以如下選擇：在第i步中，ti是4294967296*abs(sin(i))的整數部分，i的單位是弧度。Wi是512位消息分組中的一個，Si是每次循環移位的次數。對每次而言也是固定的常數。

（5）結果輸出：所有64步完成之後，將第64步的輸出加到四個初始化變數上作為新的初始化變數，進行下一個512比特分組的運算，直到所有分組處理完畢，單次操作圖如下：

圖1. MD5演算法單步操作圖

3 演算法優化

由上圖可以看到，硬體實現時，MD5演算法每一步操作中的關鍵路徑在於B的求取（其他三個變數都是直接傳遞），這個關鍵路徑包括了四個模 232加法運算、三輸入變數的邏輯運算、"兩個查找表運算及一個循環左移運算，而在FPGA設計中，加法運算最為耗時，四個加法運算至少需要三個加法器級聯完成，加法運算嚴重製約了整個操作的速度，可見要加快演算法運行速度就必須在簡化這一關鍵路徑上下工夫，經過觀察我們發現，在

中 對每個周期都是已知的常數，是輸入的512比特的一個32位分組，這樣，在512比特輸入初始化完成後，也可看作固定常數，

Ai是第i時鍾周期里寄存器D 的值，而 Di的值又是第i-1周期里的Ci-1 ，即Ai 的`值是第i-1周期里Ci-1的值。

若在第i周期設中間寄存器變數 ，並令

那麼在第i+1周期，

就可以表示為

操作就可以用下面幾個式子代替：

其中， Ai+1沒有參與任何運算，因此上式可以接著化簡為

這樣一來，原來一個周期內需要完成三級加法和相應的組合邏輯，現在只需要完成兩級加法和部分組合邏輯就行了，大大提高了演算法速度，只要在運算開始時加－個周期的初始化即可，簡化後的系統框圖如下：

圖2. 改進後的單步操作圖

4 結果比較

由上文中的演算法分析部分不難看出，傳統的實現方式關鍵路徑是3級32比特加法器延遲和組合邏輯的延遲，而改進的實現方式減少了一級加法器的延遲，並把組合邏輯的延遲分散到不同路徑上，因此，採用改進的實現方式大約可以將速度提高到原來的1.5倍左右。同時，為了實現數據的初始化，需要提前一個周期計算出寄存器A的值，因此整個演算法的實現需要65個周期。我們採用 VerilogHDL 描述，選擇Altera Stratix II EP2S15F672C5 FBGA晶元，在QuartusII6.0上驗證通過。由於在FPGA中，連線延時也很關鍵，而這部分延時不能像加法延時那樣通過預先計算並存儲在寄存器中來消除一部分，所以實際的MD5改進演算法與傳統型相比較，速度的提高約為1.3，資源方面由於只是增加了一個時鍾節拍，寄存器數量和組合邏輯並沒有增加，所以改進型在資源方面和傳統型相當。下表為演算法改進前後在資源、頻率、流量上的比較。

表1. 改進前後資源比較

5 結束語

由表1可見，改進型MD5演算法實現，使用的資源並沒有明顯增加，但速度的改善十分明顯，基本實現了用較少的資源得到較高速率的目標，證明了結構的正確性和合理性。實驗結果也說明，這種利用寄存器來減少加法器級聯從而減少關鍵路徑的實現方法也可用於一般的FPGA硬體設計中。

參考文獻

[1] R.Rivest. The MD5 Message-Digest Algorithm，RFC1321 1992。

[2] Jarvinen K， Tommiska M，Skytta J.Hardware implementation analysis of the MD5 hash algorithm.System Sciences，2005.HICSS』05.Proceedings of the 38th Annual Hawaii International conference on 03-06 Jan.2005:298

[3] Bruce Schneier. 應用密碼學.北京：機械工業出版社，2000：188～194

[4] William Stallings. 密碼編碼學與網路安全：原理與實踐.北京：電子工業出版社，2001: 216～222。

[5] 夏宇聞.Verilog 數字系統設計教程.航空航天大學出版社，2005

『叄』 FPGA xilinx FFT ipcore scale_sch 鎬庝箞紜瀹

1, scale_sch_we 楂樼數騫蟲湁鏁

1錛宻cale_sch 鎴鍙栫殑鍊煎簲璇ユ庝箞紜瀹氾紵
The butterfly calculation involves complex multiplication,addition, and subtraction. These operations can potentially cause the butterfly data width to grow by two bits from input to output. For radix-2, data can grow by a maximum factor of 2.4 from butterfly input to output (two bits of growth).

One way to avoid the overflow is to scale the butterfly outputs down after each stage.
錛堝洜涓哄伐浣滅幆澧冪殑鍏崇郴錛屾垜宸茬粡涔犳儻鐢ㄨ嫳鏂囨潵鎻忚堪鎶鏈闂棰橈紝鐢ㄤ腑鏂囨湁鐨勫悕璇嶄笉鐭ラ亾鎬庝箞琛ㄨ揪錛

姣斿 1024涓鐐 杈撳叆杈撳嚭鐨剎n_re xn_im 閮芥槸10浣 杈撳嚭xk_re xk_im涔熸槸10浣
鍩轟簩綆楁硶 Radix-2鐨剆cale_sch 鏈20浣
there are ten stages, 2 bits per stage, so there are 20bit

鍩哄洓Radix-4 scale_sch鏄10浣 錛涢兘鏄涓や綅涓や綅涓璧風殑
渚 Redix_4 10浣嶅亣濡傚啓鎴10 10 10 10 11 鎸囧兼墜鍐屼笂鍐欑殑鎰忔濇槸 絎琋0綰 shift by 3 bits ,N1 shift by bits N2 shift by 2 bits.....

榪欎釜縐誨姩2浣 縐誨姩3浣嶆槸涓轟粈涔堝憿錛熸湁浠涔堢敤錛
For radix-4, each stage can grow 3-bit (4.8 maximum). Therefore, shift right by 3-bit at 1st stage. And shift 2-bits for the rest, as the first stage is over-shifted.