Patent US5309381A successfully refreshed from Google Patents.
US5309381A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Probability estimation table apparatus
Assignee: Ricoh Co Ltd
•
Filing: 1992-04-08
•
Granted: 1994-05-03
•
Expires: 2012-04-08
Abstract
Abstract A probability estimation table reading apparatus includes a memory part for storing a probability estimation table, the table defining, for each address value, a switch data value, a probability estimate data value, an LPS data value indicative of a next address when a more probable symbol occurs and an MPS data value indicative of a next address when a less probable symbol occurs, and a control part for reading out each the LPS data value and MPS data value for a current address value of the stored table, so that next address values required by an arithmetic coder to perform arithmetic coding data compression, can be generated. Each of the LPS data value in the stored table stored in the memory part has been replaced by the difference between a current address value and a next address value indicated by a standard LPS data value for the current address value, and each of the MPS data value has been replaced by the difference between the current address value and a next address value indicated by a standard MPS data value for the current address value.
Inventors
- 👤 Ryo Fukui
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 08:33
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/005; G06F; G06F1/00; G06F1/02; G06F1/03; H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/4006; G06F2101/00; G06F2101/14
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
180 words
An apparatus for reading a simplified probability estimation table for use in an arithmetic coder, wherein said simplified probability estimation table is generated from a previously defined standard probability estimation table, said apparatus comprising: memory means for storing said simplified probability estimation table, said simplified probability estimation table defining, with respect to each of a plurality of possible address values, a switch data value, a probability estimate data value, an LPS data value which is equal to the difference between a current address value and a corresponding standard LPS data value from said standard probability estimation table, and an MPS data value which is equal to the difference between said current address value and a corresponding standard MPS data value from said standard probability estimation table; and control means coupled to said memory means for reading out said LPS and MPS data values from a location of the simplified probability estimation table in said memory means corresponding to a current address value, and for generating a next address value required for the arithmetic coder to perform arithmetic coding data compression.
Claim 2
Independent Claim
180 words
An apparatus for reading a simplified probability estimation table for use in an arithmetic coder, wherein said simplified probability estimation table is generated from a previously defined standard probability estimation table, said apparatus comprising: memory means for storing said simplified probability estimation table, said simplified probability estimation table defining, with respect to each of a plurality of possible address values, a switch data value, a probability estimate data value, an LPS data value which is equal to the difference between a current address value and a corresponding standard LPS data value from said standard probability estimation table, and an MPS data value which is equal to the difference between said current address value and a corresponding standard MPS data value from said standard probability estimation table; and control means coupled to said memory means for reading out said LPS and MPS data values from a location of the simplified probability estimation table in said memory means corresponding to a current address value, and for generating a next address value required for the arithmetic coder to perform arithmetic coding data compression.
Claim 3
Dependent Claim
258 words
An apparatus according to claim 1, wherein said control means comprises: sign bit checking means coupled to said memory means for detecting whether or not a data value read out from the simplified probability estimation table is positive by checking a sign bit corresponding to said read out data value; data reading means coupled to the memory means and the sign bit checking means for reading out said LPS and MPS data values from the simplified probability estimation table, and for selecting, as an input value, one of said LPS and MPS data values corresponding to said current address value in accordance with an output from said sign bit checking means and a switch data value corresponding to said current address value; address generating means coupled to said data reading means for generating a next address value required for arithmetic coding data compression by adding said input data value selected by said data reading means to said current address value unless the MPS data value in the simplified probability estimation table is negative and the switch data value is zero, or the LPS data value in the simplified probability estimation table is positive and the switch data value equal one; and address checking means coupled to said address generating means, wherein said address checking means includes means for detecting whether or not said generated next address value is equal to 113 in decimal, and means for converting a generated next address value to 112 in decimal if said generated next address value is equal to 113 in decimal.
Claim 4
Dependent Claim
70 words
An apparatus according to claim 2, wherein said address generating means includes means for adding the value one to the input data value generated by the data reading means when the MPS data value in the simplified probability estimation table is negative and the switch data value equals zero, or when the LPS data value in the simplified probability estimation table is positive and the switch data value equals one.
Claim 5
Dependent Claim
92 words
An apparatus according to claim 1, further comprising means for determining whether said difference value between said current address value and the corresponding standard MPS data value is a positive value, wherein a first number of bits required for representing LPS data values for each address value in the stored table and a second number of bits required for representing MPS data values for each address value in the simplified probability estimation table vary in accordance with the difference value between said current address value and said corresponding standard MPS data value.
Claim 6
Dependent Claim
58 words
An apparatus according to claim 1, further comprising means for expressing the LPS data values in said simplified probability estimation table by six binary digits and the MPS data values in said simplified probability estimation table by two binary digits if the difference value between said current address value and said corresponding standard MPS data value is positive.
Claim 7
Dependent Claim
61 words
An apparatus according to claim 1, further comprising means for expressing the LPS data values in said simplified probability estimation table by two binary digits and the MPS data values in said simplified probability estimation table by six binary digits if the difference value between said current address value and said corresponding standard MPS data value is negative or equals zero.
Claim 8
Dependent Claim
79 words
An apparatus according to claim 1, further comprising means for replacing an LPS data value in the simplified probability estimation table with a value which is calculated by subtracting the value one from an absolute value of the difference value between said current address value and said corresponding standard LPS data value if said corresponding standard LPS data value is not equal to zero and said corresponding standard LPS data value on said standard probability estimation table is negative.
Claim 9
Independent Claim
270 words
An apparatus for generating a simplified probability estimation table from a previously defined standard probability estimation table wherein said simplified probability estimation table is to be stored in a memory of a probability estimation table reading apparatus for use of a probability estimation table reading apparatus for use in an arithmetic coder, said apparatus comprising: difference generating means for generating difference values with respect to each of a plurality of addresses on said standard probability estimation table, where said addresses range from 0 through 112 in decimal, and said standard probability estimation table defines for each address a switch data value, a probability estimate data value, an LPS data value indicative of a next address when a more probable symbol occurs in a sequence of symbols, and an MPS data value indicative of a next address when a less probable symbol occurs in said sequence of symbols, wherein said difference generating means comprises means for generating a first difference value between a current address value and a next address value which represents a standard LPS data value corresponding to said current address value on said standard probability estimation table, and means for generating a second difference value between said current address value and a next address value which represents a standard MPS data value corresponding to said current address value on said standard probability estimation table; and means for substituting each respective first difference value for each of said standard LPS values on said standard probability estimation table and for substituting each respective second difference value for each of said standard MPS data values on said standard probability estimation table.
Claim 10
Independent Claim
270 words
An apparatus for generating a simplified probability estimation table from a previously defined standard probability estimation table wherein said simplified probability estimation table is to be stored in a memory of a probability estimation table reading apparatus for use of a probability estimation table reading apparatus for use in an arithmetic coder, said apparatus comprising: difference generating means for generating difference values with respect to each of a plurality of addresses on said standard probability estimation table, where said addresses range from 0 through 112 in decimal, and said standard probability estimation table defines for each address a switch data value, a probability estimate data value, an LPS data value indicative of a next address when a more probable symbol occurs in a sequence of symbols, and an MPS data value indicative of a next address when a less probable symbol occurs in said sequence of symbols, wherein said difference generating means comprises means for generating a first difference value between a current address value and a next address value which represents a standard LPS data value corresponding to said current address value on said standard probability estimation table, and means for generating a second difference value between said current address value and a next address value which represents a standard MPS data value corresponding to said current address value on said standard probability estimation table; and means for substituting each respective first difference value for each of said standard LPS values on said standard probability estimation table and for substituting each respective second difference value for each of said standard MPS data values on said standard probability estimation table.
Claim 11
Independent Claim
370 words
An apparatus for generating a simplified probability estimation table from a previously defined standard probability estimation table, wherein said simplified probability estimation table is to be stored in a memory of a probability estimation table reading apparatus for use in an arithmetic coder, said apparatus comprising: difference generating means for generating LPS and MPS difference values, with respect to each of a plurality of addresses ranging from 0 through 112 in decimal, on said previously defined standard probability estimation table which defines switch data values, probability estimate data values, standard LPS data values indicative of next address values when a more probable symbol occurs in a sequence of symbols, and standard MPS data values indicative of next address values when a less probable symbol occurs in said sequence of symbols, wherein said difference generating means includes means for representing LPS difference data values by difference values between current address values and next address values when said next address values are indicated by the standard LPS data values corresponding to said current address values, and means for representing said MPS difference data values by difference values between said current address values and next address values when said next address values are indicated by the standard MPS data values corresponding to said current address are positive, negative or equal to zero; MPS data generating means, coupled to said difference generating means, for generating MPS data values, each having either six binary digits or two binary digits based on said MPS difference data values supplied by said difference generating means for each of said plurality of addresses, where the number of said binary digits is determined in response to said MPS sign data values supplied by said difference generating means for each of said plurality of addresses; and LPS data generating mans, coupled to said difference generating means, for generating LPS data values, each having either six binary digits or two binary digits based on said LPS difference data values supplied by said difference generating means for each of said plurality of addresses, where the number of said binary digits is determined in response to said MPS sign data values supplied by said difference generating means for each of said plurality of addresses.
Claim 12
Independent Claim
370 words
An apparatus for generating a simplified probability estimation table from a previously defined standard probability estimation table, wherein said simplified probability estimation table is to be stored in a memory of a probability estimation table reading apparatus for use in an arithmetic coder, said apparatus comprising: difference generating means for generating LPS and MPS difference values, with respect to each of a plurality of addresses ranging from 0 through 112 in decimal, on said previously defined standard probability estimation table which defines switch data values, probability estimate data values, standard LPS data values indicative of next address values when a more probable symbol occurs in a sequence of symbols, and standard MPS data values indicative of next address values when a less probable symbol occurs in said sequence of symbols, wherein said difference generating means includes means for representing LPS difference data values by difference values between current address values and next address values when said next address values are indicated by the standard LPS data values corresponding to said current address values, and means for representing said MPS difference data values by difference values between said current address values and next address values when said next address values are indicated by the standard MPS data values corresponding to said current address are positive, negative or equal to zero; MPS data generating means, coupled to said difference generating means, for generating MPS data values, each having either six binary digits or two binary digits based on said MPS difference data values supplied by said difference generating means for each of said plurality of addresses, where the number of said binary digits is determined in response to said MPS sign data values supplied by said difference generating means for each of said plurality of addresses; and LPS data generating mans, coupled to said difference generating means, for generating LPS data values, each having either six binary digits or two binary digits based on said LPS difference data values supplied by said difference generating means for each of said plurality of addresses, where the number of said binary digits is determined in response to said MPS sign data values supplied by said difference generating means for each of said plurality of addresses.
Claim 13
Dependent Claim
136 words
An apparatus according to claim 9, wherein said LPS data generating means includes: first LPS data means for generating a six-bit LPS data value based on said LPS difference data value supplied by the difference generating means if a corresponding MPS sign data values indicates that said MPS difference data value is positive or equal to zero, and for generating a three-bit LPS data value based on said LPS difference data value supplied by the difference generating means if a corresponding MPS sign data value indicates that the MPS difference data value is negative; and second LPS data means for generating a two-bit LPS data value by subtracting the value one from an absolute value of said three-bit LPS data value supplied by said first LPS data means when said MPS difference data value is negative.
Claim 14
Dependent Claim
86 words
An apparatus according to claim 9, wherein said MPS data generating means generates a six-bit MPS data based on an MPS difference data value supplied by said difference generating means if a corresponding MPS sign data value indicates that the MPS difference data value is negative, and generates a two-bit MPS data value based on an MPS difference data value supplied by said difference generating means if a corresponding MPS sign data value indicates that the MPS difference data value is positive or equal to zero.
Claim 15
Independent Claim
329 words
An apparatus for reading a simplifier probability estimation table for use in an arithmetic coder, wherein said simplified probability estimation table is generated from a previously defined standard probability estimation table, said apparatus comprising: memory means for storing said simplified probability estimation table, said simplified probability estimation table defining, with respect to each of a plurality of possible address values, a switch data value, a probability estimate data value, an LPS data value which is equal to the difference between a current address value and standard LPS data value from said standard probability estimation table, and an MPS data value which is equal to the difference between a current address value and a corresponding standard MPS data value from said standard probability estimation table; control means coupled to said memory means for reading out each of said LPS data values and MPS data values for each of said current address values of the simplified probability estimation table wherein said control means comprises: sign bit checking means coupled to said memory means for detecting whether or not a data value read out from the simplified probability estimation table is positive by checking a sign bit corresponding to said read out data value; data reading means coupled to the memory means and said sign bit checking means for selecting, as an input data value, one of said LPS and MPS data values corresponding to said current address value in accordance with an output from said sign bit checking means and said switch data value corresponding to said current address value; address generating means coupled to said data reading means for generating said next address value required for arithmetic coding data compression by adding said input data value selected by said data reading means to said current address value corresponding to said read out data value; and address checking means coupled to said address generating means for detecting whether or not said generated next address value is equal to 113 in decimal.
Claim 16
Independent Claim
329 words
An apparatus for reading a simplifier probability estimation table for use in an arithmetic coder, wherein said simplified probability estimation table is generated from a previously defined standard probability estimation table, said apparatus comprising: memory means for storing said simplified probability estimation table, said simplified probability estimation table defining, with respect to each of a plurality of possible address values, a switch data value, a probability estimate data value, an LPS data value which is equal to the difference between a current address value and standard LPS data value from said standard probability estimation table, and an MPS data value which is equal to the difference between a current address value and a corresponding standard MPS data value from said standard probability estimation table; control means coupled to said memory means for reading out each of said LPS data values and MPS data values for each of said current address values of the simplified probability estimation table wherein said control means comprises: sign bit checking means coupled to said memory means for detecting whether or not a data value read out from the simplified probability estimation table is positive by checking a sign bit corresponding to said read out data value; data reading means coupled to the memory means and said sign bit checking means for selecting, as an input data value, one of said LPS and MPS data values corresponding to said current address value in accordance with an output from said sign bit checking means and said switch data value corresponding to said current address value; address generating means coupled to said data reading means for generating said next address value required for arithmetic coding data compression by adding said input data value selected by said data reading means to said current address value corresponding to said read out data value; and address checking means coupled to said address generating means for detecting whether or not said generated next address value is equal to 113 in decimal.
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) | 1997-05-02 | 1997-11-01 | 1998-05-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-05-02 | 2001-11-01 | 2002-05-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-05-02 | 2005-11-01 | 2006-05-03 | $7700.00 | Window Closed / Lapsed |