Efficient Maximum Likelihood Algorithm for Estimating Carrier Frequency Offset of Generalized Frequency Division Multiplexing Systems

Abstract

This study presents a computationally efficient maximum likelihood (ML) algorithm for estimating the carrier frequency offset (CFO) of generalized frequency division multiplexing systems. The proposed algorithm uses repetitive subsymbols and virtual carriers to estimate the fractional and integer CFOs, respectively. Through the use of repetitive subsymbols, this study first calculates the ML estimate of the fractional CFO in the time domain and then, accordingly, compensates for it from the received signal. The integer CFO can then be estimated through a virtual-carrier-mapping process in the frequency domain. In addition to improving performance in terms of estimation accuracy and computational complexity, the proposed non-data-aided algorithm is spectrally efficient relative to traditional algorithms.

1. Introduction

Frequency synchronization is critical to communication systems when carrier frequency bias between communication terminals severely affects data transmission [1,2]. Carrier frequency offset (CFO) is caused by the Doppler effect for moving terminals and by frequency differences among the local oscillators of transmitters and receivers. The accuracy of the local oscillator is usually in the order of parts-per-million (ppm) of the carrier frequency. Therefore, CFO inevitably increases when communication bands move toward high-frequency slots. For example, in fifth-generation (5G) systems, a 5 ppm CFO in the 52 GHz millimeter wave (mmWave) band is 260 KHz; this is much greater than that in the 2.8 GHz sub-6 GHz band, in which a 5 ppm CFO is 14 KHz. Because of large amounts of available unused spectrum, mmWave bands have been proposed for use in the development of future communication systems; they provide high data transmission rates, ultralow latency, and high connectivity services [3]. The necessity of being able to overcome a large CFO for frequency synchronization techniques is, thus, a key problem warranting investigation.

Generalized frequency division multiplexing (GFDM) is a multicarrier modulation technique that uses overlapping subcarriers to transmit information. GFDM uses a filter bank to shape the waveform, resulting in a smoother frequency spectrum and improved spectral efficiency. Additionally, GFDM can support non-contiguous and flexible spectrum allocation, making it suitable for 6G communications, where spectrum availability is expected to be limited. GFDM also offers improved spectral efficiency, lower out-of-band radiation, and better resistance to frequency-selective fading channels [4,5,6].

For GFDM, the CFO increases intercarrier interference (ICI) among subcarriers. This degrades system performance, especially in the case of a large CFO [7,8]. Several frequency synchronization methods have been developed for GFDM systems [9,10,11,12,13,14]. Li et al. employed identical consecutive training signal blocks to derive the CFO estimator on the basis of the least square (LS) criterion [9]. The LS-based algorithm in [9] is robust and has a large frequency estimation range. However, the involved matrix inversion operation of the large-sized training matrix leads to high computational complexity. In [10], Shayanfar et al. used a Zadoff–Chu (ZC) pilot signal [11] to simplify the cost function in [9]. Because of the orthogonality of the ZC sequences, the algorithm in [9] substantially mitigates the computational complexity from the absence of the associated matrix inversion. Na et al. [12] presented a pseudo-noise-based algorithm to estimate the CFO under the maximum likelihood (ML) criterion. The drawback of the algorithm in [12] is that the CFO acquisition region is limited to a single subcarrier space; this limits its practical applications. All the algorithms in [9,10,11,12] format the preamble symbol into two identical subsymbols and use a preamble of high dimension for the search process; this considerably increases computational complexity. In [13], a subspace-based algorithm was proposed to estimate the CFO and the channel response through a two-stage process. In [14], Wang et al. employed a fast Fourier transform (FFT)-transformed ZC sequence as a training signal to construct a GFDM preamble with a quasi-periodic structure in the time domain, and they then estimated the CFO from the root of the characteristic polynomial. The orthogonality of the ZC sequence allowed the algorithm in [14] to generate the associated null subspace matrix by circularly shifting the ZC sequence and, therefore, greatly mitigating the computational complexity. To the best of our knowledge, all the CFO estimation algorithms for GFDM systems are data-aided approaches; therefore, a training sequence is required to form a preamble in front of each GFDM data frame, resulting in reduced spectral efficiency.

Some CFO estimation algorithms developed for orthogonal frequency division multiplexing (OFDM) systems can be extended to GFDM systems [15,16,17,18,19,20,21]. Gaspar et al. proposed a method to estimate the CFO in OFDM systems that combines the preamble symbol with a windowing process to enhance spectral efficiency by reducing the out-of-band (OOB) radiation of the transmitted signal [16]. Wang et al. [17] modified the CFO estimation algorithm in [18] and presented an ML estimator that used the average power of the received signal to estimate the covariance structure induced by the overlapping spectral feature of the GFDM signal. Both the algorithms in [15,17] have a limited CFO acquisition range to one subcarrier space, restricting their realistic application. Hui et al. [19] proposed a subspace-based algorithm in which null subcarriers were employed, and FFT vectors corresponding to the null subcarriers were used to form the subspace bases for the CFO estimation. Ruan et al. developed an ML CFO estimator for practical OFDM systems that uses a preamble comprising of repetitive subsymbols in the time domain [20]. The guard subcarriers in the frequency domain were used to alleviate the complexity of the algorithm, and the CFO estimate was obtained through a three-stage process: (1) fractional CFO coarse estimation, (2) integer CFO estimation, and (3) fraction CFO refinement. A similar algorithm to [20] has been developed by Shayanfar [10] for the CFO estimation in the GFDM system, in which the employed ZC-sequence greatly reduced the computational complexity because of the avoidance of the matrix inversion in the determination of the cost function. Bölcskei employed the cyclostationarity of the filtered OFDM signal to achieve time–frequency synchronization [21]. This cyclostationarity-based algorithm can resolve a full-band coverage of frequency bias and an arbitrary length of symbol timing acquisition regions through a weighted subcarrier precoding scheme.

