Abstract:
A method and system use capacity-approaching rateless code to communicate multimedia data even with very short codewords, such as 64 bits or less, via erasure and noise channels. The method provides a way to design the edge degree distribution of rateless codes for any arbitrary channel. Based on an equivalent metric of decoding behavior in any channels, the degree distribution of a rateless code such as Luby-transform codes and raptor codes is optimized based on in-process status of decoding. A regularized least-squares optimization is used to avoid erroneous decoding. Multiple feedbacks can further improve the performance.

Description:
FIELD OF THE INVENTION 
     This invention relates generally to digital communications, and more particularly to communicating multimedia using rateless codes and feedback. 
     BACKGROUND OF THE INVENTION 
     Realizing reliable communications is an important problem in packet-based communication networks using packet erasure channels, where packets are either received and decoded, or lost. This channel model is related to a binary erasure channel (BEC). If a feedback channel is available, the channel capacity can be achieved with an automatic repeat-request (ARQ). The receiver feeds back an acknowledgment for each decoded packet, and unacknowledged packets are retransmitted. Because ARQ uses frequent feedback, ARQ is difficult to implement in many practical networks, and increases overhead. 
     Rateless coding can achieve reliable communications on erasure channels without frequent feedback. Practical rateless codes include fountain, raptor, tornado, and Luby-transformation (LT) codes. Rateless codes can approach the channel capacity in erasure channels if the code length is sufficiently long. The rateless codes generate a potentially infinite number of encoded symbols from input symbols to approach the channel capacity. Transmission of the encoded symbols is terminated when all symbols have been correctly decoded. 
       FIG. 1  shows conventional rateless encoding  100  at a transmitter. Generally, the encoding uses high-rate outer block encoding. Random parity of the data is transmitted until the encoded parity is successfully decoded. 
     A sequence of symbols (codeword)  101  is encoded by an outer block error correction encoder  102 , such as low-density parity-check (LDPC) codes. The encoded bits  103 , referred to as input symbols, are fed to, e.g., the LT encoder  110 . The encoder is shown as a Tanner graph. 
     The input symbols are combined by an exclusive-or (XOR) operation to produce the encoded output symbols. Each output symbol is the XOR&#39;ed parity bit by combining the random input symbols. The number of edges  105  from the input symbols used in the XOR is referred to as a degree  106  of the output symbol, and all input symbols contained in an output symbol are called neighbors of the output symbol. The edges are selected at random according to the degree distribution. This process can be iterated to transmit  107  until the input symbols are decoded from the received output symbols. 
       FIG. 2  shows a conventional decoder  200  for a receiver of rateless codes that uses belief propagation (BP). A general decoding process of rateless codes includes determining the likelihood of reception, propagating belief information via edges, and correcting errors by outer error correction decoding. The BP decoding  201  is simple for erasure channels if every symbol is error-free and can be decoded. 
     All degree-1 output symbols  203  are identified and moved to a storage referred to as a ripple  204 . The ripple has an associated size. Degree-1 output symbols are symbols that have a single neighbor input symbol. Symbols in the ripple are processed by the XOR operation of the ripple node to the neighbors. After a symbol has been processed  205 , the symbol is removed from the ripple and considered decoded. The processing of symbols in the ripple potentially reduces some of the buffered symbols to degree one, in which case they are moved to the ripple. This is called a symbol released. 
     The iterative decoding process  201  can be summarized as follows. Identify all degree-one symbols and add the symbols to the ripple. Process a symbol from the ripple, and then remove the symbol. After processing, add new degree-1 symbols to the ripple. This iteration continues while there still is a symbol in the ripple. Decoding succeeds when all input symbols are decoded. If the ripple size becomes zero before processing all input symbols, decoding has failed. 
     To design rateless codes, the ripple size parameter is an important factor in erasure channels. The performance depends significantly on how this parameter evolves during decoding, and thus conventional methods for rateless coding have mostly focused on the size of the ripple by determining a suitable ripple evolution and a degree distribution, which achieves that desired ripple size evolution. 
     One ideal ripple evolutions uses only one symbol in the ripple over all decoding processes. This ideal ripple provides the so-called ideal soliton distribution (ISD) for edge degree distribution. Although ISD is optimal for infinite code lengths, ISD is suboptimal in practice with finite code lengths because decoding failure frequently occurs. One of modifications is to consider a margin of ripple size to avoid decoding failure. This idea provides a robust soliton distribution (RSD). 
     Another modification is based on a random walk model, which yields a square-root ripple evolution. Although rateless codes were originally developed for erasure channels, rateless codes can also be used for additive white Gaussian noise (AWGN) channels. 
     Channel feedback facilitates the coding, i.e., encoding and decoding. Real-time oblivious erasure correction can utilize the feedback to signal the number of input symbols that have been decoded. With this information, the transmitter selects a fixed degree for future encoded symbols, which maximizes the probability of decoding new input symbols. 
     In conventional doped fountain coding, the receiver feeds back information on undecoded symbols. By sending undecoded symbols with higher priority, that method improves the coding efficiency. 
     However, the decoding reliability and coding efficiency are suboptimal for a short codeword with rateless coding. Those design techniques are not compatible in practical feedback systems to obtain some feedback from the decoder in noisy channel environments. 
     SUMMARY OF THE INVENTION 
     The embodiments of the invention provide a method for reliable multimedia communications with feedback, wherein the communications are from a transmitter to a receiver. The feedback provides information to the transmitter while data are transmitted, received and decoded. For example, the feedback includes in-process status of a rateless decoder at the receiver. 
     The method uses capacity-approaching rateless codes, even with very short codewords, e.g. 64 bits or less, while the conventional capacity approaching codes based on low-density parity-check (LDPC) require more than 10,000 bits. The method offers a way to design relates codes in any arbitrary channel including additive white Gaussian noise (AWGN) channels, and a binary symmetric channel (BSC), as well as a binary erasure channel (BEC). 
     The embodiments are a generalized design method stemming from the erasure channel. Based on an equivalent metric of decoding behavior in any channels, the degree distribution of the rateless code can be optimized dynamically. 
     A regularized least-squares optimization is used to avoid erroneous decoding. One embodiment of the invention enables multiple feedback opportunities to further improve the performance. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a schematic of conventional encoding with rateless codes; 
         FIG. 2  is a schematic of conventional decoding with rateless codes; 
         FIG. 3  is a schematic of reconfigurable rateless coding incorporating informative feedback according to embodiments of the invention; 
         FIG. 4  is a graph of ripple size to evolve in a decoding process with feedback information according to embodiments of the invention; 
         FIG. 5  is a block diagram of designing degree distribution to achieve the ripple evolution by using a least-squares optimization according to embodiments of the invention; 
         FIG. 6  is graph of the impact of feedback timing according to embodiments of the invention; 
         FIG. 7  is a graph ripple evolutions via least-squares optimization for single and double feedback opportunities according to embodiments of the invention; and 
         FIG. 8  is a block diagram of a method for designing the degree distribution based on ripple evolution in noisy channels according to embodiments of the invention. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The embodiments of the invention provide a method for reliable multimedia communications with feedback, wherein the data are communicated from a transmitter to a receiver. The receiver feeds back information regarding the decoding process to the transmitter, so that the transmitter can optimize a degree distribution used by an encoder. The degree distribution is time-varying. The feedback is generated as the decoding progresses. The feedback includes in-process status of the rateless decoder at the receiver. 
     The rateless codes use feedback when it is available. For simplicity, we focus on a single feedback. However, the concept of our rateless coding incorporating feedback can be generalized to any amount of feedback for erasure or noisy channel environments. 
       FIG. 3  shows a communication network  300 , which uses reconfigurable rateless coding with feedback  308  according to embodiments of the invention. 
     A transmitter  301  communicates with a receiver  302  via a channel  303 , which can be subject to erasures and/or noise. Multimedia data  304  are transmitted using a rateless encoder  305 , which uses a degree distribution  306 . For example, the encoder  305  is an LT encoder. 
     The receiver  302  decodes the channel output signals using a belief propagation (BP) rateless decoder  307 . The invention provides a way to optimize  309  the reliability and efficiency of the rateless codes by using the feedback  308 , which contains in-process status of the rateless BP decoder  307 . 
     Using the feedback, the transmitter optimizes  309  the degree distribution  306  for the rateless codes to improve the decoding efficiency. 
     With the erasure channel  303 , the feedback  308  signals the transmitter which input symbols have been decoded at an optimal feedback timing. Hence, the transmitter knows exactly the symbols that have been decoded. 
     This enables the rateless LT encoder  305  to adapt the degree distribution  306  dynamically. The encoder  305  excludes all decoded symbols from future encoding to reduce overhead, and modifies the degree distribution to ensure that the ripple size at the decoder does rapidly decrease to zero without a decoding failure. 
     The determining of the ripple evolutions includes both the ISD and RSD. An improved ripple evolution is based on a random walk model, which provides a square-root ripple evolution. 
     As shown in  FIG. 4 , when there are feedback opportunities, the square-root ripple evolution is modified to a piece-wise square-root evolution. This figure shows a determining ripple size evolution  401  over a decoding process. A message (codeword) length is k bits, and a number of decoded bits in process is L. 
     One design principle is to have a large enough margin for avoiding decoding failures, yet small enough to avoid redundancy to decode all bits. Hence, the initial ripple size  402  is large enough, e.g. 10, while the last ripple  403  is zero. The ripple curve is defined as a piece-wise square-root function  404  over the decoding process as:
 
 R ( L )= c   1 √{square root over ( L −(1 −f   1 ) k )} for  L &gt;(1 −f   1 ) k  
 
 R ( L )= c   i √{square root over ( L −(1 −f   i ) k )} for (1 −f   i-1 ) k&gt;L &gt;(1 −f   i ) k,  
 
