Method of Constructing Block Codes

1. Field of the Invention

The present invention relates to a method of producing a data compression block code for any finite alphabet source with a given acceptable level of distortion.

2. The Prior Art

The method according to the present invention will produce a data compression block code for any finite alphabet source. The compression rates achievable by this design approach the theoretical limits of data compression as the block size increases.

In general, the present invention presents an efficient technique for data compression. Data compression, or source coding, is used in many technological fields which require transmission of data in a cost-effective and time-effective manner. In particular, the data to be transmitted is converted, using some algorithm, to more compact data which can be transmitted faster than the original source data. In the process of this conversion, errors are introduced creating what is known as distortion. A certain amount of distortion is acceptable, the amount depending upon the particular data and application involved.

Data compression is used in such areas as the transmission of text between two locations, such as facsimile transmission, or the transmission of data for storage such as in image processing. In fact, any type of information can be transmitted more efficiently using data compression techniques, such as through the airwaves, through wires, or between computer storage systems.

Fundamentally the problem of block coding a source (source coding) is to find vectors (code words) of size N which can be used to represent all the source vectors (source words) of size N. In its most abstract definition a source is simply defined to be a set of symbols (alphabet) along with a probability distribution specifying the chance of occurrence of each symbol. If there are r letters in the source alphabet then there are r.sup.N possible vectors of size N. The code words are vectors of size N made up from letters from a reproduction alphabet. If there are s letters in the reproduction alphabet then code words can be chosen from as many as s.sup.N reproduction words.

A person designing a code must specify how to choose M code words from the set of s.sup.N reproduction vectors and he must specify how to associate source words with code words. Usually he wants M to be much less than r.sup.N (compression) so that valuable resources (disk space, transmission energy, transmission time., etc.) are not wasted by representing the full set of r.sup.N messages. Since there are less code words than source words this necessarily means that many source words will be associated with, that is coded by, the same code word. The designer is willing to tolerate this distortion in exchange for the more beneficial efficiency of data compression.

The distortion produced can be quantitatively defined by an r.s distortion matrix {D(a,b)}, where each element of the matrix represents the distortion incurred by representing the source letter a by a reproduction letter b. The distortion between a source word and a code word is the sum of the distortion between each of the corresponding letters in each N-vector. The average distortion, Nd, for the code is the statistical average over all the source words. The average per letter distortion is d (=Nd/N).

When a set of M code words is specified, the association between source word and code word is usually defined by a simple distortion criterion. The code word used to code a source word is one which gives the least distortion.

The code designer is forever concerned with trade-offs between efficiency and distortion. In 1959 C. Shannon produced a theorem which shows the theoretical relationship between the compression rate and average distortion. The proof did not show how to construct a code which achieves the desired compression and distortion, but showed only how many code words would be needed for a given set of source words with a particular average distortion. The theorem has been proven in many ways since then but, until the Doctoral Thesis of the present inventor, (J. Nardi, "Practical Techniques for Source Coding: Constructive Block Coding and Calculating the Compression Rate of Sliding-Block Codes," Univ. of Maryland (1987), incorporated by reference herein and copy attached), there have been no proofs which suggest a practical construction of a code.

An exhaustive search and test of all M combinations of s.sup.N reproduction words will certainly produce an acceptable code, however even for moderate size blocks (8), a code of 5 words would require that over 1 million combinations be tested. This method would proceed more quickly if it could be demonstrated that less than s.sup.N words need to be tried as code word candidates.

In 1980, the present inventor developed a technique for constructing a code which encodes a binary memoryless (independent) source with limiting distortion d. By successively choosing code words to maximally cover particular source vectors, one can derive the same rate distortion function as that calculated by Shannon theory.

According to the 1980 technique, for a given word, of block size N, an acceptable block distortion is chosen. For example, a distortion of 2 means that two of the bits in the source vector are different from their corresponding bits in the reproduction vector, that is, an exclusive OR function: ##EQU1##

