在本篇論文中，以FPGA晶片設計的觀點來探討有限場GF(2m)乘法器之電路實現。其中，現有乘法器在電路設計上是以邏輯閘實現邏輯運算，但FPGA晶片則是以Look-Up Table(LUT)的技術來實現邏輯運算，所以本論文以Altera公司的開發軟體 Quartus II設計乘法器的硬體電路。更進一步地，本論文針對有限場GF(2m)乘法器的Cellular、Semi-Systolic、Full-Systolic三種電路架構，進行電路效能之評估與分析，包括電路複雜度、運算速度以及運算時間延遲等。

In this paper, we will explore the multipliers over GF(2m) on the FPGA chip. Design in the existing circuit, the logic operation implement by logic gate. But on FPGA chip, the logic operation implement by look-up table (LUT). Beside, we have synthesized the cellular, semi-systolic and full-systolic multipliers over GF(24) for Altera Quartus II. In the further, we have evaluated the complexities, throughput rate and latency delay of the cellular, semi-systolic and full-systolic multipliers on the FPGA chip.

中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 viii

第一章 緒論 1
1-1 研究背景與動機 1
1-2 論文大綱 3
第二章 有限場GF(2m)乘法演算法與架構 4
2-1 LSB乘法演算法 4
2-2 LSB乘法架構 5
2-3 MSB乘法演算法 9
2-4 MSB乘法架構 10
2-5 效能比較 14
第三章 FPGA 16
3-1 FPGA晶片簡介 16
3-2 FPGA晶片之結構 18
3-3 FPGA晶片設計流程 22
第四章 有限場GF(2m)乘法器使用FPGA晶片之設計評估 24
4-1 乘法器basic cell之考量 24
4-2 乘法器運算速度之考量 33

第五章 結論 45

參考文獻 46
作者簡歷 48

圖目錄

圖2-1 LSB有限場GF(24) Cellular乘法器 6
圖2-2 LSB有限場GF(24) Semi-Systolic乘法器 7
圖2-3 LSB有限場GF(24) Full-Systolic乘法器 8
圖2-4 MSB有限場GF(24) Cellular乘法器 11
圖2-5 MSB有限場GF(24) Semi-Systolic乘法器 12
圖2-6 MSB有限場GF(24) Full-Systolic乘法器 13
圖3-1 FPGA晶片 17
圖3-2 FPGA晶片結構 17
圖3-3 FPGA晶片內部LE結構 18
圖3-4 LUT Equation 18
圖3-5 LE運算時間 19
圖3-6 ALM功能 20
圖3-7 FPGA晶片內部ALM結構 20
圖3-8 ALM內部ALUTs Equation 21
圖3-9 ALM運算時間 21
圖3-10 FPGA晶片開發流程 22
圖3-11 fmax定義 23
圖3-12 模擬兩串聯暫存器之時序分析結果 23
圖4-1 LSB有限場GF(2m)乘法器之basic cell在FPGA晶片(LE)合成結果 28
圖4-2 LSB有限場GF(2m)乘法器之basic cell在FPGA晶片(ALM)合成結果 29
圖4-3 MSB有限場GF(2m)乘法器之basic cell在FPGA晶片(LE)合成結果 30
圖4-4 MSB有限場GF(2m)乘法器之basic cell在FPGA晶片(ALM)合成結果 31
圖4-5 軟體自行佈局 35

圖4-6 有限場GF(24)乘法器佈局繞線為固定ALM 39
圖4-7 固定ALUT 41
 

表目錄

表2-1 有限場GF(2m)乘法器之效能比較 15
表4-1 LSB有限場GF(2m)乘法器在FPGA晶片之硬體複雜度比較 32
表4-2 MSB有限場GF(2m)乘法器在FPGA晶片之硬體複雜度比較 32
表4-3 MSB有限場GF(2m)乘法器在FPGA晶片之運算時脈週期 34
表4-4 MSB有限場GF(24)乘法器運算時脈週期在FPGA晶片設計之結果(軟體自行佈局繞線) 36
表4-5 MSB有限場GF(24)乘法器運算時脈週期在FPGA晶片設計之結果(自行固定ALM佈局繞線) 40
表4-6 MSB有限場GF(24)乘法器運算時脈週期在FPGA晶片設計之結果(自行固定ALM與固定ALUT佈局繞線) 42
表4-7 MSB有限場GF(24)乘法器在FPGA晶片設計之效能比較 44