where R(L) is the ripple size, f i  is a fraction of the decoding process at the i-th feedback timing, and c i  is an appropriate constant. At the feedback timing  405 , where f 1 k symbols are decoded, the ripple size is near zero, i.e., 1.
 
       FIG. 5  shows our method  500  for designing the degree distribution to achieve the determining ripple evolution for any code lengths. Two different degree distributions are determined, for a single feedback, one before the feedback, and the other after the feedback. 
     The determining ripple size evolution R(L)  501  is mapped  502  to Q(L), which denotes an expected number of releases at the decoding step. The mapping is expressed as 
               Q   ⁡     (   L   )       =           L   ⁡     (       R   ⁡     (   L   )       -     R   ⁡     (     L   +   1     )       +   1     )         L   -     (       R   ⁡     (     L   +   1     )       -   1     )         ⁢           ⁢   for   ⁢           ⁢   k     &gt;   L   ≥   0           
where Q(k)=R(k).
 
     The expected number of releases Q(L) is expressed by a theoretical release probability q(d, L k)  503  of the degree d 
               q   ⁡     (     d   ,   L     )       =         d   ⁡     (     d   -   1     )       ⁢   L   ⁢       ∏     j   =   0       d   -   3       ⁢           ⁢     (     k   -     (     L   +   1     )     -   j     )             ∏     j   =   0       d   -   1       ⁢           ⁢     (     k   -   j     )                   as                 Q   ⁡     (   L   )       =       ∑     d   =   1       k   -   L   +   1       ⁢     n   ⁢           ⁢     Ω   ⁡     (   d   )       ⁢     q   ⁡     (     d   ,   L   ,   k     )             ,         
