The document discusses circular buffering, a technique used in digital signal processors to efficiently store incoming data samples for real-time processing. Circular buffering only requires a single write operation for each new sample, unlike linear buffering which requires multiple read and write operations proportional to the filter length. With circular buffering, the newest sample overwrites the oldest sample in a fixed-size memory that logically wraps around like a circle. This allows keeping common data values in place rather than copying them, significantly accelerating data transfer rates needed for real-time systems.
The document discusses circular buffering, a technique used in digital signal processors to efficiently store incoming data samples for real-time processing. Circular buffering only requires a single write operation for each new sample, unlike linear buffering which requires multiple read and write operations proportional to the filter length. With circular buffering, the newest sample overwrites the oldest sample in a fixed-size memory that logically wraps around like a circle. This allows keeping common data values in place rather than copying them, significantly accelerating data transfer rates needed for real-time systems.
The document discusses circular buffering, a technique used in digital signal processors to efficiently store incoming data samples for real-time processing. Circular buffering only requires a single write operation for each new sample, unlike linear buffering which requires multiple read and write operations proportional to the filter length. With circular buffering, the newest sample overwrites the oldest sample in a fixed-size memory that logically wraps around like a circle. This allows keeping common data values in place rather than copying them, significantly accelerating data transfer rates needed for real-time systems.
The document discusses circular buffering, a technique used in digital signal processors to efficiently store incoming data samples for real-time processing. Circular buffering only requires a single write operation for each new sample, unlike linear buffering which requires multiple read and write operations proportional to the filter length. With circular buffering, the newest sample overwrites the oldest sample in a fixed-size memory that logically wraps around like a circle. This allows keeping common data values in place rather than copying them, significantly accelerating data transfer rates needed for real-time systems.
Download as DOCX, PDF, TXT or read online from Scribd
Download as docx, pdf, or txt
You are on page 1/ 6
Circular Buffer: A Critical Element of Digital Signal Processors
This article discusses circular buffering, which allows us to significantly
accelerate the data transfer in a real-time system.
A digital signal processor is a specialized microprocessor for the kind of
algorithms employed in digital signal processing (DSP). The main goal is to accelerate the calculations while keeping the power consumption as low as possible. In this article, we review a basic addressing capability of DSP processors, i.e. circular buffering, which allows us to significantly accelerate the data transfer in a real-time system.
Please note that since the acronym “DSP” stands for both “digital signal processing” and “digital signal processor," we will use the term “DSP processor” when referring to the hardware rather than the algorithm.
Since the finite-impulse-response (FIR) filtering is a common operation in DSP,
we will continue our discussion based on examining the difference equation of an FIR filter. This simple example will show the typical properties of many DSP algorithms. After reviewing the problem of handling the incoming samples, we will discuss the circular buffering as an efficient solution to the problem.
Performing FIR Filtering on a Real-Time Input
Assume that we have a four-tap filter with the following difference equation: y(n)=b0x(n)+b1x(n−1)+b2x(n−2)+b3x(n−3) ------1
where b0, b1, ……, b3 are the filter coefficients and x(n)x(n) denotes the input
samples. To calculate Equation 1, we need to store the last four samples of the input in a memory. Assume that we have a real-time system, such as a hearing aid. In this case, there is an infinite number of input samples which become available to us over time. As a result, we may take one input sample, calculate Equation 1, move the result to an output device, and then, repeat this procedure for the next input sample. Hence, this example requires the following steps for each input sample: 1. Acquire an input sample from the analog world and find its digital representation using an analog-to-digital converter (ADC). 2. Inform the system that the new sample is available. 3. Store the new sample in the memory (in the example of Equation 1, we will need this new sample to produce four output samples, so we have to store the acquired samples for some time). 4. Use the new sample and the last three samples to calculate Equation 1. 5. Move the result to an output device such as a digital-to-analog converter (DAC) or simply store it somewhere in the memory for later use. 6. Go back to step 1.
This example shows that a simple DSP algorithm involves data transfer, inequality evaluation, and a lot of math operations. For example, during steps 3 and 5, we have to transfer, respectively, the input and the result to a memory location. Step 4 involves a lot of math operations. In this step, the input samples are multiplied by their corresponding filter coefficients and the products are added together. This is generally achieved by a dedicated multiply-and- accumulate (MAC) unit which is shown in Figure 1.
Figure 1. The simplified model of a MAC.
Step 4 requires some inequality evaluations to keep track of the intermediate results and control the loops. The math operations in step 4 seem to be the most time-consuming part of the algorithm and the DSP processors attempt to accelerate these calculations using various techniques. However, it is interesting to note that, without a careful design, operations such as transferring the data and controlling the loops can be time-consuming too. In the rest of this article will review a well-known technique, i.e. circular buffering, to facilitate the data transfer in a real-time system. Linear Buffering The direct-form realization of Equation 1 is shown in Figure 2.
Figure 2. The direct-form realization of a four-tap filter.
The above figure suggests that we need four memory locations to store the current sample and the three previous samples. When a new sample is acquired, we will discard the oldest sample and push the other samples upward (see Figure 3) by one memory location.
Figure 3. A linear buffer at (a) time index n=3 and (b) n=4.
Figure 3(a) shows that, at time index n=3, the last four samples stored in the memory are x(3), x(2), x(1), and x(0). When a new sample is acquired at n =4, the last four samples, x(4), x(3), x(2), and x(1), will be stored in the memory as shown in Figure 3(b). This approach to storing the incoming samples is called the linear buffering. As we will see in a minute, it is simple but not at all efficient. The main problem with linear buffering is the amount of the data transfer that we need to handle. Consider the above linear buffer for the four-tap FIR filter. With each new sample, we have to read three memory locations and write their contents to another location in our array. This is shown in Figure 4. We observe that the number of read and write operations are proportional to the length of the filter. That’s why the linear buffering is not an efficient method of storing the incoming samples. For example, if we use a linear buffer to implement a 256- tap filter, then, with each new sample acquired, we have to perform almost 256 read and write operations!
Circular Buffering Let’s examine Figure 3 one more time. The memory in Figure 3(a) stores four input samples:
x(0), x(1), x(2), and x(3). Figure 3(b) stores x(1), x(2), x(3) along with the new sample x(4). We observe that three values, i.e. x(3), x(2), x(1), are common between the two cases shown in Figure 3; however different memory locations are used to store these common values. Can we use the above observation to reduce the number of the required read and write operations? For example, what’s the point of copying x(3) from the hypothetical memory location 2004 in Figure 3(a) to the address 2003 in Figure 3(b), and then using it in the upcoming calculations? If we keep the common values where they currently reside, then we only need to store the new sample, i.e. x(4), in the memory. When x(4) is acquired, we no longer need x(0), hence, we can use the memory location 2001 to store x(4). The result is shown in Figure 5. As shown in this figure, the newest sample, x(4), replaces the oldest sample x(0). This technique for storing the incoming samples is called the circular buffering. In this way, with each new sample, only a single memory write operation is required. Figure 5. A circular buffer at (a) time index n=3 and (b) n=4.
Figure 6 shows how the next four samples will be placed in the circular buffer of this example. Based on the above discussion, each new sample replaces the oldest sample. Please note the position of the newest sample in each state of Figure 6. With each new sample acquired, the position of the newest sample moves forward by one memory location from Figure 6(a) to Figure 6(c). However, when the new sample position reaches the end of the buffer in Figure 6(c), it jumps back to the beginning of the allocated memory. We can think of this as a hypothetical circular memory where the end of the buffer is connected to its beginning (Figure 7). When we reach the end the buffer, the next memory location will be the first location of the buffer. This explains the name chosen for this technique, i.e. the circular buffering. Figure 6. The circular buffer at (a) time index n=5, (b) n=6, (c) n=7, and (d) n=8.
