DFT can be thought as a simple change of basis. In the time domain, every sample of a signal represents its amplitude at that very instant.

\[ y\left[n\right] = \sin{\left( \frac{2\pi k }{N} n\right)} \]

\[ k = 2, N = 64\]

Nevertheless, when applying a transformation such as the DFT, every sample means something different.

The DFT is computed as the scalar product between the signal and a orthogonal base. This base is as follows:

\[ \{\boldsymbol{w}^{(k)}\}_{\{k=0,1,…,N-1\}} \]

\[ w_n = e^{j \frac{2\pi}{N}nk}\]

If some of these base vectors are plotted with the imaginary part in the Y axe and the real part in the X axe:

Real and imaginary part of the DFT basis with N=64

DFT calculation

The DFT of a signal can be computed then, applying a change of basis over the desired signal.

\[ X\left[k\right] = \sum_{n=0}^{N-1} x\left[n\right] e^{-j\frac{2\pi}{N}nk}, \text{      } k = 0,1,…,N-1 \]

DFT of a \(\delta\left[n\right]\)

\[ x\left[n\right] = \delta[n] = \left\{\begin{matrix}
1 & n = 0\\
0 & otherwise
\end{matrix}\right. \] \[X\left[k\right] = \sum_{n=0}^{N-1}{\delta\left[n\right] e^{-j\frac{2\pi}{N}nk}}\]

\[ X\left[k\right] =  1 \cdot e^{-j\frac{2\pi}{N}\cdot 0 \cdot k} = 1 \]

DFT of a cosine

\[ x\left[n\right] = 4 \cos{\left(\frac{2\pi}{4}n\right)} =  4 \cos{\left(\frac{2\pi 4}{16}n\right)} = \frac{4}{2} \left[e^{ \frac{2\pi}{16} 4n} + e^{-j \frac{2\pi}{16} 4n} \right]\]

[To be finished]
 

A vector space basis is the skeleton from which a vector space is built. It allows to decompose any signal into a linear combination of simple building blocks, namely, the basis vectors. The Fourier Transform is just a change of basis.

A vector basis is the linear combination of a set of vector that can write any vector of the space.

\[ w^{(k)} \leftarrow \text{basis} \]

The canonical basis in \(\mathbb{R}^2\) are:

\(e^{(0)} = [1, 0]^T \ \ e^{(1) } = [0,1]^T \)

Nevertheless, there are more basis for \(\mathbb{R}^2\):

\(e^{(0)} = [1, 0]^T \ \ e^{(1) } = [1,1]^T \)

This former basis is not linearly independent as information of \(e^{(0)}\) is inside \(e^{(1)}\).

Formal definition

H is a vector space.

W is a set of vectors from H such that \(W = \left\{ w^{(k)}  \right\} \)

W is a basis of H if:

  1. We can write \( \forall x \in H\): \( x = \sum_{k=0}^{K-1} \alpha_k w^{(k)}, \ \ \alpha_k \in \mathbb{C} \)
  2. \( \alpha_k  \) are unique, namely, there is linear independence in the basis, as a given point can only be expressed in a unique combination of the basis.

Orthogonal basis are those which inner product returns 0:

\( \left \langle w^{(k)}, w^{(n)} \right \rangle = 0, \ \ \text{for } k \neq n \)

In addition, if the self inner product of every basis element return 1, the basis are orthonormal.

How to change the basis?

An element in the vector space can be represented with a new basis computing the projection of the current basis in the new basis. If \(x\) is a vector element and is represented with the vector basis \(w^{(K)}\) with the coefficients \(a_k\), it can also be represented as a linear combination of the basis \(v^{(k)}\) with the coefficients \( \beta_k\). In a mathematical notation:

\[ x = \sum_{k=0}^{K-1} \alpha_k w^{(k)} = \sum_{k=0}^{K-1} \beta_k v^{(k)} \]

If \(\left\{ v^{(k)} \right\}\) is orthonormal, the new coefficients \(\beta_k\) can be computed as a linear combination of the previous coefficients and the projection of the new basis over the original one:

\[\beta_h = \left \langle v^{(h)}, x \right \rangle = \left \langle v^{(h)}, \sum_{k=0}^{K-1} \alpha_k w^{(k)} \right \rangle = \sum_{k=0}^{K-1} \alpha_k \left\langle v^{(h)}, w^{(k)} \right \rangle \]

This operation can also be represented in a matrix form as follows:

\[ \beta_h = \begin{bmatrix}
c_{00} & c_{01} & \cdots & c_{0\left(K-1 \right )}\\
& & \vdots & \\
c_{\left(K-1 \right )0} & c_{\left(K-1 \right )01} & \cdots & c_{\left(K-1 \right )\left(K-1 \right )}
\end{bmatrix}\begin{bmatrix}
\alpha_0 \\
\vdots \\
\alpha_{K-1}
\end{bmatrix} \]

This operation is widely used in algebra. A well-known example of a change of basis could be the Discrete Fourier Transform (DFT).

The inner product is an operation that measures the similarity between vectors.  In a general way, the inner product could be defined as an operation of 2 operands, which are elements of a vector space. The result is a scalar in the set of the complex numbers:

\[ \left \langle \cdot, \cdot \right \rangle : V \times V \rightarrow \mathbb{C}  \]

Formal properties

For \(x, y, z \in V\) and \(\alpha \in \mathbb{C}\), the inner product must fulfill the following rules:

To be distributive to vector addition:

\( \left \langle x+y, z \right \rangle = \left \langle x, z \right \rangle + \left \langle y, z \right \rangle \)

Conmutative with conjugate (applies when vectors are complex):

\( \left \langle x,y \right \rangle  = \left \langle y, x \right \rangle^* \)

Distributive respect scalar multiplication:

\(  \left \langle \alpha x, y \right \rangle =  \alpha^* \left \langle x, u \right \rangle \)

\(  \left \langle  x, \alpha y \right \rangle =  \alpha \left \langle x, u \right \rangle \)

The self inner product must be necessarily a real number:

\(  \left \langle  x, x \right \rangle \geq 0 \)

The self inner product can be zero only when the element is the null element:

\( \left \langle x,x \right \rangle = 0 \Leftrightarrow x = 0 \)

Inner product in \(\mathbb{R}^2 \)

The inner product in \( \mathbb{R}^2\) is defined as follows:

\( \left \langle x, y \right \rangle = x_0 y_0 + x_1 y_1 \)

In self inner product represents the squared norm of the vector:

\( \left \langle x, x \right \rangle = x^2_0 + y^2_0 = \left \| x \right \|^2 \)

Inner product in finite length signals

In this case, the inner product is defined as:

\[ \left \langle x ,y \right \rangle = \sum_{n= 0}^{N-1} x^*[n] y[n] \]

Vector spaces must meet the following rules:
Addition to be commutative:

\( x + y = y + x \)

Addition to be distributive:

\( (x+y)+z = x + (y + z) \)

Scalar multiplication to be distributive with respect to vector addition:

\( \alpha\left(x + y \right) = \alpha x + \alpha y\)

Scalar multiplication to be distributive with respect to vector the addition of field scalars:

\( \left( \alpha + \beta \right) x = \alpha x + \beta y \)

Scalar multiplication to be associative:

\( \alpha\left(\beta x \right) = \left(\alpha \beta \right) x \)

It must exist a null element:

\( \exists 0 \in V \ \ | \ \ x + 0 = 0 + x = x \)

It must exist an inverse element for every element in the vector space:

\( \forall x \in V \exists (-x)\ \ | \ \ x + (-x) = 0\)

For a signal to be periodic, it must fulfill the following condition:

\[ x[n] = x[n+M] \]
where \(M \in \mathbb{Z}\).

If \(x[n] = e^{j\left(\omega n + \phi\right)}\), then:

\[ e^{j\left(\omega n + \phi\right)} = e^{j\left(\omega \left(n+M\right) + \phi\right)}\]

\[ e^{j\omega n } e^{j\phi} = e^{j\omega n }e^{j\omega M} e^{j\phi}\]

\[ 1 =e^{j\omega M}\]

For \(e^{j \omega M}\) to be 1, the angle must be multiple of \(2\pi\). Then:

\[ \omega M = 2\pi N \]

where \( N \in \mathbb{Z}\) and \(2 \pi N\) represents any integer multiple of \(2\pi\).
Then, the frequency must meet:
\[ \omega = \frac{2\pi N}{M} \]

This is, \(\omega\) must be a rational multiple of \(2\pi\).

What does this mean?

Basically, that a periodic signal can’t take any arbitrary frequency in discrete time.

La definición de sistema discreto en el tiempo corresponde a una transformación o operador que relaciona un conjunto de valor de entrada \(x[n]\) con un conjunto de valores de salida \(y[n]\).
\[ y[n] = T\{x[n]\} \]

Sistemas sin memoria

Son aquellos en los que los valores de salida \(y[n]\) solo dependen de valores presentes de la entrada \(x[n]\). Es decir, no dependen de \(x[n-1]\), \(x[n-2]\), …
Un sistema sin memoria podría ser:
\[ y[n] = \left( x[n] \right)^2 \]

Sistemas lineales

Los sistemas lineales cumplen la propiedad de superposición. Esto significa que la salida será  igual a la suma proporcional de las entradas.

\[ T\{a\cdot x_1[n] + b\cdot x_2[n] \} = a\cdot T\{x_1[n]\} + b\cdot T\{x_[n]\} \]

Sistemas invariantes en tiempo

Un sistema invariante en el tiempo es aquel cuya salida se ve desplazada en tiempo si así lo hace la entrada. Por tanto, un desplazamiento temporal de la señal de entrada, provocará un desplazamiento en la señal de salida. De esta manera, un sistema será invariante si para todo \(n_0\), la señal \(x_1 = x[n-n_0]\) produce una señal a la salida cuyo valor se \(y_1[n] = y[n-n_0]\).

Un ejemplo de un sistema no invariante en tiempo es:
\[ y[n] = x[Mn]\]
La respuesta \(y_1[n-n_0]\) a la entrada \(x_1[n-n_0]\) es:
\[ y_1[n] = x_1[Mn] = x[Mn-n_0] \]
Como vemos, \[ y[n-n_0] = x[M(n-n_0)] \neq y_1[n] \]
Por tanto, el sistema no el invariante.

Sistemas causales

Un sistema causal es aquel que para determinar los valores de salida del sistema, solo se necesiten los valores presentes o pasados de la entrada.

Sistemas estables

Son aquellos que para cada una de las posibles entradas finitas del sistema, la salida siempre es finita. Cada una de las posibles entradas finitas del sistema significa:
\[ |x[n]| \leq B_x < \infty \] Una salida finitia signfica: \[ |y[n]| \leq B_y < \infty \]

Sistemas lineales invariantes en el tiempo

Los sistemas que son invariantes en tiempo y a la vez lineales se pueden estudiar fácilmente a través del operador convolución. De esta manera, es posible obtener cuál va a ser la salida de un sistema en función de su entrada.

Un sistema queda completamente descrito a través de su función de transferencia \(h[n]\). Esta función de transferencia es la salida que obtenemos cuando a la entrada aplicamos un impulso \(\delta[n]\).

Autofunciones en sistemas lineales invariantes

Como hemos visto, los sistemas lineales invariantes son de especial interés debido a que tienen ventajas sobre los sistemas no lineal o no invariantes y es que se puede describir mediante su respuesta impulsional.

Por propiedades de la función \(\delta [n]\), es posible describir la secuencia \(x[n]\) como:
\[ x[n] = \sum_{k=-\infty}^{+\infty} x[k]\cdot \delta[n-k] \]

De este modo, al aplicar la secuencia \(x[k]\) a la entrada de un sistema, su salida será:
\[ y[n] =  T\left\{x[n] \right\} = T\left\{\sum_{k=-\infty}^{+\infty} x[k]\cdot \delta[n-k] \right\} =\sum_{k=-\infty}^{+\infty} x[k]\cdot  T\left\{ \delta[n-k] \right\} \]

Si identificamos la transformación del tren de deltas \( T\left\{ \delta[n-k] \right\}\) como su respuesta impulsional \(h[n]\), obtenemos lo que se conoce como su ecuación de convolución:
\[ y[n] =  \sum_{k=-\infty}^{+\infty} x[k]\cdot  h[n-k] \]

Como ya se explicó en otra entrada, las autofunciones son útiles para la caracterización de sistemas. Las autofunciones son aquellas que al aplicarse en la entrada de un sistema, su salida es la misma que la función de la entrada multiplicada por una constante. Es decir, si \(x[n]\) es una autofunción de \(y[n]\):

\[ y[n] =  T\left\{x[n] \right\} = a \cdot x[n]  \]

donde \(a\) es una constante.

Una de las autofunciones de los sistemas invariantes es la exponencial compleja \(x[n] = z^n\) donde \(z\) es un número complejo cualquiera. Esta función es autofunción de cualquier sistema lineal invariante ya que:
\[ y[n] = \sum_{k=-\infty}^{+\infty} z^{n-k} h[k] = z^n\sum_{k=-\infty}^{+\infty} z^{-k} h[k]   \]

Si esta serie converge, ya que el sumatorio no depende de \(n\), \(y[n]\) puede escribirse como:
\[ y[n] = H(z) z^n\]

Este es lo mismo que decir que si a la entrada de un sistema lineal invariante se aplica una secuencia exponencial \(z^n\), a la salida se obtiene la misma secuencia multiplicada por una constante. Por tanto, queda demostrado que las exponenciales complejas \(z^n\) son autofunciones de un sistema lineal invariante cuyos autovalores están determiandos por:
\[ H(z) =  \sum_{k=-\infty}^{+\infty} z^{-k} h[k] \]

Si se interpreta \(z\) como una variable, \(H(z)\) es una función compleja de variable independiente compleja que se conoce como función de transferencia y describe el comportamiento del sistema frente a cualquier entrada.

Sistemas definidos por ecuaciones en diferencias finitas

Los sistemas discretos se pueden caracterizar, además de por su respuesta impulsional, por ecuaciones en diferencias finitas lineales con coeficientes constantes. Una ecuación en diferencias finitas lineal con coeficientes constantes corresponde a:
\[ \sum_{k=0}^P a_k y[n-k] = \sum_{k=0}^{Q} b_k x[n-k] \]
donde \(x[n]\) es una dato (ya que es la secuencia de entrada), \(y[n]\) es la incógnita de la ecuación y \(a_k\) y \(b_k\) son los coeficientes independientes de \(n\). El orden de la ecuación corresponde al mayor entre \(P\) y \(Q\).

No obstante, si se describe un sistema mediante ecuaciones en diferencias finitas, este no queda totalmente caracterizado debido a la falta de información sobre el estado del sistema antes de aplicar ninguna secuencia a la entrada. Es por eso, que para poder determinar cuál será la salida del sistema a una determinada secuencia, es necesario conocer también las condiciones iniciales del sistema. Por ejemplo, en el sistema que define un sumador:
\[ y[n] = x[n] + y[n-1]\]
si se le aplica una secuencia constante \(x[n] = 1\) para \(n\geq 0\), el valor de \(y[0]\) será:
\[ y[0] = x[0] + y[-1] = 1 + y[-1] \]
Solo se podrá determinar el valor de \(y[0]\) si conocemos \(y[-1]\). Normalmente, el sistema se supone que estaba en reposo y que las condiciones iniciales son \(y[n] = 0\) para \(n<0\). De esta manera, \(y[0] = 1\)
\subsubsection{Sistemas recurrentes y no recurrentes}

Los sistemas recurrentes son aquellos que proporcionan valores de \(y[n]\) en función de valores de la propia salida calculados anteriormente. Es decir:
\[ y[n] = \frac{1}{a_0}\left( \sum_{k=0}^{Q} b_k x[n-k] – \sum_{k=1}^{P} a_k y[n-k]  \right) \]

Si la salida \(y[n]\) solo depende de los valores presentes y pasados de \(x[n]\), o lo que es lo mismo, P = 0, el sistema es no recurrente.

\[ y[n] = \sum_{k=0}^{Q} \frac{b_k}{a_0} x[n-k] \]

Respuesta impulsional

Para obtener la respuesta impulsional de un sistema lineal invariante definido por diferencias finitas, basta con aplicar a la entrada la secuencia exponencial \(x[n] = z^n\). Como hemos visto, esta secuencia es autofunción del sistema y por tanto la salida será:
\[ y[n] = H(z) z^n \]

\(H(z)\) no tiene por qué existir siempre ya que el sumatorio que lo define debe converger.

Un sistema lineal invariante definido por ecuaciones de diferencias finitas, como hemos visto, corresponde a la ecuación:

\[ \sum_{k=0}^P a_k y[n-k] = \sum_{k=0}^{Q} b_k x[n-k] \]

Al sustituir \(x[n]\) e \(y[n]\) en la ecuación, se obtiene:
\[ \sum_{k=0}^P a_k H(z)z^{n-k} = \sum_{k=0}^{Q} b_k z^{n-k} \]

\(H(z)\) no depende de k, por lo que puede salir fuera del sumatorio.

\[ H(z) \sum_{k=0}^P a_k z^{n-k} = \sum_{k=0}^{Q} b_k z^{n-k} \]

Si despejamos \(H(z)\) obtenemos:

\[ H(z) = \frac{\sum_{k=0}^{Q} b_k z^{n-k}}{\sum_{k=0}^P a_k z^{n-k}} = \frac{\sum_{k=0}^{Q} b_k z^{-k}}{\sum_{k=0}^P a_k z^{-k}} \]

Por tanto, la función de transferencia de un sistema caracterizado por una ecuación en diferencias finitas es un cociente de polinomios en \(z^{-1}\) cuyos coeficientes son directamente los coeficientes de la ecuación.

Por ejemplo, si queremos diseñar un sistema de orden 2 no recurrente que cancele un tono a la frecuencia \(\omega_0 = \frac{\pi}{4}\), la ecuación en diferencias finitas debe seguir la siguiente expresión:
\[ y[n] = \sum_{k=0}^Q b_k x[n-k] \]

ya que el sistema es no recurrente. Por ser de orden 2, \(Q=2\). Por tanto, queda calcular los coeficiente \(b_k\).

La entrada del sistema será:
\[ x[n] = \cos{\left(\frac{\pi}{4}n\right)} = \frac{1}{2} \left( e^{j \frac{\pi}{4} n} + e^{-j \frac{\pi}{4} n} \right) \]

Debido a la fórmula de Euler (\(e^{jx} = \cos{x} + j \sin{x}\)), la entrada puede escribirse como combinación lineal de dos exponenciales. Como se ha demostrado, este tipo de funciones son autofunciones del sistema lineal invariante y por tanto la salida será:
\[ y[n] = \frac{1}{2} e^{j \frac{\pi}{4} n} H\left(e^{j \frac{\pi}{4}} \right) + \frac{1}{2} e^{-j \frac{\pi}{4} n} H\left(e^{-j \frac{\pi}{4}} \right)  \]

Para cancelar un tono a esta frecuencia la salida debe ser nula, \( y[n] = 0\). Esto ocurre si:
\[ H\left(e^{j \frac{\pi}{4}} \right) = H\left(e^{-j \frac{\pi}{4}} \right) = 0\]

La función de transferencia \(H(z)\) será:
\[ H(z) = \sum_{k=0}^{Q=2} b_k z^{-k}\]
ya que \(P = 0\) por ser un sistema no recurrente.

Podemos desarrollar \(H(z)\) como:
\[H(z) = b_0 + b_1 z^{-1} + b_2 z^{-2} \]

Esta expresión se puede escribir como un producto de raíces y es equivalente a:
\[ H(z) = b_0 \prod_{i=0}^1 \left(1-z_i z^{-1}\right) = b_0 \left( 1 -z_0 z^{-1}\right) \left(1-z_1 z^{-1} \right)  \]

donde \(z_0 = e^{j \frac{\pi}{4}}\) y \(z_1 = e^{-j \frac{\pi}{4}}\).

Podemos identificar ambas expresiones si desarrollamos este producto:
\[ H(z) = b_0 \left(1 + \left(-z_0-z_1\right) z^{-1} + z_0 z_1 z^{-2} \right) \]

El término \(b_0\) solo determina la ganancia del sistema y puede valer simplemente 1. Por tanto:
\[ b_0 = b_0 = 1\]
\[ b_1 = -z_0 -z_1 = -e^{j \frac{\pi}{4}}-e^{-j \frac{\pi}{4}} = 2\cdot \cos{\frac{\pi}{4}} = \sqrt{2}\]
\[ b_2 = z_0 z_1 = e^{j \frac{\pi}{4}}\cdot e^{-j \frac{\pi}{4}} = 1\]

Finalmente, \(H(z)\) queda como:
\[ H(z) = 1 +  \sqrt{2}z^{-1} + z^{-2} \]

y:

\[ y[n] = 1 + \sqrt{2} z^{-1} + z^{-2} \]