On a combinatorial problem for the set of binary vectors

K. D. Kirichenko

The Bulletin of Irkutsk State University. Series Mathematics, Tome 12 (2015), pp. 49-57

Résumé

In this paper we introduce a new combinatorial problem for covering binary sets. This problem appears in connection to research of complexity of ESOP. Shannon function is called maximum from complexities of the shortest representation of each Boolean function. Hence the upper bound of the Shannon function guarantees the existence of the representation of any Boolean function with this complexity. It is important for applications. As usual implicit algorithms of minimisation working with any Boolean function are used for defining the upper bound of Shannon function. Previously we have developed the algorithm of minimisation of Boolean functions in ESOPs which uses the combinatorial technique connected with tasks of finding covering and packing of binary sets. ESOP for given Boolean function is built by pattern which is described of non-singular matrix over the field $Z_2$ in that earch row and column matches any binary set. These binary sets should have the packing with density $1+o(1)$ for getting the effective upper bound. It is normal to use error-correcting linear codes for building a matrix of pattern. In this case Hamming code may by used. And so it lets use terms of the linear codes theory in definitions of combinatorial problems. In this paper we investigate a problem which belongs to covering and packing design. In doing so requirements to matrix impose several conditions to cover. In this work some of possible covers are introduced which have been described in terms of error-correcting linear codes.

Détail

Keywords: boolean function, ESOP, Hamming code, covering design.