Reed-Muller descriptions of symmetric functions
Jose Maria Quintana, M.J. Avedillo · 2002
Boolean functions can be expressed by using AND and XOR (Exclusive-OR) operators in what is known as the Reed-Muller (RM) expansion of the function. Important functions such as parity, adders, gray code generators and so on have a very simple form under this representation. Transformation between the operational domain (the truth table) and the function domain (the coefficients of the RM expansion) is usually done by a transformation matrix which has a dimension of 2/sup n//spl times/2/sup n/ for an n-input binary switching function. This paper presents an algebraic result which allows us to obtain Reed-Muller descriptions for the class of switching functions which are invariant under any permutation of their variables, i.e., for symmetric functions. The main characteristic of the new result is the great reduction in the dimension of the transformation matrix which falls from 2/sup n//spl times/2/sup n/ to (n+1)/spl times/(n+1).