Choosing sampling frequency and base interval to eliminate leakage

Question

I'm studying for an exam and have some trouble with an exercise. So I have a continuous-time signal that is

$$s(t)=\sin(2\pi f_{s1} t) + \sin(2\pi f_{s2}t)$$ with $f_{s1} = 1.4\text{ kHz}$ and $f_{s2} = 1.45\text{ kHz}$.

After sampling the time continuous signal I'll have to get the DFT of the discrete signal. The task is to chose the sampling frequency and the base interval of the discrete signal so that there will be no leakage-effect after calculating the DFT.

I also know that $\frac{N}{\text{period}}$ has to be an integer.

How would you approach something like this? I don't expect to be spoonfed the answer, hints would be nice though.

Answer 1

Given the sum of two continuous-time sinusoidal signals as $$ x(t) = \cos( 2\pi f_1 t) + \cos(2\pi f_2 t) $$

We shall sample it at $F_s = 1/T_s$ samples per second to get the discrete-time signal as $$ x[n] = \cos( 2\pi f_1 n Ts) + \cos(2\pi f_2 n Ts) $$

We wish to get $N$ (called base length) samples of this $x(t)$ into $x[n]$ such that its $N$-point DFT will display a leakage free kronecker-delta spectrum at eaxctly those frequency bins of the added sinusoidals. Those values $N$ and $F_s$ should be found that satisfy this.

The solution is not unique; multiple sets of $N$ and $F_s$ can yield a leakege free DFT display. However some minimum $N$ can be searched. Furthermore it should be stated that a solution may not exist too; those frequencies $f_1$, $f_2$ and $F_s$ are not completely free and are bound by some simple constraints.

I'ld actually follow the usual approach and try to match DFT bins per $N$ into discrete-time frequencies per $F_s$. However, here I'll follow Cedron's approach: period matching.

From $$ x[n] = \cos( 2\pi f_1 n T_s) + \cos(2\pi f_2 n Ts) $$

the discrete-time frequencies of individual sine waves are $$ \omega_1 = \frac{2\pi f_1} {F_s} ~~~,~~~ \omega_2 = \frac{2\pi f_2}{F_s} $$

and their periods are $$ N_1 = \frac{2\pi k} {\omega_1} = \frac{F_s k}{f_1} ~~~,~~~~ N_2 = \frac{2\pi m} {\omega_1} = \frac{F_s m}{f_2}$$

where the integers $k$ and $m$ are those minimum numbers to make the periods $N_1$ and $N_2$ integers. It's seen that $F_s$ , $f_1$ and $f_2$ simultaneously make rational factors. Then the following relation happens for a given (proper) $F_s$:

$$ k F_s = N_1 f_1 \implies \frac{N_1}{k} = \frac{F_s}{f_1} ~~~, ~~~ m F_s = N_2 f_2 \implies \frac{N_2}{m} = \frac{F_s}{f_2}$$

Then the minimum integer $N_1$ and $N_2$ are found as :

$$ \boxed{ N_1 = \frac{F_s}{\text{gcd}(F_s,f_1)} = \frac{\text{lcm}(F_s,f_1)}{f_1} ~~~,~~~ N_2 = \frac{F_s}{\text{gcd}(F_s,f_2)} = \frac{\text{lcm}(F_s,f_2)}{f_2} }$$

where $\text{lcm}$ is the least common multiple.

Then the common (base) period is $$ \boxed{ N = \text{lcm}( N_1, N_2) } $$ which is the minimum number of samples taken all that's to satisfy the DFT requirement.

Note that the process claims to find the minimum integer $N$ per given $F_s$ where $F_s$ is left as an arbitrary (rational to f1,f2) number otherwise. Of course alias-free sampling requires $F_s > 2 f_{max}$. And of course the process can be extended to any number of frequencies. Below MATLAB code shows the result for just two; note the use of $R=10^r$ to make non-integer frequencies to be used.

clc; clear all; close all

f1 = 1400;      % frequency of the first cosine
f2 = 1450;      % frequency of the second cosine

Fs = 4001;      % choose (arbitrarily) a sampling frequency in Hz.