[1] I. S. Hsu, T. K. Truong, L. J. Deutsch, and I. S. Reed, “A comparison of VLSI architecture of finite field multipliers using dual, normal, or standard bases,” IEEE Transaction on Computers, vol. 37, no. 6, pp. 735-739, 1988.
[2] H. T. Kung, “Why Systolic Architectures ? ,” Computer, vol. 15, no. 1, pp.37-46, 1982.
[3] B. A. Law, Jr, and C. K. Rushforth, “A Cellular–Array Multiplier for GF(2m),” IEEE Transactions on Computers, vol. C-20, no 12, pp. 1573-1578, 1971.
[4] C. S. Yeh, S. Reed, and T. K. Truong, “Systolic Multipliers for Finite Fields GF(2m),” IEEE Transactions on Computers, vol. 33, no 4, pp. 357-360, 1984.
[5] C. L. Wang, and J. L. Lin, “Systolic array implementation of Multipliers for finite fields GF(2m),” IEEE Transactions on Circuits and Systems, vol. 38, no. 7, pp. 796-800, 1991.
[6] S. K. Jain, S. Leilei, and K. K. Parthi, “Efficient semisystolic architectures for finite-field arithmetic,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 6, no. 1, pp. 101-113, 1998.
[7] C. Y. Lee, E. H. Lu, and J. Y, “High-speed bit-parallel systolic multipliers for a class of GF(2m),” in Proc. 2001 International Symposium on VLSI Technology, System, and Applications, 2001. Hsinchu, Taiwan, pp. 291-294, April 18, 2001.
[8] C. Y. Lee, E. H. Lu, and J. Y, “Bit-parallel systolic multipliers for GF(2m) fields defined by all-one and equally spaced polynomials,” IEEE Transaction on Computers, vol.50, no.5, pp 385-393, 2001.
[9] C. Y. Lee, E. H. Lu, and J. Y, “New bit-parallel systolic multipliers for a class of GF(2m),” in Proc. The 2001 IEEE International Symposium on Circuits and Systems, 2001. ISCAS 2001. Darling Harbour, Sydney Australia, vol. 4, pp. 578-581, May 6, 2001.
[10] C. Y. Lee, “Low complexity bit parallel systolic multiplier over GF(2m) using irreducible trinomials,” IEE Proceedings Computers and Digital Techniques, vol. 150, no. 1, pp39-42, 2003.
[11] P. K. Meher, “Systolic and Super-Systolic Multipliers for Finite Field GF(2m) Based on irreducible trinomials,” IEEE Transaction on Circuits and Systems I:Regular Papers, vol. 55, no 4, pp. 1031-1040, 2008.
[12] X. Jiafeng, P. K. Meher, and H.Jianjun, “Low-latency area-delay-efficient systolic multiplier over GF(2m) for a wider class of trinomials using parallel register sharing,” in Proc. 2012 IEEE International Symposium on Circuits and System (ISCAS). Seoul, Korea, pp. 89-92, May 30, 2012.
[13] X. Jiafeng, P. K. Meher, and H.Jianjun, “Low-Complexity for GF(2m) Based on All-One Polynomials,” IEEE Transactions on Very Large Scale Integration (VLSI) System, vol. 21, no. 1, 2013.
[14] T. P. Rajalakshmi, and C. B. Rajesh, “Low-complexity systolic design for finite field multiplier,” in Proc. 2014 International Conference on Green Computing Communication and Electrical Engineering (ICGCCEE). Coimbatore, Tamil Nadu India, pp. 1-4, March 6, 2014.