Goertzelův algoritmus

Z PanWiki

Tento článek je rozpracován uživatelem: Serych.

Prosím, abyste ho zatím neupravovali a pokud cítíte nutnost s ním v tuto chvíli nějak manipulovat, abyste se se mnou nejprve spojili prostřednictvím mojí diskuse.

Goertzelův algoritmus je metoda, pomocí které se dá digitálním signálním procesorem (DSP) identifikovat výskyt určité frekvence v signálu. Byl publikován Dr. Geraldem Goertzelem v roce 1958. Zatímco rychlá fourierova transformace (FFT) provádí výpočty rovnoměrně v celém frekvenčním pásmu vstupního signálu, Goertzelův algoritmus se věnuje pouze určitým předem definovaným frekvencím. Využití nalézá goertzelův algoritmus například při detekování tónové volby DTMF v telefonii.

Popis algoritmu

Výstupní sekvence $s (n)$ se ze vstupní sekvence $x (n)$ vypočte podle vztahu:

s (n) = x (n) + 2cos(2πω) s (n - 1) - s (n - 2)

kde $s ( - 2) = s ( - 1) = 0$ a $ω$ je hledaný kmitočet normalizovaný s ohledem na vzorkovací frekvenci.

To fakticky představuje IIR filtr druhého řádu s póly v hodnotách $e + 2π i ω$ a $e - 2π i ω$ . Je-li hodnota $2 c o s (ω)$ vypočítána dopředu, představuje algoritmus pouze jediné násobení, jeden součet a jeden rozdíl pro každý vstupní vzorek.

Koeficient vyjadřující sílu signálu vybrané frekvence ve vstupním signálu se pak vypočte podle vzorce:

X (ω) = s (N - 2) 2 + s (N - 1) 2 - 2 c o s (2πω) s (N - 2) s (N - 1)

Při implementaci algoritmu v běžných procesorech mohou být vypočítané hodnoty pro vzorky $s (n - 1)$ a $s (n - 2)$ uchovány v proměnných a vždy po vypočítání další hodnoty pouze posunuty.

Provádění algoritmu může vypadat například následovně:

predvypocet = 2*cos(2*PI*normalizovana_frekvence);
pro kazdy vzorek, x[n],
  s = x[n] + predvypocet*s_predchozi - s_predchozi_2;
  s_predchozi_2 = s_predchozi;
  s_predchozi = s;
konec 
X = s_predchozi_2*s_predchozi_2 + s_predchozi*s_predchozi - predvypocet*s_predchozi_2*s_predchozi;

Practical considerations

The term DTMF or Dual-Tone Multi Frequency is the official name of the tones generated from a telephone keypad. (AT&T used the trademark "Touch-Tone" for its DTMF dialing service.^[1]) The original keypads were mechanical switches triggering RC controlled oscillators.Šablona:Fact The digit detectors were also tuned circuits. The interest in decoding DTMF is high because of the large numbers of phones generating these types of tones.

At present, DTMF detectors are most often implemented as numerical algorithms on either general purpose computers or on fast digital signal processors. The algorithm shown below is an example of such a detector.

However, this algorithm needs an additional post-processing step to completely implement a functional DTMF tone detector. DTMF tone bursts can be as short as 50 milli-seconds or as long as several seconds. The tone burst can have noise or dropouts within it which must be ignored. The Goertzel algorithm produces multiple outputs; a post-processing step needs to smooth these outputs into one output per tone burst.

One additional problem is that the algorithm will sometimes produce spurious outputs because of a window period that is not completely filled with samples. Imagine a DTMF tone burst and then imagine the window superimposed over this tone burst. Obviously, the detector is running at a fixed rate and the tone burst is not guaranteed to arrive aligned with the timing of the detector. So some window intervals on the leading and trailing edges of the tone burst will not be entirely filled with valid tone samples. Worse, RC-based tone generators will often have voltage sag/surge related anomalies at the leading and trailing edges of the tone burst. These also can contribute to spurious outputs.

So it is highly likely that this detector will report false or incorrect results at the leading and trailing edges of the tone burst due to a lack of sufficient valid samples within the window. In addition, the tone detector must be able to tolerate tone dropouts within the tone burst and these can produce additional false reports due to the same windowing effects.

The post-processing system can be implemented as a statistical aggregator which will examine a series of outputs of the algorithm below. There should be a counter for each possible output. These all start out at zero. The detector starts producing outputs and depending on the output, the appropriate counter is incremented. Finally, the detector stops generating outputs for long enough that the tone burst can be considered to be over. The counter with the highest value wins and should be considered to be the DTMF digit signaled by the tone burst.

While it is true that there are eight possible frequencies in a DTMF tone, the algorithm as originally entered on this page was computing a few more frequencies so as to help reject false tones (talkoff). Notice the peak tone counter loop. This checks to see that only two tones are active. If more than this are found then the tone is rejected.

Sample code for a DTMF detector


#define SAMPLING_RATE       8000
#define MAX_BINS            8
#define GOERTZEL_N          92

