Generalized Reed-Muller forms as a tool to detect symmetries

TitleGeneralized Reed-Muller forms as a tool to detect symmetries
Publication TypeJournal Article
Year of Publication1996
AuthorsTsai, C-C, Marek-Sadowska, M
JournalComputers, IEEE Transactions on
Pagination33 -40
Date Publishedjan
KeywordsBoolean functions, Generalized Reed-Muller, generalized Reed-Muller forms, logic testing, MCNC benchmark, Reed-Muller codes, Reed-Muller forms, signatures, symmetric variables, symmetry
AbstractIn this paper, we present a new method for detecting groups of symmetric variables of completely specified Boolean functions. The canonical Generalized Reed-Muller (GRM) forms are used as a powerful analysis tool. To reduce the search space we have developed a set of signatures that allow us to identify quickly sets of potentially symmetric variables. Our approach allows for detecting symmetries of any number of inputs simultaneously. Totally symmetric functions can be detected very quickly. The traditional definitions of symmetry have also been extended to include more types. This extension has the advantage of grouping input variables into more classes. Experiments have been performed on MCNC benchmark cases and the results verify the efficiency of our method