# Symmetry and periodicity of frequency-shifted discrete Fourier transform

The unitary discrete Fourier transform (DFT) of a sequence of numbers $$x_n$$ to $$X_k,$$ with integer $$0 \le n < N$$ and $$0 \le k < N,$$ can be defined as:

$$X_k = \frac{1}{\sqrt{N}} \sum_{n=0}^{N-1} x_n e^{-2\pi ikn/N}\tag{1}$$

and the inverse discrete Fourier transform (IDFT) as:

$$x_n = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} X_k e^{2\pi ikn/N}\tag{2}$$

If $$x_n$$ is modulated (multiplied) by a unit-magnitude zero-phase complex sinusoid $$e^{-2\pi ibn/N}$$ before DFT, and the IDFT output is demodulated (divided) by the same, then we get another transform pair from the family of generalized discrete Fourier transforms, parameterized by the constant $$b:$$

$$X_k(b) = \frac{1}{\sqrt{N}} \sum_{n=0}^{N-1} x_ne^{-2\pi ikn/N}e^{-2\pi ibn/N} = \frac{1}{\sqrt{N}} \sum_{n=0}^{N-1} x_ne^{-2\pi i(k+b)n/N}\tag{3}$$ $$x_n = e^{2\pi ibn/N}\frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} X_k(b)\cdot e^{2\pi ikn/N} = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} X_k(b)\cdot e^{2\pi i(k+b)n/N}\tag{4}$$

Whereas DFT samples frequencies $$2\pi k/N,$$ the frequency-shifted transform samples frequencies $$2\pi (k+b)/N.$$ This can be visualized on the Z-plane: Figure 1. Z-plane representation, showing the unit circle, of the frequencies sampled by A) DFT and B) the frequency-shifted DFT, with $$N = 12$$ and $$b = 1/3.$$ The shift $$2\pi b/N$$ appears as the angle between the real axis and the vector from origin to one of the sampled frequencies.

Question: What are the time-domain symmetry and periodicity properties of such frequency-shifted Fourier transforms when extending $$n$$ beyond $$0\le n in the inverse transform, and how does this depend on the parameter $$b?$$

For DFT (or with $$b = 0$$) the time-domain extension has period $$N$$ with no time-domain symmetry imposed by the transform.

• i just saw this question now. something about this smells like a variant of the Discrete Cosine Transform. at least if $b=\frac12$ as alluded by @Hilmar. – robert bristow-johnson Dec 19 '18 at 20:31
• @robertbristow-johnson there is a smell, but it's not the same. It's more like going from DCT-I or II to DCT-III or IV. Values other than $b = 0$ and $b=1/2$ don't seem to make much sense for real signals, because the extensions will be complex. – Olli Niemitalo Dec 19 '18 at 20:45

## 2 Answers

One version that's useful is $$b=\frac{1}{2}$$

If you have an input sequence of N real numbers, the output sequence can also be represented as N real numbers: Two for DC and Nyquist and 2*(N/2-1) for N/2-1 complex values. Mixing real and complex numbers makes real time processing a bit more awkward.

Using the transform you suggest with $$b=\frac{1}{2}$$ results in exactly N/2 complex numbers which allows for more efficient code on SIMD real time processors. $$b=\frac{1}{2}$$ maintains complex conjugate symmetry. Instead of, say, sampling -10,0,10,20,30, .. you sample at -150,50,50,150,250,... avoiding DC and Nyquist.

• Thanks, these are some things I didn't notice to ask about. – Olli Niemitalo Dec 17 '18 at 12:45
• For completeness: with $b = 1/2,$ for odd $N,$ Nyquist frequency will be included. – Olli Niemitalo Dec 19 '18 at 20:51

## Symmetry and periodicity

In standard DFT, each extended $$k$$th basis function $$e^{2\pi ikn/N}$$ is periodic with a period $$N,$$ shown by:

$$e^{2\pi ik(n+N)/N} = e^{2\pi ikn/N}e^{2 \pi ik} = e^{2\pi ikn/N}1^k = e^{2\pi ikn/N} \quad\text{for all }n\in\mathbb{Z},\,k\in\mathbb{Z}\tag{1}$$

The IDFT output $$x_n$$ (Eq. 2 of the question) extended to $$n\in\mathbb{Z},$$ is a weighted sum of the extended DFT basis functions and must thus also have the property that:

$$x_{n+N} = x_n\quad\text{for all }n\in\mathbb{Z}\tag{2}$$

The extended frequency-shifted DFT basis functions $$e^{2\pi i(k+b)n/N}$$ are not in general periodic, particularly not with period $$N.$$ However, they have the property:

$$e^{2 \pi i(k+b)(n+N)/N} = e^{2\pi i(k+b)n/N}e^{2\pi i(k+b)} = e^{2\pi i(k+b)n/N}e^{2\pi ib}\quad\text{for all }n\in\mathbb{Z},\,k\in\mathbb{Z}\tag{3}$$

The extended output of frequency-shifted IDFT has the same property:

$$x_{n+N} = e^{2\pi ib}x_n\quad\text{for all }n\in\mathbb{Z}\tag{4}$$

This seems to be called Bloch-periodicity: Each replicate equals the previous one multiplied by $$e^{2\pi ib}.$$ For $$0 \le b < 1,$$ the coefficient is complex-valued except for $$b = 0$$ for which it equals $$1$$ (regular periodity) and $$b = 1/2$$ for which it equals $$-1$$ (antiperiodicity).

There is no reversal of the replicates, unlike there is with a discrete cosine transform (DCT).

## Convolution

With frequency-shifted DFT, multiplication in the frequency domain results in Bloch-periodic convolution in time domain. For example with $$b = 1/4,$$ which gives the coefficient $$i:$$

N = 8;
b = 0.25;
x = [1 1 1 1 1 0 0 0];
m = exp(j*2*pi*b*[0:N-1]/N)
x = x./m;
fx = fft(x);
fx = fx.*fx;
x = ifft(fx);
x = x.*m


Convolving the sequence x by itself results in:

                         [1-i 2   3   4   5   4   3   2]


This can be understood as representing linear convolution of sequences:

[... -i -i -i -i -i 0 0 0 1   1   1   1   1   0   0   0 i i i i i 0 0 0 ...]
[1   1   1   1   1   0   0   0]


There is literature about symmetric convolution using variants of DCT and discrete sine transform:

• S. A. Martucci, "Symmetric convolution and the discrete sine and cosine transforms," in IEEE Transactions on Signal Processing, vol. 42, no. 5, pp. 1038-1051, May 1994. doi: 10.1109/78.295213

Also of interest: Marios Athineos's The DTT and GDFT in MATLAB