Error detection and error concealment for encoded speech data

TECHNICAL FIELD OF THE INVENTION

This invention relates generally to encoded data such as encoded speech data and more particularly to data that includes convolutionally encoded data.

BACKGROUND OF THE INVENTION

In digital cellular environments, acoustic background noise and channel bit errors (both bursty and random) may severely degrade the performance of speech coders such as the current European GSM full rate standard. In this standard, every 20 milliseconds a total of 456 bits are sent, of which 260 of these bits represent the speech signal and 196 bits are added for protection against channel bit errors. In digital speech compression, it is relatively common to have a number of classes of bits with different perceptual importance. Further, for some bits (or parameters) it has been beneficial to have an indication of the likelihood of whether or not these certain key parameters are corrupt. In the GSM standard, there is a Class 1a which consists of 50 of the most sensitive bits. For these most sensitive bits there are added three parity bits. There is a second sensitive Class 1b of 132 bits and of these 132 bits there are added four tail bits used to reset a convolutional coder. There is also a Class 2 which is considered the least sensitive bits (78 bits) and these are sent without any additional bits for protection against channel bit errors. The very sensitive bits with the parity bits and the sensitive bits along with the tail bits sum up to 189 bits. Convolution coding at the rate of 1/2 convolutional coding is done to generate a forward error correction coding. The total number of bits with the error correction coding is 378 bits, each 20 millisecond frame. To this is added the 78 least sensitive bits which are not error protected, to provide every 20 milliseconds (a frame) a total of 456 bits. At the receiver, the foregoing 378 bits undergo a Viterbi decoding. This is an efficient decoding algorithm for convolution coding, well known to those skilled in the art. This decoding step produces 189 bits for the very sensitive bits and sensitive bits. From the very sensitive 50 bits, the 3-bit parity is calculated and compared to the decoded parity bits. If the two sets of parity bits are not equal, a Bad Frame Indicator (BFI) is generated. When this BFI is generated, the source decoder declares a bad frame and substitutes the information from the previous frame.

Referring to Fig. 1 there is illustrated this prior art system. The speech is encoded in the source encoder 12. The parity bits are added by the parity encoder 14. The convolutional encoder 16 generates the 378 bits to which is added the least sensitive 78 bits without any error protection encoding. The signals are sent via a channel 18 to a receiver. At convolution decoder 20 of the receiver the decoder 20 decodes using the Viterbi algorithm and the parity decoder 22 determines if the three bit parity matches the parity computed from the decoded very sensitive 50 bits and if there is no failure or mismatch, the 260 bits (= 50 very sensitive bits + 132 sensitive bits + 78 least sensitive bits) are then provided out of the source decoder 26. If there is a parity error (parity bits calculated from the 50 bits do not match the decoded 3-bit parity) this is detected at detector 24 and the BFI signal is sent to the Source Decoder 26 and all of the data in that frame is discarded.

In a Viterbi algorithm decoder, as used to decode convolutionally encoded information, reliability information is developed for various path metrics computed within the Viterbi algorithm. The metrics in the Viterbi algorithm estimate the likelihood of incorrect reception of various speech coder parameters and this is passed on to the speech or source decoder.    These confidence measures from the Viterbi decoding have been proposed to be used generally for rejecting bad parameters or accepting good parameters in frames.

It is highly desirable to provide an enhanced GSM full rate system with an improved method and system for decoding, to provide acceptable speech quality under bad channel conditions.

SUMMARY OF THE INVENTION

An aspect of the present invention is set forth in claim 1.

In accordance with one embodiment of the present invention, an improved method of error detection and error concealment for Viterbi decoding for convolutionally encoded data is provided wherein there is provided parity bits for the very sensitive bits and encoding said very sensitive bits and parity bits with convolutional coding. At the Viterbi decoder, decoding said very sensitive bits and comparing the computed parity bits with the decoded parity bits to determine if a bad frame indicator occurs and further decoding the convolutionally encoded information using a Viterbi algorithm and determining confidence levels of separate parameter sets. The decision to discard the received bits is jointly dependent upon the bad frame indicator and said confidence levels of said parameter sets.

DESCRIPTION OF THE DRAWINGS

