Systems and methods for decoding forward error correcting codes

BACKGROUND INFORMATION

0001In packet networks, non-real-time data signals and real-time data signals, such as voice, video, and audio, can be encoded with error correcting codes prior to being packetized and transmitted across the packet network. This can be accomplished through various forward error correction (FEC) schemes. In general, FEC schemes introduce sufficient redundancy in the signal (or message) to be sent so that packets lost or corrupted during transmission can be reconstructed at the receiver. In other words, the purpose of FEC is to improve the capacity of a channel by adding some carefully designed redundant information to the data being transmitted through the channel. The encoding of signals with error correcting codes can protect a transmitted signal against packet losses, packet erasures, bit errors, and also packet delay in the case of real-time signals.

0002At the receiving end of a transmission that has been encoded with an error correcting code and packetized, the arriving packets are typically first placed in a packet-receiving buffer (or 'playout' buffer). According to a 'pipelined' process, the buffered packets are read out (or 'played-out') of the buffer periodically, the bits or frames are extracted from the packet payloads, the bits or frames are decoded using a decoding method that corresponds to the encoding method that has been applied at the transmitting end prior to packetization, and the decoded digital signal is played-out to the receiving entity (a device, process, or person). Packets that arrive at the packet-receiving buffer when the buffer is already full, or, in the case of real-time signals, after a scheduled (or required) playout time has passed, may be discarded. The discarding of late packets causes the loss (or erasure) of the bits or frames contained in the late packets. The discarding of late packets is in addition to any packet loss, packet erasure, or packet corruption that may have already taken place in the packet network.

0003Bits or frames that are erased or lost may be indicated to the decoder, and the decoding method applied to the received bits or frames may correct erased, lost or corrupted bits or frames. However, even with FEC schemes in place, errors still occur in the decoding process. Therefore, systems and methods are still needed for improving the performance (i.e., the bit error rate) of forward error correcting codes.

0004<nplcit id="ncit0001" npl-type="s"><text>Joiner et al., "Sequential Decoding of Reed-Solomon Codes in an Incremental Redundancy System", Proceedings on the IEEE Annual Military Telecommunications Conference, November 2007</text></nplcit> relates to a method of soft-decision decoding of Reed-Solomon codes. This method is an iterative procedure where erasures only decoding is performed followed by a sequential procedure to determine the maximum likelihood estimate of the transmitted word. Results are given that compare this new method of soft decision decoding to more traditional soft decision decoding algorithms. The use of the sequential decoding method in an incremental redundancy system is discussed.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING(S)

0005Reference will be made herein to the accompanying drawings, which are not necessarily drawn to scale, and wherein: <ul id="ul0001" list-style="none"><li><figref idref="f0001">Figure 1</figref> illustrates a conventional technique for receiving packets and decoding information bits or frames that have been encoded with an error correcting code;</li><li><figref idref="f0002">Figure 2</figref> shows a high level block diagram of an exemplary decoding technique implemented in accordance with one embodiment of the present invention; and</li><li><figref idref="f0003">Figure 3</figref> shows a more detailed example of a decoding technique that can be implemented according to one embodiment of the present invention by using information contained in late packet arrivals in decoding an error correcting code.</li></ul>

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

0006The preferred embodiments according to the present invention now will be described hereinafter with reference to the accompanying drawings, in which some, but not all possible embodiments of the invention(s) are shown. Indeed, the invention(s) may be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided so that this disclosure will satisfy applicable legal requirements. Like numbers refer to like elements throughout.

0007In one embodiment implemented according to the present invention, a method and a system are disclosed for improving the performance of decoders of forward error correcting codes by using the information contained in late packet arrivals to update (or recompute) the state of the decoder. A well-known error correcting code that is referenced below by way of example is the convolutional error correcting code, although the method and system of embodiments according to the present invention can be employed with other error correcting codes as well. As described below, the method and system are generally applicable to decoders that maintain state information in decoding successive bits or information frames. One well-known decoder that maintains state information operates in accordance with the Viterbi algorithm, although the method and system may also be employed with other types of decoders. The method and system generally improve the performance (i.e., the bit error rate) of the decoder since the recomputed state is exactly the state that the decoder would have had if the information contained in the late packet had originally arrived on time and been decoded in a usual manner. In effect, the updating of the decoder state following a late packet arrival terminates the propagation in time of the effect of the late packet erasure on the state of the decoder.

0008The method and system described in more detail below are presented in terms of a decoder that is preceded by a packet-receiving buffer. Note that the size (in packets) of the packet-receiving buffer may be zero, one, or more. Hence, the described method and system also include the case where there is no receive buffer, in which case arriving bits or frames are immediately extracted from arriving packets and decoded in a pipelined process.

