AU4793093A - Data compression system using source representation - Google Patents

Description

DATA COMPRESSION SYSTEM USING SOURCE REPRESENTATION

This application is a Continuation-In-Part of co-pending application Serial No. 300,037, now U.S. Patent No. 5,136,618 issued August 4, 1992. Field of the Invention

This invention relates to a system for compressing or transmitting digital or analog data sequences with a high degree of compression. Background of the Invention It is well known that data carriers, such as telephone and electrical lines, radio and microwave links, optical fibers, and the like have a limited capacity to carry data. There are corresponding limits to the ability of transmitters and receivers to handle data. As a common example, many offices now have telefax machines that allow digital data (obtained by converting the light and dark regions of the document to be sent into a series of data "bits," that is, to a sequence of "l's" and "O's) to be transferred over telephone lines to a receiving machine elsewhere. Because of known physical and electrical limitations of the metal telephone wires, data cannot be transmitted faster than at a certain rate.

Furthermore, the "modems," built into the telefax machines, that actually apply the digital data to the telephone lines also have upper limits on their transmission speed. No matter how fast the telefax machine were to be able to convert a document to digital form, if its internal modem cannot transmit more than, say, 2400 data bits per second, the message cannot be sent and received at a faster rate. Finally, the speed at which the telefax machine can scan a document also limits the speed at which a message can be sent.

A way to improve transmission speed is to make the machines themselves faster. If the telefax machine is able to scan documents fast enough, if its modem can transmit at 4800 bits per second instead of only 2400, if the transmission medium is able to carry data at this rate, and if the receiving device is able to receive at this rate, then transmission speed can be doubled.

Another way to improve transmission speed is to use a transmission medium that has a greater "bandwidth," that is, a greater ability or capacity to carry data. Optical fibers, for example, transmit data in the form of light pulses, and as such they have a much greater data capacity than traditional copper wires, over which data is transmitted in the form of electrical signals.

Still another way to increase transmission speed is to compress the data to be transmitted. Continuing with the telefax example, assume one wishes to transmit a letter with only ten lines of typed text in the top half of a normal sheet of white paper. In a normal telefax machine, this document is scanned as a large number of lines, each consisting of a large number of adjacent points or picture elements ("pixels") . For the purpose of this example, assume that the scanner scans the document as a series of 1000 lines, and that each line consists of 1000 pixels; in other words, assume the telefax scanner divides the page into 1000 x 1000 = 1 million points.

During scanning, each pixel is for example assigned a value of "1" if it is mostly black and a value of "0" if it is mostly white. (More sophisticated telefax machines use different schemes, and many even represent each pixel as having one of several shades of gray.) In the example, the page can therefore be represented as a string of 1 million bits (l's and O's). With only ten lines of actual text, however, very few of the points are black, and probably at least 99% of the transmitted data string will consist of zeroes; in particular, the bottom half of the page contains no text at all, but needs 500,000 bits, all zeroes, to represent it. One transmission method in this example would be to transmit all 1 million data bits as they are. On the other hand, this would waste time and data storage space, since most of the transmission would contain no useful information (such as the bits representing the text) . The time it takes to transmit the 500,000 "bottom half-page"-bits is wasted, since the transmission medium, such as the telephone line, is not able to be used for other, information-carrying messages while these bits are being transmitted.

One can reduce wasteful transmission by observing that the data series to be transmitted has a certain structure. In the example, one could notice that most ones, and especially zeroes, tend to occur in long strings rather than randomly. Indeed, the bottom half of the page is represented as a single string of 500,000 zeroes.

According to one known data compression scheme for telefax machines, which recognizes this characteristic structure of many telefaxed documents, one does not transmit the actual ones and zeroes representing the document, but rather transmits the length of the current bit string. For example, instead of transmitting a sequence of ten "l's", followed by ten "O's", followed by five "l's", followed by 500,000 "O's", one instead simply transmits the numbers 10, 10, 5, and 500,000. By telling the receiving machine that one is beginning with a "black" string, and that each new number represents a change of string color, one can transmit only the four numbers (which can be represented digitally using only a few tens of bits) instead of a string of 500,000 + 10 + 10 + 5 = 500,025 bits.

When the telefax receiver receives the string (10, 10, 5, 500,000) it begins by printing 10 black points, then switches to printing 10 white points, then it switches to printing 5 black points, then it switches to printing 500,000 white points. By taking advantage of the structure of the original data string, one is therefore able to include the same information in a much shorter string. This in turn allows one to send the same message cheaper and faster, and to take up less of the capacity of the transmission medium.

The receiver can receive and store the string (10, 10, 5, 500,000) very quickly even though it will take much longer actually to reprint the telefaxed document. The drawback of this data compression scheme, however, is that it achieves a high degree of compression only when the transmitted data contains many long strings of unchanging binary digits. The maximum degree of compression would be had if the transmitted page were all black (1 million "l's" in a row) or all white (1 million "O's"), since one then would only have to transmit a single number (1,000,000) to recreate the text fully.

On the other hand, this scheme would achieve no compression at all if the original document consisted of a checkerboard pattern of alternating black and white pixels; in such case, the system would have to transmit a string of a million "l's" (each string is only one pixel long, and there is a color change after every pixel) . Since these would not be simple binary bits, but rather a million blocks of bits (each long enough to represent the largest possible transmitted number 1,000,000), it would actually take much longer to transmit the "compressed" data stream. The compression system requires the input data itself to have a certain structure in order for the system to be efficient.

The telefax example was given as one type of system where compression is useful but may not in every case achieve the desired result. Similar problems of data compression and efficiency are encountered in many other technical fields, such as the transmission of speech in digital form, digital television, and other areas in which information is to be communicated as a sequence of numbers. Since a majority of transmission of information, such as over modern carriers (satellites, optical fibers, etc.), is accomplished digitally (by transmitting binary numbers) , the goal of increased capacity through data compression is found in many aspects of modern telecommunications technology. Accordingly, there is a need for a data compression system which provides for a greater capacity for transmitting or handling data, and a system which provides faster handling of data resulting in greater data or information throughput. There is also a need for a system and method providing for a greater data compression than previously afforded.

Accordingly, an object of this invention is to provide a system for data communication that achieves a greater degree of data compression than is possible using existing systems.

It is a further object of the present invention to provide a method and apparatus for handling data or other information which has a greater capacity for handling the data than previously available, and which handles the data faster than previous methods and apparatus.

It is another object of the present invention to provide a method and apparatus for allowing greater data or information throughput for various data and information handling apparatus.

It is a further object of the present invention to provide a method and apparatus for increasing the capacity and speed with which data is handled by computers and by which data can be transmitted from one computer to another. Summary of the Invention

In accordance with the present invention, a data compression system and process is provided which allows for greater capacity for data handling and transmission, faster data handling and therefore greater information throughput and which provides for greater data compression, all without loss. A data compression system is provided with means for accepting a series of data at an input representing information to be transferred. Means are provided for selecting one or more labels to represent at least a portion of the series of data, the selecting means including systems of equations having corresponding labels and which systems of equations produce numerical data sequences. Means are also provided for transmitting the labels.

In a further form of the invention, a data compression system includes means for selecting one or more equations, representing one or more families of orthogonal bases to represent at least a portion of the series of data wherein each equation has a corresponding unique label. Means are further provided for transmitting to an output the one or more labels corresponding to the selected equations.

In another preferred form of the invention, the means for selecting includes means for selecting one or more maximal sequences. For example, a data_^compression system is provided which includes means for accepting a series of data representing information to be transferred. Means are also provided for selecting one or more maximal sequences to represent at least a portion of the series of data. Means are also provided for transmitting to an output representations of the one or more maximal sequences. A method is also described herein for constructing a set of algorithms to be used in a data compression system, such as may be in the form of a plurality of finite state machines. The method includes the steps of defining a set of equations wherein equations in the set of equations are orthogonal with respect to each other to form orthogonal bases to be used to represent at least a part of a sequence of data and retaining the set of orthogonal bases. The method further includes the step of assigning a unique label to each basis, wherein each label represents the corresponding basis formed in the step of defining the step of equations. In a preferred embodiment, for example, the step of defining a set of equations includes the step of defining at least one maximal sequence. The step of defining at least one maximal sequence may include defining at least one maximal sequence of length N, and

N - 1 cyclic shifts of the maximal sequence of length N. In a further preferred form of the invention, an encoding processor divides the data sequence generated by a source into blocks of N binary bits, which are then converted into blocks of N numbers. The N numbers are the corresponding arithmetic values of the binary bits or numbers. The value N is preferably chosen to be a Mersenne prime number of suitable size to enable efficient compression yet provide for acceptably rapid computation. The encoder then calculates a maximal sequence of length N for the first block. This maximal sequence, plus its N - 1 cyclic shifts, forms a basis of N vectors. The system may also provide a number "i" specifying by how much the "0th" basis is to be shifted to get a different basis vector.

The N vectors or bases may then be stored in one or more processors, for example, such as a transmitting computer and a receiving computer or a computer suitable for storing compressed data, and assigned unique labels for use in communicating data. In the situation of the transmitting and receiving computers, incoming data is converted, a maximal sequence is found and one or more of its N - 1 cyclic shifts is selected to represent a portion of the data. The labels for the maximal sequence and the related cyclic shifts are then transmitted to the receiving computer, and the receiving computer can recreate the same data block without loss. Alternatively, the system transmits the label for the maximal sequence and the indices of the basis (the degree of shift of the "0th" basis) . Therefore, by determining an appropriate maximal sequence, in this example, the system can increase the capacity by which it handles data, thereby increasing the speed with which data is handled and increasing the throughput of data or other information. This system provides a relatively high amount of data compression. This method and system can be used for a wide range of applications, including the telefax application previously discussed. One aspect of the telefax example that one should observe is that, using the described data compression scheme, one is not transmitting the actual data string representing the original message (the digitized document) , but rather a "blueprint" for how the receiving machine itself can reconstruct the original message. One transmits a description of the characteristics of the original data stream instead of the data stream itself.

In accordance with the present invention, instead of transmitting a shortened (compressed) version of the data sequence, the system according to the invention constructs a series of data "building blocks" or "data generators" which it can combine to form a model of the data source that, when activated, generates the same data sequence one wishes to transmit. Instead of transmitting data, one may transmit information that tells the receiver how to combine its data generators in such a way that the receiver itself creates the data sequence anew. The "data generators" may be described mathematically as so-called "finite state machines," which may be implemented using one or more processors. The characteristics of these finite state machines are pre-defined and stored both in the transmitter and in the receiver. The system then analyzes the input sequence to determine which of the series of constructed finite state machines will generate the data input sequence. Alternatively, the characteristics of the finite state machines may be created upon initialization of the system. Thereafter, codes or instructions used for creating the characteristics of the finite state machines may be transmitted to the receiver. The transmitter and receiver are then similarly configured, and the transmitter can then send signals identifying which finite state machine, or combination thereof, will recreate the data sequence input to the transmitter. Instead of transmitting the sequence itself, or characteristics about the sequence, the transmitter according to the invention instead transmits a signal identifying which, or which combination, of the finite state machines is able to recreate the input sequence; such a transmission requires very few data bits. The receiver can then activate this finite state machine and let it run to regenerate the data input sequence. The invention therefore develops a model or representation of the original data source, whereupon the model recreates the desired data sequence without loss within the receiver. Brief Description of the Drawings

Fig. 1 is a schematic representation of two data processing units which can be used for the data compression of the present invention.

Fig. 2 is a schematic and block diagram of a transmitter and receiver incorporating aspects of the present invention and depicting the process according to the present invention.

Figs. 3A and 3B are flow charts depicting the overall process of analysis and encoding and synthesis and decoding, respectively, according to the process of the present invention. Description of the Invention

In accordance with the present invention, a data compression system, depicted in the top block of Fig. 2, may be implemented in a number of applications. Fig. 1 depicts a transmitting and processing computer 2 containing a data compression system to receive and compress data according to the present invention and output one or more maximal sequences selected by the data compression system to represent at least a portion of the series of data to a modem 3 to transmit the maximal sequences to a receiving modem 4 linked to a receiving computer 5 containing the synthesis and decoding system for accepting the maximal sequences and synthesizing the series of data from the maximal sequences and the other information received by the transmitting computer 2. The systems depicted in Fig. 1 are simply one representation of apparatus which can be beneficially used with the present invention to more easily and quickly handle data and information. Other applications of the invention easily come to mind, including for telefax applications, transmission of speech in digital form, digital television or recording and the like.

Before delving into the actual construction and operation of the invention, it is helpful to understand the concept of source representation. FIG. 2 illustrates the concept in the form of a greatly simplified telecommunications system. In FIG. 2, a transmitter 10 is intended to transmit data over a transmission medium 12 to a receiver 14. The medium 12 may be electrical wires, electromagnetic radiation, optical fibers, etc.

The transmitter includes, or, more commonly, is connected to, a data source 16, which produces an output signal that can be converted into numerical form. The source could be, for example, a document scanner, a speech digitizer, a computer containing data one wishes to transmit, a television camera, telemetry or scanning equipment in a satellite, or any of the virtually countless other modern devices that generate information in digital form. The numerical data may be numerical sequences from primary digital data or discretized forms of analog data, for example. In the illustrated example, the source 16 has generated a string of fourteen binary digits. The transmitter also contains a coder 17, whose function is described below. The receiver 14 includes a controller or processor 18 and N digital networks or finite state machines (labelled FSM1, FSM2, . . . , FSMN) . Each finite state machine generates a unique output signal XI, X2, ... , XN in the form of a finite string of binary digits. FSM1, for example, when activated, generates the sequence 1100101. The structure of finite state machines is well understood in the field of digital electronics, and is discussed, for example, in Digital Networks and Computer Systems. Taylor L. Booth, John Wiley and Sons, Inc, 1971. Of interest to this discussion is that the components FSMl-FSMN generate unique strings of a fixed number of binary digits.

The controller 18 is connected (via output lines Al - AN) to each of the finite state machines FSM1 - FSMN, and receives the generated data strings from the state machines via input lines II - IN. The controller 18 is able to select any or all of the state machines and to combine their output signals. In this regard one should recall the binary, logical operators AND and OR. Given two binary strings X and Y, one forms (X AND Y) by multiplying their individual digits pairwise. Thus, (101 AND Oil) is 001; that is, each digit in the result is a one only if the corresponding digits in both the input strings was a one. To form (X OR Y) , one forms a resulting string that has ones only in positions where either or both of the input strings has a one in the corresponding position. Thus, (101 OR 011) is 111.

In the example shown in FIG. 2, the source 16 has generated an output string of 14 binary digits (10001001001110) that are to be transmitted. As is mentioned above, one could simply transmit these 14 bits, but this would achieve no compression. One could also try some encoding scheme such as transmitting the length of strings, but in this case, since one cannot assume long, unchanging strings, even such a scheme will not increase transmission efficiency. On the other hand, assume that the coder 17 contains information about the output strings that the state machines FSM1 - FSMN generate. The coder first divides the source output string into blocks Bl and B2 each having seven bits (the same length as the output strings of the state machines. The coder then can analyze block Bl and determine that it in fact can be obtained by forming (XI AND X2) : (1100101 AND 1000110) = 1000100 = Bl. Similarly, the coder can determine that B2 = (X2 OR XN) .

Instead of transmitting the whole 14-bit string, the transmitter can therefore simply transmit short signals identifying which state machine(s) the controller 18 is to select, as well as short signals indicating which operations are to be performed on their output signals. The controller 18, after making the appropriate combinations, then allows the state machines to run so that the source output sequence is recreated within the receiver. In essence, the state machines, through proper combination, act as the source itself — the source is modelled within the receiver, and all. that is transmitted is information necessary to configure the model. The finite state machines shown in FIG. 2 are merely representative of the class of structures that can be used to represent a data source. In certain applications, it may be sufficient to have a single state machine, which generates different output strings depending on what starting values the controller gives it. In another class, the state machines each have a set output data sequence that they generate, but each sequence can be generated in a different cyclical order; for example, a machine whose output was ABC could also generate CAB and BCA by shifting each letter to the right one step and "wrapping around" so that the last letter in one sequence becomes the first letter of the next sequence. (Letters of the alphabet are used only for the sake of clarity; strings of binary digits can be cycled in the same manner.) With the example shown in FIG. 2 it is not altogether apparent that one will be able to model all possible sources 16 by combination or other manipulation of the outputs of the state machines FSM1 - FSMN, although it is almost always possible to construct a finite state machine that will generate a desired finite output. For example, assume one only has state machines that generate XI = 100 and X2 = 010. No simple combination of AND or OR operations can produce an output with a "1" in the third position; either another state machine, a different type of output, or different permissible operations would be required. For example, if one also had the state machine that generated X3 = 001, one could reconstruct all eight possible 3-bit words by combination of XI, X2 and X3. In other words, XI, X2, and X3 form a complete basis for reconstruction of all 3-bit data sequences. Clearly, the choice of state machines and their outputs, and the process by which the outputs are manipulated determines which class of sources one can model (and transmit modelling parameters for) .

With only 7-bit data blocks Bl and B2, the degree of compression that can be achieved by such a transmission system is relatively small, since it may take more than seven bits actually to model the source. On the other hand, one can show theoretically that the degree of compression one can achieve increases greatly with increasing block size; the key is to choose a set of output data (bases) from state machines or their equivalents (such as simple, stored listings of their desired output sequences) , and suitable operations to perform on the set, such that one can model efficiently a desired or anticipated class of sources. This invention provides just such a key; it determines a complete basis of a much higher order than three, so that the system according to the invention is able to reconstruct sources that produce much longer data sequences, and thus is able to achieve a high degree of data compression. Maximals as a Complete Basis

According to the invention, a data sequence of binary digits is first converted to an equivalent sequence of "real numbers," in part so that ordinary arithmetic operations may be performed on each digit in the normally understood manner (for example, rather than having to manipulate AND's and OR's, one can use normal multiplication and addition) . One way to do this is to assign the value -1 to every binary "1" and the value +1 to every binary "0"; thus, the binary sequence (1, 0, 0, 1) is converted to the arithmetic sequence (-1, 1, 1, -1) . The assignment can be represented using the known function "aval," which stands for

"arithmetic value"; thus: aval(x) = +1 (real number) when x = 0 (binary number) and

= -1 (real number) when x = 1 (binary number) .

All operations in the system according to the invention are then carried out using conventional arithmetical operations on the arithmetical ("aval") equivalent of data sequences. The system according to the invention also calculates a complete basis for data sequences that will fully model all sources in a predetermined class. The basis that is calculated is a collection of so-called maximal seguences. The theory of maximal sequences is developed in the literature, but a brief description is given below.

Orthonormality

Returning for the moment to the 3-digit binary system, a system with the basis vectors (1,0,0), (0,1,0) and (1,1,0) would be inefficient, since it would be possible to obtain the third vector by taking the first two together with an OR combination. The third vector adds nothing to the ability to reconstruct other vectors since it is similar to the other two. In other words, the third vector has too great a correlation with the others. Ideally, all the vectors are uncorrelated with or "orthogonal" to the others or combinations of the others.

Given a data sequence of length N, there are several ways in which to develop a set of N orthogonal base vectors with which one can reconstruct source sequences through proper manipulation. One common procedure for producing such vectors is known as the Gram-Schmidt process. Unfortunately, in order to create a set of N base vectors, this procedure requires approximately N² computations. It thus takes on the order of 1,000,000 computations to convert a set of 1,000 non-orthogonal base vectors to orthogonal form. For the purposes of rapid data compression, this computational burden is often too great, and is in most cases undesirably slow. A better approach, taken by this invention, is to start with a set of vectors that are known to be orthogonal or at least nearly so. According to the invention, a maximal sequence of length L and its N-l cyclic shifts are chosen as the base sequences. The disadvantage of using maximal sequences as the base sequences is that maximal sequences are structurally very complicated except for the sequences whose lengths are so-called Mersenne primes, that is, for lengths N that are prime numbers and that have the form 2^P-1, where p itself is a prime number. (Lengths of 7, 35, 127 and 8191 are all examples of Mersenne prime lengths, for p = 3, 5, 7 and 13, respectively.) It can be shown that when N is a Mersenne prime, a single maximal sequence of length N and its N-l cyclic shifts comprises a universal basis for all sequences of N real numbers. In other words, if one is given a sequence of N real numbers, one can also construct a single maximal sequence that, together with its N-l cyclically shifted sequences (shifted one step to the left or right and

"wrapped around," as for the ABC, CAB example given above), can be used to reconstruct any sequence of N real numbers.

This construction is also very efficient, and one can prove theoretically that it is possible to construct such a universal basis for a data sequence of N real numbers using no more than p binary numbers, where p < 1 + log₂(M^CN]+l) and M^CN] is the smallest Mersenne prime that is not less than N. For example, if one has a sequence of 31 real numbers, then one needs only 1 + log₂(31+l) = 1 + 5 = 6 binary numbers for complete reconstruction. In order to reconstruct any sequence of N = 8191 real numbers, only 13 binary numbers would be needed.

