請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/73102
標題: | 可利用快速傅立葉轉換運算的里德所羅門碼之一些研究成果 Some Results on Reed-Solomon Codes Using Fast Fourier Transforms |
作者: | Ting-Xuan Huang 黃亭軒 |
指導教授: | 林茂昭(Mao-Chao Lin) |
關鍵字: | 有限場,里德-所羅門碼,快速傅立葉轉換,截短, Finite field,Reed-Solomon codes,Fast Fourier transform,Puncturing, |
出版年 : | 2019 |
學位: | 碩士 |
摘要: | 在[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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/73102 |
DOI: | 10.6342/NTU201901382 |
全文授權: | 有償授權 |
顯示於系所單位: | 電信工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-108-1.pdf 目前未授權公開取用 | 2.24 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。