0009The usual technique for receiving packets and decoding information bits/frames that have been encoded with an error correcting code is shown in <figref idref="f0001">Figure 1</figref>. In <figref idref="f0001">Figure 1</figref>, the packets arriving from the network are typically first placed in a packet receive buffer 12. Packets that arrive at a full buffer are discarded (e.g., erased, blocked). Packets, e.g., late packets, that arrive after a scheduled or required playout time are also discarded. The packets being held in the receive buffer <b>12</b> are played-out according to a packet-playout schedule. As is commonly known, playout scheduling can be used at the receiving end of a transmission in order to continuously play out the transmitted signal (contained in the individual received packets) despite variations in network delays. With the existence of delay variations (also known as delay jitter), the playout scheme at the receiving end can greatly affect the tradeoff between loss and latency in packet networks. Thus, a packet receive buffer <b>12</b> is typically employed to absorb the delay jitter before outputting the decoded signal, x(k), where k denotes the discrete time epoch. Any packet arriving later than its scheduled (or required) playout deadline has to be discarded, resulting in loss. And while scheduling a later deadline increases the possibility of playing out more packets and lower loss rate, it does so at the cost of higher buffering delay.

0010When a packet is played out, the information bits/frames f(k) are extracted from the packet and the information bits/frames are decoded by the error correcting decoder <b>14</b> one bit or frame at a time (in some implementations, bits or frames may be decoded in groups). The output of the decoder <b>14</b> is the decoded output signal x(k). Note that if the packet buffer <b>12</b> is empty (starved) when a packet should be played out, or if one or more packets are missing from the time sequence of the packets in the packet buffer, such as a result of arriving late, then bit/frame erasure indicators will usually be inserted into the received bit/frame stream to maintain a continuous bit/frame stream of information into the decoder.

0011More formally, if f(k) is the k<i>th</i> information bit or frame (i.e., the bit or frame that arrives at the discrete time epoch k), then the decoded output signal corresponding to the k<i>th</i> time interval is x(k), where x(k) = D(f(k), S(k-1)), D(.) is the error correcting decoding operator, and S(k-1) is the state of the error correcting decoder <b>14</b> after having decoded the previous information frame f(k-1). The state of the decoder <b>14</b> after having decoded f(k) is then S(k). Note that, in the case of a bit, f(k) may correspond to a 1, 0, or an indicated erasure. In the case of a frame, f(k) may correspond to a frame of bits or an indicated frame erasure.

0012As noted above, a conventional technique for receiving and decoding information bits/frames that have been encoded with an error correcting code suffers loss attributable to late arriving packets. In order to at least partially remedy this loss without increasing the buffering delay, <figref idref="f0002">Figure 2</figref> shows a high level block diagram of an exemplary decoding technique implemented in accordance with one embodiment of the present invention. More specifically, <figref idref="f0002">Figure 2</figref> illustrates a decoding technique that uses the information contained in late packet arrivals in decoding an error correcting code. In the conventional decoding technique of <figref idref="f0001">Figure 1</figref>, late packet arrivals are simply discarded (or erased). In the embodiment depicted in <figref idref="f0002">Figure 2</figref>, however, late packet arrivals are passed on to what can be referred to as a late packet arrival processing unit <b>26</b>. As will be described in detail below, the information contained in late packet arrivals can be used by the late packet arrival processing unit <b>26</b> to update (or recompute) the state of the error correcting decoder <b>24</b>. The late packet arrival processing unit <b>26</b> and its constituent elements as shown by way of example in <figref idref="f0003">Figure 3</figref> may be comprised of software that is stored in memory within the decoder and retrieved and executed by a processing element, such as a controller, microprocessor or other computing device, of the decoder. Alternatively, the late arrival processing unit 26 and its constituent elements may be comprised of hardware or firmware or any combination of software, hardware and firmware, as will be recognized by those skilled in the art.

0013<figref idref="f0003">Figure 3</figref> shows a more detailed example of a decoding technique that can be implemented according to one embodiment of the present invention by using the information contained in late packet arrivals in decoding a forward error correcting code. In <figref idref="f0003">Figure 3</figref>, packets arriving from a network are first placed in a packet receive buffer <b>22</b> unless they arrive past their scheduled (or required) playout time or unless the packet receive buffer is full. If the packet receive buffer <b>22</b> is full, the arriving packet may be simply discarded or blocked. As in <figref idref="f0001">Figure 1</figref>, the packets in the packet receive buffer <b>22</b> are played-out according to a packet-playout schedule. When a packet is played out, the information bits/frames are extracted from the packet and the information bits/frames are decoded by the error correcting decoder <b>24</b> one bit/frame at a time (or, in some implementations, in groups of bits/frames). The output of the decoder <b>24</b> is the decoded output signal x(k), where x(k) = D(f(k), S(k-1)). If the packet buffer <b>22</b> is empty (starved) when a packet should be played out, then erasure bits/frames can be inserted to maintain a continuous information stream into the decoder <b>24</b>.