The method according to the invention is accordingly for an encoding processor to divide the data sequence generated by a source into blocks of N binary bits, which are then converted into blocks of N numbers (the corresponding arithmetic values of the binary bits or numbers) . The value N is chosen to be a Mersenne prime number of suitable size to enable efficient compression yet acceptably rapid computation. The size of N will depend on the application, and on any knowledge of the structure of the source sequences.

The encoder then calculates a maximal sequence of length N (using predetermined and well-defined equations) for the first block. This maximal sequence, plus its N-l cyclic shifts, forms a basis of N vectors. Note, however, that it is not necessary to transmit all N vectors; it is sufficient to transmit the original maximal (0-shift) . Since all others have the same elements, just shifted by a certain number of positions, once a receiver has the "0^th" basis, it is only necessary to transmit a single number i specifying by how much the "0^th" basis is to be shifted to get a different basis vector.

When each succeeding source data block is sufficiently similar to the block from which the maximal was calculated, the values to be transmitted to the receiver are the indices of the bases (the degree of shift of the "0^th" basis) , and a decoding processor in the receiver can then reconstruct the source data block. In effect, the receiver creates a model or representation of the source, which is then "activated" to recreate the data sequence the "real" source generated. If the successive data blocks differ too greatly from the preceding (determined according to known formulas) , the encoding processor recalculates a new maximal and the encoding and compression procedure is carried out again. According to the invention, the encoding and decoding processors also perform certain other calculations on the various data sequences in order to transform them into more easily manipulated and analyzed forms. However, the blocking of source data into blocks of Mersenne prime length, the calculation of maximals, and the transmission only of maximals and shift indices for source reconstruction remains. The method according to the invention provides a much greater degree of data compression for long data sequences than is possible using existing compression systems.

