Patent US4935882A successfully refreshed from Google Patents.
US4935882A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Probability adaptation for arithmetic coders
Assignee: International Business Machines Corp
•
Filing: 1988-07-20
•
Granted: 1990-06-19
•
Expires: 2008-07-20
Abstract
Abstract Apparatus and method for adapting the estimated probability of either the less likely or more likely outcome (event) of a binary decision in a sequence of binary decisions involves the up-dating of the estimated probability in response to the renormalization of an augend A. The augend A changes value with each binary decision, the size of the change depending on which of the binary events has occurred as input. Re-normalization of A occurs when the A value becomes less than a prescribed minimum value AMIN. According to the invention, there may be differing contexts in which binary decisions may occur, each context having a corresponding estimated probability value which is up-dated with binary decisions in the respective context. Also according to the invention, there may be one or more possible next values for an estimated probability in response to a given binary decision event. The selection of one of multiple possible next values in response to a given binary decision event is preferably determined based on a renormalization correlation count.
Inventors
- 👤 William B. Pennebaker
- 👤 Joan L. Mitchell
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 08:54
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/4006
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
334 words
A computerized method of selectively adapting the value of an estimated probability Q e , in response to the inputting to a computer of an outcome event corresponding to a decision, wherein the value of Q e corresponds to the estimated probability of a Q e event and a Q e event is one of at least two possible outcome events that may be inputted, the method comprising the steps of: selecting and storing in the computer (i) an augend having a value A and (ii) a value qe for the estimated probability Q e ; providing a plurality of said possible outcome events as input to the computer and generating respective signals indicative thereof; changing the stored augend value A to equal a value A' derived from the selected value A and the selected value ge in response to the generation of a signal indicative of a Q e event; changing the stored augend value A to equal a value A" derived from the selected value A and a value equal to (1--the selected value qe of Q e ), in response to the generation of a signal indicative of an outcome event that is other than a Q e event; comparing the changed augend value, A' or A", to a prescribed minimum value AMIN, and generating a signal indicating when said changed augend value is less than AMIN; renormalizing the changed augend value to increase the value thereof to A"'>AMIN in response to said signal indicating that said changed value is less than said prescribed minimum value AMIN; up-dating the value of qe to qe', in response to the renormalization of the augend value; repeating the above-recited steps using the values A' or A" and qe as the stored values, and substituting the values A"' and qe' as the stored values in response to a renormalization; and continuing said repetition accordingly using continuously changing stored augend values and estimated probability values in response to the continuing input of said possible outcome events.
Claim 2
Dependent Claim
334 words
A computerized method of selectively adapting the value of an estimated probability Q e , in response to the inputting to a computer of an outcome event corresponding to a decision, wherein the value of Q e corresponds to the estimated probability of a Q e event and a Q e event is one of at least two possible outcome events that may be inputted, the method comprising the steps of: selecting and storing in the computer (i) an augend having a value A and (ii) a value qe for the estimated probability Q e ; providing a plurality of said possible outcome events as input to the computer and generating respective signals indicative thereof; changing the stored augend value A to equal a value A' derived from the selected value A and the selected value ge in response to the generation of a signal indicative of a Q e event; changing the stored augend value A to equal a value A" derived from the selected value A and a value equal to (1--the selected value qe of Q e ), in response to the generation of a signal indicative of an outcome event that is other than a Q e event; comparing the changed augend value, A' or A", to a prescribed minimum value AMIN, and generating a signal indicating when said changed augend value is less than AMIN; renormalizing the changed augend value to increase the value thereof to A"'>AMIN in response to said signal indicating that said changed value is less than said prescribed minimum value AMIN; up-dating the value of qe to qe', in response to the renormalization of the augend value; repeating the above-recited steps using the values A' or A" and qe as the stored values, and substituting the values A"' and qe' as the stored values in response to a renormalization; and continuing said repetition accordingly using continuously changing stored augend values and estimated probability values in response to the continuing input of said possible outcome events.
Claim 3
Dependent Claim
56 words
The method of claim 1 comprising the further step of: storing a table of selectable Q e values in a memory; and wherein the current value for Q e at any given time is a value from the table and said up-dating step includes selecting a prescribed table value which becomes the current Q e value.
Claim 4
Dependent Claim
102 words
The method of claim 2 wherein the Q e value corresponds to a less probable binary decision event and the Q e value up-dating step includes the steps of: choosing a large-in-value Q e value from the table in response to signals indicative of a less probable binary decision event being entered as the next input and the changed augend value being less than AMIN; and choosing a lower-in-value Q e value from the table in response to signals indicative of a more probable binary decision event being entered as the next input and the changed augend value being less than AMIN.
Claim 5
Dependent Claim
40 words
The method of claim 3 wherein said table storing step includes: assigning Q e values for the table in which each value after renormalization to a value greater than AMIN is at least a prescribed value δ greater than AMIN.
Claim 6
Dependent Claim
37 words
The method of claim 3 wherein said table storing step includes: assigning Q e values for the table to converge (i) the actual probability of the less probable event and (ii) the estimated probability Q e .
Claim 7
Dependent Claim
40 words
The method of claim 5 wherein said table storing step includes: assigning Q e values for the table in which each value after renormalization to a value greater than AMIN is at least a prescribed value δ greater than AMIN.
Claim 8
Dependent Claim
145 words
The method of claim 3 wherein the current augend value A is changed in value to equal (a) the value of Q e , in response to a signal indicating that the less probable event is entered as input, and (b) A - the value of Q e , in response to a signal indicating that the more probable event is entered as input, where the value of Q e , is the most recent current value thereof, and wherein the Q e value up-dating step includes the steps of: choosing a larger-in-value Q e value from the table in response to a signal indicating a less probable decision event input; and choosing a lower-in-value Q e value from the table in response to a signal indicating a more probable decision event input which results in the changed value of A being less than AMIN.
Claim 9
Dependent Claim
27 words
The method of claim 2 comprising the further step of: for each entry in the table, specifying which Q e values can be chosen as succeeding values.
Claim 10
Dependent Claim
59 words
The method of claim 8 wherein said specifying step includes the steps of: for each of at least some Q e values in the table, identifying a plurality of selectable succeeding Q e values one of which becomes the current Q e value in response to a selected one of the two binary decision events being entered as input.
Claim 11
Dependent Claim
43 words
The method of claim 9 wherein the Q e up-dating step includes the step of: adjusting the Q e value in correspondence with a renormalization correlation that represents the repetitive occurrence of LPS renormalization events and the repetitive occurrence of MPS renormalization events.
Claim 12
Dependent Claim
61 words
The method of claim 10 wherein the Q e adjusting step includes the steps of: indexing a counter in a first direction when an LPS renormalization follows an LPS renormalization or an MPS renormalization follows an MPS renormalization; and indexing the counter in the opposite direction when an LPS or an MPS renormalization follows an MPS or an LPS renormalization, respectively.
Claim 13
Dependent Claim
24 words
The method of claim 11 wherein the indexing in said opposite direction is at twice the rate as the indexing in said first direction.
Claim 14
Dependent Claim
54 words
The method of claim 10 comprising the further step of: representing the Q e table as a finite state machine in which each of at least some Q e table entries has a plurality of states corresponding thereto, each state in the plurality indicating and being selected according to a corresponding renormalization correlation history.
Claim 15
Dependent Claim
61 words
The method of claim 8 wherein said specifying step includes the steps of: for each of at least some of the Q e values in the table, identifying a single succeeding Q e value which is selected as the current Q e value in response to renormalization after a first of the two possible binary decision events being entered as input.
Claim 16
Dependent Claim
86 words
The method of claim 8 wherein said specifying step further includes the steps of: for each Q e value in the table, identifying a first succeeding Q e value which is selected as the current Q e value if a first of the two binary decision events is entered as input; and for each Q e value in the table, identifying a second succeeding Q e value which is selected as the current Q e value if the other possible binary event is entered as input.
Claim 17
Dependent Claim
66 words
The method of claim 1 comprising the further step of: defining a plurality of contexts, each having a corresponding current Q e value in the stored table; and wherein said up-dating step includes the step of: up-dating the corresponding current Q e value for a respective context in response to a signal indicative of an inputted outcome event resulting in a renormalization in said respective context.
Claim 18
Dependent Claim
22 words
The method of claim 16 wherein the augent value at a given time is common to all contexts at said given time.
Claim 19
Dependent Claim
15 words
The method of claim 16 wherein each context has a respective augend value assigned thereto.
Claim 20
Dependent Claim
31 words
The method of claim 1 where AMIN is 0.75 and wherein said up-dating step includes the step of: changing the Q e value whenever the value augend is less than 0.75.
Claim 21
Dependent Claim
131 words
In a computerized arithmetic coding system in which a stored augend value A is renormalized in response to the (a) the entering of a less probable binary decision event (LPS) input which reduces A below a prescribed minimum value AMIN1, or (b) the entering of a more probable binary decision event (MPS) input which reduces A below a prescribed minimum value AMIN2, apparatus for adapting the value of the probability of the input of one of the two possible binary decision events after successive binary decision event inputs comprising: means for detecting when the augend value A is renormalized and producing a signal indicative thereof; and means for up-dating the probability value of said one binary decision event in response to an indicative signal each time an augend renormalization is detected.
Claim 22
Dependent Claim
131 words
In a computerized arithmetic coding system in which a stored augend value A is renormalized in response to the (a) the entering of a less probable binary decision event (LPS) input which reduces A below a prescribed minimum value AMIN1, or (b) the entering of a more probable binary decision event (MPS) input which reduces A below a prescribed minimum value AMIN2, apparatus for adapting the value of the probability of the input of one of the two possible binary decision events after successive binary decision event inputs comprising: means for detecting when the augend value A is renormalized and producing a signal indicative thereof; and means for up-dating the probability value of said one binary decision event in response to an indicative signal each time an augend renormalization is detected.
Claim 23
Dependent Claim
96 words
The apparatus of claim 20 further comprising: table means for storing selectable values for the probability of said one binary decision event; and pointer means for identifying a current probability value in said table means; and wherein said up-dating means includes: means for moving said pointer means to a higher-in-value entry in said table means in response to a renormalization normalization after the input of one of the two possible binary decision events and to a lower-in-value entry in response to a renormalization after the input of the other of the two possible binary decision events.
Claim 24
Dependent Claim
28 words
The apparatus of claim 21 wherein said table means comprises: a finite state machine wherein the respective preceding entries and succeeding entries for each table entry are specified.
Claim 25
Dependent Claim
70 words
The apparatus of claim 21 wherein binary decisions in differing contexts are processed together, and further comprising: means for recognizing the context in which a binary decision even is produced; and wherein said pointer means comprises a plurality of pointers, each pointer identifying a respective value in said table means for each context; and means included in said pointer moving means for repositioning the pointer corresponding to the recognized context.
Claim 26
Dependent Claim
22 words
The apparatus of claim 21 further comprising: means for varying the rate of pointer movement according to a measure of renormalization correlation.
Claim 27
Dependent Claim
138 words
The apparatus of claim 21 wherein said table means comprises: a first stored table including a list of probability value entries and, for each entry therein, a corresponding index which identifies a higher succeeding probability value and the corresponding index thereof; and a second stored table including a list of probability value entries and, for each entry therein, a corresponding index which identifies a lower succeeding probability value and the corresponding index thereof; and further comprising: means for up-dating the probability value to the identified higher value entry in said first table in response to are normalization following the input of a first type of decision event, and for up-dating the probability value to the identified lower value entry in said second table in response to a renormalization following the input of a second type of decision event.
Claim 28
Dependent Claim
254 words
In a data processing system in which first and second types of decision events are input thereto, and wherein a current interval along a probability number line is divided into (a) a lesser-included first interval which becomes the current interval when a first type of decision event is entered as the next input, and (b) a lesser-included second interval which becomes the current interval when a second type of decision event is entered as the next input, with the length of the first interval corresponding to a a value indicative of a first estimated probability of the first type of event being entered as the next input, and the length of the second interval corresponding to a probability associated with the second type of decision event being entered as the next input, and in which the value A of the length of the current interval is stored in memory during the inputting of successive decision events and is renormalized to increase the value thereof when it becomes less than a prescribed minimum value AMIN, a method of selectively adapting the first estimated probability value in response to decision event inputs, comprising the steps of: storing a table of selectable first estimated probability values in a memory; selecting as a current first estimated probability value, one of the first probability values in the table; and up-dating the current first estimated probability value to a prescribed table value which becomes the current first probability value in response to the renormalization of the current interval value A.
Claim 29
Dependent Claim
254 words
In a data processing system in which first and second types of decision events are input thereto, and wherein a current interval along a probability number line is divided into (a) a lesser-included first interval which becomes the current interval when a first type of decision event is entered as the next input, and (b) a lesser-included second interval which becomes the current interval when a second type of decision event is entered as the next input, with the length of the first interval corresponding to a a value indicative of a first estimated probability of the first type of event being entered as the next input, and the length of the second interval corresponding to a probability associated with the second type of decision event being entered as the next input, and in which the value A of the length of the current interval is stored in memory during the inputting of successive decision events and is renormalized to increase the value thereof when it becomes less than a prescribed minimum value AMIN, a method of selectively adapting the first estimated probability value in response to decision event inputs, comprising the steps of: storing a table of selectable first estimated probability values in a memory; selecting as a current first estimated probability value, one of the first probability values in the table; and up-dating the current first estimated probability value to a prescribed table value which becomes the current first probability value in response to the renormalization of the current interval value A.
References Cited (Backward Citations)
US4028731A
Cited
US4122440A
Cited
US4168513A
Cited
US4259693A
Cited
US4285049A
Cited
US4286256A
Cited
US4295125A
Cited
US4426731A
Cited
US4363036A
Cited
US4467317A
Cited
US4369463A
Cited
US4488143A
Cited
US4462081A
Cited
US4591908A
Cited
US4633490A
Cited
US4672539A
Cited
US4652856A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-06-18 | 1993-12-18 | 1994-06-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-06-18 | 1997-12-18 | 1998-06-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-06-18 | 2001-12-18 | 2002-06-19 | $7700.00 | Window Closed / Lapsed |