A multi-tap software delay buffer

February 06, 2015

Ken.Wada-February 06, 2015

A multi-tap delay buffer is very similar to a queue. The main difference between a multi-tap delay buffer and a queue is the multi-tap delay buffer maintains a fixed element width data stream. The queue, however, has some ‘elasticity’ that allows the queue to shrink and grow. The data stream from beginning to end represents a fixed amount of delay. This delay is represented by the number of elements in the multi-tap delay buffer times the sampling time.

A multi-tap delay buffer implementation usually maintains a single index to the elements within the buffer. Figure 1 shows the ring structure of the delay buffer.

In general, the index will always point to the oldest data within the buffer. The element at the previous index will always point to the newest data within the buffer. Figure 2 shows the relationship at two adjacent points in time.

The ring index will always vary with respect to the elements within the data buffer. However, the ring index will always point to the oldest data element with respect to the TAP index. The TAP index will vary from 0, (newest data element), to the oldest.

Design features
Some design features of the multi-tap delay buffer controller are listed as follows:

  1. The controller must have the ability to manage a user-specified buffer. This allows us flexibility for allowing us to manage any buffer as a fixed size multi-tap delay
  2. The user-specified buffer can have any number of elements. This allows us to specify the total number of taps we would like to have for the delay buffer.
  3. The user-specified elements shall have any element size. Of course, each element will always be a fixed size. It is useful for many applications to be able to manage any element size for a fixed delay buffer.
  4. It would also be handy to define a set of buffer prefill or flush methods. In this case, we should be able to garner a fixed value prefill, a zero clear and even make a user-specified prefill available to allow any type of buffer flush method.

Given these desirable features leads us to our first listing (Listing 1). Of course, as in the other projects I have presented to you, this 1st listing is the main ‘C’ header file, which defines all the attributes and methods needed for the multi-tap delay buffer implementation.

#ifndef   __MTAPBUFFER_H
    #define   __MTAPBUFFER_H
  typedef struct t_elementS
  {
    int t_size;                     /* size of each element                 */
    int t_count;                    /* total # of elements in the buffer    */
  } t_elementS;

  struct mtapBufferS;
  /**************************************************************************/
  /*  The following is a function pointer definition for the optional       */
  /*  buffer flush function.                                                */
  /**************************************************************************/
  typedef void (*MTAP_FLUSHFN)(struct mtapBufferS *, const void *p_datum);
  /**************************************************************************/
  /*  The following is the device control block for the multi-tap buffer    */
  /**************************************************************************/
  typedef struct mtapBuffer_dcbS
  {
    int m_id;                       /* some unique identifier               */
    t_elementS buf_attr;            /* buffer attributes                    */
    void *buffer;                   /* ptr to USER memory for the buffer    */
    MTAP_FLUSHFN  *fn_flush;        /* how to flush the buffer              */
  } mtapBuffer_dcbS;
  /**************************************************************************/
  /*  The multi-tap software delay buffer                                   */
  /**************************************************************************/
  typedef struct mtapBufferS
  {
    mtapBuffer_dcbS dcb;            /* copy of the dcb that made this       */
    int index;                      /* buffer index                         */
  } mtapBufferS;

  #ifdef __cplusplus
    extern "C"  {
  #endif
    void mtapBufferS_init     (mtapBufferS *_this, const mtapBuffer_dcbS *dcb);
    void mtapBufferS_update   (mtapBufferS *_this, void *d_out, const void *d_src);
    void mtapBufferS_getAt    (mtapBufferS *_this, void *d_out, const int m_tap);
    void mtapBufferS_flush    (mtapBufferS *_this, const void *p_datum);
    int  mtapBufferS_indexGet (mtapBufferS *_this, const int m_tap);
  #ifdef __cplusplus
    }
  #endif
#endif

Listing 1. The 'C' header file with the attributes and methods for managing a multi-tap SW delay buffer