0014Unlike the conventional technique depicted in <figref idref="f0001">Figure 1</figref>, the embodiment shown in <figref idref="f0003">Figure 3</figref> includes a late packet arrival processing unit <b>26</b> which assists in implementing a set of additional steps that may be carried out when a late packet arrives. In the conventional technique of <figref idref="f0001">Figure 1</figref>, a late packet is simply discarded (or erased). In the exemplary embodiment of <figref idref="f0003">Figure 3</figref>, however, the bit/frame information in late packet arrivals can be used to: (i) update an auxiliary bit/frame buffer <b>28</b> as indicated at step <b>29</b>; (ii) update an auxiliary decoder state buffer <b>30</b> as indicated at step <b>31</b>; and (iii) update the error correcting decoder state S(k) as indicated at step <b>33</b>. The bit/frame buffer <b>28</b> holds the latest M-1 input bits/frames, including bit/frame erasure indications that may have been inserted when the packet buffer was starved. In other words, the bit/frame buffer <b>28</b> holds the recent history of bits/frames that have been presented to the error correcting decoder <b>24</b>. As bits/frames are presented to the error correcting decoder <b>24</b>, the bits/frames are also copied into the bit/frame buffer <b>28</b>. The state of the bit/frame buffer <b>28</b> at time k can therefore be defined to be the set of bits/frames A(k) = {f(k), f(k-1), ..., f(k-M)}. The decoder state buffer <b>30</b> holds the latest M states of the error correcting decoder <b>24</b>. In other words, the decoder state buffer <b>30</b> holds the recent history of decoder states. As the state of the decoder <b>24</b> changes in decoding successive bits/frames, each new state of the decoder is also copied into the decoder state buffer <b>30</b>. The state of the decoder state buffer <b>30</b> at time k may therefore be defined to be the set of decoder states B(k) = (S(k), S(k-1), ..., S(k-M-1)).

0015When a late packet arrives, the late packet arrival processing unit <b>26</b> generally first determines the time epochs to which the bits/frames in the late packet correspond during the step <b>29</b> of updating the bit/frame buffer. This may be determined from sequence number and/or timestamp information contained in the header field(s) of the late packet. The set g(.) of bits/frames in the late packet is then given by {g(e), g(e+1), ..., g(e+n-1)}, wherein <i>n</i> is the number of bits/frames in the late packet and <i>e</i> is the time epoch of the first bit/frame in the late packet. The bit/frame buffer A(k) (<b>28</b>) is then updated by replacing those bit(s)/frame(s) in A(k) that correspond to the same time epochs as does the late packet. For example, f(e) may be replaced by g(e) if f(e) is in A(k), f(e+1) may be replaced by g(e+1) if f(e+1) is in A(k), ..., and f(e+n-1) may be replaced by g(e+n-1) if f(e+n-1) is in A(k). As noted above, erasure bits/frames may be initially inserted in the bit/frame buffer A(k) in lieu of a late arriving packet to maintain a continuous information stream to the decoder <b>24</b>. As such, if f(i) is in A(k) and g(i) is contained in a late packet, then f(i) was an indicated bit/frame erasure that primarily served as a placeholder for an erasure. Following updating to include the late arriving packet, the contents of the bit/frame buffer <b>28</b> may be defined as A*(k) = {f*(k), f*(k-1), ..., f*(k-M)}.

0016Having updated the bit/frame buffer <b>28</b>, the decoder state buffer <b>30</b> is then updated by recursively recomputing (updating) the past decoder states taking into account the updated bit/frame buffer A*(k). In this regard, let f(j) be the earliest bit/frame in A(k) that was replaced by g(j) in updating the bit/frame buffer <b>28.</b> Then the decoder state buffer <b>30</b> is updated recursively by recomputing S(j) as S*(j) = D(f*(j), S(j-1)), recomputing S(j+1) as S*(j+1) = D(f*(j+1), S*(j)), and so on, until S(k) is recomputed as S*(k) = D(f*(k), S*(k-1)). Finally, the present state of the decoder <b>24</b> itself is updated by setting it to the recomputed (updated) state S*(k). The performance of the decoder 24, at least in terms of bit error rate, may therefore be improved since the recomputed state of the decoder is the same state that the decoder would have had if the information contained in the late packet had originally arrived on time and been decoded in a typical manner. By updating the state of the decoder upon receiving the late packet, the method and system of the preferred embodiments according to the present invention may terminate the propagation in time of the deleterious effect of the late packet erasure on the state of the decoder.

0017As has already been noted above, embodiments implemented according to the present invention that use the information contained in late packet arrivals can be used with error correcting decoders that maintain state information in decoding successive bits/frames. One example is the Viterbi decoder for convolutional error correcting codes. Embodiments of the present invention, however, are in no way limited in their applicability to any particular error correcting coding scheme or decoding scheme, so long as the decoder maintains state information in decoding successive bits/frames. There exist many other examples of such decoders to which the method and system of embodiments of the present invention may be applied, such as decoders for convolutional turbo codes. The embodiments and examples described herein may also be applied to any new error correcting decoders that may be invented in the future that maintain state information in decoding successive bits/frames.