US3711692A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Determination of number of ones in a data field by addition
Assignee: Lockheed Martin Tactical Systems Inc
•
Filing: 1971-03-15
•
Granted: 1973-01-16
•
Expires: 1991-03-15
Abstract
Abstract An arrangement for counting the number of a given data such as ones in a data field. The system employs full adders which count the number of ones in basic three element subsets of the data field. Additional full adders total the results of the first series of full adders and also count any additional ones of the data field.
Inventors
- 👤 K Batcher
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 13:09
CPC Classifications
G; G11; G11C; G11C15/00; G11C15/04; G06; G06F; G06F7/00; G06F7/60; G06F7/607
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
269 words
The method of determining the number of occuRrences of a selected value in a data field having at least fifteen elements, which comprises the steps of 1. dividing the data field into mutually exclusive, exhaustive subsets S1, S2, and S3, where S2 and S3 are of equal length and S1 includes at most one element of the data field; 2. counting the occurrences of the selected value in each of the subsets S2 and S3; 3. adding, by means of a full adder, the number of occurrences of the selected value in subset S1 and the least significant digit of the count of each of the subsets S2 and S3; 4. adding, by means of an additional full adder, the most significant digit of the output of the previous full adder and the next significant digit of the count of each of the subsets S2 and S3; 5. repeating step (4) until all the digits of the count of each of the subsets S2 and S3 have been exhausted, an additional full adder being employed for each addition; and 6. transmitting to an output device the least significant digit of the output of each full adder and both digits of the output of the last full adder, the least significant digit of the output of the first full adder being the least significant digit of the total count, the least significant digits of the outputs of successive full adders being the successive digits of the full count, and the most significant digit of the output of the final full adder being the most significant digit of the full count.
Claim 2
Independent Claim
269 words
The method of determining the number of occuRrences of a selected value in a data field having at least fifteen elements, which comprises the steps of 1. dividing the data field into mutually exclusive, exhaustive subsets S1, S2, and S3, where S2 and S3 are of equal length and S1 includes at most one element of the data field; 2. counting the occurrences of the selected value in each of the subsets S2 and S3; 3. adding, by means of a full adder, the number of occurrences of the selected value in subset S1 and the least significant digit of the count of each of the subsets S2 and S3; 4. adding, by means of an additional full adder, the most significant digit of the output of the previous full adder and the next significant digit of the count of each of the subsets S2 and S3; 5. repeating step (4) until all the digits of the count of each of the subsets S2 and S3 have been exhausted, an additional full adder being employed for each addition; and 6. transmitting to an output device the least significant digit of the output of each full adder and both digits of the output of the last full adder, the least significant digit of the output of the first full adder being the least significant digit of the total count, the least significant digits of the outputs of successive full adders being the successive digits of the full count, and the most significant digit of the output of the final full adder being the most significant digit of the full count.
Claim 3
Dependent Claim
194 words
The method according to claim 1 wherein the count of each multiple element subset of the data field is determined by the steps of: a. dividing the subset into three mutually exclusive, exhaustive subsets, the first of which has at most one element, a second and third of which are of equal length; b. determining if any subset produced in the immediately preceeding division contains more than three elements; c. dividing all elements produced in the immediately preceeding division which contain more than three elements into three subsets satisfying the conditions of step (a); d. repeating steps (b) and (c) until an ultimate series of subsets no one of which contains more than three elements is obtained; e. summing, by means of full adders, the number of occurrences of the selected value of each ultimate subset having more than one element; and f. by means of additional full adders, progressively combining and adding to the sums the number of occurrences of the selected value in those subsets having one element in the reverse order of their creation in steps (a) through (d) until the total count of each multiple element subset has been achieved.
Claim 4
Dependent Claim
15 words
counting the occurrences of the selected value in each of the subsets S2 and S3;
Claim 5
Dependent Claim
15 words
counting the occurrences of the selected value in each of the subsets S2 and S3;
Claim 6
Dependent Claim
34 words
adding, by means of a full adder, the number of occurrences of the selected value in subset S1 and the least significant digit of the count of each of the subsets S2 and S3;
Claim 7
Dependent Claim
34 words
adding, by means of a full adder, the number of occurrences of the selected value in subset S1 and the least significant digit of the count of each of the subsets S2 and S3;
Claim 8
Dependent Claim
189 words
Apparatus for counting the number of occurrences of a predetermined value in a data field of at least fifteen elements, comprising: first and second counting means for counting the number of occurrences in first and second portions, respectively, of the data field, the first and second portions being non-overlapping, of equal length, and including at least all but one element of the data field; a first full adder receiving as inputs the value of the data field element excluded from the first and second portions and the least significant digits of the output of the first and second counting means; additional full adders receiving as inputs, respectively, the more significant digit output of the preceeding full adder and the succeedingly more significant digits of the outputs of the first and second counting means; and an output device receiving the least significant digit outputs of each full adder and the most significant digit output of the final full adder, the output of the first full adder being the least significant digit of the total and the outputs of successive full adders being the successively more significant digits of the total.
Claim 9
Dependent Claim
189 words
Apparatus for counting the number of occurrences of a predetermined value in a data field of at least fifteen elements, comprising: first and second counting means for counting the number of occurrences in first and second portions, respectively, of the data field, the first and second portions being non-overlapping, of equal length, and including at least all but one element of the data field; a first full adder receiving as inputs the value of the data field element excluded from the first and second portions and the least significant digits of the output of the first and second counting means; additional full adders receiving as inputs, respectively, the more significant digit output of the preceeding full adder and the succeedingly more significant digits of the outputs of the first and second counting means; and an output device receiving the least significant digit outputs of each full adder and the most significant digit output of the final full adder, the output of the first full adder being the least significant digit of the total and the outputs of successive full adders being the successively more significant digits of the total.
Claim 10
Dependent Claim
19 words
Apparatus according to claim 3 wherein the first and second counting means each comprise a plurality of full adders.
Claim 11
Dependent Claim
36 words
adding, by means of an additional full adder, the most significant digit of the output of the previous full adder and the next significant digit of the count of each of the subsets S2 and S3;
Claim 12
Dependent Claim
36 words
adding, by means of an additional full adder, the most significant digit of the output of the previous full adder and the next significant digit of the count of each of the subsets S2 and S3;
Claim 13
Dependent Claim
31 words
repeating step (4) until all the digits of the count of each of the subsets S2 and S3 have been exhausted, an additional full adder being employed for each addition; and
Claim 14
Dependent Claim
31 words
repeating step (4) until all the digits of the count of each of the subsets S2 and S3 have been exhausted, an additional full adder being employed for each addition; and
Claim 15
Dependent Claim
55 words
Apparatus according to claim 4 wherein the full adders comprising each counting means are arranged in a plurality of series, the full adders of the first series counting the occurrences in two to three element subsets of the portion, the full adders of successive series combining the totals of the previous series of full adders.
Claim 16
Dependent Claim
89 words
transmitting to an output device the least significant digit of the output of each full adder and both digits of the output of the last full adder, the least significant digit of the output of the first full adder being the least significant digit of the total count, the least significant digits of the outputs of successive full adders being the successive digits of the full count, and the most significant digit of the output of the final full adder being the most significant digit of the full count.
Claim 17
Dependent Claim
89 words
transmitting to an output device the least significant digit of the output of each full adder and both digits of the output of the last full adder, the least significant digit of the output of the first full adder being the least significant digit of the total count, the least significant digits of the outputs of successive full adders being the successive digits of the full count, and the most significant digit of the output of the final full adder being the most significant digit of the full count.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1976-01-16 | 1976-07-17 | 1977-01-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1980-01-16 | 1980-07-17 | 1981-01-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1984-01-16 | 1984-07-17 | 1985-01-16 | $7700.00 | Window Closed / Lapsed |