Process for use with lempel/gin encoding

• US 5,262,776 A
• Filed: 12/11/1991
• Issued: 11/16/1993
• Est. Priority Date: 06/30/1989
• Status: Expired due to Term

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Kutka, Robert
• Primary Examiner(s): Pellinen, A. D.
• Assistant Examiner(s): Young, Brian K.
• Application Number:
  US07/781,186
• Time in Patent Office: 706 Days
• Field of Search: 341/51, 341/67, 341/87, 341/95, 341/106, 364/251.6, 364/260.6
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

An A. Lempel and J. Ziv code is frequently used for coding a sequence of elements of, for example, coefficients of a discrete cosine transform for image values of picture elements of a reproduced image. An extremely fast code generation process is disclosed for this. In coding steps, code words are marked at coding sites in accordance with the partial sequences found. The coding steps are linked by coding step pointers. The sequence of elements from a primary sequence can be converted into elements from a reduced set of elements using escape sequences.

Claims

1. A process for coding a sequence of elements by generating a Lempel/Ziv code for partial sequences, comprising the steps of:

constructing a linked list having a linked tree structure from tables, said tables being coding stages;

providing in each of the coding stages for each element of the sequence of elements a location, referred to as a coding site, at which a code word and a coding stage pointer to a subsequent coding stage may be assigned to a respective element;

assigning a respective code word to a partial sequence to be coded at a respective coding site, to which a respective coding stage pointer points, the respective coding stage pointer belonging to a further partial sequence which is produced by deletion of a last element of the partial sequence to be coded.

2. The process according to claim 1, wherein each of the code words has between 10 and 16 bits.

3. The process according to claim 1, wherein an element of the sequence of elements is represented with 4 to 8 bits.

4. The process according to claim 1, wherein a number of coding stages is between one half and one seventh of a number of code words.

5. The process according to claim 1, wherein a maximum number of elements of partial sequences is between 100 and 500.

6. The process according to claim 1, wherein the elements of the sequence of elements are coefficients of a discrete cosine transform of image values of a digital image.

7. The process according to claim 1, wherein the steps of the process are carried out by means of a general-purpose computer.

8. The process according to claim 1, wherein each of the code words has 14 bits.

9. The process according to claim 1, wherein an element of the sequence of elements is represented with 6 bits.

10. The process according to claim 1, wherein a number of coding stages is one third of a number of code words.

11. The process according to claim 1, wherein a maximum number of elements of partial sequences is 250.