0.12 Convolution algorithms  (Page 5/7)

Block state formulation

It is possible to reduce the size of the matrix operators in the blockrecursive description [link] to give a form even more like a state variable equation [link] , [link] , [link] . If $K$ in [link] has several zero eigenvalues, it should be possible to reduce the size of $K$ until it has full rank. That was done in [link] and the result is

where $H_0$ is the same $N$ by $N$ convolution matrix, $N_1$ is a rectangular $L$ by $N$ partition of the convolution matrix $H$ , $K_1$ is a square $N$ by $N$ matrix of full rank, and $K_2$ is a rectangular $N$ by $L$ matrix.

This is now a minimal state equation whose input and output are blocks of the original input and output. Some of the matrix multiplications can becarried out using the FFT or other techniques.

Block implementations of digital filters

The advantage of the block convolution and recursion implementations is a possible improvement in arithmetic efficiency by using the FFT or otherfast convolution methods for some of the multiplications in [link] or [link] [link] , [link] . There is the reduction of quantization effects due to an effective decrease in the magnitude of the eigenvalues and thepossibility of easier parallel implementation for IIR filters. The disadvantages are a delay of at least one block length and an increasedmemory requirement.

These methods could also be used in the various filtering methods for evaluating the DFT. This the chirp z-transform, Rader's method, andGoertzel's algorithm.

Multidimensional formulation

This process of partitioning the data vectors and the operator matrices can be continued by partitioning [link] and [link] and creating blocks of blocks to give a higher dimensional structure. One should useindex mapping ideas rather than partitioned matrices for this approach [link] , [link] .

Periodically time-varying discrete-time systems

Most time-varying systems are periodically time-varying and this allows special results to be obtained. If the block length is set equal to theperiod of the time variations, the resulting block equations are time invariant and all to the time varying characteristics are contained in thematrix multiplications. This allows some of the tools of time invariant systems to be used on periodically time-varying systems.

The PTV system is analyzed in [link] , [link] , [link] , [link] , the filter analysis and design problem, which includes the decimation–interpolationstructure, is addressed in [link] , [link] , [link] , and the bandwidth compression problem in [link] . These structures can take the form of filter banks [link] .

Multirate filters, filter banks, and wavelets

Another area that is related to periodically time varying systems and to block processing is filter banks [link] , [link] . Recently the area of perfect reconstruction filter banks has been further developed and shownto be closely related to wavelet based signal analysis [link] , [link] , [link] , [link] . The filter bank structure has several forms with the polyphase and lattice being particularly interesting.

An idea that has some elements of multirate filters, perfect reconstruction, and distributed arithmetic is given in [link] , [link] , [link] . Parks has noted that design of multirate filters has some elements in common with complex approximation and of 2-D filterdesign [link] , [link] and is looking at using Tang's method for these designs.