Reed-Muller Representation of Symmetric Functions
Ekaterina Pogossova and Karen Egiazarian
Reed-Muller expressions have been known since 1927. Due to their good testability properties and the possibility of efficient realization, these expressions have found wide application in logic design. This paper presents a method of reduced transform to Reed-Muller domain for symmetric functions. The method is developed for Boolean and the simplest case of multi-valued, namely, the ternary logic functions. The transformation complexity O(nlog2 (n + 1)) in the Boolean and O(n3) in the ternary case is achieved. The proposed technique is extended to the functions defined in generalized Fibonacci cubes.