This study proposes an ML algorithm to estimate the CFO of the GFDM system by using virtual carriers (VCs) and repeated subsymbols. The CFO presented in this paper is normalized to the subcarrier space and is expressed by the sum of the fractional and integer CFOs. The repetitive subsymbols cause the received signal to reveal a fractional CFO-bearing quasi-periodic structure between consecutive subsymbols. This feature enables the proposed algorithm to derive the ML estimates of the fractional CFO in the time domain. Accordingly, the proposed algorithm compensates for the fractional CFO from the received signal. Subsequently, the proposed algorithm combines the resultant subsymbols to reduce the noise power and then employs a virtual-carrier-mapping (VCM) process to estimate the integer CFO in the frequency domain. The VCM allows the proposed algorithm to resolve a CFO over the frequency band covered by all subcarriers. Additionally, increasing the number of subsymbols and subcarriers can boost the signal-to-noise-power ratio (SNR) of the received signal and, thus, improve the estimation accuracy of the proposed algorithm. In contrast to conventional algorithms that use a dedicated training symbol to facilitate the estimation, the proposed algorithm has no training signal and thus has better spectral efficiency. Additionally, the proposed algorithm demonstrates considerably lower computational complexity and higher estimation accuracy when compared with conventional algorithms.

Section 2 introduces the GFDM system model. Section 3 presents the proposed CFO estimation algorithm that uses repetitive subsymbols and VCs. Computer simulation results illustrating the effectiveness of the proposed algorithm are included in Section 4. A conclusion is provided in Section 5.

2. System Model

GFDM modulates data symbols into signal blocks through the use of subcarriers and subsymbols. The subcarriers are filtered with a prototype filter that is circularly shifted in the time and frequency domains. This process reduces OOB radiation and makes dynamic spectrum allocation feasible without severe interference among subscribers [4]. Figure 1 illustrates the generation of the GFDM signals comprising K subcarriers and M subsymbols.

Incorporated with the prototype filter, a time shifter of response $h_m\left[n\right]=\delta \left[n-mK\right]$ is employed to generate a modulating signal of the subsymbol. A frequency shifter is then used to modulate each subsymbol with the subcarrier. All the signal components in the time–frequency slots are combined, and the transmitted signal block is given by

$$x\left[n\right]={\displaystyle \sum _{k=0}^{K-1}{\displaystyle \sum _{m=0}^{M-1}{d}_{k,m}g\left[\left(n-mK\right)\mathrm{mod}N\right]e^{j\frac{2\pi }{K}kn}},n=0,\cdots ,N-1},$$

(1)

where $g\left[n\right]$ denotes the impulse response of the prototype filter employed by the GFDM system of K subcarriers and M subsymbols, $N=MK$ is the size of the GFDM signal block, which represents the amount of data symbols delivered in a signal block and $d_{k,m}$ denotes the data symbol modulated by the $m^{\mathrm{th}}$ subsymbol and $k^{\mathrm{th}}$ subcarrier.

In the frequency domain, performing an N-point FFT on $x\left[n\right]$ yields

$$X_{k^{\prime }}={\displaystyle \sum _{k=0}^{K-1}{\displaystyle \sum _{m=0}^{M-1}{d}_{k,m}{G}_{k^{\prime }-kM}{e}^{-j\frac{2\pi }{M}{k}^{\prime }m}}, k^{\prime }=0,\cdots ,N-1},$$

(2)

where $X_{k^{\prime }}$ and $G_{k^{\prime }}$ denote the ${k^{\prime }}^{\mathrm{th}}$ spectral component of $x\left[n\right]$ and $g\left[n\right]$, respectively, indicating that each subcarrier of the GFDM signal covers a bandwidth of M bins corresponding to the N-point FFT transformation. This is M times over that of the OFDM signals. Additionally, the overlapped portions of $\left\{G_{k^{\prime }-kM},\forall k\right\}$ leads to ICI among subcarriers, making GFDM a nonorthogonal modulation. Typical prototype filters of GFDM possess an adjustable spectral spread in the frequency domain [4,22]. This can be expressed by

