臺灣博碩士論文加值系統

指導教授推薦書
論文口試委員會審定書
致 謝 iii
中文摘要 iv
Abstract v
目 錄 vi
圖 目 錄 viii
表 目 錄 x
第一章 介紹 - 1 -
第二章 初步與文獻回顧 - 5 -
2.1 亂數產生器 - 5 -
2.1.1 線性同餘產生器 - 5 -
2.1.2 多重遞迴產生器 - 9 -
2.1.3 DX-k-s產生器 - 11 -
2.2 同位元 - 17 -
2.2.1 同位元運算 - 17 -
2.2.2 有趣的觀察 - 19 -
第三章 提出的前瞻進位同位元預測 - 29 -
3.1 設計方法 - 32 -
3.2 揉合DX-k-s產生器 - 43 -
第四章 比較和討論 - 46 -
4.1 分析結果與討論 - 46 -
4.1.1 延遲時間 - 46 -
4.1.2 邏輯閘數量 - 53 -
4.2 模擬結果與討論 - 59 -
4.2.1 延遲時間 - 60 -
4.2.2 邏輯閘數量 - 62 -
4.3 DX產生器比較 - 66 -
第五章 結論 - 70 -
參考文獻 - 72 -


圖 目 錄

圖2. 1. 線性同餘產生器結構圖 - 6 -
圖2. 2. 多重遞迴產生器結構 - 9 -
圖2. 3. 傳統8位元的同位元運算 - 18 -
圖2. 4. 同位元運算的觀察，當Cin = 0 (a) Even + Even (b) Odd + Odd - 19 -
圖2. 5. 同位元運算的觀察，當Cin = 1 (a) Even + Even (b) Odd + Odd - 20 -
圖2. 6. 同位元運算的觀察，奇偶相加 (a) Cin = 0 (b) Cin = 1 - 21 -
圖3. 1. 前瞻進位同位元預測 - 26 -
圖3. 2. 傳統上同位元的最長路徑 - 29 -
圖3. 3. 前瞻進位同位元最長路徑示意圖 - 29 -
圖3. 4. 以2個位元提出的前瞻進位同位元中與Cin無關的邏輯電路 - 30 -
圖3. 5. 2個位元數的前瞻進位同位元預測邏輯電路圖 - 30 -
圖3. 6. 以4個位元提出的前瞻進位同位元中與Cin無關的邏輯電路 - 33 -
圖3. 7. 4個位元數的H0與H1的邏輯電路圖 - 34 -
圖3. 8. 4個位元數的前瞻進位同位元邏輯電路圖 - 34 -
圖3. 9. 8個位元數的前瞻進位同位元邏輯電路圖 - 36 -
圖3. 10. (a) 所參考的DX-k-s產生器的架構 (b) 31位元數的環狀前瞻進位加法器 - 37 -
圖3. 11. 應用前瞻進位同位元預測之31-b環狀前瞻進位加法器 - 38 -
圖4. 1. CLA運算結構圖 - 40 -
圖4. 2. 搭載傳統同位元運算方式的CLA最長延遲時間示意圖 - 41 -
圖4. 3. 前瞻進位同位元最長路徑示意圖 - 43 -
圖4. 4. 傳統同位元與前瞻進位同位元延遲時間比較圖 - 45 -
圖4. 5. 前瞻進位同位元預測所需邏輯閘電路圖 - 49 -
圖4. 6 傳統同位元以及前瞻進位同位元預測之正反器延遲時間曲線圖 - 53 -
圖4. 7. 傳統同位元以及前瞻進位同位元預測之正反器ALUTs曲線圖 - 56 -
圖4. 8. 電路效益評分曲線圖 - 60 -
表 目 錄

