Method and means for arithmetic string coding

Details Method and means for arithmetic string coding Method and means for arithmetic string coding

1977-03-04

1978-10-24

Miller, Charles D.

Communications: electrical

Audible indication

Percussion-type sound producer

H03K 1324

Patent

active

041224400

ABSTRACT:
There is disclosed a method and means for compacting (encoding) and decompacting (decoding) binary bit strings which avoids the blocking of string elements required by Huffman coding and the ever increasing memory as is the case in simple enumerative coding. The method and means arithmetically encodes successive terms or symbols in a symbol string s=a.sub.i a.sub.j . . . , in which each new term a.sub.k in a source alphabet of N symbols gives rise to a new encoded string C(sa.sub.k) and a new length indicator L(sa.sub.k). The method and means comprises the steps of forming L(sa.sub.k) from the recursion L(sa.sub.k)=L(s)+l(a.sub.k), where l(a.sub.k) is a rational approximation of log.sub.2 1/p(a.sub.k), p(a.sub.k) being the a'priori probability of occurrence of a.sub.k, and l(a.sub.k) being so constrained that the Kraft inequality is satisfied: ##EQU1## AND FORMING C(sa.sub.k) from the recursion C(s)+[P.sub.k-1 2.sup.L(sa.sbsp.k.sup.) ],where: ##EQU2## AND WHERE P.sub.k-1 is the cumulative probability of occurrence of an arbitrary ordering of all symbols.
Instead of assigning a'priori code words to each symbol as in Huffman coding, the method and means ascertains the new encoded string C(sa.sub.k) from the ordinal number (position number k) of the symbol a.sub.k, in the arbitrary ordering, the value of the fractional part of L(sa.sub.k), and the last few bits of the previous compressed symbol string C(s). This results in the generation of two quantities i.e. the encoded string of compressed characters and the fractional length indicators. The use of only a few bits of the last encoded string C(s) for determining C(sa.sub.k) limits the requisite memory to a constant value. During each encoding cycle, the least significant number of bits of C(s) are shifted out as determined by the integrer part of L(sa.sub.k).

REFERENCES:
pasco, "Source Coding Algorithms for Fast Data Compression" Doctoral Dissertation Stanford University, .COPYRGT. 1976.
Rissanen, "IBM J. Res. Develop", vol. 20, No.3, pp 198-203, May 1976.

Affiliated with

Also associated with

Rating

Method and means for arithmetic string coding 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 means for arithmetic string coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and means for arithmetic string coding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2338792