臺灣博碩士論文加值系統

查表法技術通常被用來檢索或加速函數的計算。本論文中提出一種最小化表格之隨機亂數產生器，使用類似於傳統的廟塔式演算法的觀念，計算其機率密度函數圖形的分佈參數儲存於表格之中，使得参數讀取計算後所產生的數值，能夠符合原函數圖形的分佈。
相較於傳統表格，我們所提出的機率密度函數表格最小化演算法，具有較小的資料儲存量，因此節省了面積的開銷，且利用本團隊的一種改良式大小比較器能夠更有效率的檢索並讀取參數。藉由以上兩點，可以降低由於大量資料所造成的較大的功耗和較長的工作時間。

Look-up table is used to search data or enhance the speed of function evaluation. In this thesis the random number generator with a minimum table adopts the concept which is similar to traditional Ziggurat algorithm. Calculating the probability density functions(PDF) and storing the parameters in the tables makes the random numbers produced by computing the parameters stored in the tables fitting the distribution of PDF.
Comparing the traditional tables, the proposed PDF table minimization algorithm has the advantage of fewer stored data and lower area overhead. Moreover a content addressable memory with range compare function is improved to make data search and reading coefficients more efficiently. With the above-mentioned advantages, the power consumption and the execution time due to large amounts of data can be reduced.

目錄
中文摘要 i
Abstract ii
致謝 iii
目錄 iv
圖目錄 vii
表目錄 x
第一章 介紹 1
1-1查表法應用與考量 1
1-1-1解析度與吻合度的考量 1
1-1-2面積的考量 3
1-1-3功耗的考量 3
1-1-4速度的考量 3
1-2亂數查表的應用 3
1-3論文架構編排 6
第二章 背景 8
2-1 BOX-Muller演算法 8
2-2反累積分佈函數查表法 9
2-3中央極限定理 10
2-4廟塔式演算法 11
第三章 文獻回顧與探討 14
3-1明確值查表電路之參考文獻 14
3-2亂數查表電路之參考文獻 19
3-3大小比較器之參考文獻 22
第四章 架構設計 32
4-1非等距查表電路應用於亂數產生器 32
4-1-1高效率之隨機亂數產生器 32
4-1-2表格最小化和移除乘法器 35
4-2隨機亂數產生器之電路結構 37
4-2-1線性回授移位暫存器 38
4-2-2找查表 38
4-2-3運算電路 40
4-2-4移位器 41
4-2-4加法器 41
4-3參考文獻數位大小比較器及其延伸 42
4-4改良之數位大小比較器應用於查表電路 44
第五章 實驗結果 46
5-1 亂數產生器模擬 46
5-1-1 線性回授移位暫存器 46
5-1-2 找查表 47
5-1-3 運算電路 47
5-1-4 移位器 48
5-1-5 加法器 48
5-1-6 隨機亂數產生器 49
5-1-7 Matlab統計 49
5-2 參考文獻之大小比較器之模擬 50
5-3 數位大小比較器應用於查表電路之模擬 52
5-4 表格最小化亂數產生器 55
5-4-1 分割線段實驗 55
5-4-2 表格最小化亂數模擬 57
第六章 結論 58
參考文獻 60
作者簡歷 62

