RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Guidelines for authors Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Probl. Peredachi Inf.: Year: Volume: Issue: Page: Find

 Personal entry: Login: Password: Save password Enter Forgotten password? Register

 Probl. Peredachi Inf., 2003, Volume 39, Issue 3, Pages 3–10 (Mi ppi304)

This article is cited in 32 scientific papers (total in 32 papers)

Information Theory and Coding Theory

Method for the Fast Fourier Transform Evaluation over a Finite Field

P. V. Trifonov, S. V. Fedorenko

Saint-Petersburg State Polytechnical University

Abstract: We consider the problem of fast computation of the Fourier transform over a finite field by decomposing an arbitrary polynomial into a sum of linearized polynomials. Examples of algorithms for the Fourier transform with complexity less than that of the best known analogs are given.

Full text: PDF file (682 kB)
References: PDF file   HTML file

English version:
Problems of Information Transmission, 2003, 39:3, 231–238

Bibliographic databases:

UDC: 621.391.1:681.3
Received: 25.10.2002
Revised: 05.02.2003

Citation: P. V. Trifonov, S. V. Fedorenko, “Method for the Fast Fourier Transform Evaluation over a Finite Field”, Probl. Peredachi Inf., 39:3 (2003), 3–10; Problems Inform. Transmission, 39:3 (2003), 231–238

