Programmable Logic Devices:Logic Design with PLAs.

Logic Design with PLAs

Minimization techniques for multiple-output logic functions discussed in Chapter 30 can be used to minimize the size of a PLA. If the number of AND gates in a two-level AND-OR network (i.e., the number of distinct multiple-output prime implicants in disjunctive forms) for the given output functions is minimized, we can minimize the number of product lines, t. Thus, the array size (2n + m)t of a PLA is minimized when the PLA has n inputs, m outputs, and t product lines, where n and m are given. Also, if the total number of connections in a two-level AND-OR network is minimized as the secondary objective, as we do in the minimization of a multiple-output logic function, then the number of dots (i.e., connected intersections) of the product lines and the horizontal lines) in the PLA is minimized. Therefore, the derivation of a minimal two-level network with AND and OR gates by the minimization techniques known in switching theory is very important for the minimal and reliable design of PLAs.

The PLA show in Figure 45.3, for example, is minimized for the given functions f1, f2, and f3, with 8 product lines and array size, (2 × 4 + 3) × 8 = 88.

However, the minimization of the number of connections in a minimal two-level AND-OR network may not be as important as the minimization of the number of AND gates, although it tends to reduce the power consumption, because the chances of faulty PLAs can be greatly reduced by careful fabrication of chips. But the PLA size is determined by the number of AND gates and cannot be changed by any other factors. Also, instead of making connections (i.e., dots) as they become necessary on a PLA, a PLA is sometimes prepared by disconnecting unnecessary connections by laser beam or by blowing fuses after it has been manufactured with all MOSFET gates connected to the lines. In this case, the chances of faults can be reduced by increasing the number of connections (i.e., the number of dots) in the two-level AND-OR network.

For comparison with a PLA, the MOS realization of a ROM is shown in Figure 45.4. The upper matrix is a decoder which has 2n vertical lines if there are n input variables. The lower matrix stores information by connecting or not connecting MOSFET gates. Figure 45.4 actually realizes the same output functions (in negative logic) as those in Figure 45.1(a). The AND array in Figure 45.1(a) is essentially a counterpart of the decoder in Figure 45.4, or the decoder may be regarded as a fixed AND array with 2n product lines, which is the maximum number of the product lines in a PLA. The AND array in Figure 45.1(a) has only three vertical lines, whereas the decoder in Figure 45.4 has eight fixed vertical lines. This indicates the compact information packing capability of PLAs. PLAs are smaller than ROMs, although the packing advantage of PLAs varies, depending on functions. For example, if we construct a ROM that realizes the functions of the PLA of Figure 45.3, in a manner similar to Figure 45.4, the decoder consists of 8 horizontal lines and 16 vertical lines, and the lower matrix for information storage consists of 16 vertical lines and 3 horizontal lines. Thus, the ROM requires the array size of 16 × (8 + 3) = 176, compared with 88 in Figure 45.3.

Generally, the size difference between PLAs and ROMs sharply increases as the number of input variables increases.

A PLA, however, cannot store some functions, such as x1 ⊕ x2 ⊕ … ⊕ xn if n is large, because 2n –1 product lines are required and the number of these lines is excessively large for a PLA. (The horizontal lines become too long with excessive fan-out and parasitic capacitance.) However, we can store these functions in a ROM with an appropriate decoding scheme.

Of course, in the case of ROMs, storing a truth table without worrying about conversion of given logic functions into a minimal sum is convenient, although it makes the ROM size bigger than the PLA size. Minimal two-level networks of AND and OR gates for the absolute minimization of the PLA size can be derived by the minimization methods discussed in earlier chapters, if a function to be minimized has either at most several variables, or many more variables but with a simple relationship among its prime implicants [8]. But otherwise, we have to be content with near-minimal networks instead of minimal networks. In many cases, efforts to reduce the PLA size, even without reaching an absolute minimum, result in significant size reduction. Also, CAD programs have been developed with heuristic minimization methods [12,13], such as the one by Hong et al. [7], which was the first powerful heuristic procedure drastically different from conventional minimization procedures. MINI, PLA minimization program of Hong, et al., was later improved to ESPRESSO by Rudell, Brayton, et al. [1,10,11]. Recently, however, Coudert and Madre [2–6] developed a new method for absolute minimization by implicitly expressing prime implicants and minterms using BDDs described in Chapter 29. By this method, absolute minimization of functions with greater numbers of variables is more feasible than before, although it is still time-consuming.