臺灣博碩士論文加值系統

這項研究提出一種排序統計解碼的簡化方式，以作為Reed-Solomon碼使用QAM訊號在加法性高斯通道之解碼使用。此種所研提之方式使用抹去式解碼，取代原排序統計解碼中生成過程。在解碼複雜度之考量下，抹去式解碼方式使用週遭四點取代原點之方式。以(15,9,7) RS為例，模擬結果顯示order-1的排序統計解碼可提供1 dB的編碼增益，然而full-order的排序統計解碼提供2 dB的編碼增益，但卻花費非常大的運算量。由此證明，本研究所研提之方式是可行又易實現。

This work presents a simple way of ordered statistic decoding (OSD) to decode Reed-Solomon codes with QAM signaling over additive white Gaussian channels. In such a way, there is a proposed erasure decoding employed in decoding instead of re-encoding process in OSD. Under consideration of decoding complexity, four nearest neighbors are used to replace each symbol in an erasure sequence during proposed decoding. Simulation results of (15,9,7) RS code show that order-1 OSD with proposed simple way can provide 1 dB coding gain, while full-order OSD only supports 2 dB coding gain but with lots of complexity. From those comparisons of complexity, this proposed simple way in OSD is achievable and easily implemented.

封面內頁
簽名頁
中文摘要............iii
ABSTRACT............iv
誌謝............v
目錄............vi
圖目錄............vii
表目錄............viii

第一章 緒論............1
1.1前言............1
1.2研究動機............2
第二章 伽羅瓦場(Galois Field)的建立與運算............5
2.1 伽羅瓦場(Galois Field)元素的建立與基本運算............5
2.2.1伽羅瓦場(Galois Field)基本運算............8
第三章 Reed-Solomon編碼演算法則............10
3.1 生成多項式............10
3.2 Reed-Solomon編碼演算法則............10
3.3 Reed-Solomon解碼演算法............12
第四章 以抹去式解碼過程為基礎之排序統計解碼演算法............15
4.1 排序統計解碼[13][14]............16
4.2 抹去式解碼過程為基礎之排序統計解碼演算法............18
4.2.1 抹去式解碼演算法............19
4.2.2排序統計解碼的簡單搜尋............25
4.3 解碼成效結果和比較............26
4.4 小結............27
第五章 有理函數化Reed-Solomon碼之解碼演算法............29
5.1 概論............30
5.2有理函數和類RS碼生成多項式的連接方法............34
5.3 解碼演算法之研擬............36
5.4 解碼過程比較............41
5.5 小結............45
參考文獻............46


圖目錄

圖1.1 通訊系統方塊圖............3
圖1.2 傳輸與儲存系統............3
圖4.1 使用16QAM訊號............26
圖4.2 使用QAM訊號，取最近4點作為抹去解碼過程所需修改之處............ 26
圖4.3 使用16QAM訊號的(15,9,7)RS碼改錯性能比較............28


 
表目錄

表 2.1 場元素之三種表示方式............6
表 3.1 碼字多項式............11
表 3.2 Reed-Solomon碼參數............11
表3.2 Berlekamp-Massey疊代運算的初始化............13
表4.1 OSD的生成碼字和本文所提出方式之複雜度比較............22
表4.2 以QAM訊號傳送，RS解碼過程使用本文提出演算法比OSD擁有較小複雜度的最低碼率............22
表5.2 研擬之匹配方式............35
表5.3 匹配生成多項的根和冪級數展開式零點............36
表5.4 BIA解碼過程............40
表5.5 EEA解碼過程(5.10)............40
表5.6 BIA解碼的假設過程............41
表5.7 EEA解碼的假設過程............42
表5.8 BIA解碼過程的錯誤定位和錯誤值估算多項式所需之複雜度，以場元素乘法和加法表示............42
表5.9 EEA解碼過程的錯誤定位和錯誤值估算多項式所需之複雜度，以場元素乘法和加法表示............43
表5.10解碼複雜度之比較:使用場加法和乘法之數量............43
表5.11 RS(255,239,t=8)碼解碼的BIA和EEA的複雜度比較............44

