Multiplication-free multi-alphabet arithmetic code

Details Multiplication-free multi-alphabet arithmetic code Multiplication-free multi-alphabet arithmetic code

1986-02-04

1987-03-24

Miller, Charles D.

Communications: electrical

Audible indication

Percussion-type sound producer

H03M 730

Patent

active

046528563

ABSTRACT:
Method and apparatus which cyclically generate a compressed, arithmetically-coded binary stream in response to binary occurrence counts of symbols in an uncoded string. The symbols in the uncoded string are drawn from a multi-character alphabet which is not necessarily a binary one. Coding operations and hardware are simplified by deriving from the binary occurrence counts an estimate of the probability of each unencoded symbol at its precise lexical location. The probability estimation eliminates any requirement for division or multiplication by employing magnitude-shifting of the binary occurrence counts. The encoded stream is augmented by the estimated symbol probability at the same time that an internal variable is updated with an estimate of the portion of a probability interval remaining after coding the current symbol, the interval estimate being obtained from the left-shifted occurrence counts. Decoding is the dual of encoding. The unencoded symbol stream is extracted, symbol-by-symbol, by subtracting the estimated symbol probability that comes closest to, but does not exceed the magnitude of the compressed stream, re-estimating the symbol probabilities based upon the decoding, and testing the difference of the subtraction against the re-estimated probability.

REFERENCES:
patent: 4122440 (1978-10-01), Langdon, Jr. et al.
patent: 4259693 (1981-03-01), Aaron et al.
patent: 4286256 (1981-08-01), Langdon, Jr. et al.
patent: 4295125 (1981-10-01), Langdon, Jr.
patent: 4420771 (1983-12-01), Pirsch
patent: 4467317 (1984-08-01), Langdon
patent: 4494108 (1985-01-01), Langdon
"Method for Converting Counts to Coding Parameters," by G. G. Langdon, Jr. and J. J. Rissanen, IBM Technical Disclosure Bulletin, vol. 22, No. 7, Dec. 1979.
"Integer-Length Arithmetic Code for Conditional Binary Sources," by G. G. Langdon, Jr. and J. J. Rissanen, IBM Technical Disclosure Bulletin, vol. 22, No. 10, Mar. 1980.
"Method for Carry-Over Control in a Fifo Arithmetic Code String," by G. G. Langdon, Jr., IBM Technical Disclosure Bulletin, vol. 23, No. 1, Jun. 1980.
"Apparatus Supporting Half-Duplexed Encoding/Decoding Action," by G. G. Langdon, Jr., IBM Technical Disclosure Bulletin, vol. 23, No. 11, Apr. 1981.

Affiliated with

Also associated with

Rating

Multiplication-free multi-alphabet arithmetic code does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Multiplication-free multi-alphabet arithmetic code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiplication-free multi-alphabet arithmetic code will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1356457