# DFT and perfect reconstruction of a square wave on a digital computer

I know that in theory, when reconstructing a square wave from its Fourier coefficients, unless we have an infinite amount of them, the resulting reconstruction will have Gibbs ringing artifacts due to lack of enough harmonics.

On a computer, we can take the Fourier transform X = fft(x) of a square wave x, and reconstruct it without artifact with x_rec = ifft(X), maybe with some rounding error of the order of 1e-17 or something but no visible ringing.

I don't have a satisfying answer for that? I guess there has to be something to do with the fact the "the square wave" x is a digitized version of a continuous wave, and my Fourier basis vectors (complex exponentials are also discretized of course since we are in a computer...) but still... how would you justify the absence of Gibbs ringing artefacts from Fourier reconstruction of the Fourier transform of a digital square wave ?

%%%%%%%%%%%%%%%%%%%% Tought experiment proposed by  Dan Szabo
fs=10;%sampling frequency
t=0:(1/fs):1-(1/fs);

s = [1 1 1 1 1 0 0 0 0 0];
sTr = imtranslate(s,[0.5 0])

sTr =

0.5000    1.0000    1.0000    1.0000    1.0000    0.5000         0         0         0         0

• Not that this hasn’t been answered sufficiently, but I’d like to propose a thought experiment. What would happen if you applied a fractional delay to your digital square wave? It may help with your intuition. Jul 10 '20 at 2:10
• Thanks for proposal of the thought experiment. I m not sure but i would implement it as added to my question cf above how I would do it.. is it that what you meant? my square wave is simply [1 1 1 1 1 0 0 0 0 0] and i translated it by 0.5 Jul 10 '20 at 12:58
• but i don't see what you want to show with that? Jul 10 '20 at 13:00
• As you shift by different amounts, you will see the ringing in the Gibbs phenomenon. Jul 10 '20 at 14:19
• did I do it (cf added code) the way you intended to do it? Jul 10 '20 at 15:57

First of all, it's a misunderstanding that the Gibbs phenomenon disappears if you use infinitely many Fourier series coefficients to reconstruct a discontinuous periodic function, such as a square wave. It doesn't. The reason is that generally the Fourier series doesn't converge point-wise, but it converges in the mean, i.e.,

$$\lim_{N\to\infty}\int_{0}^{T}\left|x(t)-\sum_{k=-N}^{N}c_ke^{j2\pi kt/T}\right|^2= 0\tag{1}$$

if $$x(t)$$ is a $$T$$-periodic function, and $$c_k$$ are its Fourier coefficients.

Taking the discrete Fourier transform (DFT) of a finite sequence of numbers just corresponds to a matrix multiplication:

$$\mathbf{y}=\mathbf{Ax}\tag{2}$$

and as long as the matrix $$\mathbf{A}$$ is invertible you can compute $$\mathbf{x}$$ from $$\mathbf{y}$$:

$$\mathbf{x}=\mathbf{A}^{-1}\mathbf{y}\tag{3}$$

This has nothing to do with the Fourier series of a continuous periodic function, and it has nothing to do with the Gibbs phenomenon.