The first step is to select a starting reproduction vector and find all those source vectors which have a distortion equal to 2 with respect to the chosen reproduction vector. For the starting reproduction vector, the number of source vectors having a distortion of 2 is determined. The first code word is arbitrarily chosen from those reproduction vectors which correspond to the maximum number of source vectors with a distortion of 2. These source vectors are then eliminated from the list. The next code word is then taken from the list of reproduction vectors that yield the maximum count, i.e., have a distortion of 2 with respect to the most number of sources. Again, all the source vectors that have a distortion of 2 with respect to the new code word are then eliminated. This continues until all source vectors are eliminated or until no other code words correspond to that maximum number of source words.

This method had two major disadvantages. First, the source and reproduction alphabet was limited to the binary set {0,1}. Second, no control was allowed over the distortion matrix, which was limited to the exclusive OR distortion matrix.

Other prior techniques of data compression allowed for picking a source code for a given distortion rate using algebraic codes or annealing codes. Both these prior methods were inefficient in that too much processing time was required, too many codes were produced, more than were required, and the user had no control over the distortion which resulted.

The technique according to the present invention differs from methods used in the previous work of Wolfowitz, Csiszar, and Korner (J. Wolfowitz, "Coding Theorems of Information Theory," Erg. Math. (N.F.)31. Berlin-Gottingen-Heidielberg: Springer-Verlag (1959), I, Csiszar and J. Kroner, Information Theory: Coding for Discrete Memoryless Systems, New York: Academic Press (1981)) in that the set of block vectors from which code words are chosen is much smaller and thus easier and quicker to search. The method differs from the Nardi, Davisson results of 1980 (J. Nardi and L. Davisson, "Constructive Method for Calculating R(d)," Proceedings of the 1980 Conference on Information Sciences, Dept. of Elec. Eng., Princeton, N.J. p. 163 (1980)) in that the current technique applies to sources of arbitrary alphabets having any number of symbols, not just binary sources, and it applies to arbitrary distortion matrices, not just the fidelity criterion.

The algorithm according to the present invention uses only strictly typical vectors, which constitutes many less vectors than s.sup.N, thus this method of choosing code words is much faster. The work of Wolfowitz is based on searches of typical sets which, although less numerous than the full set of code words, are still much more numerous than the strictly typical set. The work of Csiszar and Korner also uses typical sets. The work of Wolfowitz, Csiszar, Korner also used the more general idea of covering.

The work of Nardi, Davisson used strictly typical sets but was only applicable to binary sources (alphabet={0,1}) with a particular distortion matrix: ##EQU2## That work also differed because the previous method of choosing code words was based on a less general idea of maximizing distortion spheres rather than maximizing covering spheres as in the present invention.

It is an object of the present invention to provide a method of choosing code words to represent a set of source words constructed from a finite alphabet, based on a variable, acceptable distortion rate.

It is a further object of the present invention to provide a method of data compression in which the source alphabet and the reproduction alphabet need not be the same.

It is a further object of the present invention to provide a method of choosing code words using strictly typical vectors.

According to a first embodiment of the present invention, a method of selecting at least one code word from a set of second data having at least one data group representing a set of first data having at least one data group is provided comprising the steps of determining for one of the set of second data, all those data groups in the set of first data covered by the one of the set of second data, eliminating the covered data groups from the set of first data, selecting as one of the at least one code word the one of the set of second data which covers the maximum number of data groups of the remaining data groups in the set of first data, and repeating the above steps until a given criteria is satisfied.

The step of determining comprises the step of selecting a joint probability matrix Q that minimizes mutual information of the set of first data with respect to the set of second data. The sets of first and second data groups each consist of N elements and the step of determining further comprises the step of determining that a data group of the first set is covered by a data group of the second set if, when the elements of the two data groups are paired, each pair with first data element i and second data element j occurs exactly NQ.sub.ij times.

According to a second embodiment of the invention, the method also includes the step of eliminating each data group in the set of second data which is covered by the covered data groups in the set of first data.

Means, particularly in the form of computer programs, are provided for selecting at least one code word from a set of second data having at least one data group representing a set of first data having at least one data group comprising determining means for determining, for one of the set of second data, all those data groups in the set of first data covered by the one of the set of second data, eliminating means for eliminating the covered data groups from the set of first data, selecting means for selecting as one of the at least one code word the one of the set of second data which covers the maximum number of data groups remaining in the set of first data, and means for repeating the above steps until a given criteria is satisfied.

Still other objects, features and attendant advantages of the present invention will become apparent to those skilled in the art from a reading of the following detailed description of embodiments constructed in accordance therewith, taken in conjunction with the accompanying drawings.

