Programmable Logic Devices:Simple Combinatorial Programmable Logic Devices

Simple Combinatorial Programmable Logic Devices

The Basic Version Of The PAL

This basic type shown in figure 18.8 is directly derived from the PROM.

The component offers 10 inputs and 8 outputs which are active high (Active High – H). These three characteristics are responsible for the additional name 10H8. The 10 inputs feed in true and inverted mode the vertical input lines which are crossing the horizontal AND lines. This is the programmable AND matrix. Thus any of the 16 AND lines disposes of 20 physical inputs; however, only a maximum of 10 inputs can be used. Otherwise a true signal and an inverted signal would be conjunctively linked together, which always results in the low value. The 16 AND lines are combined in pairs with OR gates feeding the 8 output signals. A compact form of all information about the device is also included in the functional block diagram as shown in figure 18.7.

The possibilities offered by the PAL 10H8 are illustrated by means of three examples. In a microprocessor system an enable signal f for a port has to be produced with respect to a given address A:

The binary representation of the address provides the logic operation of the 10 address bits.

This wide AND operation is ‘programmed’ at pin 19 in fig. 18.8: those programmable memory cells which are marked by an ‘x’ in the upper AND term remain intact, all others will be destroyed during the programming process. The second AND term of pin 19 is not needed, it must always supply a ‘low’. For this purpose, all programmable memory cells remain intact. An address decoder realized in this way generates the intended

enable signal within typical 0.5 ns.

In addition to this, 4 event lines have to be monitored and flagged with graded priority in the same microprocessor system. In table 18.2 the status signals are allocated to the events, respectively.

In fig. 18.8 these logic operations are also ‘programmed’ at the pins 18 to 16. Finally a 1-bit full adder according to table 18.3 illustrates the limits of PAL 10H8.

In figure 18.8 the ‘programming’ is carried out at pin 15 and pin 14. In addition, the outputs of pin 13 (g) and pin 12 (h) with the inputs of pin 8 and pin 11 have to be connected externally. This results in a cascaded AND-OR operation. The component is used twice and the delay is doubled. For the 1-bit full adder a component with at least 4 AND terms per OR gate is of course more suitable.

Additional Internal Feedback and Switchable Output Drivers

The logic diagram of PAL 10H8 in fig. 18.8 is already complex enough. In order to concentrate on the essential issue, the following sections deal  with simple examples. However, the indications given follow the real models which are shown in brackets.

The example of the full adder shows that a cascade of AND-OR logic is sometimes necessary. For this purpose, some PALs are provided with an internal feedback as shown in fig. 18.9.

In addition to this, a controllable output driver inverts the signal of the OR gate. Thus the output becomes low active (active low – L) which leads to the ‘L’ in the suffix of PAL 4L2 (of PAL 16L8). The upper AND term with the abbreviation of OE (output enable) serves as a control of the output driver. Three different connection types can be programmed in this way.

a) OE = 1: all programmable memory cells are destroyed, the pull-up resistor is active: The output driver is constantly enabled and the connection works as an output.

b) OE = 0: all programmable memory cells are intact, true signals and inverted signals result in low: The output driver is constantly disabled and therefore highly resistive. The connection can now be used as an additional input.

c) OE is changed by the logic operation while operating. In this case the connection operates in both directions as input/output.

The internal feedback allows the immediate programming of an output signal in the AND matrix. If it is used in adjacent AND terms, there will be a multi-stage ‘transparent’ logic. If the output signal is, however, used in its own AND terms, there will be a feedback. Two possibilities have to be distinguished:

There will be a positive feedback if the re-feeding driver/inverter relinquishes the inversion of the output driver. This is programmed in the upper half of fig. 18.9. As long as pin 5 indicates ‘low’, the positive feedback term supplies a ‘high’. However, if pin 5 becomes ‘high’ it will be confirmed by a ‘low‘ of the positive feedback term and will be maintained until the voltage is cut off. Such a circuit catches the high.

There will be an inverse feedback if the inversion is maintained in the feedback. As shown in the lower part of fig. 18.9, the programmed circuit is never satisfied and constantly changes the output value at pin 4. There is a ring oscillator which could be switched on and off via the middle AND term. It should actually be handled with caution, as it does not have any guaranteed frequency.

The ring oscillator may be useful for test purposes. The delay time of the complete feedback loop, e.g., of the input driver/inverter, the AND line, the OR gate, and the output driver occurs between two counter-sense clock edges. This is identical with the gate sequence of an input pin to an output pin. Thus the delay time tPD between the pins can be determined by the measured oscillator frequency

Programmable Polarity