With the foregoing general description of the invention, a more detail discussion of the invention will be provided below. Principle of Operation

The general principle of operation of the invention is as follows:

A binary data sequence (the input sequence) is analyzed to determine which finite state machine, which may be in the form of an algorithm

(sometimes termed the generator algorithm) of a labeled collection of finite state machines (sometimes termed the generator class of algorithms) , all of which produce binary data sequences, will produce the input sequence. The label of this selected finite state machine is assigned to the input sequence and is designated the source representation for the input sequence. The input sequence is retrieved as the output sequence by selection, from the generator class of algorithms, of the algorithm whose label is the Source Representation of the input sequence and initiation of operation of this algorithm. Utilization of Source Representation Data Communication in Data Transmission

If Source Representation Data Communication is utilized as an operational element of a data transmission system in which the Source Representation of the input sequence is itself represented as a binary sequence (the Source Representation Code of the input sequence) , and if this Source Representation Code is the sequence actually transmitted, and if the receive element of the system retrieves the input sequence as the output sequence in accordance with the above description of Source Representation Data Communication, then:

Where the input sequence and the Source

Representation Code of the input sequence have identical bit timing, the effect of Source

Representation Data Communication is that the input sequence is transmitted and its replica output sequence is received with a code-bandwidth transmission factor that is the ratio of the length (number of binary elements or bits) of the input sequence to the length (similarly defined) of the Source Representation Code of the input sequence. Construction of Generator Classes of Algorithms An algorithm is a specification of a finite collection of arithmetic processes that produce assignments of numerical values to resultants (outputs) by application of arithmetic operations to numbers that are assigned values of operands (inputs) . An algorithm is described by a collection of algebraic equations. For the purposes of this discussion, the complexity of an algorithm is indicated by the number of independent equations in its specification. Algorithms may have intermediate resultants, and some of these may also be intermediate operands; such algorithms are said to be recursive. This concept is also the basis for decomposition and concatenation of algorithms. These last attributes of algorithms are strictly ancillary to this discussion.

