Discrete Fourier Transform of Boolean Functions over the Complex Field and Its Applications
Zilong Wang, Guang Gong · IEEE Transactions on Information Theory · 2017
In this paper, the discrete Fourier transform (DFT) of Boolean functions over the complex field is introduced and the locations of zero-valued Fourier spectrum are studied. Then a Fourier spectral characterization of correlation immune and resilient Boolean functions is investigated. It is shown that a Boolean function f is mth-order correlation immune if and only if the Fourier spectrum of f under any permutation of variables (or the equivalence class of f defined by Golomb in 1959) vanishes at a specified location. This is an analog of using Walsh-Hadamard spectra to characterize correlation immunity of the Boolean functions. In particular, if f is a symmetric function, f is correlation immune if and only if its Fourier spectrum vanishes at a specified location. Similarly, zero-valued Fourier spectrum can also be used to characterize resilient functions. The application of the Fourier spectral analysis on studying the peak-to-mean envelope power ratio of the sequences is also addressed.