Distance duality on some classes of boolean functions

Pantelimon Stnica, Tsutomu Sasao, Jon T. Butler

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

A function/is at a distance d(f,S) from a set S of Boolean functions if the minimum Hamming distance between/and all g ? S is d(f,S). Given a set S of Boolean functions, the set S of functions is said to have a maximum distance from S if it has the property that for all/? S, d(f,S) is maximum. The well-studied bent Boolean functions (S) are defined to have a maximum distance from the set of affine functions (5). Tokareva [14] showed the converse is also true. That is, 5 is a maximum distance from S. In such a case, we say that <S and <S are mutually maximally distant. We introduce partition set functions, which include symmetric functions, rotation symmetric functions, self-anti-dual-functions, lin-ear structure functions, and degenerate functions. We show that partition set functions associated with a partition on the domain FJ are mutually maximally distant from another set S of functions. We show that the distributions of weights in 5 is binomial and centered at 2n 1, the point at which a function is perfectly balanced. Because there is much interest in symmetric functions, we consider this special case, and verify a prior enumeration of functions that are maximally distant from symmetric functions [8] (we call them maximally asymmetric functions). We characterize balanced maximally asymmetric functions. A similar analysis is done on rotation symmetric functions.

Original languageEnglish
Pages (from-to)181-198
Number of pages18
JournalJournal of Combinatorial Mathematics and Combinatorial Computing
Volume107
Publication statusPublished - Nov 2018

Fingerprint Dive into the research topics of 'Distance duality on some classes of boolean functions'. Together they form a unique fingerprint.

  • Cite this