亂度萃取碼與應用

Abstract

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