US 2004/0064494 A1 · Discrete-time convolution cycle reduction with programmable digital signal processor

Abstract

A programming algorithm reduces from θ (2N2) to θ (N2) the number of multiply-and-accumulate (MAC) instructions required to perform a discrete-time convolution on a programmable digital signal processor. Through the use of a single repeat instruction along with a single repeat count register, the algorithm dynamically changes the number of times the multiply-accumulate instruction is repeated depending upon the current term being convolved. The avoids performing the multiply-accumulate when one term is zero. The nature of the discrete-time convolution calculation and the flexibility of a re-programmable single repeat count register offers permits this. Additional instructions are required for data pointer alignment. The trade-off between reduced multiply-accumulate operations and the overhead required to achieve it is examined.

Claims6

Dependent claims

A method of discrete time convolution of two sets of time limited signals of the form

2 Y ⁡ ( n ) = ∑ k = 0 N ⁢ ⁢ X ⁡ ( k ) ⁢ H ⁡ ( n - k )
where:
H(n−k) is a discrete-time component of some transfer function of the system, shifted by the current time step, and X(k) is the discrete-time component of the input function, the method comprising:
performing a multiply-accumulate of X(k) and H(n−k) when both X(k) and H(n−k) are non-zero;
and
not performing a multiply-accumulate of X(k)H(n−k) when either X(k) or H(n−k) is zero.

3 more elements

Dependencies are inferred from the claim text.

Discrete-time convolution cycle reduction with programmable digital signal processor

Life of this patent

Discrete-time convolution cycle reduction with programmable digital signal processor

Life of this patent

Abstract

Claims6