0.12 Convolution algorithms  (Page 4/7)

This can also be written to generate the square partitions of the impulse response matrix by

with initial conditions given by

ane $K=-A_0^{-1}{A}_1$ . This recursively generates square submatrices of $H$ similar to those defined in [link] and [link] and shows the basic structure of the dynamic system.

Next, we develop the recursive formulation for a general input as described by the scalar difference equation [link] and in matrix operator form by

which, after substituting the definitions of the sub matrices and assuming the block length is larger than the order of the numerator or denominator,becomes

From the partitioned rows of [link] , one can write the block recursive relation

Solving for ${\underline{y}}_{n+1}$ gives

which is a first order vector difference equation [link] , [link] . This is the fundamental block recursive algorithm that implements the originalscalar difference equation in [link] . It has several important characteristics.

• The block recursive formulation is similar to a state variable equation but the states are blocks or sections of the output [link] , [link] , [link] , [link] .
• The eigenvalues of $K$ are the poles of the original scalar problem raised to the $N$ power plus others that are zero. The longer the block length, the “more stable" the filter is, i.e. the further the poles arefrom the unit circle [link] , [link] , [link] , [link] , [link] .
• If the block length were shorter than the denominator, the vector difference equation would be higher than first order. There would be anon zero $A_2$ . If the block length were shorter than the numerator, there would be a non zero $B_2$ and a higher order block convolution operation. If the block length were one, the order of the vector equationwould be the same as the scalar equation. They would be the same equation.
• The actual arithmetic that goes into the calculation of the output is partly recursive and partly convolution. The longer the block, the morethe output is calculated by convolution and, the more arithmetic is required.
• It is possible to remove the zero eigenvalues in $K$ by making $K$ rectangular or square and N by N This results in a form even more similar to a state variable formulation [link] , [link] . This is briefly discussed below in section 2.3.
• There are several ways of using the FFT in the calculation of the various matrix products in [link] and in [link] and [link] . Each has some arithmetic advantage for various forms and orders of the originalequation. It is also possible to implement some of the operations using rectangular transforms, number theoretic transforms, distributedarithmetic, or other efficient convolution algorithms [link] , [link] , [link] , [link] , [link] , [link] .
• By choosing the block length equal to the period, a periodically time varying filter can be made block time invariant. In other words, all thetime varying characteristics are moved to the finite matrix multiplies which leave the time invariant properties at the block level. This allowsuse of z-transform and other time-invariant methods to be used for stability analysis and frequency response analysis [link] , [link] . It also turns out to be related to filter banks and multi-rate filters [link] , [link] , [link] .