里德所羅門碼之編碼與徵狀值計算的一種改良

An Enhancement to Encoding and Syndromes Evaluation of Reed-Solomon Codes

陳健文(Chien-Wen Chen)

指導教授 ： 張肇健

共同指導教授 ： 陳延華(Yan-Haw Chen)

義守大學/電機資訊學院/資訊工程學系/博士(2014年)

https://doi.org/10.6343/ISU.2014.00306

摘要

本論文提出一種運用於里德所羅門碼編碼器上以進行高傳輸率通道編碼的演算法。基於范德蒙矩陣與多項式計算，本演算法是可進行訊息多項式計算的高效率查表法。由本演算法所導出的查值表不僅適用於里德所羅門碼的編碼器也能運用在解碼時的徵狀值計算。與Horner法則比較起來，運用本演算法可讓用於計算訊息多項式值的查表操作時間縮短三倍。這將使運用線性反饋移位暫存器計算的(204,188,t=8)里德所羅門碼之編碼工作減少50%的時間。本演算法也可用於計算里德所羅門碼解碼器中所需的徵狀值，讓整體解碼速度比單純運用Horner法則的演算法更快。最後，所提之演算法可讓里德所羅門碼之編碼與徵狀值之計算更加一般化及簡單化，而且適合透過軟體來實現。

關鍵字

里德所羅門碼 ； 編碼 ； 徵狀值 ； 查值表

並列摘要

An efficient lookup table algorithm for computing the values of message polynomials during high throughput encoding of Reed-Solomon (RS) codes is presented in this dissertation. The algorithm can be applied to RS encoders, which are based on Vandermonde matrix and the polynomial computations. The lookup table derived from the algorithm can then be applied not only to an encoder of RS codes but also to syndromes evaluation in the decoding of RS codes. By comparing with the Horner’s rule, one of advantages of utilizing this algorithm is that the table lookup operations for computing the values of the message polynomials are reduced by a factor of three. It would reduce the encoding time by fifty-percent using the linear feedback shift register (LFSR) to encode the (204,188,t=8) RS code. The algorithm can also be used to evaluate the syndromes needed in the RS decoder, and thus the speed is much faster than Horner’s rule. As a consequence, the proposed encoding and syndromes evaluation for RS codes can be made regular, simple, and suitable for software implementations.

並列關鍵字

Reed-Solomon Codes ； Encoding ； Syndrome ； Lookup Table

參考文獻

[1] Albertengo, G. and Sisto, R. 1990. “Parallel CRC Generation.” IEEE Micro 10 (5): 63-71. doi: 10.1109/40.60527.

[2] Berlekamp, E. R., Rumsey, H., and Solomon, G. 1967. “On the Solution of Algebraic Equations over Finite Fields.” Information Control 10 (6): 553-564. doi: 10.1016/S0019-9958(67)91016-9.

[3] Blahut, R. E. 1979. “Transform Techniques for Error Control Codes.” IBM Journal of Research and Development 23 (3): 299-315. doi: 10.1147/rd.233.0299.

[5] Costa, E., Fedorenko, S. V., and Trifonov P.V. 2004. “On Computing the Syndrome Polynomial in Reed–Solomon Decoder.” European Transactions on Telecommunications 15 (4): 337–342. doi: 10.1002/ett.982.

[6] Eisinberg, A. and Fedele, G. 2006. “On the Inversion of the Vandermonde Matrix.” Applied Mathematics and Computation 174 (2): 1384-1397. doi: 10.1016/j.amc.2005.06.014.