Understanding DFT-ODD operation in Gardner Efficient Convolution paper
The task is to compute the DFT of a sequence from the DFTs of its two halves:

$$X[k]=\text{DFT}_N\{x[n]\}=\sum_{n=0}^{N-1}x[n]e^{-j2\pi nk/N}$$
$$\begin{align}x_1[n]&amp;=x[n],\quad n=0,\ldots,N/2-1\\x_2[n]&amp;=x[n],\quad n=N/2,\ldots,N-1\end{align}$$
$$X_1[k]=\text{DFT}_{N/2}\{x_1[n]\},\quad X_2[k]=\text{DFT}_{N/2}\{x_2[n]\}$$

i.e., compute $X[k]$ from $X_1[k]$ and $X_2[k]$. This exact question is treated in this answer, where it is shown (cf. Eq.$(2)$) that the even indices of $X[k]$ are easily computed as

$$X[2k]=X_1[k]+X_2[k]\tag{1}$$

but where it is also shown that there is no efficient way of computing the odd indices $X[2k+1]$ from $X_1[k]$ and $X_2[k]$, even though it is of course possible, albeit inefficiently.

For this reason, in his paper, Gardner suggests another method for computing $X[2k+1]$, called "DFT-ODD", which evaluates the DFT at odd indices. First, we need two equivalent representations of $X[2k+1]$:

$$\begin{align}1.\;X[2k+1]&amp;=\text{DFT-ODD}_N\{x[n]\}=\text{DFT}_{N/2}\{(x_1[n]-x_2[n])W_N^n\}\\
2.\;X[2k+1]&amp;=\text{DFT-ODD}_{N/2}\{x[2n]\}+W_N^{2k+1}\text{DFT-ODD}_{N/2}\{x[2n+1]\}\end{align}\tag{2}$$ 

where $\text{DFT-ODD}_N\{x[n]\}$ denotes the DFT of the length $N$ signal $x[n]$ evaluated at odd indices (i.e., its length is $N/2$), and $W_N=e^{-j2\pi/N}$. The first representation is identical to the one given in the above mentioned answer, and the second one follows immediately from the definition of the DFT, after splitting the signal in its even and odd samples.

We need one more expression relating the DFT-ODD of a complex-valued sequence of length $N/2$ to the DFT-ODDs of its real and imaginary parts, respectively:

$$\begin{align}g[n]&amp;=g_R[n]+jg_I[n]\\
\text{DFT-ODD}_{N/2}\{g[n]\}&amp;=G[2k+1]=G'[k]\\
\text{DFT-ODD}_{N/2}\{g_R[n]\}&amp;=\frac12\left(G'[k]+G'^*[N/4-k-1]\right)\\
\text{DFT-ODD}_{N/2}\{g_I[n]\}&amp;=\frac{1}{2j}\left(G'[k]-G'^*[N/4-k-1]\right)\end{align}\tag{3}$$

where $*$ denotes complex conjugation.

The DFT-ODD of the original sequence $x[n]$ is now computed as follows:


generate a complex sequence from the even and odd indices of $x[n]$: $g[n]=x[2n]+jx[2n+1]$
compute DFT-ODD of $g[n]$ using representation $1$ of Eq. $(2)$: $G'[k]=\text{DFT}_{N/4}\{(g[n]-g[n+N/4])W_{N/2}^n\}$
compute the DFT-ODDs of $x[2n]$ and $x[2n+1]$ from $G'[k]$ according to Eq. $(3)$: $\text{DFT_ODD}_{N/2}\{x[2n]\}=\frac12\left(G'[k]+G'^*[N/4-k-1]\right)\\\text{DFT_ODD}_{N/2}\{x[2n+1]\}=\frac{1}{2j}\left(G'[k]-G'^*[N/4-k-1]\right)$
compute $X[2k+1]$ from these two DFT-ODDs according to the second representation in Eq. $(2)$.


This little Matlab/Octave script shows how it works:


N = 256;    % some multiple of 4
x = rand(N,1);
N2 = N/2; N4 = N/4;
x1 = x(1:N2); x2 = x(N2+1:N);
X1 = fft(x1); X2 = fft(x2);
Xeven = X1 + X2;

xe = x(1:2:N); xo = x(2:2:N); g = xe + 1i*xo;
G = fft( ( g(1:N4) - g(N4+1:N2) ) .* exp( -1i*2*pi/N2*(0:N4-1)' ) );  % DFT_odd of g
Xe = .5 * ( G + conj( G(N4:-1:1) ) );                          % DFT_odd of x[2n]
Xo = -1i*.5 * ( G - conj( G(N4:-1:1) ) );                      % DFT_odd of x[2n+1]

Xodd = [Xe;Xe] + exp(-1i*2*pi/N*(1:2:N-1)') .* [Xo;Xo];

X = [Xeven.'; Xodd.']; X = X(:);

% check result
X2 = fft(x);
max(abs(X2-X))    % 2.8422e-14