These and other features of the invention that will be apparent to those skilled in the art from the following detailed description of exemplary embodiments of the invention, taken together with the accompanying drawings which:- <ul id="ul0001" list-style="none"><li>Fig. 1 is a block diagram of a GSM full rate speech coder system in accordance with the prior art;</li><li>Fig. 2 is a block diagram of a coder system according to one embodiment of the present invention;</li><li>Fig. 3 is a flow chart for determining confidence levels;</li><li>Fig. 4 is an example of the trellis used in a four state Viterbi decoder;</li><li>Fig. 5 illustrates computing the parameter confidence levels from the best path wherein the top path contains metrics used for the noisy channel and the bottom path contains the metrics in the clean channel; and</li><li>Fig. 6 illustrates a flow chart for the modified parity failure decoder of Fig. 2.</li></ul>

DESCRIPTION OF PREFERRED EMBODIMENT OF THE PRESENT INVENTION

Referring to Fig. 2 there is illustrated a coder system in accordance with one embodiment of the present invention. The input signals at source 40 are encoded by source encoder 22. The encoded source signals may be, for example, the 260 bits every 20 milliseconds (a frame) in GSM full rate standard system. Some of the encoded source signals at 42 are parity encoded at parity encoder 24 to produce the encoded source and parity signals at 44. This may represent, for example, the very sensitive 50 bits plus 3 parity bits (or perhaps the alternative of 6 parity bits or some other parity level), and 132 sensitive bits with 4 tail bits. The tail bits are used to reset the convolutional coder at the end of each frame. The encoded source and parity bits are sent to the convolutional encoder 26 which operates, say, as in the previous example at rate 1/2, to provide 378 bits made from the 50 very sensitive bits and 3 parity bits, and the 132 sensitive bits and the four tail bits. The remaining 78 bits are sent directly to the channel 28 along with the convolutionally encoded 378 bits. The signals are then transmitted over the channel 28 whether that be a wire or in the preferred case for use with cellular phone wireless channel. The received convolutionally encoded source and parity signals at 48 are sent to a modified convolutional decoder 30. The convolutional decoder 30 includes a Viterbi decoder. The Viterbi algorithm is well understood by those skilled in the art. Fig. 4 illustrates the processing used by the Viterbi algorithm for a frame with an incoming stream of data consisting of two bit words. In the Viterbi algorithm (which is a trellis search technique) a series of metrics are computed. Applicants' algorithm uses the metrics from the best path to compute a confidence level that a particular parameter has been corrupted as follows:<maths id="math0001" num=""><math display="block"><mrow><msub><mrow><mtext mathvariant="italic">C</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub><mtext> = </mtext><mfrac><mrow><msub><mrow><mover accent="true"><mrow><mtext mathvariant="italic">M</mtext></mrow><mo>^</mo></mover></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext mathvariant="italic">-</mtext><mover accent="true"><mrow><mtext mathvariant="italic">M</mtext></mrow><mo>^</mo></mover><msub><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">k-a</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></msub></mrow><mrow><msub><mrow><mtext mathvariant="italic">M</mtext></mrow><mrow><mtext mathvariant="italic">k</mtext></mrow></msub><mtext mathvariant="italic">-M</mtext><msub><mrow><mtext>​</mtext></mrow><mrow><msub><mrow><mtext mathvariant="italic">k-B</mtext></mrow><mrow><mtext mathvariant="italic">j</mtext></mrow></msub></mrow></msub></mrow></mfrac></mrow></math><img file="EP0805572A2_D0001.tif" /></maths> where <maths id="math0002" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">M</mtext></mrow><mo>^</mo></mover></mrow></math><img file="EP0805572A2_D0002.tif" /></maths>_<i>k</i> is the metric of the best path at time k in the noisy channel case and <i>M</i>_<i>k</i> is a metric of the best path at the time k in the case of a channel with no errors (the latter is a constant and could be pre-computed). The parameter of interest, B, is comprised of B_j bits. When the confidence is one or near one, it indicates that the parameter is very likely correct and when the confidence is small (for example zero), it indicates that the parameter is very likely incorrect. For each parameter, the decoded parameter value may be retained only if its confidence level is larger than a pre-selected threshold; the parameter value is discarded if the confidence level is smaller than said threshold. The thresholds that correspond to different parameters are chosen to optimize the speech quality for the particular channel of interest. The Viterbi algorithm essentially comprises a maximum likelihood process that includes, as a key computation, computation survivor metrics; mainly, some paths survive and some do not during the processing of the Viterbi algorithm. By discarding some paths, the Viterbi algorithm remains computationally efficient. At the same time, of course, by discarding some paths, from time to time a potential for error arises. If a decision to discard must be made at a time when only the equivocal information is available as to a likelihood that one path of many is a particular better choice than the others, a decision to discard made at that time may lead to erroneous results ultimately. If the reader is interested in additional information regarding Viterbi decoding of convolutional codes the reader may wish to consider the article entitled, "The Viterbi Algorithm", by G. David Forney, Jr. as appears in the March 1973 issue of proceedings of the IEEE.

