The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
May. 06, 2003
Filed:
Jun. 25, 1999
Craig S. Brown, Bothell, WA (US);
Thomas A. Grate, Issaquah, WA (US);
Microsoft Corporation, Redmond, WA (US);
Abstract
Arithmetic coding and decoding, and compressing and decompressing methods and systems are described. In one embodiment, occurrence values are calculated that represent the number of times individual component values appear in an input stream that is to be encoded. The occurrence values are first normalized to ensure that they are all powers of 2. The occurrence values are then second normalized to ensure that the sum of all of the occurrence values is a power of 2. After normalization, encoding or compressing takes place through arithmetic techniques that utilize a range having a length equal to the normalized sum of the occurrence values. Various sub-ranges within the range are assigned to individual component values that are to be encoded. A position is defined within the range and a determination is made as to whether the position is within a sub-range that is necessary to encode an individual component value. If the position is not within the appropriate sub-range, then the position is moved, one or more encoding bits are emitted, and the new position is checked. When the position is found to be within the desired sub-range, the sub-range is expanded and the next component value of the input string is retrieved for encoding. Decoding takes place through arithmetic techniques that draw upon some of the same fundamentals of position location and sub-range expansion.