Multicontext compression system with shared data structures

• US 5,526,363 A
• Filed: 05/16/1995
• Issued: 06/11/1996
• Est. Priority Date: 05/16/1995
• Status: Expired due to Term

• Current Assignee: Avaya Incorporated, Telco Systems Incorporated (BATM Advanced Communications Ltd.)
• Original Assignee: Telco Systems Incorporated (BATM Advanced Communications Ltd.)
• Inventors: Weiss, Jeffrey, Black, Jeffrey, Lam, Wing
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): PHILLIPS, MATTHEW
• Application Number:
  US08/441,868
• Time in Patent Office: 392 Days
• Field of Search: 370/118, 370/79, 370/82, 370/83, 370/84, 370/99, 370/109, 370/94.1, 375/240, 341/51, 341/87, 348/385, 348/387
• US Class Current: 370/477
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

A system for transmitting compressed data for multiple channels or contexts from a single node which system reduces memory utilization without significant adverse effect on compression ratio by providing a separate history buffer for each channel, with a single hash table being provided for generating potential match addresses in the history buffer for at least selected ones of the channels. A single chain table may also be provided, the chain table having a single offset address for the corresponding offset addresses in the buffers for the selected channels. Collisions in the common hash table may be reduced by including channel address or the like as an additional input to the hash table, thereby biasing the address outputs therefrom.

Claims

1. In a system for transmitting compressed data for multiple contexts from a single node, apparatus for facilitating reduced memory utilization comprising:

a history buffer for each of said contexts; and

a single hash table for generating potential match addresses in the history buffers for at least selected ones of the contexts, the hash table including means for overwriting address entries for one context in the hash table with address entries for a succeeding context when collisions occur in the hash table.

2. Apparatus as claimed in claim 1 including a single chain table having a single address location for the corresponding address location in all of the buffers for said at least selected ones of the contexts, the chain table including means for overwriting chain address entries for one context with chain address entries for a succeeding context when collisions occur in the chain table.

3. Apparatus as claimed in claim 2 including means for limiting the depth of searches in the chain table.

4. Apparatus as claimed in claim 2 wherein there are a plurality of hash tables and a like plurality of chain tables, with each hash table and chain table pair servicing a selected plurality of said history buffers.

5. Apparatus as claimed in claim 1 including a hashing element for generating addresses in said single hash table for inputs from all of said contexts, said hashing element also receiving an input indicative of the context for a given input, and including means responsive to the input indicative of context for generating different hash table addresses for each context for at least selected input character combinations.

6. Apparatus as claimed in claim 1 wherein there are a plurality of hash tables, with each hash table servicing a selected plurality of said history buffers.