The reed-muller-fourier transform—computing methods and factorizations

Abstract

Reed-Muller (RM) expressions are an important class of functional expressions for binary valued (Boolean) functions which have a double interpretation, as analogues to both Taylor series or Fourier series in classical mathematical analysis. In matrix notation, the set of basic functions in terms of which they are defined can be represented by a binary triangular matrix. Reed-Muller-Fourier (RMF) expressions are a generalisation of RM expressions to multiple valued functions preserving properties of RM expressions including the triangular structure of the transform matrix. In this paper, we discuss different methods for computing RMF coefficients over different data structure efficiently in terms of space and time. In particular, we consider algorithms. corresponding to Cooley-Tukey and constant geometry algorithms for Fast Fourier transform. We also consider algorithms based on various decompositions borrowed from the decomposition of the Pascal matrix and related computing algorithms.