圖目錄
圖1-1 y=sinx,x屬於[0,2 ] 2
圖1-2 y=sinx,x屬於[0,2 ],Reduce the bin width 2
圖1-3 抖動波形(Jitter Waveforms 4
圖1-4 電壓雜訊波形(Voltage noise Waveforms) 4
圖1-5 文獻[2]中可程式化抖動/雜訊產生器 5
圖1-6 文獻[2]中標竿轉換器(a)可規畫延遲線 (b)數位類比轉換器 6
圖1-7 參考文獻兩個主要的方向 7
圖2-1 常態分佈累積分佈函數 9
圖2-2 (a)弦波與(b)常態分佈的典型查表示意圖 9
圖2-3 中央極限定理(a)n=1(b)n=2(c)n=4(b)n=8 10
圖2-4 7層矩形組成的廟塔式分佈曲線 12
圖3-1 文獻[9]記算分段位址之電路 15
圖3-2 文獻[9]之函式計算結構 16
圖3-3 文獻[9] 梯度之位元數與函式近似誤差之關係 16
圖3-4 文獻[11]中四種分割法圖示 18
圖3-5 文獻[10]中圖形分割 19
圖3-6 文獻[12]使用 =0.5對高斯分佈做簡易的近似 20
圖3-7 文獻[12]誤差最佳化之迭代演算法 20
圖3-8 文獻[12]產生亂數之演算法 21
圖3-9 文獻[12]演算法之硬體結構 21
圖3-10 一位元比較器電路圖 22
圖3-11 文獻[14]傳統四位元比較器電路圖 23
圖3-12 文獻[14]之二位元比較器 24
圖3-13 文獻[13]之二位元比較器 24
圖3-14 文獻[14][13]之可擴充式4位元比較器 24
圖3-15 文獻[15]中八位元比較器 26
圖3-16 美國專利[16]中的二進位大小比較器 28
圖3-17 美國專利[1]中的大小比較器 29
圖4-1 均勻分佈和由其組成的分佈 32
圖4-2 機率密度函數分佈縱向切割 33
圖4-3 第i個機率密度函數線段的水平和垂直梯形 33
圖4-4 垂直梯形分割法的管線電路 35
圖4-5 表格最小化演算法 36
圖4-6 移位器來代替乘法器之管線電路 37
圖4-7 任意機率密度函數 39
圖4-8 n-bit 參考文獻[1]中的大小比較器 44
圖4-9 常數位元(a)為0與(b)為1之不小於之位元基本單元電路 45
圖4-10 常數位元為1之不小於之位元基本單元電路 45
圖5-1 LFSR波型輸出結果 46
圖5-2 LUT波型輸出結果 47
圖5-3 運算電路波型輸出結果 48
圖5-4 移位器波型輸出結果 48
圖5-5 加法器波型輸出結果 49
圖5-6 隨機亂數產生器波型輸出結果 49
圖5-7 原機率密度函數分佈 50
圖5-8 隨機亂數統計結果 50
圖5-9 10位元之參考文獻[1]中大小比較器schematic diagram 51
圖5-10 輸入訊號 51
圖5-11 B輸入訊號 52
圖5-12 結果訊號輸出 52
圖5-13 10位元改良式大小比較器陣列之schematic diagram 53
圖5-14 B輸入訊號 54
圖5-15 結果訊號輸出 54
圖5-16 10位元改良式大小比較器陣列之佈局圖 55
圖5-17 分割線段(a)標竿分佈(b)等面積分割(c)等距離分割(d)表格最小化 55
圖5-18 表格最小化亂數模擬結果(二進至表示) 57
圖5-19 表格最小化亂數模擬結果(十進至表示) 57

表目錄
表3-1 一位元比較器真值表 22
表3-2 文獻[15]中比較器設計之1補數修正 25
表3-3 美國專利[16]中的二進位大小比較器真值表 29
表4-1 表格儲存參數 40
表4-2 選擇係數真值表 41
表5-1 梯形數目比較 56

[1]J. P. Pereira, “Content Addressable Memory with Range Compare Function,” US Patent No. 7,035,968 B1, 2006.
[2]P-C Chen, S-J Fan, Y-P Wang, Y-S Kao and T-C Huang, “Area-Efficient High Goodness-of-Fit Noise Generator for Communication Test,” presented at 4th VLSI Test Technology Workshop. S3-2, Yilan, R.O.C., Aug. 19, 2010.
[3]D. Derickson and M. Müller, Digital Communications Test and Measurement: High-Speed Physical Layer Characterization, New Jersey: Prentice Hall, 2007.
[4]D. Lee, J. D. Villasenor, W. Luk and P. H. W. Leong, “A hardware Gaussian noise generator using the Box-Muller method and its error analysis,” IEEE Trans. Computers, vol. C-55, no. 6, pp. 659-671, June 2006.
[5]D-U Lee, W. Luk, J Villasenor and P. Y. K. Cheung, “A hardware Gaussian noise generator for channel code evaluation,” in Proc. 11th Annu. IEEE Symp. Field-Programmable Custom Computing Machines, Napa, California, USA, April 2003, pp 69-78.
[6]G. E. P. Box and M. E. Muller, “A Note on the Generation of Random Normal Deviates,” Ann. Math. Statist., vol. 29, no. 2 pp. 610-611, 1958.
[7]H. C. Tijms, Understanding Probability : Chance Rules in Everyday Life, Cambridge: Cambridge University Press, 2004
[8]K.-C. Chen, “Design and Analysis of Table-based Arithmetic Units with Memory Reduction,” M.S. thesis, Department of Computer Science and Engineering, NSYSU, R.O.C., 2008
[9]D.-U. Lee, W. Luk, J. Villasenor, and P.Y.K. Cheung, “Non-uniform Segmentation for Hardware Function Evaluation,” in Proc. 13th Int. Conf. Field Programmable Logic and Applications, Lisbon, Portugal, Sept. 2003, pp. 796-807.
[10]D.-U. Lee, W. Luk, J. Villasenor, and P.Y.K. Cheung, “Hierarchical Segmentation Schemes for Function Evaluation,” in Proc. IEEE Int. Conf. Field-Programmable Technology (FPT), Tokyo, Japan, Dec. 2003, pp. 92-99.
[11]D.-U. Lee, Cheung R.C.C., Luk W., Villasenor, J.D., “Hierarchical Segmentation for Hardware Function Evaluation,” IEEE Trans. Very Large Scale Integration (VLSI) Systems, vol.17, pp. 103-116, Dec. 2009.
[12]D.B. Thomas and W. L, “Non-uniform random number generation through piecewise linear approximations,” IET Computer and Digital Techniques, vol. 1, no. 4, pp. 312-321, July 2007.
[13]W.-S. Liu, C-T Zou, and Cheng-Wei Wang, “Realization of A Expandable 8-bit Digital Comparator Using 2-bit Digital comparator,” presented at 2008 Conf. Innovative Applications of System Prototyping and Circuit Design, Taichung, R.O.C., 2008
[14]C.-T. Zou, W-S Liu,”Realization of Expandable 8-bit Digital Comparator Using Transmission Gates,” in Proc. 2007 National Computer Symposium, vol. 2, Taichung, R.O.C., Dec. 2007, pp. 478-487.
[15]S.-W. Cheng, “A High-Speed Magnitude Comparator With Small Transistor Count,” in Proc. 10th IEEE Int. Conf. Electronics, Circuits and Systems, vol.3, Sharjah, United Arab Emirates, Dec. 2003, pp. 1168-1171.
[16]L. Pascucci, “Binary-number comparator,” US Patent No.7,016,931, 2006.