請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/67649完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 江介宏(Jie-Hong Jiang) | |
| dc.contributor.author | Yen-Ting Lin | en |
| dc.contributor.author | 林彥廷 | zh_TW |
| dc.date.accessioned | 2021-06-17T01:42:06Z | - |
| dc.date.available | 2020-08-20 | |
| dc.date.copyright | 2020-08-20 | |
| dc.date.issued | 2020 | |
| dc.date.submitted | 2020-08-15 | |
| dc.identifier.citation | [1] V. Balabanov and J.-H. R. Jiang. Unified qbf certification and its applications. Formal Methods in System Design, 41, 08 2012. [2] M. Bellare, O. Goldreich, and E. Petrank. Uniform generation of NP-witnesses using an NP-oracle. Information and Computation, 163:510–526, 12 2000. [3] R. Brayton and A. Mishchenko. ABC: An academic industrial-strength verification tool. In Proceedings of International Conference on Computer Aided Verification (CAV), pages 24–40, 2010. [4] S. Chakraborty, D. Fremont, K. Meel, S. Seshia, and M. Vardi. On parallel scalable uniform SAT witness generation. In Proceedings of International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pages 304–319, 2015. [5] S. Chakraborty, K. Meel, and M. Vardi. A scalable and nearly uniform generator of SAT witnesses. In Proceedings of International Conerence on Computer Aided Verification (CAV), pages 608–623, 2013. [6] S. Chakraborty, K. Meel, and M. Vardi. A scalable approximate model counter. In Proceedings of International Conference on Principles and Practice of Constraint Programming (CP), pages 200–216, 2013. [7] S. Chakraborty, K. Meel, and M. Vardi. Balancing scalability and uniformity in SAT witness generator. In Proceedings of Design Automation Conference (DAC), pages 60:1–60:6, 2014. [8] R. A. Fisher. Statistical methods for research workers. In S. Kotz and N. L. Johnson, editors, Breakthroughs in Statistics: Methodology and Distribution, pages 66–70. Springer New York, 1992. [9] J. Gentle. Random Number Generation and Monte Carlo Methods. Springer New York, 2003. [10] C. Gomes, A. Sabharwal, and B. Selman. Model counting: A new strategy for obtaining good bounds. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 54–61, 2006. [11] C. Gomes and B. Selman. Near-uniform sampling of combinatorial spaces using XOR constraints. In Proceedings of Advances in Neural Information Processing Systems (NIPS), pages 481–488, 2006. [12] C.-S. Han and J.-H. R. Jiang. When Boolean satisfiability meets Gaussian elimination in a simplex way. In Proceedings of International Conference on Computer Aided Verification (CAV), pages 410–426, 2012. [13] M. Jerrum, L. Valiant, and V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169– 188, 12 1986. [14] V. N. Kravets, J.-H. R. Jiang, and H. Riener. Learning to automate the design updates from observed engineering changes in the chip development cycle. In Proceedings of Design, Automation Test in Europe Conference Exhibition (DATE), pages 738–743, 2020. [15] V. N. Kravets, N.-Z. Lee, and J.-H. R. Jiang. Comprehensive search for eco rectification using symbolic sampling. In Proceedings of Design Automation Conference (DAC), pages 71:1–71:6, 2019. [16] K. Pearson. On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling. In S. Kotz and N. L. Johnson, editors, Breakthroughs in Statistics: Methodology and Distribution, pages 11–28. Springer New York, 1992. [17] J. P. Schmidt, A. Siegel, and A. Srinivasan. Chernoff-Hoeffding bounds for applications with limited independence. SIAM J. Discret. Math., 8(2):223–250, 1995. [18] M. Sipser. A complexity theoretic approach to randomness. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 330–335, 1983. [19] F. Somenzi. CUDD: CU Decision Diagram Package (release 2.4.1). University of Colorado at Boulder, 2005 | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/67649 | - |
| dc.description.abstract | 均勻採樣是統計上一個重要的方法，並被廣泛地運用於模型計數(model counting)、系統驗證與演算法設計等諸多領域。布林空間(Boolean space)中的象徵性採樣(symbolic sampling)是一項於近期提出的技術，其結合了採樣與象徵性的表述來達到有效率的布林論證(Boolean reasoning)。本論文在象徵性採樣的框架下提出一個密實的互斥或閘電路建構方法，在此方法下所產生之電路可於給定的布林空間中進行均勻採樣。 而我們也將此方法進一步的擴展至專注於特定子空間的偏差採樣。 實驗結果顯示了採驗電路生成之效率與其促進布林論證之潛力。 | zh_TW |
| dc.description.abstract | Uniform sampling is an important method in statistics and has various applications in model counting, system verification, algorithm design, among others. Symbolic sampling in a Boolean space is a recently proposed technique that combines sampling and symbolic representation for effective Boolean reasoning. Under the framework of symbolic sampling, we propose a method to construct compact XOR circuits achieving uniform sampling in a given Boolean space. The method is further extended to biased sampling within a focused subspace of interest. Experimental results show the effectiveness of compact sampling circuit generation and its potential to facilitate Boolean reasoning. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-17T01:42:06Z (GMT). No. of bitstreams: 1 U0001-1508202012315000.pdf: 2471274 bytes, checksum: 36553bd030b76655f3ed420adaec19f5 (MD5) Previous issue date: 2020 | en |
| dc.description.tableofcontents | Contents Verification Letter from the Oral Examination Committee i Acknowledgements ii Chinese Abstract iii Abstract iv List of Figures vii List of Tables viii 1 Introduction 1 1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Preliminaries 7 2.1 Symbolic Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 XOR constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Symbolic Uniform Sampling 11 3.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2.1 Sampling Circuit Construction . . . . . . . . . . . . . . . . . . 14 3.2.2 Sampling Circuit Enhancement . . . . . . . . . . . . . . . . . 20 3.3 Symbolic Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3.1 Uniform Sampling . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3.2 Biased Uniform Sampling . . . . . . . . . . . . . . . . . . . . 22 4 Discussions 24 4.1 Symbolic Sampling v.s. Random Pattern Simulation . . . . . . . . . . 24 4.2 An Alternative of Sampling Matrix Generation . . . . . . . . . . . . . 25 5 Experiments 27 5.1 Sampling Circuit Generation . . . . . . . . . . . . . . . . . . . . . . . 28 5.2 Symbolic Sampling and Circuit Simplification . . . . . . . . . . . . . 29 5.3 Uniformity Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.4 Biased Uniform Sampling . . . . . . . . . . . . . . . . . . . . . . . . 36 5.5 Application in Error Detection in Industrial ECOs . . . . . . . . . . . 39 6 Conclusions and Future Work 43 Bibliography 44 List of Publications 47 | |
| dc.language.iso | en | |
| dc.subject | 象徵性採樣 | zh_TW |
| dc.subject | 錯誤偵測 | zh_TW |
| dc.subject | 均勻採樣 | zh_TW |
| dc.subject | 均勻度測試 | zh_TW |
| dc.subject | 電路簡化 | zh_TW |
| dc.subject | 雜湊函數 | zh_TW |
| dc.subject | error detection | en |
| dc.subject | symbolic sampling | en |
| dc.subject | hash function | en |
| dc.subject | circuit simplification | en |
| dc.subject | uniformity testing | en |
| dc.subject | uniform sampling | en |
| dc.title | 象徵性均勻採樣之於互斥或閘電路 | zh_TW |
| dc.title | Symbolic Uniform Sampling with XOR Circuits | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 108-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 王柏堯(Bo-Yao Wang),陳郁方(Yu-Fang Chen),黃鐘揚(Zhong-Yang Huang),顏嘉志(Jia-Zhi Yan) | |
| dc.subject.keyword | 均勻採樣,象徵性採樣,雜湊函數,電路簡化,均勻度測試,錯誤偵測, | zh_TW |
| dc.subject.keyword | uniform sampling,symbolic sampling,hash function,circuit simplification,uniformity testing,error detection, | en |
| dc.relation.page | 47 | |
| dc.identifier.doi | 10.6342/NTU202003506 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2020-08-17 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
| 顯示於系所單位： | 電子工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| U0001-1508202012315000.pdf 未授權公開取用 | 2.41 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。