The discrete Fourier transform over the binary finite field

IEEE Access. 2023. Vol. 11. P. 62771–62779.

Sergei Valentinovich Fedorenko

The novel methods for binary discrete Fourier transform (DFT) computation over the finite field have been proposed. The methods are based on a binary trace calculation over the finite field and use the cyclotomic DFT. The direct DFT computational complexity has been reduced due to using the binary trace function over the finite field and the functions of trace which are stored in small tables. The computational complexity of the inverse DFT has been reduced due to representation of elements in the finite field with respect to the normal basis. The proposed methods can be used for encoding/decoding subfield subcodes, especially for binary Bose–Chaudhuri–Hocquenghem (BCH) codes. The computational complexity of the direct/inverse DFT computation methods is the smallest of all known methods.

Keywords: декодирование, Сложность вычислений, decoding, Computational Complexity, быстрое дискретное преобразование Фурье, trace, след, decoding algorithm, алгоритм декодирования, error correction codes, discrete Fourier transforms, Fast Fourier transforms, decoding complexity, коды, исправляющие ошибки, конечные поля, discrete Fourier transforms over finite fields, BCH codes, дискретное преобразование Фурье, Galois fields, БЧХ коды, cyclotomic DFT, циклотомический алгоритм

Publication based on the results of: Исследование и разработка методов множественного доступа и помехоустойчивого кодирования для организации энергоэффективной передачи данных в системах Интернета вещей (2023)