Method and means for arithmetic string coding

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).