# Elegant way of calculating minimal sampling frequency without aliasing for annoying signals

Given a symmetric Fourier transform with finite support as below, there's an algorithmic procedure to determine the minimal frequency for sampling without aliasing:

1. Find an integer $L>1$ satisfying $f_2=L(f_2-f_1)$
2. The desired frequency $f_s$ is given by $\frac{2f_2}L$.
3. If no such $L$ exists, expand to the right or left and repeat.

The problem I was given is to find this minimal frequency for the signal below.

However, I can only manage to find the answer (which is 4) manually. Is there some algorithmic procedure again to find the answer?

• For the example you give, the support is symmetric about 3, so just recenter 3 -> 0 and apply your procedure. Asymmetric supports won't work, though. – Peter K. Jun 27 '16 at 19:44
• @PeterK. but the Fourier transform is symmetric by assumption so it seems after adding the reflection w.r.t the axis the support is not symmetric about 3 but in fact still about 0. – Arrow Jun 27 '16 at 19:47
• I am not saying reflect. I am saying shift so the origin is at the current $f=3$ location. Then your procedure should work. – Peter K. Jun 27 '16 at 20:00
• @PeterK. I understand your suggestion but do not understand why a shift would work: only the right part of the graph of $X^\text{f}(f)$ is given - the entire graph is the one I showed reflected about $0$. Hence the support of the entire graph is not symmetric about 3. This is what I meant in my previous comment. – Arrow Jun 27 '16 at 20:02
• Ah, my mistake. I thought the graph showed the whole spectrum, as the top one does. – Peter K. Jun 27 '16 at 20:05

Let me start by pointing out that for a band pass signal with a single band, there is no need for an iterative procedure. Taking your first figure as an example, in order to avoid aliasing, the sampling frequency $f_s$ must satisfy

$$\frac{2f_2}{n+1}\le f_s\le \frac{2f_1}{n}\tag{1}$$

for some integer $n$. The largest integer $n$ for which the range defined by $(1)$ is non-empty results in the smallest possible sampling frequency. This largest value of $n$ is given by

$$n_{max}=\left\lfloor\frac{f_1}{f_2-f_1}\right\rfloor\tag{2}$$

where $\lfloor\cdot\rfloor$ denotes the floor function. So you just need to determine $n_{max}$ from $(2)$ and then evaluate $(1)$ with $n=n_{max}$ to determine the possible range for $f_s$.

For multi-band signals, you usually need an iterative procedure. Let's take your second figure as an example (assuming that the spectrum is only shown for positive frequencies, and that it is symmetrical around $f=0$). Let's define $f_0=1$, $f_1=5$, and $f_2=6$. First consider the band pass component in the range $[f_1,f_2]$. From $(2)$ we get $n_{max}=5$. From $(1)$ we get the following "range" for $f_s$:

$$2\le f_s\le 2$$

Let's also evaluate the other ranges for values $n<n_{max}$:

\begin{align}n=4:&\quad 2.4\le f_s\le 2.5\\ n=3:&\quad 3.0\le f_s\le 3.3\\ n=2:&\quad 4.0\le f_s\le 5.0\\ n=1:&\quad 6.0\le f_s\le 10.0\end{align}\tag{3}

Let's now consider the low pass component. In any case, due to $f_0=1$, the minimum sampling frequency must satisfy $f_s\ge 2$. However, the aliases of the low pass component must not interfere with the band pass component. In a manner completely analogous to the single band band pass case, this leads to the following inequalities:

$$kf_s+f_0\le f_1,\quad (k+1)f_s-f_0\ge f_2$$

resulting in

$$\frac{f_0+f_2}{k+1}\le f_s\le \frac{f_1-f_0}{k}\tag{4}$$

The maximum value of $k$ for which the range defined by $(4)$ is non-empty is

$$k_{max}=\left\lfloor\frac{f_1-f_0}{2f_0+f_2-f_1}\right\rfloor\tag{5}$$

For the given values this gives $k_{max}=1$, resulting in the range

$$3.5\le f_s\le 4.0\tag{6}$$

Comparing $(3)$ and $(6)$, the only overlap is $f_s=4.0$, as you've already figured out.

Since this "overlap" is only a single frequency at the edge of two ranges, this solution is a purely theoretical one. Any imperfection in the implementation will cause aliasing. In practice, you would choose a larger sampling frequency. Considering $k=0$ in $(4)$ (meaning that the upper limit becomes infinite), we get $f_s\ge 7$. Comparing this with the ranges in $(3)$, we can conclude that a practical sampling frequency should satisfy $7+\delta<f_s<10-\delta$ with some reasonably chosen $\delta>0$.

In sum, for a signal composed of a low pass and a band pass signal (as in your example), the procedure is as follows:

• determine the maximum values $n_{max}$ and $k_{max}$ from $(2)$ and $(5)$
• determine the possible ranges for $f_s$ from $(1)$ and $(4)$ for decreasing values of $n$ and $k$, until you find overlapping ranges.

A general iterative procedure for finding the minimum sampling frequency which guarantees zero aliasing for arbitrary multi-band signals can be found in this paper.