N'TH POWER GALOIS LINEAR GATE

• US 3,805,037 A
• Filed: 03/24/1972
• Issued: 04/16/1974
• Est. Priority Date: 02/22/1972
• Status: Expired due to Term

• Current Assignee: James T. Ellison
• Original Assignee: James T. Ellison
• Inventors: Ellison, James T.
• Primary Examiner(s): Morrison, Malcolm A.
• Assistant Examiner(s): Gottman, James F.
• Application Number:
  US05/237,817
• Time in Patent Office: 753 Days
• Field of Search: 235/152,156,197 340/166R
• US Class Current: 708/492
• CPC Class Codes: E06B 3/01 Removable or disappearing walls for hangars or other halls, e.g. for aircraft wall constructions E04B2/00

Abstract

A configuration of two-level Boolean elements for implementing an n'"'"''"'"'th power Galois linear gate on a single medium scale integrated circuit chip is disclosed. The illustrated configuration includes orthogonally arranged sets of four parallel X input lines and four parallel Y input lines having each of their sixteen intersections intercoupled by a two-input AND gate. The outputs of the AND gates are, in turn, coupled to seven internal EXCLUSIVE OR gates and four output EXCLUSIVE OR gates. A separate Z input line is coupled to each of the four output EXCLUSIVE OR gates for providing the function G(X)G(Y) + G(Z) G(XY + Z).

Claims

1. A Galois linear gate, comprising:

n,X input lines x0, . . . xn 1 and n,Y inpuT lines y0, . . . yn 1 for forming the n2 intersections x0y0, x0y1, . . . xn 1yn 2, xn 1yn 1;

n2, AND gates, a separate one coupled across the X input line and the Y input line of an associated one of said intersections;

a plurality of EXCLUSIVE OR gates;

n,Z input lines z0, . . . zn 1;

each of said n,Z input lines coupled as an input to an associated separate one of n of said EXCLUSIVE OR gates;

means intercoupling said n2, AND gates and said EXCLUSIVE OR gates for generating as the outputs of said n of said EXCLUSIVE OR gates the Galois linear resultant G(XY + Z) (XY + Z)0, . . . (XY + Z)n 1, of the Galois input on said n,X input lines of G(X) x0, . . . xn 1, of the Galois input on said n,Y input lines of G(Y) y0, . . . yn 1, and of the Galois input on said n,Z input lines of G(Z) z0, . . . zn 1.

2. A Galois linear gate, comprising:

a matrix array of n, X input lines x0, . . . xn 1 and n, Y input lines y0, . . . yn 1 for forming the n2 intersections x0y0, x0y1, . . . xn 1yn 2, xn 1yn 1;

n2, two-input AND gates, a separate one having its two inputs coupled across the X input line and the Y input line of an associated one of said n2 intersections;

n, Z input lines z0, . . . zn 1;

a plurality of internal EXCLUSIVE OR gates;

n, output EXCLUSIVE OR gates;

each of said n, Z input lines coupled as an input to an associated separate one of said n, output EXCLUSIVE OR gates;

means intercoupling said AND gates, said plurality of internal EXCLUSIVE OR gates and said n, output EXCLUSIVE OR gates for generating as the outputs of said n, output EXCLUSIVE OR gates the Galois linear resultant G(XY + Z) (XY + Z)0, . . . (XY + Z)n 1, of the Galois input on said n, X input lines of G(X) x0, . . . xn 1, of the Galois input on said n, Y input lines of G(Y) y0, . . . yn 1, and of the Galois input on said n, Z input lines of G(Z) z0, . . . zn 1.

3. A Galois linear gate, comprising:

a matrix array of four, X input lines x0, x1, x2, x3 and four, Y input lines y0, y1, y2, y3 for forming the 16 intersections x0y0, x0y1, x0y2, x0y3, x1y0, x1y1, . . . x3y2, x3y3;

16 two-input AND gates, a separate one having its two inputs coupled across the X input line and the Y input line of an associated one of said 16 intersections;

four, Z input lines z0, z1, z2, z3;

a plurality of internal EXCLUSIVE OR gates;

four, output EXCLUSIVE OR gates;

each of said four, Z input lines coupled as an input to an associated separate one of said four, output EXCLUSIVE OR gates;

