Block Signal Processing In this section the usual convolution and recursion that implements FIR and IIR discrete-time filters are reformulated in terms of vectors and matrices. Because the same data is partitioned and grouped in a variety of ways, it is important to have a consistent notation in order to be clear. The nth element of a data sequence is expressed h(n) or, in some cases to simplify, hn. A block or finite length column vector is denoted h̲n with n indicating the nth block or section of a longer vector. A matrix, square or rectangular, is indicated by an upper case letter such as H with a subscript if appropriate.

Block Convolution The operation of a finite impulse response (FIR) filter is described by a finite convolution as y ( n ) = ∑ k = 0 L - 1 h ( k ) x ( n - k ) where x(n) is causal, h(n) is causal and of length L, and the time index n goes from zero to infinity or some large value. With a change of index variables this becomes y ( n ) = ∑ k = 0 n h ( n - k ) x ( k ) which can be expressed as a matrix operation by y 0 y 1 y 2 ⋮ = h 0 0 0 ⋯ 0 h 1 h 0 0 h 2 h 1 h 0 ⋮ ⋮ x 0 x 1 x 2 ⋮ . The H matrix of impulse response values is partitioned into N by N square sub matrices and the X and Y vectors are partitioned into length-N blocks or sections. This is illustrated for N=3 by H 0 = h 0 0 0 h 1 h 0 0 h 2 h 1 h 0 H 1 = h 3 h 2 h 1 h 4 h 3 h 2 h 5 h 4 h 3 etc. x ̲ 0 = x 0 x 1 x 2 x ̲ 1 = x 3 x 4 x 5 y ̲ 0 = y 0 y 1 y 2 etc. Substituting these definitions into () gives y ̲ 0 y ̲ 1 y ̲ 2 ⋮ = H 0 0 0 ⋯ 0 H 1 H 0 0 H 2 H 1 H 0 ⋮ ⋮ x ̲ 0 x ̲ 1 x ̲ 2 ⋮ The general expression for the nth output block is y ̲ n = ∑ k = 0 n H n - k x ̲ k which is a vector or block convolution. Since the matrix-vector multiplication within the block convolution is itself a convolution, () is a sort of convolution of convolutions and the finite length matrix-vector multiplication can be carried out using the FFT or other fast convolution methods. The equation for one output block can be written as the product y ̲ 2 = H 2 H 1 H 0 x ̲ 0 x ̲ 1 x ̲ 2 and the effects of one input block can be written H 0 H 1 H 2 x ̲ 1 = y ̲ 0 y ̲ 1 y ̲ 2 . These are generalize statements of overlap save and overlap add , . The block length can be longer, shorter, or equal to the filter length.

