Vrftsjtryk

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^{-2pi 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^{2pi ikn/N}tag{2}$$

If $x_n$ is modulated (multiplied) by a unit-magnitude zero-phase complex sinusoid $e^{-2pi 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^{-2pi ikn/N}e^{-2pi ibn/N} = frac{1}{sqrt{N}} sum_{n=0}^{N-1} x_ne^{-2pi i(k+b)n/N}tag{3}$$
$$x_n = e^{2pi ibn/N}frac{1}{sqrt{N}} sum_{k=0}^{N-1} X_k(b)cdot e^{2pi ikn/N} = frac{1}{sqrt{N}} sum_{k=0}^{N-1} X_k(b)cdot e^{2pi i(k+b)n/N}tag{4}$$

Whereas DFT samples frequencies $2pi k/N,$ the frequency-shifted transform samples frequencies $2pi (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 $2pi 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 $0le 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.

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.

Symmetry and periodicity

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

$$e^{2pi ik(n+N)/N} = e^{2pi ikn/N}e^{2 pi ik} = e^{2pi ikn/N}1^k = e^{2pi ikn/N} quadtext{for all }ninmathbb{Z},,kinmathbb{Z}tag{1}$$

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

$$x_{n+N} = x_nquadtext{for all }ninmathbb{Z}tag{2}$$

The extended frequency-shifted DFT basis functions $e^{2pi 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^{2pi i(k+b)n/N}e^{2pi i(k+b)} = e^{2pi i(k+b)n/N}e^{2pi ib}quadtext{for all }ninmathbb{Z},,kinmathbb{Z}tag{3}$$

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

$$x_{n+N} = e^{2pi ib}x_nquadtext{for all }ninmathbb{Z}tag{4}$$

This seems to be called Bloch-periodicity: Each replicate equals the previous one multiplied by $e^{2pi 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