Depopulated programmable logic array

Details Depopulated programmable logic array Depopulated programmable logic array

2003-06-10

2004-10-12

Nguyen, Linh M. (Department: 2816)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000

Reexamination Certificate

active

06804812

ABSTRACT:

FIELD OF INVENTION
This invention generally relates to programmable logic arrays (PLAs), and particularly to minimizing the size and speed of PLAs.
BACKGROUND
Programmable Logic Arrays (PLAs) have been used in the semiconductor industry for many years. They are essentially generic electronic circuits, able to be programmed to provide a variety of logic functions. PLAs are well understood in the art, but a brief explanation is provided below.
In PLAs, a logic function to be implemented is expressed in product terms (AND terms) and sum terms (OR terms). Each product term is generated by circuitry that can be programmed to form the AND of any subset of the inputs to the PLA and their complements. Product terms are then be summed, or OR'd, through additional programmable circuitry.
More specifically, PLAs are generally constructed in the form of regular arrays, with the input lines being orthogonal to the product lines, as shown in the generalized circuit diagram of FIG.
1
.
FIG. 1
shows one type of PLA known as a PAL. In
FIG. 1
, PAL
100
includes inputs
102
, A-D, where each input and its complement is input into programmable AND array
104
on lines
106
. AND lines
108
are formed orthogonal to lines
106
. When a selected intersection between an input-term line
106
and an AND line
108
is programmed, then “AND terms” or “product terms”
110
are formed. The product terms
110
are then fed into OR gates
112
forming “sum terms”
114
.
As is understood in the art, product-terms are often implemented with a wired-OR mechanism, where at each intersection of lines
106
and
108
programmable transistors
115
are used. A pull-up
116
is also used, as shown in the generalized circuit diagram of FIG.
2
. Although the pull-up
116
is shown as a resistor in
FIG. 2
, frequently a passive pull-up is implemented with a biased P-channel transistor instead. It will be noted that when using the structure of
FIG. 2
, the AND gates
109
shown in
FIG. 1
are not actually physically present, but instead in FIG.
1
AND gates
109
represent logically the function being performed.
A second type of PLA structure (sometimes referred to as a “Full PLA”) is shown in
FIG. 3
, having both a programmable AND array
104
and a programmable OR array
117
. In other words, both product terms and sum terms can be programmed. Thus, the device of
FIG. 3
can implement any set of combinational logic limited only by the number of inputs, outputs, and product terms.
Relative to the device of
FIG. 1
, the device of
FIG. 3
sacrifices some speed, but has greater programming flexibility and is better for implementing state machines. As well, unlike the
FIG. 1
device, in the
FIG. 3
device, each product term can be used by, or shared among, all sum terms. Still, as shown in
FIG. 4
, some PLA devices create OR arrays where selected groups of the product terms are shared among selected groups of the sum terms.
Flexibility of PLA structures, including those of
FIGS. 1 and 3
, can be further enhanced by adding flip-flops
118
(shown in
FIG. 3
) to one or more of the outputs to create general-purpose sequential circuits. As shown in
FIG. 5
, inverted product terms such as !PT can also be fed back directly into the AND array. As used herein, complemented terms will be indicated with either a “!” or with an overbar, as is the practice in the art. As shown in
FIG. 5
a
, when many product terms are inverted and fed back, it forms what is known as a NAND-NAND (or NOR-NOR) array.
Many PLA devices also include post-array logic structures as shown in FIG.
6
. The most frequent need for such structures is to complement a logic function—otherwise, to complement the function, one would have to resort to DeMorgan's Law (!(AB)=(!A+!B)), typically resulting in a large number of product terms that would need to be programmed. XOR gates
120
are commonly used as such post-array structures. Inversion can be controlled by (1) a sum term representing a complex function (as for XOR gate
120
1
), (2) a single product term (as for XOR gate
120
2
), or (3) by a single logic value that can be programmed to a logical “1” (V
dd
) or “0” (V
ss
) (as for XOR gate
120
3
).
Similarly, pre-array logic structures
122
are also often used as shown in FIG.
7
. Such pre-array logic structures are often useful in performing arithmetic functions such as accumulators. Both post-array and pre-array logic structures are used to reduce the number of product terms that would otherwise be required, and hence allow the use of smaller and faster PLA devices.
Each of the conventional PLA structures described in
FIGS. 1-7
is usually a discrete device and is programmable and reprogrammable by the user either using a specialized programming device or in-system as is understood in the art. As should be understood in the art from
FIGS. 1-7
, there are numerous types of PLAs available and those described are exemplary only.
As alluded to above with the discussion of pre- and post-array structures, it is generally desirable to use the smallest PLA device available, for real-estate reasons as well as speed. To that end, “PLA folding” has been studied and is described in Ferreira and Song, “Achieving Optimality for Gate Matrix Layout and PLA Folding: a Graph Theoretic Approach”, 1992. In general, PLA folding is a technique that, given a PLA, attempts to produce an equivalent PLA that occupies less space. For example, consider the following logic functions to be implemented by a PLA:
f
6
={overscore (v)}
1
v
5
+{overscore (v)}
2
{overscore (v)}
3
+v
1
v
3
+{overscore (v)}
5
f
7
=v
2
v
4
+{overscore (v)}
2
{overscore (v)}
4
These functions are shown implemented in a traditional PLA in
FIG. 8
, where the “dots” represent a programmed connection. Through a series of matrix manipulation and rearranging of rows, the result of the folding is shown in FIG.
9
. More details of this example can be found in Ferreira and Song (cited above). As shown in
FIG. 9
, the folded PLA is much more compact, retaining as much physical regularity as possible by causing the tiling of product term groupings.
Still, this PLA folding technique has gained little practical application. To effectively use folding, an engineer must know with relative certainty the functions to be programmed. And the freedom to make changes to the functionality is severely limited by the “folds.” Moreover, PLAs are typically only available as discrete devices (e.g., PLDs) in fixed sizes with fixed characteristics. So while folding techniques might be useful in theory, there are essentially no devices using them.
SUMMARY
A PLA in accordance with an embodiment of the invention is designed after knowing the initial logic to be implemented by the PLA. Once such logic is known, a PLA sized specifically to that logic is modelled. Then unnecessary programmable connections are removed creating a relatively small, but fast PLA to implement the given function. Additional programmable connections are then re-added to the model to allow for future reprogramming. Finally, the modelled PLA is constructed.
The result is a PLA that achieves a maximum amount of depopulation while still implementing a logic function and maintaining flexibility for future reprogramming. In addition a PLA in accordance with an embodiment of the invention can be built so that no matter what functionality is programmed, the performance characteristics for the device remain the same.
A PLA in accordance with an embodiment of the invention does not require a regular array structure. Therefore, such a PLA is flexible for place and route considerations, particularly when integrated with other logic in larger circuits.


REFERENCES:
patent: 4761768 (1988-08-01), Turner et al.
patent: 5543732 (1996-08-01), McClintock et al.
patent: 5566127 (1996-10-01), Hoshizaki
patent: 5572148 (1996-11-01), Lytle et al.
patent: 5646545 (1997-07-01), Trimberger et al.
patent: 5670897 (1997-09-01), Kean
patent: 5708597 (1998-01-01), Kelem
patent: 5715197 (19

Affiliated with

Also associated with

Rating

Depopulated programmable logic array does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Depopulated programmable logic array, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Depopulated programmable logic array will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3270380