LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Fedorenko, Sergei V. (2011)
Languages: English
Types: Preprint
Subjects: Computer Science - Information Theory
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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [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.
    • [14] J. von zur Gathen and J. Gerhard, Modern computer algebra. Cambridge, U.K.: Cambridge University Press, 1999.
    • [15] G. Goertzel. An Algorithm for the Evaluation of Finite Trigonometric Series. The American Mathematical Monthly, vol. 65, no. 1, pp. 34-35, January 1958.
    • [16] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. Amsterdam-New York-Oxford: North-Holland Publishing Company, 1977.
    • [17] E. H. Moore. A two-fold generalization of Fermat's theorem. Bulletin of the American Mathematical Society, vol. 2, no. 7, pp. 189-199, 1896.
    • [18] P. V. Trifonov and S. V. Fedorenko. A method for fast computation of the Fourier transform over a finite field. Problems of Information Transmission, vol. 39, no. 3, pp. 231-238, 2003. Translation of Problemy Peredachi Informatsii.
    • [19] P. Trifonov, private communication.
    • [20] P. Trifonov. Matrix-vector multiplication via erasure decoding. Proceedings of the XI international symposium on problems of redundancy in information and control systems at St.Petersburg, Russia, pp. 104-108, July 2007.
    • [21] X. Wu, M. Wagh, N. Chen, Y. Wang, and Z. Yan. Composite cyclotomic Fourier transforms with reduced complexities. IEEE Transactions on Signal Processing, vol. 59, no. 5, pp. 2136-2145, 2011.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article

Collected from