Browse Prior Art Database

Exclusive or Reduction Algorithm

IP.com Disclosure Number: IPCOM000060968D
Original Publication Date: 1986-Jun-01
Included in the Prior Art Database: 2005-Mar-09
Document File: 4 page(s) / 44K

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...