Since all members of a generator class of algorithms must produce binary sequences, it will always suffice to consider only binary arithmetic algorithms. That is to say, it will suffice to consider only algorithms whose operands and resultants are binary variables and that are realized by arithmetic processes consisting entirely of binary arithmetic operations, whether formulated as direct or recursive computations. Such algorithms are necessarily reducible to linear functions (disjunctive normal form) of all initial and intermediate operands. Hence:

Any generator class of algorithms is a subclass of the class of all binary arithmetic algorithms. Every finite binary sequence (in any realization, a

Source Representation Data Communication can operate only upon finite sequences) has at least one (trivial) generator algorithm. (For a binary sequence {a_n: l ≤n ≤N) the trivial generator algorithm is {χ_Q = 1 ; x_n = a_n- x₀: l≤n ≤N) . ) There consequently exists a generator class of algorithms for any finite sequence, and there is at least one generator algorithm for this sequence that has a minimum number of explicit relations (equations) in its specification. This is a minimal generator of the sequence. The example just given of the trivial generator indicates that any minimal generator of a sequence of length n has at most n + 1 independent (non-redundant) equations in its specification.

There consequently exists a generator class of algorithms for any collection of finite sequences. If every member of such a collection of sequences has a representation as an arithmetic combination of elements of some one fixed collection of sequences (a collection of basis sequences) , then the minimal generators of these basis sequences form a set of basis algorithms, and all members of the generator class of algorithms for the original collection of sequences can be expressed as algebraic combinations (the basis algorithm synthesis) of the elements of set of basis algorithms. These algebraic combinations are necessarily realized as formulas (the synthesis formulas) consisting of specifications of the corresponding arithmetic combinations of the outputs of the basis algorithms. The complexity or otherwise of these basis algorithm syntheses will clearly depend upon the form of the basis sequence representations of the original collection of sequences.

