跳到主要內容

臺灣博碩士論文加值系統

(100.28.2.72) 您好!臺灣時間:2024/06/13 11:00
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:陳品充
研究生(外文):Pin-Chong Chen
論文名稱:低成本快速任意分佈之高符合度亂數產生法
論文名稱(外文):Low-Cost Fast Distribution-Programmable Random Number Generators with Goodness of fit
指導教授:黃宗柱
指導教授(外文):Tsung-Chu Huang
學位類別:碩士
校院名稱:國立彰化師範大學
系所名稱:積體電路設計研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:英文
論文頁數:31
中文關鍵詞:亂數產生器符合度線性回授移位暫存器蒙地卡羅模擬查表非等間距表格分佈可規劃開方測試通訊測試
外文關鍵詞:random number generatorgoodness of fitlinear feedback shift registerMonte Carlo Simulationlook-up tablenon-equal bin-widthdistribution-programmablechi-square testbit-error rate testcommunication test
相關次數:
  • 被引用被引用:0
  • 點閱點閱:171
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
中文摘要
亂數產生器在很多領域的很多面向上扮演著非常關鍵的角色,包括通訊測試、蒙地卡羅模擬、位元錯誤率測試、統計與機率處理、雜訊與抖動產生與加密等等。亂數產生器的主要特徵包括亂度、解析度與符合度,但對於多數具有可以接受之亂度與解析度的應用中,符合度往往成為基於統計分析與隨機處理的快速評估之最重要之特性。尤其是,對於加速位元錯試測試而言,符合度無疑是遠比亂度和解析度來的重要。
在本篇論文中,一種分佈可補償的方法藉由調整與補償分佈,提出來矯正雜訊轉換器或抖動產生器的非線性所造成之符合度偏差。尤其是,為了能在每一時脈週期產生亂數,本論文主要兩項技術來達到低面積成本與快速:其一藉由本研究團隊新發明之一大小比較器來實現非等間距機率密度查表縮減技術;其二藉由在機率微積分中的冪次搜尋演算法來消除面積龐大的乘法器,並進而加快速度。
另外,本論文也首先提出對分佈的補償,用以提昇符合度。補償的方法,主要是藉由給定一個理想分佈,用來校正非線性數位對時間轉換器。我們發展出一種可規劃、快速且具有面積效益梯型之任意線段亂數產生器。本文的亂數產生器均勻分佈的部分是來自於線性回授移位暫存器,其分佈計算方式是以垂直廟塔式的方法,我們將所產生可任意分佈的亂數輸入到基準的數位對時間轉換器,而經由數位對時間轉換器輸出的分佈進行補償。

Abstract
Random number generators play an important role over a lot of fields in many aspects including communication test, Monte-Carlo simulation, bit error rate test, statistic and probabilistic process, noise and jitter generation, encryption, and so on. Randomness, resolution and goodness of fit are three major properties of a random number generator. For most applications in testing including communication test, jitter generation and bit error rate test, goodness of fit is usually the most critical for fast estimation based on statistic process when the randomness and resolution are acceptable enough. Especially distribution goodness-of-fit is actually more critical than randomness and resolution for accelerating BERT.
In this thesis, a distribution compensable methodology is proposed for calibrating the non-ideality of noise converters by adjusting the given distribution of random number generators. For generating every cycle in built-in communication test, a fast and area-efficient piecewise-line random number generator is developed by the non-equal bin-width probability-density table minimization technique using a novel magnitude-comparator-based CAM and the multiplier-elimination searching algorithm.
In our experiments, the speedup and area reduction can be obviously estimated from the proposed algorithms. However, a jitter generator and a flash DAC are still developed to validate the effectiveness and efficiency of jitter and noise compensations respectively.

Contents
中文摘要 i
Abstract ii
誌謝 iii
LIST OF FIGURE v
LIST OF TABLES vi
Chapter 1 Introduction 1
Chapter 2 Distribution-Compensable Jitter Generator 6
Basic Methodology 6
Efficient RNG 7
Chapter 3 Table Minimization and Multiplier Removing 11
Pdf Table Minimization 11
Magnitude-Comparator Based CAM 14
Chapter 4 Experiments 18
Benchmark Distributions 18
Benchmark Converters for Experiments 18
Simulations of LUTs 20
Simulations of RNGs 21
NG/JG Distribution Compensation 23
Chapter 5 Conclusions 27
References 28

