General information
Latest issue
Impact factor
Guidelines for authors

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Probl. Peredachi Inf.:

Personal entry:
Save password
Forgotten password?

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
\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
\jour Problems Inform. Transmission
\yr 2003
\vol 39
\issue 3
\pages 231--238

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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  crossref  isi
    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  crossref  mathscinet  zmath  isi  elib
    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  mathnet  crossref  mathscinet
    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  crossref  mathscinet  zmath  isi  elib
    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  crossref  isi
    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  isi
    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  crossref  adsnasa  isi
    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  crossref  isi
    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  crossref  isi
    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  crossref  isi
    11. Chen Ning, Yan Zhiyuan, “Reduced-complexity Reed-Solomon decoders based on cyclotomic FFTs”, IEEE Signal Processing Letters, 16:4 (2009), 279–282  crossref  adsnasa  isi  elib
    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  crossref  mathscinet  adsnasa  isi
    13. Gao Sh., Mateer T., “Additive Fast Fourier Transforms Over Finite Fields”, IEEE Trans Inform Theory, 56:12 (2010), 6265–6272  crossref  mathscinet  isi  elib
    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  crossref  mathscinet  adsnasa  isi
    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  isi
    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  crossref  isi
    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  crossref  mathscinet  isi
    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  crossref  isi
    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  crossref  isi
    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  crossref  mathscinet  adsnasa  isi
    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  crossref  mathscinet  adsnasa  isi  elib
    22. Bellini S., Ferrari M., Tomasoni A., “On the Reduction of Additive Complexity of Cyclotomic Ffts”, IEEE Trans. Commun., 60:6 (2012), 1465–1468  crossref  isi  elib
    23. Trifonov P., “On the Additive Complexity of the Cyclotomic Fft Algorithm”, 2012 IEEE Information Theory Workshop (Itw), IEEE, 2012, 537–541  crossref  isi
    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  mathnet  crossref  crossref  mathscinet  elib  elib
    25. Mateer T.D., “Simple Algorithms for Decoding Systematic Reed-Solomon Codes”, Des. Codes Cryptogr., 69:1 (2013), 107–121  crossref  mathscinet  zmath  isi  elib
    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  crossref  isi
    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  isi
    28. Fedorenko S.V., “Normalized Cyclic Convolution: the Case of Even Length”, IEEE Trans. Signal Process., 63:20 (2015), 5307–5317  crossref  mathscinet  isi  elib
    29. Trifonov P., “Low-Complexity Implementation of Raid Based on Reed-Solomon Codes”, ACM Trans. Storage, 11:1 (2015), 1  crossref  isi  elib
    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  isi
    31. Samanta J., Bhaumik J., Barman S., “Fpga Based Area Efficient Rs(23,17) Codec”, Microsyst. Technol., 23:3, SI (2017), 639–650  crossref  isi  scopus
    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  crossref  isi  scopus
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:854
    Full text:262

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020