Citation in format AMSBIB
\Bibitem{TriFed03} \by P.~V.~Trifonov, S.~V.~Fedorenko \paper Method for the Fast Fourier Transform Evaluation over a Finite Field \jour Probl. Peredachi Inf. \yr 2003 \vol 39 \issue 3 \pages 3--10 \mathnet{http://mi.mathnet.ru/ppi304} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2099858} \zmath{https://zbmath.org/?q=an:1074.65157} \transl \jour Problems Inform. Transmission \yr 2003 \vol 39 \issue 3 \pages 231--238 \crossref{https://doi.org/10.1023/A:1026171930630} 

Linking options:
• http://mi.mathnet.ru/eng/ppi304
• http://mi.mathnet.ru/eng/ppi/v39/i3/p3

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Costa E., Fedorenko S.V., Trifonov P.V., “On computing the syndrome polynomial in Reed-Solomon decoder”, European Transactions on Telecommunications, 15:4 (2004), 337–342
2. Fedorenko S.V., “A simple algorithm for decoding Reed-Solomon codes and its relation to the Welch-Berlekamp algorithm”, IEEE Trans. Inform. Theory, 51:3 (2005), 1196–1198
3. S. V. Fedorenko, “A Method for Computation of the Discrete Fourier Transform over a Finite Field”, Problems Inform. Transmission, 42:2 (2006), 139–151
4. Truong T.K., Chen P.D., Wang L.J., Chang Y., Reed I.S., “Fast, prime factor, discrete Fourier transform algorithms over $\mathrm{GF}(2^m)$ for $8\le m\le10$”, Inform. Sci., 176:1 (2006), 1–26
5. Lin Tsung-Ching, Truong T.K., Chen P.D., “A fast algorithm for the syndrome calculation in algebraic decoding of reed-solomon codes”, IEEE Transactions on Communications, 55:12 (2007), 2240–2244
6. Lin T.C., Chen P.D., Truong T.K., “Simplified procedure for decoding Reed-Solomon codes using Euclid's algorithm and the fast Fourier transform over GF(2(m))”, Tencon 2007 - 2007 IEEE Region 10 Conference, Tencon-IEEE Region 10 Conference Proceedings, 2007, 753–756
7. Chen N., Yan Zh., “Complexity analysis of the GAO algorithm”, 2007 IEEE Workshop on Signal Processing Systems, IEEE Workshop on Signal Processing Systems, 2007, 243–248
8. Chen N., Yan Zh., “Reduced-complexity cyclotomic FFT and its application to Reed-Solomon decoding”, 2007 IEEE Workshop on Signal Processing Systems, IEEE Workshop on Signal Processing Systems, 2007, 657–662
9. Al Ghouwayel A., Louet Y., Nafkha A., Palicot J., “On the FPGA implementation of the Fourier transform over finite fields GF(2(m))”, 2007 International Symposium on Communications and Information Technologies, 2007, 146–151
10. Lin Tsung-Ching, Chen Pe-Din, Truong Trieu-Kien, “Simplified procedure for decoding nonsystematic Reed-Solomon codes over $gf(2^m)$ using Euclid's algorithm and the fast Fourier transform”, IEEE Transactions on Communications, 57:6 (2009), 1588–1592
11. Chen Ning, Yan Zhiyuan, “Reduced-complexity Reed-Solomon decoders based on cyclotomic FFTs”, IEEE Signal Processing Letters, 16:4 (2009), 279–282
12. Chen Ning, Yan Zhiyuan, “Cyclotomic FFTs with reduced additive complexities based on a Novel common subexpression elimination algorithm”, IEEE Transactions on Signal Processing, 57:3 (2009), 1010–1020
13. Gao Sh., Mateer T., “Additive Fast Fourier Transforms Over Finite Fields”, IEEE Trans Inform Theory, 56:12 (2010), 6265–6272
14. Wu X., Wagh M., Chen N., Wang Y., Yan Zh., “Composite Cyclotomic Fourier Transforms With Reduced Complexities”, IEEE Transactions on Signal Processing, 59:5 (2011), 2136–2145
15. Wu X., Yan Zh., “Computational Complexity of Cyclotomic Fast Fourier Transforms Over Characteristic-2 Fields”, 2011 IEEE Workshop on Signal Processing Systems (Sips), IEEE Workshop on Signal Processing Systems, 2011, 1–6
16. Fedorenko S.V., “The discrete Fourier transform over a finite field with reduced multiplicative complexity”, 2011 IEEE International Symposium on Information Theory Proceedings (ISIT), 2011, 1200–1204
17. Bellini S., Ferrari M., Tomasoni A., “On the Structure of Cyclotomic Fourier Transforms and Their Applications to Reed-Solomon Codes”, IEEE Transactions on Communications, 59:8 (2011), 2110–2118
18. Lin Ts.-Ch., Truong T.-K., Chang H.-Ch., Lee H.-P., “A Future Simplification of Procedure for Decoding Nonsystematic Reed-Solomon Codes Using the Berlekamp-Massey Algorithm”, IEEE Transactions on Communications, 59:6 (2011), 1555–1562
19. Lin Ts.-Ch., Truong T.-K., “Decoding Nonsystematic Reed-Solomon Codes Using the Berlekamp-Massey Algorithm”, Free-Space and Atmospheric Laser Communications XI, Proceedings of SPIE, 8162, eds. Majumdar A., Davis C., SPIE-Int Soc Optical Engineering, 2011, 81620X
20. Wu X., Wang Y., Yan Zh., “On Algorithms and Complexities of Cyclotomic Fast Fourier Transforms Over Arbitrary Finite Fields”, IEEE Transactions on Signal Processing, 60:3 (2012), 1149–1158
21. Wu X. Yan Zh. Lin J., “Reduced-Complexity Decoders of Long Reed-Solomon Codes Based on Composite Cyclotomic Fourier Transforms”, IEEE Trans. Signal Process., 60:7 (2012), 3920–3925
22. Bellini S., Ferrari M., Tomasoni A., “On the Reduction of Additive Complexity of Cyclotomic Ffts”, IEEE Trans. Commun., 60:6 (2012), 1465–1468
23. Trifonov P., “On the Additive Complexity of the Cyclotomic Fft Algorithm”, 2012 IEEE Information Theory Workshop (Itw), IEEE, 2012, 537–541
24. S. B. Gashkov, I. S. Sergeev, “On complexity and depth of Boolean circuits for multiplication and inversion over finite fields of characteristic 2”, Discrete Math. Appl., 23:1 (2013), 1–37
25. Mateer T.D., “Simple Algorithms for Decoding Systematic Reed-Solomon Codes”, Des. Codes Cryptogr., 69:1 (2013), 107–121
26. Chen Ya.-H., Huang Ch.-F., Chu Sh.-I., Lien Ch.-Yu., Kao Ch.-E., “a Fast Method For Decoding Reed-Solomon Codes on Processors”, 2014 Tenth International Conference on Intelligent Information Hiding and Multimedia Signal Processing (Iih-Msp 2014), eds. Watada J., Ito A., Pan J., Chao H., Chen C., IEEE, 2014, 293–296
27. Deshmukh T.P., Dewalkar V.P., “the Design Approach For Fast Computation of Fourier Transform Over a Finite Field”, 2014 International Conference on Green Computing Communication and Electrical Engineering (Icgccee), eds. Porkumaran K., Chinnaiyan V., IEEE, 2014
28. Fedorenko S.V., “Normalized Cyclic Convolution: the Case of Even Length”, IEEE Trans. Signal Process., 63:20 (2015), 5307–5317
29. Trifonov P., “Low-Complexity Implementation of Raid Based on Reed-Solomon Codes”, ACM Trans. Storage, 11:1 (2015), 1
30. Lin T.C., Truong T.K., Chen Y.H., Lee C.D., “a Fast Discrete Fourier Transform Algorithm Over Gf(2(8))”, International Conference on Computer Science and Environmental Engineering (Csee 2015), Destech Publications, Inc, 2015, 1269–1275
31. Samanta J., Bhaumik J., Barman S., “Fpga Based Area Efficient Rs(23,17) Codec”, Microsyst. Technol., 23:3, SI (2017), 639–650
32. Deshmukh T., Deshmukh P., Dakhole P., “Design of Common Subexpression Elimination Algorithm For Cyclotomic Fast Fourier Transform Over Gf (2(3))”, Proceedings of the International Conference on Data Engineering and Communication Technology, Icdect 2016, Vol 1, Advances in Intelligent Systems and Computing, 468, eds. Satapathy S., Bhateja V., Joshi A., Springer-Verlag Singapore Pte Ltd, 2017, 559–567
•  Number of views: This page: 854 Full text: 262 References: 43

 Contact us: math-net2020_02 [at] mi-ras ru Terms of Use Registration Logotypes © Steklov Mathematical Institute RAS, 2020