The multi-tap buffer record
There is very little within the multi-tap delay buffer record. The only fields are the device control block and the current buffer index. The following is a brief description of what is contained within the device control block (DCB).

m_id

This is some unique handle to a particular multi-tap buffer instance. This index can be used within the application to identify some unique instance of a multi-tap buffer.

buf_attr.t_size

This is the size, in bytes of each element within the buffer. Actually, this is the element size of each element within the user-supplied buffer.

buf_attr.t_count

This is the total number of elements within the user supplied buffer. The total size of the user buffer, in bytes is the element size times the element count.

buffer

This is the pointer to the user-supplied buffer. I made the decision to allow the user to supply some type of buffer for the multi-tap delay controller. This allows a maximum flexibility of where the buffer is stored. The user buffer can be allocated either globally as a static reference or dynamically on a heap if desired.

fn_flush

This can be thought of as a virtual ‘C’ function. This function pointer can either be set to NULL, or set to some user supplied function. The parameters for this function are the pointer to the multi-tap buffer instance and a pointer to some data element which will be used to prefill the buffer. It is important to note that the data element is a void pointer. This allows the developer maximum flexibility on how to implement their flush or prefill function.

The multi-tap buffer methods
There are five(5) methods defined for managing the multi-tap buffer. A brief description of what these methods do are shown in Table 1.

UPDATE
Listing 2 shows the update member function. This function will copy in the newest data element and will retrieve a copy of the oldest data element. We use the standard ‘C’ library memcpy() function here since we have no idea what type we are dealing with. It is up to the developer to make absolutely certain that the element size is properly specified in the DCB.

#include  
#include  "mtapBuffer.h"
/*  This function will update the multi-tap delay buffer with the contents  */
/*  pointed to by 'd_src'.                                                  */
/*                                                                          */
/*    mtapBufferS *_this;       ' pointer to mtap buffer to operate on    ' */
/*    void *d_out;              ' pointer to destination to copy to       ' */
/*    void *d_src;              ' pointer to input data                   ' */
/*                                                                          */
void mtapBufferS_update (mtapBufferS *_this, void *d_out, const void *d_src)
{
  unsigned char *d_array  = (unsigned char *)_this->dcb.buffer;
  int t_size              = _this->dcb.buf_attr.t_size; /* element size     */
  int i                   = t_size * _this->index;      /* get byte index   */
  memcpy (d_out, &d_array[i], t_size);  /* copy the oldest element to dest  */
  memcpy (&d_array[i], d_src, t_size);  /* copy in the newest element       */
  ++_this->index;                       /* update user buffer index         */
  if (_this->index>=_this->dcb.buf_attr.t_count) 
  {
    _this->index  = 0;
  }
}

Listing 2. The multi-tap delay buffer UPDATE member function.

FLUSH
I include the listing for the FLUSH member function in LISTING 3. This function is used to either flush or prefill the buffer. Since I have no idea what is needed, or is appropriate for future implementations, I have defined three(3) different ways to ‘flush’ the buffer.

A. The 1st method is the USER supplied method. In this case, if the USER supplies a FLUSH member function pointer, then this USER method shall be applied
B. The 2nd method is where the datum pointer is a non-null value. In this case, every element of the buffer shall be set to whatever is pointed to.
C. The 3rd method is where the datum pointer is set to NULL. In this case, the flush member function will clear the entire buffer to all zeros(0)

#include  
#include  "mtapBuffer.h"
void mtapBufferS_flush (mtapBufferS *_this, const *p_datum)
{
  if (_this->dcb.fn_flush)    /* invoke USER flush if method != NULL        */
  {
    (* _this->dcb.fn_flush)(_this, p_datum);
  }
  else                        /* default flush methods                       */
  {
    int i;
    unsigned char *d_array  = (unsigned char *)_this->dcb.buffer;
    int element_size        = _this->dcb.buf_attr.t_size;
    int element_count       = _this->dcb.buf_attr.t_count;
    if (p_datum)
    {
      for (i=0; idcb.buffer, 0, element_size * element_count);
    }
  }
  _this->index  = 0;
}
Listing 3: The FLUSH method