means intercoupling the output of said 16 AND gates, said plurality of internal EXCLUSIVE OR gates and said four, output EXCLUSIVE OR gates for generating as the output of said four, output EXCLUSIVE OR gates the GaloiS linear resultant G(XY + Z) (XY + Z)0, (XY + Z)1, (XY + Z)2, (XY + Z)3, of the Galois input on said four, X input lines of G(X) x0, x1, x2, x3, of the Galois product on said four, Y input lines of G(Y) y0, y1, y2, y3 and of the Galois input on said four, Z input lines of G(Z) z0, z1, z2, z3.

4. A Galois linear gate, comprising:

a matrix array of four X input lines x0, x1, x2, x3 and four Y input lines y0, y1, y2, y3 for forming the 16 intersections x0y0, x0y1, x0y2, x0y3, x1y0, x1y1, . . . x3y2, x3y3;

16 AND gates each coupled across the X input line and the Y input line of an associated one of said intersections;

11 EXCLUSIVE OR gates;

means coupling the output of the x2y2 intersection AND gate as a first input of the first of said EXCLUSIVE OR gates;

means coupling the output of the x0y0 intersection AND gate as a first input of the second of said EXCLUSIVE OR gates;

means coupling the output of the x3y3 intersection AND gate as a first input of the third of said EXCLUSIVE OR gates;

means coupling the output of the x1y1 intersection AND gate as a first input of the fourth of said EXCLUSIVE OR gates;

means coupling the output of the x0y1 intersection AND gate as a first input of the fifth of said EXCLUSIVE OR gates;

means coupling the output of the x2y0 intersection AND gate as a first input of the sixth of said EXCLUSIVE OR gates;

means coupling the output of the x3y0 intersection AND gate as a first input of the seventh of said EXCLUSIVE OR gates;

means coupling the output of the x2y1 intersection AND gate as a first input of the eighth of said EXCLUSIVE OR gates;

means coupling the output of the x3y1 intersection AND gate as a first input of the ninth of said EXCLUSIVE OR gates;

means coupling the output of the x3y2 intersection AND gate as a first input of the 10th of said EXCLUSIVE OR gates;

means coupling the outputs of said seventh and eighth EXCLUSIVE OR gates as the first and second, respectively, inputs of the 11th of said EXCLUSIVE OR gates;

means coupling the output of said eleventh EXCLUSIVE OR gate as a second input of said first, said second, said third, and said fourth EXCLUSIVE OR gates;

means coupling the output of the x1y0 intersection AND gate as a second input of the fifth of said EXCLUSIVE OR gates;

means coupling the output of the x0y2 intersection AND gate as the second input of the sixth of said EXCLUSIVE OR gates;

means coupling the output of the x0y3 intersection AND gate as a second input of the seventh of said EXCLUSIVE OR gates;

means coupling the output of the x1y2 intersection AND gate as the second input of the eighth of said EXCLUSIVE OR gates;

means coupling the output of the x1y3 intersection AND gate as a second input of the ninth of said EXCLUSIVE OR gates;

means coupling the output of the x2y3 intersection AND gate as the second input of the 10th of said EXCLUSIVE OR gates;

means coupling the output of the fifth of said EXCLUSIVE OR gates as a third input of the third of said EXCLUSIVE OR gates;

means coupling the output of the sixth of said EXCLUSIVE OR gates as a third input of the fourth of said EXCLUSIVE OR gates;

means coupling the output of the ninth of said EXCLUSIVE OR gates as a third input of the first of said EXCLUSIVE OR gates;

means coupling the output of the tenth of said EXCLUSIVE OR gates as a third input of the second of said EXCLUSIVE OR gates;

four Z input lines z0, z1, z2, z3;

means coupling said Z input line z0 as a fourth input of the first of said EXCLUSIVE OR gates;

means coupling said Z input line z1 as a fourth input of the second of said EXCLUSIVE OR gates;

means coupling said Z input line z2 as a fourth input of the third of said EXCLUSIVE OR gates;

means coupling said Z input line z3 as a fourth input of the fourth of said EXCLUSIVE OR gates.

5. The improvement that converts a Galois multiplication gate, which Galois multiplication gate generates the Galois product G(XY) (XY)0, . . . (XY)n 1 as the output of n, output EXCLUSIVE OR gates from the Galois input on n, X input lines of G(X) x0, . . . xn 1 and from the Galois input on n, Y input lines of G(Y) y0, . . . yn 1, to a Galois linear gate, comprising:

n, Z input lines, a separate one coupled as an input to an associated separate one of said n, output EXCLUSIVE OR gates for generating as the output of said n, output EXCLUSIVE OR gates the Galois linear resultant G(XY + Z) (XY + Z)0, . . . (XY + Z)n 1.