Unisys Corporation

Sperry Corporation

The Mitre Corporation

Willard L Eastman

Abraham Lempel

Martin Cohn

Thomas M Hopkinson

Jacob Ziv

John J Vaccaro

A programmable decoder that provides both error and erasure decoding for all Reed-Solomon, primitive BCH, non-primitive BCH, and binary BCH codes of any rate over any field is disclosed. The user can specify decoding parameters including the code block-length, the code-generator polynomial, and the field-generator polynomial. The basic architecture, less the small overhead for programmability, is also recommended for fixed-code applications. The decoding processor of the decoder includes systolic arrays implementing a syndrome calculator, a key equation solver, a Chien search, a recursive extender, and an inverse transform. The number of cells required for each of the five functions is on order of the error correction capability t. The systolic arrays can be fabricated on a single VLSI microchip that is itself systolic. Each of the individual systolic arrays can extended by arraying microchips together, so that any desired error correction capability can be attained by using multiple systolic microchips with a single controller.

Programmable systolic BCH decoder

Short-data records are compressed and decompressed by Lempel-Ziv compression and decompression utilizing a fixed searchtree database, an encoder and a decoder. The searchtree database is incrementally grown by a file preprocessor from a sample of the input data. The searchtree is fixed either when the data sample or the storage space for the searchtree is exhausted. The encoder maintains an encoded-record directory for locating the compressed records. A record located by the directory is decompressed by the decoder, and may be modified and recompressed by the encoder. Lempel-Ziv compresssion and decompression of the type of U.S. Pat. No. 4,464,650 is utilized. The preprocessor also constructs, as part of the searchtree database, a last-descendant list for use by the decoder to extend internal nodes received as leaf pointers by the appropriate number of repetitions of the first encountered symbol of the alphabet.

Short-record data compression and decompression system

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

Growing community of inventors

Lexington, MA, United States of America

Willard L Eastman