所謂亂度萃取器就是那些能夠將具有些許亂度的分佈中萃取出``亂度''的函式，而亂度萃取器對於計算理論方面有著許多不同的應用。亂度萃取碼則是利用亂度萃取器來將資訊作編碼。由於這種亂度萃取碼有著非常良好的漢明距離性質，因此具有軟性解碼的能力，並且非常適合用於大量干擾的頻道之中。
在本論文中，我們首先簡介亂度萃取器以及它與編碼之間的關係，並介紹一個架構在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.