2.4  Block Transforms

Generic block processing was presented in Section 1.4. This section discusses block transforms as a specific block-oriented signal processing, including DCT, DFT, and Haar transforms, which are among the most used transforms, together with the already presented KLT (or PCA).

In many signal processing tasks, it is useful to have two related transformations called a transform pair. One transform is the inverse of the other, with the inverse undoing the forward transform. When dealing with block transforms,⁵ one simply uses linear algebra (as detailed in Appendix A.14), and both transforms are simple matrix multiplications. The pair of transforms is defined by a pair of matrices. The matrices can be rectangular, as in lapped transforms,⁶ but most block transforms are defined by a pair of $N\times N$ square matrices $\mathbf{\text{A}}$ and ${\mathbf{\text{A}}}^{-1}$ and the jargon $N$-point transform indicates their dimension. The inverse matrix ${\mathbf{\text{A}}}^{-1}$ is assumed to exist and can “undo” the transformation $\mathbf{\text{A}}$ (and vice-versa). Here, the forward (or direct) transformation is denoted as

while the inverse transformation is denoted here as

The vector $\mathbf{\text{X}}$ is called the transform of $\mathbf{\text{x}}$ and the elements of $\mathbf{\text{X}}$ are called coefficients. In this text, vectors are represented by bold lower case letters, but the vector with coefficients will be denoted by capital letters to be consistent with the jargon (unfortunately, vectors of coefficients such as $\mathbf{\text{X}}$ can be confused with matrices, but the context will distinguish them).

An important concept is:

• The columns of the inverse transform matrix ${\mathbf{\text{A}}}^{-1}$ are called the basis functions (or basis vectors).

2.4.1  Advanced: Unitary or orthonormal transforms

A matrix $\mathbf{\text{B}}$ with orthonormal columns is called unitary. The rows of a unitary matrix are also orthonormal. If one takes any pair of distinct rows or columns of the unitary matrix $\mathbf{\text{B}}$, their inner product is zero (they are orthogonal) and their norms are equal to one.

Unitary matrices are widely used in transforms because their inverse is simply the conjugate transpose as indicated in:

where $H$ denotes the Hermitian (conjugate transposition).

Considering Eq. (2.10), if the basis functions (columns of ${\mathbf{\text{A}}}^{-1}$) are orthonormal, then ${\mathbf{\text{A}}}^{-1}={\mathbf{\text{A}}}^H$. Consequently, the rows of the direct transform $\mathbf{\text{A}}$ are the complex-conjugate of the basis functions. Two important facts are:

• Forward: the $k$-th coefficient $X[k]$ of the forward transform $\mathbf{\text{X}}=\mathbf{\text{A}}\mathbf{\text{x}}$ is obtained by performing the inner product between $\mathbf{\text{x}}$ and the $k$-th basis function. Based on the definition of inner product for complex-valued vectors in Eq. (A.32), it is adopted the complex conjugate of the $k$-th basis function. The larger is this coefficient $X[k]$ magnitude, the better the $k$-th basis function represents signal $\mathbf{\text{x}}$.
• Inverse: in the inverse transform $\mathbf{\text{x}}={\mathbf{\text{A}}}^{-1}\mathbf{\text{X}}$, the column vector $\mathbf{\text{x}}$ is obtained by the linear combination of the basis functions: the $k$-th element (coefficient) in $\mathbf{\text{X}}$ multiplies the $k$-th column (basis function) of ${\mathbf{\text{A}}}^{-1}$ in a linear combination that generates $\mathbf{\text{x}}$.

Observing that the inverse of a unitary real matrix is its transpose

To get insight on why ${\mathbf{\text{B}}}^{-1}={\mathbf{\text{B}}}^H$ for a unitary $\mathbf{\text{B}}$, consider the elements of $\mathbf{\text{B}}$ are real numbers, such that ${\mathbf{\text{B}}}^H={\mathbf{\text{B}}}^T$. The result of the product ${\mathbf{\text{B}}}^T\mathbf{\text{B}}=\mathbf{\text{I}}$ is the identity matrix (that is ${\mathbf{\text{B}}}^{-1}={\mathbf{\text{B}}}^T$), because the inner product between the rows of ${\mathbf{\text{B}}}^T$ (columns of $\mathbf{\text{B}}$) with the columns of $\mathbf{\text{B}}$ is one when they coincide (main diagonal of $\mathbf{\text{I}}$) and zero otherwise (due to their orthogonality). In other words, the inner products of columns of $\mathbf{\text{B}}$ with themselves is the identity, given they are orthonormal. In case $\mathbf{\text{A}}$ is complex-valued, one has ${\mathbf{\text{A}}}^{-1}={\mathbf{\text{A}}}^H$ via a similar reasoning.

