Wireless and voice-over-internet protocol (VoIP) communications are subject to frequent loss of packets as a result of adverse connection conditions. Such lost packets result in clicks and pops or other artifacts being present in the output voice signal at the receiving end of the connection. This degrades the perceived speech quality at the receiving end and may render the speech unrecognizable if the packet loss rate is sufficiently high.
Broadly speaking, two approaches are taken to combat the problem of lost packets. The first approach is the use of transmitter-based recovery techniques. Such techniques include retransmission of lost packets, interleaving the contents of several packets to disperse the effect of packet loss, and addition of error correction coding bits to the transmitted packets such that lost packets can be reconstructed at the receiver. In order to limit the increased bandwidth requirements and delays inherent in these techniques, they are often employed such that packet loss can be recovered if the packet loss rate is low, but not all packet loss can be recovered if the packet loss rate is high. Additionally, some transmitters may not have the capacity to implement transmitter-based recovery techniques.
The second approach taken to combating the problem of lost packets is the use of receiver-based concealment techniques. Such techniques are generally used in addition to transmitter-based recovery techniques to conceal any remaining losses left after the transmitter-based recovery techniques have been employed. Additionally, they may be used in isolation if the transmitter is incapable of implementing transmitter-based recovery techniques. Low complexity receiver-based concealment techniques such as filling in a lost packet with silence, noise, or a repetition of the previous packet are used, but result in a poor quality output voice signal. Regeneration based schemes such as model-based recovery (in which speech on either side of the lost packet is modeled to generate speech for the lost packet) produce a very high quality output voice signal but are highly complex, consume high levels of power and are expensive to implement. In practical situations interpolation-based techniques are preferred. These techniques generate a replacement packet by interpolating parameters from the packets on one or both sides of the lost packet. These techniques are relatively simple to implement and produce an output voice signal of reasonably high quality.
Pitch based waveform substitution is a preferred interpolation-based packet loss recovery technique. The pitch period of the voiced packets on one or both sides of the lost packet is estimated. A waveform of the estimated pitch period is then repeated and used as a substitute for the lost packet. This technique is effective because voice signals appear to be composed of a repeating segment when viewed over short time intervals. Consequently, the pitch period of the lost voice packet will normally be substantially the same as the pitch period of the voice packets on either side of the lost packet.
Many methods are used to estimate the pitch period of a voice signal. Generally speaking, these methods include use of a normalized cross-correlation (NCC) method. Such a method can be expressed mathematically as:
                              N          ⁢                                          ⁢          C          ⁢                                          ⁢                                    C              t                        ⁡                          (              τ              )                                      =                                            ∑                              n                =                                                      -                    N                                    /                  2                                                                              (                                      N                    /                    2                                    )                                -                1                                      ⁢                                          x                ⁡                                  [                                      t                    +                    n                                    ]                                            ⁢                              x                ⁡                                  [                                      t                    +                    n                    -                    τ                                    ]                                                                                                        ∑                                  n                  =                                                            -                      N                                        /                    2                                                                                        (                                          N                      /                      2                                        )                                    -                  1                                            ⁢                                                                    x                    2                                    ⁡                                      [                                          t                      +                      n                                        ]                                                  ⁢                                                      ∑                                          n                      =                                                                        -                          N                                                /                        2                                                                                                            (                                                  N                          /                          2                                                )                                            -                      1                                                        ⁢                                                            x                      2                                        ⁡                                          [                                              t                        +                        n                        -                        τ                                            ]                                                                                                                              (                  equation          ⁢                                          ⁢          1                )            where x is the amplitude of the voice signal and t is time. The equation represents a correlation between two segments of the voice signal which are separated by a time τ. Each of the two segments is split up into N samples. The nth sample of the first segment is correlated against the respective nth sample of the other segment.
This equation essentially takes a first segment of a signal (marked A on FIG. 1) and correlates it with each of a number of further segments of the signal (for ease of illustration only three, marked B, C and D, are shown on FIG. 1). Each of these further segments lags the first segment along the time axis by a lag value (τ1 for segment B, ρ2 for segment C). The calculation is carried out over a range of lag values within which the pitch period of the voice signal is expected to be found. The term on the bottom of the fraction in equation 1 is a normalizing factor. The lag value τNCC that maximizes the NCC function represents the time interval between the segment A and the segment with which it is most highly correlated (segment D on FIG. 1). This lag value τNCC is taken to be the pitch period of the signal.
Calculation of the normalized cross-correlation accounts for over 90% of the algorithmic complexity in typical pitch based waveform substitution techniques. Although the complexity level of the calculation is low, it is significant for low-power platforms such as Bluetooth. In order to correctly determine the pitch period of a voice signal, a wide pre-defined pitch period range (range of lag values) is usually used, for example from 2 ms (for a person with a high voice) to 20 ms (for a person with a low voice). For most pitch determination algorithms, the wider the pitch period range used, the higher the computational complexity.
One way to reduce the computational complexity is to reduce the number of calculations that the algorithm computes. U.S. patent application Ser. No. 10/394,118 proposes to reduce the number of calculations by dynamically adapting the time interval between successive segments that are correlated with the first segment. (In the illustration of FIG. 1, the time interval between successive segments B and C is τ2-τ1.) If the correlation decreases, then the time interval to the next segment to be correlated is increased. Conversely, if the correlation increases, then the time interval to the next segment is decreased. This method evaluates the correlation over the same range of pitch periods (for example from 2 ms-20 ms) as methods in which the time interval between successive segments is constant, but advantageously this method is less computationally complex because it carries out fewer calculations by skipping over segments that it considers unlikely to lag the first segment by the pitch period. However, this method is sensitive to local pitch errors. For example, if an error leads to the correlation decreasing just before the pitch period lag value is computed, then the time interval to the next segment may be increased resulting in the algorithm skipping over the pitch period lag value. The accuracy of the estimated pitch period may suffer as a result. Additionally, this method may have difficulty handling voice signals with rapid local pitch variations.
A further problem with pitch based waveform substitution techniques is that they are prone to pitch doubling and pitch halving errors. Pitch halving occurs when the pitch period is determined to be about double its actual length. This may occur, for example with the method described by U.S. Ser. No. 10/394,118 if the peak best correlated with the peak in the first segment were to be skipped over.
Pitch doubling occurs when the pitch period is determined to be about half its actual length. This may happen in the following situation. Voice signals often have two similar peaks per pitch period that are highly correlated with each other. For example, on FIG. 1 the peaks marked 1 and 2 are highly correlated. These could be mistaken for being the same feature present in consecutive pitch periods and hence the time interval between them could be computed to be the estimated pitch period of the signal. Pitch doubling is particularly problematic for packet loss concealment applications because the replacement signal used for the lost packet will be at a non-integer multiple of the pitch period of the lost packet.
Techniques for reducing pitch doubling and pitch halving errors have been proposed, for example frequency domain and statistical techniques and post processing techniques. However these techniques incur additional computational complexity and cost.
There is thus a need for an improved method of estimating the pitch period of a signal that reduces the computational complexity associated with the estimation, and that additionally reduces susceptibility to pitch doubling and pitch halving errors without incurring extra algorithmic complexity.