US3784977A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Self-testing checking circuit
Assignee: International Business Machines Corp
•
Filing: 1972-06-20
•
Granted: 1974-01-08
•
Expires: 1992-06-20
Abstract
Abstract There is disclosed a self-testing checking circuit which checks that greater than or equal to k out of n input variables are 1. This circuit has the output (1,0) or (0,1) if the > OR = k condition is satisfied and the output (0,0) or (1,1) if it is not. The circuit is self-testing, i.e., every line other than the primary inputs is tested during normal operation. The logical equation representing this circuit is (CK,N,DK,N) (AN.EK,N 1(A1,A2, . . . ,AN 1),AN.EK 1,N 1(A1,A2, . . . ,AN 1)) WHEREIN A1, . . . ,AN ARE THE N INPUT VARIABLES, EK,N,(A1,A2, . . . ,AN) DENOTES THE FUNCTION WITH THE THRESHOLD K, THE FUNCTION BEING 1 IF GREATER THAN OR EQUAL TO K OF THE N INPUT VARIABLES A1,A2, . . . ,AN ARE 1. It is suitably implemented as an OR circuit of (k) AND circuits, each of the latter AND circuits being a conjunct constituted by k of the n input variables. The function (ck,ndk,n) is a two-output threshold k function, i.e., it is (0,1) or (1,0) if greater than or equal to k out of the n input variable are 1 and (0,0) otherwise. Logical equations representing the two output k threshold function are CK,N ANA1A2 . . . AKVANA1A2 . . . AK 1AK 1V . . . VANAN K . . . AN 1 DK,N ANA1A2 . . . AK 1 V ANA1A2 . . . AK 2AK V . . . V ANAN K 1 . . . AN 1 WHEREIN V REPRESENTS THE OR function. A two-output self-testing circuit which checks for less than or equal to k out of n input variables equal to 1 is represented by the following logical equation (GK,N,HK,N) (ANVFN K,N 1(A1, . . . , AN 1), ANVFN K 1,N 1 (A1, . . . , AN 1)) WHEREIN (GK,N, HK,N) IS THE TWO OUTPUT THRESHOLD WHICH IS (0,1) OR (1,0) IF LESS THAN OR EQUAL TO K OUT OF N INPUT VARIABLES ARE 1, A1, . . . ,AN ARE THE INPUT VARIABLES, FK,N IS THE FUNCTION WITH THE THRESHOLD K, I.E., IT IS 0 IF GREATER THAN OR EQUAL TO K OUT OF N INPUTS ARE 0. The function fk,n is represented by the following equation FK,N (A V A2 V A2 V . . . V AK) (A1VA2V . . . VAK 1VAK 1) . . . (AN K 1V . . . VAN) WHICH COMPRISES (K) OR circuits providing inputs to an AND circuit, each OR circuit being constituted by a disjunct of k input variables. By providing the outputs of both of the twooutput circuits mentioned above to a morphic AND circuit, there is provided a circuit which indicates whether greater than or equal to i of the input variables and less than or equal to k of the input variables are 1. When this condition is obtained, the output of the morphic AND circuit is either (0,1) or (1,0).
Inventors
- 👤 W Carter
- 👤 A Wadia
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 10:09
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/085; H; H03; H03K; H03K19/00; H03K19/007; H03K19/0075
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
158 words
A self-testing circuit which checks that greater than or equal to k out of n input variables are 1 comprising: a circuit represented by the following logical equation (ck,n,dk,n) (an.ek,n 1(a1,a2, . . . ,an 1), an.ek 1,n 1(a1,a2, . . . ,an 1)) wherein a1, . . . ,an are said input variables, ek,n is a function which is implemented by a circuit comprising (k) AND circuits, feeding an OR circuit, wherein (k) for 0 < OR = k < OR = n being defined as the number of combinations of n elements taken k at a time, which is equal to the integer n(n1) . . . (n-k+1)/(1.2 . . . k), each of said last named AND circuits being a conjunct composed of k of the n input variables, and wherein (ck,n,dk,n) (0,1) or (1,0) if greater than or equal to k out of n input variables are 1 and (0,0) if it is not.
Claim 2
Dependent Claim
158 words
A self-testing circuit which checks that greater than or equal to k out of n input variables are 1 comprising: a circuit represented by the following logical equation (ck,n,dk,n) (an.ek,n 1(a1,a2, . . . ,an 1), an.ek 1,n 1(a1,a2, . . . ,an 1)) wherein a1, . . . ,an are said input variables, ek,n is a function which is implemented by a circuit comprising (k) AND circuits, feeding an OR circuit, wherein (k) for 0 < OR = k < OR = n being defined as the number of combinations of n elements taken k at a time, which is equal to the integer n(n1) . . . (n-k+1)/(1.2 . . . k), each of said last named AND circuits being a conjunct composed of k of the n input variables, and wherein (ck,n,dk,n) (0,1) or (1,0) if greater than or equal to k out of n input variables are 1 and (0,0) if it is not.
Claim 3
Dependent Claim
236 words
A self-testing circuit which checks that greater than or equal to k out of n input variables are 1 comprising: a circuit represented by the following logical equation (ck,n,dk,n) (an.ek,n 1(a1,a2, . . . ,an 1), an.ek 1,n 1(a1,a2, . . . ,an 1)) wherein a1, . . . ,an are said input variables, ek,n is a function which is implemented by a circuit of (k) AND circuits, feeding an OR circuit, wherein (k) for 0 < or = k < or = n being defined as the number of combinations of n elements taken k at a time, which is equal to the integer n(n-1) . . . (n-k+1)/(1.k . . . k), each of said AND circuits being a conjunct of k of the n input variables and (ck,n,dk,n) is a two-output threshold k function which is (0,1) or (1,0) if greater than or equal to k out of said n input variables are 1, and (0,0) if otherwise, said two output threshold k function being represented by the following logical equations ck,n ana1a2 . . . akvana1a2 . . . ak 1ak 1v . . . vanan k . . . an 1 and dk,n ana1a2 . . . ak 1vana1a2 . . . ak 2akv . . . vanan k 1 . . . an 1 wherein a1, . . . ,an have their previous significance and v represents the OR function.
Claim 4
Dependent Claim
236 words
A self-testing circuit which checks that greater than or equal to k out of n input variables are 1 comprising: a circuit represented by the following logical equation (ck,n,dk,n) (an.ek,n 1(a1,a2, . . . ,an 1), an.ek 1,n 1(a1,a2, . . . ,an 1)) wherein a1, . . . ,an are said input variables, ek,n is a function which is implemented by a circuit of (k) AND circuits, feeding an OR circuit, wherein (k) for 0 < or = k < or = n being defined as the number of combinations of n elements taken k at a time, which is equal to the integer n(n-1) . . . (n-k+1)/(1.k . . . k), each of said AND circuits being a conjunct of k of the n input variables and (ck,n,dk,n) is a two-output threshold k function which is (0,1) or (1,0) if greater than or equal to k out of said n input variables are 1, and (0,0) if otherwise, said two output threshold k function being represented by the following logical equations ck,n ana1a2 . . . akvana1a2 . . . ak 1ak 1v . . . vanan k . . . an 1 and dk,n ana1a2 . . . ak 1vana1a2 . . . ak 2akv . . . vanan k 1 . . . an 1 wherein a1, . . . ,an have their previous significance and v represents the OR function.
Claim 5
Dependent Claim
193 words
A self-testing circuit which checks that less than or equal to k out of n input variables are 1 comprising: a circuit represented by the following equation (gk,n,hk,n) (anfn k,n 1(a1, . . . ,an 1),anfn k 1,n 1(a1, . . . ,an 1)) wherein a1, . . . ,an are said input variables, and the function fn k,n 1 is represented by the equation fn k 1,n 1 (a1va2v . . . an k 1) (a1va2v . . . van k 2van k) . . . (ak 1, . . . ,an 1) wherein v represents the OR function, and which comprises (n k 1) OR circuits feeding a single AND circuit, said term (n k 1) being equivalent to the term (j) for 0 < or = j < or = i which is defined as the number of combinations of i objects taken j at a time which is equal to the integer i(i-1) . . . (i-j+1)/(1.. . . j), each circuit being constituted by a disjunct of n-k-1 input variables; said function (gk,n,hk,n) being (0,1) or (1,0) if said k or less of said input variables are 1.
Claim 6
Dependent Claim
193 words
A self-testing circuit which checks that less than or equal to k out of n input variables are 1 comprising: a circuit represented by the following equation (gk,n,hk,n) (anfn k,n 1(a1, . . . ,an 1),anfn k 1,n 1(a1, . . . ,an 1)) wherein a1, . . . ,an are said input variables, and the function fn k,n 1 is represented by the equation fn k 1,n 1 (a1va2v . . . an k 1) (a1va2v . . . van k 2van k) . . . (ak 1, . . . ,an 1) wherein v represents the OR function, and which comprises (n k 1) OR circuits feeding a single AND circuit, said term (n k 1) being equivalent to the term (j) for 0 < or = j < or = i which is defined as the number of combinations of i objects taken j at a time which is equal to the integer i(i-1) . . . (i-j+1)/(1.. . . j), each circuit being constituted by a disjunct of n-k-1 input variables; said function (gk,n,hk,n) being (0,1) or (1,0) if said k or less of said input variables are 1.
Claim 7
Dependent Claim
439 words
A self-testing arrangement which checks that greater than or equal to i and less than or equal to k of n input variables are 1 comprising: a first circuit represented by the following logical equation (ci,n,di,n) (an.ei,n 1(a1,a2, . . . ,an 1),anei 1,n 1(a1,a2, . . . ,an 1)) wherein ci,n is a function which is implemented by an OR circuit fed by (i) AND circuits, said term (i) for 0 < or = i < or = n is defined as the number of combinations of n elements taken i at a time, which is equal to the integer n(n-1) . . . (n-i+1)/(1.2 . . . i), each of said AND circuits being a conjunct of i of the n input variables, a1, . . . ,an are said input variables, said ci,n function being a circuit represented by the followIng equation ci,n ana1a2 . . . aivana1a2 . . . ai 1ai 1v . . . vanan i . . . an 1 wherein a1, . . . ,an are said n input variables and v represents the OR function, said di,n function being a circuit represented by the following equation di,n ana1a2 . . . ai 1vana1a2 . . . ai 2aiv . . . vanan i 1 . . . an 1 wherein a1, . . . ,an are said input variables and v represents the OR function; a second circuit represented by the following equation (gk,n,hk,n) (anvfn k,n 1(a1, . . . ,an 1),anvfn k 1,n 1(a1, . . . ,an 1)) wherein a1 . . . an are said n input variables, v represents the OR function and fk,n is a function that is 0 if greater than or equal to k out of n inputs are 0, said function fk,n being a circuit represented by the equation fk,n (a1va2v . . . vak) (a1va2v . . . ak 1vak 1) . . . (an k 1, . . . ,an) wherein a1, . . . ,an are said input variables and v represents the OR function and wherein said last-named circuit comprises (k) OR circuits feeding a single AND circuit, said term (k) for 0 < or = k < or = n being defined as the number of combinations of n elements taken k at a time, which is equal to the integer n(n-1) . . . (n-k+1)/(1.2 . . . k), each of said last-named OR circuits being constituted by a disjunct of k input variables; and a morphic AND circuit for receiving the outputs of said first and second circuits to provide a single self-testing output pair.
Claim 8
Dependent Claim
439 words
A self-testing arrangement which checks that greater than or equal to i and less than or equal to k of n input variables are 1 comprising: a first circuit represented by the following logical equation (ci,n,di,n) (an.ei,n 1(a1,a2, . . . ,an 1),anei 1,n 1(a1,a2, . . . ,an 1)) wherein ci,n is a function which is implemented by an OR circuit fed by (i) AND circuits, said term (i) for 0 < or = i < or = n is defined as the number of combinations of n elements taken i at a time, which is equal to the integer n(n-1) . . . (n-i+1)/(1.2 . . . i), each of said AND circuits being a conjunct of i of the n input variables, a1, . . . ,an are said input variables, said ci,n function being a circuit represented by the followIng equation ci,n ana1a2 . . . aivana1a2 . . . ai 1ai 1v . . . vanan i . . . an 1 wherein a1, . . . ,an are said n input variables and v represents the OR function, said di,n function being a circuit represented by the following equation di,n ana1a2 . . . ai 1vana1a2 . . . ai 2aiv . . . vanan i 1 . . . an 1 wherein a1, . . . ,an are said input variables and v represents the OR function; a second circuit represented by the following equation (gk,n,hk,n) (anvfn k,n 1(a1, . . . ,an 1),anvfn k 1,n 1(a1, . . . ,an 1)) wherein a1 . . . an are said n input variables, v represents the OR function and fk,n is a function that is 0 if greater than or equal to k out of n inputs are 0, said function fk,n being a circuit represented by the equation fk,n (a1va2v . . . vak) (a1va2v . . . ak 1vak 1) . . . (an k 1, . . . ,an) wherein a1, . . . ,an are said input variables and v represents the OR function and wherein said last-named circuit comprises (k) OR circuits feeding a single AND circuit, said term (k) for 0 < or = k < or = n being defined as the number of combinations of n elements taken k at a time, which is equal to the integer n(n-1) . . . (n-k+1)/(1.2 . . . k), each of said last-named OR circuits being constituted by a disjunct of k input variables; and a morphic AND circuit for receiving the outputs of said first and second circuits to provide a single self-testing output pair.
References Cited (Backward Citations)
US3559167A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1977-01-07 | 1977-07-09 | 1978-01-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1981-01-07 | 1981-07-09 | 1982-01-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1985-01-07 | 1985-07-09 | 1986-01-08 | $7700.00 | Window Closed / Lapsed |