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

\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 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. 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. Dec 19 '18 at 20:45
• Gosh, Olli. I didn't see this one go by either. I will look into it and may include the b =1/2 in my version of the FFT (I'm calling it QFT, quick) I have in my to do pile. The other values won't have the root symmetries where the calculation savings come from. (I'm also including range specifications in the input range and output range to save further calculations, built in zero padding, and optional window function evaluation as the first step for each sample.) Aug 20 '20 at 11:50
• "The Fractional Fourier Transform and Applications" David H. Bailey and Paul N. Swarztrauber, October 19, 1995, Ref: SIAM Review , vol. 33 no. 3 (Sept. 1991), pg. 389 Note, this is not the same "Fractional" as is commonly used. Aug 20 '20 at 12:25

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. Dec 17 '18 at 12:45
• For completeness: with $b = 1/2,$ for odd $N,$ Nyquist frequency will be included. 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