In vocoders, Linear Prediction Coding (LPC) is used to whiten a speech signal so as to encode much of its shape. This allows for the residual signal to be more uniform and thus requires less information to encode. The associated LPC analysis filter is an all-pole which can be computationally intensive to implement. Finding an efficient algorithm for this is important in order to reduce the requirements of the hardware it is being run on, which reduces the cost of the final product. The straight forward implementation would be:
for(i=0; i<length; i++)
{
out[i] = 0;
for(j=0; i<order; j++)
out[i] += in[i-j] * coefficient[j];
}
The issue with this implementation is that it can create a bottleneck in memory as we are trying to read the input array in a way that jumps around. This can cause large sections of the input array to be removed from memory when in fact it will be needed again during the computation of the next element of the “out” array. A solution to this is to create a state array which will hold the necessary previous elements of the “in” array. One implementation of this is:
for(i=0; i<length; i++)
{
out[i] = 0;
for(j=1; i<order; j++)
{
state[j-1] = state[j];
out[i] += in[j-1] * coefficient[order – j];
}
state[order-1] = in[i];
out[i] += state[order-1] * coefficient[0];
}
This removes the bottleneck with the in array, as it is being accessed in order, which will help with memory control. The problem with this implementation is that we need to copy the state array at each iteration. This can be overcome by using a circular filter where we keep track of where we start in the state array at each iteration. Then, when we reach the end of state in the middle of computing “out”, we wrap back to the beginning of state. This can be implemented as:
k=0;
for(i=0; i<length; i++)
{
out[i] = 0;
for(j=1; i<order; j++)
{
out[i] += state[k] * coefficient[j];
k++;
if(k==order) k=0;
}
out[i] += in[i] * coefficient[0];
state[k] = in[i];
}
This incorporates the idea of the state array while not requiring that we copy the entire array with each iteration. This can be improved even further by removing the “if” statement. Conditional statements such as this can slow down the processor because most of the time it will need to discard the command to set k=0, which it will have preloaded into its queue. If we know what order is ahead of time, we can define a function which will perform the conditional on a binary level. This will remove the issue of adjusting the operations at the conditional. For example if order is a power of 2, we can take the function to be bitwise anding with order-1. For other values of order, there are other fast computations that can be used as replacements for the “if” statement.