In Fig. 4 there is illustrated an example of the trellis used in the 4 state Viterbi decoder. The best path is indicated by a heavy line. As stated previously, the computing of the confidence level at decoder 30 is done by the equation discussed above. Referring to Fig. 5 the top path contains the metrics <maths id="math0003" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">M</mtext></mrow><mo>^</mo></mover></mrow></math><img file="EP0805572A2_D0003.tif" /></maths> for the noisy channel and the bottom path are the metrics M for the clean channel. The bottom path metric values may be pre-computed. The operation for computing confidence levels would follow the flow chart of Fig. 3 where in step 70 the metrics would be computed for the noisy channel case as represented at the top half of Fig. 5 and the clean channel metrics represented by the bottom half of Fig. 5 would be retrieved from the pre-computed and pre-stored constant metrics in step 72. For example, the metric at point <maths id="math0004" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">M</mtext></mrow><mo>^</mo></mover></mrow></math><img file="EP0805572A2_D0004.tif" /></maths>_<i>k</i> is subtracted by metric at point <maths id="math0005" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="italic">M</mtext></mrow><mo>^</mo></mover></mrow></math><img file="EP0805572A2_D0005.tif" /></maths>_<i>k</i> -4 (4 bits away) divided by the metrics from the same points (<i>M</i>_<i>k</i> and <i>M</i>_<i>k</i>_-4) for the clean channel. From that the confidence level is determined using the equation discussed previously. This confidence level is computed at step 74 for each of the parameters. This confidence level would be used to determine a bad parameter indicator (BPI). This represents a confidence level for a subset of the 182 bits (50 very sensitive bits +132 sensitive bits), in the above example. The subsets are the parameters. The parameters may be the LPC parameters of the frame, pitch, or gain, for example. The Viterbi decoded source and parity signals would be applied to the parity decoder 32 and the confidence levels computed would be applied to the modified parity failure detector 36. The decoded parity and computed parity signals would be applied from the parity decoder 32 at output 54. The detector 36 would compare the decoded parity with the computed parity and if not equal generate the BFI signal. The detector 36 would also generate BPI signals from the computed confidence levels. The data provided from the decoder 34 would be controlled by the BFI and the BPI. If the BFI indicates the frame is in error, the BPI can be used to detect which parameters are most likely uncorrupted and permit these to be provided out of the decoder 34 rather than discarding all parameters from the frame. If the BFI indicates there is no error, the BPI can be used to detect and discard those parameters likely to be corrupted. The confidence level thresholds used in deciding BPI are different for BFI = True and BFI = False cases. The thresholds are set higher for BFI = True than for BFI = False.

Referring to the flow chart of Fig. 6, in accordance with one embodiment, the first step is determining if the decoded parity is equal to the computed parity. If yes, in accordance with one embodiment the convolutionally decoded source signals would then be provided out of source decoder 34 because no BFI signal is generated.

In accordance with another embodiment of the present invention, a BPI confidence measurement for each of the individual parameters would then be compared to a corresponding confidence threshold level (Threshold TH2) and if that confidence level exceeds the threshold, then that parameter would be provided out of the decoder. If the confidence level was below the threshold, then a BPI flag would be set, which would then be coupled to the decoder 26 to prevent that parameter set from being provided out of the decoder even though parity check was good (no BFI) and in its place the previous frame value for the parameter would be provided. In the case of the decoded parity not being equal to the computed parity, unlike the standard GSM full rate case, a threshold test would undergo for each parameter to determine if the confidence level for that parameter was above or below a second threshold (TH1). The threshold TH1 would be a higher threshold than threshold TH2. For each parameter it would be determined whether the confidence level for each parameter was above the threshold level reached even though BFI flag was set. If the confidence level was high enough a good parameter indicator is generated (GPI) and for that parameter it would override the BFI flag signal. During the presence of that good parameter indicator (GPI) the corresponding parameter is provided out of the decoder 34. The threshold TH1 or TH2 can be different for different parameters. As noted above, the threshold values are chosen by optimizing the speech quality for a given noisy channel.

Although embodiments of the invention and advantages thereof have been described in detail, it should be understood that various changes, substitutions and alterations can be made herein without departing from the scope of the invention.