The next paragraphs present the DCT transform, which can be used for both frequency analysis and coding.

2.4.2  DCT transform

An example of a unitary matrix transform very useful for coding is the discrete cosine transform (DCT). When $N=4$, the corresponding matrices are

and

for the direct and inverse transforms, respectively.

Because they have finite duration, one can represent the input signals of block transforms as vectors or sequences. For instance, the DCT basis function corresponding to the second column of ${\mathbf{\text{A}}}^{-1}$ could be written as

Considering that the first element is $a_{0,0}$ (first index in equations is zero, not one as in Matlab/Octave), an element $a_{n,k}$ of the $N$-point inverse DCT matrix ${\mathbf{\text{A}}}^{-1}=\{a_{n,k}\}$ can be obtained by

where $w_k$ is a scaling factor that enforces the basis vectors to have unit norm, i. e., $w_k=\frac{1}{\sqrt{N}}$ for $k=0$ and $w_k=\sqrt{\frac{2}{N}}$ for $k=1,2,\dots ,N-1$.

Example 2.5. DCT calculation in Matlab/Octave. Listing 2.1 illustrates how the DCT matrices can be obtained in Matlab/Octave.

1function [A, Ainverse] = ak_dctmtx(N) 
2% function [A, Ainverse] = ak_dctmtx(N) 
3%Calculate the DCT-II matrix of dimension N x N. A and Ainverse are 
4% the direct and inverse transform matrices, respectively. Ex: 
5%  [A, Ainv]=ak_dctmtx(4); x=[1:4]'+1j; A*x, dct(x) 
6Ainverse=zeros(N,N); %pre-allocate space 
7scalingFactor = sqrt(2/N); %make base functions to have norm = 1 
8for n=0:N-1 %a loop helps to clarify obtaining inverse matrix 
9    for k=0:N-1 %first array element is 1, so use A(n+1,k+1): 
10       Ainverse(n+1,k+1)=scalingFactor*cos((pi*(2*n+1)*k)/(2*N)); 
11    end 
12end 
13Ainverse(1:N,1)=Ainverse(1:N,1)/sqrt(2); %different scaling for k=0 
14%unitary transform: direct transform is the Hermitian of the inverse 
15A = transpose(Ainverse); %Matrix is real, so transpose is Hermitian
  

The matrices obtained with ak_dctmtx.m can be used to perform the transformations but this has only pedagogical value. There are algorithms for computing the DCT that are faster than a plain matrix multiplication. Check the functions dct and idct in Matlab/Octave and scipy.fftpack.dct in Python.    $\text{□}$

Example 2.6. The DCT basis functions are cosines of distinct frequencies. Figure 2.2 shows four basis functions of a 32-points DCT transform.

Figure 2.2 indicates that, in order to represent signals composed by “low frequencies”, DCT coefficients of low order (small values of $k$ can be used), while higher order coefficients are more useful for signals composed by “high frequencies”. For example, the commands:

1N=32;k=3;n=0:N-1;x=7*cos(k*(pi*(2*n+1)/(2*N)));stem(x); X=dct(x)

return a vector X with all elements equal to zero but X(4)=28, which corresponds to $k=3$ (recall the first index in Matlab/Octave is 1, not 0). Using a larger $k$ will increase the frequency and the order of the corresponding DCT coefficient.    $\text{□}$

Example 2.7. Example of a DCT transformation. For example, assuming a 4-points DCT and $\mathbf{\text{x}}={[1,2,3,4]}^T$, the forward transform can be obtained in this case with

In this case,

where $\mathbf{\text{A}}(0,:)$ represents the first (0-th) row of matrix $\mathbf{\text{A}}$. Similarly, $X(2)$ is given by

and so on.

The previous expressions provide intuition on the direct transform. In the inverse transform, when reconstructing $\mathbf{\text{x}}$, the coefficient $X[k]$ is the scaling factor that multiplies the $k$-th basis function in the linear combination $\mathbf{\text{x}}={\mathbf{\text{A}}}^{-1}\mathbf{\text{X}}$. Still considering the 4-points DCT, the inverse corresponds to

Note that $X[2]=0$ and, consequently, the basis function $0.5{[1,-1,-1,1]}^T$ is not used to reconstruct $\mathbf{\text{x}}$. The reason is that this specific basis function is orthogonal to $\mathbf{\text{x}}$ and does not contribute to its reconstruction. As another example, the DCT coefficient $X[0]=5$ indicates that a scaling factor equals to 5 should multiply the corresponding $0$-th basis function $0.5{[1,1,1,1]}^T$ in order to reconstruct the vector $\mathbf{\text{x}}$ in time-domain.   $\text{□}$