LIST OF FIGURE
Fig. 1 Typical table-lookup methods. ................................................................................ 3
Fig. 2 (a) Ziggurat algorithm and (b) 7-layer Ziggurat diagram........................................ 4
Fig. 3 A programmable noise/jitter generator. ................................................................... 5
Fig. 4 Distribution-Compensable algorithm. ..................................................................... 6
Fig. 5 Uniform and composed distributions. ..................................................................... 7
Fig. 6 The ith H- and V-trapezoid pdf ’s. ............................................................................ 8
Fig. 7 A pipeline circuit for the V-trapezoid method according to Eq.3. .......................... 10
Fig. 8 Proposed pdf table minimization algorithm. ......................................................... 12
Fig. 9 A pipeline circuit for the V-trapezoid method according to Eq.3. .......................... 13
Fig. 10 An example for pdf tabular. .................................................................................. 14
Fig. 11 Proposed n-bit GE magnitude comparator........................................................... 16
Fig. 12 An SRAM magnitude comparator based CAM................................................... 17
Fig. 13 Two benchmark converters (a) PDL, and (b) DAC. ........................................... 19
Fig. 14 Transfer function of a 5-bit DTC in Fig. 13(a). ................................................... 20
Fig. 15 An SRAM magnitude comparator based CAM................................................... 21
Fig. 16 Examples of the H-trapezoid RNGs with the simulation results......................... 22
Fig. 17 Examples of the V-trapezoid RNGs with the simulation results. ........................ 23
Fig. 18 Compensating Steps of an example with specification in Table I. ...................... 25


