Browse Prior Art Database

Method for Removing Redundancies From Programmable Logic Arrays

IP.com Disclosure Number: IPCOM000060391D
Original Publication Date: 1986-Mar-01
Included in the Prior Art Database: 2005-Mar-08
Document File: 4 page(s) / 26K

Publishing Venue

IBM

Related People

Popp, DE: AUTHOR

Abstract

A programming concept makes is possible to reduce logic redundancies in a PLA (Programmable Logic Array) without converting the product terms to their Boolean equivalents. This permits the designer to work with a familiar format and reduces processing time, at the expense of a less than completely optimum reduction. A value is determined for each product term to establish a sort list in descending value order. Each product term is then compared successively with all other product terms, testing for one of four conditional rules. Depending on conditions detected in each comparison, product terms or elements of them may be deleted. Successive passes through the list are made until no further deletions are detected. A PLA consists of an input (AND) array and an output (OR) array. Fig.

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 46% of the total text.

Page 1 of 4

Method for Removing Redundancies From Programmable Logic Arrays

A programming concept makes is possible to reduce logic redundancies in a PLA (Programmable Logic Array) without converting the product terms to their Boolean equivalents. This permits the designer to work with a familiar format and reduces processing time, at the expense of a less than completely optimum reduction. A value is determined for each product term to establish a sort list in descending value order. Each product term is then compared successively with all other product terms, testing for one of four conditional rules. Depending on conditions detected in each comparison, product terms or elements of them may be deleted. Successive passes through the list are made until no further deletions are detected. A PLA consists of an input (AND) array and an output (OR) array. Fig. 1 shows a simple PLA array of the seven product terms, T1 to T7, with a chart shown in Table 1. It is seen that each product term includes four input vector (AND) elements, X1 to X4, and seven output vector (OR) elements, Y1 to Y7 . It is further seen that the AND element bit values are "1", "0", and "d", and that the OR element bit values are "1", and "d". (d = don't care").

(Image Omitted)

A sort order value for each product term is established by counting the active (1) OR elements in each product term, as shown in Fig. 1. The product terms are then placed in descending value order, as shown in Table 2. Terms having equal values are placed in the order of their occurrence.

(Image Omitted)

The next step is to pair up each product term with all other product terms for the evaluation of redundancies. A pair consists of a "reference" term and an "evaluated" term. Action starts at the top of the list in Table 2, with the first term as the reference term. Working downwards, it is paired successively with all other terms as the evaluated term. The reference term steps down one line each time all other product terms have been evaluated against it, and the procedure is repeated. With each pairing a comparison is made and any detected redundant elements or terms are deleted. Product terms thus reduced are immediately reflected in Table 2 and are operative in any subsequent evaluations. This pairing process continues until all product terms have been paired against all other product terms. This process is iterated until no further reductions can be made. This can generally be accomplished by the second or third pass through the product term list. At this point Table 2 will contain the final reduced form of all product terms, and the PLA may be modified accordingly. Shown below are four conditional rules with examples. In each pairing evaluation, reductions are made according to these conditional rules applied in sequence one at a time. Once a rule is applied and reductions made, processing continues to the next pair. In these examples, the reference term is the upper one and the evaluated term is t...