• thanks, I think it is clear for the DFT. Indeed, invertible matrix <=> lossless transform. makes sense... it is a change of basis as in linear algebra. (in fact i knew about the matrix interpretation of the DFT but my mind was kind of "clouded" when I thought about the Gibbs phenomenon.. and i didnt think to include this linear algebra concept ... frustrating sometimes that one has the tools but doesn't see how to put them together! thanks!) Jul 9 '20 at 15:05
• also: Gibbs doesn't disapear but is it very significantly reduced when N->infinity , i.e. when we have almost infinite number of harmonics ? Jul 9 '20 at 15:09
• @Machupicchu: The peaks caused by the Gibbs phenomenon become more and more narrow the more terms you use in the Fourier series, but their amplitude remains unchanged, even if the number of terms goes to infinity. Jul 9 '20 at 16:10
• By same amplitude you imply they are still significantly visible? Jul 9 '20 at 20:21
• @Machupicchu We were taught in my Real Analysis classes that this is the problem that spawned the whole field. Everything is strange, and generally counterintuitive in RA. That is why everything has to be rigorously proved from stated postulates. Heaven for the reductionist, hell for the intuitionalist. I fall in the latter category. That is the true divide in math, BTW, it is not theoretical vs applied. Synthesis vs analysis, opposite directions. Jul 9 '20 at 20:57

You can certainly create a discrete square wave and take it's FFT. However, the result will NOT be the spectrum of a square wave. Since the square wave is not band limited, you will get substantial amount of aliasing. Keep in mind that everything you represent numerically in a computer is discrete and periodic in both time and frequency.

In order to match the spectrum of the square wave, you would have to low-pass filter your time domain signal first, and that would certainly generate a lot of ringing.

• thanks for quickly answering, however my question is rather about abrupt discontinuities like a square, why don't they produce Gibbs artifacts ? Jul 9 '20 at 14:53

This is easier understood by the principles of Linear Algebra. The DFT is a lossless linear transform. The span of basis vectors is the full vector space, so it doesn't matter what your signal is, you can always reconstruct it losslessly.

Response to the last comment.

Leaving the ranges off, each is a dot product corresponding to calculating a single element of your output vector.

$$X[k] = \sum x[n] e^{-i 2\pi \frac{n}{N} k }$$

$$F(\Omega) = \int f(t) e^{-i 2\pi t \Omega }$$

In the discrete case, $$k$$ is the element index corresponding to frequency. In the continuous case $$\Omega$$ is in the frequency domain. They are both just dot products, aka inner products.

Sweep across the $$k$$s, you have a matrix multiplication. Sweep across the $$\Omega$$s, the same, only continuous.

Think of the basis vector as this:

$$g_{\Omega}(t) = e^{-i 2\pi t \Omega }$$

Then:

$$F(\Omega) = f \cdot g_{\Omega}$$

I can't make it clearer than that. Nor am I going to try.

• Oh thanks for this answer, this is helpful indeed. Please let me ask a few complementary questions. I remember and I like this way of thinking of the DFT as a matrix vector multiplication. In this context we can think of the DFT matrix as a change of basis matrix and therefore indeed lossless since its an orthogonal and unitary basis, yes? Also can so add a few works w.r.t. the continuous case, where we have the rining artifacts? In the continuous case we cannot use linear algebra, i.e. matrix vector multiplication hence ...? Jul 9 '20 at 14:57
• @Machupicchu Continuous functions do behave like vectors. This is because they are the limit case as your sampling rate approaches infinity. All the math proofs in Real Analysis are based on this. Thinking of a discrete sequence as the sampled version of a continuous function is actually the reverse of what the theory is founded on. Integration is the limit of a summation. Summations are generally not created by dirac delta train convolution of an integral. Secondly, change of basis matrices don't have to be unitary or orthogonal, just full rank so they are invertible. Jul 9 '20 at 15:31
• Ok but this notion that contiuous functions are vector is quite confusing and they cannot obviously be represented as matrices since they would need an infinite number of elements...or can they?Also, why does the Gibbs manifest itself if you say they are also vector spaces ? Jul 9 '20 at 20:19
• @Machupicchu Start with the dot product (sticking with the reals): $$f \cdot g = \int_{a}^{b} f(t) g(t) dt$$ $$\| f \| = (f \cdot f)^{1/2}$$ You can then calculate "the angle" between two functions: $$\cos(\theta) = \frac{f \cdot g }{ \| f \| \| g \| }$$ Notice any similarity to a correlation function (math and stats meaning, not engineering meaning)? Jul 9 '20 at 20:55
• Do you mean similar to the pearson correlation coefficient for two RVs X and Y?which is similar to a normalized dot product of X and Y Jul 9 '20 at 21:25