使用List Decodable Codes之似磁碟陣列系統

Abstract

利用錯誤更正碼之條列式解碼，我們可以更正超越傳統“錯誤更正極限”的錯誤量。它的好處在於我們所傳送的訊息可以承受更多來自於頻道上的雜訊，不過在我們執行條列式演算法於所接收到的訊息後，我們可能得到很多個可能的結果，但卻無法得知那一個是正確的原訊息。我們稱具有條列式演算法的錯誤更正碼為list-decodable codes。 在這篇論文中，我們將使用list-decodable codes來建造一個具有高容錯性質的似磁碟陣列系統。也就是說，即使有超過一半的系統發生錯誤，我們也可以保存住儲存於系統中的文件。此外，我們也將展示一些關於這系統的實驗結果。

With list decoding of error-correcting codes, we can correct errors beyond the traditional "error-correction radius". The advantage is that the transmitted message can suffer from more errors caused by the noise in the communication channel. But after we perform the list-decoding algorithm on the received word, we get a list of codewords, and still don't know which is the correct one. Codes that have list-decoding algorithm are called list decodable codes. In the thesis, we will use the list-decodable codes to build a RAID-like system with high fault tolerance, for example, more than half the system is faulty. That is, we can safeguard a document in the system, even when more than half the system are failure. We will also bring up some experimental results about our system.