where n is the number of received symbols and Ω(d) is the degree distribution. That is, Ω(d) represents a probability that an output symbol has degree d, (d=1, 2, 3, . . . ). For the case of single feedback, the method solves  505  the optimal degree distributions, i.e., Ω 1 (d) before feedback, and Ω 2 (d) after feedback. Because the above equation is numerically unstable to solve, the invention uses a least-squares optimization to obtain near optimal degree distributions.
 
       FIG. 6  shows the efficiency in the sense of overhead of the LT coding with single feedback as a function of the feedback timing f 1 . The optimal feedback timing is about f 1 =0.75 for piece-wise square-root ripple evolutions. The curves, from top to bottom are for k=128, 256, 512, 1024, and 2048. The graph shows that shorter codes need more overheads, and the method using feedback can significantly reduces the overhead. 
     The design method, which uses the least-squares optimization and piece-wise square-root ripple evolution, can be extended to the case of multiple intermediate feedback opportunities. The number of feedback opportunities can be a network parameter. The least-squares solution achieves optimal determining ripple evolutions. 
       FIG. 7  shows an example of achieved near optimal ripple evolutions to approach the determining piece-wise square-root ripple for the similar cases of single and double feedback cases. 
     The conventional RSD has a considerably large overhead, while our LT coding with feedback can significantly improve the efficiency of the coding. The invention also decreases the encoding/decoding complexity because the average degree is decreased. 
     The rateless raptor coding structure, which uses an outer error-correction code, can further reduce the coding (encoding/decoding) complexity. 
     xxThe invention can be applied to the raptor coding by adding a constraint of the average degree into the least-squares optimization. The average degree is expressed as 
               d   _     =       ∑     i   =   1       m   +   1       ⁢         n   i     n     ⁢       ∑     d   =   1         k     i   -   1     ′     -     k   i   ′         ⁢     d   ⁢           ⁢       Ω   i     ⁡     (   d   )                             n   =       ∑     i   =   1       m   +   1       ⁢     n   i         ,         