The set of basis algorithms is an algebraic structure common to all generator algorithms for the given collection of sequences. This set of basis algorithms can be minimized by discarding those basis algorithms that can be synthesized using other basis algorithms; the basis algorithm syntheses of the elements of the generator class of algorithms can then be restated in terms of this minimal set of basis algorithms. The basis algorithm syntheses can also be reduced in complexity by the elimination of redundant terms. Application of these steps will produce a minimum basis algorithm synthesis for each generator algorithm, but there is in general no guarantee that this minimum synthesis will be unique; there may be several valid minimum syntheses for a given generator algorithm. Notwithstanding this fact, specification of any minimum basis algorithm synthesis of a particular generator algorithm will uniquely identify the binary sequence produced by that generator. The details of specification of the elements of the basis generator class of algorithms are unnecessary to this identification if the objective of identification is restricted to selection only from among the original collection of sequences; all of these sequences have the same set of basis generators and differ only in their basis algorithm syntheses.

The previous discussion provides the basis for the identification and exact reconstruction of each of the original sequences: For any collection of binary sequences, and for any collection of basis sequences for this collection,

Each sequence of this collection completely specifies its representation in terms of the basis collection;

Each such basis representation completely specifies a corresponding synthesis formula; Each such synthesis formula completely specifies a generator algorithm for the original sequence.

The original sequence is retrieved by execution of the generator algorithm. Summarily, any basis representation of the original sequence specifies a synthesis formula, and any such synthesis formula enables retrieval of the original sequence.

Universal Basis Sequence Collections The mathematical theory of basis structures is extensively developed, and can be considered well-known to anyone "skilled in the art" of mathematics. Arithmetic computational processes involving binary numbers are implemented by the use of the ival ("integer value") function that maps binary numbers onto their symbolically corresponding real integers: ival (x) = 1 (real number) when x = 1 (binary number) ; = 0 (real number) when x = 0 (binary number) .

The function inverse to ival is designated ival^"1 and is defined in the conventional manner.

The theoretical basis for Source Representation Data Communication is developed in terms of a second pair of mappings designated aval ("arithmetic value") and bval ("binary value"): aval(x) = +1 (real number) , when x = 0 (binary number) ;

= -1 (real number) , when x ~ 1 (binary number) . This function is defined for binary numbers and takes on the real number values +1 and -1. The bval function is inverse to aval and is defined by the relations: bval(x) = 1 (binary number) , when x = -1 (real number) ;

= 0 (binary number) , when x = +1 (real number) .

This function is defined for the real numbers +1 and -1 and takes on binary number values.

The functions ival and aval are related by two identities: aval(x) = 1 - 2- ival(x) ; ival(x) = ¹ - av l⁽x⁾ .

2

The correlation of two binary sequences is a real number that quantifies the degree of similarity of the sequences. Sequence pairs with large absolute correlation values are highly similar, and pairs with low absolute correlation values are highly dissimilar. The value of the correlation function for any two binary sequences is the number of termwise agreements less the number of termwise disagreements. Sequences with zero correlation have exactly as many terms that differ as terms that are the same. Clearly sequences whose lengths are odd numbers cannot have zero correlation; such sequences may exhibit a minimal degree of correlation with correlation values of +1 or -1. Sequences with correlation values of N are termwise identical, and sequences with correlation values of -N are termwise complementary.

The correlation of two binary sequences (x_n) and {y_n} assumes a very simple form in terms of the aval function: N p ( {χ_n) , {y_n} ) = ∑ aval ( x_n Θ y_n ) n=1 N

= £ ( aval ( x_n ) ) ^• ( aval ( y_n ) ) . n=1

The symbol Θ designates conventional binary addition.

The correlation of binary sequences, in other words, is the conventional numerical correlation of the arithmetic evaluation of the sequences given by the aval function. If all binary numbers are represented in the Source Representation Data Communication computations by their aval equivalents, then correlations can be implemented with the conventional correlation formulas. Thus:

The implementation of a Source Representation Data Communication is initialized by application of the aval function to replace all input sequences by their arithmetic equivalents, and all Source Representation Data Communication processing is performed using conventional arithmetic operations thereon.

In other words, binary data is represented biuniquely as sequences of +1 and -1 numbers. This representation is to be understood throughout the remainder of this presentation; the aval notation will be suppressed, and binary data sequences will be treated as sequences of real numbers having values +1 and -1. The formula for the correlation function is then simply

N p({χ_n), {y_n}) = ^~ - y_n . n=1

In the standard theory, basis collections are orthonormal (orthogonal and normal) , that is, the correlation of two basis sequences has the value 0 (orthogonality) if the sequences are distinct, but has the value 1 (normality) if they are identical. Normality is easily achieved for any sequence by multiplicative scaling, but orthogonality requires some calculation effort if the candidate collection does not already have this property. The Gram-Schmidt process will convert any collection of candidate basis elements into an orthonormal collection, but if the collection has ab initio a common correlation value, this process reduces to a simple arithmetic scaling. Since the Gram-Schmidt process in general requires on the order of N² computations to orthogonalize N sequences of length N, it will materially simplify a Source Representation Data Communication to start with a collection of sequences that have some small common correlation value.

A maximal sequence and its termwise cyclic shifts are a strong candidate for this selection; the proper mutual correlations of such a collection of sequences all have the same minimum value (0, +1, or -1) . The disadvantage of this selection is that maximal sequences are structurally complicated except for the sequences whose lengths are Mersenne primes, that is, for lengths N that are prime numbers and that have the form 2^P - 1. (p must also be prime for such an N to be prime.) Mersenne primes have been found of such large magnitude that a requirement that the sequences to be considered be of Mersenne prime lengths is not a practical restriction on any Source Representation Data Communication that depends on such an assumption. The formal statement of maximality is as follows:

{m ( n ) = ±1: n = 0 , 1, 2 , ^{• • •} , N - l) is a maximal sequence if and only if

N-1 in ( n mod N ) m ( (n + k )mod N ) = N when k = 0 n-⁴-0

