An Algebraic Approach to Reducing the Number of Variables of Incompletely Defined Discrete Functions

• Main Authors: Astola, Jaakko T., Astola, Pekka, Stankovic, Radomir S., Tabus, Ioan
• Format: Conference Proceeding
• Language: English
• Subjects: Algebra; Boolean algebra; Construction; Correlation; Discrete functions; Electronic mail; Frequency modulation; Image recognition; index generation functions; Indexes; Logic; Mathematical analysis; multiple valued functions; reduction of variables; Ring structures; Structural rings; Transforms
• ISSN: 2378-2226
• DOI: 10.1109/ISMVL.2016.18

In this paper, we consider incompletely defined discrete functions, i.e., Boolean and multiple-valued functions, f:S→{0,1,...,q-1} where S ⊆ {0,1,...,q-1} n i.e.,the function value is specified only on a certain subset S of the domain of the corresponding completely defined function. We assume the function to be sparse i.e. |S| is 'small' relative to the cardinality of the domain. We show that by embedding the domain {0,1,...,q-1} n , where n is the number of variables and q is a prime power, in a suitable ring structure, the multiplicative structure of the ring can be used to construct a linear function {0,1,...,q-1} n {0,1,...,q-1} m that is injective on S provided that m > 2log q |S| + log q (n - 1). In this way we find a linear transform that reduces the number of variables from n to m, and can be used e.g. in implementation of an incompletely defined discrete function by using linear decomposition.