A single-output switching network is tautological when the output response is h1j regard-
less of the primary input assignment. Due to the observations of the structure of a transfer matrix,
it is apparent that a tautological network must have a characterizing transfer matrix whose col-
umn vector with index j D 0 is h¿¿ : : : ¿j and whose j D 1 indexed column vector is htt : : : tj.
Likewise, a contradictory switching network is the inverse of a tautological network and always
yields an output response of h0j. e contradictory network must have a characterizing transfer
matrix whose j D 0 column vector is the total vector htt : : : t j and whose j D 1 vector is null.
In general, the form of a transfer matrix is T D Œt
where log
.N / D n the number
of primary inputs and log
.M / D m, the number of primary outputs. In the case where N D M ,
the network is comprised of an equal number of primary inputs and outputs. Furthermore, when
T is of full rank and N D M , a bijective mapping is present since the collection of input stimuli
are each uniquely mapped to a corresponding output response. is special class of switching
networks are said to be logically reversible and is a subject of interest in the research community due
to the results of Landauer [18] which state that such networks when used to process information
do not dissipate power due to information loss.
Depending upon the implementation technology, a reversible switching network may also
allow an output response to be applied to the physical implementation of a network and the pri-
mary inputs to then produce the resulting input stimulus. Such is not the case for common elec-
tronic switching networks implemented in a technology such as static CMOS electronic transistor
networks, thus this class of networks is logically reversible, but not physically reversible. Quantum
logic networks are necessarily both logically and physically reversible due to the laws of quantum
mechanics. For the case of quantum logic networks, other properties of their transfer matrices
are also in place such as the matrices being unitary and being comprised of complex-valued co-
efficients. e vector space model presented in this work for conventional switching networks
can thus be viewed as a superset of the special case of reversible switching networks and provides
a convenient mathematically unifying theory for modeling conventional reversible and quantum
logic networks with the general case of irreversible switching networks where N ¤ M is com-
monly encountered. is unification of mathematical modeling is one advantage of the approach
described here as it provides a means for comparing network functionality among these different
forms of physical implementation.
Several EDA tasks require the determination of an input stimulus vector given a characterization
of the network and an output response, referred to as the justification problem. Logic network
justification is useful in multiple design and analysis applications, including synthesis, verification,
and test. In terms of automatic test pattern generation (ATPG) algorithms including the D-
algorithm [32], PODEM [33], and FAN [34], justification is a core technique. It is also inherently
related to the satisfiability problem (SAT). Furthermore, reverse logic implications are a special

Get Modeling Digital Switching Circuits with Linear Algebra now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.