Full metadata record
DC FieldValueLanguage
dc.contributor.author陳兆軒zh_TW
dc.contributor.author陸曉峯zh_TW
dc.contributor.authorLu, Hsiao-Fengen_US
dc.date.accessioned2018-01-24T07:40:04Z-
dc.date.available2018-01-24T07:40:04Z-
dc.date.issued2017en_US
dc.identifier.urihttp://etd.lib.nctu.edu.tw/cdrfb3/record/nctu/#GT070560219en_US
dc.identifier.urihttp://hdl.handle.net/11536/141000-
dc.description.abstract當人們想要擴大里德．所羅門碼 (Reed-Solomon code) 解碼器的解碼半徑(Decoding radius) 時，通常會想到 Guruswami-Sudan 演算法。這篇論文首先會對此演算法背後的理論及實作部分進行完整的回顧，由於現行實作算法效率的瓶頸主要來自於其中的插值 (Interpolation)步驟，因此回顧之後，我們會對插值步驟進行複雜度分析，探討其中最多需要使用幾個有限體 (Finite field) 乘法；透過電腦模擬的輔助，我們也分析在對 [255,128] 里德．所羅門碼進行解碼的過程中，插值步驟實際所需的有限體乘法次數。另外，此數字會與傳統的 Berlekamp-Massey演算法相比較以檢驗現行插值算法的效率。 最後，在能夠得到通道(Channel)額外旁訊息(Side information)的情況下，我們對Guruswami-Sudan演算法進行推廣，不論從理論分析的角度或是從電腦模擬的結果來看，我們的推廣算法都較適用於高碼率編碼 (High rate code)。zh_TW
dc.description.abstractWhen 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.en_US
dc.language.isoen_USen_US
dc.subjectGuruswami-Sudan 解碼器zh_TW
dc.subject降低複雜度zh_TW
dc.subject旁訊息zh_TW
dc.subjectGuruswami-Sudan decodersen_US
dc.subjectComplexity reductionen_US
dc.subjectSide informationen_US
dc.titleGuruswami-Sudan 解碼器: 使用旁訊息降低複雜度zh_TW
dc.titleComplexity Reduction of Guruswami-Sudan Decoders with Side Informationen_US
dc.typeThesisen_US
dc.contributor.department電信工程研究所zh_TW
Appears in Collections:Thesis