The two PALs dealt with above both have a defined output polarity, either active high or active low. An additional exclusive OR (EXOR) placed before each output allows the individual programming of the polarity. Figure 18.10 shows an EXOR gate with a programmable input.

In the case of an in tact programmable memory cell the input p shows ‘low’, and in case of a destroyed fusible link there will be ‘high’ by means of pull up. As shown in the truth table 18.4, the output a for p = 0 is identical with the input e. For p = 1, however, ‘e’ will be inverted to become ‘a’.

The possibility of inverting may be very helpful. A code transcriber from BCD Code (Binary Coded Decimal) to the Excess 3 Gray Code according to table 18.5 is to be realized by means of the PAL 4P4 (of PAL 10P8).

The position g2 needs too many AND terms, so the code transcriber seems to be too much for the PAL 4P4. Using the programmable inverter it is however possible to alternatively program the inverter function. It needs one AND term only. The four equations can now all be programmed into PAL 4P4 as shown in fig. 18.11.

Apart from selecting between 1 active (H) and 0 active (L), the programmable inverter also allows one to reduce the AND terms required in this example.

Random Multiple Allocation of AND Terms

The examples of the full adder and the code transcriber demonstrate that there may be a short of definitely allocated AND terms. It would be more favorable to have a more flexible distribution among the outputs. With the OR matrix, which is also programmable, such a possibility is presented by the PLA (Programmable Logic Array) structure shown in fig. 18.12. By means of the OR line any number of the existing AND terms may be allocated to any output (Product Term Sharing).

This is to be demonstrated with the example of the full adder. The equations to be programmed are as follows in the original Sum of Products:

Transformation is no longer necessary, then the PLA is configured in a way which is adapted to the respective problem. Output 7 is assigned to four AND terms and output 6 to three.

Distributed in this way, the two equations can be programmed directly, as shown in fig. 18.12.

The easy use and the flexibility of the PLA is not for nothing. The programmable OR matrix requires more silicon space than defined OR gates. Simple PAL components are therefore available at a lower price.

Simple Sequential Programmable Logic Devices

In addition to the combinatorial logic, the sequential devices are provided with storage elements. The devices have a memory. Their output signals do not depend only on the input signals but they also depend on the memory values. Thus they are able to supply bit pattern sequences justifying their additional identification as ‘sequential’.

Programmable Register Input In this PLD the already well known input drivers/inverters are replaced by a D flip flop. All D flip flops shown in fig. 18.13 receive the same clock signal. They adopt new values simultaneously. They are therefore represented in a register. Every D flip flop can be disabled individually via a programmable memory cell. It is then diminished to a standard input driver/inverter, as in case of  PAL 4L2 shown in fig. 18.9.

This is also indicated by the name of PAL R4L2 (of PAL R19L8). The prefix R for registered input is complementary to PAL 4L2. As an alternative to the D flip flop there is also a programmable d-latch available which can be seen from the prefix T for   transparent latch in the name of PAL T4L2.

Such PLDs with input register are suitable for the output of coded information to be valid for a longer

period and still to be decoded. A typical example is given by the numerical display in fig. 18.14 with 7 segments, e.g., for indicating the actual time (in a minute cycle) or the time of departure (irregular).

For a short period of time the number to be dis- played is available in a BCD coded way and is stored into the input register. Decoding of all 7 individual segments is then carried out according to table 18.6.

These equations directly follow from table 18.6, considering all input combinations which supply a ‘low’ at the outputs. For input combinations which are unknown to the code, the decoder therefore generates ‘high’ signals. The /e signal is an exception to this rule, it can also take the value ‘low’. If there is an unknown BCD bit combination in the input register owing to a failure, the display will show 8 or 9.

This 7 segment decoder is not yet a sequential circuit because the output signals depend exclusively on the register contents.

PLD with Output Registers

Sequential devices combine the contents of a register (from the past) with the current input signals (from the present) for a subsequent status (in the future). The programmable AND-OR structure should precede the memory elements. In fig. 18.15 the D flip flops are therefore prior to the outputs and form an output register because of the common clock.

The selection of a D flip flop as a storage element does not imply any limitation. With the preceding logic all other flip flop types can be programmed as well. The clocked SR flip flop is provided with two separate inputs, e.g., the input s (set) for charging a ‘high’ and the input r (reset) for charging a ‘low’. The described separation of tasks implies a conflict, namely, if both inputs are activated simultaneously. In table 18.8 this conflict is solved first in favor of the input s (d1) and then in favor of the input r (d2).

Again, the respective equations only need 2 AND terms each and could immediately be programmed into PAL 4R2. Thus the preceding AND-OR structure allows the implementation of other flip flop types, too.

