Balanced Boolean functions
Krishnendu Chakrabarty, John P. Hayes · IEE Proceedings - Computers and Digital Techniques · 1998
Many common logic circuits such as adders, parity checkers and multiplexers realise Boolean functions that are true for exactly half their input combinations, and false for the other half; we refer to such functions as balanced. Recently, these functions have been shown to be very useful for testing logic circuits, and for data encryption in cryptography. Here, we present a general theory of balanced Boolean functions. We derive a necessary and sufficient condition for balance by establishing an equivalence between a balanced function f(X) and a bijection from X to itself. We then analyse the conditions under which functional compositions preserve balance, and examine some specific balance-preserving decompositions. A new characterisation of functional completeness in terms of balance is presented. Finally, we address the problem of counting equivalence classes of balanced functions.