Alternatively, the matrix multiplication can be described by a transform equation. For example, the DCT coefficients can be calculated by

and

As mentioned, the $k$-th element (or coefficient) $X[k]$ of $\mathbf{\text{X}}$ can be calculated as the inner product of $\mathbf{\text{x}}$ with the complex conjugate of the $k$-th basis function. This can be done because the DCT basis functions are orthogonal among themselves, as discussed in Section A.14.3. The factors $\sqrt{2∕N}$ and $1∕\sqrt{N}$ are used to have basis vectors with norms equal to 1. The $k$-th basis vector is a cosine with frequency $(\mathit{k\pi })∕N$ and phase $(\mathit{k\pi })∕(2N)$.

Section 2.10 discusses examples of DCT applications, including coding (signal compression). One advantage of adopting block transforms in coding applications is the distinct importance of coefficients. In the original domain, all samples (or pixels in image processing) have the same importance, but in the transform domain, coefficients typically have distinct importance. Hence, the coding scheme can concentrate on representing the most important coefficients and even discard the non-important ones. Another application of DCTs is in frequency analysis (finding the most relevant frequencies that compose a signal). But, in this application, the DFT is more widely adopted than the DCT.

2.4.3  DFT transform

As the DCT, the discrete Fourier transform (DFT) is a very useful tool to accomplish frequency analysis, where the goal is to estimate the coefficients for basis functions that are distinguished by their frequencies. The DFT is related to the discrete-time Fourier series, which also uses cosines $\text{cos}<!--\; FUNCTION\; APPLICATION\; -->\left(\frac{2\mathit{\pi nk}}{N}\right)$ and sines $\text{sin}<!--\; FUNCTION\; APPLICATION\; -->\left(\frac{2\mathit{\pi nk}}{N}\right)$, $k=0,1,\dots ,N-1$, as basis functions, and will be discussed in this chapter. While the DCT uses cosines and its matrices are real, the DFT uses complex exponentials as basis functions.

Using Euler’s formula, Eq. (A.1), complex numbers provide a more concise representation of sines and cosines and the $k$-th DFT basis function is given by

where $n=0,1,\dots ,N-1$ expresses time evolution, as for the DCT. The value $k$ determines the angular frequency ${\mathrm{\Omega }}_k=\frac{2\mathit{\pi k}}{N}$ (in radians) of the basis function $b[n]$. Eq. (2.11) can be written as

which gives the $n$-th value of the time-domain basis function $b[n]$.

Hence, one can notice that the DFT operates with an angular frequency resolution $\mathrm{\Delta }\mathrm{\Omega }=2\pi ∕N$, such that ${\mathrm{\Omega }}_k=k\mathrm{\Delta }\mathrm{\Omega }$. For instance, considering $N=4$, the resolution is $\mathrm{\Delta }\mathrm{\Omega }=2\pi ∕4=\pi ∕2$ rad and the DFT uses basis functions with angular frequencies ${\mathrm{\Omega }}_k=0,\pi ∕2,\pi$ and $3\pi ∕2$ rad. This is depicted in Figure 2.3.

When $k=2$ in Figure 2.3, the angular frequency is ${\mathrm{\Omega }}_k=\pi$ rad, and the basis function is $b[n]=\frac{1}{N}{e}^{\mathit{j\pi n}}=\frac{1}{N}{\left(e^{\mathit{j\pi }}\right)}^n=\frac{1}{N}{(-1)}^n$. The signal ${(-1)}^n$ corresponds to the highest angular frequency $\mathrm{\Omega }=\pi$ rad among discrete-time signals, and this frequency is called Nyquist frequency, as discussed in Section 1.8.3.

To complement Figure 2.3, which uses an even value $N$, Figure 2.4 describes the DFT angular frequencies when $N=5$.

As depicted in Figure 2.4, when $N$ is odd, the Nyquist frequency $\mathrm{\Omega }=\pi$ rad is not used by the DFT.

The $N$-point forward and inverse DFT pair can be written as a pair of equations. The forward (direct) transform is

which corresponds to calculating the $k$-th DFT coefficient $X[k]=⟨x[n],e^{\frac{j2\mathit{\pi nk}}{N}}⟩$ as the inner product between the time-domain signal $x[n]$ and the $k$-th basis vector of Eq. (2.11) multiplied by $N$. In this calculation, the adopted inner product for complex-valued vectors of Eq. (A.32) is responsible for Eq. (2.20) using $e^{-\frac{j2\mathit{\pi nk}}{N}}$ instead of $e^{\frac{j2\mathit{\pi nk}}{N}}$.

