(34.239.150.57) 您好!臺灣時間:2021/04/18 22:52
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:鄧欽元
研究生(外文):Chin-Yuan Teng
論文名稱:亂度萃取碼與應用
論文名稱(外文):Extractor Codes with Applications
指導教授:蔡錫鈞蔡錫鈞引用關係
指導教授(外文):Shi-Chun Tsai
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:英文
論文頁數:80
中文關鍵詞:亂度萃取器列舉解碼法軟性決策解碼法亂度萃取碼困難函式磁碟陣列
外文關鍵詞:ExtractorsList decodingSoft-decision decodingExtractor codesHardcore functionsRAID
相關次數:
  • 被引用被引用:0
  • 點閱點閱:132
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
所謂亂度萃取器就是那些能夠將具有些許亂度的分佈中萃取出``亂度''的函式,而亂度萃取器對於計算理論方面有著許多不同的應用。亂度萃取碼則是利用亂度萃取器來將資訊作編碼。由於這種亂度萃取碼有著非常良好的漢明距離性質,因此具有軟性解碼的能力,並且非常適合用於大量干擾的頻道之中。
在本論文中,我們首先簡介亂度萃取器以及它與編碼之間的關係,並介紹一個架構在Trevisan所發明的亂度萃取器上的亂度萃取碼。接著我們介紹兩種關於亂度萃取碼的應用:困難函式與亂度萃取碼-磁碟陣列。對於亂度萃取碼-磁碟陣列系統,我們也將提出多種明確且有效率的存取演算法與回復演算法,使得這種新系統能夠有良好的可靠度與效率。

Extractors are functions which can ``extract'' random bits from certain distributions that contain some randomness. There are many applications of extractors in complexity theory. Extractor codes are codes which use extractors to encode information.These codes have the very good distance property.
Therefore they have the soft-decision decoding ability and could be suitable for highly noisy channels.
In this thesis, we first explain extractors and some relations with codes. We introduce an explicit extractor code based on Trevisan's extractor. Then we show two applications of extractor codes: hardcore functions and EC-RAID. We also bring up explicit and efficient calculating and recovering algorithms in our EC-RAID system, so that this new system can offer the high reliability and performance.

1 Introduction 1
2 Extractors and Dispersers 3
2.1 Weak RandomSources .. . . . . . . . . . . . . . . . . . 3
2.2 Extractors . . . . . . .. . . . . . . . . . . . . . . . 5
2.3 Dispersers . . . . . .. . . . . . . . . . . . . . . . . 6
3 Coding theory 9
3.1 Basic concepts . . . . .. . . . . . . . . . . . . . . . 9
3.2 Maximum likelihood decoding . . . . . . . . . . . . . . 11
3.3 List decoding . . . . . . . . . . . . . . . . . . . . . 12
3.4 Soft-decision decoding . . . . . . . . . . . . . . . . 13
4 Extractor codes 17
4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . 17
4.2 The equivalence between codes and extractors . . . . . 18
4.3 The Johnson bound . . . . . . . . . . . . . . . . . . . 21
5 Trevisan’s extractor 25
5.1 Idea . . . . . . .. . . . . . . . . . . . . . . . . . . 25
5.2 Designs . . . . . . . . . . . . . . . . . . . . . . . . 26
5.3 Trevisan’s extractor . . . . . . . . . . . . . . . . . 27
5.4 Extractor codes with efficient soft decoding . . . . . 28
5.4.1 Encoding extractor codes . . . . . . . . . .. . . . . 28
5.4.2 Decoding extractor codes . . . . .. . . . . . . . . . 29
6 Hardcorebits 35
6.1 One-way functions . . . . . . . . . . . . . . . . . . . 35
6.2 Construction . . . . . . . . . . . . . . . . . . . . . 36
7 Reed-Solomon codes in RAID 39
7.1 RAID basics . . . . . . . . . . . . . . . . . . . . . . 39
7.2 Reed-Solomon Codes . . . . . . . . . . . . . . . . . . 42
7.2.1 Encoding Reed-Solomon codes . . . . . . . . . . . . . 43
7.2.2 Berlekamp-Welch decoding algorithm . . . . .. . . . . 44
7.3 Reed-Solomon coding in RAID-like systems . . . . . . . 47
7.3.1 Calculating checksum words . . . . . . .. . . . . . . 48
7.3.2 Maintaining checksum words . . . . . . . . . . . . . 49
7.3.3 Recovering fromfailures . . . . . . . . . . . . . . . 50
8 Extractor codes in RAID 53
8.1 Concatenated codes . . . . . . . . . . . . . . . . . . 53
8.1.1 Distance properties . . . . . . . . . . . . . . . . . 54
8.1.2 Hadamard codes . . . . . . . . . . . . . . . . .. . . 54
8.2 Extractor coding in RAID-like systems . . . . . . . . . 56
8.2.1 Preparations . . . . . . . . . . . . . . . . .. . . . 56
8.2.2 Simple designs . . . . . . . . . . . . . . . . . . . 57
8.2.3 Calculating algorithm. . . . .. . . . . . . . . . . . 59
8.2.4 Unique recovering algorithm . . . . . . . . . . . . . 61
8.2.5 Soft recovering algorithm. . . .. . . . . . . . . . . 64
8.3 An example . . . . . . . . . .. . . . . . . . . . . . . 70
8.4 Improvement issues . . . . . . . . . . . . . . . . . . 74
Bibliography 77