$$G_k=\left\{\begin{array}{l}{G}_{N-k}^{*},k=1,\cdots ,⌊\alpha M⌋\hfill \\ 0, \mathrm{otherwise}\hfill \end{array}\right.$$

(3)

where the asterisk denotes a complex conjugate, $⌊\cdot ⌋$ is the floor operation, and $\alpha$ is the roll-off factor controlling the overlapped spectral portion between adjacent subcarriers.

With (1), a cyclic prefix (CP) of a length longer than that of the channel response is added in front of each GFDM signal block to avoid interblock interference. At the receiver, after the removal of the CP and inclusion of the influence of the CFO, the received signal is obtained by

$$y\left[n\right]=\left(x\left[n\right]\otimes h\left[n\right]\right)e^{-j\frac{2\pi }{K}\epsilon n}+z\left[n\right]=y_{\mathrm{s}}\left[n\right]+z\left[n\right]$$

(4)

where $\otimes$ denotes the circular convolution, $h\left[n\right]$ is the channel impulse response (CIR), $\epsilon$ is the CFO normalized to the subcarrier space of the GFDM signal, $z\left[n\right]$ is the additive white Gaussian noise with zero mean and variance ${\sigma }_z^2$, and $y_{\mathrm{s}}\left[n\right]=\left(x\left[n\right]\otimes h\left[n\right]\right)e^{-j\frac{2\pi }{K}\epsilon n}$ denotes the signal part of the received signal.

3. Proposed Approach

This study represents the CFO as the sum of the integer and fractional CFOs, $\epsilon ={\epsilon }_{\mathrm{i}}+{\epsilon }_{\mathrm{f}}$, where the integer CFO falls in the range of $-\frac{K}{2}<{\epsilon }_{\mathrm{i}}\le \frac{K}{2}$, and the fractional CFO in $\left|{\epsilon }_{\mathrm{f}}\right|\le \frac{1}{2}$. The proposed algorithm first uses repetitive subsymbols to estimate the fractional CFO and then accordingly compensates for it from the received subsymbols. The fractional CFO compensation shifts the data modulated at each subcarrier by the integer CFO. The proposed algorithm then combines all the subsymbols to reduce noise and then uses the VCM to search for the integer CFO.

3.1. ML Estimate of the Fractional CFO

To estimate the fractional CFO, the proposed algorithm sets the data symbols in (1) identical for all subsymbols: $d_{k,m}=d_k,\forall m$. Additionally, to estimate the integer CFO, the proposed algorithm selects some subcarriers as the VCs, given by

$$d_k=0, \forall k\in S_{\mathrm{VC}},$$

(5)

where $S_{\mathrm{VC}}$ is the set of VC indices. Accordingly, the spectral component in (2) becomes

$$\begin{array}{ll}{X}_{k^{\prime }}& ={\displaystyle \sum _{k=0}^{K-1}{d}_k{G}_{k^{\prime }-kM}{\displaystyle \sum _{m=0}^{M-1}{e}^{-j\frac{2\pi }{M}{k}^{\prime }m}}, }\\ & =M{\displaystyle \sum _{k=0}^{K-1}{d}_k{G}_{\left(l-k\right)M}\delta \left[k^{\prime }-lM\right], }{k}^{\prime }=0,\cdots ,N-1, \mathrm{and} l=0,\cdots ,K-1\end{array}$$

(6)

where $\delta \left[k^{\prime }\right]$ is the Kronecker delta function that takes 1 when $k^{\prime }=0$, and 0 otherwise. The controlled spectral spread feature in (3) shows that $G_{\left(l-k\right)M}=G_0\delta \left[l-k\right]$, and (6) becomes

$$X_{k^{\prime }}=M{d}_l{G}_0\delta \left[k^{\prime }-lM\right].$$

(7)

Accordingly, performing an N-point inverse FFT (iFFT) on (7) yields

$$x\left[n\right]=\frac{1}{\sqrt{N}}{\displaystyle \sum _{k^{\prime }=0}^{N-1}{X}_{k^{\prime }}{e}^{j\frac{2\pi }{N}{k}^{\prime }n}}=\sqrt{M}{G}_o\tilde{d}\left[n\right],$$

(8)

where $\tilde{d}\left[n\right]=\frac{1}{\sqrt{K}}{\displaystyle \sum _{l=0}^{K-1}{d}_l{e}^{j\frac{2\pi }{K}ln}}$ is the K-point iFFT of the data symbols ${\left\{d_k\right\}}_{k=0,\cdots ,K-1}$. This shows that $x\left[n\right]$ is a periodic time sequence of period K given by

$$x\left[n\right]=x\left[mK+n\right], \mathrm{for} n=0,\cdots ,K-1, \mathrm{and} m=0,\cdots ,M-1.$$

(9)

Accordingly, the received signal $y_{\mathrm{s}}\left[n\right]$ in (4) reveals a fractional CFO-bearing quasi-periodic structure given by

$$\begin{array}{ll}{y}_{\mathrm{s}}\left[mK+n\right]& ={\displaystyle \sum _{l=0}^{L-1}h\left[l\right]x\left[mK+n-l\right]e^{-j\frac{2\pi }{K}\epsilon \left(mK+n\right)}},\\ & =\underset{y_{\mathrm{s}}\left[n\right]}{\underbrace{{\displaystyle \sum _{l=0}^{L-1}h\left[l\right]x\left[n-l\right]e^{-j\frac{2\pi }{K}\epsilon n}}}}{e}^{-j2\pi {\epsilon }_{\mathrm{f}}m}\end{array}$$

(10)

$$=y_{\mathrm{s}}\left[n\right]e^{-j2\pi {\epsilon }_{\mathrm{f}}m}, \mathrm{for} n=0,\cdots ,K-1, \mathrm{and} m=0,\cdots ,M-1,$$

(11)

where L is the length of the channel response.

To estimate the fractional CFO, the proposed algorithm uses the real and imaginary components of each received time sample to define the signal vector

$$y_{m,n}=\left[\begin{array}{c}{y}_{m,n}^{\mathrm{R}}\\ y_{m,n}^{\mathrm{I}}\end{array}\right], \mathrm{for} m=0,\cdots ,M-1 \mathrm{and} n=0,\cdots ,K-1,$$

(12)

where $y_{m,n}^{\mathrm{R}}=\mathrm{Re}\left\{y\left[mK+n\right]\right\}$ and $y_{m,n}^{\mathrm{I}}=\mathrm{Im}\left\{y\left[mK+n\right]\right\}$ denote the real and imaginary parts of the $n^{\mathrm{th}}$ sample of the $m^{\mathrm{th}}$ subsymbol in (4). Because of (11), the relationship between $y_{m,n}$ and $y_{m-1,n}$ can be expressed by

$$y_{m,n}=R\left({\epsilon }_{\mathrm{f}}\right)y_{m-1,n}+{\overline{z}}_{m,n},$$

(13)

where $R\left({\epsilon }_{\mathrm{f}}\right)$ is a rotational matrix given by

$$R\left({\epsilon }_{\mathrm{f}}\right)=\left[\begin{array}{cc}\cos 2\pi {\epsilon }_{\mathrm{f}}& \sin 2\pi {\epsilon }_{\mathrm{f}}\\ -\sin 2\pi {\epsilon }_{\mathrm{f}}& \cos 2\pi {\epsilon }_{\mathrm{f}}\end{array}\right],$$

(14)

and ${\overline{z}}_{m,n}=\left[\begin{array}{c}{\overline{z}}_{m,n}^{\mathrm{R}}\\ {\overline{z}}_{m,n}^{\mathrm{I}}\end{array}\right]$ denotes the composited noise vector with ${\overline{z}}_{m,n}^{\mathrm{R}}$ and ${\overline{z}}_{m,n}^{\mathrm{I}}$ being independent and identically distributed Gaussian random variables with zero mean and variance ${\sigma }_z^2$. Therefore, conditioned on $y_{m-1,n}$ and ${\epsilon }_{\mathrm{f}}$, the density function of $y_{m,n}$ can be expressed by

$$f\left(y_{m,n}\left|y_{m-1,n},{\epsilon }_{\mathrm{f}}\right.\right)=\frac{1}{\pi {\sigma }_z^2}{e}^{-\frac{{‖y_{m,n}-R\left({\epsilon }_{\mathrm{f}}\right)y_{m-1,n}‖}^2}{2{\sigma }_z^2}},$$

(15)

where $‖ \cdot ‖$ denotes the vector norm. With the received signal vectors $\left\{y_{m,n},\forall m,n\right\}$, the chain rule of the joint density function yields

$$\begin{array}{ll}f\left(\left\{y_{m,n},\forall m,n\right\}\left|{\epsilon }_{\mathrm{f}}\right.\right)& ={\displaystyle \prod _{n=0}^{K-1}{\displaystyle \prod _{m=0}^{M-1}f\left(y_{m,n}\left|y_{m-1,n},{\epsilon }_{\mathrm{f}}\right.\right)}}\\ & =\frac{1}{{\left(\pi {\sigma }_z^2\right)}^{N-1}}{e}^{-{\displaystyle \sum _{n=0}^{K-1}{\displaystyle \sum _{m=0}^{M-1}\frac{{‖y_{m,n}-R\left({\epsilon }_{\mathrm{f}}\right)y_{m-1,n}‖}^2}{2{\sigma }_z^2}}}},\end{array}$$

(16)

Accordingly, the log-likelihood function for estimating the fractional CFO is then given by

$$L\left({\epsilon }_{\mathrm{f}}\right)={\displaystyle \sum _{n=0}^{K-1}{\displaystyle \sum _{m=0}^{M-1}{‖y_{m,n}-R\left({\epsilon }_{\mathrm{f}}\right)y_{m-1,n}‖}^2}}.$$

(17)

To determine the ML estimate of the fractional CFO, setting the gradient of $L\left({\epsilon }_{\mathrm{f}}\right)$ to zero yields

$$\frac{d}{d{\epsilon }_{\mathrm{f}}}L\left({\widehat{\epsilon }}_{\mathrm{f}}\right)={\displaystyle \sum _{n=0}^{K-1}{\displaystyle \sum _{m=0}^{M-1}{y}_{m-1,n}^T{\dot{R}}^T\left({\widehat{\epsilon }}_{\mathrm{f}}\right)y_{m,n}-y_{m,n}^T\dot{R}\left({\widehat{\epsilon }}_{\mathrm{f}}\right)y_{m-1,n}}}=0,$$

(18)

where

$$\dot{R}\left({\widehat{\epsilon }}_{\mathrm{f}}\right)=2\pi \left[\begin{array}{cc}-\sin 2\pi {\epsilon }_{\mathrm{f}}& \cos 2\pi {\epsilon }_{\mathrm{f}}\\ -\cos 2\pi {\epsilon }_{\mathrm{f}}& -\sin 2\pi {\epsilon }_{\mathrm{f}}\end{array}\right].$$

(19)

Substituting (12) and (19) into (18) yields

$$\begin{array}{l}{\displaystyle \sum _{n=0}^{K-1}{\displaystyle \sum _{m=0}^{M-1}\left(y_{m-1,n}^{\mathrm{R}}{y}_{m,n}^{\mathrm{R}}+y_{m-1,n}^{\mathrm{I}}{y}_{m,n}^{\mathrm{I}}\right)\sin 2\pi {\widehat{\epsilon }}_{\mathrm{f}}}}\\ ={\displaystyle \sum _{n=0}^{K-1}{\displaystyle \sum _{m=0}^{M-1}\left(y_{m-1,n}^{\mathrm{R}}{y}_{m,n}^{\mathrm{I}}-y_{m-1,n}^{\mathrm{I}}{y}_{m,n}^{\mathrm{R}}\right)\cos 2\pi {\widehat{\epsilon }}_{\mathrm{f}}}}.\end{array}$$

(20)

Accordingly, the ML estimate is obtained by

$${\widehat{\epsilon }}_{\mathrm{f}}=\frac{1}{2\pi }{\tan }^{-1}\frac{{\displaystyle \sum _{n=0}^{K-1}{\displaystyle \sum _{m=0}^{M-1}\left(y_{m-1,n}^{\mathrm{R}}{y}_{m,n}^{\mathrm{I}}-y_{m-1,n}^{\mathrm{I}}{y}_{m,n}^{\mathrm{R}}\right)}}}{{\displaystyle \sum _{n=0}^{K-1}{\displaystyle \sum _{m=0}^{M-1}\left(y_{m-1,n}^{\mathrm{R}}{y}_{m,n}^{\mathrm{R}}+y_{m-1,n}^{\mathrm{I}}{y}_{m,n}^{\mathrm{I}}\right)}}},$$

(21)

$$=\frac{1}{2\pi }{\tan }^{-1}\frac{{\displaystyle \sum _{n=0}^{K-1}{\displaystyle \sum _{m=0}^{M-1}\mathrm{Im}\left(y^{*}\left[mK+n\right]y\left[\left(m-1\right)K+n\right]\right)}}}{{\displaystyle \sum _{n=0}^{K-1}{\displaystyle \sum _{m=0}^{M-1}\mathrm{Re}\left(y^{*}\left[mK+n\right]y\left[\left(m-1\right)K+n\right]\right)}}}$$

(22)

3.2. Integer CFO Estimation

According to the fractional CFO estimate, the proposed algorithm compensates for it from the received signal, yielding an integer-CFO-distorted signal given by

$$\tilde{y}\left[n\right]=y\left[n\right]e^{j\frac{2\pi }{K}{\widehat{\epsilon }}_{\mathrm{f}}n}={\tilde{y}}_{\mathrm{s}}\left[n\right]+\tilde{z}\left[n\right],$$

(23)

where ${\tilde{y}}_{\mathrm{s}}\left[n\right]={\displaystyle \sum _{l=0}^{L-1}h\left[l\right]x\left[n-l\right]e^{-j\frac{2\pi }{K}{\epsilon }_{\mathrm{i}}n}}$ is the signal part of $\tilde{y}\left[n\right]$ and $\tilde{z}\left[n\right]$ is the resultant noise. This shows that ${\tilde{y}}_{\mathrm{s}}\left[n\right]$ distorts $y_{\mathrm{s}}\left[n\right]$ through a phase rotation that translates data symbols at each subcarrier by ${\epsilon }_{\mathrm{i}}$ in the frequency domain. With (8), ${\tilde{y}}_{\mathrm{s}}\left[n\right]$ can be expressed by

$${\tilde{y}}_{\mathrm{s}}\left[n\right]=\sqrt{\frac{M}{K}}{\displaystyle \sum _{l=0}^{K-1}{G}_0{H}_l{d}_{l+{\epsilon }_{\mathrm{i}}}{e}^{j\frac{2\pi }{K}nl}}={\tilde{y}}_{\mathrm{s}}\left[n+mK\right],$$

(24)

where $H_l$ denotes the frequency response of the channel at subcarrier l. Accordingly, the proposed VCM process estimates the integer CFO in the frequency domain by finding the displacement of the VCs. The proposed algorithm forms subsymbol vectors by

$${\overline{y}}_m=\left[\begin{array}{c}{\tilde{y}}_{\mathrm{s}}\left[mK\right]\\ ⋮\\ {\tilde{y}}_{\mathrm{s}}\left[\left(m+1\right)K-1\right]\end{array}\right]={\overline{y}}_{\mathrm{s}}+{\overline{z}}_m, m=0,\cdots ,M-1$$

(25)

where ${\overline{y}}_{\mathrm{s}}={\left[\begin{array}{ccc}\tilde{y}\left[0\right]& \cdots & \tilde{y}\left[K-1\right]\end{array}\right]}^T$ is the resultant signal vector that is identical for all subsymbols and ${\overline{z}}_m$ is the associated noise vector. Specifically, from (24), ${\overline{y}}_{\mathrm{s}}$ can be expressed through the iFFT and is given by

$${\overline{y}}_{\mathrm{s}}=\sqrt{M}{F}_K{\overleftrightarrow{d}}^{\left[{\epsilon }_{\mathrm{i}}\right]},$$

(26)

where $F_K={\left[W_{k,l}\right]}_{K\times K}$ is the K-point iFFT matrix with $W_{k,l}=\frac{1}{\sqrt{K}}{e}^{j\frac{2\pi }{K}kl}$, and ${\overleftrightarrow{d}}^{\left[{\epsilon }_{\mathrm{i}}\right]}$ represents the resultant data vector obtained by circularly shifting the original vector ${\overleftrightarrow{d}}^{\left[0\right]}={\left[\begin{array}{ccc}{G}_0{H}_0{d}_0,& \cdots ,& G_0{H}_{K-1}{d}_{K-1}\end{array}\right]}_{K\times 1}^T$ by ${\epsilon }_{\mathrm{i}}$ times. The subcarrier translation allows the VCM to estimate the integer CFO by locating the displacement of the VC pattern. According to (10), the proposed algorithm first combines all subsymbol vectors to enhance the signal strength and form,

$$\overline{y}=\frac{1}{M}{\displaystyle \sum _{m=0}^{M-1}{\overline{y}}_m}={\overline{y}}_{\mathrm{s}}+\overline{z},$$

(27)

where $\overline{z}$ is the resultant noise vector with covariance matrix $\frac{1}{M}{\sigma }_z^{2}I$. Next, the proposed VCM conducts a K-point FFT on $\overline{y}$ yielding

$$\stackrel{⌣}{y}=F_K^H\overline{y}=\sqrt{M}{\overleftrightarrow{d}}^{\left[{\epsilon }_{\mathrm{i}}\right]}+\stackrel{⌣}{z},$$

(28)

where the superscript ${}^H$ denotes the Hermitian operation and $\stackrel{⌣}{z}$ is the noise vector in the frequency domain. According to the set of VC indices in (5), the VCM defines a VC position vector given by

$${\overleftrightarrow{p}}^{\left[0\right]}={\left[p_k\right]}_{K\times 1},$$

(29)

where the $k^{\mathrm{th}}$ element $p_k=1$, if $k\in S_{\mathrm{VC}}$, and $p_k=0$, otherwise. The cost function for estimating the integer CFO is then defined by

$$P\left[k\right]=‖{\Psi }_k\stackrel{⌣}{y}‖,-\frac{K}{2}\le k<\frac{K}{2},$$

(30)

where ${\Psi }_k=diag\left\{{\overleftrightarrow{p}}^{\left[k\right]}\right\}$ is the searching matrix with ${\overleftrightarrow{p}}^{\left[k\right]}$ denoting the circular shift of ${\overleftrightarrow{p}}^{\left[0\right]}$ by k times. The VCs in (5) make the cost function minimum when $k={\epsilon }_{\mathrm{i}}$ and, therefore, the integer CFO estimate can be obtained by searching over subcarriers with $P\left[k\right],$ and it is given by

$${\widehat{\epsilon }}_{\mathrm{i}}=\arg {\min }_{k}P\left[k\right].$$

(31)

In conclusion, the proposed algorithm (Algorithm 1) can be summarized as follows:

Algorithm 1: The proposed algorithm
Step 1:	According to (5)–(8), generate the GFDM signal block comprising identical subsymbols.
Step 2:	Use (22) to estimate the fractional CFO, ${\widehat{\epsilon }}_{\mathrm{f}}$, from the received signal block.
Step 3:	Use (23) to compensate for the fractional CFO from the received signal, and then use (25) and (27) to form the average subsymbol vector $\overline{y}.$
Step 4:	Use (28)–(31) to find the integer CFO estimate ${\widehat{\epsilon }}_{\mathrm{i}}.$
Step 5:	The resultant CFO estimate is: $\widehat{\epsilon }={\widehat{\epsilon }}_{\mathrm{i}}+{\widehat{\epsilon }}_{\mathrm{f}}.$

Remark 1.

In step 1, the system can achieve better spectral efficiency if the selection of VCs in $S_{\mathrm{VC}}$ covers the subcarriers experiencing deep-faded channel responses. However, without knowing the channel, the proposed algorithm determines the $S_{\mathrm{VC}}$ in a random manner.

Remark 2.

From (8), the power of the transmit signal in step 1 is

$$E\left\{{\left|x\left[n\right]\right|}^2\right\}=M\left|G_0\right|\left(K-\left|S_{\mathrm{VC}}\right|\right){\sigma }_d^2,$$

(32)

where ${\sigma }_d^2=E\left\{{\left|d_k\right|}^2\right\}$ is the variance of the data symbol and $\left|S_{\mathrm{VC}}\right|$ is the size of $S_{\mathrm{VC}}$. Accordingly, the SNR of the received symbol vector $\stackrel{⌣}{y}$ is given by

$$SNR\left(\stackrel{⌣}{y}\right)=M\frac{{\displaystyle \sum _{k\notin S_{\mathrm{VC}}}{\left|G_0\right|}^2{\left|H_k\right|}^2{\sigma }_d^2}}{{\sigma }_z^2},$$

(33)

which is proportional to both the number of the subsymbols M and the number of payloads $K-\left|S_{\mathrm{VC}}\right|,$ rendering the proposed algorithm beneficial for a power gain in the CFO estimation.

Remark 3.

The SNR can be improved by increasing either M or K, but as indicated in (22), the proposed algorithm uses $\left(M-1\right)K$ time samples of $y\left[n\right]$ to estimate the fractional CFO. Therefore, for a fixed $N=MK,$ increasing M provides more time samples to the proposed algorithm than increasing K. This achieves better estimation accuracy in the fractional CFO estimation at the expense of spectral efficiency.

Remark 4.

This study calls the inverse of the cost function of the VCM in (30) the pseudospectrum, which can help to identify the integer CFO estimate by means of a peak in its amplitude response.

3.3. Computational Complexity Analysis

The proposed algorithm requires $\left(N-K\right)$ flops in the estimation of the fractional CFO in (22) and $K\log K$ flops for the K-point FFT in (28), plus $K\left|S_{\mathrm{VC}}\right|$ flops for the VCM process of the integer CFO estimation in (31). Therefore, in total, the computational complexity of the proposed algorithm is $\left(N-K\right)+K\left|S_{\mathrm{VC}}\right|+K\log K.$ By comparison, the algorithm presented in [14] requires $\left(N-K\right)+\left(2K-1\right){\left(\log \left(2K-1\right)\right)}^2$ flops for the CFO estimation, whereas the computational complexity of the method in [10] is $LN\left(\frac{N}{2}+10\left(4\left(L-1\right)+3\right)+21q\right)$, where q is the exponent of the associated fine-grid-searching process. In addition, the computational complexity of the method in [9] is $\frac{11}{6}{N}^3+\frac{4}{3}{N}^2+L^{2}N.$ 

Table 1. Computational complexities of different methods.

Algorithms	Computational Complexity (Flops)
The algorithm in [9]	$\frac{11}{6}{N}^3+\frac{4}{3}{N}^2+L^{2}N$
The algorithm in [10]	$LN\left(\frac{N}{2}+10\left(4\left(L-1\right)+3\right)+21q\right)$
The algorithm in [14]	$\left(N-K\right)+\left(2K-1\right){\left(\log \left(2K-1\right)\right)}^2$
The proposed algorithm	$\left(N-K\right)+K\left|S_{\mathrm{VC}}\right|+K\log K$

summarizes the complexities of these algorithms.

The method in [9] entails using high-dimensional matrix inversion to estimate the CFO, which entails a substantially larger computation burden compared with that of the proposed algorithm, in which the ML estimate of the fractional CFO and the VCM of the integer CFO estimation require considerably fewer computations. In addition, in contrast with the other algorithms in Table 1 that employ a preamble signal block, the proposed algorithm uses repetitive subsymbols incorporating VCs to estimate the CFO. This makes it more spectrally efficient than the others.

4. Computer Simulations

Consider a GFDM system comprising $M=2$ subsymbols and $K=32$ subcarriers where a root-raised-cosine filter [23] is employed as the prototype filter with a roll-off factor $\alpha =0.35,$ and the response is given by

$$g\left[n\right]=\left\{\begin{array}{l}\frac{1}{MK}\left(1+\alpha \left(\frac{4}{\pi }-1\right)\right),n=0\\ \frac{\alpha }{MK\sqrt{2}}\left[\left(1+\frac{2}{\pi }\right)\sin \left(\frac{\pi }{4\alpha }\right)+\left(1-\frac{2}{\pi }\right)\cos \left(\frac{\pi }{4\alpha }\right)\right],n=\pm \frac{MK}{4\alpha }\\ \frac{\sin \left(\pi \frac{n}{MK}\left(1-\alpha \right)\right)+4\alpha \frac{n}{MK}\cos \left(\pi \frac{n}{MK}\left(1+\alpha \right)\right)}{\pi n\left[1-{\left(4\alpha \frac{n}{MK}\right)}^2\right]}, \mathrm{otherwise}\end{array}\right.$$

(34)

The channel length is $L=5$, and the delay power profile of a Rayleigh fading channel is expressed by

$${\sigma }_l^2=E\left\{{\left|h\left[l\right]\right|}^2\right\}=e^{-\frac{l}{\kappa }}, l=0,\cdots ,L-1$$

(35)

where $\kappa$ denotes the path loss coefficient and is set as $\kappa =6.$ The channel response is assumed to be constant over the time duration of a GFDM signal block. The number of the VCs is set to $\left|S_{\mathrm{VC}}\right|=\beta K$ where $\beta =0.2$ is the VC percentage factor, and the noise power ${\sigma }_z^2$ is adjusted to achieve the specified SNR. In computer simulations, the mean square error (MSE) of the CFO is defined as

$$MS{E}_{\epsilon }=\frac{1}{N_t}{\displaystyle \sum _{n=1}^{N_t}{\left|\widehat{\epsilon }\left(n\right)-\epsilon \right|}^2}$$

(36)

where $N_t$ is the number of Monte Carlo trials and $\widehat{\epsilon }\left(n\right)$ is the CFO estimate in trial n.

Figure 2 presents the results of the comparison of the MSE of the proposed CFO estimate with that of the LS method developed by Li et al. [9], the ZC-sequence-aided algorithm of Shayanfar et al. [10], and the polynomial-rooting-based algorithm of Wang et al. [14]. The CFO is randomly selected from the interval $\left[-\frac{K}{2},\frac{K}{2}\right)$. Figure 2 demonstrates that the proposed algorithm possesses better estimation accuracy than the conventional algorithms by at least a 3-dB power gain in the MSE.

Figure 3a–c presents the MSEs of the proposed algorithm with respect to different parameter settings of the GFDM signal. Figure 3a presents the MSEs of the proposed algorithm under a fixed number of subcarriers K = 32 and various numbers of subsymbols M = 2, 4, and 8. As noted, the proposed algorithm has an SNR proportional to the number of subsymbols M, as demonstrated in (8) and (33). Figure 3a indicates that the MSE of the proposed CFO estimate decreases as M increases. Conversely, for a fixed number of subsymbols M = 2, Figure 3b presents the MSEs of the proposed algorithm with various numbers of subcarriers: K = 32, 64, and 128, demonstrating that an increased number of subcarriers can improve the MSE of the proposed algorithm. However, the black line (for M = 8, K = 32) in Figure 3a is superior to the black one (for M = 2, K = 128) in Figure 3b in MSE, even though both cases have the same signal size: N = 256. As noted, the proposed algorithm uses (M − 1)K time samples in the calculation of the ML estimate in (22). The case of (M = 8, K = 32) in Figure 3a provides more samples than does the case (M = 2, K = 128) in Figure 3b for the fractional CFO estimation and, thus, performs better in the MSE. Similar results are evident for the green lines in Figure 3a,b, with the signal size N = 128 for both cases. Therefore, for a fixed signal size N, the combination of (M, K) presents a tradeoff between the estimation accuracy and spectral efficiency of the proposed method. To demonstrate this, Figure 3c presents the MSEs of the proposed algorithm under a fixed signal block size N = 256 and various combinations of (M, K) = (2, 128), (4, 64), and (8, 32). For a fixed N, setting a large M provides more time samples to the proposed algorithm in the calculation of the fractional CFO estimate in (22). This enhances the signal strength and, thus, improves estimation accuracy at the expense of spectral efficiency.

Figure 4 presents the CFO acquisition regions of the proposed algorithm and the methods in [9,10,14] with an SNR of 20 dB; all of the algorithms are demonstrated to have a CFO acquisition region in the interval $\left[-\frac{K}{2},\frac{K}{2}\right)$. Figure 4 shows that for all CFO values, the proposed non-data-aided algorithm has better estimation accuracy compared with the other methods for which a training sequence is used for the estimation.

Figure 5 compares the computational burden (as listed in Table 1) of the proposed ML-based algorithm with that of the algorithms by Li, Shayanfar, and Wang in [9,10,14], respectively. The precision of the search process conducted in [9,10] is 10⁻⁴ (or equivalently, q = 4). The experiment sets the number of subcarriers K = 32, and the number of subsymbols ranges from M = 2 to M = 32, resulting in a GFDM block size ranging from N = 64 to N = 1024. Because the algorithms in [9,10] use a full-sized preamble block to search for the CFO in a fine grid, this results in high computational complexity that is inversely proportional to the grid size, ${10}^{-q}.$ The algorithm in [14] employs a ZC sequence to estimate the CFO from the root of the associated cost function, namely a polynomial of degree K, thus, considerably reducing the complexity relative to those in [9,10]. The proposed ML algorithm estimates the fractional and the integer CFOs through correlation matching. This greatly reduces computational complexity. Therefore, we conclude that in addition to having improved performance in the estimation accuracy, the proposed ML-based algorithm is more efficient in computation overheads than the conventional algorithms in [9,10,14].

Figure 6 presents the MSEs of the proposed algorithm using different numbers of VCs for the integer CFO estimation under the scenario M = 2 and K = 32. The number of VCs is set at $\left|S_{\mathrm{VC}}\right|=\beta K$ with $\beta$ given in percentage. It demonstrates that the proposed algorithm fails to estimate the integer CFO when $\beta =5\%$ because the insufficient number of VCs leads the cost function in (30) to make a false alarm at the deep-faded subcarriers. As the number of VCs increases, as Figure 6 illustrates, the proposed algorithm has comparable MSEs when $\beta \ge 15\%$.

Figure 7 shows the pseudo-spectrum of the proposed algorithm when $\epsilon =-7.4332$, $\beta =15\%$, and $\mathrm{SNR}=10 \mathrm{dB}$. It demonstrates that the proposed VCM effectively identifies the integer CFO from the peak of the pseudo-spectrum.

5. Conclusions

This study proposes an efficient CFO estimation algorithm for GFDM systems. In contrast to traditional algorithms using a preamble signal block for estimation, the proposed algorithm uses repetitive subsymbols incorporating VCs to estimate the CFO in two stages. The repetitive subsymbols enable the proposed algorithm to estimate the fractional CFO through an ML method, and the VCs allow the proposed algorithm to identify the integer CFO through VCM. The selection of the number of repetitive subsymbols and the number of subcarriers results in a tradeoff between the estimation accuracy and the spectral efficiency of the proposed method. For a fixed GFDM signal block size, an increase in the number of repetitions effectively improves the estimation accuracy of the proposed algorithm at the expense of spectral efficiency. Compared with conventional algorithms, the proposed algorithm requires considerably lower computational complexity in addition to having better estimation accuracy and spectral efficiency.