The inverse DFT transform equation is

Eq. (2.13) and Eq. (2.14) are the most adopted definitions of a DFT pair. But the DFT scaling factor $1∕N$ in Eq. (2.21) can be changed to $1∕\sqrt{N}$, and the same factor $1∕\sqrt{N}$ be also used in Eq. (2.13), if one wants to have a DFT pair with basis functions with unit norm. In this case the transform is called unitary DFT and has the properties already discussed in Section 2.4.1.⁷

Instead of using transform equations, sometimes it is convenient to use a matrix notation for transforms. With a matrix notation, it is easier to interpret Eq. (2.21) as composing the time-domain signal $x[n]$ as a linear combination of basis functions $(1∕N)e^{\frac{j2\mathit{\pi nk}}{N}}$ scaled by the respective coefficient $X[k]$.

To develop the matrix notation, one can observe that an element $a_{n,k}$ of the $N$-point inverse DFT matrix ${\mathbf{\text{A}}}^{-1}=\{a_{n,k}\}$ is given by

Because $n$ and $k$ appear in Eq. (2.15) as multiplication parcels, $a_{n,k}=a_{k,n}$ and the inverse DFT matrix ${\mathbf{\text{A}}}^{-1}$ is symmetric, that is ${\mathbf{\text{A}}}^{-1}={\left({\mathbf{\text{A}}}^{-1}\right)}^T$.

For the sake of comparison, when $N=4$, the inverse DCT and DFT matrices are, respectively:

The example shows that the inverse DFT matrix ${\mathbf{\text{A}}}_{\mathrm{\text{DFT}}}^{-1}$ is symmetric, while the inverse DCT matrix ${\mathbf{\text{A}}}_{\mathrm{\text{DCT}}}^{-1}$ is not. It can also be noticed that the inverse DFT matrix ${\mathbf{\text{A}}}_{\mathrm{\text{DFT}}}^{-1}$ is complex-valued, having elements that are real and imaginary. In contrast, the inverse DCT matrix ${\mathbf{\text{A}}}_{\mathrm{\text{DCT}}}^{-1}$ is real-valued. However, the first and third columns of ${\mathbf{\text{A}}}_{\mathrm{\text{DFT}}}^{-1}$ are real-valued (all elements are $+1$ or $-1$). For $N=4$, these rows correspond to $k=0$ and $k=N∕2$, which are called DC and Nyquist frequencies, respectively. All $N$ values corresponding to the basis vector of frequency $k=0$ (DC) are given by $a_{n,0}=1∕4=0.25,n=0,\dots ,N-1$, as indicated in the first column of ${\mathbf{\text{A}}}_{\mathrm{\text{DFT}}}^{-1}$. And for $N$ even, all $N$ values corresponding to the basis vector of the Nyquist frequency $k=N∕2$ (third column of ${\mathbf{\text{A}}}_{\mathrm{\text{DFT}}}^{-1}$) are given by $a_{n,N∕2}={(-1)}^n,n=0,\dots ,N-1$.

From Eq. (2.15) and adopting $N=4$, the DFT inverse matrix is given by

Note that the complex numbers $e^{j\mathrm{\Omega }}$ with angles $\mathrm{\Omega }=0,\pi ∕2,\pi$ and $3\pi ∕2$ (which is equivalent to $-\pi ∕2$) rad and magnitudes equal to 1, can be written as $1,j,-1$ and $-j$, respectively. This simplifies writing the elements of ${\mathbf{\text{A}}}^{-1}$ for $N=4$ and other values of $N$.

Example 2.8. Examples of 4-points DFT calculation. Let us calculate the 4-points DFTs of three signals represented by the column vectors $\mathbf{\text{x}}={[2,2,2,2]}^T$, $\mathbf{\text{y}}={[0,5,-5,0]}^T$ and $\mathbf{\text{z}}={[1,2,3,4]}^T$. In this case, the forward and inverse matrices can be written as

respectively. The coefficient vectors are $\mathbf{\text{X}}=\mathbf{\text{A}}\mathbf{\text{x}}={[8,0,0,0]}^T$, $\mathbf{\text{Y}}=\mathbf{\text{A}}\mathbf{\text{y}}={[0,5-j5,-10,5+j5]}^T$ and $\mathbf{\text{Z}}=\mathbf{\text{A}}\mathbf{\text{z}}={[10,-2+j2,-2,-2-j2]}^T$.