Very often the D flip flop is directly used when designing sequential devices. Starting from the actual state, a subsequent state is prepared depending on the input signals. Figure 18.16 shows a variable divider as an example of a finite state machine (FSM). The circles represent the states, and the arrows show state transitions which are triggered by a clock edge.

If an actual state has more than one subsequent state, the state transitions need additional transition conditions. In most cases they are specified by

the input signals and are indicated at the respective arrows. Each state transition can also be found in the functional table 18.9.

In fig. 18.18 these Boolean equations are programmed into PAL 4R2.

The example of variable dividers clearly illustrates the various methods of description for a sequential device. The transition graph in fig. 18.16, its representation in form of the table shown in 18.9, and the KV tables given in fig. 18.17 are still independent of the realization. The Sum of Products of the Boolean equations already takes the possibilities of the target hardware into account.

The logic diagram in fig. 18.18 with the × marks at the effective inputs provides the wiring diagram and thus it serves as a production document.

EXOR Gate Preceding The Register Inputs

In case of the present PAL 4X2 an EXOR gate supplements the programmable AND-OR structure of the D flip flop as shown in fig. 18.20. Unlike in case of PAL 4P4 with first programmable and then defined polarity, it is now also possible to invert dynamically.

According to fig. 18.19 a T flip flop gate is realized by using the EXOR gate. With ‘low’ at the T input, the T flip flop takes its former q value with every new clock, thus maintaining its value. A ‘high’ at the T input inverts the q value, and the flip flop toggles.

The aforesaid T flip flop is especially useful for the design of counter circuits as is shown by the ex- ample of a four digit binary upward counter. Table 18.10 shows the actual state {q3, q2, q1, q0}, the subsequent state {d3, d2, d1, d0} and the toggle conditions {t3, t2, t1, t0}, too.

This clearly shows that the number of required AND terms for the d inputs increases with the number of digits. The toggle equations, however, can be realized with one single AND term. More- over, it follows a very simple construction law:

‘the n-th digit has to toggle if all lower digits are at high, e.g., ‘1’!’. Considering the EXOR gate in fig. 18.19, the equation for the highest digit of a 10 digit binary upward counter would read:

d9 = q9⊕q8 ∗ q7 ∗ q6 ∗ q5 ∗ q4 ∗ q3 ∗ q2 ∗ q1 ∗ q0 It can hardly be easier than this! As to the equally useful downward counter, ‘at maximum’ means that all lower digits show the value ‘0’.

The conversion of the storage element into a T flip flop is certainly not the only possibility of using the EXOR gate. It also supports general logical expressions in the AND-OR-EXOR version.

Reed Muller Standard Form

Apart from the two best known standard forms for Boolean expressions, namely, the Sum of Products (SOP) and the Product of Sums (POS), there are other standard forms which use for example ex- clusively the NAND gate or exclusively the NOR gate. An EXOR Sum of Products (ESOP) is named after its fathers Reed and Muller. It contains only true signals (not inverted). Any logical expression can be represented by the Reed Muller format. A generalization also allows inverted signals; how- ever it does not allow a signal in both polarities. It is called ‘generalized Reed Muller (GRM)’. If there are signals in both polarities in an AND-OR- EXOR expression this is called ‘mixed GRM’. The last mentioned Sum of Products is supported by the PAL 4X2 because of the input drivers.

How is a given Boolean expression transferred into a Reed Muller format? The inventors proved the existence and definite expression which guaranteed the success of the search, but they were at a loss to indicate a simple guide. A possibility is provided by the ‘EXOR Factoring’ according

If a logical expression A is EXOR combined twice with the identical expression F, they cancel out and A remains unchanged. In the case of ‘EXOR factoring’ one of the EXOR operations is carried out, the other one maintained as the EXOR factor. The equation for the d3 input of the upward counter are taken as an example. As all AND terms include the variable q3 the latter is taken as an EXOR factor:

The result is no longer surprising because it is already known as the toggle condition. In the Reed Muller form d3 requires only one AND gate and one EXOR gate compared to four AND gates and one OR gate in the Sum of Products.

Arithmetic Combinations Of Inputs With Outputs

The buffers/inverters for the inputs and for fed back outputs are now replaced by four different OR gates. In fig. 18.21 the vertical input lines already represent arithmetic combinations of an input/output signal pair respectively.

In this way it is possible to program 16 individual functions within the AND matrix. They are shown in table 18.11 in the form of a programming specification. For some functions the arithmetic denotation is added.

