Patent US4077034A successfully refreshed from Google Patents.
US4077034A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data compression
Assignee: Individual
•
Filing: 1974-11-04
•
Granted: 1978-02-28
•
Expires: 1994-11-04
Abstract
Abstract A data compression apparatus is described having an encoder and a decoder. Data in the form of an N-bit data message from an external data source is received in the encoder and stored in an N-bit memory. Coupled to the memory is a "one's" detector and three arithmetic units. The "one's" detector counts the number of logical "one's" in the N-bit message irrespective of their position in the memory for generating a number Q. The three arithmetic units sum columns of the contents of the memory in three predetermined sequences for generating three numbers A, B and C. The numbers A, B, C and Q are then used to form a P-bit data message, where P is less than N for a sufficiently large N - e.g., for N=256, N/P is approximately 2.8 - for transmission to the decoder. The decoder is provided with an N-bit memory, three arithmetic units and a comparison circuit. Upon receipt of the P-bit data message, Q logical "one's" are stored in the decoder memory. The arithmetic units in the decoder, as in the encoder, sum columns of the contents of the decoder memory in three sequences for generating three numbers A', B' and C'. The numbers A', B', and C' are compared with the numbers A, B and C in the comparison circuit. A shifting circuit controlled by the comparison circuit repetitively shifts the logical "one's" in the decoder memory until A'=A, B'=B and C'=C. When A'=A, B'=B and C'=C, the original N-bit data message is recreated and is available for use by an external utilization apparatus.
Inventors
- 👤 Harold R. Dell
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 16:53
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/46
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
411 words
A data compression apparatus comprising: a first memory means having a plurality of memory cells; means for storing an N-bit data message in said first memory means, where N is the number of bits in said N-bit data message; means for providing a number Q corresponding to the total number of logical "one's" in said N-bit data message irrespective of their position in said first memory means; means coupled to said memory cells in a first predetermined order for providing a number A corresponding to the total number of logical "one's" stored in said first memory means according to a first predetermined sequence; means coupled to said memory cells in a second predetermined order which is different from said first predetermined order for providing a number B corresponding to the total number of logical "one's" stored in said first memory means according to a second predetermined sequence; means coupled to said memory cells in a third predetermined order which is different from both said first and said second predetermined order for providing a number C corresponding to the total number of logical "one's" stored in said first memory according to a third predetermined sequence; means for providing a P-bit message having an A, B, C and Q segment corresponding to said numbers A, B, C and Q, respectively, where P is the number of bits in said P-bits message; a second memory means responsive to said Q segment of said P-bit data message for storing Q logical "one's" in said second memory means; means for providing a number A' corresponding to the total number of logical "one's" stored in said second memory means according to a first predetermined sequence; means for providing a number B' corresponding to the total number of logical "one's" stored in said second memory means according to a second predetermined sequence; means for providing a number C' corresponding to the total number of logical "one's" stored in said second memory means in a third predetermined sequence; means for comparing predetermined pairs of said numbers, A' and A, B' and B and C' and C, said comparing means including means for providing an output signal corresponding to the numerical relationship between each of said pairs; and means responsive to said output signal, in the event said numerical relationship is one of inequality, for reordering the position of logical "one's" in said second memory means until said numerical relationship between each of said number pairs is one of equality.
Claim 2
Dependent Claim
411 words
A data compression apparatus comprising: a first memory means having a plurality of memory cells; means for storing an N-bit data message in said first memory means, where N is the number of bits in said N-bit data message; means for providing a number Q corresponding to the total number of logical "one's" in said N-bit data message irrespective of their position in said first memory means; means coupled to said memory cells in a first predetermined order for providing a number A corresponding to the total number of logical "one's" stored in said first memory means according to a first predetermined sequence; means coupled to said memory cells in a second predetermined order which is different from said first predetermined order for providing a number B corresponding to the total number of logical "one's" stored in said first memory means according to a second predetermined sequence; means coupled to said memory cells in a third predetermined order which is different from both said first and said second predetermined order for providing a number C corresponding to the total number of logical "one's" stored in said first memory according to a third predetermined sequence; means for providing a P-bit message having an A, B, C and Q segment corresponding to said numbers A, B, C and Q, respectively, where P is the number of bits in said P-bits message; a second memory means responsive to said Q segment of said P-bit data message for storing Q logical "one's" in said second memory means; means for providing a number A' corresponding to the total number of logical "one's" stored in said second memory means according to a first predetermined sequence; means for providing a number B' corresponding to the total number of logical "one's" stored in said second memory means according to a second predetermined sequence; means for providing a number C' corresponding to the total number of logical "one's" stored in said second memory means in a third predetermined sequence; means for comparing predetermined pairs of said numbers, A' and A, B' and B and C' and C, said comparing means including means for providing an output signal corresponding to the numerical relationship between each of said pairs; and means responsive to said output signal, in the event said numerical relationship is one of inequality, for reordering the position of logical "one's" in said second memory means until said numerical relationship between each of said number pairs is one of equality.
Claim 3
Dependent Claim
24 words
An apparatus according to claim 1 wherein said means for providing said numbers A, B, C, A', B' and C' comprises an arithmetic means.
Claim 4
Dependent Claim
18 words
An apparatus according to claim 2 wherein said means for providing said number Q is a "one's" detector.
Claim 5
Dependent Claim
94 words
An apparatus according to claim 1 wherein said means for providing said numbers, A, B, C, A', B' and C' comprises a plurality of arithmetic units each having a plurality of input lines and said first and said second memory means each comprises a plurality of memory cells and further comprising means for coupling corresponding ones of said input lines of said plurality of arithmetic units to predetermined ones of said plurality of memory cells in said first and said second memories in accordance with said first, said second and said third predetermined sequences.
Claim 6
Dependent Claim
69 words
An apparatus according to claim 4 wherein said first and said second memory means each comprises an A-axis, a B-axis and a C-axis, and said numbers A' and A, B' and B and C' and C comprise numbers corresponding to the sum of the total number of logical "one's " stored in said first and said second memory means relative to said A-axis, said B-axis and said C-axis, respectively.
Claim 7
Dependent Claim
80 words
An apparatus according to claim 5 wherein a predetermined number of said arithmetic units are coupled to said second memory means and further comprising register means for storing said A, said B and said C segments of said P-bit data message and wherein said comparing means is coupled between said arithmetic units coupled to said second memory means and said register means for providing said comparison between said number pairs A' and A, B' and B and C' and C.
Claim 8
Dependent Claim
103 words
An apparatus according to claim 6 wherein said means for reordering the position of logical "one's" in said second memory means comprises means for increasing the numerical value of A' relative to A if A' is less than A, increasing the numerical value of B' relative to B if B' is less than B, increasing the numerical value of C' if C' is less than C, decreasing the numerical value of A' if A' is greater than A, decreasing the numerical value of B' if B' is greater than B and decreasing the numerical value of C' if C' is greater than C.
Claim 9
Dependent Claim
56 words
An apparatus according to claim 7 wherein said means for increasing and decreasing the numerical value of A', B' and C' relative to A, B and C, respectively, comprises means for shifting predetermined ones of said logical "one's" in said second memory means left and right relative to said A-axis, said B-axis and said C-axis, respectively.
Claim 10
Dependent Claim
78 words
An apparatus according to claim 8 wherein said means for shifting said logical "one's" in said second memory means includes means for interrogating a pair of adjacent memory cells in said second memory, said interrogating means including means for determining whether it is possible to shift a logical "one" from a first one of said adjacent cells to the second one of said adjacent cells without changing the total number of logical "one's" stored in said second memory.
Claim 11
Dependent Claim
394 words
A data compression apparatus comprising: an encoding means; a first memory means in said encoding means having a plurality of memory cells for storing data bits; means for storing an N-bit data message in said memory cells of said first memory means where N is the number of data bits in said N-bit data message; means coupled to said storing means for counting and generating a number Q corresponding to the number of logical "one's" in said N-bit data message; means, including first means coupled to said memory cells in a first predetermined order, second means coupled to said memory cells in a second predetermined order which is different from said first predetermined order, and third means coupled to said memory cells in a third predetermined order which is different from both said first and said second predetermined order for summing the contents of said memory cells in said first memory means in a first, a second and a third predetermined order for generating a plurality of numbers A, B and C corresponding to said summations; means for generating a P-bit data message including said numbers A, B, C and Q as segments thereof where P is the number of bits in said P-bit data message; a decoding means; means for transferring said P-bit data message to said decoding means; a second memory means in said decoding means having a plurality of memory cells for storing data bits; means for storing Q logical "one's" in said memory cells in said second memory means; means for registering said numbers A, B and C from said P-bit data message received in said encoding means; means for summing the contents of said memory cells in said second memory means in a first, a second and a third predetermined order for generating a plurality of numbers A', B' and C' corresponding to said summations; means coupled to said registering means and said summing means for comparing said numbers A, B, C, A', B' and C' in pairs A' and A, B' and B and C' and C and generating an output signal if there is an inequality between the members of any one of said pairs; and means responsive to said output signal for repositioning the contents of the memory cells in said second memory means until A' equals A, B' equals B and C' equals C simultaneously.
Claim 12
Dependent Claim
394 words
A data compression apparatus comprising: an encoding means; a first memory means in said encoding means having a plurality of memory cells for storing data bits; means for storing an N-bit data message in said memory cells of said first memory means where N is the number of data bits in said N-bit data message; means coupled to said storing means for counting and generating a number Q corresponding to the number of logical "one's" in said N-bit data message; means, including first means coupled to said memory cells in a first predetermined order, second means coupled to said memory cells in a second predetermined order which is different from said first predetermined order, and third means coupled to said memory cells in a third predetermined order which is different from both said first and said second predetermined order for summing the contents of said memory cells in said first memory means in a first, a second and a third predetermined order for generating a plurality of numbers A, B and C corresponding to said summations; means for generating a P-bit data message including said numbers A, B, C and Q as segments thereof where P is the number of bits in said P-bit data message; a decoding means; means for transferring said P-bit data message to said decoding means; a second memory means in said decoding means having a plurality of memory cells for storing data bits; means for storing Q logical "one's" in said memory cells in said second memory means; means for registering said numbers A, B and C from said P-bit data message received in said encoding means; means for summing the contents of said memory cells in said second memory means in a first, a second and a third predetermined order for generating a plurality of numbers A', B' and C' corresponding to said summations; means coupled to said registering means and said summing means for comparing said numbers A, B, C, A', B' and C' in pairs A' and A, B' and B and C' and C and generating an output signal if there is an inequality between the members of any one of said pairs; and means responsive to said output signal for repositioning the contents of the memory cells in said second memory means until A' equals A, B' equals B and C' equals C simultaneously.
Claim 13
Dependent Claim
146 words
A data compression apparatus comprising: a first means having a plurality of memory cells for storing an N-bit data message comprising "one's" and "zeros;" means for generating a number Q corresponding to the number of "one's" in said data message; means, including first means coupled to said memory cells in a first predetermined order, second means coupled to said memory cells in a second predetermined order which is different from said first predetermined order, and third means coupled to said memory cells in a third predetermined order which is different from both said first and said second predetermined order for generating a plurality of numbers A, B and C corresponding to a first, a second and a third summation of the contents of said first storing means; and means for generating and storing a P-bit data message corresponding to said numbers A, B, C and Q.
Claim 14
Dependent Claim
146 words
A data compression apparatus comprising: a first means having a plurality of memory cells for storing an N-bit data message comprising "one's" and "zeros;" means for generating a number Q corresponding to the number of "one's" in said data message; means, including first means coupled to said memory cells in a first predetermined order, second means coupled to said memory cells in a second predetermined order which is different from said first predetermined order, and third means coupled to said memory cells in a third predetermined order which is different from both said first and said second predetermined order for generating a plurality of numbers A, B and C corresponding to a first, a second and a third summation of the contents of said first storing means; and means for generating and storing a P-bit data message corresponding to said numbers A, B, C and Q.
Claim 15
Dependent Claim
161 words
An apparatus according to claim 11 further comprising: a second means having a plurality of memory cells for storing an N-bit data message; means for storing Q "one's" in said second storing means; means, including fourth means coupled to said memory cells in a fourth predetermined order, fifth means coupled to said memory cells in a fifth predetermined order which is different from fourth predetermined order, and sixth means coupled to said memory cells in a sixth predetermined order which is different from both said fourth and said fifth predetermined order for generating a plurality of numbers A', B' and C' corresponding to a first, a second and a third summation of the contents of said second storing means; means for comparing said numbers A' and A, B' and B and C' and C; and means responsive to said comparing means for reducing the magnitude of any inequality between the numbers A' and A, B' and B and C' and C.
Claim 16
Dependent Claim
40 words
An apparatus according to claim 12 wherein said means responsive to said comparing means comprises means for selectively shifting the contents of said second storing means until said numbers A' equals A, B' equals B and C' equals C, simultaneously.
Claim 17
Dependent Claim
40 words
An apparatus according to claim 12 wherein said means for generating said numbers A, B and C and said numbers A', B' and C' comprises means for summing columns of the contents of said first and said second storing means.
Claim 18
Dependent Claim
14 words
An apparatus according to claim 14 wherein said summing means comprises arithmetic unit means.
Claim 19
Dependent Claim
73 words
An apparatus according to claim 15 wherein said first and said second storing means comprise a plurality of memory cells and said arithmetic unit means comprises a plurality of arithmetic units each having a plurality of inputs, and further comprising means for coupling each of said plurality of inputs to predetermined ones of said memory cells for providing said summing of columns of the contents of said first and said second storing means.
Claim 20
Dependent Claim
52 words
An apparatus according to claim 13 wherein said shifting means comprises: means for selectively checking the contents of adjacent ones of said memory cells and means responsive to said checking means for storing a "one" in a cell initially containing a "zero," and a "zero" in a cell initially containing a "one."
Claim 21
Dependent Claim
12 words
An apparatus according to claim 17 wherein said checking means further comprises:
Claim 22
Dependent Claim
32 words
a memory for storing addresses of said adjacent ones of said memory cells; and means for selectively addressing first one and then the other of said adjacent ones of said memory cells.
Claim 23
Dependent Claim
32 words
a memory for storing addresses of said adjacent ones of said memory cells; and means for selectively addressing first one and then the other of said adjacent ones of said memory cells.
References Cited (Backward Citations)
US3093707A
Cited
US3213268A
Cited
US3235661A
Cited
US3490690A
Cited
US3432754A
Cited
US3694639A
Cited
US3726993A
Cited
US3813485A
Cited
US3821711A
Cited
US3863248A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1981-02-27 | 1981-08-29 | 1982-02-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1985-02-27 | 1985-08-29 | 1986-02-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1989-02-27 | 1989-08-29 | 1990-02-28 | $7700.00 | Window Closed / Lapsed |