LIST OF TABLES
TABLE I Specification for the example shown in fig.18. ............................................... 25
TABLE II Chi-square Test Statistics for Distribution-Compensability. ......................... 26
[1] D. Derickson and M. Müller. Digital Communications Test and Measurement: High-Speed Physical Layer Characterization. Prentice Hall, ISBN: 0132209101, 2007.
[2] M. M. Hafed, G. D. Huerden and G. W. Roberts. System and Method for Generating a Jittered Test Signal. ROC Innovation Patent, No. 200606615, Feb. 16, 2006.
[3] S. Tabatabaei, M. Lee and F. Ban-Zeev. “Jitter generation and measurement for test of multi-Gbps serial IO,” IEEE Int’l Test Conference, pp.1313-1321, Oct. 2004.
[4] T. Nakamura and T. Sekino. Jitter Generating Circuit. ROC Innovation Patent, No. 200703911, Jan. 1, 2007.
[5] M. S. Walker. System and Method for Generating a Jittered Signal. US Patent No.06285197, July 31, 1998.
[6] S.-W. Chang and J.-L. Huang. An On-Chip Jitter Generation Technique for SerDes Jitter Tolerance Testing. In Proc. The 17th VLSI Design/CAD Symposium, pages 707-710, Taiwan, Aug. 2006.
[7] S. F. Blazo. Signal Generator for Generating a Jitter/Wander Output. US Patent No.05742208, Sep. 6, 1996.
[8] H.-M. Tseng and J.-C. Wang. Digital Jitter Synthesizer. ROC Patent Innovation No. 200603545, 2006/7/21.
[9] J.-L. Chia. Digital Frequency Jittering Apparatus with Random Data Generator Data Generator and Method Thereof. ROC Innovation Patent, No. 200805143, Jan. 2008.
[10] K. A. Jenkins, J.-C. Lo, P. Song and T. Xia. Programmable Jitter Signal Generator. US Patent No.07095264, Dec. 2, 2003.
[11] K. Sato, M. Mizuno and K. Aoki. Delay Time Control Circuit. US Patent No.05424590, Jun. 23, 1993.
[12] J. Li, Z. Zheng, M. Liu and S. Wu, “Large Dynamic Range Accurate Digitally Programmable Delay Line with 250-ps Resolution,” The 8th International Conf. on Signal Processing, Volume 1, pp.16-20, 2006.
[13] M. M. Hafed, G. D. Huerden and G. W. Roberts. System and Method for Generating a Jittered Test Signal. ROC Patent 200606615, Feb. 16, 2006.
[14] A. Lymer and W. Lothian. Variable Frequency Jitter Generator. US Patent No.04916441, May 19, 1989.
[15] A. D. Black and T. M. Tobin. Apparatus and Method for Synthesis of Signals with Programmable Period. US Patent No.05394106, Aug. 31, 1993.
[16] M. S. Reid, E. A. Brown, S.P. DeWeerth, “Subthreshold CMOS array for generating a Gaussian distribution of currents,” IEEE Trans. on Circuits and Systems II, vol.53, no.10, pp.1123-1127, Oct. 2006.
[17] 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. on Computers, 55(6), pp. 659-671, June 2006.
[18] S. Kogan. Electronic Noise and Fluctuations in Solids. Cambridge University Press, 1996.
[19] G. E. P. Box and M. E. Muller, “A Note on the Generation of Random Normal Deviates,” The Annals of Mathematical Statistics, Vol. 29, No. 2 pp. 610-611, 1958.
[20] G. Marsaglia and W.-W. Tsang, “The Ziggurat method for generating random variables,” Journal of Statistical Software, vol.5, no.8, 2000.
[21] D. B. Thomas and W. Luk, “Non-uniform random number generation through piecewise linear approximations,” IET Computers and Digital Techniques, vol. 1, no. 4, pp.312-321, 2007.
[22] Y.-H. Chou, T.-H. Wu, P.-C. Chen and T.-C. Huang. Distribution-Compensable Jitter Generator for Communication Test. The 20th VLSI Design and CAD Symp., Taiwan, pp.574-577, Aug. 5, 2009.
[23] D.-U. Lee, R.C.C. Cheung, W. Luk and J.D. Villasenor. "Hierarchical Segmentation for Hardware Function Evaluation." IEEE Trans. on Very Large Scale Integration (VLSI) Systems,vol.17, pp. 103-116, Dec. 2009.
[24] T.-C. Huang. "Magnitude Comparator and Magnitude Comparator Based Content Addressable Memory Cell." ROC Patent, Ap. No.98144567, Dec. 23, 2009.
[25] A. Hai. "Magnitude comparator based content addressable memory for search and sorting." US Patent No.6,987,683, Jan. 17, 2006.
[26] S. M. Wanzakhade. "Magnitude comparator circuit for content addressable memory with programmable priority selection." US Patent No.7,403,407, Jul. 22, 2008.
[27] L. Pascucci. "Binary-number comparator." US Patent No.7,016,931, Mar. 21, 2006.
[28] S. Perri and P. Corsonello. "Fast Low-Cost Implementation of Single-Clock-Cycle Binary Comparator." IEEE Trans. on Circuits and Systems—II: Express Briefs, vol. 55, no. 12, Dec. 2008.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 侯錦雄、林宗賢(1996)。日月潭風景區目標市場定位策略中之旅遊意象度量探討。戶外遊憩研究學報,9(1),57-77。
2. 林雲燦、莊翔達、張良漢(2009)。休閒農業區遊憩地吸引力對遊客重遊意願之影響。運動與遊憩研究,4(1),153-166。
3. 沈進成、廖若岑(2005)。不同旅遊意象遊客之旅遊體驗與忠誠度影響關係之研究-以華山咖啡為例。生物與休閒事業研究,3(1),43-56。
4. 林晏州、陳惠美、顏家芝(1998)。高雄都會公園遊客滿意度及相關因素之研究,戶外遊憩研究,11(4):59-71。
5. 侯錦雄(1999)。形式的魅影-金門觀光的戰地異境想像與體驗。觀光研究學報,5(1),39-52。
6. 林聖偉、李君如(2006)。品牌形象、知覺價值、顧客滿意度與忠誠度關係之研究-以旅行社海外團體套裝旅遊為例。旅遊管理研究(6-1),63-81。
7. 鄭琦玉、楊文燦(1995)。遊憩衝擊認知及其滿意度關係之研究,戶外遊憩研究,8(2),109-132。
8. 劉瓊如、林若慧、吳正雄(2002)。海岸型風景區遊客旅遊意象之區隔研究-以東北角海岸國家風景區為例,戶外遊憩研究學報,15(3),55-78。
9. 蔡鳳兒(2006)。遊客體驗、旅遊意象、滿意度與忠誠度相關性之研究-以日月潭國家風景區為例。國立空中大學生活科學係生活科學學報。10,211~242。
10. 蔡進發、甘唐沖、江靜宜(2008)。遊客對國家公園遊憩資訊、滿意度、場所依戀與重遊意願之研究。運動與遊憩研究。3(1),125-152。
11. 趙家民、鮑敦瑗、陳君音(2008)。安平港國家歷史風景區觀光發展之研究。運動與遊憩研究。3(2),143-162。
12. 許義忠(2002)。遊客對參加冒險旅遊之動機與滿意度之研究-以秀姑巒溪泛舟為例,觀光研究學報,8(2),115-130。
13. 陳慧如、黃純德、劉靜霙(2009)。鶯歌地區遊客特性與觀光意象之關係研究。運動休閒餐旅研究,4(1),110-130。
14. 陳思倫、劉錦桂(1993)。影響旅遊目的地選擇之地點特性及市場區隔之研究。戶外遊憩研究,5(2),39-70。
15. 孫樹根、劉建麟、莊淑姿(2008)。民宿滿意度與重遊意願關聯性分析-以白河民宿遊客為例。台大農業推廣學報,24,1-16。