Patent Publication Number: US-6215821-B1

Title: Communication system using an intersource coding technique

Description:
FIELD OF THE INVENTION 
     this invention relates to communication systems, networks, and more particularly to transmission techniques for networked information sources. 
     BACKGROUND OF THE INVENTION 
     Heretofore, data compression methods have been designed to compress the bit rate of signals transmitted from a single source. This includes such methods as employed in adaptive delta modulation for voice compression, Joint Photographic Experts Group (JPEG) compression for still images, Motion Picture Expert Group (MPEG) compression for real-time video, and entropy coding for data files. These compression methods are known as source coding in communication or information theory, and they are most effective in situations where there is a single-point to single-point transmission over a physical link, such as a telephone line. These compression methods reduce the amount of information that needs to be transmitted from a source, and they often provide large communication bandwidth reductions in single-point to single-point transmissions. 
     When, however, a multitude of information sources are transmitted over a single shared physical link as a multitude of data streams, such present day source coding methods alone do not provide the largest possible bandwidth reduction. In such multi-source to multi-source (hereinafter “multi-stream”) communications, the signal from each data source is separately compressed using a particular source coding method optimized for that source. The compressed signals are then summed or multiplexed onto a single physical link to be transmitted over a network. In the most popular network known as synchronous time multiplexed (“STM” hereafter) network, each data stream is assigned a certain time slot in a data frame that is predefined by the network. As a result, in an STM network having a plurality of sources communicating over a single physical link, the multiple data streams do not overlap in time, and there is no interaction among the data streams as they are transmitted over the physical link. 
     The disadvantage of present day STM multistream communications over a single link, however, is that when the different data streams are partially correlated (i.e. when some sources store the same data bit at the same time), redundant data is carried on the communication link. As a result, when the sources are at least partially correlated, present day system can waste a significant amount of transmission bandwidth by communicating redundant data over the link at the same time. 
     Some present day communication networks reduce the transmission bandwidth of multistream communications over a single physical link by combining the multiple streams into an aggregate signal. Such systems are designed with the assumption that the data streams carried on the communication link are statistically independent of one another. As a result, when the data streams are combined into an aggregate signal transmitted over the single communication link, the bit rate of the aggregate signal is often less than the sum of the individual data stream bit rates. This is known as statistical multiplexing gain (SMG). Typically, SMG is obtained by transmitting information of a momentarily ON source (i.e. a source transmitting during that moment) during the time slot of a momentarily OFF source (a source not transmitting during that moment). 
     In a present day network designed to take advantage of SMG, such as an asynchronous transfer mode (ATM) network, data buffers are designed as shared buffers with a certain SMG expected. When, however, the data streams are partially correlated (i.e. the sources exhibit similar ON/OFF behavior), the buffers may not have the capacity to handle all the information from the multiple sources. As a result, the buffer overflow forces the network to discard information, thus substantially reducing the network&#39;s ability to realize any SMG. Consequently, for ATM networks providing multisource, partially correlated transmission over a single link, there are additional bandwidth problems associated with buffer overflow. 
     SUMMARY OF THE INVENTION 
     Accordingly, the present invention is directed to a method and apparatus for achieving maximum bandwidth reduction, with or without buffer overflow problems, for both correlated and uncorrelated transmissions from a plurality of data sources communicating over a single physical link. To attain this, the present invention provides an intersource encoder having a multisource (“multi-stream”) coding scheme that substantially reduces the transmission bandwidth of a plurality of content-correlated sources communicating in the form of an aggregate signal over a single physical link. 
     In one embodiment of the invention, an intersource encoder is used to reduce the aggregate bit rate of the multi-stream traffic on a single physical link. The intersource encoder provides data compression for both completely correlated and partially correlated sources. For completely correlated sources, wherein all sources transmit the same information at a given time, only a single copy is transmitted over the physical link. The redundant transmissions of the same data packet are avoided by performing a caching-equivalent step at the lowest physical OSI layer. For partially correlated sources, wherein some of the sources share the same data bit at a given time, the intersource encoder removes the bits on which the sources agree, and leaves intact the bits on which the sources do not agree. The term “sources” herein refers to the end users and any intermediary node in the network between the end users. 
     In another embodiment of the invention, a high-speed digital shift register is used as a binary storage device for the information bits contained in the data streams. This enables the application of all the lossless video and picture compression techniques of the prior art in the present invention. These and other features of the invention are described in more detail in the following detailed description of the embodiments of the invention when taken with the drawings. The scope of the invention, however, is limited only by the claims appended hereto. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram showing the data transmission and receiver paths of one embodiment of the invention in a compressed multi-stream to multi-stream (multi-source) communication network using a single, shared physical link. 
     FIG. 2 is a diagrammatic view of the transmission path of the multi-stream transmit buffer shown in the embodiment of FIG.  1 . 
     FIG. 3 is a diagrammatic view of the transmission path of the intersource encoder shown in the embodiment of FIG.  1 . 
     FIG. 4 is a diagrammatic view of the intersource decoder path for communication system shown in FIG.  1 . 
     FIG. 5 is a diagrammatic view of the receiver path of the receive buffer for communications on the system shown in FIG.  1 . 
     FIG. 6 is a block diagram showing another embodiment of the transmission path of the communication system according to the present invention. 
     FIG. 7 is a block diagram showing the receiver path for communications on the system shown in FIG.  6 . 
     FIG. 8 shows two of many possible constructions of the run-length encoder shown in FIG.  3 . 
    
    
     DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTION 
     Referring now to FIG. 1 there is shown a communications network employing one embodiment of the intersource data compression technique of the present invention, hereinafter referred to as network  10 . Network  10  has a plurality of correlated data sources  11  electrically coupled to transmit buffer  12  and receive buffer  16 . Transmit buffer  12  is electrically coupled to intersource coding block or encoder  13  which, in turn is electrically coupled to transmission driver  14 . Transmission driver  14  is electrically coupled to shared physical link  15 . Shared physical link  15  is also electrically coupled to receiver driver  18 . Receiver driver  18  is electrically coupled to intersource decoder  17  which, in turn is electrically coupled to receiver buffer  16 . As stated above, the term “sources” herein refers to the end users and any intermediary node in the network between the end users. Also, although “sinks” are not mentioned herein, it is understood that a source ends with a sink. 
     A more detailed view of transmit buffer  12  of network  10  is shown in FIG.  2 . As shown, transmit buffer  12  has a set of bit registers  121  through  12 N wherein N is the number of sources sharing link  15 . As a result, buffer  12  has N registers, wherein each register provides storage for a given set of information (e.g. a binary picture) from each source  11 . The bits of these binary pictures are passed from buffer  12  to intersource encoder  13  for the reduction of redundant intersource information. That is, intersource encoder  13  substantially reduces the redundant information between the binary pictures from each source so that the aggregate signal (not shown), made by combining all the source information, is transmitted through driver  14  on physical link  15 . 
     A more detailed view of intersource encoder  13  of embodiment  10  is shown in FIG.  3 . As shown, intersource encoder has a run length encoder  31  coupled to register  12 l through  12 N of buffer  12  and to registers  13 l through  13 M, wherein M (M ≦N) is the number of bits in each binary picture after run length coding. The output of registers  13 l through  13 M are coupled to transmission driver  14  which, in turn, is coupled to physical link  15  which carries the aggregate signal (not shown). For each bit slice, M ≦N, transmission bandwidth has been changed with no information loss. 
     The receiver path of the aggregate signal is similar to the transmit path discussed above. As shown in FIG. I receiver driver  18  receives the aggregate signal (not shown) from physical link  15 , and sends that signal to intersource decoder  17  which separates the aggregate signal into its respective data streams  11  through receive buffer  16 . A detailed view of the receiver path of network  10  is shown in FIGS. 4 and 5. 
     As shown in FIG. 4, intersource decoder  17  has a run-length decoder  41  coupled between receiver register  17 l through  17 M and  16 l through  16 N, wherein M is the number of compressed bits in a binary picture as described above, and N is the number of data streams  11 . Run length decoder  41  separates the individual data streams from the received aggregate signal and places them in the registers  16 l through  16 N of buffer  16  for transfer to respective data streams  11 . A detailed view of the binary bits in register  16 l through  16 N of receive buffer  16  is shown in FIG. 5 
     In another embodiment, conventional single-stream compression methods can be used on multi-stream traffic. For example, assuming network  10  provides a conventional ATM variable bit rate (VBR) transmission from N partially correlated sources  11 , each transmitting a sequence of binary pictures denoted by {P 1  }, {P 2 },. . . {P N  }, at any given time, network  10  transmits an aggregate compressed signal over link  15 . First, the binary pictures or signals from each source  11  are temporarily stored in transmit buffer  12 , wherein they are added to achieve a statistical multiplexing gain. Then, before being transmitted over link  15 , the aggregate signal is sent to intersource coding block  13  or any other lossless compressor, wherein the signal is compressed. Since most advanced compression schemes in the prior art are designed for video, use of the term “picture” herein is intended to refer to any bit-slice, as shown in FIG.  8 . 
     To compress the signal, intersource encoder  13  performs run-length coding on the aggregate of the pictures from sources  11  to form a superpicture. Depending on whether sources  11  are completely or only partially correlated, intersource encoder  13  will perform different steps to form the superpicture  21 . When sources  11  are completely correlated, intersource encoder  13  strips-off the intersource redundancies and transmits only a single copy of the information. When, however, sources  11  are partially correlated, intersource encoder  13  compresses strings of 1&#39;s and 0&#39;s through vector run-length coding techniques. That is, intersource encoder vector codes any strings of 1&#39;s and 0&#39;s that run the length of a position between the pictures of different sources. The strings of 1&#39;s and 0&#39;s that run along a line within a picture, however, are not so vector coded. Thus, the intersource encoder provides intersource compression as opposed to intrasource or frame to frame compression. This substantially reduces the bandwidth requirements on a network wherein a plurality of sources communicate over a single physical link. 
     In one embodiment of encoder  13 , digital shift registers can be used as binary storage devices for storing information bits within the pictures. To provide the intersource compression, a particular bit from each source is read-out of the registers, either in parallel or sequentially, to perform the vector run-length coding described above. FIG. 8 illustrates both a serial and a parallel implementation of such run length encoding. As shown, for serial run-length coding of the pictures generated by partially correlated sources  11 , the first bit from each picture is vector run-length coded to generate output  1 . Similarly, the second bit from each picture is vector run-length coded to generate output  2 , and so forth up to the last or M-th bit. 
     In the parallel implementation of the vector run-length coding shown in FIG.  8 . The N bits of the picture from each source is passed into a predetermined shift register to form the N-th row therein. Each row of bits is then compared, in parallel, to a set of digital words contained in a look-up table to quickly determine the substantially exact match therein. The address (having fewer bits than the row of bits) for the match is then sent over the physical link, resulting in a predetermined bandwidth savings. In addition, the process can be repeated several times until the information can not be compressed any further. The parallel implementation, however, is best suited for systems wherein the number of correlated sources is relatively small (e.g. N=16). 
     In general, vector run-length coding involves the generation of run-length sequences that indicate the number of bits required to communicate the information contained in a long sequence of bits. For example, a bit stream of 110000101000111 (15 bits) results in a run-length sequence of 2,4,1,1,1,3,3. This sequence requires a total of 1+2+1+1+1+2log 2  3 =9.17 bits, which results in a compression ratio of 15/9.17 =1.64. As a result, vector run-length coding such a sequence of bits results in a bandwidth savings of approximately 39%. Although, there is a possibility of the rare case of alternating 1&#39;s and 0&#39;s (e.g. 10101010101010), which results in a zero compression ratio under vector run-length coding, it rarely occurs. 
     It is emphasized that although run-length coding is used here to demonstrate intersource compression in the present embodiment, there are other coding schemes that may provide even more efficient compression than vector run-length coding. For example, a system under the present invention can use Huffman coding or any other lossless entropy coding techniques to achieve such intersource compression. The design philosophy of the present inventive system, however, is the same for each system. That is, to substantially reduce intersource redundancies for a plurality of correlated or partially correlated sources communicating over a single physical link. 
     Alternate embodiments of the transmission path and the receiver path of a network providing such intersource data compression is shown in FIGS. 6 and 7, respectively. As shown in FIG. 6, transmit buffer  61  has a set of registers for temporarily storing the information bits from a plurality of sources. Transmit buffer is coupled to lossless compressor  62  which, in turn, is coupled to forward error correction encoder  63 . Forward error correction encoder  63  is coupled to transmitter  64  which, in turn, is coupled to a single physical link (not shown). As shown in FIG.  7 . the signal receive path includes a receiver  74  coupled to a forward error correction decoder  73  which, in turn, is coupled to a lossless decompressor  72 . Lossless decompressor  72  is coupled to receive buffer  71 . In operation, the embodiment of a network according to the present invention, as illustrated in FIGS. 6 and 7, provides intersource encoding and decoding, to ultimately provide intersource data compression for the reduction of redundancies of the information between the sources communicating on the network. Thus, FIGS. 6 and 7 further illustrate the various embodiments and the scope of the present invention.