The above table shows all theoretically possible functions with up to two variables. The abnormal functions with a constant value high (1) or low (0) may cause astonishment, the practice shows however, that they do occur in the case of defective components.

The aforesaid PLD type is preferentially applied to fast arithmetic parallel operations. It can demonstrate its efficiency by searching a maximum value for example. It will compare the 4-digit binary numbers {e3, e2, e1, e0} with its stored output values {a3, a2, a1, a0}. If the actual input value is higher than the one stored, this value shall be stored as the new maximum value.

A complete function table taking all possible combinations of numbers into account requires 24 × 24 = 256 lines. The comparison is, however, only made by positions starting with the highest position. In addition there are only three possible comparison results per position, e.g., higher, lower, or equal. In the latter case the next lower position has to be queried. The result is the compressed function table 18.12 with only nine lines.

In the Sum of Products the Boolean equations for the d0 input would therefore require nine AND terms. But a change is realized in only four lines of the function table. A T flip flop which is satisfied by the toggle conditions can be programmed by means of the EXOR gate. The existing Reed Muller standard format requires a maximum of only four AND terms for each position:

These equations follow directly from the function table 18.12. A position needs to change only when it does not match. This explains the additional unequal conditions at the lower positions. Because of the programming specification in table 18.11 the arithmetic terms can be programmed directly. The importance of the said components demands the highest respect when you try to solve the task, for example, with the PAL 8R4.

Asynchronous Register Functions

All sequential logic devices dealt with so far are provided with a clock input which controls all storage elements simultaneously. The outputs can only change synchronously with this clock. Additional possibilities for set or reset are required for some applications. Such possibilities are, for example, provided by PAL 20RA10. Its outputs are provided with a macro cell each, as shown in fig. 18.22.

Out of the eight AND terms the four outer ones each serve a specific task:

• control of the output driver;

• asynchronous set (ap); and

• asynchronous reset (ar); as well as

• clock (cl) of flip-flop.

The four middle AND terms are collected by the OR gate. The polarity of the d input can be selected by means of an EXOR. The resolution of the set/reset conflict is very interesting: If both signals ap and ar are active the register is avoided, making the output combinatorial.

The preload function (PL) facilitates the test of complex state machines. It allows, by using output pins, to charge arbitrary, even forbidden, states into the flip flops. Following a clock edge it is possible to test a subsequent state. If several subsequent states are possible, depending on the input conditions, they can directly and successively be tested without running through long sequences.

The combination of combinatorial and sequential logic devices had a stimulating effect on imitations.

Generic-Array-Logic GAL 16V8 (versatile – V)

The GAL components of the Lattice company use the EEPROM technology and are electrically programmable and electrically erasable. Such a possibility of correction during a development is very welcome, especially for prototypes. GAL components are simply a temptation to try other circuit realizations [18.5].

The logic diagram in fig. 18.23 shows the well known structure with eight programmable AND terms for each of the eight output logic macro-cells (OLMC).

Figure 18.24 shows an output logic macro-cell OLMC. Four multiplexers allow different configurations. The output multiplexer (OMUX) selects the type of output. The switchable output driver drives the TSMUX (tri-state multiplexer), one of its four inputs being an AND term. If the AND term is selected the Product Term Multiplexer (PT- MUX) will replace it by a low (0) signal at the OR gate. Finally, the Feedback Multiplexer (FMUX) is responsible for the desired feedback. Theoretically it may be possible to program 2 × 4 × 2 × 4 = 64 different combinations, but in practice the selection is limited to only six variants. In table 18.13 they are even subdivided into three operation modes.

In ‘registered mode’ the pins 1 and 11 serve as a clock input (CLK) and as control (OE) of the output driver. In ‘simple mode’ they feed, as standard inputs, the AND matrix via the feedback. As far as the pins 19 and 12 are concerned, being inputs, they have to back up to the neighboring output cells. In such a competition of suppression

the pins 15 and 16 are left over. They have to become outputs. If even only one single flip flop is required, the remaining output cells can only be realized with ‘complex mode’.

Even with the aforesaid limited number of variants, a GAL 16V8 can simulate up to 21 different 20-pin PAL types:

10H8 12H6 14H4 16H2 16H8 16R8 16R6 16R4 10P8 12P6 14P4 16P2 16P8 16RP8 16RP6 16RP4 10L8 12L6 14L4 16L2 16L8 The corresponding 24-pin PAL types are emulated by GAL 20V8. Thus two GAL components can replace more than 40 PAL devices. No wonder that some PAL types are no longer on the market.

In the following section the GAL 16V8 is used to emulate a PAL 4R2 according to fig. 18.18. The variable divider will be taken as an example for computer supported programming.