Method and apparatus for performing rapid convolution

A method for performing a finite impulse response filter operation on a plurality of inputs using a plurality of coefficients comprising the steps of:

• a) defining a maximum number of the plurality of coefficients and a maximum number of a plurality of outputs, both of which are multiples of four;
• b) setting a first counter (n) equal to zero;
• c) setting a second counter (i) equal to zero;
• d) calculating four equations as below:
• output(i)=coeff(n)*input(n+i)+coeff(n+1)*input(n+i+1)+coeff(n+2)*input(n+i+2)+coeff(n+3)*input(n+i+3) (equation 1);
• output(i+1)=coeff(n−1)*input(n+i)+coeff(n)*input(n+i+1)+coeff(n+1)*input(n+i+2)+coeff(n+2)*input(n+i+3) (equation 2);
• output(i+2)=coeff(n−2)*input(n+i)+coeff(n−1)*input(n+i+1)+coeff(n)*input(n+i+2)+coeff(n+1)*input(n+i+3) (equation 3);
• output(i+3)=coeff(n−3)*input(n+)+coeff(n−2)*input(n++1)+coeff(n−1)*input(n+i+2)+coeff(n)*input(n+i+3) (equation 4),
• wherein coeff(n) is an nth coefficient of the plurality of coefficients and input(n) is an nth input of the plurality of inputs;
• e) incrementing the second counter (i) by four and repeating step d) until the second counter (i) exceeds said maximum number of the plurality of outputs;
• and
• f) incrementing the first counter (n) by four and repeating steps c) through e) until the first counter (n) exceeds said maximum of the plurality of coefficients.

A method for calculating a plurality of outputs of a convolution operation on a plurality of inputs comprising the steps of:

• a) performing a matrix-vector multiplication in which a set of four coefficients of a plurality of coefficients is used to process all inputs, four at a time, to derive a partial sum of four outputs;
• b) repeating step a) for a next set of four coefficients until all coefficients of the plurality of coefficients are processed and updating the partial sum each time;
• and
• c) reusing the set of four coefficients in each successive calculation in step a).

In a reduced instruction set processor having a wide internal bus, whereby the processor can access multiple data in a single cycle, said processor performing a memory access of two data elements (inputR(n)) and inputI(n)) and a matrix-vector multiplication in four cycles, a method for performing a complex filter operation using a plurality of real coefficients (coeffR(n)) and a plurality of imaginary coefficients (coeffI(n)), comprising the steps of:

• a) defining a plurality of real outputs (ouput(R(i)) and a plurality of imaginary outputs (outputI(i));
• b) setting a first counter (n) to zero;
• c) setting a second counter (i) equal to zero;
• d) calculating the following equations:
• outputR(i)=coeffR(n)*inputR(n+i)−coeffI(n)*inputI(n+i)+coeffR(n+1)*inputR(n+i+1)−coeffI(n+1)*inputI(n+i+1);
• outputI(i)=coeffI(n)*inputR(n+i)+coeffR(n)*inputI(n+i)+coeffI(n+1)*inputR(n+i+1)+coeffR(n+1)*inputI(n+i+1);
• outputR(i+1)=coeffR(n−1)*inputR(n+i)−coeffI(n−1)*inputI(n+i)+coeffR(n)*input(n+i+1)−coeffI(n)*inputI(n+i+1);
• outputI(i+1)=coeffI(n−1)*inputR(n+i)+coeffR(n−1)*inputI(n+i)+coeffI(n)*inputR(n+i+1)+coeffR(n)*inputI(n+i+1);
• e) incrementing the second counter by two and repeating step d) until the second counter exceeds a predetermined number;
• and
• f) incrementing the first counter by two and repeating steps c) through e) until the first counter exceeds a number of the plurality of real coefficients or the plurality of imaginary coefficients.

In a reduced instruction set processor having a wide internal bus, whereby the processor can access multiple data in a single cycle, said processor performing a memory access of two data elements and a matrix-vector multiplication in four cycles, a method for performing a filter adaptation operation to determine a plurality of coefficients, said filter adaptation operation using an error signal and a scaleFactor to determine the plurality of coefficients, comprising the steps of:

• a) setting a first counter (n) to zero;
• b) setting a second counter (i) equal to zero;
• c) calculating the following equation:
• output(i)=error(i)×input(n+i);
• d) incrementing tie second counter (i) and repeating step d) until the second counter (i) exceeds a predetermined number of outputs;
• e) incrementing the first counter (n) and repeating steps b) through d) until the first counter (n) exceeds a number of the plurality of coefficients;
• f) setting a third counter (k) to zero;
• g) calculating the following equation:
• coeff(k)=scaleFactor×Output(k),
• wherein coeff(k) is a kth coefficient of the plurality of coefficients;
• and
• h) incrementing the third counter (k) and repeating step g) until the third counter (k) exceeds the number of the plurality of coefficients.

In a reduced instruction set processor having a wide internal bus, whereby the processor can access multiple data in a single cycle, said processor performing a memory access of two data elements and a matrix-vector multiplication in four cycles, a method for performing a decimating filter operation on a plurality of inputs using a plurality of coefficients and a decimating value, comprising the steps of:

• a) setting a first (j) counter to zero;
• b) setting a second counter (n) equal to zero;
• c) setting a third counter (i) equal to zero;
• d) calculating the following equation:
• output(i)=coeff(n×d+j)×input(n×d+i+j),
• wherein coeff(n) is an nth coefficient of the plurality of coefficients, d is the decimating value, input (n) is an nth input of the plurality of inputs, and output(i) is an ith output of a plurality of outputs;
• e) incrementing the third counter (i) and repeating step d) until the third counter (i) exceeds a number of the plurality of outputs;
• f) incrementing the second counter (n) and repeating steps c) through e) until the second counter (n) exceeds a number of the plurality of coefficients;
• and
• g) incrementing the first counter (j) and repeating steps b) through f) until the first counter (j) exceeds the decimating value.

An apparatus for performing a convolution operation comprising:

• a) a matrix multiplier receiving as a fist input an n×n-bit coefficient and receiving as a second input an n-bit wide signal;
• b) an n-element adder coupled to the matrix multiplier and receiving an n-bit wide output from the matrix multiplier as a first input and a second input being n-bits wide, and having an output being n-bits wide;
• c) a first multiplexer being coupled to the output of the n-element adder and converting an nl-bit input to a plurality of l outputs, each of which are n bits;
• d) an output register having nl bits and having l inputs, each being n-bits wide, said l inputs being coupled to the first multiplexer and l outputs, each being n-bits wide;
• and
• e) a second multiplexer having l inputs each being n-bits wide, said l inputs being coupled to the l outputs of the output register and converting the ln inputs to a single output being n-bits wide, said single output being coupled in feedback fashion to the second input of the n-element adder.

A method for performing a convolution operation comprising the steps of:

• a) initializing a first counter;
• b) shifting a plurality of ln input values into an input register;
• c) initializing an output register,
• d) loading a coefficient register with a plurality of coefficients;
• e) initializing a second counter;
• i) selecting a j+ith input of a first multiplexer;
• g) performing a matrix multiplication;
• h) selecting ith inputs from a second and third multiplexers;
• i) performing an n-element addition of the matrix product and an output of the third multiplexer;
• j) loading n output partial products into the output register at location i;
• and
• k) incrementing the second counter by one, and returning to step f) and repeating steps f) through k) as long as the second counter remains such that i<l, wherein once the second counter exceeds l (i.e., i>l), continuing with step 1);
• l) loading n-input coefficients into the coefficient matrix register;
• m) shifting the coefficient matrix register;
• and
• n) incrementing the first counter by one, and returning to step e) and repeating steps e) through n) as long as the first counter remains such the j<m, wherein once the first counter exceeds m (i.e., j>m), and shifting an output of the output register.

An apparatus for performing a convolution operation comprising:

• a) means for performing a matrix multiplication, said matrix multiplication means receiving as a first input an n×n-bit coefficient and receiving as a second input an n-bit wide signal;
• b) means for performing an n-element addition, said n-element addition means coupled to the matrix multiplication means and receiving an n-bit wide output from the matrix multiplication means as a first input and having a second input being n-bits wide, and having an output being n-bits wide;
• c) first multiplexer means being coupled to the output of the n-element addition means and converting an nl-bit input to l outputs, each of which is n bits wide;
• d) a first storage means storing nl bits and having l inputs, each being n-bits wide, said l inputs being coupled to the first multiplexer means and l outputs, each being n-bits wide;
• and
• e) a second multiplexer means having l inputs, each being n-bits wide, said l inputs being coupled to the l outputs of the first storage means and converting the ln inputs to a single output being n-bits wide, said single output being coupled in feedback fashion to the second input of the n-element addition means.

An apparatus for performing a convolution operation comprising:

• a) a first counter counting a first integer value j;
• b) an input register receiving a plurality of jn input values;
• c) an output register;
• d) a coefficient register receiving a plurality of coefficients;
• e) a second counter counting a second integer value i;
• f) a first multiplexer having a plurality of inputs and outputting a j+ith input;
• g) means for performing a matrix multiplication;
• h) a second multiplexer having a plurality of inputs and outputting an ith input;
• i) a third multiplexer having a plurality of inputs and outputting an ith input;
• j) means for performing an n-element addition of a matrix product and an output of the third multiplexer;
• k) an output register having a plurality of locations and receiving n output partial products at location i;
• l) wherein said second is incremented by one and said first multiplexer, said matrix multiplication means, said second multiplexer, said third multiplexer, said n-element adding means and said output register continue to perform their functions as long as the second counter remains such that i<j, wherein once the second counter exceeds j said first multiplexer, said matrix multiplication means, said second multiplexer, said third multiplexer, said n-element adding means and said output register stop performing their functions;
• wherein said coefficient matrix register receives n-input coefficients, said coefficient matrix register is shiftable in accordance with the first counter, and said first counter is incremented by one and said first multiplexer, said matrix multiplication means, said second multiplexer, said third multiplexer, said n-element adding means and said output register start their functions again as long as the first counter remains such that i<n, and once the first counter exceeds n an output of the output register is shifted out.