int         sample_count;
double      q1[ MAX_BINS ];
double      q2[ MAX_BINS ];
double      r[ MAX_BINS ];

/*
 * coef = 2.0 * cos( (2.0 * PI * k) / (float)GOERTZEL_N)) ;
 * Where k = (int) (0.5 + ((float)GOERTZEL_N * target_freq) / SAMPLING_RATE));
 *
 * More simply: coef = 2.0 * cos( (2.0 * PI * target_freq) / SAMPLING_RATE );
 */
double      freqs[ MAX_BINS] = 
{
  697,
  770,
  852,
  941,
  1209,
  1336,
  1477,
  1633
};

double      coefs[ MAX_BINS ] ;


/*----------------------------------------------------------------------------
 *  calc_coeffs
 *----------------------------------------------------------------------------
 * This is where we calculate the correct co-efficients.
 */
void calc_coeffs()
{
  int n;

  for(n = 0; n < MAX_BINS; n++)
  {
    coefs[n] = 2.0 * cos(2.0 * 3.141592654 * freqs[n] / SAMPLING_RATE);
  }
}


/*----------------------------------------------------------------------------
 *  post_testing
 *----------------------------------------------------------------------------
 * This is where we look at the bins and decide if we have a valid signal.
 */
void post_testing()
{
  int         row, col, see_digit;
  int         peak_count, max_index;
  double      maxval, t;
  int         i;
  char *  row_col_ascii_codes[4][4] = {
    {"1", "2", "3", "A"},
    {"4", "5", "6", "B"},
    {"7", "8", "9", "C"},
    {"*", "0", "#", "D"}};


  /* Find the largest in the row group. */
  row = 0;
  maxval = 0.0;
  for ( i=0; i<4; i++ )
  {
    if ( r[i] > maxval )
    {
      maxval = r[i];
      row = i;
    }
  }

  /* Find the largest in the column group. */
  col = 4;
  maxval = 0.0;
  for ( i=4; i<8; i++ )
  {
    if ( r[i] > maxval )
    {
      maxval = r[i];
      col = i;
    }
  }


  /* Check for minimum energy */

  if ( r[row] < 4.0e5 )   /* 2.0e5 ... 1.0e8 no change */
  {
    /* energy not high enough */
  }
  else if ( r[col] < 4.0e5 )
  {
    /* energy not high enough */
  }
  else
  {
    see_digit = TRUE;

    /* Twist check
     * CEPT => twist < 6dB
     * AT&T => forward twist < 4dB and reverse twist < 8dB
     *  -ndB < 10 log10( v1 / v2 ), where v1 < v2
     *  -4dB < 10 log10( v1 / v2 )
     *  -0.4  < log10( v1 / v2 )
     *  0.398 < v1 / v2
     *  0.398 * v2 < v1
     */
    if ( r[col] > r[row] )
    {
      /* Normal twist */
      max_index = col;
      if ( r[row] < (r[col] * 0.398) )    /* twist > 4dB, error */
        see_digit = FALSE;
    }
    else /* if ( r[row] > r[col] ) */
    {
      /* Reverse twist */
      max_index = row;
      if ( r[col] < (r[row] * 0.158) )    /* twist > 8db, error */
        see_digit = FALSE;
    }

    /* Signal to noise test
     * AT&T states that the noise must be 16dB down from the signal.
     * Here we count the number of signals above the threshold and
     * there ought to be only two.
     */
    if ( r[max_index] > 1.0e9 )
      t = r[max_index] * 0.158;
    else
      t = r[max_index] * 0.010;

    peak_count = 0;
    for ( i=0; i<8; i++ )
    {
      if ( r[i] > t )
        peak_count++;
    }
    if ( peak_count > 2 )
      see_digit = FALSE;

    if ( see_digit )
    {
      printf( "%s", row_col_ascii_codes[row][col-4] );
      fflush(stdout);
    }
  }
}


/*----------------------------------------------------------------------------
 *  goertzel
 *----------------------------------------------------------------------------
 */
void goertzel( int sample )
{
  double      q0;
  ui32        i;

  sample_count++;
  for ( i=0; i<MAX_BINS; i++ )
  {
    q0 = coefs[i] * q1[i] - q2[i] + sample;
    q2[i] = q1[i];
    q1[i] = q0;
  }

  if (sample_count == GOERTZEL_N)
  {
    for ( i=0; i<MAX_BINS; i++ )
    {
      r[i] = (q1[i] * q1[i]) + (q2[i] * q2[i]) - (coefs[i] * q1[i] * q2[i]);
      q1[i] = 0.0;
      q2[i] = 0.0;
    }
    post_testing();
    sample_count = 0;
  }
}

Externí odkazy

Chybná citace Nalezena značka <ref> bez příslušné značky <references/>.

[1]

Goertzelův algoritmus

Z PanWiki

Obsah

Popis algoritmu

Practical considerations

Sample code for a DTMF detector

Externí odkazy

Zobrazení

Osobní nástroje

Navigace

Hledat

Nástroje

Na Wikipedii