Kotelnikov's theorem

Kotelnikov's theorem (also known as the sampling theorem or the Nyquist–Shannon theorem) is a fundamental statement in signal theory that defines the condition for accurately reconstructing a continuous signal from its discrete samples.

If there is a continuous signal it has a limited spectrum (i.e. it contains only frequencies in the range from before ), then it can be accurately reconstructed from its samples taken with frequency:

where:

— sampling rate (sampling rate),
— the maximum frequency in the signal spectrum.

What you should pay attention to:

Nyquist frequency is the minimum sampling frequency at which accurate signal recovery is possible:

If , there is spectrum overlap (aliasing), and the signal cannot be restored without distortion.
The signal is restored using the Kotelnikov series (interpolation formula):

where:

- the interval between counts,

Verification of the basic condition of the theorem

Let's simulate a "continuous" signal (in fact, the same discrete signal, but with very densely spaced samples, and then we will "digitize" it:

using DSP;
fs0 = 10000;                    # Завышенная частота дискртизации для отображения "аналогового" сигнала
dt0 = 1/fs0;                    # Шаг временной сетки
endtime = 0.04;                 # Конечный момент времени
t0 = 0:dt0:endtime-dt0;         # Вектор отсчётов времени (временная сетка)
Fmax = 100;                    # Основная частота синусоидального сигнала в Гц
analog = cos.(2*pi*Fmax*t0);   # Синусоидальный "непрерывный" сигнал для "оцифровки"

A discrete signal that obviously satisfies the condition of Kotelnikov's theorem:

fs1 = 10 * Fmax;               # Частота дискретизации сигнала, удовлетворяющая теореме Котельникова    
dt1 = 1/fs1;
t1 = 0:dt1:endtime-dt1;         
stem1 = cos.(2*pi*Fmax*t1);    # Дискретный сигнал (отсчёты непрерывного сигнала)
plot(t0, analog, linewidth=4, label="Непрерывный")
plot!(t1, stem1, line=:stem, marker=:circle, linewidth=2, label="ЧД = 1000 Гц")

Now let's create a signal that satisfies the condition in the limiting case ():

fs2 = 2 * Fmax;
dt2 = 1/fs2;
t2 = 0:dt2:endtime-dt2;
stem2 = cos.(2*pi*Fmax*t2);
plot(t0, analog, linewidth=3, label="Непрерывный")
plot!(t2, stem2, line=:stem, marker=:circle, linewidth=3, label="ЧД = 200 Гц")

Finally, let's check what the "digitized" signal looks like if the condition of Kotelnikov's theorem is not fulfilled.:

fs3 = 1.5 * Fmax;
dt3 = 1/fs3;
t3 = 0:dt3:endtime-dt3;
stem3 = cos.(2*pi*Fmax*t3);
plot(t0, analog, linewidth=4, label="Непрерывный")
plot!(t3, stem3, line=:stem, marker=:circle, linewidth=3, label="ЧД = 150 Hz")

Let's check the possibility of restoring the signal from fs = 200 Гц. To do this, we will have to add zeros between the samples of the discrete signal, and then pass it through the forming low-pass filter.:

upsampled_stem2_chunk = [1; zeros(49); -1; zeros(49)];
upsampled_stem2 = repeat(upsampled_stem2_chunk, 4);
plot(t0, analog, linewidth=4, label="Непрерывный")
plot!(t0, upsampled_stem2, line=:stem, marker=:circle, linewidth=3, label="ЧД = 200 Гц, с нулями")

Let's simulate signal recovery using a digital low-pass filter (DAC model):

myfilt = digitalfilter(Lowpass(2*110/fs0), Elliptic(4, 0.01, 60));
H, w = freqresp(myfilt);
freq_vec = fs0*w/(2*pi);
plot(freq_vec, pow2db.(abs.(H))*2, linewidth=3,
     xlabel = "Частота, Гц",
     ylabel = "Амплитуда, дБ",
     title = "АЧХ фильтра нижних частот")

Let's display the signal at the output of the DAC:

DAC = filt(myfilt, upsampled_stem2);
plot(t0, analog, linewidth=4, label="Непрерывный")
plot!(t0, DAC * 25, linewidth=4, label="Выход ЦАП")

We have seen that even in the extreme case of observing the condition of the theorem, the restoration of the form is possible.

Aliasing in case of non-compliance with the condition of Kotelnikov's theorem

We visualize the effect of "superimposing" samples of a signal with a higher fundamental frequency onto samples of a signal with a lower frequency. The discrete samples "belong" to both signals, but after sampling we will see only a lower frequency signal.:

tvec = 0:0.01:10;
x1 = cos.(pi/5*tvec);
x2 = cos.(11*pi/5*tvec)
plot(tvec,x2, linewidth=3, label = "Исходный сигнал")

tnew = 0:10;
y1 = cos.(11*pi/5*tnew)
plot!(tnew,y1, line=:stem, marker=:circle, linewidth=3, label = "Дискретизация")
plot!(tvec,x1, linewidth=4, label = "Наложение", title = "Наложение, сигнал с частотой в 11 раз меньше")

If aliasing has already occurred, it is useless to deal with it using any post-processing methods. It is necessary to prevent its occurrence by choosing the sampling frequency correctly and using anti-aliasing filters.

Now let's evaluate the aliasing effect using the example of an audio signal. Add an auxiliary function for listening to audio:

using WAV
using Base64

function audioplayer(s, fs);
    buf = IOBuffer();
    wavwrite(s, buf; Fs=fs);
    data = base64encode(unsafe_string(pointer(buf.data), buf.size));
    markup = """<audio controls="controls" {autoplay}>
                <source src="data:audio/wav;base64,$data" type="audio/wav" />
                Your browser does not support the audio element.
                </audio>"""
    display("text/html", markup);
end

By changing the position of the slider, you can move from the "zone" of compliance with the condition of the theorem to the zone of non-compliance. In the rightmost position, at BH = 3000 Hz, the signal with a fundamental frequency of 2250 Hz is audibly indistinguishable from the signal with a frequency of 750 Hz.:

var_fs = 3000 # @param {type:"slider",min:3000,max:5000,step:500}

freq1 = 750;
freq2 = 1500;
freq3 = 2250;

timevec = 0:1/var_fs:1 - 1/var_fs;

sig1 = cos.(2*pi*freq1*timevec);
sig2 = cos.(2*pi*freq2*timevec);
sig3 = cos.(2*pi*freq3*timevec);

audioplayer(sig1,var_fs)
audioplayer(sig2,var_fs)
audioplayer(sig3,var_fs)

Conclusion

We got acquainted with the basics of Kotelnikov's theorem, which is widely used in digital signal processing (audio, video, telecommunications) and in the design of analog-to-digital converters (ADCs). To prevent aliasing, antialiasing filters are used before sampling, suppressing frequencies above .

By the way, the theorem was independently discovered:

In 1927 ** by Vladimir Kotelnikov** (USSR).
In 1928 ** By Harry Nyquist** (USA).
Later generalized by Claude Shannon in 1949.

In Western literature, it is often called the Nyquist–Shannon theorem, but in the Russian-speaking tradition, the name has been fixed. Kotelnikova.