Process for use with lempel/gin encoding

Details Process for use with lempel/gin encoding Process for use with lempel/gin encoding

1991-12-11

1993-11-16

Pellinen, A. D.

Coded data generation or conversion

Digital code to digital code converters

Adaptive coding

3642516, H03M 700

Patent

active

052627764

DESCRIPTION:

BRIEF SUMMARY
BACKGROUND OF THE INVENTION

The invention relates to a process for coding a sequence of elements, preferably for generating the Lempel/Ziv code for such a sequence of elements.
An A. Lempel and J. Ziv code is frequently used for reducing the redundancy of a sequence of, for example, coefficients of a discrete cosine transform for image values of picture elements of a reproduced image, preferably of a medical diagnostics image, for example of an X-ray image.
The authors Abraham Lempel and Jakob Ziv describe in the journal IEEE Transactions on Information Theory, Vol. IT-23, May 1977, in an article entitled "A Universal Algorithm for Sequential Data Compression" a coding of a sequence of elements. As agreed upon, the coding and decoding cooperate here. During the coding, the sequence of elements to be coded is processed sequentially element by element. In each case here, one of the elements or, respectively, a plurality of the elements are treated as a partial sequence. Accordingly, each of the partial sequences consists of at least one of the elements. Each of the partial sequences can be extended by an added element to form a further one of the partial sequences. As agreed upon, at the beginning of the coding, for each agreed element of a set of elements, which is also frequently referred to as the alphabet, in each case one partial sequence is known, consisting in each case of exactly one of the elements. These partial sequences known at the beginning are frequently also referred to as the primary partial sequences. A code consisting of code words which form a sequence of code words is generated as the result of the coding. In this case each code word corresponds to one partial sequence in each case. At the beginning of the coding, and likewise at the beginning of the decoding, in each case one agreed code word is assigned to each element of the set of elements, and hence also assigned to each primary partial sequence. These code words are frequently also referred to as the primary code words.
Beginning with the first element of the sequence of elements to be coded, the primary partial sequence for this element is recognized and the code word assigned to it is entered in the code as first code word of the code. After this the following element of the sequence of elements to be coded is processed. After a partial sequence has been recognized in each case, the following element is processed in two respects. Firstly the last partial sequence recognized is extended by this element to form an extended new recognized partial sequence, to which a following code word is assigned. This code word is here the next one in a sequence agreed for this purpose. And secondly, for searching for subsequent partial sequences, this element extending the partial sequence is used as the first element for the subsequent partial sequences to be searched for. In each case one partial sequence consisting of as many as possible directly successive elements, for which a code word has already been assigned, is searched for.
In his article "How to quadruple dial-up communications efficiency", Mini-Micro Systems, Vol. 21, No. 2, February 1988, Newton, Mass., USA, pp. 77-81, F. Bacon gives a general description of the Lempel/Ziv process for coding temporal sequences of elements of an alphabet. A coding process, the so-called Telcore model, is described in this paper by F. Bacon, which is to be understood as the connection of the Lempel/Ziv process with the Huffman coding. This process is not suitable for the generation of the Lempel/Ziv code, neither is it otherwise compatible with Lempel/Ziv codes. A contribution to the achieving of the object on which the present patent application is based cannot be found in the publication by F. Bacon. In particular, no reference is made to a process for code generation which avoids a searching for code words.
During the coding, in each case the entire list of the previously recognized partial sequences must be searched through here. The code word which is assigned to the longest of these partial se

REFERENCES:
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4558302 (1985-12-01), Welch
"How to Quadruple Dial-Up Communications Efficiency", Mini-Micro Systems, No. 2, Feb. 1988, by F. Beason pp. 77-81.
"A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, vol. ITT-23, No. 3, May 1977, by J. Ziv and A. Lempel, pp. 337-343.

Affiliated with

Also associated with

Rating

Process for use with lempel/gin encoding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Process for use with lempel/gin encoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process for use with lempel/gin encoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-24663