Factoring Perfect Reconstruction Filter Banks into Causal Lifting Matrices: A Diophantine Approach

The elementary theory of bivariate linear Diophantine equations over polynomial rings is used to construct causal lifting factorizations (elementary matrix decompositions) for causal two-channel FIR perfect reconstruction transfer matrices and wavelet transforms. The Diophantine approach generates causal factorizations satisfying certain polynomial degree-reducing inequalities, enabling a new factorization strategy called the Causal Complementation Algorithm. This provides a causal (i.e., polynomial, hence realizable) alternative to the noncausal lifting scheme developed by Daubechies and Sweldens using the Extended Euclidean Algorithm for Laurent polynomials. The new approach replaces the Euclidean Algorithm with Gaussian elimination employing a slight generalization of polynomial division that ensures existence and uniqueness of quotients whose remainders satisfy user-specified divisibility constraints. The Causal Complementation Algorithm is shown to be more general than the causal version of the Euclidean Algorithm approach by generating additional causal lifting factorizations beyond those obtainable using the polynomial Euclidean Algorithm.