Circular Buffer for Processing Audio Samples

1. Field of the Invention

The present invention relates generally to buffers. It relates more particularly to a fixed length circular buffer wherein samples are added at one end and samples are removed from the other end.

2. Art Background

Specialized filters generally require a buffer that holds the number of the most recent samples that have been passed through the system, where the number of the most recent samples is a fixed integer. Buffers of fixed length which add samples at one end and remove samples from the other end are known as circular buffers or ring buffers. Circular buffers have been implemented in hardware addressing systems in some digital signal processors, by special address registers, which address memory such that if the address pointer is at the end of the buffer and is incremented, instead of going to the next physical address it moves back to the beginning of the buffer. If the address pointer is at the beginning of the buffer, and is decremented, it automatically moves to the end.

However, the type of functionality available in hardware implemented buffers is not available in a general purpose processor or in a high level language.

Therefore, there has been a need existing for a system which is capable of providing the functionality of a hardware implemented buffer in a general purpose processor or high level language. The present invention fulfills those needs.

Briefly and in general terms, the present invention provides a system for implementing a circular buffer, where samples are added at one end and removed from the other end, without hardware implementation, by doubling the physical buffer length and inserting each new sample at two spaced apart positions.

The system includes a circular buffer for storing a plurality of audio samples during iteration of a system for processing audio samples, wherein a plurality of audio samples comprise an address. The length of the buffer comprises a multiple of the length of an address. The buffer includes first and second opposed ends, wherein an audio sample is added to multiple positions in the buffer upon each iteration of the processing system, and an audio sample is removed from multiple positions in the buffer after a plurality of iterations of the processing system. The system further includes means for adding an audio sample to the multiple positions in the buffer upon each iteration of the processing system, and means for removing an audio sample from the multiple positions in the buffer after a plurality of iterations of the processing system.

One aspect of the present invention is that the system implements a circular buffer which includes a sample window, the length of which is the length of a plurality of samples, wherein the length of the circular buffer is a multiple of the length of the sample window. The entire sample window is treated as a contiguous linear address space in each iteration of the processing system, that is moved through the physical multiple sample length buffer between iterations of the processing system, and is reset to the beginning every sample window length number of iterations of the processing system, substantially increasing the addressing efficiency of the system.

Another aspect of the present invention is that the number of address calculations for each iteration of the processing system is substantially reduced in systems where every buffer position is to be addressed on every iteration, such as specialized filtering, and where circular addressing is not provided in hardware.

Other features and advantages of the invention will become apparent from the following detailed description taken in conjunction with the accompanying drawings, which illustrate, by way of example, the features of the invention.

FIG. 1 is a diagram illustrating a circular buffer in accordance with the present invention;

FIG. 2 is a diagram illustrating a circular buffer in accordance with the prior art;

FIG. 3 is a flow chart illustrating the circular buffer in accordance with the present invention;

FIG. 4 is a flow chart illustrating the circular buffer in accordance with the prior art;

FIG. 5 is a table comparing the number of address calculations in accordance with the present invention and in accordance with the prior art .

Referring now to the drawings, and in particular to the preferred embodiment of the invention in FIG. 1 and to the prior art in FIG. 2, there are shown a buffer 10 for a filter in a system for processing audio samples 12.

Buffer 10 includes a plurality of locations 14 for audio samples 12. Audio samples 12 include samples A, B, C, and D. In the invention embodiment in FIG. 1, there are eight locations 14, locations W, X, Y, Z, W, X, Y, and Z, whereas in the prior art in FIG. 2, there are four locations W, X, Y, and Z. Audio samples A, B, C, and D are input in buffer positions 16 as identified by the pointer arrow or arrows 18 above particular locations 14. Audio samples 12 currently in the filter are identified as current audio samples 20 and by the numbers 0, -1, -2, and -3 below particular locations 14.

In the embodiment of the invention shown in FIG. 1, for example, the size of the buffer is doubled to eight audio sample locations, W, X, Y, Z, W, X, Y and Z, and each audio sample A, B, C, and D is copied to two locations 14 in buffer 10.

In the prior art, as illustrated in FIG. 2, the size of buffer 10 is the same as the filter length, which is four audio samples 12, namely A, B, C and D. For a length of buffer 10 which is the same as the filter length, on each iteration of the filter, it is desired to access every sample 12 on buffer 10. In order to do that on a general purpose processor or the like, the address calculations would have to be checked while incrementing through buffer 10, and for each increment buffer 10 would have to be checked to make sure an audio sample 12 did not go past the end of buffer 10, and if it did then the pointer 18 would have to be wrapped back to the beginning.

As shown the example in FIGS. 1 and 2, buffer 10 starts in an initial state, and then there are four audio sample inputs 12, A, B, C and D, each input at a position or positions 16 in buffer 10 as indicated by pointer arrow or arrows 18 above the position or positions 16. In the FIG. 1 invention embodiment implementation, each audio sample 12 goes in at two positions 14, so that there is always a region in buffer 10, a linear contiguous address space, that doesn't cross the physical buffer boundary, which represents the four samples 12 that are currently in the filter, which positions 16 are identified as zero, minus one, minus two, and minus three. In the FIG. 1 invention embodiment implementation, the current filter samples 0 to -3 do not cross the buffer boundary. In the FIG. 2 prior art implementation, each audio sample 12 goes into buffer 10 at only one position 16. In the FIG. 2 prior art, the position of audio samples 12 in buffer 10 needs to be checked every iteration of the filter, since for each iteration of buffer 10, the buffer boundary is crossed, and only on each fourth iteration is the buffer boundary not crossed.