The invention of the present application will now be described in more detail with reference to the preferred embodiments of the device, given only by way of example, and with reference to the accompanying drawings, in which:

FIG. 1 illustrates a first embodiment of the present invention in circle graph format;

FIG. 2 is a flowchart of the method of selecting code words according to a first embodiment of the present invention;

FIG. 3 is a flowchart of the method of selecting code words according to a second embodiment of the present invention; and

FIGS. 4A and 4B are flowcharts of a method of selecting the distortion matrix according to the present invention.

The Np-Sequence Covering Theorem according to the present invention is stated in the above-cited dissertation as follows.

Let p=(p.sub.1,p.sub.2, . . . , p.sub.r), q=(q.sub.1, q.sub.2, . . . , q.sub.11), and Q=(Q.sub.ij), i=1,2, . . . , r and j=1,2, . . . , s be distributions of rational numbers such that for every i=1,2, . . . , r, ##EQU3## and for every j=1,2, . . . , s, ##EQU4## Let ##EQU5## be the set of Np-sequences on an alphabet A with equiprobable probability assignments where there are Np, occurrences of the letter a.sub.1, p.sub.1 are rational and Np.sub.1 are integers, and likewise for ##EQU6## on an alphabet B. Let ##EQU7## Then for any .epsilon.>O and any N>No we can find a code, ##EQU8## Ps with J=.vertline.Cn.vertline. such that: Also if Cn is any subset of ##EQU9## with J=.vertline.Cn.vertline., then: ##EQU10##

For a fixed N, we will specify how to inductively pick a set Cn of coding vectors from ##EQU11## which covers ##EQU12## with high probability. High probability is achieved when the number of source vectors that are covered divided by the total number of source vectors approaches 1. The first vector is chosen arbitrarily. Call it y.sub.1 and let S.sub.1 =B(y.sub.1). Let n.sub.1 =.vertline.S.sub.1 .vertline.. Suppose we have already chosen vectors y.sub.1, y.sub.2, . . . , y.sub.j ; the next code word, y.sub.j+i, is chosen from the remaining vectors of ##EQU13## so that the number of Np-sequences, that is strictly typical vectors, covered by this additional vector is maximized. In particular, let ##EQU14## the set of all strictly typical source vectors already covered by y.sub.1, y.sub.2, . . . , y.sub.i, and n.sub.j =.vertline.S.sub.j .vertline., then we choose y.sub.j+1 to maximize .vertline.S.sub.j B(y.sub.j+1).vertline..

According to a first embodiment of the present invention, a basic algorithm is provided to select code words. In practice, the source words are coded to the code word of minimum distortion. The best codes are those from which p and q are related by a joint distribution matrix which minimizes the mutual information given an acceptable amount of distortion.

For a source alphabet A={a.sub.1, a.sub.2, . . . , a.sub.r } having a probability p={p.sub.1, p.sub.2, . . . , p.sub.r }, with a block size N having r.sup.N possible vectors, the strictly typical vector is determined as follows: ##EQU15##