The other methods are included in the download area of this website. Of particular note is the relationship between the TAP index and the USER buffer index. Inspection of Figure 2 shows how we can obtain this relationship. The relationship between the TAP index and USER buffer index is shown in Equation 1. In this case, we are interested in obtaining a specific USER buffer index given a specific TAP index. The rationale for this will become clear when we discuss the applications for the multi-tap buffer.

Equation 1 The relationship between the TAP index and the USER buffer index

Given that the MODULO operator is a bit expensive in time; we can alter the above equation to a more algorithmic formula. This formula is defined as a set of inequalities. Equation 2 shows this relationship.

Equation 2 The relationship between the TAP index and the USER buffer as a set of inequalities

Applications
The main reason for creating and maintaining a general purpose multi-tap delay buffer can be readily seen when attempting to implement a finite impulse response, (FIR) filter. In general, an FIR filter is a multi-tap real time convolution of the data stream with a set of coefficients. Figure 3 shows just how this convolution occurs in real time.

Figure 3 A four-tap convolution of a data stream using a 4-tap FIR filter

Simple Moving Average (SMA)
The simplest of the FIR filters is the non-weighted moving average, or the Simple Moving Average, (SMA) filter. In the SMA case, the coefficients are all set to unity (1). LISING 4 shows the header file for the SMA. In this listing we see an instance of the multi-tap delay buffer, in this example the number of taps is set to eight (8). This number can be set to any value and recompiled. Also, we can generalize this value as some user input along with an external buffer. However, I left this exercise up to the reader.

#ifndef   __FIR_SMA8_H
  #include  "mtapBuffer.h"            /* the multi-tap delay buffer         */

  #define FIR_SMA_NUM_TAPS 8

  typedef struct  fir_sma8S
  {
    mtapBufferS m_ctl;                /* sw tapped delay line controller    */
    int m_buffer[FIR_SMA_NUM_TAPS];     /* the buffer to operate on           */
    int accumulator;                  /* accumulator                        */
    int m_result;                         /* the result of the last update         */
  } fir_sma8S;

  #ifdef __cplusplus
    extern "C"  {
  #endif
    void  fir_sma8S_init    (fir_sma8S *_this, const int init_value);
    int   fir_sma8S_update  (fir_sma8S *_this, const int input);
    int    fir_sma8S_getResult (fir_sma8S *_this);
  #ifdef __cplusplus
    }
  #endif

#endif

Listing 4. An example of an SMA filter using the multi-tap delay buffer

The implementation of the SMA filter using the multi-tap delay buffer can be more readily seen within the SMA UPDATE function. The listing for the SMA UPDATE is shown in LISTING 5. Here we see how the oldest value is subtracted from the accumulator and the newest value is added to the accumulator. Notice how the returned update result is the normalized SMA value.

#include  
#include  "mtapBuffer.h"
#include  "fir_sma8.h"

int fir_sma8S_update (fir_sma8S *_this, const int input)
{
  int my_lastValue;

  mtapBufferS_update (&_this->m_ctl, &my_lastValue, &input);
  _this->accumulator = _this->accumulator - my_lastValue;
  _this->accumulator += input;
  _this->m_result     = _this->accumulator / _this->m_ctl.dcb.buf_attr.t_count;
  return (_this->m_result);
}

Listing 5. The update function for an SMA filter using the multi-tap delay buffer controller

Figure 4 shows the test results of the SMA filter for the 4-tap and the 8-tap case. This figure shows that the SMA filter is quite decent at filtering data which has uncorrelated noise. The SMA however, is notoriously bad at rejecting out-of-band signals. For this, you need a different kind of filter.

Figure 4 SMA filter test results for 4 and 8 taps

< Previous
Page 1 of 2
Next >

Loading comments...