[1] M. Blum and S. Micali, “How to generate cryptographically strong sequences of pseudo-random bits,” SIAM Journal on Computing, 13(4):850—864, November 1984.
[2] P. M. Chen, E. K. Lee, G. A. Gibson, R. H. Katz, and D. A. Patterson, “RAID: High Performance Reliable Secondary Storage,” ACM Computing Surveys, 26(2):145—185, 1994.
[3] P. Elias, “List decoding for noisy channels,” Institute of Radio Engineers, 94—104, 1957.
[4] G. D. Forney, “Generalized Minimum Distance Decoding,” IEEE Trans. Inform. Theory, 12:125—131, 1966.
[5] O. Goldreich and L. A. Levin, “A hard-core predicate for all one-way functions,” Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, 25—32, May 1989.
[6] V. Guruswami and M. Sudan, “Improved decoding of Reed-Solomon and algebraic-geometric codes,” IEEE Transactions on Information Theory, 45:1757—1767, September 1999.
[7] V. Guruswami and M. Sudan, “List decoding algorithms for certain concatenated codes,” Proceedings of the 32nd annual ACM symposium on Theory of computing, 181—190, May 2000.
[8] R. Impagliazzo, “Personal Communication,” July 1997.
[9] R. Impagliazzo and L.A. Zuckerman, “How to Recycle Random Bits,” 30th FOCS, 248—253, 1989.
[10] S. M. Johnson, “A new upper bound for error-correcting codes,” IEEE Trans. on Info. Theory, 8:203—207, 1962.
[11] E. Kaltofen, “A Polynomial-Time Reduction from Bivariate to Univariate Integral Polynomial Factorization,” In 23rd Annual Symposium on Foundations of Computer Science, 57—64, 1982.
[12] R. Koetter and A. Vardy, “Algebraic soft-decision decoding of Reed-Solomon codes” IEEE Transactions on Information Theory, August 31 2001
[13] N. Nisan and A. Ta-Shma, “Extracting randomness: A survey and new constructions,” Journal of Computer and System Sciences, 58(1):148—173, 1999.
[14] N. Nisan and A. Wigderson, “Hardness vs randomness,” Journal of Computer and System Science, 49:149—167, 1994.
[15] N. Nisan and D. Zuckerman, “More deterministic simulation in logspace,” In Proceedings of the 25th Annual ACM Symposium on the Theory Computing, 235—244, 1993.
[16] D. A. Patterson, G. Gibson, and R. H. Katz, “A case for redundant arrays of inexpensive disks (RAID),” ACM SIGMOD International Conference on Management of Data, 109—116, June 1988.
[17] J. S. Plank, “A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems,” Software, Practice and Experience, 27(9):995—
1012, September 1997.
[18] R. Raz, O. Reingold, and S. Vadhan, “Extracting all the randomness and reducing the error in Trevisan’s extractors,” Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 149—158, 1999.
[19] M. Santha and U. Vazirani, “Generating quasi-random sequences from slightly random sources,” Journal of Comput. System Science, 75—87, 1986.
[20] A. Srinivasan and D. Zuckerman, “Computing with very weak random sources,” Proceedings of the 35th Annual IEEE Symposium on the Foundations of Computer Science, 1994.
[21] M. Sudan, “Algorithmic issues in coding theory,” In 17th Conference on Foundations of Software Technology and Theoretical Computer Science, 1997.
[22] M. Sudan, “Decoding of Reed-Solomon codes beyond the error correction bound,” Journal of Complexity, 13(1):180—193, 1997.
[23] M. Sudan, “List decoding: Algorithms and applications,” SIGACT News, 31:16—27, 2000.
[24] A. Ta-Shma and D. Zuckerman, “Extractor Codes,” Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 193—199, July
2001.
[25] A. Ta-Shma, C. Umans, and D. Zuckerman, “Loss-less Condensers, Unbalanced Expanders, and Extractors,” Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001.
[26] L. Trevisan, “Extractors and pseudorandom generators,” Journal of the ACM, 48(4):860—879, July 2001.
[27] L. R. Welch and E. R. Berlekamp, “Error correction for algebraic block codes,” US patent, Number 4, 633, 470, 1986.
[28] X-W. Wu and P.H. Siegel, “Ecient root-nding algorithm with application to list decoding of algebraic-geometric codes,” IEEE Trans. Inform. Theory, 47:2579—2587, September 2001.
[29] X. Yu, B. Gum, Y. Chen, R. Y. Wang, K. Li, A. Krishnamurthy, and T. E. Anderson, “Trading capacity for performance in a disk array,”Proceedings of the OSDI, October 2000.
[30] D. Zuckerman, “Simulating BPP using a general weak random source,”Proceedings of the 32nd Annual IEEE Symposium on the Foundations of Computer Science, 79—89, 1991.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