Title: Guruswami-Sudan 解碼器: 使用旁訊息降低複雜度
Complexity Reduction of Guruswami-Sudan Decoders with Side Information
Authors: 陳兆軒
Lu, Hsiao-Feng
Keywords: Guruswami-Sudan 解碼器;降低複雜度;旁訊息;Guruswami-Sudan decoders;Complexity reduction;Side information
Issue Date: 2017
Abstract: 當人們想要擴大里德.所羅門碼 (Reed-Solomon code) 解碼器的解碼半徑(Decoding radius) 時,通常會想到 Guruswami-Sudan 演算法。這篇論文首先會對此演算法背後的理論及實作部分進行完整的回顧,由於現行實作算法效率的瓶頸主要來自於其中的插值 (Interpolation)步驟,因此回顧之後,我們會對插值步驟進行複雜度分析,探討其中最多需要使用幾個有限體 (Finite field) 乘法;透過電腦模擬的輔助,我們也分析在對 [255,128] 里德.所羅門碼進行解碼的過程中,插值步驟實際所需的有限體乘法次數。另外,此數字會與傳統的 Berlekamp-Massey演算法相比較以檢驗現行插值算法的效率。 最後,在能夠得到通道(Channel)額外旁訊息(Side information)的情況下,我們對Guruswami-Sudan演算法進行推廣,不論從理論分析的角度或是從電腦模擬的結果來看,我們的推廣算法都較適用於高碼率編碼 (High rate code)。
When it comes to the decoding of Reed-Solomon codes (RS codes, in short) beyond the traditional error correction bound, people usually resort to the so-called Guruswami-Sudan (GS, in short) algorithm. In this paper, we first give a self-contained review of GS algorithm. Since the complexity of interpolation, one of the key steps in GS, has always been a great concern, we provide a worst-case analysis in terms of the number of finite field multiplications. With computer simulation, we also discuss how many finite field multiplications are required in the decoding of practical $[255,128]$ RS codes. To see the efficiency of current implementations, this number will be compared to that of the well-known inversionless Berlekamp-Massey algorithm. Finally, a complexity reduction scheme of GS is proposed via the help of additional side information. It turns out that our reduction scheme is more suitable for high rate codes.
URI: http://etd.lib.nctu.edu.tw/cdrfb3/record/nctu/#GT070560219
Appears in Collections:Thesis