where m is the number of feedback opportunities, k′ i =(1−f i )k with f i  is the i-th feedback timing, n i  is the received symbol at the i-th feedback. This equation is added to the least squares optimization with a relatively large constraint weighting.
 
     The ripple size is near zero at the feedback timing for piece-wise square-root evolutions. If it becomes exactly zero, then the decoding has failed. To avoid such a decoding failure, a constraint is added to the least-squares optimization so that the sufficient amount of releases is achieved prior to the feedback. And, the feedback is performed when the actual ripple size becomes 1 to avoid decoding failure. 
     For raptor coding of k=128 bits with single feedback, the average degree is reduced to be half of the comparable LT code, and hence, the complexity is half. 
       FIG. 8  shows an embodiment of the invention for degree optimization in noisy channels, instead of erasure channels based on ripple analysis. For noisy channels, the BP decoding becomes more complicated because the channel output is not perfectly reliable. While the conventional BP decoding uses a batch scheduling, in which a belief message is simultaneously propagated, it is known that sequential scheduling such as random propagation performs better. 
     The feedback information for noisy channels includes belief messages. The belief propagation messages indicate the reliability of the decoding of each symbol. Using this information, the transmitter optimizes the degree distribution and priority weighting according to the reliability. 
     The embodiment first analyzes the entropy of the belief messages  802 , for such a modified scheduling  801 . Based on the entropy, the invention provides a way of equivalently interpreting the noisy channels into the erasure channels by determining  803  the information-theoretic mutual information  804 , which defines an equivalent ripple. The mutual information is then used to optimize the degree distribution using the least-squares optimization  805 . 
     For noisy channels, the optimal degree distribution depends on the error probability or the noise variance. To deal with the impact of the noise variance, the embodiment of the invention uses a modified random walk model  806  to optimize the determining ripple. Because the belief message may contain erroneous information, the least-squares optimization is also modified to improve the performance by adding a regulation term to avoid trapping  807  during erroneous belief propagation  807 . With updated degree distribution, the optimization process from the entropy analysis  802  to the degree design  805  iterates  808  until convergence. 
     A conventional random walk model assumes increment or decrement at random for one symbol decoding process. For noisy channels, the processed symbol is not always one symbol. The embodiment uses a high-order polynomial to model the transient movement. For most cases, the first-order polynomial has a sufficiently good performance. With this modified random walk model, the determining ripple evolution is expressed by a bended square-root function. 
     For noisy channels, the BP decoding can be trapped by an even number of erroneous belief messages in neighbors. Such a trapping can be avoided by maximizing the probability of an even number of error bits compared to the probability of an odd number of error bits. The regularized least-squares optimization maximizes this probability subject to squared error of the ripple equation. 
     Another embodiment of the invention, the outer block error-correcting code is at a relatively high rate, i.e., greater than 0.95, and includes nonlinear block coding linear block coding so that layered multimedia data have unequal error protection for layered multimedia data by using nonlinear block error correction codes, rather than linear block coding. A random edge selection is modified by considering priority information, which is obtained from the feedback. 
     While the degree distribution can be designed off-line, an informative feedback can reconfigure the degree distribution and priority weighting dynamically in real-time-line. 
     The embodiments provide a way to reconfigure those parameters by Monte-Carlo simulation of an expected performance before transmitting. After Monte-Carlo simulations, the optimal performing degree distribution is selected. 
     Although the invention has been described by way of examples of preferred embodiments, it is to be understood that various other adaptations and modifications can be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.