Browse Prior Art Database

Switching-Network Analysis

IP.com Disclosure Number: IPCOM000047970D
Original Publication Date: 1983-Dec-01
Included in the Prior Art Database: 2005-Feb-08
Document File: 3 page(s) / 17K

Publishing Venue

IBM

Related People

Roth, JP: AUTHOR [+3]

Abstract

Given a switching network, the following algorithm efficiently computes its logical functions and compactly represents them. This is of particular use for verification of the correctness of the design. Switching networks have long been used for control, communication and computing purposes, notably in telephone switching systems. Some of the first computers were designed with switches. With the development of vacuum tubes and later transistors for the realization of computers, switching circuits fell into disuse. Recently in the development of very large-scale integration (VLSI) transistors have emerged (pass transistors) which behave very much like switches and in assemblages like switching networks. In VLSI, very large assemblages of transistor switches will be mass-fabricated and used in such large assemblages.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 38% of the total text.

Page 1 of 3

Switching-Network Analysis

Given a switching network, the following algorithm efficiently computes its logical functions and compactly represents them. This is of particular use for verification of the correctness of the design. Switching networks have long been used for control, communication and computing purposes, notably in telephone switching systems. Some of the first computers were designed with switches.

With the development of vacuum tubes and later transistors for the realization of computers, switching circuits fell into disuse.

Recently in the development of very large-scale integration (VLSI) transistors have emerged (pass transistors) which behave very much like switches and in assemblages like switching networks. In VLSI, very large assemblages of transistor switches will be mass-fabricated and used in such large assemblages. It is of substantial importance to determine whether or not such designs are correct, for example, whether they satisfy the specifications for their design. What we do here is to define an efficient procedure to translate a switching network into a logic circuit equivalent to it. Then efficient algorithms for logic-circuit verification[1] may be used to determine the correctness of the switching design. In a separate report we describe the few modifications necessary in this procedure to adapt it to pass-transistor networks. A SWITCHING NETWORK X is defined by a set of NODES, here denoted by lower-case letters a,b,c,...; BRANCHES consisting of selected pairs of nodes, denoted <a,b> ,..., connecting them; and ASSIGNMENTS of binary variables, denoted A, B, C,... and possibly their complements A',B',C',..., to the branches. The assignment of binary variable A to branch <a,b> defines a SWITCH, denoted A<a,b> which is CLOSED (a and b are connected through this branch) when A=1, and OPEN (a and b are disconnected through this branch) when A=0. Inversely, A'<a,b> implies that a and b are connected when A'=1, i.e., A=0, and disconnected when A'=0, i.e., A=1. (It may be convenient to allow the assignment of cubical functions, a special case being Boolean functions, when there are no "don't-cares", to branches, especially when dealing with large switching networks). Pick any two distinct nodes of X, say, p and q.

Then, X together with p and q define a function F, by the following rule: If for any assignment of values to the control variables A, B, etc., there exists a closed path between p and q, then F has the value 1; if no such path exists, then F has the value 0. Clearly, each such pair of distinct nodes of a network defines such a Boolean function. A switching network X is specified by a list A1<a1,b1>,...,An<an,bn>, where Ai is the binary variable assigned to branch <ai,bi> (it is allowed that more than one assignment be made to a given branch). For simplicity, assume that a1 and an are the single pair of external nodes and let us compute the Boolean function defined by X, a1 and an. We start with...