= -1 when k ≠ 0 It follows readily that

N-1

∑ m (n ) ~ ±1; n=0

Trivial replication of complements is avoided by uniform choice of the negative option. The collection of cyclic shifts of a maximal {m} is converted to an orthonormal basis (relative to the metric generated by the correlation operation) by a linear arithmetic transformation; if (m) is any element of the collection, its corresponding orthonormal basis element is

Shifted versions of m produce shifted versions of m . This procedure is referred to here as the arithmetization transformation. Its inverse is:

The N sequences im) are orthonormal, as is readily verified by direct calculation of their correlations, and therefore any sequence of N real numbers can be represented uniquely as a linear combination of shifts of im) . For any Mersenne prime N and any selection of a maximal sequence (m(n)), the shifts of this maximal therefore generate a universal basis for representation of all numerical sequences of length N; the computational processes of the representation are implemented in principle by application of the inverse arithmetization transformation just described to the conventional orthogonal basis computations. In summary: When N is any fixed Mersenne prime, a single maximal sequence of length N and its N - l cyclic shifts comprise a universal basis for all sequences of N real numbers. The maximals of a given length have structural properties that separate them into properly and trivially distinct species; when N is a Mersenne prime, the number of properly distinct species of maximals is (N - l ) /μ The distinction between "proper" and "trivial", in the mathematical sense, is well understood and is therefore not discussed in detail here; the properly distinct species are structurally related in such a way that the transformations from one such species to another form an Abelian group, that is, these transforms are all iterations of a single transform.

The binary version of each such species of maximal of Mersenne prime length 2^p-lis generated by a binary shift register of length p; the arithmetic version of this binary generator algorithm is

N-1 m n ) = ^~~[ l( ( a ( k ) + l ) m ( n - k mod N ) + ( a ( k ) - 1)) k=0 ²

in which the numbers (a(k)} have either the value +1 or -1 and are parameters that completely determine the species of the maximal. Various combinatorial equivalents of this expression are useful for calculations, but this representation is used as stated in the implementation of Source Representation Data Communication computational algorithms. For Source Representation Data Communication, the salient features of all these formulas are, firstly, that, as noted, a complete universal basis representation is produced using exactly one maximal, and secondly, that any such maximal requires specification of only p ~ log₂ N binary numbers (a (k ) : 1 < k ≤ p) . Since any realizable finite sequence (one that could conceivably be recorded by some means) can be embedded in a sequence of Mersenne prime length, it follows that:

A universal basis can always be constructed for a collection of sequences of realizable length N that requires no more than p < (1 + log₂ M ^m ) + 1 binary numbers for its complete specification, where M ^CN] is the smallest Mersenne prime that is not less than N. Partitions of Collections of Sequences Generated by Universal Basis Representations

It can be shown that every cyclic shift of a maximal sequence is also maximal, and the collection of all maximals of a given length N is thereby sorted into disjoint subcollections of maximals that are equivalent in this sense, i.e., any two elements of such a subcollection are not only maximal sequences, but they are also cyclic shifts of each other. Maximal sequences belonging to different subcollections are essentially different in that no cyclic shift operation can possibly make them identical. These subcollections are referred to as species of maximals, and the structural differences among species are in general very complicated and difficult to describe quantitatively. When N is a Mersenne prime, however, the several species of maximals of length N are constructively defined by a binary- valued function χ (s) whose domain is the non-negative integers mod (N - l)/p. This function is referred to as the characteristic or signature of the species, and it specifies the distribution of signs in the binary arithmetic form of any maximal. The characteristic is constrained by the relation

N-l..,

∑ χ(s) = o . s=0

Not all possible such binary functions are characteristics, but any cyclic shift of a characteristic is also a characteristic. The cyclic shift operations on characteristics form an Abelian group since all cyclic shifts are iterations of the cyclic shift that advances every term by exactly one position. There is always at least one characteristic that is maximal relative to this Abelian group, i.e., for which χ(s + v πodW) ^≡ X(s) for all s only when v is a multiple of (N - l)/p. This characteristic and its

(N - l)/p - 1 cyclic shifts will be referred to as the proper characteristics of the maximals of length N and the corresponding species as the proper species of those maximals. Given a specification of the characteristic of any one of the proper species of maximals of a fixed Mersenne prime length N, all proper species of such maximals can be fully identified by specification of only the shift index v, whose domain is simply the integers mod (N - l)/p.

The structure described above is a specific implementation of the general situation that arises when the standard basis representation methods are applied to any collection of distinct but equivalent bases. The parameterv in general merely identifies which basis of the collection is under consideration; its structural significance in the maximal species case is extremely useful but remains peculiar to the maximal basis situation. In general, then, let B denote a finite collection of distinct bases for binary sequences of length N. Let L = \ B \ denote the number of bases in B, and let the elements of B be given any fixed order. Label the elements of B by this ordering: = {j (v) : v = 0, l, 2, - ^{• •} , L - l) .

Here (v)is a basis set, and consists of N sequences of N real numbers: Jb(v) = { {b ( n , k j v ) : n - 0 , 1 , 2 , ^{• • •} , N - l): k - 0 , 1, 2,

In the maximal-sequence implementation described above, b ( n , k ; v) is the n^th coefficient of the k-term cyclic shift of a maximal sequence of species v, and L is equal to (N -l)/p. Any binary sequence a ( ^• Xactually, any sequence) has a unique basis representation in terms of each one of these bases:

N-1 a ( n ) = ∑ α (.k ; v ) ^• b ( n , k ; v) . k=0

If now a given sequence a ( ^• ) has basis representation coefficients iα ( k ) : 0 < k ≤N-l) relative to a specific basis, say b(0) , any of the related sequences

N-1 a (n; v) = ∑ α (fc)J (n, k; v) k=0 can be generated from only a specification of the basis index v. It is evident that all such sequences have a common basis representation α(- ) and differ only in the selection of the basis J (v ) used for their reconstruction from this common basis representation. The totality of possible N-term representations therefore creates a basis representation partition of the collection of all sequences of length N, and the structure of this partition depends entirely on the family B of basis collections. A basis representation partition consists of disjoint collections of sequences, and specification of any sequence of a given partition requires only specification of its unique basis index v. In summary:

Any finite ordered family B of orthonormal bases partitions the totality of sequences of a fixed length into disjoint collections of sequences with a common basis representation; any sequence is completely identified relative to the partition to which it belongs only by specification of the order index of its associated basis.

Operational Analysis Procedures for Source Representation Data Communications

The various details of the preceding discussions are assembled and exploited in a description of the general analysis method of a Source Representation Data Communication as follows:

An ordered family B of N-term orthonormal bases is specified.

An input bit stream is segmented into sequences of common length N.

A specific basis is selected and the basis representation of the first of these input sequences in terms of the selected basis is computed. Each subsequent input sequence is compared with all the sequences of the partition generated by the basis representation found for the first input sequence, and if a termwise match is found, the index of the corresponding basis is recorded as the representation number for that particular sequence. When no match is found, a new basis representation is computed and the above process is repeated. Generic Implementation of a Finite-State Source Representation Data Communication Process

When the common-basis-family method described above is used to implement Source Representation Data Communication, the partitions of sequences of length N created by the basis representations are independent of the organization of the basis family (construction and order) ; they depend only upon the input sequence. These partitions were seen to be uniquely labeled by the N-term sequences identified as basis representations and the prior selection of a 0^th basis. The basis representations are therefore independent of the history of the particular Source Representation Data

Communication being implemented, and so constitute state variables for the system. Since, in this case, both analysis and synthesis processes are linear (the orthonormal basis representation and reconstruction equations are linear) , this implementation of Source Representation Data

Communication is in fact a linear finite-state system, and since the input sequence is the only input to the system

(there are no control inputs) , the system is a linear finite-state automaton. These types of systems have been extensively studied and a very considerable mathematical infrastructure (including software realizations) exists in the published literature.

A specific realization of Source Representation Data Communication can be constructed without this degree of elaboration, however; the initial step consists of the selection of a Mersenne prime of sufficient length (e.g., preferably, at least 2¹³ -1 = 8191 with 630 species of maximals, or 2³¹ -1 = 2147843647 with 69273666 species of maximals) , computation of the characteristic for maximals of that length, and construction of a representative maximal of each species. The basis family then consists of the orthonormal bases generated by all the cyclic shifts of these maximals. The remaining steps are generic:

For a fixed family of orthonormal bases B the generator class of algorithms consists of all linear combinations of the basis elements from single basis sequence collections of B. The synthesis formulas in this case are specifications of the members of the family of bases. If the sequence length is a Mersenne

- prime, the synthesis formulas can be reduced to generator algorithms for the maximal sequences of length N. The source representation of any input sequence consists of successive blocks of binary data that include the initializing basis representation followed by a sequence of basis indices. Estimation of the Number of Bits of Information Required for a Generic Source Representation Data Communication

For a preassigned block sequence length N, the Source Representation Code for R blocks of input data as described in section 7 above consists of N strings of N binary numbers (the binary form of the basis representation of the first block) followed by R - 1 basis indices which are numbers from 0 to L - 1, L being the number of distinct bases in the family B. The number of bits required to specify the basis representation is N², and the number of bits required to represent a basis index is log₂L ; the number of bits required to represent R blocks of input data is then

N² + (i. - 1) log₂ .

The number of bits required to represent R blocks of N binary numbers is RN; the ratio of these numbers is N ' + ( R - l)log_{2 =} W _{+ (1} _ 2_} log₂

RN R ^λ R' N which reduces to N as required when R = 1, but which is asymptotically

log₂J-

N when R » N.

When N is a Mersenne prime, N - 2^P, and L ~ 2^p/p , so that this ratio becomes p - log₂p

2 and clearly the effective code-bandwidth factor (the reciprocal of this ratio) is not bounded when the input sequence is such that the blocks of length N remain in a single partition. Constructive Definitions of the Species of Maximal Seguences

The Residue Class Mod N for Mersenne Primes A Mersenne prime is a prime number N of the form 2^p - 1. The integer p is the order of a multiplicative subgroup of the residue class mod N, and the integer L = (N - l)/p (N - l is divisible by p if N is a Mersenne prime) is the order of a multiplicative subgroup of the residue class mod N; this second subgroup is isomorphic with the quotient group of the residue class mod N relative to the first subgroup. The integer 2 is a generator of the subgroup of order p, and there can always be found an integer g that generates the quotient group, i.e., such that g ■= 1 mod N *-> λ = L or 0. Then every element of the residue class mod N is either 0 or uniquely of the form g^λ- 2° for some λ, p subject to 0 < λ < - l, 0 < p < p - l.. λ is a member of the residue class mod L and p is a member of the residue class mod p. Sign Invariance of Maximals Relative to the Generator 2 Subgroup and the Characteristic

By employment of known combinatorial methods, it can be established that for any maximal sequence im ( n ) : 0 < n ≤ N - l) of Mersenne prime length N, there exists a fixed member k of the residue class mod N such that m( ( n + k ) mod N ) = m ( (2 n + k ) mod N ) , -7 = 0, 1, - ^{• •} , N - 1

This result is referred to as the "2's sampling" property of maximals. When k = 0, the maximal m is said to be in its principal phase. Since the above relation will also be satisfied by the complement of any sequence that satisfies it, it is customary to achieve uniqueness by the additional requirement that m(0) = -1 for principal-phase sequences.

In terms of the residue class representation explained above, the 2's sampling property states the invariance of the sign of principal-phase maximal sequence elements over the generator 2 subgroup of its index set; jn(2^pg^λ)is a function of λ alone. This function of λ is the characteristic of the sequence {m} ; m ( (2^pgr^λ) mod N ) = χ ( λ ) , λ - 0 , 1 , ^{• • •} , L - 1 .

Since the product representation of the index n excludes only n = 0, it follows that

N-1 N-1

∑-n(n) =∑-ϋ(n) - m (0) = (-1) -(-l) = 0 n=1 n=0 p-1 L-1 p-1 L-1

= ∑ ∑ ra((2^pg^λ) modW) = ∑ ∑ χ(λ) p=0 λ-O p=0 λ=0

L-1

= p-∑ χ(λ) .

The conclusion is that

L-1

∑ χ(λ) = o λ=0 Construction of Maximal Sequences in Principal Phase