Block Recursion Although less well-known, IIR filters can be implemented with block processing , , , , . The block form of an IIR filter is developed in much the same way as for the block convolution implementation of the FIR filter. The general constant coefficient difference equation which describes an IIR filter with recursive coefficients al, convolution coefficients bk, input signal x(n), and output signal y(n) is given by y ( n ) = ∑ l = 1 N - 1 a l y n - l + ∑ k = 0 M - 1 b k x n - k using both functional notation and subscripts, depending on which is easier and clearer. The impulse response h(n) is h ( n ) = ∑ l = 1 N - 1 a l h ( n - l ) + ∑ k = 0 M - 1 b k δ ( n - k ) which can be written in matrix operator form 1 0 0 ⋯ 0 a 1 1 0 a 2 a 1 1 a 3 a 2 a 1 0 a 3 a 2 ⋮ ⋮ h 0 h 1 h 2 h 3 h 4 ⋮ = b 0 b 1 b 2 b 3 0 ⋮ In terms of N by N submatrices and length-N blocks, this becomes A 0 0 0 ⋯ 0 A 1 A 0 0 0 A 1 A 0 ⋮ ⋮ h ̲ 0 h ̲ 1 h ̲ 2 ⋮ = b ̲ 0 b ̲ 1 0 ⋮ From this formulation, a block recursive equation can be written that will generate the impulse response block by block. A 0 h ̲ n + A 1 h ̲ n - 1 = 0 for n ≥ 2 h ̲ n = - A 0 - 1 A 1 h ̲ n - 1 = K h ̲ n - 1 for n ≥ 2 with initial conditions given by h ̲ 1 = - A 0 - 1 A 1 A 0 - 1 b ̲ 0 + A 0 - 1 b ̲ 1 This can also be written to generate the square partitions of the impulse response matrix by H n = K H n - 1 for n ≥ 2 with initial conditions given by H 1 = K A 0 - 1 B 0 + A 0 - 1 B 1 ane K=-A0-1A1. This recursively generates square submatrices of H similar to those defined in () and () 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 () and in matrix operator form by 1 0 0 ⋯ 0 a 1 1 0 a 2 a 1 1 a 3 a 2 a 1 0 a 3 a 2 ⋮ ⋮ y 0 y 1 y 2 y 3 y 4 ⋮ = b 0 0 0 ⋯ 0 b 1 b 0 0 b 2 b 1 b 0 0 b 2 b 1 0 0 b 2 ⋮ ⋮ x 0 x 1 x 2 x 3 x 4 ⋮ 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 A 0 0 0 ⋯ 0 A 1 A 0 0 0 A 1 A 0 ⋮ ⋮ y ̲ 0 y ̲ 1 y ̲ 2 ⋮ = B 0 0 0 ⋯ 0 B 1 B 0 0 0 B 1 B 0 ⋮ ⋮ x ̲ 0 x ̲ 1 x ̲ 2 ⋮ . From the partitioned rows of (), one can write the block recursive relation A 0 y ̲ n + 1 + A 1 y ̲ n = B 0 x ̲ n + 1 + B 1 x ̲ n Solving for y̲n+1 gives y ̲ n + 1 = - A 0 - 1 A 1 y ̲ n + A 0 - 1 B 0 x ̲ n + 1 + A 0 - 1 B 1 x ̲ n y ̲ n + 1 = K y ̲ n + H 0 x ̲ n + 1 + H ˜ 1 x ̲ n which is a first order vector difference equation , . This is the fundamental block recursive algorithm that implements the original scalar difference equation in (). 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 , , , . 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 are from the unit circle , , , , . If the block length were shorter than the denominator, the vector difference equation would be higher than first order. There would be a non zero A2. If the block length were shorter than the numerator, there would be a non zero B2 and a higher order block convolution operation. If the block length were one, the order of the vector equation would 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 more the 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 , . 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 () and in () and (). Each has some arithmetic advantage for various forms and orders of the original equation. It is also possible to implement some of the operations using rectangular transforms, number theoretic transforms, distributed arithmetic, or other efficient convolution algorithms , , , , , . By choosing the block length equal to the period, a periodically time varying filter can be made block time invariant. In other words, all the time varying characteristics are moved to the finite matrix multiplies which leave the time invariant properties at the block level. This allows use of z-transform and other time-invariant methods to be used for stability analysis and frequency response analysis , . It also turns out to be related to filter banks and multi-rate filters , , .

Block State Formulation It is possible to reduce the size of the matrix operators in the block recursive description () to give a form even more like a state variable equation , , . If K in () has several zero eigenvalues, it should be possible to reduce the size of K until it has full rank. That was done in and the result is z ̲ n = K 1 z ̲ n - 1 + K 2 x ̲ n y ̲ n = H 1 z ̲ n - 1 + H 0 x ̲ n where H0 is the same N by N convolution matrix, N1 is a rectangular L by N partition of the convolution matrix H, K1 is a square N by N matrix of full rank, and K2 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 be carried 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 other fast convolution methods for some of the multiplications in () or () , . There is the reduction of quantization effects due to an effective decrease in the magnitude of the eigenvalues and the possibility of easier parallel implementation for IIR filters. The disadvantages are a delay of at least one block length and an increased memory requirement. These methods could also be used in the various filtering methods for evaluating the DFT. This the chirp z-transform, Rader's method, and Goertzel's algorithm.

Multidimensional Formulation This process of partitioning the data vectors and the operator matrices can be continued by partitioning () and () and creating blocks of blocks to give a higher dimensional structure. One should use index mapping ideas rather than partitioned matrices for this approach , .