Hewlett-packard Company

Sperry Corporation

Sperry Rand Corporation

Hewlett-packard Corporation

Abraham Lempel

Gadiel Seroussi

Martin Cohn

Jeffrey P Tobin

Terry A Welch

Willard L Eastman

Carl B Lantz

Kenzel P Manning

Jacob Ziv

A scheme for compression of large sets of short blocks of data for storage in a storage medium, such as a read-only memory. Applications of the scheme include compression of fonts for printers, ROM disks in portable PCs, and others. These applications require random access to individual blocks, and fast, real-time decompression. The scheme applies an asymmetrical three-stage methodology in which a first stage provides training and optimization for a set of data blocks; a second stage effects data compression; and a third stage effects data decompression.

Method and apparatus for compressing and decompressing short blocks of

The invention is a dictionary initialization scheme adaptive to changes in the type and structure of input data. The compression ratio is increased by minimizing the number of data entries used to represent single characters in the input data. By using fewer codes than what is normally used to represent characters in an array of input data, the dictionary can have fewer entries than the alphabet size. A further aspect of the invention implements a type of run-length encoding in the LZ methodology which exploits the redundant structure existing in the compressed stream in the presence of a long run. Some of the codewords in the compressed stream are deleted but can be recovered at the decompression site. The foregoing LZE method is used alone, or used in combination with other methods to form a compression scheme that is especially useful for transmitting network packets.

Compression using small dictionaries with applications to network packets

A novel memory hashing system is disclosed. The system converts an address into a hashed address of the form (B,C) where B is a module number in a multi-module memory system and C is an offset in the module. The system can be shown to have no pathological cases for any stride value less than some predetermined value. An apparatus according to the present invention is conveniently implemented in a pipelined architecture which allows one address value to be calculated each memory cycle. The present invention utilizes a special matrix calculated from a primitive polynomial for calculating the hashed addresses. The conversion of any given address requires one row of the matrix. The entries of the matrix may be stored in ROM. Alternatively, the required row of the matrix may be calculated in response to receiving the address which is to be convened to the hashed address.

Method and apparatus for memory interleaving using an improved hashing

A class of lossless data compression algorithms use a memory-based dictionary of finite size to facilitate the compression and decompression of data. To reduce the loss in data compression caused by dictionary resets, a standby dictionary is used to store a subset of encoded data entries previously stored in a current dictionary. In a second aspect of the invention, data is compressed/decompressed according to the address location of data entries contained within a dictionary built in a content addressable memory (CAM). In a third aspect of the invention, the minimum memory/high compression capacity of the standby dictionary scheme is combined with the fast single-cycle per character encoding/decoding capacity of the CAM circuit. The circuit uses multiple dictionaries within the storage locations of a CAM to reduce the amount of memory required to provide a high data compression ratio.

Apparatus and method for managing multiple dictionaries in content

A class of lossless data compression algorithms use a memory-based dictionary of finite size to facilitate the compression and decompression of data. When the current dictionary (CD) fills up with encoded character strings, it is reset thereby losing the compression information previously contained in the dictionary. To reduce the loss in data compression caused by dictionary resets, a second, standby dictionary (SD) is used to simultaneously store a subset of the encoded data entries stored in the first dictionary. The data entries in the second dictionary represent the data entries of the first dictionary that compress the greatest amount of input data. When the first dictionary is ready to be reset, the first dictionary is replaced with the second dictionary, maintaining high data compression and freeing up memory space for new encoded data strings.

Lempel-Ziv compression scheme with enhanced adapation

An apparatus for protecting computer memory utilizes a parity matrix to generate an n-k check bit signal of an extended linear (n,k,4) code from a k data bit signal. Exclusive-OR gates add the n-k check bit signal to an n-k tag bit signal selected from a predetermined class, to form, when concatenated with the k data bit signal, an element of a code of a certain class. The element comprising the k data bit signal is written in memory. A correction matrix or And gate cooperating with exclusive-OR gates detects an attempt to access the k data bit signal with an n-k key bit signal belonging to the same class as the n-k tag bit signal, but which does not match it.

Coset code generator for computer memory protection

A compressor parses the input data stream into segments where each segment comprises a prefix and the next symbol in the data stream following the prefix. The prefix of a segment is the longest match with a previously parsed segment of the data stream. The compressor constructs a search tree data base to effect the parsing and to generate a pointer for each segment pointing to the previous segment matching the prefix. The search tree comprises internal nodes including a root and external nodes denoted as leaves. The nodes are interconnected by branches representative of symbols of the alphabet. Each parsed segment of the input data is represented by a path from the root to a leaf. The tree is adaptively constructed from the input data such that as each new segment is parsed, one new internal node of the tree is created from a leaf and new leaves are defined, one for each symbol already encountered by the encoder plus an additional branch to represent all potential but unseen symbols. The compressor transmits a leaf pointer signal for each parsed segment representative of the prefix thereof and the suffixed symbol of the alphabet. A decompressor constructs an identical search tree in response to the received leaf pointers so as to reconstitute the original data stream.

Apparatus and method for compressing data signals and restoring the

The invention is described in the environment of a binary data magnetic recording and reproducing system and comprises a binary to non-consecutive zero code converter for encoding the input binary data into a non-consecutive zero code which, in turn, is recorded on the magnetic medium. In recording, a flux transition occurs for each ONE of the non-consecutive zero code. A bipolar peak detector detects the flux transitions and thus detects the presence of the recorded ONEs. The peak detected signals are utilized to continuously trigger a mono-stable multivibrator having a period whereby the multivibrator relaxes to its stable state in the absence of a ONE which denotes the presence of a ZERO. The peak detected signal and the output of the mono-stable multivibrator are utilized to synthesize a clock signal from the recorded non-consecutive zero data. The recorded data is applied to a non-consecutive zero code to binary converter which is synchronized by the data derived clock to recover the originally recorded binary information.

Growing community of inventors

Haifa, Israel

Abraham Lempel