Browse Prior Art Database

Heuristic Algorithm for Maximizing Subarrays Extracted from a Source Array

IP.com Disclosure Number: IPCOM000080161D
Original Publication Date: 1973-Nov-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 2 page(s) / 64K

Publishing Venue

IBM

Related People

Dubil, JF: AUTHOR

Abstract

Given an NxM source array of elements, some of which are nonuseable or defective, this algorithm locates the maximum or near maximum, number of SxT subarrays which can be extracted from the source arrays. The subarrays can appear horizontally and/or vertically and will contain no defective elements. The algorithm is applicable to any pattern shape whose boundaries are horizontally and vertically identifiable.

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

Page 1 of 2

Heuristic Algorithm for Maximizing Subarrays Extracted from a Source Array

Given an NxM source array of elements, some of which are nonuseable or defective, this algorithm locates the maximum or near maximum, number of SxT subarrays which can be extracted from the source arrays. The subarrays can appear horizontally and/or vertically and will contain no defective elements. The algorithm is applicable to any pattern shape whose boundaries are horizontally and vertically identifiable.

An operation 10 stores geometrical data descriptive of a source array, e.g., LS1 devices in a semiconductor wafer. The data also identifies those devices that are useable and those devices that are not useable or defective. Data is also stored of the subarray or pattern that is to be extracted from the source array. Since defective elements are likely to occur anywhere within the source array, the entire source array is initially scanned to determine all possible placements of the subarray pattern whose encompassed elements satisfy the definition of acceptability in a decision 12. The source array is scanned once using the pattern array in a horizontal placement sequence, and then again using the pattern array in a vertical placement sequence. The decision 12 creates hit matrices for the horizontal placement sequence (HH) and vertical placement sequence (HV). The hit matrices identify the start point of a subarray of good devices.

In forming the HH and HV matrices, an operation 14 stores a 0 in the source array when a start point in the source array will not complete the requirements of the pattern array. An o...