A general construction of Reed-Solomon codes based on generalized discrete Fourier transform

Document Type : Research Paper


Department of mathematical sciences, University of Kashan, Kashan, Isfahan, Iran.


In this paper, we employ the concept of the Generalized Discrete Fourier Transform, which in turn relies on the Hasse derivative of polynomials, to give a general construction of Reed-Solomon codes over Galois fields of characteristic not necessarily co-prime with the length of the code. The constructed linear codes  enjoy nice algebraic properties just as the classic one.


[1] R. E. Blahut, Algebraic codes for data transmission, Cambridge University Press, Cambridge, 2003.
[2] S. Gao, A new algorithm for decoding Reed-Solomon codes, Communications, Information and Network
Security, edited by V. K. Bhargava, H. V. Poor, V. Tarokh and Yoon Seokho, Kluwer (2002) 55-68.
[3] V. Guruswami, List decoding of error-correcting codes, Lecture notes in computer science, Springer, 2004.
[4] J. Justesen, On the complexity of decoding Reed-Solomon codes, IEEE Trans. Inform. Theory 22 (1976),
[5] R. Lidl and H. Niederreiter, Finite Fields, Cambridge University Press, Cambridge, 1997.
[6] J. L. Massey and S. Serconek, Linear complexity of peridic sequences: A general theory, Advances in
Cryptology-CRYPTO' 96, edited by N. Koblitz, Kluwer (1996), 358-371.
[7] G. Quintin, M. Barbier and C. Chabot, On generalized Reed-Solomon codes over commutative and non-
commutative rings, IEEE Trans. Inform. Theory 59(9) (2013), 5882-5897.
[8] I. S. Reed and G. Solomon, Polynomial codes over certain nite elds, J. Soc. Ind. Appl. Math. 8(2) (1960),
[9] A. Shokrollahi, A class of generalized RS-codes with faster encoding and decoding algorithms, ITA (2013),
[10] M. Sudan, Decoding of Reed-Solomon codes beyond the error-correction diameter, Proceedings of the 35th Annual Allerton Conference on Communication, Control and Computing, University of Illions at Urbana-
Champaign (1997), 215-224.
[11] S. B. Wicker and V. K. Bhargava, Reed-Solomon codes and their applications, IEEE Press, 1994.