Browse Prior Art Database

Decreasing the Size of Associative Logic Arrays

IP.com Disclosure Number: IPCOM000082071D
Original Publication Date: 1974-Sep-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Roth, JP: AUTHOR

Abstract

In the realization of digital functions in associative logic arrays, although the number of levels classically associated with such arrays has been two, it is sometimes expedient to render the logic in three levels rather than two. Associative logic arrays were originally known as "cubical covers" which are described in the publications "Computer Design/1", J. P. Roth, BA 45, December 22, 1972 and "Computer Design Architecture II", J. P. Roth, BA 48, March 1, 1973, both RA 45 and RA 48 being published by the IBM Corporation.

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

Page 1 of 2

Decreasing the Size of Associative Logic Arrays

In the realization of digital functions in associative logic arrays, although the number of levels classically associated with such arrays has been two, it is sometimes expedient to render the logic in three levels rather than two. Associative logic arrays were originally known as "cubical covers" which are described in the publications "Computer Design/1", J. P. Roth, BA 45, December 22, 1972 and "Computer Design Architecture II", J. P. Roth, BA 48, March 1, 1973, both RA 45 and RA 48 being published by the IBM Corporation.

In the technique described herein, the problem of rendering a cubical cover,
i.e., associative logic array in three levels is formulated in terms of factoring the cubes. The cubes which are referred to are called associative cubes or singular cubes. They have an input portion as well as an output portion. Each variable input or output is associated with some condition or circumstance associated with a function being rendered. The associative aspect signifies that if the conditions are met in the input portion, then the conditions will be met on the output.

When an arithmetic logic unit (ALU) with 4-bit byte arguments is implemented in an associative logic array, factoring by hand and permitting third-level functions of exactly two variables, the technique described herein enables the reducing of the number of cubes, and hence the size of the associative logic array by a factor of two. The technique, accordingly, is a description of a formal procedure for obtaining a minimal implementation in three levels.

The technique is essentially constituted of two portions. One of these portions involves a product suitably termed the "combo product" of two cubes. It seeks pairs of cubes which have the property in that they differ in precisely two coordinates. The combo product is defined such that each of the possible differences in the two coordinates in which they differ, can be identified. For example, 1x would be A; x1, B; 01, C; 10, D; 0x, E; and x0, F.

The combo product then of two or more cubes (there could be three which would so combine) contains all of the information contained in the original cubes so combined. Consequently, they may be eliminated from subsequent combinations, except for the fact that one particular cube is combined and "combo produced" with more than one other cube and, therefore, the question would be which of the various combo products to use to cover the original cube.

It is to be noted that such formulation amounts to a covering problem in the classical sense, as discussed in the above referred to RA 45 publication, pp. 2- 46. In this formulation, the cubes themselves may be thought of as vertices and the combo products as 1-cubes having the appropriate subcubes as vertices.

In the carryin...