Guruswami-Sudan 解碼器: 使用旁訊息降低複雜度

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.