請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/73102
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 林茂昭(Mao-Chao Lin) | |
dc.contributor.author | Ting-Xuan Huang | en |
dc.contributor.author | 黃亭軒 | zh_TW |
dc.date.accessioned | 2021-06-17T07:17:35Z | - |
dc.date.available | 2019-07-15 | |
dc.date.copyright | 2019-07-15 | |
dc.date.issued | 2019 | |
dc.date.submitted | 2019-07-11 | |
dc.identifier.citation | [1] S.-J. Lin, W.-H. Chung, and Y. S. Han, “Novel polynomial basis and its application to reed-solomon erasure codes,” in 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 316–325, IEEE, 2014.
[2] I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields,” Journal of the society for industrial and applied mathematics, vol. 8, no. 2, pp. 300–304,1960. [3] N. Chen and Z. Yan, “Complexity analysis of reed-solomon decoding over gf (2^m) without using syndromes,” EURASIP Journal on Wireless Communications and Networking, vol. 2008, no. 1, p. 43634, 2008. [4] S. B. Wicker and V. K. Bhargava, Reed-Solomon codes and their applications. John Wiley & Sons, 1999. [5] J. W. Cooley and J. W. Tukey, “An algorithm for the machine calculation of complex fourier series,” Mathematics of computation, vol. 19, no. 90, pp. 297–301, 1965. [6] S.-J. Lin, T. Y. Al-Naffouri, and Y. S. Han, “Fft algorithm for binary extension finite fields and its application to reed–solomon codes,” IEEE Transactions on Information Theory, vol. 62, no. 10, pp. 5343–5358, 2016. [7] R. Wang and R. Liu, “A novel puncturing scheme for polar codes,” IEEE Communications Letters, vol. 18, no. 12, pp. 2081–2084, 2014. [8] S. Gao and T. Mateer, “Additive fast fourier transforms over finite fields,” IEEE Transactions on Information Theory, vol. 56, no. 12, pp. 6265–6272, 2010. [9] O. Ore, “On a special class of polynomials,” Transactions of the American Mathematical Society, vol. 35, no. 3, pp. 559–584, 1933. [10] D. G. Cantor, “On arithmetical algorithms over finite fields,” Journal of Combinatorial Theory, Series A, vol. 50, no. 2, pp. 285–300, 1989. [11] J. Von zur Gathen and J. Gerhard, “Arithmetic and factorization of polynomial over f2,” in ISSAC, vol. 96, pp. 1–9, 1996. [12] S. Gao, “A new algorithm for decoding reed-solomon codes,” in Communications, Information and Network Security, pp. 55–68, Springer, 2003. [13] A. Shiozaki, “Decoding of redundant residue polynomial codes using euclid’s algorithm,” IEEE Transactions on Information Theory, vol. 34, no. 5, pp. 1351–1354, 1988. [14] J. Von Zur Gathen and J. Gerhard, Modern computer algebra. Cambridge university press, 2013. [15] R. T. Moenck, “Fast computation of gcds,” in Proceedings of the fifth annual ACM symposium on Theory of computing, pp. 142–151, ACM, 1973. [16] E. Arikan, “Channel polarization: A method for constructing capacity-achieving codes,” in 2008 IEEE International Symposium on Information Theory, pp. 1173– 1177, IEEE, 2008. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/73102 | - |
dc.description.abstract | 在[1]之中提出了一個可以利用快速傅立葉轉換作二進制拓展有限場運算的多項式基底。因為傳統的里德-所羅門碼在編碼端與解碼端有較高的複雜度,利用此多項式基底可以建構出碼長為二的次方倍的里德-所羅門碼並使其複雜度降低。其中在解碼演算法中,碼長與訊息長度的差必須為二的次方倍,因此利用此方法只能建構碼率最低為0.5的里德-所羅門碼。
本論文研究課題之一是對解碼過程中提出另一種多項式除法,藉此改善在某種情況下不能進行多項式除法的問題,並對其有限場中的乘法與加法效能進行分析。除此之外,利用子空間多項式的性質,我們提出針對此多項式基底所建構出的里德-所羅門碼的解碼演算法,並適用於碼率小於0.5的里德-所羅門碼,而此多項式基底是由子空間多項式所組合而成。在不改變解碼結構的前提下,我們還提出了一種針對此里德-所羅門碼的截短方法,並使其碼長更有彈性。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-17T07:17:35Z (GMT). No. of bitstreams: 1 ntu-108-R06942111-1.pdf: 2289438 bytes, checksum: fb2004650fc9a35726287e4f68de979d (MD5) Previous issue date: 2019 | en |
dc.description.tableofcontents | 口試委員會審定書i
致謝ii 中文摘要iii Abstract iv Contents vi List of Figures viii 1 Introduction 1 2 Review of Reed-Solomon Codes Using a Novel Polynomial Basis 5 2.1 Review of a Novel Polynomial Basis over Binary Extension Fields . . . 5 2.1.1 Subspace Polynomial . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.2 Novel Polynomial Basis . . . . . . . . . . . . . . . . . . . . . 8 2.2 Reed-Solomon Codes Using a Novel Polynomial Basis . . . . . . . . . 9 2.2.1 Encoding Algorithm for Non-systematic Reed-Solomon Codes . 9 2.2.2 Alternative Polynomial Basis . . . . . . . . . . . . . . . . . . 11 2.2.3 Decoding Algorithm for Non-systematic Reed-Solomon Codes . 13 2.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3 Proposed Method for Improvement 26 3.1 Another Polynomial Division and Simulation Results . . . . . . . . . . 26 3.2 Decoding Algorithm for Low Coding Rate Reed-Solomon Codes Using a Novel Polynomial Basis . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2.1 Syndrome for Low Coding Rate Reed-Solomon Codes . . . . . 32 3.2.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . 36 4 A Puncturing Scheme for Reed-Solomon Codes Using a Novel Polynomial Basis 40 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2 Proposed Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5 Conclusions and Future Research 44 5.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.2 Future Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Bibliography 46 | |
dc.language.iso | en | |
dc.title | 可利用快速傅立葉轉換運算的里德所羅門碼之一些研究成果 | zh_TW |
dc.title | Some Results on Reed-Solomon Codes Using Fast Fourier Transforms | en |
dc.type | Thesis | |
dc.date.schoolyear | 107-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 韓永祥(Yung-Hsiang Han),翁詠祿(Yung-Lu Ueng),唐宏驊(Hung-Hua Tang) | |
dc.subject.keyword | 有限場,里德-所羅門碼,快速傅立葉轉換,截短, | zh_TW |
dc.subject.keyword | Finite field,Reed-Solomon codes,Fast Fourier transform,Puncturing, | en |
dc.relation.page | 48 | |
dc.identifier.doi | 10.6342/NTU201901382 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2019-07-11 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電信工程學研究所 | zh_TW |
顯示於系所單位: | 電信工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-108-1.pdf 目前未授權公開取用 | 2.24 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。