BALANCED BOOLEAN FUNCTIONS

Many common logic circuits such as adders, parity checkers and multipl exers realise Boolean functions that are true for exactly half their i nput combinations, and false for the other half; we refer to such func tions as balanced. Recently, these functions have been shown to be ver y useful for testing logic circuits, and for data encryption in crypto graphy. Here, we present a general theory of balanced Boolean function s. We derive a necessary and sufficient condition for balance by estab lishing an equivalence between a balanced function f(X) and a bijectio n from X to itself. We then analyse the conditions under which functio nal compositions preserve balance, and examine some specific balance-p reserving decompositions. A new characterisation of functional complet eness in terms of balance is presented. Finally, we address the proble m of counting equivalence classes of balanced functions.