Franaszek, U.S. Pat. No. 3,689,899, issued Sept. 5, 1972, described a method for increasing the density with which data could be recorded on disks or which could be reliably transmitted through existing channels by a run length limited coding technique. This technique converts ordinary binary data strings by requiring that each one in a coded bit sequence must be separated from the nearest adjacent one by a number of zeros at least equal to a minimum quantity d in order to ensure freedom from intersymbol interference during recording or transmission but not exceeding a maximum number k which was required for self-clocking purposes. Such codes are referred to as (d,k) RLL codes. The coded information is processed in code groups or code words of variable lengths. The lengths of the encoded words bear a constant ratio (fixed rate) to the respective lengths of their corresponding original data bit strings. Further, Franaszek disclosed in "Sequence State Methods For Run Length Limited Coding", IBM Journal of Research and Development, pp. 376-383, July 1970, that a binary string could be mapped into either a fixed rate or variable rate RLL code using either state dependent or state independent transformations.
Guazzo, "A General Minimum Redundancy Source Coding Algorithm", IEEE Transactions on Information Theory, Vol. IT26, pp. 15-25, January 1980, described the mapping of source strings into a variable rate RLL symbol string using a Huffman decoder. Recovery of the source string was by way of applying the RLL symbol string to a Huffman encoder. In this regard, the Huffman decoder expands the RLL string relative to the data string while the encoder recovers the original string by compression of the RLL string.
The compression of bit strings by using a pair of recursions for arithmetically combining bit pairs of relatively shifted binary finite number strings is described by Rissanen and Langdon in "Arithmetic Coding", IBM Journal of Research and Development, Vol. 23, pp. 149-162, March 1979. One recursion arithmetic combines an increment to a retained portion of the compressed code string, while the second recursion controls the compressed string's length increase. Also, arithmetic codes may be either probability oriented or length oriented. These are respectively described in Langdon, et al., U.S. patent application, Ser. No. 98,285, filed Nov. 28, 1979, and Langdon, et al., U.S. Pat. No. 4,122,440, issued Oct. 24, 1978.
The Langdon, et al., references point out that in arithmetic compression encoding, the current code strings are generated recursively by adding augends to the previous code string which resulted from the encoding of the previous binary source symbol. In contrast, compression decoding involves examining the most significant part of the code string and determining from its magnitude the largest augend not exceeding the numerical value of said code string. This augend is, in turn, subtracted out. The decoded symbol is that source alphabet symbol which corresponds to the subtracted out augend.
According to these references, arithmetic codes order (arrange) the source alphabet a.sub.1, a.sub.2, . . . , a.sub.w, where a.sub.w is the last symbol in the ordering according to a length parameter l(a), where the relative frequency of occurrence p(a) is related to the length parameter according to ##EQU1##
In this regard, a length based arithmetic code maps a source string "u" recursively into code strings F(u). Given u and F(u), the encoding of the next symbol "a" means that the source string "u.a" now maps into code string F(u.a). The "length" of code string F(u) is the sum of the length parameters of the individual symbols which comprise string u. The length parameter has an integral part E(u) and a fractional part X(u). The length of F(u) may be represented by EQU length F(u)=E(u)+X(u).
USPTO Backgrounds
USPTO Backgrounds