US 4,124,899 AGrant
Programmable Array Logic Circuit
Issue Date:1978-11-07
•21 Claims
•13 Drawing Sheets
Abstract
Programmable array logic circuitry is disclosed wherein the outputs from a field programmable AND gate array are connected, non-programmably, to specified OR gates. For greater architectural and operational flexibility, registered outputs, internal feedback to the AND gate array, input/output pin interchangeability, and means for allowing performance of arithmetical, as well as logic, operations, are provided.
Metadata
Assignee
- Monolithic Memories, Inc.
Inventors
- John M. Birkner
- Hua-Thye Chua
Application Information
Application Number:US 7995091
Filing Date:1977-05-23
Priority Date:1977-05-23
Art Unit:236
Classifications
IPC:
H03K 1920
Field of Search:
235307340364152;156;164207166 R;900716
Patent Drawings (13 sheets)
Description
Background of the Invention
Fusable links used in bipolar PROMS (Programable Read-Only Memories) have given the digital systems designer the ability to "write on silicon." In little more than a few seconds, an algorithm, a process, or a boolean transfer function can be permanently provided in the regular structure of an integrated circuit (IC) read-only memory.
PROMs are useful for many purposes including microprogram stores for high speed processors and controllers, non-volatile program stores for minicomputers and microprocessors, and high speed character generation and look up tables.
More recently, programmable integrated circuits have been extended to logic circuit arrays. These are sometimes referred to as PLAs (Programmable Logic Arrays) and FPLAs (Field Programmable Logic Arrays). FPLAs, in contrast to earlier mask-programmable circuits, can be programmed away from the place they are manufactured. Any problems in a programmed design that are discovered can be corrected simply by programming a new FPLA and discarding the old one. If the particular application has high enough volumes to cost justify it, a mask can be designed subsequently so that mask-programmable arrays can be made.
PLAs are used in the implemention of random logic networks, data routing, code converters, instruction decoders, state sequences, and a variety of other functions. For a general discussion of PLAs and FPLAs, reference is made to Electronic Design, Vol. 18, Sept. 1, 1976, "PLAs or .mu.Ps? At Times They Compete, and At Other Times They Cooperate", pp. 24-30.
Existing FPLAs comprise an array of logical AND and OR gates which can be programmed for a specific function. Each output function is the sum (logical OR) of selected products (logical ANDs) where each product is the product of selected polarities of selected inputs.
FPLAs can be programmed so that (1) any input line can be connected to any AND gate input and (2) any of the products (ANDs) can be summed by any of the OR gates. This is accomplished by providing a programmable array or matrix (1) between the circuit inputs and the AND gate inputs and (2) between the output of the AND gates and the inputs of the OR gates, respectively. The FPLA is then programmed by blowing or not blowing the fusible links connecting the conductors of the two arrays much the same way as PROMs are programmed. Examples of such FPLAs are Signetic Models 82S100 and 82S101.
Existing FPLAs as described above, while useful in many applications, have certain disadvantages. First, the size of the IC chip is quite large, due to the use of two programmable arrays per FPLA. This means lower yields, greater costs, and larger IC packages.
Secondly, the flexibility of such FPLAs is limited. They are limited as to the number of inputs, speed, and perhaps most importantly, architecture. Existing FPLAs are very limited in terms of the logical and arithmetical operations they can perform.
Summary of the Invention
It is therefore an object of the invention to provide improved field programmable circuit arrays;
Another object of the invention is to provide an improved field programmable logic circuit array which is smaller in chip size and less costly to fabricate and package;
Another object of the invention is to provide improved field programmable logic circuit arrays with improved architectural design and function;
Another object of the invention is to provide a family of field programmable logic arrays to give maximum flexibility for circuit design and implementation;
Yet another object of the invention is to provide field programmable circuit arrays which permit arithmetical as well as logical circuit functions.
In accordance with the present invention, an improved FPLA, hereinafter referred to as a programmable array logic (PAL), comprises a single programmable array or matrix of circuit inputs and the inputs to a plurality of AND gates (product terms). Outputs from subgroups of AND gates, in turn, are nonprogrammably connected as inputs to individual, specified OR gates (sum of the products).
By making the AND gate inputs programmable, i.e. selectable by the designer, while having the OR gate inputs nonprogrammable, some design flexibility is sacrificed. However, the reduction in IC chip size for the PAL more than makes up for the slight reduction in flexibility. Smaller chip size means greater yields and hence lower costs. Smaller chip size also means that smaller, more convenient packaging can be used. For example, a package size of approximately 300 mils wide by 1000 mils long with 20 pins is easily accomplished. This compares with the 600 mils by 1400 mils package size, and 28 pins, for existing FPLAs of comparable circuit components and function.
In accordance with another aspect of the present invention, PALs are provided having greater design and operational flexibility than existing FPLAs. This is accomplished through improved architectural design.
One improved architectural feature is the use of registered outputs with feedback. Registers are provided at OR gate outputs which allows temporary storage of the OR gate outputs. Additionally, a feedback path from each such register to the AND gate array is provided. This combination forms a state sequencer which can be programmed to execute elementary sequences such as count up, count down, shift, skip, and branch.
In accordance with another feature of the invention, a feedback path is provided back to the AND gate array from the output of OR gates. This allows the OR gate outputs to be sent back to the AND gate array at the same time they are provided to the output pins. Additionally, programmable means are provided to selectively enable or disable the OR gate outputs. When enabled, the OR gate output is the PAL output. When disabled, the output pin can be used as an input pin and the feedback path serves as another PAL input to the AND gate array.
The use of internal PAL feedback paths gives flexibility to the designer. It also reduces the number of external PAL connections. This has the salutorious effect of increasing the number of inputs to the product terms without increasing the number of pins.
The OR gate enable/disable feature allows greater flexibility in providing the ratio of inputs and outputs. In the static case, by disabling OR gates, more inputs to the PAL is provided. In the dynamic case, this feature provides a bidirectional pin for operations such as shifting.
In accordance with another object of the invention the PAL of the present invention is provided with a combination of exclusive OR gates (XOR) and additional OR logic circuitry at the input to the AND gate array. This permits PAL circuitry to perform arithmetic as well as logical circuit operations.
Brief Description of the Drawings
FIG. 1 is a schematic illustration of one embodiment of an unprogrammed and uncompleted Programmable Array Logic (PAL) circuit in accordance with the present invention.
FIG. 2 is a more detailed schematic diagram of the PAL circuit of FIG. 1.
FIG. 3A is a conventional schematic diagram representing an AND gate with four inputs; FIG. 3B shows the same AND gate of FIG. 3A in a new symbology; and FIG. 3C illustrates schematically the fusible connection used in a programmable array.
FIG. 4 illustrates in the new symbology the AND gate circuit of FIG. 2.
FIG. 5A is a logic circuit diagram for a particular transfer function; and FIG. 5B is a programmed version of the circuit of FIG. 4 to provide the transfer function of FIG. 5A.
FIGS. 6A-6I show the uncompleted PAL circuit of FIG. 1 in a variety of configurations.
FIG. 7 is a schematic diagram of another uncompleted PAL circuit configuration.
FIG. 8 is a schematic diagram of a part of the PAL circuit of FIG. 7.
FIG. 9 is a schematic diagram of another part of the PAL circuit of FIG. 7.
FIGS. 10A-10D show the uncompleted PAL circuit of FIG. 7 in a variety of configurations.
FIG. 11 is a partial PAL circuit with means for doing arithmetic operations.
Description of the Preferred Embodiments
FIG. 1 is a schematic illustration of one embodiment of an unprogrammed and uncompleted Programmable Array Logic (PAL) 30 in accordance with the present invention. As is explained subsequently, this basic arrangement can be used to provide a whole series of circuit configurations each of which in turn is individually programmable by the user. PAL 30 is arranged generally as it is physically configured in an actual, packaged IC. Twenty pins, identified by blocks 1-20, provide inputs and outputs to the PAL 30.
A programmable matrix or array 32 comprises input lines 34, and conductors 36, which are inputs to a plurality of logical AND gates 38-53. Input drivers 54 provide two outputs: an inverted output 56 and non-inverted output 58.
Shown unconnected to the outputs of AND gates 38-53 are a plurality of OR gates 60-67. The manner of their connection with AND gates 38-53 will be discussed subsequently. Of importance, however, is that as finally fabricated for use by the circuit designer, each output from each of the AND gates 38-53 is directly and nonprogrammably connected to an individual one of OR gates 60-67. Thus, the basic PAL 30 architecture comprises a programmable AND gate array feeding a fixed set of OR gates.
FIG. 2 is a more detailed schematic diagram of a part of PAL circuit 30 of FIG. 1, including AND gates 38 and 39, whose outputs are connected as inputs to OR gate 60. Inputs I.sub.1 and I.sub.2 are applied to pins 1 and 2. The output of OR gate 60, O.sub.1, is provided at pin 19. Each of the inputs 36 to AND gates 38 and 39 are connected through a fuse to an input line 34. Thus fuses f.sub.1 -f.sub.4 are provided for AND gate 38, and fuses f.sub.5 -f.sub.8 for AND gate 39. By either blowing or not blowing individual fuses f.sub.1 -f.sub.8, different inputs can be provided at the input to AND gates 38 and 39.
In the schematic of FIG. 2, the output is the familiar sum of products and can be expressed as:
where for:
fuse blown, f=0
fuse not blown, f=1
Given enough products, the sum of the products can express all boolean transfer functions.
Logic is generally defined by logic diagrams and truth tables, rather than the cumbersome equation shown above. For this reason the form used to describe the subject invention is also a logic diagram. But rather than the logic diagram of FIG. 2, a more convenient symbology is used.
FIG. 3A shows the conventional way of schematically representing four inputs, A-D, to an AND gate 61. FIG. 3B shown the same AND gate 60, with the same four inputs A-D, in the new symbology which is used hereafter. The "x" represents a transistor Q.sub.1 and a fuse as shown in FIG. 3C, with the base of transistor Q.sub.1 connected to an input line 34, the collector to the circuit supply voltage, and the emitter and fuse to the AND gates. If the fuse is blown, then there is no "x". In other words, the existence of an "x" indicates that the input 13 provided to an AND gate; and the absence of an "x" indicates the contrary.
FIG. 4 shows the same circuit of FIG. 2 drawn in the new symbology, where all of the fuses are intact.
To illustrate the way PAL circuit 30 is programmed, an illustration is provided, using the partial PAL circuit of FIG. 4 as an example. Let us assume that the desired transfer function is:
the logic circuit diagram for this transfer function is illustrated in FIG. 5A. FIG. 5B is a programmed version of FIG. 4 to provide this transfer function.
The uncompleted PAL 30 of FIG. 1 can be completed to configure a family of PALs having a variety of ratios of inputs to outputs, and either an OR or NOR output. FIGS. 6A-6I show the basic PAL 30 structure of FIG. 1 in a variety of configurations. Each of these configurations is made by the IC fabricator, as opposed to the circuit designer. In other words, the differences between each of the circuits of FIGS. 6A-6I is not normally field programmable. For purposes of clarity the "x's" indicating a fused connection between the input lines 34 and the AND gate inputs 36 are omitted. To help explain FIGS. 6A-6I, reference is made to the first nine entries of Table I:
For example the circuit of FIG. 6A has ten inputs, pins 1-9, and 11. It has eight outputs, pins 12-19. There are 16 AND gates giving a total of 16 product terms, or 2 product terms per output. The fuses, not shown, total 320. Each NOR gate has a circle at its output end. This indicates that the OR gate output is inverted by an inverter (not shown). This results in NOR outputs for this cirucit. FIG. 6B is the same configuration as 6A except it has OR outputs.
FIGS. 6C and 6D are identical except the former has NOR outputs and the latter OR outputs. In both there are 12 inputs: pins 1-9, 11-12; and six outputs: pins 13-18. Gates 61 and 66 have four AND gate inputs; the rest have two.
FIGS. 6E and 6F are identical except the former has NOR outputs and the latter OR outputs. Both have 14 inputs, pins 1-9, 11-13, and 18-19; and both have 4 outputs, pins 14-17.
FIGS. 6G and 6H are identical except the former has NOR outputs and the latter OR outputs. Both have 16 inputs, pins 1-9, 11-14, and 17-19; and both have 2 outputs, pins 15-16. Note that the outputs are NOR(OR) gates 64 and 65. OR gate 64 has AND gates 38-45 as inputs and OR gate 65 has AND gates 46-53 as inputs. For convenience in illustrating this schematically, four extra OR gates (not numbered) are shown as inputs to OR gates 64 and 65. In fact these extra four OR gates do not exist physically; but logically the two are equivalent.
FIG. 6I has a single OR gate 64. An OR output is provided at pin 16 and a NOR at pin 15. There are 16 inputs.
In FIGS. 6A-6I, pin 20 is reserved for the circuit voltage supply, Vcc, and pin 10 is used for ground.
FIG. 7 is a schematic diagram of another PAL circuit configuration 70 and like FIG. 1, is not programmed and, is not completed. FIGS. 10A-10D, also identified in Table I, show completed circuit configurations of the PAL circuit 70, which are subsequently described.
In addition to the AND and OR gates of PAL 30 of FIGS. 1 and 6A-6I, PAL 70 includes series D-type registers 72-79 which temporarily store the output of OR gates 60-67. This is shown in the completed circuits of FIGS. 10B-10D. It is also shown in an isolated schematic of one OR gate 67 in FIG. 8.
Referring to FIGS. 7 and 8, each register, such as register 79, loads its sum of products on the rising edge of a clock pulse provided at line 80. The Q output of each register is gated to the output pin through an active low enable three-state buffer 82. Additionally, the Q output of each register 72-79 feeds back through line 84 to the input lines 34 through the drivers 54.
The feedback arrangement shown in FIG. 8, in combination with register 72-79, forms a state sequencer which can be programmed to execute elementary sequences, such as count up, count down, shift, skip, and branch. Random control sequences, as with state sequencing, are efficiently performed by PAL 70.
Referring to the PAL 70" circuit of FIG. 10B and Table I, four registers 74-77 are utilized, each being internally fed back via line 84 to the input lines 34. In the PAL 70'" circuit of FIG. 10C, six registers 73-78 are utilized. And in the PAL 70"" circuit of FIG. 10D, all eight registers are utilized.
PAL 70 of FIG. 7 can also be configured to provide the designer with the option of (1) feeding back the sum from an OR gate while at the same time providing an output at the output pin, or (2) disengaging the OR gate from the output pin, and permitting another input into the AND gate array, at the expense of an output pin. This is shown in the completed circuits of FIGS. 10A, 10B, and 10C. It is also shown in an isolated schematic of one OR gate 67 in FIG. 9, which is now described.
In FIG. 9 where one of the product terms, AND gate 86, is used to directly control the three state buffer 82, via line 88, to gate the sum of the products from OR gate 67 to the output pin 12. When the gate 82 is "on", i.e. OR gate 67 is enabled, the output from OR gate 67 is provided at pin 12. When gate 82 is "off," i.e. OR gate 67 is disabled, pin 12 can be used as an input pin. In the latter case, an input signal passes from pin 12 via the "feedback" line 84 to the input lines 34.
In the static case, this programmable I/O feature is used to allocate the ratio of input pins to output pins. By "static case", is is meant that gate 82 is permanently driven either "on" or "off" by AND gate 86. In the dynamic case this feature provides a bidirectional pin for operations such as shifting. By "dynamic case" it is meant that gate 82 can be either "on" or "off" depending on the state of AND gate 86.
Referring additionally to Table 10, the I/O feature is provided for all eight OR gates 60-67, pins 12-19, in the PAL 70' circuit of FIG. 10A. The I/O feature is provided for OR gates 60-61 and 66-67, in the PAL 70" circuit of FIG. 10B. These correspond to pins 20, 19, 13 and 12 respectively. In PAL circuit 70'" of FIG. 10C, OR gates 60 and 67 are provided with the I/O feature.
Another feature of the PAL circuit family is described in FIG. 11. FIG. 11 shows a part of the uncompleted PAL circuit 70 of FIG. 7, namely, a pair of the OR gates 66 and 67. The circuit of FIG. 11, as will be explained, is particularly useful in performing arithmetic operations, such as addition, subtraction, greater than and less than.
FIG. 11 comprises one stage of a multiple stage arithmetic summing circuit. Summing circuits are well known to those skilled in the art and will not be explained at this time. It is sufficient to say that a characteristic of an arithmetic adder is the utilization of exclusive-OR gates and carry circuitry.
Referring to FIG. 11, an exclusive-OR gate is provided between the register 79 and the OR gates 67 and 68. In other words, the output from gates 66 and 67 provides the input to exclusive-OR gate 90.
Also shown in FIG. 11 is the addition of another OR gate 92, which has as its inputs the Q output of register 79 and an input to the PAL circuit. The output of OR gate 92 goes to a driver 94 which, like drivers 54, has an inverted output 96 and a non-inverted output 98. The output from OR gate 94 goes to the AND array via the input lines 34.
It can be shown that in addition to the exclusive-OR function performed by exclusive-OR gate 90, that a combination of AND gates of the AND gate array and OR gates 66 and 67 can additionally function to perform the same logical function as exclusive-OR gate 90. In other words, the combination of the AND array and the OR gate 67 and 68 with the exclusive-OR gate 90 forms a pair of series connected exclusive-OR gates. This combination is the heart of an arithmetic summing circuit.
The addition of the OR gate 92 provides additional logic circuitry necessary for carry look-ahead operations to be formed by each summing stage. Once again, the necessity of the additional OR gates for the carry functions of an adder are known to those skilled in the art and are not herein described.
Claims
We claim:
1. A programmable integrated logic circuit array comprising: (a) a plurality of groups of logical AND gates; (b) a plurality of logical OR gates; (c) non-programmable connections between the outputs from all of the AND gates within each of said groups of AND gates to inputs of predetermined and select individual ones of the logical OR gates; (d) a matrix of electrical conductor lines comprising (i) input lines, and (ii) AND gate input lines for each of the AND gates within said plurality of groups of logical AND gates; and (e) means for selectively connecting input lines and AND gate input lines to program a desired logical output from said OR gates.
2. A programmable integrated logic circuit array as in claim 1 including register means connected to the output of at least one of said logical OR gates for storing the logical state of the OR gate to which it is connected.
3. A programmable integrated logic circuit array as in claim 2 including means for connecting the output from each of said register means to selected ones of said input lines.
4. A programmable integrated logic circuit array as in claim 1 including gating means connected to the output of at least one of said OR gates, feedback means for connecting the output of each gating means to selected ones of said input lines; and means for gating each of said gating means to either disable or enable said OR gate, said feedback means being operable as an input line when said OR gate is disabled.
5. A programmable integrated logic circuit array as in claim 4 wherein at least one of said gating means is permanently gated to either enable or disable said OR gate.
6. A programmable integrated logic circuit array as in claim 4 wherein at least one of said gating means is temporarily gated to either enable or disable said OR gate.
7. A programmable array of integrated logic circuitry comprising: (a) a plurality of AND gates, each AND gate having a plurality of inputs and an output; (b) a progrmmable matrix comprising a plurality of input lines and said inputs to said AND gates; (c) a plurality of OR gates; and (d) non-programmable electrical connections between the outputs of sub-pluralities of said AND gates and predetermined and select individual ones of said OR gates.
8. A programmable integrated logic circuit array as in claim 7 including register means connected to the output of at least one of said logical OR gates for storing the logical state of the OR gate to which it is connected.
9. A programmable integrated logic circuit array as in claim 8 including means for connecting the output from each of said register means to selected ones of said input lines.
10. A programmable integrated logic circuit array as in claim 7 including gating means connected to the output of at least one of said OR gates; feedback means for connecting the output of each gating means to selected ones of said input lines; and means for gating each of said gating means to either disable or enable said OR gate, said feedback means being operable as an input line when said OR gate is disabled.
11. A programmable integrated logic circuit array as in claim 10 wherein each of said gating means is permanently gated to either enable or disable said OR gate.
12. A programmable integrated logic circuit array as in claim 10 wherein each of said gating means is temporarily gated to either enable or disable said OR gate.
13. A programmable integrated logic circuit array comprising: (a) a plurality of logical AND gates, each AND gate having a plurality of inputs and an output; (b) a matrix comprising the inputs to said logical AND gates and a plurality of input lines; (c) means for selectively connecting desired input lines with desired logical AND gate inputs; (d) a plurality of logical OR gates; (e) non-programmable connections from outputs of specified logical AND gates to inputs of an individual and select OR gate; (f) register means connected to the output of at least one of said logical OR gates for storing the logical state of the OR gate to which it is connected.
14. A programmable integrated logic circuit array as in claim 13 including means for connecting the ouput from at least one of said register means to selected ones of said input lines.
15. A programmable integrated logic circuit array as in claim 14 including gating means connected to the output of at least one of said logical OR gates to which a register means is not connected feedback means for connecting the output of each of the gating means to selected ones of said input lines and means for gating each of said gating means to either disable or enable said OR gate, said feedback means being operable as an input line when said OR gate is disabled.
16. A programmable integrated logic circuit array comprising: (a) a plurality of logical AND gates, each AND gate having a plurality of inputs and an output; (b) a matrix comprising the inputs to said logical AND gates and a plurality of input lines; (c) means for selectively connecting desired input lines with desired logical AND gate inputs; (d) a plurality of logical OR gates; (e) means for connecting outputs from said logical AND gates to inputs to said OR gates; (f) gating means connected to the output of at least one of said OR gates; (g) feedback means for connecting the output of each of the gating means to selected ones of said input lines; and (h) means for gating each of said gating means to either disable or enable said OR gate; said feedback means being operable as an input line when said OR gate is disabled.
17. A programmable integrated logic circuit array as in claim 15 wherein at least one of said gating means is permanently gated to either enable or disable said OR gate.
18. A programmable integrated logic circuit array as in claim 16 wherein at least one of said gating means is temporarily gated to either enable or disable said OR gate.
19. A programmable integrated logic circuit array as in claim 16 including register means connected to the output of at least one of said logical OR gates to which a gating means is not connected for storing the logical state of the OR gate to which it is attached.
20. A programmable integrated logic circuit array as in claim 19 including means for connecting the output of each of said register means to selected input lines.
21. A programmable integrated logic circuit array for performing arithmetic operations, comprising: (a) a plurality of logical AND gates, each AND gate having a plurality of inputs and an output; (b) a matrix comprising the inputs to said logical AND gates and a plurality of input lines; (c) means for selectively connecting desired input lines with desired logical AND gate inputs; (d) a plurality of logical OR gates; (e) means for connecting outputs from said logical AND gates to inputs of said OR gates; (f) a plurality of exclusive-OR gates whose inputs comprise at least a pair of said OR gates; (g) register means connected to the outer of at least one of said logical exclusive-OR gates for storing the logical state of the exclusive-OR gate to which it is connected; and (h) carry logic circuitry each having a pair of inputs, one input being connected to said register means and one input from an external input for providing carry signal information to said AND gate inputs.
Patent Citations (3)
Non-Patent Literature (2)
- H. Fleisher et al., "Reconfigurable Machine," IBM Tech. Disclosure Bulletin, vol. 16, No. 10, Mar. 1974, pp. 3342-3344.
- J. E. Elliott et al., "Array Logic Processing," IBM Tech. Disclosure Bulletin, vol. 16, No. 2, Jul. 1973, pp. 586-587.