Polyphase Representation of
Downsampled Sequences

The standard expression for the fourier transform of of a sequence is

X(w) = Sx(n)e-jwn

Since n integrates out of the expression, this is a function of w (omega), the frequency. When we downsample
a sequence, we first set to 0 all of the odd numbered elements:

Xfe(n) = …, 0, x(-2), 0, x(0), 0, x(2), 0, … (fe
stands for "full even")

We can do this by adding 2 sequences together and dividing the sum by 2:

x (the original sequence) and x (with the odd element negated)

(…, x(-1), x(0), x(1), x(2),… + …, -x(-1), x(0), -x(1),
x(2), …)/2

or

[x(n) + x(n)*(-1)n]/2 = Xfe(n)

Clearly (hopefully), with the odd elements negated in one and not negated in
the other, these elements become 0 in the sum. Note: the addition of 2
sequences is not usually defined in math and engineering books. It is assumed
that everybody understands that x(n) + y(n) = z(n), e.g. x(1) + y(1) = z(1),
with z(n) being the resultant "summed" sequence. It is an element by
element sum or "inner sum".

Since (-1)n = e-j(p)n we can incorporate the negation in the fourier
transform of the second sequence. Taking the fourier transform of the sum of
both sequences we have:

Xfe(w) = (1/2)[Sx(n)e-jwn + Sx(n)e-jwne-j pn]

Xfe(w) = (1/2)[Sx(n)e-jwn + Sx(n)e-j(w+p)n]

Xfe(w) = (1/2)[X(w) + X(w-p)]

In a similar way we can create the expression for Xfo(n), the
"full odd" sequence by subtracting the second sequence:

Xfo(w) = (1/2)[Sx(n)e-jwn - Sx(n)e-jwne-j pn]

Xfo(w) = (1/2)[Sx(n)e-jwn - Sx(n)e-j(w+p)n]

Xfo(w) = (1/2)[X(w) - X(w-p)]

Obviously (hopefully),

X(w) = Xfe(w) + Xfo(w)

Converting to the z domain in easy (hopefully), using the following
formulas:

ejw ó z

ej(w+p) ó -z

Note: ej(w+p) = ejwej p= z * (-1) = -z

Therefore

Xfe(z) = (1/2)[X(z) + X(-z)]

Xfo(z) = (1/2)[X(z) - X(-z)]

Recall that these are the z transforms of the sequences

Xfe(n) = …, 0, x(-2), 0, x(0), 0, x(2), 0, …

Xfo(n) = …, x(-3), 0, x(-1), 0, x(1), 0, x(3), 0, …

Note: If we wish to shift the odd sequence to the left, we multiply the z
transform by z.

Compressing the sequences means removing the 0s and filling in the positions
held by the 0s with the remaining values (in order). The above sequences now
become

Xep(n) = …, x(-2), x(0), x(2), …

Xop(n) = …, x(-3), x(-1), x(1), x(3), …

Where ep and op mean "even phase" and "odd phase"
respectively. Xep(n) and Xop(n) are written as X0(n)
and X1(n) respectively. When we compress the sequences with replace
z with z-1/2. So the new transforms are now

X0(z) = (1/2)[X(z-1/2) + X(-z-1/2)]

X1(z) = (1/2)[X(z-1/2) - X(-z-1/2)]

or

X0(z2) = (1/2)[X(z) +
X(-z)]

X1(z2) = (1/2)[X(z) -
X(-z)]

Approching even and odd phase the
other way

Xep(n) = …, x(-2), x(0), x(2), …

Xop(n) = …, x(-3), x(-1), x(1), x(3), …

Xep(w) = Sx(2k)e-jwk = Sx(n)e-j(w/2)n n=2k

Xop(w) = Sx(2k+1)e-jwk = Sx(n)e-jw(n-1)/2ejw/2 = Sx(n)e-j(w/2)nejw/2

= ejw/2Sx(n)e-j(w/2)n n=2k-1

And the corresponding z transform

Xep(z) = Sx(2k)z-k = Sx(n)z-(1/2)n n=2k

Xop(z) = Sx(2k+1)z-k = z1/2Sx(n)z-(1/2)n
n=2k-1

Expanding (upsampling) the compressed (downsampled) sequence inserts 0s at
every other location. This is the inverse of compressing mentioned above.
Expanding simply substitutes z2 for z in the z transform. But
there is a slight twist. The odd sequence has its elements lined up exactly
with the even sequence. If we want to reconstruct the original sequence we have
to shift the odd sequence with respect to the even sequence and then add. This
also in evident in the z1/2 term in the odd phase z transform
above:

X(z) = Xep(z2) + z-1Xop(z2)

The shift is represented by the z-1 term.
Now we have an expression for X(z) in terms of its even and odd phases.

Polyphase representation of
downsampled sequences

All the results can be combined into a concise set of expressions. From this
point on

Xep = X0

Xop = X1

We know from the previous expressions

Xfe(z) = X0(z2)

Xfo(z) = z-1X1(z2)

The convolution of a sequence with a transfer function can be expressed in
terms of the even and odd parts of the two:

X(z)C(z) = {(1/2)[X(z) + X(-z)] +
(1/2)[X(z) - X(-z)]} * {(1/2)[C(z) + C(-z)] + (1/2)[C(z) - C(-z)]}

or more succinctly

X(z)C(z) = [Xfe(z) + Xfo(z)] * [Cfe(z) + Cfo(z)]

And we can substitute the even and odd phases in this expression:

X(z)C(z) = [X0(z2) + z-1X1(z2)]
* [C0(z2) + z-1C1(z2)]

Expanding this expression we get

X(z)C(z) = X0(z2)C0(z2)
+ z-1X0(z2)C1(z2) + z-1X1(z2)C0(z2)
+ z-2X1(z2)C1(z2)

And grouping the terms

X(z)C(z) = X0(z2)C0(z2)
+ z-2X1(z2)C1(z2) + z-1X0(z2)C1(z2)
+ z-1X1(z2)C0(z2)

X0(z2)C0(z2)
+ z-2X1(z2)C1(z2)
= even phase

z-1X0(z2)C1(z2)
+ z-1X1(z2)C0(z2)
= odd phase

To downsample the output of the filter, X(z)C(z),
the odd phase is removed and the elements are compressed (z ó z1/2):

X(z(1/2))C(z(1/2))downsampled
= X0(z)C0(z) + z-1X1(z)C1(z)

The nice thing about this expression is that the even and odd phases of the
sequence are grouped with the even and the odd phases of the filter. This is
the polyphase expression. It can be further expressed as the product of the polyphase
matrix and the input:

[C0(z) C1(z)] [X0(z)
z-1X1(z)]T

[C0(z) C1(z)] =
the polyphase matrix

Thus the sampled filter output can be
implemented as 2 parallel operations: