Browse Prior Art Database

Algorithm for Computing an Almost Minimum Cover

IP.com Disclosure Number: IPCOM000079134D
Original Publication Date: 1973-May-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 16K

Publishing Venue

IBM

Related People

Roth, JP: AUTHOR

Abstract

In the Research Report, RC-2007, February 6, 1968, published by the IBM Corporation, there is described a calculus and an algorithm for the problem: given a function mapping strings of binary digits into strings of binary digits, find a "2-level implementation" (or cover) having a minimum cost, cost being computed according to a relatively general cost function. This algorithm is precise and provides a precisely minimum cover. However, because of the complexity of the procedure, the extent of the calculation both in space and time requirements, particularly for large problems, may be prohibitive.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 41% of the total text.

Page 1 of 3

Algorithm for Computing an Almost Minimum Cover

In the Research Report, RC-2007, February 6, 1968, published by the IBM Corporation, there is described a calculus and an algorithm for the problem: given a function mapping strings of binary digits into strings of binary digits, find a "2-level implementation" (or cover) having a minimum cost, cost being computed according to a relatively general cost function. This algorithm is precise and provides a precisely minimum cover. However, because of the complexity of the procedure, the extent of the calculation both in space and time requirements, particularly for large problems, may be prohibitive.

The algorithm described herein and hereinafter referred to as ALMOST, is an algorithm to compute a cover of almost minimum cost for any multiple input multiple output function of binary digits. The above referred-to report RC-2007 describes an exact algorithm suitably termed extraction algorithm wherein, given a multiple input multiple output function described by a two-level cubical array or cover, the extraction algorithm obtains another cover of the function having a minimum "cost", where cost is computed in accordance with any number of criteria such as, for example, the number of cubes, the number of 1's and 0's in each cube. These criteria may be weighted in accordance with the dictates of the technology.

The extraction algorithm, has been embodied in a PL/I program known as MIN/360. It has been run on the Model 91 of IBM System 360, and has proven to be effective in a computational sense. The extraction algorithm obtained a minimum where previous algorithms were not able to so obtain, regardless of the size of the circuit.

Practical problems using the extraction algorithm run into an extensive number of variables. The program itself is capable of handling problems up to 32 inputs and 32 outputs. Time limitations (but never space) often, however, prevent the obtaining of a solution much above ten inputs and ten outputs.

The algorithm, ALMOST, described herein is a fast approximation to the exact minimization algorithm. Where the extraction algorithm may take one hundred hours, for certain problems, on a computer such as IBM 360/91, ALMOST can obtain a "near minimum" in less than one minute. The running time of ALMOST is roughly a linear function of the number of cubes and the number of coordinates in each cube. Thus, as the size of the problem increases, the running time of the problem increases only linearly with the change. While ALMOST does not in general compute an exact minimum, experience has shown that it may deviate from the minimum from zero to about ten percent.

Prior to describing the algorithm, ALMOST, there is described the cubical notation for describing a function. Let there be assumed a function having r binary inputs and s binary outputs.

The function itself is defined by a set of "singular cubes", this set being termed a "cover". Each singular cube or "cube" consists...