Lempel-Ziv decoder

• US 5,058,137 A
• Filed: 07/31/1989
• Issued: 10/15/1991
• Est. Priority Date: 07/31/1989
• Status: Expired due to Fees

• Current Assignee: North American Philips Corp. (Koninklijke Philips N.V.)
• Original Assignee: North American Philips Corp. (Koninklijke Philips N.V.)
• Inventors: Shah, Imran A.
• Primary Examiner(s): Chin, Stephen
• Application Number:
  US07/388,283
• Time in Patent Office: 806 Days
• Field of Search: 375/25, 375/94, 375/122, 341/51, 341/65, 341/91, 358/426, 358/261.1, 358/261.2, 370/109
• US Class Current: 375/340
• CPC Class Codes: G06F 7/785 having a sequence of storage locations each being individually accessible for both enqueue and dequeue operations, e.g. using a RAM
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

A decoder for data encoded in a form combining a prefix which is a previously coded sub-string and a next data element in the data stream. The decoder includes memories for storing code words and data separately. Upon receipt of a code word the decoder stores the previously received code word, applies the newly received word to the code word memory to obtain the location of the last data element which is part of the data represented by the newly received code word, and another code word associated with the prefix. Upon completion of decoding the latest code word, the first data element of the decoded word is appended to the next previously received code word, and the combination is stored as the equivalent of a code word which is next after the highest code word already received. At least one memory is shared for use during encoding and decoding.

Claims

1. A decoder for decoding Lempel-Ziv encoded data, comprising;

memory means for storing code words and data corresponding to the stored code words;

means for receiving and for storing a code word to be decoded;

means for storing data elements read out from said memory means during decoding; and

means for applying said code word to be decoded to said memory means for reading out a data element, and a prefix coded as another code word, and supplying said data element to said means for storing; and

for applying said another code word to said memory means, for reading out a further data element and a successive code word, supplying said further data element to said means for storing, and applying each successive code word read out from said memory means to said memory means until the stored code word is decoded,

said means for applying comprising a multiplexer having an input for receiving the stored code word to be decoded and having another input for receiving a latest code word read out from said memory means.

2. A decoder for decoding encoded data, comprising:

first memory means for storing code words and data corresponding to the stored code words;

means for receiving and for storing a code word to be decoded;

second memory means connected for shared use in encoding and decoding;

means of controlling said second memory means to provide data on a last-in first-out basis during decoding;

means for applying said code word to be decoded to said first memory means for reading out a data element, and a prefix coded as another code word, and supplying said data element to said second memory means; and

for applying said another code word to said first memory means, for reading out a further data element and a successive code word, supplying said further data element to said second memory means, and applying each successive code word read out from said memory means to said first memory means until all data elements corresponding to said code word to be decoded have been supplied to said second memory means.

3. A decoder for decoding Lempel-Ziv encoded data, comprising;

memory means for storing code words and data corresponding to the stored code words;

means for receiving and for storing a code word to be decoded;

means for storing data elements read out from said memory means during decoding; and

means for applying said code word to be decoded to said memory means for reading out a data element, and a prefix coded as another code word, and supplying said data element to said means for storing; and

for applying said another code word to said memory means, for reading out a further data element and a sucessive code word, supplying said further data element to said means for storing, and applying each successive code word read out from said memory means to said memory means until the stored code word is decoded,

means for determining when the code word is one of a set of basic code words indicating the end of a string;

means for maintaining the address value of the next entry to be made in said memory means;

means for storing the previously received code word; and

means for writing the previously received code word and the first character of the current code word into said memory means for making a new decoder table entry in response to the determination of the end of the string condition.

4. A decoder according to claim 3, wherein said means for applying the stored code word is comprised of a first multiplexer having a first input for receiving the stored code word to be decoded and having a second input for receiving the code word read out from said memory means, and a second multiplexer having a first input for receiving the output of said first multiplexer and a second input for receiving the address value of the next entry to be made in said memory means.

5. A decoder according to claim 3, wherein said means for determining is a comparator connected to receive the output of said means for applying.

6. A decoder according to claim 3, wherein said means for maintaining the address value is a counter.