r = 0;          % set r=0 if all fk are already integers.
R = 10^r;       % Ex: if f1=1450.34 => set r = 2

N1 = lcm( R*Fs , R*f1) /(R*f1)   % period of cosine-1
N2 = lcm( R*Fs , R*f2) /(R*f2)   % period of cosine-1

% Alternatively: use GCD() function   
% N1 = R* Fs / gcd( R*Fs, R*f1)
% N2 = R* Fs / gcd( R*Fs, R*f2)

N = lcm(N1,N2)   % Find the common (base) period ; 
                 % N: min number of samples to satisfy the DFT property.

k1 = N*f1/Fs    % DFT bin index at which the delta appears.
k2 = N*f2/Fs    % Assumes no aliasing; k=0 is the first bin.

t = [0:N-1]/Fs;             % sampling instants
x = cos(2*pi*f1*t) + cos(2*pi*f2*t);


figure,subplot(3,1,1)
plot(x);title(['x[n]: , f1 = ', num2str(f1), ', f2 = ', num2str(f2), ...
               ', Fs = ', num2str(Fs), ', N1 = ', num2str(N1), ', N2 = ',...
                num2str(N2), ', N = ', num2str(N)]);
subplot(3,1,2)
stem([0:N-1],abs(fft(x,N))), xlabel('DFT index k');
subplot(3,1,3),stem(linspace(0,Fs*(1-1/N),N),abs(fft(x,N)));
xlabel('Analog Frequency [Hz]');

Running this code for $F_s = 4000$ (no-aliasing) and $F_s = 375$ (aliasing) results in the following plots.

Fs = 4000 Hz case

Fs = 375 Hz case

Answer 2

The key attribute you need to consider is for a DFT not to have leakage a sinusoidal signal must have a whole number of cycles in the sample frame. Looking at your frequencies, clearly a one second interval satisfies this criteria, but it is not the shortest interval to do so. The base interval is the shortest one that you are looking for that has a whole number of cycles for each signal.

Notice, this does not determine the sampling frequency. Your $0th$ sample and your $Nth$ sample have to occur at the same relative point in your repeat pattern. To get this, once you have found your base interval in continuous time, divide it into $N$ pieces to get your sampling frequency. Any choice of $N>1$ will work to not have leakage, but if you want the bin indexes to represent the actual frequencies and not aliases you have to select $N$ large enough so that the higher frequency signal is at or below the Nyquist frequency. Another way to say this is that you have to have at least two samples per cycle.

---

Followup:

This is the spoonfeeder version so the OP should stop reading here until they've tried to solve it using my clues themselves.

Honestly, I think Fat32's solution is a little overcomplicated, but impressive.

Let's call the two component sinusoidals Tone1 and Tone2. Tone1 has 1400 cycles in a second and Tone2 has 1450 cycles in a second. Observe:

$$ \frac{1400}{1450} = \frac{50 \cdot 28}{50 \cdot 29} = \frac{28}{29} $$

From this we can deduce that it takes Tone1 28 cycles and Tone2 29 cycles to span the base interval of $1/50$ of a second. Thus any DFT on this interval, no matter the sampling rate, will have non-zero bin values at bin 28 and bin 29 (or their aliased equivalent) and at the corresponding mirror image bins in the negative direction.

If $N \ge 29$ then it will be bins 28 and 29, otherwise you have to take modulo N to figure out the aliased bin index. In order to be below the Nyquist limit $N \ge 58$. Note that if either tone falls on the Nyquist bin (or the DC bin), the results may be zero or all the way up to the actual amplitude depending on where the sampling occurs within the sine wave. For the OP's equation, the result will be zero since the sampling will occur at the zero crossings. There still won't be any leakage.

For Fat32's first example, a samping rate of 4000Hz was used. For an interval of $1/50$ of a second it means $ N = 80 $. As per the first diagram, you can see that bins 28 and 29 are non-zero, and the mirror image bins 52(=80-28) and 51(=80-29) are also non-zero.

