Patent US5363099A successfully refreshed from Google Patents.
US5363099A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for entropy coding
Assignee: Ricoh Americas Corp
•
Filing: 1993-10-04
•
Granted: 1994-11-08
•
Expires: 2013-10-04
Abstract
Abstract The present invention provides an encoding and decoding apparatus used for the compression and expansion of data. A state machine is provided having a plurality of states. Each state has at least one transition pair. Each element of the transition pair comprises zero or more bits representative of the compact code to be output and the identification of the next state to proceed to. The transition pair reflects an output for a yes and no response associated with the probability of the data to be compacted and whether the data falls within that probability.
Inventors
- 👤 James D. Allen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 14:54
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/005; H; H03; H03M; H03M13/00; H03M13/03; H03M13/23; H03M13/31; H03M5/00; H03M5/02; H03M5/04; H03M5/14; H03M5/145; H03M7/00; H03M7/30; H03M7/40; H03M7/4006; G11; G11B; G11B20/00; G11B20/10; G11B20/14; G11B20/1403; G11B20/1423; G11B20/1426
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
199 words
A method of generating a coded output in response to a plurality of inputs, wherein each of the plurality of inputs is in one of a plurality of possible first states, said method comprising the steps of: receiving a first threshold value for one of the plurality of inputs; receiving a first indication for said one of the plurality of inputs, wherein said first indication indicates whether said one of the plurality of inputs is within one of the plurality of possible first states; selecting one of a plurality of sets of transitions in one of a plurality of transition states according to the first threshold value, wherein each transition in the plurality of sets of transitions is associated with an output and a next state within the plurality of transition states; selecting a transition in said one of a plurality of sets of transitions according to said first indication; outputting the output associated with the transition; and transitioning to the next state associated with the transition, such that a transition within the next state is selected using a second threshold value and a second indication corresponding to an input immediately following said one of the plurality of inputs.
Claim 2
Independent Claim
199 words
A method of generating a coded output in response to a plurality of inputs, wherein each of the plurality of inputs is in one of a plurality of possible first states, said method comprising the steps of: receiving a first threshold value for one of the plurality of inputs; receiving a first indication for said one of the plurality of inputs, wherein said first indication indicates whether said one of the plurality of inputs is within one of the plurality of possible first states; selecting one of a plurality of sets of transitions in one of a plurality of transition states according to the first threshold value, wherein each transition in the plurality of sets of transitions is associated with an output and a next state within the plurality of transition states; selecting a transition in said one of a plurality of sets of transitions according to said first indication; outputting the output associated with the transition; and transitioning to the next state associated with the transition, such that a transition within the next state is selected using a second threshold value and a second indication corresponding to an input immediately following said one of the plurality of inputs.
Claim 3
Dependent Claim
15 words
The method defined in claim 1 wherein the first indication comprises one of two codes.
Claim 4
Dependent Claim
17 words
The method defined in claim 1 wherein the first indication comprises one of a binary decision pair.
Claim 5
Dependent Claim
14 words
The method defined in claim 1 wherein the first indication comprises a yes/no indicative.
Claim 6
Dependent Claim
15 words
The method defined in claim 1 wherein the first threshold value comprises a probability value.
Claim 7
Dependent Claim
15 words
The method defined in claim 5 wherein the first probability value comprises a probability estimate.
Claim 8
Dependent Claim
13 words
The method defined in claim 1 wherein the output comprises a bit stream.
Claim 9
Dependent Claim
14 words
The method defined in claim 1 wherein the output comprises zero or more bits.
Claim 10
Dependent Claim
20 words
The method defined in claim 1 wherein each of the plurality of sets of transitions comprises a pair of transitions.
Claim 11
Dependent Claim
21 words
The method defined in claim 1 wherein the output represents a compressed version of said one of the plurality of inputs.
Claim 12
Independent Claim
217 words
A method of generating a coded output in response to a plurality of inputs, wherein each of the plurality of inputs is in one of a plurality of possible first states, said method comprising the steps of: receiving a first probability for one of the plurality of inputs; receiving a first indication for said one of the plurality of inputs, wherein said first indication indicates whether said one of the plurality of inputs is within one of the plurality of possible first states; selecting one of a plurality of transition pairs in one of a plurality of transition states according to the first probability, wherein each transition in the plurality of transition pairs is associated with an output and a next state within the plurality of transition states, wherein the output comprises a bit stream of zero or more bits representing a compressed version of said one of the plurality of inputs; selecting a transition in said one of a plurality of transition pairs according to said first indication; outputting the output associated with the transition; and transitioning to the next state associated with the transition, such that a transition within the next state is selected using a second probability and a second indication corresponding to an input immediately following said one of the plurality of inputs.
Claim 13
Independent Claim
217 words
A method of generating a coded output in response to a plurality of inputs, wherein each of the plurality of inputs is in one of a plurality of possible first states, said method comprising the steps of: receiving a first probability for one of the plurality of inputs; receiving a first indication for said one of the plurality of inputs, wherein said first indication indicates whether said one of the plurality of inputs is within one of the plurality of possible first states; selecting one of a plurality of transition pairs in one of a plurality of transition states according to the first probability, wherein each transition in the plurality of transition pairs is associated with an output and a next state within the plurality of transition states, wherein the output comprises a bit stream of zero or more bits representing a compressed version of said one of the plurality of inputs; selecting a transition in said one of a plurality of transition pairs according to said first indication; outputting the output associated with the transition; and transitioning to the next state associated with the transition, such that a transition within the next state is selected using a second probability and a second indication corresponding to an input immediately following said one of the plurality of inputs.
Claim 14
Dependent Claim
15 words
The method defined in claim 11 wherein the first indication comprises one of two codes.
Claim 15
Dependent Claim
17 words
The method defined in claim 11 wherein the first indication comprises one of a binary decision pair.
Claim 16
Dependent Claim
14 words
The method defined in claim 11 wherein the first indication comprises a yes/no indicative.
Claim 17
Independent Claim
154 words
A method of decoding a compressed bit stream of a plurality of bits into a plurality of input symbols, said method comprising the steps of: receiving a first threshold value; receiving a first portion of the compressed bit stream; selecting one of a plurality of sets of transitions in one of a plurality of transition states according to the first threshold value, wherein each transition in the plurality of sets of transitions is associated with an output and a next state within the plurality of transition states; selecting a transition in said one of a plurality of sets of transitions according to said first portion of the compressed bit stream; outputting the output associated with the transition; and transitioning to the next state associated with the transition, such that a transition within the next state is selected using a second threshold value and a second portion of the compressed immediately following said first portion.
Claim 18
Independent Claim
154 words
A method of decoding a compressed bit stream of a plurality of bits into a plurality of input symbols, said method comprising the steps of: receiving a first threshold value; receiving a first portion of the compressed bit stream; selecting one of a plurality of sets of transitions in one of a plurality of transition states according to the first threshold value, wherein each transition in the plurality of sets of transitions is associated with an output and a next state within the plurality of transition states; selecting a transition in said one of a plurality of sets of transitions according to said first portion of the compressed bit stream; outputting the output associated with the transition; and transitioning to the next state associated with the transition, such that a transition within the next state is selected using a second threshold value and a second portion of the compressed immediately following said first portion.
Claim 19
Dependent Claim
16 words
The method defined in claim 15 wherein the output comprises one of a binary decision pair.
Claim 20
Dependent Claim
13 words
The method defined in claim 15 wherein the output comprises a yes/no indicative.
Claim 21
Dependent Claim
20 words
The method defined in claim 15 wherein each of the plurality of sets of transitions comprises a pair of transitions.
Claim 22
Dependent Claim
15 words
The method defined in claim 15 wherein the first threshold value comprises a probability indication.
Claim 23
Independent Claim
118 words
A method of generating a code bit stream from at least one input, said method comprising the steps of: providing a transition machine having a plurality of sets of transitions, wherein each of the plurality of sets of transitions are in one of a plurality of transition states, wherein each transition in the plurality of sets of transitions is associated with an output, and wherein the transition machine is initially in one of the plurality of transition states; selecting a transitions in the plurality of sets of transitions using a first threshold; selecting a transition in said one of a plurality of sets of transitions according to a first indication; and outputting the output associated with the transition.
Claim 24
Independent Claim
118 words
A method of generating a code bit stream from at least one input, said method comprising the steps of: providing a transition machine having a plurality of sets of transitions, wherein each of the plurality of sets of transitions are in one of a plurality of transition states, wherein each transition in the plurality of sets of transitions is associated with an output, and wherein the transition machine is initially in one of the plurality of transition states; selecting a transitions in the plurality of sets of transitions using a first threshold; selecting a transition in said one of a plurality of sets of transitions according to a first indication; and outputting the output associated with the transition.
Claim 25
Dependent Claim
75 words
The method defined in claim 20 wherein each transition in the plurality of sets of transitions includes a next state within the plurality of transition states, and the method further comprises the step of transitioning to the next state associated with the transition, such that a transition within the next state is selected using a second threshold value and a second indication corresponding to an input immediately following said one of the plurality of inputs.
Claim 26
Dependent Claim
16 words
The method defined in claim 20 wherein the step of outputting includes outputting a bit stream.
Claim 27
Independent Claim
102 words
A method for decoding a compressed bit stream in order to reconstruct an uncompressed data, said method comprising steps of: receiving a portion of the compressed bit stream; searching a plurality of states having at least one set of transitions, wherein one of said plurality of states is chosen in response to a first threshold value and one of said transitions in said one of said plurality of states according to a predetermined yes/no indicative; and outputting the uncompressed bit stream associated with said one of said transitions and transitioning to one of said plurality of states according to said first indicative.
Claim 28
Independent Claim
102 words
A method for decoding a compressed bit stream in order to reconstruct an uncompressed data, said method comprising steps of: receiving a portion of the compressed bit stream; searching a plurality of states having at least one set of transitions, wherein one of said plurality of states is chosen in response to a first threshold value and one of said transitions in said one of said plurality of states according to a predetermined yes/no indicative; and outputting the uncompressed bit stream associated with said one of said transitions and transitioning to one of said plurality of states according to said first indicative.
Claim 29
Independent Claim
155 words
A system for the compression of input data comprising a modeling means for characterizing the input data as a threshold value and an indication value indicative that the input data is within the range specified by the threshold value; a coder for generating a stream of bits representative of the compressed form of the input data including: input means for receiving a threshold value and the indication value, wherein the indication indicates whether the input data is in one of a plurality of possible symbol states; state means which identifies the state of the decoder, said state means initialized to be at a predetermined ground state; and a select transition mechanism for selecting the next state of the decoder and zero or more bits as output data representative of the compressed form of the input data in response to the state of the decoder from the state means and the threshold value and indication value.
Claim 30
Independent Claim
155 words
A system for the compression of input data comprising a modeling means for characterizing the input data as a threshold value and an indication value indicative that the input data is within the range specified by the threshold value; a coder for generating a stream of bits representative of the compressed form of the input data including: input means for receiving a threshold value and the indication value, wherein the indication indicates whether the input data is in one of a plurality of possible symbol states; state means which identifies the state of the decoder, said state means initialized to be at a predetermined ground state; and a select transition mechanism for selecting the next state of the decoder and zero or more bits as output data representative of the compressed form of the input data in response to the state of the decoder from the state means and the threshold value and indication value.
Claim 31
Dependent Claim
83 words
The system for the compression of input data as set forth in claim 24, further comprising a decoder for decoding a compressed bit stream in order reconstruct the uncompressed data, said decoder including: input means for receiving a portion of compressed bit stream; state means which identifies the state of the decoder; a select transition mechanism for selecting the next state of the decoder and a second indication value indicative of whether data to be reconstructed is within a range of threshold values.
References Cited (Backward Citations)
US4122440A
Cited
US4286256A
Cited
US4467317A
Cited
US4933883A
Cited
US4891643A
Cited
US5059976A
Cited
US5045852A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-11-07 | 1998-05-09 | 1998-11-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-11-07 | 2002-05-09 | 2002-11-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-11-07 | 2006-05-09 | 2006-11-08 | $7700.00 | Window Closed / Lapsed |