可利用快速傅立葉轉換運算的里德所羅門碼之一些研究成果

Abstract

在[1]之中提出了一個可以利用快速傅立葉轉換作二進制拓展有限場運算的多項式基底。因為傳統的里德-所羅門碼在編碼端與解碼端有較高的複雜度，利用此多項式基底可以建構出碼長為二的次方倍的里德-所羅門碼並使其複雜度降低。其中在解碼演算法中，碼長與訊息長度的差必須為二的次方倍，因此利用此方法只能建構碼率最低為0.5的里德-所羅門碼。 本論文研究課題之一是對解碼過程中提出另一種多項式除法，藉此改善在某種情況下不能進行多項式除法的問題，並對其有限場中的乘法與加法效能進行分析。除此之外，利用子空間多項式的性質，我們提出針對此多項式基底所建構出的里德-所羅門碼的解碼演算法，並適用於碼率小於0.5的里德-所羅門碼，而此多項式基底是由子空間多項式所組合而成。在不改變解碼結構的前提下，我們還提出了一種針對此里德-所羅門碼的截短方法，並使其碼長更有彈性。

In [1], a novel polynomial basis over finite fields of characteristic two was proposed, such that the fast Fourier transform can be employed in the computation over binary extension finite fields. Because traditional Reed-Solomon codes have high complexity in the encoder, we can reduce its complexity by applying this polynomial basis to construct n is a power of two Reed-Solomon codes over binary extension finite field. In the decoding procedure, n-k is a power of two. Thus the approach can only be used in Reed-Solomon Codes with coding rate more than or equal to 0.5. One of the topics of this thesis is using another polynomial division in the decoding procedure to solve restrictions, and we analyze its finite field multiplications and additions complexities. Moreover, we provide an algorithm to decode Reed-Solomon codes with coding rate less than 0.5 using this polynomial basis by exploiting the properties of the subspace polynomial, and the subspace polynomial is the pattern of this polynomial basis. We also present a puncturing scheme on this Reed-Solomon codes and make the codeword length more flexible without changing the decoding architecture.