DATA COMPRESSION FOR NOISELESS CHANNELS (HUFFMAN CODES, LATTICE THEORY)

A data compression method to compress strings of digital data and to encode the compressed data for transmission over a noiseless channel is presented. Several aspects of information theory and lattice theory are combined to produce a method by which an optimum way of reorganizing and combining source words can be found. The source considered here has identification bits and data bits intermingled. Source words that are related in some fashion, either sequentially or by position in a group of words, are stacked and new subsources formed by taking source words vertically rather than horizontally. A partition lattice is then formed with the partition being over source combination. A minimal length chain can be found which connects the minimum-entropy partition for each level. By using the truncated lattice method, this chain may be calculated directly with a significant reduction in work to find the optimum partition for the given constraints on a system. Several examples are given and a practical application to the on-board F-15 radar system is discussed.