As used in the method according to the present invention, a reproduction vector is said to cover a source vector, or visa versa, if, when the vectors are paired off coordinate to coordinate, the resultant vector is a typical Q vector. This is different from distortion discussed in the prior art description of this disclosure. As used herein, Q is the joint probability or distribution matrix which achieves minimum mutual information subject to the constraint that the average distortion is d or less and the source statistics are p. The Q matrix relates to p (the probabilities on the source alphabet) and q (the probabilities on the reproduction alphabet) such that q.sub.j is the sum of the elements in column j and p.sub.i is the sum of the elements in row i. Q.sub.ij is the probability of getting a source letter i and a reproduction letter j. For the algorithm we do not use Q directly but instead use an integer matrix we represent by NQ where each element is a next highest or lowest integer to the value N.Q.sub.ij (subject to the constraint that ##EQU16## Integer values for Q elements are achieved by multiplying each element in the matrix by N, the block size.

The methods according to the present invention can work with any NQ. However, in order to achieve close to perfect theoretical limits, NQ must be chosen to be the matrix which minimizes mutual information. For purposes of this invention, Q is related to the definition of coverage. When the elements of the two vectors are paired, each pair with source i and reproduction j must occur exactly NQ.sub.ij times in order for a finding that one vector covers the other.

As shown in circle graph format in FIG. 1, the set 10 of ##EQU17## represents the set of all strictly typical source words. To start, pick any ##EQU18## as the first code word. To determine the next code word, the number of source words covered by each ##EQU19## is determined, shown as circles B(y.sub.i). The code word is chosen as any y which maximizes the coverage. In the graph, B(y.sub.2) through B(y.sub.4), B(y.sub.6) would be chosen as code words. However, B(y.sub.5) does not provide maximum coverage and therefore would not be chosen as a code word.

The algorithm according to the first embodiment of the present invention is illustrated in the flowchart shown in FIG. 2. In step 20, ##EQU20## is the set of all strictly typical source words, ##EQU21## is the set of all strictly typical reproduction words, and B(y) is the set of source words covered by a code word y. In step 22, any reproduction word, y.sub.1, is chosen from the set of strictly typical reproduction words, ##EQU22## In step 24, all those vectors that are covered by y.sub.1 are eliminated from ##EQU23## This reduced set is called ##EQU24##

At step 26, suppose that code words y.sub.1, y.sub.2, . . . , y.sub.k have already been chosen. Let ##EQU25## At step 28, the next code word, y.sub.k+1, is determined by counting the number of vectors of T.sub.K covered by each of the vectors not already chosen as code words. It is understood that when the first code word is chosen it necessarily yields maximum coverage. It is only when vectors of the source words are eliminated that a code word may no longer cover the maximum number of source vectors. In successive iterations of the algorithm, all of the remaining code words are checked to determine which one covers the maximum number of available (that is, not yet eliminated) source words.

A vector y.sub.k+1 is chosen which has the maximum coverage number, that is covers the maximum number of vectors remaining in the set of source vectors. At step 30, source words covered by y.sub.k+1 are eliminated from T.sub.k to produce T.sub.k+1 =T.sub.k -B(y.sub.k+1). Steps 28 and 30 are repeated until all source words are covered, that is until T.sub.N is empty. Of course, the user can stop the processing at his discretion.

A computer program, written in "C" by the present inventor to implement the method described in this first embodiment is shown in Table I.

A second embodiment of the present invention is shown in the flowchart of FIG. 3. The program implementing the second embodiment, shown in Table II, runs more quickly than the basic algorithm of the first embodiment because candidate code words are eliminated at each step, thus fewer covering searches are required. It specifies how to pick code words whose covering spheres are non-intersecting. A code with disjoint coverage usually sacrifices larger distortion for more favorable efficiency.

The sets ##EQU26## are the same as described in the first embodiment. In step 40, B(y) is defined as the set of source words covered by a code word y, B(x) is the set of code words covered by a source word x, and B(B(y)) is the set of all reproduction words covered by some vector of B(y). At step 42, sets ##EQU27## are ordered, for ease of processing. This step may also be done in the algorithm according to the first embodiment of the present invention. At step 44 any reproduction word, y.sub.1, is chosen from the set of strictly typical reproduction words, ##EQU28## At step 46, all those vectors that are covered by y.sub.1 are eliminated from ##EQU29## This reduced set is called ##EQU30## At step 48, all reproduction words which are covered by some source word from B(y,) are eliminated from ##EQU31## Let ##EQU32##

At step 50, suppose code words, y.sub.1,y.sub.2, . . . , y.sub.k, are already chosen. Let ##EQU33## And let ##EQU34## At step 52, the next code word, y.sub.k+1, is chosen as any reproduction word V.sub.k. (This is necessarily of maximum coverage.) At step 54, source words covered by y.sub.k+1 are eliminated to produce T.sub.k+1 =T.sub.k -B(y.sub.k+1). At step 56, reproduction words covered by vectors of B(y.sub.k+1) are eliminated to form V.sub.k+1 =V.sub.k -B(B(y.sub.k+1)). Steps 52, 54 and 56 are repeated until all reproduction words are eliminated, that is until V.sub.n is empty.

The user of these algorithms chooses the acceptable level of distortion by choosing the appropriate NQ matrix which corresponds to the desired distortion level. As noted above, Q is the joint probability or distribution matrix which achieves minimum mutual information subject to the constraint that the average, per letter distortion is d or less. The average distortion d is selected by the user according to his needs. The NQ matrix may be determined in one of three ways: using Shannon's formula to calculate, by hand, the matrix, using Balhut's algorithm, or by using the algorithm described below and developed by the present inventor. According to this algorithm, as N approaches infinity, (1/N) log (N.sub.cov) approaches the results achievable using Shannon's formulas. The algorithm is shown in the flowchart of FIG. 4 and the "C" program implementing this algorithm is shown in Table III.

In step 60, the user inputs the average distortion on block size N, the distortion matrix and the statistics of the source alphabet in block size N. In the example shown in the flowchart, a two-dimensional matrix is used. In step 62, the values for N.sub.max and N are set. All possible values of the matrix entries are examined to minimize mutual information. At steps 66 and 68, it is determined whether the value of Q.sub.ij is acceptable for block size N. If not, control returns to node A. If so, at steps 70 and 72, it is determined whether the values are consistent with the probability of the source words. If not, control returns to node A. If so, at steps 74 and 76, it is determined whether the average distortion is acceptable. If not, the next incrementation of i,j is examined. If so, at steps 78 and 80, it is determined whether the number of vectors covered by the current matrix is the maximum number covered so far. If so, the matrix is saved and N.sub.max is updated. The program continues to loop to find the maximum until all values of Q.sub.ij are examined.

For source coding problems, the following rational behind the proof presented in the above-cited doctorate shows why minimizing mutual information is equivalent to maximizing coverage. The mutual information between a source, X, and its code, Y, is defined as:

where: ##EQU35## Likewise we define h(Y), h.sub.pi (Q), and h(Y.vertline.X).

It is assumed here that the source, X, takes on values from a finite set of symbols A={a.sub.1, a.sub.2, . . . , a.sub.n } with a distribution (p.sub.1, . . . , p.sub.n), where, for each i, p.sub.i is any real number such that p.sub.i >0 and ##EQU36## P.sub.i =1.

Also we assume the reproduction letters, Y, are taken from the set B={b.sub.1, b.sub.2, . . . , b.sub.m } and the letter probabilities, (q.sub.1, . . . , q.sub.m), are related to those of X by the joint distribution Q.sub.ij by ##EQU37## Qij=q.sub.ij, for all 1.ltoreq.j.ltoreq.s and ##EQU38## Q.sub.ij =p.sub.i, for all 1.ltoreq.i.ltoreq.r, where Q.sub.ij .gtoreq.0.

The number of source words covered by a typical code word is given by: ##EQU39##

This expression converges, in the (1/N) log limit to H(X.vertline.Y). Since the term H(X) is constant (for the source coding problem) we minimize the mutual information by maximizing the negative term H(X.vertline.Y). Hence we can just as well maximize .vertline.B(Y).vertline. for finite N.

The algorithm according to the present invention could also be used to choose channel codes. For channel coding applications, that is the correction for errors produced by noise occurring over channels used to transmit information, the object would be to maximize mutual information, that is, to use an NQ matrix which maximizes mutual information. It can be shown that maximizing mutual information is equivalent to minimizing coverage for fixed q.

It is known that one wants to maximize mutual information for efficient channel coding. It is also known that the mutual information can be expressed as:

In the (1/N) log limit, the number of channel output words covered by a channel code word converges to H(Y.vertline.X). Hence, for finite N, with fixed values of q, we can just as well use a coverage which is defined by a matrix which minimizes mutual information.

It is understood that the present invention, described herein by means of computer software, can be implemented using hardware or hardwired components without departing from the scope of the invention.

The embodiments described herein are implemented using a two-dimensional NQ matrix and a binary alphabet. However, it is understood that the algorithms can be implemented for larger matrices and any arbitrary alphabet by making appropriate modifications to the programs presented herein.

The foregoing description of the specific embodiments will so fully reveal the general nature of the invention that others can, by applying current knowledge, readily modify and/or adapt for various applications such specific embodiments without departing from the generic concept, and, therefore, such adaptations and modifications should and are intended to be comprehended within the meaning and range of equivalents of the disclosed embodiments. It is to be understood that the phraseology or terminology employed herein is for the purpose of description and not of limitation. ##SPC1##