Fat32's second example is actually over an interval of 1/25(=15/375) of a second, so it is twice as long as the base interval. Thus Tone1 has 56 cycles in the frame and Tone2 has 58. Since N=15 in the example, aliasing does occur. The bin indexes are then 11(=56 mod 15) and 13(=58 mod 15). The mirror image bins are then 4(=15-11) and 2(15-13). Doubling the interval doubles the spacing between the bins.

Side comment: Fat32's example also shows why I prefer a $1/N$ normalized DFT. If it were used, the bin magnitudes would be $1/2$ regardless of $N$.

---

Response to Fat32's comment:

Your approach is still overly cumbersome. I think it is because you are thinking about the problem backward, and then backsolving.

Step 1. Set Sampling Rate

Step 2. Find N

Step 3. Calculate Interval length (Impicit)

For your first case:

Step 1. $F_s=4000$

Step 2. $N=80$

Step 3. $T_{frame} = 1/50 = .02$ seconds

For your second case:

Step 1. $F_s=375$

Step 2. $N=15$

Step 3. $T_{frame} = 1/25 = .04$ seconds

Clearly your second case frame interval is twice as long as your first case. Neither your 375 sample rate or the 4001 sample rate will result in an interval that is the .02 second minimum, thus the 28 and 29th bin stipulation is not applicable.

In contrast, I did it in reverse order to yours:

Step 1. Find Interval

Step 2. Set N

Step 3. Calculate Sampling Rate

The minimum frame interval for which both tones have a whole number of cycles is independent of the sampling rate. Thus, it can be found before any step into the discrete domain needs to be taken. Finding the minimum value of .02 seconds was done above and I don't think too difficult to understand. The only intervals that lead to leakage free DFTs are whole integer multiples of the minimum value. Any non-integer multiplier will lead to non-whole cycle tones.

Once an interval has been chosen, it quite easy to set the number of sample values (N) to any value you want. It has to be an integer by definition.

The DFT doesn't care about the sampling rate, it only cares about the number of samples. The sampling rate is calculated from the frame interval duration and the number of samples.

The most important concept is that the bin index (zero based, not MATLAB's stupid one based) corresponds to the number of cycles per frame. Thus, no matter what N is, as long as N is greater than 29, it will be bin 28 and 29 that have non-zero values for any DFT done on a .02 second interval of this signal. The value of N will definitely determine where the mirror image bin values are at. In your second case, since then frame interval is twice as long, the two tones will have frequencies of 56 and 58 cycles per frame respecively. So those are the bin indexes (or modulus N thereof) that will have non-zero values along with their mirror images.

All possible solutions can then be found by:

Step 1. $T_{frame} = .02 \cdot m $

Step 2. Set an $N$

Step 3. $F_s=N/T_{frame}$

Where $m$ and $N$ are integer values.

---

Response to Fat32's followup comments:

Comment 1: You are absolutely correct. Poor wording on my part. What I meant was "determined" not "constrained". I have fixed it.

Comment 2: The OP said "The task is to chose the sampling frequency and the base interval of the discrete signal so that there will be no leakage-effect after calculating the DFT." I think the salient concept behind the question is that you need to have a whole number of cycles of the constituent tones in order not to have leakage in the DFT. The sampling rate/number of samples is not important in this regard. I never called your approach wrong, just cumbersome and overly complicated.

Technically, your approach does not work for any $F_s$. Integer yes, even rational yes, but irrational no. There are an uncountable infinity worth of values that won't work compared to a mere countable infinity that will.

I think this is poorly worded: "the resulting N will take more samples than base interval minimum." Perhaps "the resulting N will take a longer interval than the minimum interval."

C3: I did cover the possibility and consequences in my answer of the bin values falling in the DC or Nyquist bins for some choices of N. Per the criteria of the problem statement, what is important is that there will still not be leakage if this happens.

I am not a MATLAB user, but I am aware of the one based indexing and am also aware that it is the most common criticism of MATLAB. If it is the tool of choice for you, fine, but arguing what is the best platform quickly devolves into a religious war and is supposed to be off-topic for SE.

SUMMARY: The problem wasn't stated in either of those ways. If either additional criteria were given then that would be a discriminant on which solution to choose. Absent that, I believe my solution demonstrates the underlying concepts clearer and definitely requires fewer calculations.