Because the basis functions (columns of ${\mathbf{\text{A}}}^{-1}$) are orthogonal, but not orthonormal, the $k$-th coefficient of the forward transform is obtained by performing the inner product between $\mathbf{\text{x}}$ and the complex conjugate of the $k$-th basis function multiplied by $N=4$.

The first basis function (corresponding to $k=0$) is always the first column of ${\mathbf{\text{A}}}^{-1}$, which in this case is ${[0.25,0.25,0.25,0.25]}^T$. Because all elements of this basis function are a constant ($0.25$ when $N=4$), the job of the respective coefficient is to represent the average value (DC level) of the input signal. After multiplication by $N=4$, the scaled basis function for $k=0$ is $[1,1,1,1]$ (first row of $\mathbf{\text{A}}$) and the corresponding coefficients in $\mathbf{\text{X}}$, $\mathbf{\text{Y}}$ and $\mathbf{\text{Z}}$ are 8, 0 and 10, respectively. This indicates that the DC level of $\mathbf{\text{x}}$, $\mathbf{\text{y}}$ and $\mathbf{\text{z}}$ are 2, 0 and 2.5, respectively.

This example also illustrates the symmetry of DFT coefficients when the input signal is real-valued. One can note that the coefficients corresponding to $k=1$ and $k=3$ are complex conjugates, while the coefficients corresponding to $k=0$ and $k=2$ (more generally, $k=N∕2$, for $N$ even) is always real-valued. In fact, because the basis functions for frequencies $k=0$ (DC) and $k=N∕2$ (Nyquist) are real-valued, if the input vector is also real-valued, these two DFT coefficients will always be real-valued (in the case $N$ is even).   $\text{□}$

The following example addresses the situation when $N$ is an odd number. In this case, the Nyquist frequency is not represented in the DFT values.

Example 2.9. Examples of 5-points DFT calculation. Let us calculate the 5-points DFTs of three signals that have five elements but are similar to the ones in the previous example: $\mathbf{\text{x}}={[2,2,2,2,2]}^T$, $\mathbf{\text{y}}={[0,5,-5,0,0]}^T$ and $\mathbf{\text{z}}={[1,2,3,4,5]}^T$. In this case, the inverse matrix can be written as

which can be written in Cartesian form using two decimal places as

When $N=5$, the DFT angular resolution is $\mathrm{\Delta }\mathrm{\Omega }=2\pi ∕5$ rad, which corresponds to $72$ degrees. To better visualize the involved angles, as a third altenative to denote ${\mathbf{\text{A}}}^{-1}$, one can use the notation $\mathit{m\angle }{𝜃}^{\circ }$ for complex values and use angles in degrees to write

Performing the direct transform, one finds that the coefficient vectors in this case are $\mathbf{\text{X}}=\mathbf{\text{A}}\mathbf{\text{x}}={[10,0,0,0,0]}^T$, $\mathbf{\text{Y}}=\mathbf{\text{A}}\mathbf{\text{y}}={[0,5.59-j1.82,-5.59-7.69j,-5.59+7.69j,5.59+j1.82,]}^T$ and $\mathbf{\text{Z}}=\mathbf{\text{A}}\mathbf{\text{z}}={[15,-2.5+3.44j,-2.5+0.81j,-2.5-0.81j,-2.5-3.44j]}^T$.

The first (DC) coefficients in $\mathbf{\text{X}}$, $\mathbf{\text{Y}}$ and $\mathbf{\text{Z}}$ are 10, 0 and 15, respectively. After division by $N=5$, one can find that the DC level (or average value) of the time-domain vectors $\mathbf{\text{x}}$, $\mathbf{\text{y}}$ and $\mathbf{\text{z}}$ are 2, 0 and 3, respectively.

This example also illustrates the symmetry of DFT coefficients when the input signal is real-valued. One can note that the coefficients corresponding to $k=1$ and $k=3$ are complex conjugates, while the coefficients corresponding to $k=0$ and $k=2$ (more generally, $k=N∕2$, for $N$ even) is always real-valued. In fact, because the basis functions for frequencies $k=0$ (DC) and $k=N∕2$ (Nyquist) are real-valued, if the input vector is also real-valued, these two DFT coefficients will always be real-valued (in the case $N$ is even).   $\text{□}$

On the symmetry of DFT coefficients when the input signal is real-valued

Assuming a DFT with $N=6$ points, Figure 2.5 indicates the angular frequency ${\mathrm{\Omega }}_k$ corresponding to each DFT coefficient $X[k]$. For instance, the DC coefficient corresponding to $k=0$ is the first element of the vector with DFT coefficients. For $N$ even, the Nyquist frequency is used and its respective coefficient is the element corresponding to $k=N∕2$.

Figure 2.6 shows a figure similar to Figure 2.5 but for a DFT with $N=5$ points. In the case of an odd value of $N$, the Nyquist frequency is not used in the DFT calculation.

Another aspect depicted by both Figure 2.6 and Figure 2.5 is that the negative frequencies are located after the positive ones in the DFT coefficients vector. The Matlab/Octave function fftshift can be used to move the negative frequencies to the first elements of this vector.

Figure 2.5 and Figure 2.6 are also useful to observe symmetries related to the DFT transform. Starting from Eq. (2.12), if we substitute the original angular frequency ${\mathrm{\Omega }}_k$ by $-{\mathrm{\Omega }}_k$, the new basis $d[n]$ is given by

Comparing $d[n]$ with Eq. (2.12), one can note that $d[n]=b^{\ast }[n]$ is the complex conjugate⁸ of the function that has frequency ${\mathrm{\Omega }}_k$. Therefore, if $X[k]=⟨x[n],b[n]⟩$, in case one changes the sign of the angular frequency of $b[n]$ from ${\mathrm{\Omega }}_k$ to $-{\mathrm{\Omega }}_k$ to obtain a new basis function $d[n]=b^{\ast }[n]$, the new coefficient $Z[k]=⟨x[n],d[n]⟩$ has the property $Z[k]=X^{\ast }[k]$ of being the complex conjugate of $X[k]$ if $x[n]$ is real-valued.

Observing Figure 2.5, the angles corresponding to $k=1$ and $k=5$ are opposites. Also, $k=2$ is the opposite of $k=4$. Therefore, the respective pairs of DFT coefficients are complex conjugates. More specifically, $X[1]=X^{\ast }[5]$ and $X[2]=X^{\ast }[4]$, when a 6-points DFT is adopted. Similarly, when assuming $N=5$ and following the mentioned reasoning, one can conclude from Figure 2.6 that $X[1]=X^{\ast }[4]$ and $X[2]=X^{\ast }[3]$.

In general, if the input signal is real-valuded one has DFT coefficients with the complex conjugate property

If $N$ is even, this is valid for $k\prime =1,\dots ,(N∕2-1)$. And if $N$ is an odd number, the range is $k\prime =1,\dots ,(N-1)∕2$. The following example illustrates this fact.

Example 2.10. Coefficients that are complex conjugates when the signal is real-valued. All the time-domain input vectors of Example 2.8 and Example 2.9 are real-valued and can be used to help studying the symmetry of the respective DFT coefficients.

In Example 2.8, the coefficient vectors are $\mathbf{\text{X}}={[8,0,0,0]}^T$, $\mathbf{\text{Y}}={[0,5-j5,-10,5+j5]}^T$ and $\mathbf{\text{Z}}={[10,-2+j2,-2,-2-j2]}^T$. Recalling that the first element has index $k=0$ (not $k=1$), it can be seen that the coefficients corresponding to $k=1$ and $k=3$ are always complex conjugates.

Similarly, in Example 2.8, the coefficient vectors are $\mathbf{\text{X}}={[10,0,0,0,0]}^T$, $\mathbf{\text{Y}}={[0,5.59-j1.82,-5.59-7.69j,-5.59+7.69j,5.59+j1.82,]}^T$ and $\mathbf{\text{Z}}={[15,-2.5+3.44j,-2.5+0.81j,-2.5-0.81j,-2.5-3.44j]}^T$, and one can observe that the coefficients corresponding to the pairs $(k=1,k=4)$ and $(k=2,k=3)$ are always complex conjugates.   $\text{□}$

The basis functions $b[n]$ for the DC and Nyquist coefficients are real-valued⁹ Hence, another property of the DFT for real-valued inputs is that $X[k]=⟨x[n],b[n]⟩$ are real-valued coefficients for $k=0$ and, in case $N$ is even, $k=N∕2$. This can be observed in the DFT coefficients discussed in Example 2.10.

Advanced: DFT and FFT denoted with the twiddle factor $W_N$

For convenience, the twiddle factor $W_N$ is defined as

such that the $k$-th basis is $(1∕N){\left(W_N\right)}^{-\mathit{nk}}$ for the conventional DFT and $(1∕\sqrt{N}){\left(W_N\right)}^{-\mathit{nk}}$ for the unitary DFT. Twiddle means to lightly turn over or around and is used because the complex number $W_N$ has magnitude equals to 1 and changes only the angle of a complex number that is multiplied by it. Each element of the inverse DFT matrix ${\mathbf{\text{A}}}^{-1}=\{a_{n,k}\}$ is

Hence, the twiddle factor $W_N=e^{-\frac{j2\pi }{N}}$ denotes the DFT angular frequency resolution $\mathrm{\Delta }\mathrm{\Omega }$.

Figure 2.7 illustrates the complex numbers $W_N$ as vectors for different values of $N$. Because $|W_N|=1$, the twiddle factor is located on the unit circle of the complex plane and effectively informs an angle. For example, the three angles used by a DFT of $N=3$ points are 0, 120 and 240 degrees, while a 4-points DFT uses 0, 90, 180 and 270.

(a) $N=3$

(b) $N=4$

(c) $N=5$

(d) $N=6$

For $N=4$, the DFT pair is given by

and

Note that ${\mathbf{\text{A}}}^{-1}\ne {\mathbf{\text{A}}}^H$ because the basis functions have norms equal to $1∕\sqrt{N}$ (the DFT matrix $\mathbf{\text{A}}$ was not defined as unitary). In this case,

Also note that the reason to have $W_N$ defined as a negative exponent in Eq. (2.17) is that the direct transform $\mathbf{\text{A}}$ uses positive powers of $W_N$. Another important fact is that ${(W_N)}^{\mathit{aN}+b}={(W_N)}^b$ for any $a\in \mathbb{Z}$. This can be seen by noting that $W_N^n$ has a period of $N$ samples and ${(W_N)}^{\mathit{aN}}=1$. Hence, the 4-points direct DFT matrix of Eq. (2.18) can be written as

It can be seen that the matrix $\mathbf{\text{A}}$ (and also ${\mathbf{\text{A}}}^{-1}$) has several symmetries that can be explored to save computations. There is a large set of algorithms for efficiently computing the DFT. These are collectively called fast Fourier transform (FFT) algorithms. Apart from numerical errors, both DFT (the plain matrix multiplication) and FFT algorithms lead to the same result. Therefore, the DFT is the name of the transform and FFT is a fast algorithm (from a large collection) used to speed up calculating the DFT. Implementing an FFT routine is not trivial but they are typically available in softwares such as Matlab/Octave.

There are FFT algorithms specialized in the case where the FFT size $N$ is a power of two (i. e., $N=2^a,a\in \mathbb{N}$). Other FFT algorithms do not present this restriction but typically are less efficient. The computational costs of DFT and FFT are quite different when $N$ grows large. The DFT matrix multiplication requires computing $N$ inner products, so the order of this computation is $O(N^2)$ while FFT algorithms achieve $O(N{\text{log}<!--\; FUNCTION\; APPLICATION\; -->}_{2}N)$. Figure 2.8 illustrates this comparison.

Instead of using matrix notation, one can use transform equations. The $N$-point DFT pair (forward and inverse, respectively) is:

and

For the unitary DFT pair, the normalization factors should be changed to:

and

2.4.4  Haar transform

In signal processing, the Haar transform is intimately related to wavelets. This section will not explore this relation nor detail the generation law of Haar matrices. The goal here is to motivate the study of wavelets by indicating how basis functions with support shorter than $N$ can be useful.

The Haar transform is unitary, such that ${\mathbf{\text{A}}}^{-1}={\mathbf{\text{A}}}^H$. The reader can use the script MatlabOctaveThirdPartyFunctions/haarmtx.m with A=haarmtx(N) to obtain the forward matrix $\mathbf{\text{A}}$. For $N=2$, the Haar, DCT and unitary DFT forward matrices are all the same:

For $N=4$, the Haar forward matrix is

Figure 2.9 and Figure 2.10 depict some Haar basis functions. The most interesting aspect is that, in contrast to DCT and DFT, some Haar functions are non-zero only at specific intervals. This characteristic allows the Haar coefficients to provide information not only about “frequency”, but also about “time” (or localization). For example, it is well-known in signal processing that Fourier transforms are better suited for stationary signals while wavelets can better represent transient signals in a time-frequency plan. This kind of behavior can already be visualized by comparing DFT (and DCT) basis with Haar’s and is explored in Application 2.2.

2.4.5  Advanced: Properties of orthogonal and unitary transforms

As commented, for transforms with unitary matrices, $X[k]$ is simply the inner product between $\mathbf{\text{x}}$ and the $k$-th basis function.¹⁰ In the inverse transform, the coefficient $X[k]$ is the scaling factor that multiplies the $k$-th basis function. This interpretation is not valid for a general non-unitary transform pair $\mathbf{\text{A}}$ and ${\mathbf{\text{A}}}^{-1}$.

The next paragraphs discuss the fact that unitary matrices do not change the norm of the input vectors. After that, the orthogonal transforms are compared to the unitary, to show that even when the norm of the basis vectors is not equal to one, the orthogonality still enables inverting a matrix using inner products.

