# downsampling DFT with aliasing

(Schuam's DSP Outline, 2nd edition, problem 6.11(c), page 241).

Is there a DFT down-sampling property that looks something like this:

Given $$x[\![n]\!]_M$$ we want to downsample from M to N to obtain $$y[\![n]\!]_N$$...

$$\Bigg(y[\![n]\!]_N = x\Big[\!\Big[\ [\![n]\!]_M\ \Big]\!\Big]_N \Bigg) \xrightarrow{DFT} \left( Y[\![k[\!]_N = X\left[\!\left[ \frac{M}{N}k \right]\!\right]_M \right)$$

$$\text{for } (M > N)\ \&\ (M \ modulus\ N = 0)$$

For Example, if I downsample $$x[\![n]\!]_6$$ which was modulo 6 and convert it to modulo 3 and assign it to $$y[\![n]\!]_3$$ which is modulo 3, then it looks like this in frequency domain:

$$\Bigg(y[\![n]\!]_3 = x\Big[\!\Big[\ [\![n]\!]_6\ \Big]\!\Big]_3\Bigg) \xrightarrow{DFT} (Y[\![ k]\!]_3 = X[\![ 2k]\!]_6)$$

Is this relationship true, and is there an easier way to write this relation as a transform?

Maybe I can invent a math notation to keep my DFT table from getting to crazy:

$$\Bigg(y[\![n]\!]_N = x[\![n]\!]_{M\ to\ N} \Bigg) \xrightarrow{DFT} \left( Y[\![k[\!]_N = X\left[\!\left[ \frac{M}{N}k \right]\!\right]_M \right)$$

• There's no aliasing involved here, as far as I can tell. But maybe I'm just not understanding exactly what you want! Can you elaborate on what you want $y$ to be, compared to $x$? (Also, I feel a bit stupid because I've never seen your $[[\,]]_U$ syntax; what does it mean?) – Marcus Müller Jan 25 at 16:56
• ( $[[x]]_N = x\ modulus\ N$). I think its downsampling because X has 6 sampling points per period... y has 3 sampling points per period... it loses sampling information... thus potentially introduces sinusoidal ambiguity because information is lost … – MrCasuality Jan 25 at 18:39
• Actually, I've never seen it before either... i'm just trying to be consistent with notation used in DFT chapter of "Shaum's DSP outlines"... $x[n\ modulus\ N] = x[\![n]\!]_N$... (note: preferring "square brackets" when function is discrete-time and curled brackets when function is continuous time) – MrCasuality Jan 25 at 18:44
• You know what, then let's add that definition to your question – Marcus Müller Jan 25 at 19:00
• "(note: preferring "square brackets" when function is discrete-time and curled brackets when function is continuous time)" good idea. before the Schuam DSP outline there was Oppenheim and Schafer, and i believe that is where this very helpful notational convention came from. before that it was $x_n$ and $X_k$, but then we started to get into trouble when we had signal vectors like, in continuous time: $x_1(t), x_2(t)...$ when they were sampled, it looked horrible to have $x_{1,n}, x_{2,n}$. – robert bristow-johnson Jan 25 at 22:01

First of all very similar questions have been asked here and even I have answered some of them, but now I will provide an answer using yet another approach.

Our aim is to show the effect of down-sampling on the DFT. Let $$x[n]$$ be a sequence of length $$N$$. And let's define $$y[n]$$ by downsampling $$x[n]$$ by an integer factor $$M$$ as shown:

$$x[n] \longrightarrow \boxed{ \downarrow M } \longrightarrow y[n] = x[Mn] \tag{1}$$

$$y[n]$$ is of length $$K = N/M$$. At the moment assume $$K$$ is integer.

I will make use of the relation between DTFT $$X(\omega)$$ and DFT $$X[k]$$ for finite length sequence which states:

$$X[k] = X(\omega)|_{w = \frac{2\pi}{N}k } = X( \frac{2\pi}{N}k ) ~~~,~~~ k = 0,1,2,...,N-1 \tag{2}$$

From the theoretical DTFT definition, it can be shown that the DTFT $$Y(\omega)$$ of $$y[n]$$ is given as:

$$Y(\omega) = \frac{1}{M} \sum_{m=0}^{M-1} X( \frac{ \omega + 2\pi k}{M} ) ~~~,~~~ -\pi \leq \omega < \pi \tag{3}$$

And we define the $$K$$-point DFT of $$Y[k]$$ as:

$$Y[k] = Y(\omega)|_{\omega = \frac{2\pi}{K} k } = Y(\frac{2\pi}{K} k) ~~~,~~~ k = 0,1,...,K-1 \tag{4}$$

Note the range of DFT index $$k$$ for $$Y[k]$$. Since $$y[n]$$ is a $$K$$-point sequence we have defined a $$K$$-point DFT of it.

Finally plug Eq(4) into Eq(3)

$$Y[k] = Y(\frac{2\pi}{K} k) = \frac{1}{M} \sum_{m=0}^{M-1} X( \frac{ \frac{2\pi}{K} k + 2\pi m}{M} )$$

$$Y[k] = Y(\frac{2\pi}{K} k) = \frac{1}{M} \sum_{m=0}^{M-1} X( \frac{2\pi}{KM} k + \frac{2\pi}{M} m )$$

Now $$KM = N$$ and we replace $$\frac{2\pi}{M}$$ with $$\frac{2\pi}{N}(N/M) = \frac{2\pi}{N}K$$ to get

$$Y[k] = Y(\frac{2\pi}{K} k) = \frac{1}{M} \sum_{m=0}^{M-1} X( \frac{2\pi}{N} k + \frac{2\pi}{N} Km )$$

$$Y[k] = Y(\frac{2\pi}{K} k) = \frac{1}{M} \sum_{m=0}^{M-1} X( \frac{2\pi}{N} ( k + Km) )$$

And finally we recognize that $$X( \frac{2\pi}{N} ( k + Km) )$$ is actually the $$N$$-point DFT $$X[r]$$ of $$x[n]$$, evaluated at $$r = k + Km$$ and insert it into the equation:

$$\boxed{ Y[k] = \frac{1}{M} \sum_{m=0}^{M-1} X[ k + Km] ~~~,~~~k = 0,1,...,K-1 } \tag{5}$$

Note that DFT index k for $$Y[k]$$ is of modulo-K where as DFT index $$r = k + Km$$ for $$X[r]$$ is of modulo-N. Hence Eq(5) can alo be written like:

$$\boxed{ Y[(k)_K] = \frac{1}{M} \sum_{m=0}^{M-1} X[ (k + Km)_N] } \tag{6}$$

The following is a MATLAB/ OCTAVE code to demonstrate the result:

N = 32;        % Length of x[n]
M = 4;         % Downsampling factor (integer)
K = N/M;       % length of y[n] (assuming N divisble by M)

x = randn(1,N);     % x[n]
y = x(1:M:end);     % y[n] = x[Mn]

X = fft(x,N);       % N-point DFT X[r] of x[n]

Y = zeros(1,length(y));  % K-point DFT Y[k] of y[n]
k = 0:length(Y)-1;       % DFT index range k

for m = 0:M-1            % implements Eq.6 above
Y = Y +  X( mod(k+K*m,N)+1 );
end
Y = Y/M;

Y2 = fft(y,K);          % Comput Y[k] directly from y[n] for         checking.

figure,stem(abs(Y))     % display that they are the same..
hold on
stem(abs(Y2),'r+');