A novel method for computation of the discrete Fourier transform over characteristic two finite field of even extension degree

Preprint English OPEN
Fedorenko, Sergei V. (2011)

A novel method for computation of the discrete Fourier transform over a finite field with reduced multiplicative complexity is described. If the number of multiplications is to be minimized, then the novel method for the finite field of even extension degree is the best known method of the discrete Fourier transform computation. A constructive method of constructing for a cyclic convolution over a finite field is introduced.
  • References (18)
    18 references, page 1 of 2

    [4] R. E. Blahut, Theory and Practice of Error Control Codes. Reading, MA: Addison-Wesley, 1983.

    [5] R. E. Blahut, Fast Algorithms for Digital Signal Processing. Reading, MA: Addison-Wesley, 1985.

    [6] R. E. Blahut, Fast Algorithms for Signal Processing. Cambridge, U.K.: Cambridge University Press, 2010.

    [7] N. Chen and Z. Yan. Cyclotomic FFTs with reduced additive complexities based on a novel common subexpression elimination algorithm. IEEE Transactions on Signal Processing, vol. 57, no. 3, pp. 1010-1020, 2009.

    [8] E. Costa, S. V. Fedorenko, and P. V. Trifonov. On computing the syndrome polynomial in Reed-Solomon decoder. European Transactions on Telecommunications, vol. 15, no. 3, pp. 337-342, 2004.

    [9] S. Fedorenko and P. Trifonov. On computing the fast Fourier transform over finite fields. Proceedings of Eighth International Workshop on Algebraic and Combinatorial Coding Theory at Tsarskoe Selo, Russia, pp. 108-111, September 2002.

    [10] S. V. Fedorenko. A method for computation of the discrete Fourier transform over a finite field. Problems of Information Transmission, vol. 42, no. 2, pp. 139-151, 2006. Translation of Problemy Peredachi Informatsii.

    [11] S. V. Fedorenko, Fast algorithms for decoding of linear block codes. St.Petersburg: GUAP, 2008. In Russian.

    [12] S. V. Fedorenko. On semifast Fourier transform algorithms. Proceedings of the XII international symposium on problems of redundancy in information and control systems at St.Petersburg, Russia, pp. 65-70, May 2009. [Online]. Available: http://arxiv.org/abs/0907.1975v2

    [13] S. V. Fedorenko. The discrete Fourier transform over a finite field with reduced multiplicative complexity. Proceedings of the IEEE International Symposium on Information Theory at Saint-Petersburg, Russia, pp. 1200-1204, July-August 2011.

  • Metrics
    No metrics available
Share - Bookmark