On the number of classes of (n,k) switching networks

✍ Scribed by Michael A. Harrison

• Publisher: Elsevier Science
• Year: 1963
• Tongue: English
• Weight: 588 KB
• Volume: 276
• Category: Article
• ISSN: 0016-0032
• DOI: 10.1016/0016-0032(63)90456-3

✦ Synopsis

An (n,k) switching network is defined as all n-input, k-output network such that associated with each output is a Boolean transmission function of the n-inputs. If we allow a group @ on the inputs and a group ~ on the outputs, then the family of networks is decomposed into equivalence classes. In this paper the number of equivalence classes is derived for the important groups encountered in switching theory.

Many writers have considered the problem of classifying Boolean functions under various groups (1,4,10,14). 2 In this paper we shall show how to extend the approach that this writer has taken in (4, 5, 6, 7) in order to count the number of classes of sequences of k Boolean functions of n variables.

We shall be initially interested in classifying sequences of k Boolean functions of n variables under some transformation groups on the n variables. The functions in these sequences may be regarded as the transmission functions of a switching circuit having k outputs. Figure 1 shows the generic network called an (n, k) network. These (n, k) networks realize the (k, n) sequences of Povarov (12) as their behavior.

Either of two points of view may be taken in this investigation. Networks may be characterized by (1) their structure, that is, the place-

XI

XFI fi(xi,...,x,) ~fk(Xl,...,X n) FIG. 1. A generic (n, k) network.