In the flow chart in FIG. 3 for the invention embodiment, there is only one decision required to check for an audio sample position going past the physical buffer end, specifically where j equals 4. Initially the input is 0, and buffer 10 is at 0. Each of the four inputs is then inserted at two buffer positions, with four checks at decision points in the outer loop where j is less than 4, and no checks in the inner loop, for a total of four checks. In particular, in the flow chart in FIG. 3 for the buffer in FIG. 1, initially a counter i for an outer loop 22 and valid input buffer index (0, 1, 2, 3) is initialized to 0, to initialize the loop counter at a valid buffer index at the beginning of buffer 10. An array b of the eight samples (0, 1, 2, 3, 4, 5, 6, 7) in buffer 10 is also initialized to 0. The next input sample is then input to current valid index input position b[i], and the input is mirrored at a second place in buffer 10, at the higher end of buffer 10 at valid index input position b[i+4], a loop counter j for an inner loop 24 is set to 0, and a convolution counter and valid buffer index k for inner loop 24 is set to i, to initialize k for inner loop 24. Then an accumulator V for calculating the output value of the filter is initialized to 0 at the beginning of outer loop 22. Next the value at b[k] is accumulated into V, which is the output value of the filter, k is incremented so that the next value can be accumulated as the index to the buffer in the next pass through inner loop 24, and j is incremented by 1 as the loop counter. Because buffer 10 has the mirrored input at b[i+4], no check of the value of k has to be made, since k is still a valid buffer address. Next a check is made to see if j<4, to check the loop condition to cycle the inner loop 24 four times which is a buffer wrap, modeling a circular buffer, even though the buffer is a linear buffer of eight samples. Inner loop 24 is then cycled four times, and when j gets to 4, all buffer 10 values have been accumulated into V, whereupon V is output as the output sample, and loop counter i is incremented by 1 to i+1. Next a check is made of outer loop counter i, to see if i.gtoreq.4, and if it is, 4 is subtracted from i to model the circular buffer 10, and to continue through outer loop 22.

In the flow chart in FIG. 4 for the prior art for example, decisions are required for the three values of j other than j less than 4, to check to see if the audio sample position has gone past the physical buffer end. Initially the input is 0, and buffer 10 is at 0. Each of the four inputs is then inserted at one buffer position, with eight checks at decision points in the outer loop where j is less than 4, and sixteen checks in the inner loop, for a total of twenty-four checks. In particular, in the flow chart in FIG. 4 for the prior art buffer in FIG. 2, initially a counter i for outer loop 22 and valid input buffer index (0, 1, 2, 3) is initialized to 0, to initialize the loop counter at a valid buffer index at the beginning of buffer 10. An array b of the four samples (0, 1, 2, 3) in buffer 10 is also initialized to 0. The next input sample is then input to current valid index input position b[i], a loop counter j for inner loop 24 is set to 0, and a convolution counter and valid buffer index k for inner loop 24 is set to look back one buffer length in buffer 10 and increment to where i is. Next a circular buffer address calculation is made to check if k<0. If so, an adjustment is made to set k=k+4, which is the buffer wrap, modeling a circular buffer, even though the buffer is a linear buffer of four samples. This check buffer wrap is required frequently in prior art buffer 10 in FIG. 2, but required infrequently in buffer 10 in FIG. 1. Then an accumulator V for calculating the output value of the filter is initialized to 0 at the beginning of outer loop 22. Next the output value of the filter is accumulated in accumulator V, then k is incremented so that the next value can be accumulated in the next pass through inner loop 24. Next a check is made to see if k.gtoreq.4, since k has just been modified by incrementing it, to see if k is outside of the buffer range. If k.gtoreq.4 then 4 must be subtracted from k to model the circular buffer. Next loop counter j is incremented by 1 to j+1. Next a check is made to see if j<4, to check the loop condition to cycle the inner loop 24 four times. Inner loop 24 is then cycled four times, and when j gets to 4, all buffer 10 values have been accumulated into V, whereupon V is output as the output sample, and loop counter i is incremented by 1 to i+1. Next a check is made of outer loop counter i; to see if i.gtoreq.4, and if it is, 4 is subtracted from i to model the circular buffer 10, and to continue through outer loop 22.

For the invention embodiment in FIGS. 1 and 3, for a buffer length of eight audio samples, for every four audio samples processed, as shown in the right hand column in the table in FIG. 5 there are no address calculations for buffer boundary checks in the inner loop and only four address calculations for buffer boundary checks in the outer loop and in total, which is a substantial savings computationally and in performance over the prior art. For the exemplary prior art buffer where the buffer length is four audio samples, which would be iterated through four times, there is a buffer boundary address calculation check in the inner filter loop, which is an expensive calculation computationally and reduces system performance, resulting in 24 calculations, as shown in the middle column in the table in FIG. 5.

In systems which include a general purpose processor or high level language, and where there is access to a substantial amount of memory without access to hardware addressing, substantially increasing the size in memory of the buffer substantially reduces the processing time for computational calculation.

A functional description of the circular buffer of the present invention is included in the attached Appendix A.

While this invention has been particularly described with reference to a prepared embodiment thereof, it will be understood by one skilled in the art that the present system may be practiced without many of the specific details described above, and that changes in the above description or illustrations may be made with respect to form or detail without departing from the spirit and scope of the invention. ##SPC1##