# Test Pattern Generation for Shorts in Programmable Logic Arrays

Original Publication Date: 1975-Oct-01

Included in the Prior Art Database: 2005-Mar-02

## Publishing Venue

IBM

## Related People

## Abstract

An algorithm is developed to detect the shorts between two neighboring wires within a programmable logic array (PLA). The most likely physical faults in a PLA are shorts between two neighboring wires and stuck-at faults. A set T(1) of tests to detect stuck-at faults can be generated by previously known techniques (1, 2,). If a set T(2) of tests are added to T(1), that will detect all the neighboring shorts, it would be a very good test set for the PLA as it will detect the most likely physical faults.

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

__Page 1 of 4__**Test Pattern Generation for Shorts in Programmable Logic Arrays **

An algorithm is developed to detect the shorts between two neighboring wires within a programmable logic array (PLA). The most likely physical faults in a PLA are shorts between two neighboring wires and stuck-at faults. A set T(1) of tests to detect stuck-at faults can be generated by previously known techniques (1, 2,). If a set T(2) of tests are added to T(1), that will detect all the neighboring shorts, it would be a very good test set for the PLA as it will detect the most likely physical faults.

Any PLA consists of two arrays. See the figure. Let X(1), X(2),...X(n) e the input lines to the search array. They usually feed into a decoder, i.e., two bit or one-bit partition decoder. The outputs of the decoder will feed into the search array. Let Y(1), Y(2) ,..., Y(f(n)) be the output of the decoder. If the decoder uses only one bit and two-bit partitions, f(n)=2n.

Let p(1),p(2),...,p(g) be the product lines of the search array, such that each product line will be product term of some Y(j). Those product lines will feed into the read array through a driver. Let F(1), F(2),...,F(m) be the output lines of the read array, such that each F(j) line will be a sum of some p(i)0.

Consider the short between two neighboring wires Y(i) and Y(j) (outputs of the decoder and input to the search array). If the personality along Y(i) and Y(j) are the same, then the short is undetectable, but in that case, it is not important as this short will not change the logic of the good circuit. If there exists a product line p such that p contains y(i) but not Y(j), i.e.; p=Y(i) . Y(il) ...Y(ik) where no Y(ip) =Y(j) p=1,...,k, and let p be a term on one output line F=p+p(jl) + ...+p(jl), then set p=1, Y(j)=0 and p(jl) =...=p(jl) =0 by assigning suitable values on Y's, which will assign corresponding values on X's.

If the above conditions cannot be satisfied, then another output line is tried that contains Y(i) but not Y(j). If the conditions cannot be satisfied for any output line that contains y(i) but not Y(j), then find another product line p that contains Y(j) but not Y(i). For that case, assign p/1/=1, Y(i)=0 and other product lines that are on the same output line as p/1/ to be zero.

The test thus generated will be guaranteed to detect the short between Y(i) and Y(j) by observing the output line F that was chosen; if F=1 then no fault exists and if F=0 then a short exists. If the conditions still cannot be satisfied by any product term that contains Y(j) but not Y(i) or vice versa through any output lines, then the short will not change any outputs from being correct. The proof is given below. Any output line F can be written as: F=Y(i) P(1) + Y(j)P(2) + Y(i)Y(j)P(3) + P(4). where P(1), P(2), P(3) and P(4) are the sum of product terms of Y's that do not contain Y(i) or Y(j). They can be empty.

If the short occurs between Y(i) and Y(j), that output line F becomes: F(s)=Y(i)Y(j)P(1) + Y(...