Sometimes you need to split a signal in two or more phases and keep
(one of) these in seperate shorter arrays. That process is equivalent
to downsampling. From a matrix perspective, it can be considered a row
permutation. I want to illustrate phase decomposition as a matrix
operation here.

I will start from the identity matrix, and later convert that to a
downsampling matrix. The input vector is a series from 0 to 7, so we
can track where they go. Multiplication with the identity matrix, of
course, gives an output identical to the input.

We can remove the entries from the odd rows in the identity matrix.
This is not yet a downsampling matrix. It only removes the odd
phase from the signal.

The empty rows themselves have to be removed as well. Now there are
four rows instead of eight, and also four output rows. There is a
'double shift' in the rows: the identities do not move rightward one
cell,
but two cells at a time.

Of course it is also interesting to check what downsampling does to a
waveshape. I plotted a simple 8-point cosine to illustrate that.
Downsampling basically doubles the frequency, in contrast to the
suggestion of the word.

However, double frequencies can not always be represented. When they
go over the Nyquist frequency, we get the alias. In the case below, I
started with the Nyquist frequency as the input. The output vector
represents DC.

Two such rectangular downsample matrices can be combined. They split
the input vector in two phase vectors of length N/2. This is even-odd
phase decomposition. It is an ingredient of radix 2 Fast Fourier
Transform. And because I want to know how FFT works, I am exploring
phase decomposition here.

Below is a plot of a cosine example, now downsampled into an even
and odd vector. Notice that the odd output represents the same doubled
frequency, but with a phase shift. That originates from the one-sample
shift of the odd phase in the original frequency.

The two N/2 vectors can be further decomposed. The NxN matrix must
then
contain two square N/2xN/2 matrices with two rectangular downsample
matrices each. Although the matrix looks different, the underlying
process is the same: downsampling by a factor 2.

After downsampling the eight-point vector two times with factor 2,
we now have
four two-point vectors. Theoretically, these can be downsampled one
more time, in order to get one-point vectors. Although the operation is
trivial, I have done the illustrations of it, to complete the pattern.
There is 8 small rectangular downsample matrices here. But it looks and
works exactly like the identity matrix. That's funny eh.

By the time all stages of phase decomposition are done, most
frequencies will have been pushed over the Nyquist edge in one
direction or the other. For the Fast Fourier Transform, that does no
harm. An FFT must be done with complex vectors and complex
multiplication anyway. Any real input is converted to complex
immediately. Then you have no aliases, but conjugates which keep all
positive and negative frequencies neatly separated.

When we compare the binary values of input and output numbers,
we see the famous bit-reversal which is typical for an N-point vector
decomposed into one-point vectors. This is not coincidence, nor magic. |

Sorting samples into 2 phases, is sorting to low and high bits
actually. In the first stage, the even and odd input was sorted to the
most significant output bit. In the second stage, to the second-most
significant bit. This system would work for any N=2^{x}. Below,
I indexed the row and column numbers in binary, to illustrate the idea
without further comments.

Row permutations can also be utilised for upsampling. Start from an
identity matrix again. Instead of deleting rows from the identity
matrix, we now insert empty rows. Look what such an upsampling matrix
does: an input vector is stretched to twice it's length. The empty
places between the samples in the stretched vector are supposed to be
filled with zero's.

We can combine upsample matrices to interleave two N/2 length
vectors into one N length vector:

Or we can interleave four N=2 vectors into two N=4 vectors, like
here:

But this matrix is, apart from my colours and dotted lines, exactly
the same as the 2nd stage decomposition matrix earlier on this page. I
will copy it for comparison:

What is happening? Are these processes the same? Not precisely, in
general. It took me a while to perceive the pattern, but after all it
is damn logical: the interleaving matrix is the transpose of the
corresponding decomposition matrix. You can check that in the figure
below. The rows of the decomposition matrix become columns in the
interleaving matrix. And because there is always unit vectors in each
row/column, it is exactly the inverse.

Downsampling, upsampling, phase decomposition and interleaving can
also be done with factors other than two. If only N is an integer
multiple of the factor.