Coded data generation or conversion – Digital code to digital code converters – To or from code based on probability
Reexamination Certificate
2005-11-22
2005-11-22
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from code based on probability
Reexamination Certificate
active
06967601
ABSTRACT:
Methods and apparatuses for performing arithmetic encoding and/or decoding are disclosed. In one embodiment, the method for creating a state machine for probability estimation comprises assigning probabilities to states of a look up table (LUT), including setting a probability for each state i of the states equal to the highest probability of the LPS multiplied by the adaptation rate to the power i, where i is a number for a given state and the adaptation rate is smaller than 1. The method also comprises generating state transitions for states in the LUT to be transitioned to upon observing an MPS and an LPS, wherein the next state to which the state machine transitions from a current state when an MPS is observed is a next state higher than the current state if the current state is not the highest state and is the current state if the current state is the highest state. Furthermore, the next state to which the state machine transitions from a current state when an LPS is observed for a plurality of states is a rounded version of a result of calculating:number of current state+log((probability of the current state*the adaptation rate+(1−the adaptation rate))/probability of the current state)/log(the adaptation rate).
REFERENCES:
patent: 5099440 (1992-03-01), Pennebaker et al.
patent: 5309381 (1994-05-01), Fukui
patent: 5414423 (1995-05-01), Pennebaker
patent: 5471207 (1995-11-01), Zandi et al.
patent: 5583500 (1996-12-01), Allen et al.
patent: 5689589 (1997-11-01), Gormish et al.
patent: 5751859 (1998-05-01), Howard
patent: 5781136 (1998-07-01), Imanaka et al.
patent: 5955977 (1999-09-01), Lei
patent: 5986594 (1999-11-01), Nakayama et al.
patent: 6118900 (2000-09-01), Yokose et al.
patent: 6236759 (2001-05-01), Horie et al.
patent: 6411231 (2002-06-01), Yanagiya et al.
patent: 6476740 (2002-11-01), Bengio et al.
patent: 6677869 (2004-01-01), Horie
IBM Tech. Disclosure NN79122880 Dec. 1, 1979 “Converting Counts To Code Parameters”.
Yip (U.S. Appl. No. 09/927,316), “Entropy Encoding and Decoding,” filed on Aug. 13, 2001.
Horie (U.S. Appl. No. 10/680,152), “Arithmetic Decoding Method and an Arithmetic Decoding Apparatus,” filed on Oct. 8, 2003.
Saunders et al. (U.S. Appl. No. 10/079,713), “Signal Processing,” filed on Feb. 19, 2002.
Haskell, B. et al., “Digital Video: An Introduction to MPEG-2,” 1999, Digital Multimedia Standards Series, no month, Kluwer Academic Publication, Boston, Massachusetts, U.S.A., XP002270324, ISBN: 0-412-08411-2, pp. 370-381.
“Line Transmission of Non-Telephone Signals Video Coding for Low Bitrate Communication,” ITU-T Draft Recommendation H.263, May 2, 1996, pp. I-IV and 1-50, XP001025117.
“Recommendation H.263: Video Coding for Low Bit Rate Communication,” ITU-T Draft Recommendation H.263, Feb., 1998, pp. 1-167, XP002176560.
Sullivan, G., “Draft for H.263++ Annexes U, V, and W to Recommendation H.263,” ITU-T H.263++ Draft for H.263++ Annexes U, V, and W to Recommendation H.263, Nov. 2000, pp. 1-46, XP000986538.
Hoffman, R. “Data Compression in Digital Systems: Section 4.5: Arithmetic Coding,” 1997, Digital Multimedia Standards Series, New York, New York, U.S.A., no month, Chapman & Hall, XP002270325, ISBN: 0-412-08551-8, pp. 60-63.
Salomon, D., “Data Compression: The Complete Reference; Section 2.14, 2.15: (Adaptive) Arithmetic Coding,” 1998, New York, New York, U.S.A., Springer, no month XP002270343, ISBN: 0-387-98280-9, pp. 69-84.
PCT Search Report mailed Jun. 10, 2004, International Application No. PCT/US03/29690, 10 pages.
Blakely , Sokoloff, Taylor & Zafman LLP
NTT DoCoMo Inc.
Young Brian
LandOfFree
Method and apparatus for arithmetic coding, including... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for arithmetic coding, including..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for arithmetic coding, including... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3495148