The discrete Fourier transform over a finite field finds applications in algebraic coding theory. A novel method for computation of the discrete Fourier transform over a finite field with reduced multiplicative complexity is described.
For the DFT computation in the field GF(2^m) for even m, the exact formula for the number of multiplications is analytically obtained.
Prof. Sergei Fedorenko, Saint-Petersburg State University of Aerospace Instrumentation, is currently visiting us as a guest scientist of Alexander von Humboldt Stiftung.
The main results of Prof. Fedorenko belong to a very important part of communication theory: channel coding.
Prof. Fedorenko has given the simple derivation, the proof, and the complexity analysis of the Shiozaki-Gao algorithm for decoding algebraic codes (including Reed-Solomon codes), and its relation to the Welch-Berlekamp and Euclidean algorithms. The connection between known decoding algorithms demonstrated by Prof. Fedorenko has important methodological significance in coding theory. The modification of this algorithm for decoding both errors and erasures of Reed-Solomon codes are the simplest for codes with short lengths for any implementation.
Prof. Fedorenko has introduced the method for computation of the discrete Fourier transform (DFT) over a finite field. If the number of multiplications is to be minimized, then this algorithm is the best known algorithm of the DFT for small lengths (less than or equal to 511). Nowadays there are many modifications of Fedorenko's method which decrease the additive complexity of DFT.
Prof. Fedorenko has invented the method for finding roots of polynomials over finite fields. This algorithm for evaluation of arbitrary polynomials at many points of the finite field has significantly better performance than well-known methods. This method makes possible significant speed up of the decoding process of Bose-Chaudhuri-Hocquenghem (BCH), Reed-Solomon and some other error-correcting codes. One of modifications of this method is patented.