Dial tone detector based on monobit periodograms - Embedded.com

Dial tone detector based on monobit periodograms

This “Product How-To” article focuses how to use a certain product in an embedded system and is written by a company representative.

An important part in both standard telecommunications and VoIP gateways, dialtone detection is challenging due to the variation of dial tone parameters (e.g. frequency, duration, cadence, etc.) depending on the geographic area. In literature one can find many algorithms that facilitate tone detection for different purposes but not many concentrate on implementation constraints.

The algorithm proposed here is designed to detect dial tones as specified in ITU recommendation E.180 and various tones used in national networks (according to ITU-T recommendation E.180) [5].

The design difficulty comes from elaborating an algorithm that is computationally efficient has a small memory footprint and that reliably indicates the presence of a specific dial tone (single or multiple frequencies) in an input stream.

The amount of persistent data is very important in a multi-channel environment considering that the latencies to memory and caches increase considerably leading to higher power consumption.

Having in mind that the frequencies to be detected are in a tolerance interval of about 25Hz the design has to distinguish between frequencies 25Hz apart. The algorithm has also to cope with impairments that come from real life environments (white noise, attenuation, impulse noise).

The algorithm proposed here will detect some relevant dial tone frequencies and will not give a complete indication of dial tone (the user has to set cadence conditions, duration conditions and other validity checks depending on geographic area).

The frequencies (expressed in Hz) taken into consideration are part of the Set S, below.

S = {2125, 1800, 1400, 900, 770, 760, 740, 733, 720, 600, 500, 480, 467, 460, 450, 445, 440, 433, 425, 424, 420, 400, 380, 376, 375,367,360,350,340,330,300}

Due to the fact that a dial tone is composed from maximum 3 frequencies, the design has to be able to detect 3 frequencies at a time. The signal level for the tones that will be detected are considered greater than -27dbm0 (considering ITU E.180 recommendation and the maximum admissible line attenuation on EIA5).

The sampling rate considered here is 8 KHz and the input signal is split in 5ms frames (40 samples). The output of the model is the indication of presence of the specific frequencies.

Other detection schemes
One frequent used approach for tone detection is based on FFT or Goertzel algorithm. The algorithm designer has to design Goertzel filters for each frequency.

The usual way is to select a block size N for the Goertzel algorithm so that the target frequency is an integer multiple of Sampling_Rate/N . The resolution of detection for a block size of 160 samples is around 8000Hz/160 = 50Hz. [3]

The problem with such algorithms is that multiple detections in a row have to be considered until giving the decision of presence of the target frequencies. Also the algorithm is very susceptible to impulse noise, dependent on the position of the noise in the input block.

In the special case of dial tones the block size should be adapted for each frequency so that the Goertzel algorithm is efficient, this complicates further the implementation.[3]

Other tone detection schemes rely on PLLs (phase lock loops). The detection schemes based on PLL are very robust and reliable. The problem with such schemes in dial tone detection arises from the fact that the frequencies to be detected are spread in a large amount of the spectrum making the number of the PLL needed very large. The algorithms based on PLL are computationally expensive making them impractical for dial tone detectors.

Algorithm description
The approach we used is based on periodogram computation for the frequency of interest. Furthermore, we used the so called monobit Fourier kernel and one bit signal quantization in order to reduce the arithmetic complexity [1].

It was shown that the performance of monobit Fourier analysis is acceptable if the number of input signals (tones) and their amplitude difference are low. In order to achieve these requirements we filtered the interest frequencies first.

As show in Figure 1 below , the block scheme of the detection algorithm (considering a single frequency). The signal is split up into overlapping segments (20 ms analysis window with 15 ms overlapping). The implicit rectangular window is used since the signal is peak filtered and one bit quantized, thus we don't need any further side lobe reduction.

Figure 1. Block diagram of the algorithm for a single frequency

Such nonlinear systems are difficult to evaluate analytically, so we proved the concept using Monte Carlo simulation. We varied the frequency and phase of the tone (the amplitude is not important due to the one bit quantization of the input signal), adding various types of noise.

Two monobit periodograms are shown in Figure 2 below for single tone plus white noise with two different signal to noise ratios: SNR = 6dB, and SNR = -1dB. Frequency was swept 150Hz around the reference frequency, and phase from 0 to 2*pi in steps of pi/100.

Figure 2. Monobit Periodogram for single tone plus white noise a) SNR = 6dB, b) SNR = -1dB

Red and blue curves represent the envelope of the simulation, the maximum and minimum values obtained for a given input frequency, and the green curve is the mean across all periodograms.

