# Exclusive or Reduction Algorithm

Original Publication Date: 1986-Jun-01

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

## Publishing Venue

IBM

## Related People

Savir, J: AUTHOR [+3]

## Abstract

This algorithm determines a reduced implementation of a multiple-input multiple-output exclusive-OR network when limited by technology to a two-input exclusive-OR gate. The steps involved in each iteration of the exclusive-OR reduction algorithm are outlined below. What follows is a detailed description of each step preceded by definitions of terms and variables used in the description. STEPS 1. Create the output matrix. 2. Determine the most frequently occurring combinations. 3. Determine the disjoint combinations. 4. Replace the disjoint combinations with pseudo-inputs. 5. Save the pseudo-input information in the save matrix 6. Check if each output is a function of only one input yes no solution DEFINITION OF TERMS Exclusive-OR - Logical function described by modulo-two addition and denoted by O.**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 44% of the total text.**

__Page 1 of 4__**Exclusive or Reduction Algorithm **

This algorithm determines a reduced implementation of a
multiple-input multiple-output exclusive-OR network when limited by
technology to a two-input exclusive-OR gate. The steps involved in
each iteration of the exclusive-OR reduction algorithm are outlined
below. What follows is a detailed description of each step preceded
by definitions of terms and variables used in the description. STEPS

1. Create the output matrix. 2. Determine the most frequently
occurring combinations. 3. Determine the disjoint combinations. 4.
Replace the disjoint combinations with pseudo-inputs. 5. Save the
pseudo-input information in the save matrix 6. Check if each output
is a function of only one input yes no solution DEFINITION OF TERMS
Exclusive-OR - Logical function described by modulo-two addition and
denoted by O. The output of a two-input exclusive-OR is a logical 1
if only one of the two inputs is at a logical 1 value. All other
input conditions produce a logical 0 at the output. Combination -
Any two-input exclusive-OR possibility that occurs in the network.
Pseudo-Input - The output of a combination determined to have
occurred most frequently in the network for a given iteration.

Replaces every occurrence of that combination in the network. This is the fundamental element of the reduction algorithm. ***** SEE OROGINAL DOCUMENT ***** OUTPUTS Disjoint -Two combinations are disjoint if removing all occurrences of one combination from the network does not eliminate any occurrence of the other combination in the network. Output Matrix- M x N logical matrix describing an N input, M output exclusive-OR network. Save Matrix - Matrix describing the pseudo-inputs created. DEFINITION OF VARIABLES N = Number of inputs to the XOR network. M = Number of outputs from the XOR network. a(i,j) = The (i,j)th coefficient of the output matrix that relates input j to output i. 1 if output i is a function of input j 0 if output i is not a function of input j S(i,1) =

The (i,1) element of the save matrix which represents the
pseudo-input number. S(i,2) = The (i,2) element of the save matrix
which indicates the first input, primary or pseudo, of the
combination for pseudo-input i. S(i,3) = The (i,3) element of the
save matrix which indicates the second input, primary or pseudo, of
the combination for pseudo-input i. Detailed Procedure for
Determining Reduced Network In general, any N input M output
exclusive-OR network can be described by M equations: y(1) =
a(1,1)x(1) O a(1,2)x(2) O . . . O a(1,N)x(N) y(2) = a(2,1)x(1) O
a(2,2)x(2) O . . . O a(2,N)x(N) y(3) = a(3,1)x(1) O a(3,2)x(2) O . .

. O a(3,N)x(N) y(M) = a(M,1)x(1) O a(M,2)x(2) O . . . O a(M,N)x(N) 1.

CREATE THE OUTPUT MATRIX The "a" coefficients of the M output equations define the output matrix where: a(i,j) e {0,1} i=1,2,...,M; j=1,2,...,N 2. DETERMINE THE MOST FREQUENTLY OCCURRING COMBINATIONS By multiplying the output matrix with its transpose, the elements of the resultin...