On cherche à avoir une interprétation spectrale de ce signal dont on ne connaît que \(N\) valeurs prises à des instants séparés consécutivement de \(\tau_{e}\).

Pour cela, on introduit la fréquence d'échantillonnage:

\[\nu_{e}=\frac{1}{\tau_{e}}\]

ainsi que le tableau des instants d'échantillonnage \(\left(t_{n}\right)_{n\in\left[0,N-1\right]}\) et des fréquences \(\left(\nu_{k}\right)_{k\in\left[0,N-1\right]}\) avec:

\[\boxed{\left\{ \begin{array}{l}t_{n}=n\tau_{e}\\\nu_{k}=\frac{k}{N}\nu_{e}\end{array}\right.}\]

On échantillonne donc le signal \(x\) dans l'intervalle semi-ouvert \(\left[0,\triangle t\right[\) en examinant le spectre échantillonné dans l'intervalle \(\left[0,\triangle\nu\right[\) avec:

\[\boxed{\left\{ \begin{array}{l}\triangle t=N\tau_{e}\\\triangle\nu=\nu_{e}\end{array}\right.}\]

Soit un \(X=\left(x_{n}\right)_{n\in\left[0,N-1\right]}\), où \(X\) est un vecteur de \(\mathbb{C}^{N}\).

On appelle transformée de Fourier discrète l'application linéaire:

\[DF_{N}:\left\{ \begin{array}{l}\mathbb{C}^{N}\longrightarrow\mathbb{C}^{N}\\X\longmapsto Y=DF_{N}\left(X\right)\end{array}\right.\]

avec, \(\forall k\in\left[0,N-1\right]\):

\[\boxed{Y_{k}=\hat{X}_{N}\left(k\right)=\sum_{n=0}^{N-1}x_{n}e^{-j2\pi\nu_{k}t_{n}}=\sum_{n=0}^{N-1}x_{n}e^{-j2\pi\frac{nk}{N}}}\]

et \(Y=\left[\hat{X}_{N}\left(k\right)\right]_{k\in\left[0,N-1\right]}\).

On peut imaginer introduire la fonction:

\[x_{\acute{e}ch}=\left\{ \begin{array}{ccc}x_{0} & \textrm{si} & t=0\\x_{1} & \textrm{si} & t=\tau_{e}\\ & \left(\ldots\right)\\x_{N-1} & \textrm{si} & t=\left(N-1\right)\tau_{e}\end{array}\right.\]

et nulle ailleurs.

On peut ensuite remarquer que l'on rend compte d'un l'échantillonnage fini avec la distribution \(X_{ech}\):

\[\varphi\longmapsto\left\langle X_{ech},\varphi\right\rangle =\sum_{n=0}^{N-1}x_{n}\varphi\left(n\right)\]

notée usuellement:

\[\boxed{X_{ech}\left(x\right)=\sum_{n=0}^{N-1}x_{n}\delta\left(x-n\right)}\]

On obtient alors que:

\[\hat{X}_{ech}\left(y\right)=\sum_{n=0}^{N-1}x_{n}e^{-j2\pi ny}\]

de sorte que: \[Y_{k}=\sum_{n=0}^{N-1}x_{n}e^{-j2\pi\frac{nk}{N}}=\hat{X}_{ech}\left(y_{k}=\frac{k}{N}\right)\]

s'identifie bien à une transformée de Fourier numérique d'argument \(y_{k}=\frac{k}{N}\).

Prolongeons \(Y_{k}\) à \(k\in\mathbb{Z}\).

La fonction \(k\longmapsto Y_{k}\) est \(N\)-périodique:

\[Y_{k+N}=\sum_{n=0}^{N-1}x_{n}e^{-j2\pi\frac{n\left(k+N\right)}{N}}=\sum_{n=0}^{N-1}x_{n}e^{-j2\pi\frac{nk}{N}}e^{-j2\pi n}=Y_{k}\]

ce qui signifie que l'on peut se limiter aux fréquences \(\nu\in\)\(\left(\nu_{k}=\frac{k}{N}\frac{1}{\tau_{e}}\right)_{k\in\left[0,N-1\right]}\).

C'est une grande différence avec la transformée de Fourier d'un signal continu dans l'intervalle \(\left[0,\Delta t\right]\):

\[\hat{f}\left(\nu\right)=\int_{-\infty}^{+\infty}f\left(t\right)e^{-j2\pi\nu t}dt=\int_{0}^{\Delta t}f\left(t\right)e^{-j2\pi\nu t}dt\]

qui n'est pas périodique.

Par exemple, pour \(f\) constante et égale à \(E\):

\[\hat{f}\left(\nu\right)=Ee^{-j\pi\nu\Delta t}\textrm{sinc}\left(\pi\nu\Delta t\right)\]

n'est pas périodique, contrairement à la fonction discrète \(DF_{N}\) associée à la suite constante \(X=\left(x_{n}=E\right)_{n\in\left[0,N-1\right]}\) pour laquelle il se trouve que, \(\forall k\in\left[0,N-1\right]\):

\[Y_{k}=\int_{-\infty}^{+\infty}X_{ech}\left(t\right)e^{-j2\pi\nu t}dt=\sum_{n=0}^{N-1}Ee^{-j2\pi\frac{nk}{N}}=E\frac{1-e^{-j2\pi k}}{1-e^{-j2\pi\frac{k}{N}}}=0\]

et qui est plus généralement seulement \(N\)-périodique.

Avec le prolongement précédent:

\[Y_{-k}=\sum_{n=0}^{N-1}x_{n}e^{-j2\pi\frac{n\left(-k\right)}{N}}=Y_{k}^{*}\]

Si \(X\in\mathbb{R}^{N}\) i.e. \(X\) est réel:

\[Y_{-k}=\sum_{n=0}^{N-1}x_{n}e^{j2\pi\frac{nk}{N}}=Y_{k}^{*}\]

sont complexes conjugués.

On en déduit que le domaine utile, donnant des informations indépendantes, est donné par les fréquences \(\nu\in\)\(\left(\nu_{k}=\frac{k}{N}\frac{1}{\tau_{e}}\right)_{k\in\left[0,\frac{N-1}{2}\right]}\) ou \(\nu\in\)\(\left(\nu_{k}=\frac{k}{N}\frac{1}{\tau_{e}}\right)_{k\in\left[0,\frac{N}{2}-1\right]}\) suivant la parité de \(N\).

En gros, le domaine utile de l'analyse harmonique d'un signal échantillonné réel correspond au domaine \(\boxed{\nu\in\left[0,\frac{\nu_{e}}{2}\right[}\) (avec des fréquences discrètes séparées de \(\frac{\nu_{e}}{N}\)), ce qui apparaît cohérent avec le théorème de Shannon.

La transformée de Fourier discrète admet une réciproque:

\[IF_{N}:\left\{ \begin{array}{l}\mathbb{C}^{N}\longrightarrow\mathbb{C}^{N}\\Y\longmapsto X=IDF_{N}\left(Y\right)\end{array}\right.\]

avec, \(\forall n\in\left[0,N-1\right]\):

\[\boxed{X_{n}=\hat{Y}_{N}^{-1}\left(n\right)=\frac{1}{N}\sum_{k=0}^{N-1}y_{k}e^{j2\pi\nu_{k}t_{n}}=\frac{1}{N}\sum_{k=0}^{N-1}y_{k}e^{+j2\pi\frac{nk}{N}}}\]

et \(X=\left[\hat{Y}_{N}^{-1}\left(n\right)\right]_{n\in\left[0,N-1\right]}\).

En effet:

\[I_{n}=\frac{1}{N}\sum_{k=0}^{N-1}\left(\sum_{l=0}^{N-1}x_{l}e^{-j2\pi\frac{lk}{N}}\right)e^{+j2\pi\frac{nk}{N}}=\frac{1}{N}\sum_{k=0}^{N-1}\sum_{l=0}^{N-1}x_{l}e^{+j2\pi\frac{\left(n-l\right)k}{N}}\]

En permutant les sommes:

\[I_{n}=\frac{1}{N}\sum_{l=0}^{N-1}x_{l}K_{nl}=x_{n}\]

avec:

\[K_{nl}=\sum_{k=0}^{N-1}e^{+j2\pi\frac{\left(n-l\right)k}{N}}=\left\{ \begin{array}{ccc}N & \textrm{si} & l=n\\\frac{1-e^{+j2\pi\frac{\left(n-l\right)N}{N}}}{1-e^{+j2\pi\frac{\left(n-l\right)}{N}}}=0 & \textrm{si} & l\neq n\end{array}\right.\]

Le théorème de réciprocité de Fourier prend donc ici la forme:

\[\boxed{\hat{Y}_{N}^{-1}\left(n\right)=\frac{1}{N}\hat{Y}_{N}\left(-n\right)}\]

Idéalement, s'il existe un entier \(p\) tel que:

\[\boxed{N=2^{p}}\]

(sinon on rajoute la contribution des éléments restant), l'algorithme de Cooley-Tuckey dit FFT (Fast Fourier Transform), implémenté partout, permet d'optimiser le calcul des sommes trigonométriques mises en jeu dans les transformées de Fourier discrètes (complexite en \(Np=N\log_{2}N\) au lieu de \(N^{2}\)).

On peut ainsi gérer des tableaux comportant un échantillonnage comportant un grand nombre de données.

La réciproque, i.e. l'agorithme iFFT (inverse fast Fourier Transform) est, comme attendu, de même complexité.