Abstract:
An apparatus and method for using an error correcting code to achieve data compression in a data communication network is disclosed. Data compression is achieved by performing an error correction encoding operation on input data. Data compression is further achieved by providing, for transmission across a communication channel, compressed data that is representative of the input data. The compressed data preferably includes error correction information produced by the error correction encoding operation. The compressed data requires less transmission channel capacity than does the input data.

Description:
TECHNICAL FIELD OF THE INVENTION 
   The present invention is directed generally to data communication systems and, more specifically, to the use of error correcting codes to perform data compression in such systems. 
   BACKGROUND OF THE INVENTION 
   Data compression is a useful tool for reducing the bandwidth required for communication of data on a transmission channel. 
   Some current compression schemes, such as Huffman compression, require knowledge about the frequency of expected data words, while others rely on compression of repeated data words, such as run length encoding, or require state information. Both lossless and lossy codes are available. Huffman compression and run length encoding are examples of lossless compression, and MP3 is an example of lossy compression. 
   Codes requiring knowledge of the frequency of expected data, such as Huffman codes, are useful for applications like the English language, where knowledge of the frequency of letter occurrence in English words can be used. Also, frequency information can be derived from the data to select the data encoding scheme. However, these codes may not work well for data with a more uniform distribution. Run length encoding is good if there are long periods of repeated data, such as zeros, but is of little use when noise causes the data to vary. 
   MP3 uses characteristics of the human ear to eliminate inaudible information, and thus is a lossy compression scheme. It uses Huffman encoding as a coding method, which in addition to serving as an encoding mechanism, allows additional compression in areas of relatively uniform sounds. If the application does not relate to the human ear, then MP3 is not applicable. Even for audio applications such as Voice Over IP (VoIP), the data is already severely limited at the high end of the frequency range, so the human ear effects are already addressed to some degree. Also, stereophonic effects are not applicable because VoIP is monaural. 
   Therefore, there is a need in the art for improved apparatuses and methods for compressing data in communication networks. In particular, there is a need for data compression with reduced dependence on factors such as, state information, knowledge of the data characteristics, characteristics of human users, and stereophonic effects. 
   SUMMARY OF THE INVENTION 
   Exemplary embodiments of the present invention achieve data compression by performing an error correction encoding operation on input data, and then providing compressed data including error correction information that corresponds to the input data and that has been produced by the error correction encoding operation. 
   To address the above-discussed deficiencies of the prior art, it is a primary object of the present invention to provide a data compression method and a related apparatus. According to an advantageous embodiment of the present invention, the method comprises the steps of: 1) receiving input data; and 2) providing compressed data that represents the input data but requires less transmission channel capacity than does the input data, including performing an error correction encoding operation on the input data, the compressed data including error correction information that corresponds to the input data and has been produced by the error correction encoding operation. 
   According to one embodiment of the present invention, the compressed data includes parity bits produced by the error correction encoding operation. 
   According to another embodiment of the present invention, the compressed data includes all parity bits produced by the error correction encoding operation. 
   According to still another embodiment of the present invention, the compressed data includes only parity bits produced by the error correction encoding operation. 
   According to a further embodiment of the present invention, the error correction encoding operation is a BCH encoding operation. 
   According to a still further embodiment of the present invention, the input data includes one of audio data and video data. 
   According to a yet further embodiment of the present invention, the transmission channel includes one of a wired channel, a wireless channel and a fiber optic channel. 
   It is a further object of the present invention to provide a data decompression apparatus and a related method. According to an advantageous embodiment of the present invention, the data compression apparatus comprises: 1) an input for receiving compressed data that represents a desired data word but requires less transmission channel capacity than does the desired data word, the compressed data including error correction information which corresponds to the desired data word and which has been produced by performing an error correction encoding operation on the desired data word; and 2) a determiner coupled to the input for determining the desired data word based on the compressed data. 
   According to one embodiment of the present invention, the determiner includes a look-up table having stored therein a plurality of possible data words which each correspond to the compressed data. 
   According to another embodiment of the present invention, the determiner is for selecting one of the possible data words that is closest to a prediction of the desired data word. 
   According to still another embodiment of the present invention, the determiner is for selecting one of the possible data words that is within a predetermined range of a prediction of the desired data word. 
   According to yet another embodiment of the present invention, the determiner is for taking a prediction of the desired data word to be the desired data word if none of the possible data words is within a predetermined range of the prediction. 
   Before undertaking the DETAILED DESCRIPTION OF THE INVENTION below, it may be advantageous to set forth definitions of certain words and phrases used throughout this patent document: the terms “include” and “comprise,” as well as derivatives thereof, mean inclusion without limitation; the term “or,” is inclusive, meaning and/or; the phrases “associated with” and “associated therewith,” as well as derivatives thereof, may mean to include, be included within, interconnect with, contain, be contained within, connect to or with, couple to or with, be communicable with, cooperate with, interleave, juxtapose, be proximate to, be bound to or with, have, have a property of, or the like; and the term “controller” means any device, system or part thereof that controls at least one operation, such a device may be implemented in hardware, firmware or software, or some combination of at least two of the same. It should be noted that the functionality associated with any particular controller may be centralized or distributed, whether locally or remotely. Definitions for certain words and phrases are provided throughout this patent document, those of ordinary skill in the art should understand that in many, if not most instances, such definitions apply to prior, as well as future uses of such defined words and phrases. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     For a more complete understanding of the present invention and its advantages, reference is now made to the following description taken in conjunction with the accompanying drawings, in which like reference numerals represent like parts: 
       FIG. 1  illustrates a prior art communication system that utilizes data compression; 
       FIG. 2  illustrates in tabular format the characteristics of a conventional error correction code; 
       FIG. 3  illustrates in tabular format a parity-to-data word mapping characteristic of the code of  FIG. 2  that can be utilized for data compression according to exemplary embodiments of the invention; 
       FIG. 4  illustrates exemplary embodiments of a communication system that utilizes data compression according to the invention; 
       FIG. 5  illustrates exemplary embodiments of the sector determiner of  FIG. 4 ; 
       FIG. 6  illustrates exemplary sector determination operations according to the invention; 
       FIG. 7  illustrates further exemplary sector determination operations according to the invention; 
       FIG. 8  illustrates further exemplary sector determination operations according to the invention; and 
       FIG. 9  illustrates in tabular format selected data compression performance characteristics associated with the various error correction codes. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
     FIGS. 1 through 9 , discussed below, and the various embodiments used to describe the principles of the present invention in this patent document are by way of illustration only and should not be construed in any way to limit the scope of the invention. Those skilled in the art will understand that the principles of the present invention may be implemented in any suitably arranged data communication system. 
     FIG. 1  illustrates a conventional example of a data communication system including data compression. At the transmitter  110 , data provided by a communication application  111  is compressed by a compressor  112 , and the resulting compressed data is transmitted to a receiver  130  via a communication channel  120 . At the receiver, a decompressor  131  receives the compressed data and attempts to reconstruct therefrom the original data as provided by the communication application  111 . The reconstructed data is then provided to a communication application  132 . 
   The present invention recognizes that error correcting codes can be used for data compression. 
     FIG. 2  illustrates a conventional example of an error correcting code, namely a Bose, Chaudhuri, and Hocquenghem (BCH) code. The example of  FIG. 2  is commonly referred to as a BCH [7,4] code. It is a BCH code whose code words include 7 total bits, 4 of which are data bits and 3 of which are redundant parity bits. The code word is transmitted over a communication channel to a receiver, and the combination of the data bits and the parity bits of the code word facilitate the receiver&#39;s ability to correct errors that may have occurred in the data bits during transmission of the code word. Also as shown in  FIG. 2 , a BCH code can be generally represented by BCH [n, k], where a code word includes n bits, k of which are data bits, and n−k of which are parity bits. The parity bits of a given code word are determined from the remainder produced when x n−k  times the data bits of that code word are divided by a generator polynomial associated with the BCH code, for example, x 3 +x+1 (1011) for a BCH [7,4] code. 
   Continuing with the exemplary BCH [7,4] code, if only the parity bits of a given code word are transmitted, then 3 bits are transmitted instead of the 4 data bits, thus achieving data compression. Due to the compression, there is not a one-to-one correspondence between the parity value and the data value in  FIG. 2 . Rather, each parity value is associated with two different binary data values, as illustrated in  FIG. 3 . Thus, for example, if a parity value of 3 (011) is received at the receiver, then the decompressor at the receiver needs to determine whether the original binary data value was 1(0001) or 10 (1010). Thus, in the BCH [7,4] code, each parity value is repeated twice in the code space and, if the parity value alone is received, then the corresponding data could be one of two different values. This effectively divides the data into two sectors, and the receiver needs to determine which of these sectors holds the desired data value. 
   More generally, a BCH [C,D] code has 2 D  data words (i.e., sets of data bits), 2 C−D  parity words (i.e., sets of parity bits) and 2 2D−C  sectors (i.e., repetitions of the data words). So the BCH 
   code has 2 4 =16 data words, 2 3 =8 parity words and 2 1 =2 sectors. Similarly, a BCH [15,11] code has 2 11 =2048 data words, 2 4 =16 parity words, and 2 7 =128 sectors. Thus, for the BCH [15,11] code, each parity word corresponds to 128 data words, one in each sector. Therefore, the receiver would need to determine which of the 128 sectors contains the desired data word. 
     FIG. 4  illustrates exemplary embodiments of a data communication system according to the invention. In the example of  FIG. 4 , an error correction encoder  410  at the transmitter functions as a data compressor which receives input data from the communication application  111  (see also  FIG. 1 ), and produces compressed data which represents the input data. In the example of  FIG. 4 , the error correction encoder performs an error correction encoding operation on the input data word. The parity bits resulting from this error correction encoding operation are then provided at  411  as compressed data which is representative of the input data word and which is to be transmitted across the communication channel  120 . At the receiver, a sector determiner  420  receives the parity bits and attempts to determine the sector in which the desired data word resides. The sector determiner  420  thus performs the decompression function of reconstructing the desired data word from the compressed data received from the channel  120 . The desired data word is then provided at  421  for use by the communication application  132  (see also  FIG. 1 ). 
   In the exemplary data communication system of  FIG. 4 , either or both of the transmitter and receiver can be, for example, a fixed-site apparatus (such as a computer or a cellular base station), a portable apparatus (such as an apparatus mounted in a land, sea or airborne vehicle), or a mobile apparatus (for example a laptop computer or a cellular telephone). The communication channel  120  can be, for example, a wired channel, a wireless channel, a fiber optic channel, or any combination thereof. The transmitted data can be, for example, audio data such as voice data or VoIP, video data, or data associated with any application where occasional errors can be tolerated or filtered out. The error detection encoder  410  can be, for example, a BCH encoder, or an encoder that implements any other type of error correcting code that produces redundant parity bits for error correction purposes. 
     FIG. 5  illustrates exemplary embodiments of the sector determiner  420  of  FIG. 4 . In the example of  FIG. 5 , the parity bits received from the channel  120  are used to identify in a look-up table  510  the data words which correspond to the particular set of parity bits that has been received. Each corresponding data word comes from a different sector, so the number of possible data words depends on the number of sectors associated with the error correction code that was used to produce the parity bits. As mentioned above, there are two sectors for a BCH [7,4] code, and there are 128 sectors for a BCH [15,11] code. Logic  520  coupled to look-up table  510  attempts to determine the desired sector, and thus the desired data word. The desired data word is then output at  521  for use by the communication application  132 . 
   In some exemplary embodiments, the logic  520  determines the desired sector based on predictive information that is provided to the logic  520 . In some exemplary embodiments, this predictive information may be obtained by tracking previously selected sectors over time. In other exemplary embodiments, the logic  520  selects the desired data word based on predictive information that tracks previously selected data words over time. In other exemplary embodiments, the logic  520  selects the desired data word based on a predicted data word produced by a filtering operation. In some exemplary embodiments the logic  520  selects the desired data word based on predictive information about the data communication that is known a priori. In some embodiments, the logic  520  selects the desired data word by combining the predictive information with window information that defines a predetermined range of acceptable data values relative to the predictive information. For example, if the predictive information predicts the value of the desired data word, and if the window information specifies a predetermined range of values relative to (e.g., surrounding) the predicted value, then logic  520  can select the value from table  510  that falls within the window range. If more than one value from table  510  falls within the window range, the logic  520  can, for example, select the value that is closest to the predicted value. 
     FIG. 6  illustrates exemplary sector selection operations according to the invention, utilizing predictive information based on tracking of previously selected sectors. At  605 , the current sector value N t  is set equal to the immediately preceding sector value (N t−1 ) that was selected in decompressing the immediately preceding set of received parity bits. At  610 , the currently received parity bits are used together with N t  to produce a first data word, DW 1 . It is then determined at  615  whether N t−1  is greater than N t−2 , where N t−2  is the sector value that was selected in decompressing the second-most recently received set of parity bits. If N t−1  is greater than N t−2  at  615 , then M t  is set to N t +1 at  620 . Otherwise M t  is set to N t −1 at  625 . After M t  is set at  620  or  625 , it is used at  630  together with the currently received parity bits to produce a second data word DW 2 . Thus, if the sector value is trending upwardly at  615 , then the sector value M t  used to produce DW 2  is larger by one than the sector value N t  that was used to produce DW 1 . Conversely, M t  is less than N t  by one if the sector value is not trending upwardly at  615 . Once DW 1  and DW 2  have been determined at  610  and  630 , respectively, it is determined at  635  which of these two data words is closer to the data word DW(t−1) that was ultimately selected during decompression of the immediately preceding set of parity bits. If DW 1  is closer, then DW 1  is selected as the desired data word at  640 . If DW 2  is closer, then DW 2  is selected as the desired data word at  645 . 
   The logic  520  of  FIG. 5  can perform the exemplary operations of  FIG. 6 , using N t  together with the currently received parity bits to address the look-up table  510  and thereby obtain DW 1 , and using M t  together with the currently received parity bits to address the look-up table  510  and thereby obtain DW 2 . 
     FIG. 7  illustrates exemplary operations for selecting a desired data word in response to received parity bits according to the invention. After receiving the parity bits at  705 , one or more possible data words can be identified at  710 . If a single data word has been identified (e.g., randomly selected from the set of possible data words) at  710 , and is within a predetermined window relative to a predicted data word at  715 , then the identified data word is used at  725 . Otherwise, the predicted data word is used at  720 . If a plurality of possible data words are identified at  710 , and if more than one of the identified data words are within the window at  715 , then the identified data word that is closest to the predicted data word is used at  725 . If only one of the plurality of possible data words identified at  710  is within the window at  715 , then that data word is used at  725 . If none of the plurality of possible data words identified at  710  is within the window at  715 , then the predicted data word is used at  720 . 
     FIG. 8  illustrates further exemplary operations for selecting a desired data word in response to received parity bits according to the invention. The operations of  FIG. 8  are similar to those of  FIG. 7 , but the windowing operation of  FIG. 7  is not utilized in  FIG. 8 . After the parity bits are received at  805 , a plurality of possible data words is identified at  810 . The identified data word that is closest to the predicted data word is then selected as the desired data word at  815 . 
   As mentioned above, some exemplary embodiments utilize a filtering operation to produce predicted information for use in selecting the desired data word in response to received parity bits. An example of a conventional alpha-beta filter which can be used for this purpose is as follows:
 
 d   p,i+1   =d   s,i   +v   i 
 
