Abstract
This paper discusses reduction of the number of product terms in representation of totally symmetric Boolean functions by Sum of Products (SOP) and Fixed Polarity Reed- Muller (FPRM) expansions. The suggested method reduces the number of product terms, correspondingly, the implementation cost of symmetric functions based on these expressions by exploiting Gray decoding of input variables. Although this decoding is a particular example of all possible linear transformation of Boolean variables, it is efficient in the case of symmetric functions since it provides a significant simplification of SOPs and FPRMs. Mathematical analysis as well as experimental results demonstrate the efficiency of the proposed method. Index Terms—Symmetric function, Gray code, linear transformation, autocorrelation.
I. INTRODUCTION
Linearization of switching functions based on linear transformation of variables is a classical method of optimization in circuit synthesis originating already in 1958 [22]. It has been recently efficiently exploited by several authors and discussed for different aspects due to its : 1) Effectiveness. When properly performed, the method provides considerable savings in complexity of the representation of functions with respect to different optimization criteria. 2) Simplicity of the implementation. The overhead comprises EXOR circuits required to perform the selected linear combination of variables. The overhead is usually quite negligible compared to the overall complexity of the implementation [12]. The linearization can be performed over different data structures used to represent functions. For example, it has been performed over Sum-of-Product (SOP) expressions [10], [13], [15], [28], AND-EXOR expressions [5], word-level expressions [27] as well as decision diagrams [7], [14], [18]. In spectral techniques, this method is studied as a mean to reduce the number of non-zero coefficients in spectral expressions for discrete functions [8], [12]. In [12], [20], and [21] the extensions to multiple-valued logic functions are discussed. The complexity of determining an optimal non-singular binary matrix that defines the optimal linear transformation of variables is NP-complete. For this reason different strategies have been suggested in exploiting this method. In searching for exact optimum, some restrictions should to be made on the number of variables in functions processed. For example, it has been reported in [7] that the complete This work was supported by BSF under grant 2002259 search over all possible linear transformations is feasible for functions up to seven variables within reasonable space and time resources. Another approach is to restrict considerations to particular classes of functions. For instance, in [10], [27] a method has been used for specific circuits, such as n-bit adders and an optimal linear transform has been found. Alternatively, nearly optimal solutions can be provided by deterministic algorithms if analysis of additional information about the functions can be provided. In this direction, research has been reported by analyzing besides the functions their Walsh coefficients and autocorrelation coefficients, see, for instance, [8], [12] and [14] and references therein. In this paper, we discuss a compromising approach. We show that when the class of functions is the totally symmetric Boolean functions, then an efficient linear transformation of variables can be determined analytically, it reduces to Gray decoding of input variables. A justification to consider symmetric functions can be found in the following considerations. Symmetric Boolean functions represent an important fraction of Boolean functions. There are 2n+1 binary-valued symmetric functions out of 22n functions. There are efficient circuit-based methods and complete BDDbased methods for identifying symmetries of completely and incompletely specified functions [11], [17], [19], [23], [29], [32]. In last several years, symmetric functions have been studied from different aspects. Optimal Fixed Polarity Reed-Muller (FPRM) expansions for totally symmetric functions are discussed in [4], [31] and references therein. A lower bound on the number of gates in conjunctive (disjunctive) normal form representation of symmetric Boolean functions is given in [30] and a method for generating a minimal SOP cover is presented in [3]. A multilevel synthesis of symmetric functions which exploits the disjoint decomposability and weight dependency of the functions is presented in [16] and a mapping of symmetric and partially symmetric functions to the CA-type FGPAs was suggested in [2]. A new expansion of symmetric functions and their application to non-disjoint functional decompositions for LUT-type FPGAs is presented in [25]. In this paper we show that the Gray decoding of the input variables almost always reduces the complexity in terms of the above three measures: the number of gates in two-level realization, the number of FPRM terms and the number of FPGA LUTs.


Download full report
http://googleurl?sa=t&source=web&cd=2&ve...y-Symm.pdf&ei=JCdTTqjoJ4XrrQfo66XkDg&usg=AFQjCNGDBWyujAl-nPODdZgHAuutu2BrjA