Table 1. 1. 關係式(1) = 7的範例 - 7 -
Table 2. 1. 進位等於零(Cin=0)的同位元K-Map - 23 -
Table 2. 2. 進位等於零(Cin=1)的同位元K-Map - 24 -
Table 3. 1. 、 、 邏輯運算真值表 - 27 -
Table 3. 2. 或閘(OR Gate)的真值表 - 28 -
Table 4. 1. 傳統運算方法同位元所需邏輯閘數之延遲時間 - 42 -
Table 4. 2. 前瞻進位同位元預測所需邏輯閘數之延遲時間 - 44 -
Table 4. 3. 各個邏輯閘延遲時間比 - 44 -
Table 4. 4. 傳統同位元運算以及前瞻進位同位元預測所需延遲時間 - 45 -
Table 4. 5. CLA所需邏輯閘數量 - 47 -
Table 4. 6.傳統同位元運算所需邏輯閘數量 - 48 -
Table 4. 7. 前瞻進位同位元預測所需邏輯閘數量 - 49 -
Table 4. 8. 應用前瞻進位同位元預測的CLA所需邏輯閘數量 - 50 -
Table 4. 9. 各個邏輯閘面積比例 - 50 -
Table 4. 10. 傳統同位元與前瞻進位同位元所需面積比 - 51 -
Table 4. 11. CLA與應用傳統同位元運算的CLA以及搭載前瞻進位同位元預測的CLA之延遲時間比較表 - 52 -
Table 4. 12. 傳統同位元以及前瞻進位同位元預測之正反器延遲時間模擬結果 - 53 -
Table 4. 13. CLA與傳統同位元運算的CLA以及前瞻進位同位元預測的CLA之邏輯閘數量表 - 54 -
Table 4. 14. 傳統同位元以及前瞻進位同位元預測之正反器ALUTs模擬結果 - 55 -
Table 4. 15 DX產生器與搭載前瞻進位同位元預測之DX產生器延遲模擬結果 - 58 -
Table 4. 16 DX產生器與搭載前瞻進位同位元預測之DX產生器ALUTs模擬結果 - 59 -

參考文獻

[1] M. P. Kennedy, R. Rovatti, and G. Setti, Chaotic Electronics in Telecommunications. Boca Raton, FL: CRC Press, Inc., 2000.
[2] J. E. Gentle, Random Number Generation and Monte Carlo Methods, 2nd ed. Springer-Verlag, New York, 2003.
[3] D. H. Lehmer, “Mathematical methods in large-scale computing units,” in Proc. of the Second Symp. on Large Scale Digital Computing Machinery. Cambridge, MA.: Harvard University Press, 1951, pp. 141– 146.
[4] P. C. Wu, “Multiplicative, congruential random-number generators with multiplier ±2k1 ±2k2 and modulus 2p - 1,” ACM Trans. on Mathematical Software, vol. 23, pp. 255–265, 1997.
[5] P. L’ Ecuyer and R. Simard, “Beware of linear congruential generators with multipliers of the form a = ±2q ±2r,” ACM Trans on Mathematical Software, vol. 25, pp. 367-374, 1999.
[6] J. Hastad and A. Shamir, “The cryptographic security of truncated linearly related variables,” in Proc, of the 17th ACM Symposium on Theory of Computing. ACM, pp. 356-362.
[7] J. Boyar, “Inferring sequences produced by pseudo-random number generators,” J. the Association for Computing Machinery, vol. 36, pp. 129-141, 1989.
[8] L. Y. Deng, “Efficient and portable multiple recursive generators of large order,” ACM Trans. on Modeling and Computer Simulation, vol. 15, no. 1, pp. 1-13, Jan. 2005.
[9] W. Hong, R. Modugu, and M. Choi, “Efficient Online Self-Checking Modulo 2n + 1 Multiplier Design,” IEEE Trans on Computer, vol. 60, no. 9, Sep. 2011.
[10] M. Agrawal, N. Kayal, and N. Saxena, “Primes is in P,”Annals of Mathematics, 160:781-793, 2004.
[11] Deng, L. Y. and Xu, H., “A system of high-dimensional, efficient, long-cycle and portable uniform random number generators,” ACM Trans. on Modeling and Computer Simulation, 2003, Vol. 13, Issue 4, p. 299-309.
[12] Deng, L.Y. and Lin, D. K. J. 2000. Random number generation for the new century. American Statistician. vol. 54, pp. 145-150, 2000.
[13] C. Y. Li, Y. H. Chen, T. Y. Chang, L. Y. Deng, and K. To, “Period Extension and Randomness Enhancement Using High-Throughput Reseeding-Mixing PRNG,” IEEE Trans. on VLSI systems, vol. 20, no. 2, Feb. 2012.
[14] C. M. Huang, L. C. Wang, C. Y. Li, and L. Y. Deng, “A Class of Hardware-Efficient PRNGs with Maximum Periods,”IEEE GHTCE 2014
[15] J. Khakbaz and F. J. McCluskry, “Self-Testing Embedded Checkers,” CFC Technical Report 83-19, Center for Reliable Computing, Stanford Univ., Stanford, Calif., Dec. 1983.
[16] D. Nikolos, “Optimal Self-Testing Embedded Parity Checkers,” IEEE TCOMP, vol. 47, no. 3, pp. 313-321, 1998.
[17] C. Y. Li, “High Speed Parity Prediction for Binary Additions Using the Recursive Carry-masking Method,” National Tsing Hua University, 1998.