The diagram suggests the threshold and uncertainty (the distance between the red and the blue curve for a fixed threshold), for a given frequency tolerance at a given SNR.

It can be seen that, within the fundamental limitation of the uncertainty principle, the method is robust for positive SNR's while going below 0dB implies rapid degradation.

The monobit complex exponentials references are computed once at initialization according to the user specified frequency. This method was chosen as a tradeoff between code size and real-time speed requirements.

Since only the sign of the real and imaginary part of the reference and not the entire value is required, the reference can be extracted from evaluating the quadrant of the argument, arg= 2pi nf /f S :

Each reference sample needs only one bit so the reference can be stored on 10 32-bit values.

First the algorithm calculates the energy of the input signal and returns silence if the energy is below -50dBm0. The signal is passed through a peak filter and the energy is calculated again.

The two energies are compared with the thresholds T1 and T2. T1 is -27dBm0 and T2 is considered experimentally so that the detection delay is not too large. The next step is to calculate the correlation of the filtered input signal with a reference signal constructed at initialization time.

The absolute value of the correlation result is compared with a threshold T considered experimentally so that the detection time is not too large and there are no false detections.

Filtering the input signal has also the role of avoiding false detections due to modulated frequencies used in some geographic areas.

An important optimization applicable to this method regards the monobit complex correlator that can be implemented efficiently on the StarCore DSP architecture, having in mind the following equivalence between monobit product and XOR operations:

This equivalence implies that the product of 40 samples can be done in one instruction. The summation can be obtained easily by computing the difference between the number of “one” bits and the number of “zero” bits within the product. We implemented the bit counting algorithm using a lookup table approach.

Below is a code snippet on how the correlation could be performed using StarCore specific intrinsic X_xor which performs 40 bit logic XOR operation in one cycle:

Counting bits in a word implies shifting and masking operations. For example using a 256 entries LUT containing the number of “one” bits in 8 bit numbers, the number of ones in a 32 bit register d is:

LUT[d&255] + LUT[(d>>24)&255] + LUT[(d>>16)&255] + LUT[(d>>8)&255]

The implementation takes advantage of the extraction instruction of the StarCore architecture which extracts a bit-field at a specified offset from a data register and places in a destination register right aligned and zero-extended, the core being able to execute two extraction instruction in a single cycle [6].

Results and discussions
Tone detection algorithms are usually evaluated based on the following metrics:

1) Start front clipping = number of frames clipped until the first frame with positive detection is reported

2) Hangover = number of frames from the moment the tone ends until the frequency is not reported any more

3) Middle clipping = percentage from the overall duration of the tone where the frequency was not detected

4) False detects = frames where the tone is not present but are reported as detected

The algorithm proposed here was tested in noise environments (white noise at -40dbm0 , impulse noise and attenuation) and performed good. The following values where obtained:

* average start front clipping = 20ms
* average hangover = 5ms
* average middle clipping = 0%
* False detects = 0.001% (environments with impulse noise and white noise at -40dbm0 ); 0% (in noise free environments)

Conclusions
The memory footprint for this algorithm is 16 times smaller than the one needed for a normal correlation-based algorithm and computing the correlation is performed in an efficient way. When implemented on a Freescale MSC8101 DSP, the computational load was about 800 cycles for each target frequency (considering a 5ms frame) and the memory footprint is around 4Kb for code and data together.

Krutsch Robert Cristian is a Software Engineer in Packet Telephony Application Group at Freescale Semiconductor. He received a BSc degree specializing in automatics and computer science from the Polytechnic University of Timisoara; a BSc degree from the Automation Institute at the University of Bremen and PhD in automatic control from Polytechnic University of Bucharest.

Pralea Radu is a Software Engineer in Packet Telephony Application Group at Freescale Semiconductor. He graduated with BSc and PhD degrees in wireless communications and DSP from the Polytechnic University of Bucharest.

References
[1] “Efficient Multitone Detection,” Vladimir L. Vassilevsky, IEEE Xplorer, March 2007
[2] “ITU-T E.180/Q.35 Technical characteristics of tones for the telephone service,” 03/1998
[3] “The Goertzel Algorithm” , Kevin Banks, Embeded System Design
[4] “Universal tone detection based on the Goertzel Algorithm,” Schwingshackl D , IEEE Circuits and Systems, August 2006
[5] International Telecommunications Union ITU Dial tone specifications.[6] Code Warrior StarCore Reference manual

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.