Coding wavelets the easy way

The z-transform


When we shall implement the discrete wavelet transform, we shall use FIR filters which are causal, and others which are not. A filter L is said to be causal if its impulse response h satisfies h[k] = 0 if k<0. As a consequence the output y[k] at index k of a causal filter L only involves input values x[n] for indices smaller than k, i.e. n≤k.
The convolution formula does not make very clear how to implement non causal filters. This can be more easily understood by introducing the z-transform of a signal:
Definition: the z-transform of a signal x is the formal series X(z) defined by

X(z) = ∑x[k]z^k where k spans the set on signed integers and z^k denotes the k-th power of the indeterminate z.

We see that a filter L is FIR if and only if the z-transform H of its impulse response h is , up to a multiplication with a monomial z^d, a polynomial in the indeterminate z. Note: another version uses the inverse of z in place of the indeterminate z; this has no consequence for this z-transform.
The main result is the following:
Let L an LTI filter with impulse response h, x a signal and y the output y = Lx. Define H, X and Z as, respectively, the z-transforms of h,x and y. Then

Y = H X

i.e., the z-transform maps convolution into ordinary product of formal series.
A case of particular interest is when h is causal and x has a support within the set of nonnegative integers. Then their z-transforms are polynomials, and the z-transform of the output is obtained by a product of polynomial. This is why Matlab implements the product of polynomials as a convolution of vectors.
What we shall do is use the idea on the z-transform to generalize the convolution operator to non causal filters, or signals with support partly in the set of negative integers.

I do not see z-transforms in my wavelet textbook: why?
What you will see instead is the Fourier integral of a sampled signal or impulse response. If you want to get the Fourier integral from the z transform, assuming the sampling interval is 1, replace z by e^(-iω).
This transforms a polynomial into a trigonometric polynomial. The Fourier integral is used because it can be used for variable sampling rates, and it provides a unified framework. It provides a formula for the subsampling operator, whereas the z-transform cannot. However, for the purpose of this tutorial, the z-transform does most of the job, and it requires much less mathematical background than the Fourier integral. In particular, we do not have here to make any assumption on the way discrete time data is related to continuous time data.

Summary


The z-transform maps data into formal series, and it maps the convolution product into the product of series.