Browse Prior Art Database

Truth Tables for Operating On Expressions of More than Five Variables

IP.com Disclosure Number: IPCOM000102315D
Original Publication Date: 1990-Nov-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 5 page(s) / 131K

Publishing Venue

IBM

Related People

Halbert, AR: AUTHOR [+2]

Abstract

The use of truth-tables and relevance-tables for redundant primitive elimination is published in a European Patent Application EP-A-339778. Two implementations are discussed, one in hardware and one in software. The software implementation is limited to five variables in 32-bit register machines. This disclosure extends the implementation to more variables, conveniently to 11, but easily extendable to more. For convenience the IBM System/370 instruction set is used.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 44% of the total text.

Truth Tables for Operating On Expressions of More than Five Variables

       The use of truth-tables and relevance-tables for
redundant primitive elimination is published in a European Patent
Application EP-A-339778.  Two implementations are discussed, one in
hardware and one in software.  The software implementation is limited
to five variables in 32-bit register machines.  This disclosure
extends the implementation to more variables, conveniently to 11, but
easily extendable to more.  For convenience the IBM System/370
instruction set is used.

      The original algorithm uses the following register and
register- storage operations:

                            (Image Omitted)

      (Sometimes an XOR and LTR may be replaced by a comparison, or
the condition code will be set from a previous instruction without
needing the LTR.)

      The extension of most of these operations for truth-tables up
to 2**11 bits = 256 bytes is straightforward.

      The only problem is the SHIFT operation, used to match up
corresponding u-true and u-false bits:

      Shifts of 2**n bits, n > = 3:

      Shifts are all of 2**n bits, for integer n.  For n > = 3,
2 **n bits is an integral number of bytes.  We may either:
(i)  perform an MVC, or
(ii) remember that the shift should have occurred, and offset the
operation of subsequent operations (virtual shift).  We use the
virtual shift in the examples below.

      Note :  The key to this disclosure is that the original
algorithm does not require all the data generated by a shift.
Shifting is performed to align corresponding u-true and u-false parts
of a truth-table.  When it shifts left to move u-true data into
u-false positions, for some primitive u, the data that is shifted
into the u-true position is irrelevant,  as it is always subsequently
masked out.  A similar argument applies to right shifts.

      Shifts of 2**n Bits, n < 3:

      As a consequence of the above observation we may use a
translate instruction to perform shifts of 1, 2 and 4 bits. Six
translate tables are needed, for left and right of 1, 2 and 4 bits.

      In many cases, the same translate instruction can also be used
to perform logical operations that follow the shift in the register
case.

      Code Examples:

      In all the following examples, we assume that we have a truth-
table TT of length N bytes.  The i'th primitive is to be checked,
implying that the corresponding true and false parts of the table are
offset by 2**(i-1) bits = S bits = SB bytes.

      The examples show how the contents of tables such as STRUE,
TESTS and STOTRUE are worked out for S = 2 or S = 16. The
values for tables for other values of S follow.

      The code is discussed in two sections:  the basic case where
relevance-tables are not used, and the extended case using relevance-
tables.
1.   Basic Code

      This section discusses the code wh...