A multi-tap software delay buffer - Embedded.com

A multi-tap software delay buffer


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).


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.


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.


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.


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.


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 .

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.

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

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

High Pass Filter, (differencing filter)
We can setup an array of coefficients for a different kind of FIRfilter. Here, we specify a simple +/- 1 filter coefficient set. Thistype of high-pass filter also has a small low-pass averagingcharacteristic. This averaging characteristic is important when we wishto do any kind of real-time differencing or derivative computation onreal time data. This is because the act of differencing increases thenoise gain on the signal. LISTING 6 shows the header file for thedifferencing, or high pass FIR filter.

#ifndef   __FIR_DIFF_H  #include  "mtapBuffer.h"            /* the multi-tap delay buffer         */  #define FIR_DIFF_NUM_TAPS 8  typedef struct  fir_diffS  {    mtapBufferS m_ctl;                /* sw tapped delay line controller    */    int m_buffer[FIR_DIFF_NUM_TAPS];       /* the buffer to operate on           */    int coeff[FIR_DIFF_NUM_TAPS];          /* array of FIR coefficients          */    int m_result;                     /* result of each update     */  } fir_diffS;  #ifdef __cplusplus    extern "C"  {  #endif    void  fir_diff_init    (fir_diffS *_this, const int init_val);    int   fir_diff_update  (fir_diffS *_this, const int input);    int   fir_diff_getResult  (fir_diffS *_this);  #ifdef __cplusplus    }  #endif#endif

Listing 6. The header file for the high pass or differencing FIR filter

The coefficient array is organized in TAP order. The correlation between the TAP index and the USER buffer index is shown in Equation 2 . The coefficient initialization for the differencing filter is shown in Listing 7 .

#include  #include  "mtapBuffer.h"              /* the multi-tap delay buffer         */#include  "fir_diff.h"                /* real-time derivative filter        */void fir_diff_init (fir_diffS *_this, const int init_val){  int i;  mtapBuffer_dcbS my_dcb  =  {    0,    {sizeof(int), FIR_DIFF_NUM_TAPS},    _this->m_buffer,    NULL   };   mtapBufferS_init  (&_this->m_ctl, &my_dcb);  mtapBufferS_flush (&_this->m_ctl, &init_val);  for (i=0;icoeff[i] = 1;  }  for (i=FIR_DIFF_NUM_TAPS/2;icoeff[i] = -1;  }} 

Listing 7: this is the case where we initialize the high-pass or differencing filter

The update and convolution is shown in Listing 8 . We need the ‘for’ loop for doing the multiply-accumulate operation. Even though the FIR construct is simple, the implementation of the FIR algorithm does take some time. This listing clearly shows why we need the TAP to user buffer index translation. We need this index translation in order to properly order the convolution computation loop.

Notice how the macro FIR_DIFF_NUM_TAPS is only used in the initializer function. All of the other functions reference the number of taps by accessing its mtapBufferS member. By limiting the access to the number of taps to the initialization; we can readily generalize these filters to any number of taps by simply changing the reference to the user buffer and by changing how the initialization is accomplished.

#include  #include  "mtapBuffer.h"              /* the multi-tap delay buffer         */#include  "fir_diff.h"                /* real-time derivative filter        */int fir_diff_update(fir_diffS *_this, const int input){  int i;  int my_datum;  int my_result=0;  mtapBufferS_update (&_this->m_ctl, &my_datum, &input);  for (i=0;i< _this->m_ctl.dcb.buf_attr.t_count;i++)  {    mtapBufferS_getAt (&_this->m_ctl, &my_datum, i);    my_result += _this->coeff[i] * my_datum;  _this->m_result = my_result;  }  _this->m_result = my_result;  return (_this->m_result);}

Listing 8. The update implementation of a high pass FIR filter

Figure 5 shows the test results for a4-tap and an 8-tap FIR high pass filter. The larger spike for the 1stderivative of the leading and trailing edges of the pulse is due to thelower pass band frequency of the filter with the larger number of taps.Of course, a more sophisticated coefficient selection will yield betterresults.

Just the beginning
Now you know howto create a generic multi-tap software delay buffer. I also showed howto apply this generic method for two specific FIR implementations. Ofcourse, you can go much further than what I describe here. One of thethings you can do is to go out and grab a good book on signal processingand try some filter coefficients on your own.I have enclosed the source code and test routines written in C and C++.It should not be too difficult to generate some test wave forms usingan Excel spreadsheet and do some experimenting using some differentcoefficients for various types of FIR filters.

2 thoughts on “A multi-tap software delay buffer

  1. “This is a nice article on a very useful tool in software. However, my question is, why do you implement this (an ring buffer object) in a language that does not support working with objects at all?nnAs part of a DSP course I teach, I let students design

    Log in to Reply
  2. “I agree … doing this in C++ is superior in every way. However; I am attempting to reach the widest possible audience with these articles. Therefore, the use of C instead of C++. And yes, using templates is indeed the better way to go! Maybe, in a set of

    Log in to Reply

Leave a Reply

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