dft - 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.

Answer

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