The Discrete Fourier Transform Over the Binary Finite Field

Abstract

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

• Binary codes
• decoding
• discrete Fourier transforms
• fast Fourier transforms
• Galois fields