參考文獻

[1]Lin, Shu and Costello, Daniel J. Jr., Error Control Coding, Prentice hall, 2nd edition, pp.235-269, 2004.
[2]Wicker, Stephen B., Error Control Systems for Digital Communication and Storage, Prentice hall, pp.204-233, 1995.
[3]Peterson, W. W. and Weldon, E. J., Error-Control Codes, MIT press, Cambridge, 2nd edition, pp.269-299, 1972.
[4]Massy, J. L,“Step-by-Step Decoding of Bose-Chauhuri-Hocquenghem Codes,”IEEE Trans. Inform. Theory, Vol. 11, No. 4, pp.580-585, 1965.
[5]Wei, S. –W. and Wei, C-H.“High-Speed Decoder of Reed-Solomon Codes,” IEEE Trans. Commun, Vol. 41, No. 11, pp.1588-1593, 1993.
[6]Chen, T. –C., Wei, C.-H. and Wei ,S.-W.,“Step-by-Step Decoding Algorithm for Reed-Solomon Codes,”IEEE Proc.-Commun., Vol. 147, No. 1, pp.8-12, 2000.
[7]Masakatu ,M., and Masao, K.,“Generalized Key-Equation of Remainder Decoding Algorithm for Reed-Solomon Codes,”IEEE Trans. Inform. Theory, Vol.38, No.6, pp. 1801-1807, 1992.
[8]Fedorenko, S. V.,“A simple algorithm for decoding Reed-Solomon codes and its relation to the Welch-Berlekamp algorithm,”IEEE Trans. Inform. Theory, Vol.51, No.3, pp.1196-1198, 2005.
[9]Guruswami, V., and Sudan, M.,“Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes,”IEEE Trans. Inform. Theory, Vol. 45, NO.6, pp.1757-1767, 1999.
[10]Koetter, R., and Vardy, A.,“Algebraic Soft-Decision Decoding of Reed-Solomon Codes,”IEEE Trans. Inform. Theory, Vol.49, No.11, pp.2809-2825, 2003.
[11]Forney, G. D.,“Generalized Minimum Distance Decoding,”IEEE Trans. Inform. Theory, Vol.12, No 2, pp.125-131, 1966.
[12]Vardy, A., and Yair, B.,“Bit-level Soft Decision Decoding of Reed-Solomon Codes,”IEEE Trans. Commun., Vol.39, No.3, pp.440-444, March 1991.
[13]Hu, T. H., and Lin, S.,“An Efficient Hybrid Decoding Algorithm of Reed-Solomon Codes Based on Bit Reliability,”IEEE Trans. Commun., Vol.51, No.7, pp.1073-1081, 2003.
[14]Fossorier, M. P. C. and Lin, S.,“Soft-Decision Decoding of Linear Bock Codes Based on Ordered Statistic Algorithm,”IEEE Trans. Inform. Theory, Vol.41, No.5, pp.1379-1396, 1995.
[15]Wenyi, J., and Fossorier, M.P.C.“Reliability-Based Soft-Decision Decoding With Multiple Biases,”IEEE Transactions on Information Theory, Vol.53, No.1, pp.105-120, 2007.
[16]Fabian, Lim, and Kavˇci´c Aleksandar; Fossorier, M. P. C.,“List Decoding Techniques for Intersymbol Interference Channels Using Ordered Statistics,”IEEE Selected Areas Commun. Vol.28, No.2, pp.241-251, 2010.
[17]Alnawayseh, S. E. A. and Loskot, p.,“Complexity Reduction of Ordered Statistics Decoding Using Side Information,＂IEEE Commun. Letters, Vol.16, No. 2, pp. 249-251, 2012.
[18]Wenyi, J., and Fossorier, M. P. C.,“Towards Maximum Likelihood Soft Decision Decoding of the (255,239) Reed Solomon Code,＂IEEE Transactions on Magnetics, Vol.44, No.3, pp.423-428, 2008.
[19]Kothiyal,A., and Takeshita,O.Y., and Wenyi,J., and Fossorier. M. P. C.,“Iterative reliability-based decoding of linear block codes with adaptive belief propagation,” IEEE Commun. Letters, Vol.9, No. 12, pp. 1067-1069, 2005.
[20]E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968.
[21]A. Zeh, A. Wachter, and S. Bezzateev, "Efficient decoding of some classes of binary cyclic code beyond the Hartmann-Tzeng bound," Information Theory Proceedings (ISIT), 2011 IEEE International Symposium, pp. 1017-1021, Aug 2011.
[22]A. Zeh, A. Wachter, and S. Bezzateev, "Decoding Cyclic Codes up to a New Bound on the Minimum Distance," IEEE transactions on information theory, Vol. 58, No.6, pp.3951-3960, 2012.
[23]Jacobus H. Van Lint, Richard M.Wilson, "On the minium Distance of Cyclic Codes, " IEEE transactions on information theory, Vol. IT-32, No.1, pp.23-40, Jan 1986.
[24]Gui-Liang Feng and Kenneth K. Tzeng, "A Generalization of the Berlekamp-Massey Algorithm for Multisequence Shift-Register Synthesis with Applications to Decoding Cyclic Codes," IEEE transactions on information theory, Vol. 37, No.5, pp.1274-1287, Sep 1991.
[25]Nadia Ben Atti, Gema M. Diaz-Toca, and Henri Lombardi, "The Berlekamp-Massey Algorithm revisited," Journal Applicable Algebra in Engineering, Communication and Computing, Vol. 17, pp. 75-82, Apr 2006.
[26]Jean Louis Dornstetter, "On the Equivalence Between Berlekamp’s and Euclid’s Algorithms," IEEE transactions on information theory, Vol. 33, No.3, pp. 428-431, 1987.
[27]Ulrich K. Sorger, "A New Reed-Solomon Code Decoding Algorithm Based on Newton’s Interpolation," IEEE transactions on information theory, Vol. 39, No.2, pp. 358-365, Mar 1993.
[28]C. R. P. Hartmann and K.K. Tzeng, "Decoding Beyond the BCH Bound Using Multiple Sets of Syndrome Sequences," IEEE transactions on information theory, Vol. 20, No.2, pp. 292-295, Mar 1974.
[29]G. D. Forney, "On Decoding BCH Codes, " IEEE transactions on information theory, Vol. 11, No.4, pp. 549-557, Oct 1965.
[30]C. Roos, "A generalization of the BCH bound for cyclic codes, including the Hartmann-Tzeng bound," Journal of Combinatorial Theory, Series A, Vol. 33, No.2, pp. 229-232, Sep 1982.
[31]J. L. Massey, "Shit-register synthesis and BCH decoding," IEEE transactions on information theory, Vol. IT-15, No.1, pp. 122-127, Jan 1969.
[32]C. R. P. Hartmann and K.K. Tzeng, "Generalization of the BCH bound," Inform. Contr., Vol. 20, No.5, pp. 489-498, June 1972.
[33]R. E. Blahut, Theory and Practice of Error Control Codes, Reading, MA: Addison-Wesley, 1983.
[34]R. M. Roth, "Efficient Decoding of Reed-Solomon Codes Beyond Half the Minimum Distance," IEEE transactions on information theory, Vol. 46, No.1, pp. 246-257, Jan. 2000.
[35]A. E. Heydtmann and J. M. Jensen, " On the Equivalence of the Berlekamp–Massey and the Euclidean Algorithms for Decoding," IEEE transactions on information theory, Vol. 46, No.7, pp. 2614-2624, Nov. 2000.