Advanced: Unitary matrices lead to energy conservation

Another interesting property of a unitary matrix (or transform) $\mathbf{\text{A}}$ is that it does not change the norm of the input vector, that is

As indicated in Eq. (1.65), the squared norm of a vector corresponds to its energy and, consequently, a unitary matrix conserves energy when $\mathbf{\text{x}}$ is transformed into $\mathbf{\text{X}}$. The following example summarizes this result.

Example 2.11. If the transform is unitary in a coding application, the total error energies in time and frequency domains are equal. In a coding application that uses a unitary transform, the error energy in time and “frequency” domains are the same. In other words, assume that $\mathbf{\text{A}}$ is a unitary matrix and the original vector $\mathbf{\text{x}}={\mathbf{\text{A}}}^H\mathbf{\text{X}}$ is obtained from the coefficients $\mathbf{\text{X}}$. If the original coefficients $\mathbf{\text{X}}$ are encoded and represent an approximation $\widehat{\mathbf{\text{X}}}$, the error vector ${\mathbf{\text{e}}}_f=\mathbf{\text{X}}-\widehat{\mathbf{\text{X}}}$ has the same norm $||{\mathbf{\text{e}}}_f||=||{\mathbf{\text{e}}}_t||$ of the error vector in time domain ${\mathbf{\text{e}}}_t=\mathbf{\text{x}}-\widehat{\mathbf{\text{x}}}$.

To better understand this fact, one can write:

The proof above uses the reasoning adopted in Eq. (A.35).    $\text{□}$

Advanced: Orthogonal but not unitary also allows easy inversion

Orthogonal but not unitary matrices also lead to useful transforms. They do not lead to energy conservation but the coefficients are conveniently obtained by inner products, as for unitary matrices. An important detail is that when used in transforms, the inner products with the basis vectors of a orthogonal matrix must be normalized by the norms, as discussed for the DFT. This aspect is further discussed in the sequel. The term “energy” is used here instead of vector “norm” because the results are valid not only for vectors, but also for continuous-time signals, for example.

An orthogonal matrix $\mathbf{\text{B}}$ can be written as $\mathbf{\text{B}}=\mathbf{\text{A}}\mathbf{\text{D}}$, where $\mathbf{\text{A}}$ is unitary and $\mathbf{\text{D}}=\mathrm{\text{diag}}[\sqrt{E_1},\dots ,\sqrt{E_N}]$ is a diagonal matrix with the norm of the $i$-th column of $\mathbf{\text{B}}$, or square root of its energy $E_i$, composing the main diagonal. The inverse of a matrix with orthogonal columns is

Example 2.12. Inversion of orthogonal but not unitary matrix. For example, ${[3,3]}^T$ and ${[-1,1]}^T$ form a basis for ${ℝ}^2$ with energies $E_1=18$ and $E_2=2$, respectively. The matrix $\mathbf{\text{B}}=[3,-1;3,1]$ with orthogonal columns can be written as $\mathbf{\text{B}}=\mathbf{\text{A}}[\sqrt{18},0;0,\sqrt{2}]$, where $\mathbf{\text{A}}=[3∕\sqrt{E_1},-1∕\sqrt{E_2};3∕\sqrt{E_1},1∕\sqrt{E_2}]$ is orthonormal. The inverse of $\mathbf{\text{B}}$ is ${\mathbf{\text{B}}}^{-1}=[1∕\sqrt{E_1},0;0,1∕\sqrt{E_2}]A^H$ or, equivalently, ${\mathbf{\text{B}}}^{-1}=[1∕E_1,0;0,1∕E_2]B^H$.   $\text{□}$

If all columns of an orthogonal matrix $\mathbf{\text{B}}$ have the same energy $E_i=E,\forall <!--\; FUNCTION\; APPLICATION\; -->i$, its inverse is

Example 2.13. About the orthogonal (non-unitary) DFT transform. For example, in Eq. (2.11) or, equivalently, Eq. (2.20), the DFT transform was defined by an orthogonal matrix with the same energy $E=1∕N$ for all basis functions. Therefore, Eq. (2.25) leads to ${\mathbf{\text{B}}}^{-1}=N\mathbf{\text{B}}$, which is equivalent to Eq. (2.19).   $\text{□}$

The next section focuses in Fourier transforms and series. The connections with block transforms are plenty. For example, extending Eq. (2.25) for continuous-time signals, the basis functions for Fourier series, other than the one for $k=0$, have energy $E=T_0$ over the duration of a fundamental period $T_0$. Hence, the inverse transform in Eq. (2.27) has the factor $1∕T_0$.