Symmetry and periodicity of frequency-shifted discrete Fourier transform

Question

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:$

$$ \begin{aligned} 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} \end{aligned} \tag{3} $$

$$ \begin{aligned} 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} \end{aligned} \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<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.

Answer 1

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.

Answer 2

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