Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

FET Logical Analysis Program

IP.com Disclosure Number: IPCOM000043845D
Original Publication Date: 1984-Sep-01
Included in the Prior Art Database: 2005-Feb-05
Document File: 6 page(s) / 58K

Publishing Venue

IBM

Related People

Ditlow, G: AUTHOR [+3]

Abstract

This article describes a method for computing the H1, H0, S1, and S0 function of complex FET circuitry embodied in an APL implementation which generates these functions for one output of a 32-bit barrel shifter in about a minute of computation time. This device had in excess of 384 transistors. The figure shows the FET network of an 8-bit barrel shifter. The functions for output F0 are: (Image Omitted) Note that simultaneous time on S1P and S1N opens a larger number of paths - the same for S2P and S2N. The algorithm described herein works recursively. At each step, it assigns a value to just one input variable of the network, and may decide that several edges and/or assignments of variables need not be considered at deeper levels of recursion.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 27% of the total text.

Page 1 of 6

FET Logical Analysis Program

This article describes a method for computing the H1, H0, S1, and S0 function of complex FET circuitry embodied in an APL implementation which generates these functions for one output of a 32-bit barrel shifter in about a minute of computation time. This device had in excess of 384 transistors. The figure shows the FET network of an 8-bit barrel shifter. The functions for output F0 are:

(Image Omitted)

Note that simultaneous time on S1P and S1N opens a larger number of paths - the same for S2P and S2N. The algorithm described herein works recursively. At each step, it assigns a value to just one input variable of the network, and may decide that several edges and/or assignments of variables need not be considered at deeper levels of recursion. After each assignment of a value to a variable the algorithm collects all the nodes which have been connected electrically by that new assignment to the output node and labels them as belonging to reached territory (initially, the reached territory consists of only the output node; each variable assignment adds to the reached territory new nodes - the algorithm assigns at each step values only to variables on edges connecting the currently reached territory to nodes outside that territory). At such an assignment step, consider a variable which resides only on edges that do not have both endpoints outside the currently reached territory. Assigning a value to that variable at that point crosses the territorial bound, and makes it uninteresting for succeeding invocations of the algorithm to cross the territorial bound in any other way - so we label all current edges from territory to outside as "used", which means that the succeeding invocations of the algorithm will not pick their variables from those edges. During the territorial extension, the algorithm checks whether it has reached its goal nodes; if it has, it adds a term to the result function and does not invoke itself - otherwise, it invokes itself at a deeper level of recursion. After return, it undoes its labelling of edges and frees the territory it reached during the preceding variable assignment. The variable is considered now to have been used at either 1 or 0, depending on what the assignment was. It will look at another variable on the edges connecting the reached territory to outside the territory, and repeat the process if such a variable exists. If it has run out of variables, it will remove all the used labels it generated at this step for variables and then return. This algorithm assures an exhaustive scan of all possible assignments of values to variables, which could generate paths from the output node to the goal nodes. Mathematical Statement of Problem The problem is given in terms of a triple (N,V,E), where N = a set of nodes (x1,x2,...., xn) V = a set of variables (v1,v2,...., vm)

E = a set of edges - each a triple (x1,xj,( )vk)

S = a subset of N (the "starting" set)

1

Page 2 of 6

G = a su...