The characteristic is specified above in terms of the coefficients of its maximal sequence. This specification can be phrased so as to exhibit the coefficients in terms of the characteristic; the device used is the Kronecker delta (<5 (^• ) defined to have the value 1 only when its argument is zero, and to have the value zero otherwise:

L-1 p-1

-71 (n) - -δ(n) + ∑ ∑ δ( (n - 2»g^λ) mod N)χ(λ) . λ=0 p=0

The defining equation for the characteristic is derived from the correlation condition for maximal sequences: upon substitution of the above formula into the correlation equation for maximal sequences, there results r(k) = ∑ m(n)m( (n + k) mod N) = (N + 1) δ (k) - 1 n=0

(defining condition of maximal sequence)

L-1

= δ (k) 1 + P∑ X (λ) λ=0

(1 - δ(k) ) ( - χ(λ) - χ( (λ + i) mod L)

L-1 p-1

∑ δ( (1 - g^λl2^Pl - g^λ22^p2) modW)

"^•1. λ2=0 Pl. P2⁼⁰

^x X ( ( λ-, + - + λ) mod L ) χ ( ( λ₂ + λ ) mod L ) ] When k is not zero, it has the form that characterizes the elements of the multiplicative group on the non-zero elements of the residue class mod N; thus, k ~ g^λ2^pmodW and the value of λ in the last expression is that found in this representation of k. Note that the characteristicχ (λ) has only the values +1 and -1, and so the sum in the term involving <5(λ)has the value L and that portion of the formula therefore reduces to N as required when k = 0.

The expression in square brackets depends only upon the structure of the residue class mod N, and so its computation is a primitive step in the formula: let p-1

X ( λi , λ₂ ) = ∑ δ ( ( 1 - g 2 ^Pl - g 2 ^Pz ) mod N ) ;

Pl. P2=° then the equation

- χ((λ + i) modL) - χ(λ) +

L-1

+ ∑ X(λ, , λ₂) χ ( (λ, + λ + ) mod L )

χ ( (λ₂ + λ) mod N ) = -l

is the defining equation of the characteristic (also called the signature equation) . The solutions are sequences of +1, -1 values when suitably normalized, and those that replicate themselves only under cyclic shifts of L steps are the characteristics of the proper species of maximals. There are in general only L such solutions of this equation, and they are all cyclic shifts of each other. Each such solution produces a species of maximal sequence in principal phase from the defining relation stated first above in this subsection.

Computation of the Quotient Group Generator g

The range of the numbers n^p mod N, n being the non-zero elements of the residue class mod N, consists of powers of the quotient group generator g. The quotient group is of order L, and so the powers mod N from 0 to L - 1 of these numbers are all the powers of the quotient group generators. From this collection of numbers it is straightforward to select the primitive roots of g^L = 1. (These are the numbers g such that g^x ~ 1 only when λ = L . ) Any of these will suffice for execution of the procedures exhibited above; the smallest is generally easiest to use.

The following relations exhibit the number-theoretic basis for these remarks:

2^P = 1 mod N; n ~ g^λ2^p mod N -₌> _n = (g ₂ )P = _gpλ₂ ^pp = ₍g ₎ ^λ mo_d I_V; g is a primitive root of g^L = 1 mod N

<= g^p is a primitive root of g^l = 1 mod N (p, L are relatively prime) ; g is a primitive root of g^L = 1 mod N =>

^{g^λ mod N : 0 < λ < Ii-l) is a proper Abelian group of order L.

Generic Flow Chart For Source Representation Data Communication

A Source Representation Data Communication Process may consist basically of two independent system processes; one process operates on input sequences and produces representations of them, and the other operates on representations and reconstructs the original input sequences. These two systems are referred to, respectively, as the Analysis System (Encode) and the Synthesis System (Decode) . Obviously Analysis is associated with transmission and synthesis with reception. Generic flow charts of these processes are exhibited in Figure 3; the necessary elements of prior system design are included also.

Claims (17)

n the Claims

1. A data compression system comprising: means for accepting a series of data at an input representing information to be transferred; means for selecting one or more maximal sequences to represent at least a portion of the series of data, wherein each maximal sequence has a corresponding unique label; and means for transmitting to an output the one or more labels corresponding to the selected maximal sequences.

2. The data compression system of claim 1 wherein the accepting means includes an encoding processor for dividing the series of data into blocks of binary bits and further comprises means for converting the blocks of binary bits into blocks of numbers.

3. The data compression system of claim 2 wherein the means for selecting one or more maximal sequences includes means for determining a maximal sequence of length N for a first block, wherein the first block of binary bits includes a block of N binary bits.

4. The data compression of claim 3 further comprising means for communicating with a remote processor.

5. The data compression system of claim 4 wherein the remote processor includes means for receiving a label corresponding to a maximal sequence from the output of the transmitting means; means for synthesizing the series of data from the maximal sequence corresponding to the label from the transmitting means.

6. The data compression system of claim 3 wherein N is a Mersenne prime number.

7. The data compression system of claim 6 further comprising means for selecting at least one maximal sequence of length N and a number "i" representing how much the at least one maximal sequence is to be shifted.

8. A data compression method comprising the steps of: accepting a series of data at an input of a processor representing information to be transferred; selecting one or more maximal sequences having unique labels to represent at least a portion of the series of data; and transmitting to an output the one or more labels corresponding to the maximal sequences representing the portion of the series of data.

9. The data compression method of claim 8 wherein the step of accepting includes the step of dividing the series of data into blocks of data containing N characters in each block.

10. The data compression method of claim 9 wherein the step of dividing includes the step of dividing the series of data into blocks of binary bits and converting the blocks of binary bits into blocks of numbers.

11. A data compression system comprising: means for accepting a series of data at an input representing information to be transferred; means for selecting one or more equations representing one or more families of orthogonal bases to represent at least a portion of the series of data wherein each equation has a corresponding unique label; and means for transmitting to an output the one or more labels corresponding to the selected equations.

12. The system of claim 11 wherein the means for selecting includes means for selecting one or more maximal sequences.

13. A method for constructing a set of algorithms to be used in a data compression system, in the form of a plurality of finite state machines, the method comprising the steps of: defining a set of equations wherein equations in the set of equations are orthogonal with respect to each other to form orthogonal bases to be used to represent at least a part of a sequence of data; retaining the set of orthogonal bases; and assigning a unique label to each basis wherein each label represents the corresponding basis formed in the step of defining the set of equations.

14. The method of claim 13 wherein the step of defining a set of equations includes the step of defining at least one maximal sequence.

15. The method of claim 14 wherein the step of defining at least one maximal sequence includes the step of defining at least one maximal sequence of length N and N - l cyclic shifts of the maximal sequence of length N.

16. A data transmission method including the following steps: pre-calculating a set of operating parameters for at least one finite state machine; partitioning a data stream into a sequence of data blocks; for each data block, transmitting a set of labels, whereby each label uniquely identifies one of the sets of operating parameters of the finite state machines; and in a receiver, reconstructing each data block as an algebraic combination of output sequences from the finite state machines corresponding to the transmitted labels.

17. A data compression system comprising: means for accepting a series of numerical data at an input representing information to be transferred; means including systems of equations having corresponding labels and which produce numerical data sequences for selecting one or more labels to represent at least a portion of the series of data; and means for transmitting to an output the one or more Labels corresponding to the portion of the series of data.