and smoothing given by
 
 d   s,i+1   =d   p,i+1   +α[d   new   −d   p,i+1 ]
 
 v   i+1   =v   i   +β[d   new   −d   p,i+1 ]
 
where d p,i+1  is the predicted data value for sample i+1, d s,i+1  is the smoothed data value for sample i+1, d new  is the new data value, v i+1  and v i  are the data rate of change values at samples i+1 and i respectively, and α and β are the filter constants. This collapses to a simple one pole filter of the form d i =d i−1 +α[d new −d i−1 ] when β is zero.
 
   In some exemplary embodiments, a BCH [7,4] code is used together with predictive information produced by an alpha-beta filter with alpha=0.9 and beta=0 and no windowing. In other exemplary embodiments, a BCH [15,11] code is used with predictive information provided by an alpha-beta filter having alpha=0.9 and beta=0 and no windowing. 
   Other exemplary embodiments utilize a BCH [7,4] code and predictive information provided by an alpha-beta filter where alpha=0.6 and beta=0.25, and with windowing according to any of the following parameters:
         no windowing;   a window width of 4;   a window width of 7.5;   a window width of 8.5; or   a window width of 9.       

   Other exemplary embodiments use a BCH [15,11] code and predictive information provided by an alpha-beta filter having alpha=0.6 and beta=0.25, together with windowing according to either of the following parameters:
         a window width of 200; or   a window width of 1000.       

   In some exemplary embodiments, the predictive information is produced by a filter having a cut-off frequency chosen to match the input data function. 
     FIG. 9  illustrates in tabular format selected characteristics of various error correction codes. Those codes with a negative value in the “bits saved” column do not achieve data compression. The “samples” and “bits” columns indicate how the various codes can be applied to an exemplary communication session involving data with an 8-bit sample size. For example, the BCH [31, 26] code fits the data fairly well because it accommodates three 8-bit data samples with two bits left over. The amount of compression provided by BCH [31, 26] is relatively high, as indicated by the large number of sectors (2 21 ), but this does lead to a large degree of uncertainty about the actual data value. 
   It will be evident to workers in the art that the embodiments of  FIGS. 3-9  can be readily implemented, for example, by suitably modifying software, hardware, or a combination of software and hardware in conventional data communication transmitters and receivers. 
   Although the present invention has been described with an exemplary embodiment, various changes and modifications may be suggested to one skilled in the art. It is intended that the present invention encompass such changes and modifications as fall within the scope of the appended claims.