4.3. THE PSEUDO-INVERSE OF A TRANSFER MATRIX AND NETWORK JUSTIFICATION 29

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

ij

N M

where log

2

.N / D n the number

of primary inputs and log

2

.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-

eﬃcients. 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 uniﬁcation of mathematical modeling is one advantage of the approach

described here as it provides a means for comparing network functionality among these diﬀerent

forms of physical implementation.

4.3 THE PSEUDO-INVERSE OF A TRANSFER MATRIX AND

NETWORK JUSTIFICATION

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 justiﬁcation problem. Logic network

justiﬁcation is useful in multiple design and analysis applications, including synthesis, veriﬁcation,

and test. In terms of automatic test pattern generation (ATPG) algorithms including the D-

algorithm [32], PODEM [33], and FAN [34], justiﬁcation is a core technique. It is also inherently

related to the satisﬁability 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.