FTN-GFDM Detection Based on Reduced-Complexity Soft Sphere Decoding Integrated with Polar Codes

I. INTRODUCTION

THE spectral efficiency of beyond fifth generation (5G) and sixth generation (6G) networks needs to increase significantly to enable the high volume of data traffic predicted for future applications. Several new applications scenarios are being proposed by researchers around the world to provide global connectivity, invisible security, digital twins and other high demanding use cases [1]. Massive multipleinput multiple-output (MIMO) and ultra-dense network (UDN) improve capacity in densely populated areas, but these technologies are not readily in remote and rural areas [2]. Since enhanced remote area communications (eRAC) applications are more likely to operate in bands below 1 GHz, it is desirable to increase the spectral efficiency of the waveform to achieve higher data rates. By using non-orthogonal waveforms compressed in time and frequency domains beyond the Nyquist limit for interference-free communication, it is possible to increase the number of transmitted bits per sample of the waveform, achieving higher data rates and overall better quality of experience (QoE). This requires a dedicated detector because linear receivers designed for orthogonal waveforms cannot mitigate the interference, leading to a poor bit error rate (BER) performance.

In principle, faster than Nyquist (FTN) can be applied to any waveform, but generalized frequency division multiplexing (GFDM) [3] stands out among possible waveforms for 6G networks because of its flexibility to address different requirements, such as low adjacent channel leakage ratio (ACLR), low peak-to-average power ratio (PAPR) or high cyclic prefix (CP) efficiency [4]. Also, GFDM has Orthogonal frequency division multiplexing (OFDM), discrete Fourier transform spread orthogonal frequency division multiplexing (DFT-s-OFDM), orthogonal time frequency space (OTFS) and other waveforms as corner cases [5], [6], making it compatible with legacy networks or other wireless standards.

Due to its flexibility, FTN can be easily applied to GFDM simultaneously in time and frequency domains, increasing the overall spectrum efficiency gains if the Mazo limit [7], [8] in each dimension is respected. This approach leads to a new waveform, defined as FTN-GFDM, which has been shown to provide higher spectrum efficiency without uncoded BER performance loss [9].

However, in order to achieve the desirable performance, the receiver must resolve the interference introduced by the FTN signaling. It has been shown that non-linear MIMO detectors can be redesigned to address the self-interference in FTN-GFDM waveform [10]. From the available detectors sphere decoder (SD) has shown to achieve the best uncoded BER performance with an affordable complexity. Although, the SD detector available in the literature delivers hard decisions for the forward error correction (FEC) decoder, which means that the error correction algorithm cannot provide its best performance. In order to achieve the optimal performance, the FEC decoder needs the log-likelihood ratios (LLRs) from the waveform detector, which means that the SD must provide a soft output.

The main aim of this paper is to design a soft SD detector for FTN-GFDM system and evaluate its performance in terms of complexity and coded BER when integrated with a stateof- the-art FEC scheme. Polar codes have been selected to be integrated with the FTN-GFDM because of its high error correction capability and flexibility in terms of code rates and codeword length [11], [12]. Polar codes have also been shown to achieve the channel capacity for both discrete and continuous memoryless channels [11]. Polar codes also can be designed to be systematic, reducing the encoder and decoder complexities. These characteristics are beneficial for eRAC applications in remote and rural areas, since the trade-off between complexity, robustness and data rate can be tailored for different situations. Furthermore, polar codes have attracted interest from the academic community, having been chosen by the 3rd Generation Partnership Project (3GPP) as the FEC scheme for the control channel in 5G networks [13]. The key contributions of this paper, when compared to the existing literature, are as follows:

· Design of a soft-output detector based on SD for the FTN-GFDM waveform;

· Integration with a coding scheme to evaluate the performance gain achieved from using a soft-output detector for FTN-GFDM;

· Performance analysis under different channel models; and

· Complexity analysis and comparison between soft and hard decision detectors.

It is important to highlight that the aim of this paper is not an exhaustive exploration of all state-of-the-art FEC schemes in order to define the scheme that achieves the best performance. Instead, the contributions presented are closely related to the design, implementation, and evaluation of a soft-output detection scheme for the FTN-GFDM waveform, which will benefit the performance of any FEC scheme that can take advantage of the extra information provided by such detector. This paper shows that simple FEC schemes can also benefit from a soft-output detector, achieving better BER performance even when low complexity FEC decoders are employed.

The remainder of this paper has the following structure. Section II presents the proposed system model. Section III describes the design of the soft SD detector, in particular the use of tree search algorithms to find symbols that minimize the distance to the discrete filtered received signal. The detector’s complexity analysis is also presented in this section. Section IV presents the coded BER performance of the proposed detector in comparison with hard decision SD assuming different channel models. Also, the complexity of the proposed detector is compared with the hard SD in terms of floating-point operations (FLOPs). Finally, Section V concludes this paper and presents future research directions.

II. SYSTEM MODEL

The block diagram of the proposed FTN-GFDM transceiver is shown in Fig. 1. Each subsystem is described in the following subsections.

A. Polar Encoding and Decoding

Polar coding is a channel coding technique that uses polarized bits to improve the reliability of transmission over noisy channels [11]. Polar codes were first introduced in [11] and gained considerable attention due to their excellent error correction performance, scalability, and low decoding complexity. The idea of polar codes is to take a channel with a high error probability and transform it into two channels, one with a low error probability and one with a high error probability. The information is transmitted on the low error probability channel, while the high error probability channel is used for error correction [12]. Therefore, polar coding is integrated before FTN-GFDM modulation and after FTN-GFDM detection to ensure the reliability of the communication system.

1) Encoding: The polar encoder block, shown in Fig. 1, converts a block of information bits [TeX:] $$\mathbf{b}_{\mathrm{i}} \in \mathbb{R}^{N_{\mathrm{i}} \times 1}$$ into a sequence of coded bits [TeX:] $$\mathbf{b}_{\mathrm{c}} \in \mathbb{R}^{N_{\mathrm{c}} \times 1}$$. The systematic encoding is performed by two non-systematic encoders interleaved with the insertion of frozen bits between them. The non-systematic encoding process can be defined as

where [TeX:] $$\mathbf{b}_{\mathrm{u}} \in \mathbb{R}^{N_{\mathrm{c}} \times 1}$$ is formed by concatenating the information bits [TeX:] $$\mathbf{b}_i$$ with [TeX:] $$N_{\mathrm{c}}-N_{\mathrm{i}}$$ frozen bits, and [TeX:] $$\mathbf{F}^{(\oplus n)} \in \mathbb{R}^{N_{\mathrm{c}} \times N_{\mathrm{c}}}$$ is the nth power Kronecker matrix, which its first power is given by

The permutation matrix [TeX:] $$\mathbf{B}_n \in \mathbb{R}^{N_{\mathrm{c}} \times N_{\mathrm{c}}}$$ is called bit-reversal matrix and it reverses the row positions of [TeX:] $$\mathbf{F}^{(\oplus n)}.$$ The coding rate can be expressed as [TeX:] $$R_{\mathrm{c}}=N_{\mathrm{i}} / N_{\mathrm{c}},$$ where [TeX:] $$N_{\mathrm{i}}$$ is the number of information bits and [TeX:] $$N_{\mathrm{c}}$$ is the number of coded bits, with [TeX:] $$N_{\mathrm{c}}$$ being a power of 2.

The code was constructed as proposed in [14], where an exhaustive search for the set of frozen bits was performed. Firstly, a range of signal-to-noise ratio (SNR) of interest was considered. Then, [TeX:] $$\mathcal{X}$$ polar codes were designed using the Bhattacharyya parameter [11], where [TeX:] $$\mathcal{X}$$ represents the SNR set of interest. The BER and frame error rate (FER) were evaluated and, based on the results, the code with the best performance was selected. As demonstrated in [14], the performance is independent of the method when the code is optimized for the best performance considering BER and FER parameters.

2) Puncturing: To integrate the polar code into the FTN-GFDM system, the number of coded bits [TeX:] $$N_{\mathrm{c}}$$ must be divisible by N = KM, where K and M are the number of FTN-GFDM subcarriers and subsymbols, respectively. Otherwise, some bits must be punctured. The number of punctured bits is equal to the remainder of the division. As shown in [11], the code performance increases with [TeX:] $$N_{\mathrm{c}}$$ and, hence, this parameter shall be chosen to result in the lowest number of punctured bits possible.

The punctured bits are initially inserted in the last positions of [TeX:] $$\mathbf{b}_\mathrm{u}.$$ The initial puncturing pattern is derived from the column weight of [TeX:] $$\mathbf{F}^{(\oplus n)}$$ based on the non-systematic polar encoding structure. A bit reversal permutation [TeX:] $$\mathbf{B}_n$$ is applied to generate the puncturing pattern [TeX:] $$\mathcal{I}_p.$$ Once this is done, the punctured bits are considered part of the information bits, and only the frozen bits are re-inserted after the first encoding process. Finally, using the knowledge of [TeX:] $$\mathcal{I}_p,$$ the punctured bits are removed from [TeX:] $$\mathbf{b}_\mathrm{c}$$ and they are not transmitted.

At the receiver side, before decoding, the punctured bits must be re-inserted. Assuming that the punctured bit positions at the receiver can be filled with “0”, then the LLRs at these positions can be set to infinity [15].

3) Decoding: The polar decoder uses a decoding algorithm called successive cancellation (SC), which operates by iteratively canceling the effect of unreliable bits in the code [11].

In the SC algorithm, [TeX:] $$\hat{\mathbf{b}}_{\mathrm{u}}$$ is estimated by a recursive computation of likelihood ratios (LRs) of [TeX:] $$\hat{\mathbf{b}}_{\mathrm{c}}.$$ The [TeX:] $$\iota\text{th}$$ decoded bit, [TeX:] $$\hat{b}_{\mathbf{u}}^\iota,$$ is defined by

Here, [TeX:] $$\hat{\mathbf{b}}_{\mathrm{u}}^{(0: \iota-1)}=\left\{\hat{b}_{\mathrm{u}}^0, \hat{b}_{\mathrm{u}}^1, \cdots, \hat{b}_{\mathrm{u}}^{(\iota-1)}\right\} \in \mathbb{R}^{\iota \times 1}$$ and [TeX:] $$\mathcal{H}(\cdot)$$ is decision function given by

where [TeX:] $$\mathcal{I}_f$$ is the subset of frozen bits index and

Here, [TeX:] $$\operatorname{Pr}\left[\left(\hat{\mathbf{b}}_{\mathrm{c}}, \hat{\mathbf{b}}_{\mathrm{u}}^{(0: \iota-1)}\right) \mid \hat{b}_{\mathrm{u}}^\iota=s\right]$$ represents the conditional probability of the received codeword being [TeX:] $$\hat{\mathbf{b}}_{\mathrm{c}}$$ and the previously decoded bits being [TeX:] $$\hat{\mathbf{b}}_{\mathrm{u}}^{(0: \iota-1)},$$ given that [TeX:] $$\hat{b}_{\mathrm{u}}^\iota=s \in\{0,1\}.$$ LRs in (5) can be computed recursively using a graph defined by the functions f and q, each given by

and

where [TeX:] $$\hat{b}_{\mathrm{u}}^{(\mathrm{sum})}$$ is the partial sum of the elements of [TeX:] $$\hat{\mathbf{b}}_{\mathrm{u}}^{(0: \iota-1)} .$$ Thus, the LR can be computed as

where [TeX:] $$0 \leq \ell\lt \log _2 N_{\mathrm{c}}$$ is the graph stage, ι is the index of the current decoded bit.

In the FTN-GFDM transceiver of Fig. 1, estimates of the coded bits, [TeX:] $$\hat{\mathbf{b}}_{\mathrm{c}} \in \mathbb{R}^{N_{\mathrm{s}} \times 1},$$ or the LLR values, [TeX:] $$\mathbf{L} \in \mathbb{R}^{N_{\mathrm{c}} \times 1},$$ can be supplied to the polar decoder when the switch is in position 1 or 2, respectively. The vector containing the estimated information bits, [TeX:] $$\hat{\mathbf{b}}_{\mathrm{i}} \in \mathbb{R}^{N_{\mathrm{s}} \times 1},$$ is delivered at the output of the polar decoder.

The SC polar decoder with LLR has been shown to provide a good trade-off between decoding performance and computational complexity. It can achieve near-optimal performance with moderate computational complexity, making it suitable for practical applications [16]. Despite its effectiveness, when compared to more sophisticated decoding techniques, such as SC-list [17] and SC-flip [18], the SC algorithm is considered a baseline with inferior performance. Nonetheless, the purpose of this article is to demonstrate that even the simplest decoder can benefit from LLRs and improve BER compared to the hard output detectors.

B. Symbol Mapping and Demapping

In the block diagram of Fig. 1, the mapper converts the coded bits [TeX:] $$\mathbf{b}_\mathrm{c}$$ into J-quadrature amplitude modulation (QAM) symbols and allocates the symbols into the FTN-GFDM data matrix, [TeX:] $$\mathbf{S} \in \mathbb{C}^{K \times M}.$$ As a result, [TeX:] $$\mathbf{S}$$ contains the N QAM symbols to be transmitted in an FTN-GFDM block, such that

On the receiver side, the demapper is responsible for converting each QAM symbol provided by the hard output detector into its sequence of [TeX:] $$\log _2 J$$ bits. Thus, the demapper outputs [TeX:] $$N \log _2 J$$ bits for each received FTN-GFDM block.

C. FTN-GFDM Modulation

Slight modifications in the definition of the time-frequency grid enable GFDM to include FTN signaling [9], [19]. Let the prototype filter have [TeX:] $$\mathcal{N}$$ samples divided into [TeX:] $$\mathcal{P}$$ periods with [TeX:] $$\mathcal{S}$$ samples each. Let also the the subsymbols be defined at time intervals of [TeX:] $$\mathcal{K}$$ samples and the subcarriers at frequency intervals of [TeX:] $$\mathcal{M}$$ samples. Using these definitions, the GFDM signal is given by

where [TeX:] $$n=0, \cdots, \mathcal{N}-1, s_{k, m}$$ is the QAM symbol for the kth subcarrier and mth subsymbol, and g[n] is the prototype filter impulse response.

There are three approaches to apply FTN signaling in GFDM. The first one consists of decreasing the time delay between the prototype filters for each subsymbol [TeX:] $$(\mathcal{K} \lt \mathcal{S})$$, increasing the time overlap among the subsymbols. The second approach consists of reducing the frequency spacing among the subcarriers [TeX:] $$(\mathcal{M} \lt \mathcal{P})$$, increasing the overlapping in the frequency domain. The third approach is the combination of the first two.

The spectral efficiency gain can be computed by the squeezing factors in time and frequency, namely [TeX:] $$v_t=\mathcal{K} / \mathcal{S}$$ and [TeX:] $$v_f=\mathcal{M} / \mathcal{P}$$, respectively.

It is important to highlight that

and when [TeX:] $$\mathcal{N} / \mathcal{M}$$ and [TeX:] $$\mathcal{N} / \mathcal{K}$$ are not integers, the squeezing factors must be adjusted by [TeX:] $$\bar{v}_t=\mathcal{P} / M \text { and } \bar{v}_f=\mathcal{S} / K$$, respectively, and the GFDM signal must be adjusted to

where [TeX:] $$\sqrt{\bar{v}_t \bar{v}_f}$$ normalizes the transmit power. Fig. 2 shows the block diagram of the FTN-GFDM transmitter, where [TeX:] $$\mathbf{s}=\operatorname{vec}(\mathbf{S}) \in \mathbb{C}^{N \times 1}$$ is the symbol vector obtained by stacking the columns of [TeX:] $$\mathbf{S}$$ i.e., [TeX:] $$\mathbf{s}=\left(s_{0,0}, s_{1,0}, \cdots, s_{K-1,0}, s_{0,1}, \cdots, s_{K-1, M-1}\right)^{\mathrm{T}}.$$ This vector is parallelized and the element [TeX:] $$s_{m, k}$$ is carried by the mth subsymbol, denoted by [TeX:] $$g\left[\left\langle n-m v_t \mathcal{S}\right\rangle_{\mathcal{N}}\right],$$ of the kth subcarrier, denoted by [TeX:] $$\exp \left(j 2 \pi \frac{k v_f}{\mathcal{S}} n\right).$$ The FTN-GFDM signal, x[n], is obtained by adding the subsymbols from all subcarriers. As described in (13), power normalization is used to generate [TeX:] $$\bar{x}[n].$$

In matrix notation, vector [TeX:] $$\overline{\mathrm{x}}=(\bar{x}[0], \bar{x}[1], \cdots, \bar{x}[\mathcal{N}-1])^{\mathrm{T}} \in \mathbb{C}^{\mathcal{N} \times 1}$$ can be computed as

where [TeX:] $$\mathbf{A} \in \mathbb{C}^{\mathcal{N} \times N}$$ is the transmission matrix containing N = KM versions of the prototype filter [TeX:] $$\mathrm{g} \in \mathbb{C}^{\mathcal{N} \times 1}$$ circularly shifted in time and frequency, i.e.,

The column vector

contains the prototype filter samples shifted to the kth subcarrier and the mth subsymbol. Before transmitting the signal [TeX:] $$\overline{\mathbf{x}} \in \mathbb{C}^{\mathcal{N} \times 1},$$ a CP can be added to the FTN-GFDM vector by copying the last [TeX:] $$N_{\mathrm{CP}}$$ samples from [TeX:] $$\bar{\mathbf{x}}$$ to the beginning, thus creating the transmission vector [TeX:] $$\tilde{\mathbf{x}} \in \mathbb{C}^{\left(\mathcal{N}+N_{\mathrm{CP}}\right) \times 1}.$$

D. Channel and Equalization

The received vector [TeX:] $$\tilde{\mathbf{y}} \in \mathbb{C}^{\mathcal{N} \times 1}$$ after removing CP is given by

where [TeX:] $$\mathbf{w} \in \mathbb{C}^{\mathcal{N} \times 1}$$ is the additive white Gaussian noise (AWGN) vector and [TeX:] $$\mathbf{H} \in \mathbb{C}^{\mathcal{N} \times \mathcal{N}}$$ contains circularly shifted versions of the channel impulse response [TeX:] $$\mathbf{h} \in \mathbb{C}^{\mathcal{L} \times 1},$$ such that

In this paper, three channel models are considered: the additive white Gaussian noise (AWGN) channel, the timeinvariant frequency-selective (TIFS) channel, and the block time-variant flat (TVF) channel. In particular, a TVF channel with a Rayleigh tap changes with each FTN-GFDM block, and a flat frequency response is assumed, i.e., the channel response varies with each transmitted FTN-GFDM block, but it is constant over the block interval.

The received signal can be represented in the frequency domain as

where [TeX:] $$\mathbf{F}_{\mathcal{N}} \in \mathbb{C}^{\mathcal{N} \times \mathcal{N}}$$ is the Fourier matrix, [TeX:] $$\bar{\mathbf{X}} \in \mathbb{C}^{\mathcal{N} \times 1}$$ is the transmit vector [TeX:] $$\bar{\mathbf{x}}$$ in the frequency domain, W [TeX:] $$\mathbf{W} \in \mathbb{C}^{\mathcal{N} \times 1}$$ is the AWGN vector [TeX:] $$\mathbf{w}$$ in the frequency domain, and [TeX:] $$(\cdot)^{\mathrm{H}}$$ represents the Hermitian operator. Additionally, [TeX:] $$\mathrm{F}_{\mathcal{N}} \mathrm{HF}_{\mathcal{N}}^{\mathrm{H}}$$ is a diagonal matrix containing the channel frequency response. Assuming knowledge of the channel impulse response, the equalization in the frequency domain is given by

where [TeX:] $$\bar{\mathbf{Y}} \in \mathbb{C}^{\mathcal{N} \times 1}$$ is the equalized received vector in the frequency domain. Alternatively, [TeX:] $$\bar{\mathbf{Y}}$$ can be represented in the time domain by

where [TeX:] $$\bar{\mathbf{y}} \in \mathbf{C}^{\mathcal{N} \times 1}$$ is the equalized received vector in the time domain.

E. FTN-GFDM Demodulation

The matched filter (MF) is used to decouple the FTN-GFDM subcarriers and subsymbols in [TeX:] $$\bar{\mathbf{y}}$$ to allow proper detection of the symbols vector. Furthermore, MF maximizes the signal-to-interference-plus-noise ratio (SINR) of [TeX:] $$\bar{\mathbf{y}}$$. The received discrete signal at the MF output [TeX:] $$\mathbf{r} \in \mathbb{C}^{N \times 1}$$ is given by

where [TeX:] $$\mathbf{G}=\mathbf{A}^{\mathrm{H}} \mathbf{A} \in \mathbb{C}^{N \times N}$$ is the correlation coefficient matrix, [TeX:] $$\bar{\mathbf{w}}=\mathbf{A}^{\mathrm{H}} \mathbf{H}^{-1} \mathbf{w} \in \mathbb{C}^{\mathrm{N} \times 1}.$$ Since the linear operation [TeX:] $$\mathbf{A}^{\mathrm{H}} \mathbf{H}^{-1}$$ correlates the samples of [TeX:] $$\mathbf{w}$$, the filtered samples in [TeX:] $$\bar{\mathbf{w}}$$ are colored.

The MF block diagram is shown in Fig. 3, where [TeX:] $$\bar{y}[n]$$ denotes the nth sample in the equalizer output and the index [TeX:] $$n=0, \cdots, \mathcal{N}-1$$ is reset with each new FTN-GFDM block received.

F. Soft FTN-GFDM Detection

Given that the [TeX:] $$\nu \text {th}$$ J-QAM symbol, with [TeX:] $$\nu=1, \cdots, N,$$ represents a set of [TeX:] $$\log _2 J$$ bits, i.e., [TeX:] $$\left\{b_{\nu, 1}, \cdots, b_{\nu, \log _2} J\right\},$$ the soft-output FTN-GFDM detection is calculated as follows

where [TeX:] $$L_{\nu, \mu}$$ is the LLR of the [TeX:] $$\mu\text{th}$$ bit in the [TeX:] $$\nu\text{th}$$ symbol of the estimated QAM symbol sequence vector [TeX:] $$\hat{\mathbf{s}} \in \mathbb{C}^{N \times 1},$$ whose binary representation [TeX:] $$\hat{\mathbf{b}} \in \mathbb{R}^{\left(N \log _2 J\right) \times 1}$$ is given by

The direct computation of the LLRs in (23) results in prohibitive computational complexity. The max-log approximation can be employed to reduce the complexity. Hence, equation (23) can be approximated as

where [TeX:] $$\mathbb{M}_{\nu, \mu}^{(0)} \text { and } \mathbb{M}_{\nu, \mu}^{(1)}$$ represent the FTN-GFDM sequences that have [TeX:] $$\hat{b}_{\nu, \mu}=0 \text { and } \hat{b}_{\nu, \mu}=1 \text {, }$$ respectively. For each bit [TeX:] $$\hat{b}_{\nu, \mu} \text {, }$$ one of the minima in (25) will be the Euclidean distance of the maximum likelihood (ML) solution, while the other will be the minimum Euclidean distance of the ML antipodal solution [20].

The ML solution [TeX:] $$\hat{\mathbf{s}}^{\mathrm{ML}} \in \mathbb{C}^{N \times 1}$$ is given by

where [TeX:] $$\mathbb{M}$$ is the set of all possible J-QAM symbol sequences. The distance [TeX:] $$d^{\mathrm{ML}}$$ is the Euclidean distance of the ML solution [TeX:] $$\hat{\mathbf{s}}^{\mathrm{ML}},$$ given by

and [TeX:] $$d_{\nu, \mu}^{\overline{\mathrm{ML}}}$$ is the minimum Euclidean distance of the ML antipodal solution, given by

where [TeX:] $$\hat{b}_{\nu, \mu}^{\mathrm{ML}}$$ is the [TeX:] $$\mu\text{th}$$ bit of the [TeX:] $$\nu\text{th}$$ symbol of the ML solution [TeX:] $$\hat{\mathbf{s}}^{\mathrm{ML}} \text { and } \hat{b}_{\nu, \mu}^{\overline{\mathrm{ML}}}$$ is its binary complement. Then, [TeX:] $$\mathbb{M}^{\hat{b}_{\nu, \mu}^{\overline{\mathrm{ML}}}}$$ are the FTN-GFDM sequences that have [TeX:] $$\hat{b}_{\nu, \mu}^{\overline{\mathrm{ML}}}$$ for the [TeX:] $$(\nu, \mu)$$ element.

With the aid of (26), (27), and (28), equation (25) can be rewritten as

To calculate the LLRs in (29), it is necessary to find the Euclidean distance of the ML antipodal solution, [TeX:] $$d_{\nu, \mu}^{\overline{\mathrm{ML}}},$$ for each bit of each symbol of the FTN-GFDM signal [20]. Since softoutput detection uses the minimum Euclidean distances of all antipodal ML solutions, soft-output detection results in higher computational complexity than hard-output detection [20], [21].

The maximum likelihood sequence estimation (MLSE) detector can find [TeX:] $$d^{\mathrm{ML}}$$ and [TeX:] $$\mathbf{d}^{\overline{\mathrm{ML}}} \in \mathbb{R}^{\left(N \log _2 J\right) \times 1}$$ in (29). Since the Mazo limit is respected, the MLSE detector can effectively handle the interference caused by FTN-GFDM and reduce the BER. The search for the ML solution is performed as in (27). As a result, all possible combinations of transmitted QAM symbols are exhaustively scanned to find the one that gives the minimum Euclidean distance for r. Then, the MLSE detector must find the ML antipodal solution for each bit of [TeX:] $$\hat{\mathbf{b}}^{\mathrm{ML}} \in \mathbb{R}^{\left(N \log _2 J\right) \times 1}$$ as in (28). The set of possible ML antipodal solutions for each bit [TeX:] $$\mathbb{M}^{\hat{b}_{\nu, \mu}^{\overline{\mathrm{ML}}}}$$ consists of [TeX:] $$J^N / 2$$ combinations of QAM symbols.

A FLOP [22] can be defined as an addition, subtraction, division, or multiplication operation in the real domain. Thus, the computational complexity of MLSE detection as a function of FLOPs can be expressed in two steps. The first step is to find [TeX:] $$\hat{\mathbf{s}}^{\mathrm{ML}} \text {. }$$ This step requires [TeX:] $$\left(16 N^2+8 N-2\right) J^N$$ FLOPs [10]. The second step is to search for [TeX:] $$N \log _2 J$$ ML antipodal solutions. Since the number of possible ML antipodal solutions for each bit is [TeX:] $$J^N / 2$$, the computational complexity to find all [TeX:] $$d_{\nu, \mu}^\overline{\mathrm{ML}}$$ is [TeX:] $$\left(16 N^2+8 N-2\right) \frac{J^N}{2} N \log _2 J$$ FLOPs. Therefore, the total MLSE complexity is given by

MLSE detection complexity is constant among all SNR values and grows exponentially with transmission matrix size and modulation order. Although the nonlinear MLSE detector can find the LLRs and minimize the error probability, its computational complexity is prohibitive, making this detector unfeasible. Therefore, lower computational complexity detectors must be used to find [TeX:] $$d^{\mathrm{ML}} \text { and } \mathbf{d}^\overline{\mathrm{ML}}.$$

III. SOFT SPHERE DECODING

The design of a soft SD for recovering the LLRs from the received FTN-GFDM signal after the MF is the main contribution of this paper. This detector improves the overall BER performance of the system, as it provides more information for the FEC decoder. The following subsections describe the sphere decoding principles, the proposed algorithm, and the complexity analysis of our solution as compared with other detectors.

A. Sphere Decoding Principles

Traditional ML detectors search for the best candidate sequence from the entire sample space of the modulation scheme, which means comparing the Euclidean distance between the received sequence and all possible transmit sequences. This search mechanism has a prohibitive high complexity when the modulation order, number of subsymbols and number of subcarriers take on standard operation values. One approach to deal with this problem is to exploit suboptimal detectors. Sphere decoding consists of limiting the search space to a multidimensional sphere with a radius of ρ and searching only for lattice points that are inside the sphere [23]. In order to find the ML and its antipodal solution with affordable complexity, the SD can be employed to solve (29) efficiently. The closest lattice point to the vector received inside the sphere is also the closest lattice point of the entire search space. Thus, the SD can achieve ML optimal¹ performance with lower computational cost than exhaustive search algorithms [24].

¹ In fact, the performance is max-log optimal, since the smallest-vector algorithm operates on the approximated problem of equation (29).

The search radius must be large enough to contain the ML solution and to have few lattice points inside it [25]. The search within the sphere can be transformed into a tree search, where a node and its sub-tree are pruned when they can no longer lead to an ML solution update. Every time a leaf node is found, i.e., the first level of the tree search is reached, a lattice point is found inside the sphere, and the ML solution is updated.

The sphere radius in SD is defined according to the AWGN variance. Since the problem in (29) has noise samples colored by MF, a whitening filter is used, resulting in

Considering [TeX:] $$\zeta=\left(\mathbf{A}^{\mathrm{H}} \mathbf{A}\right)^{-1} \mathbf{A}^{\mathrm{H}} \mathbf{r},$$ the SD radius can be expressed by

To simplify the evaluation of the Euclidean norm in (31), the interference matrix [TeX:] $$\mathbf{G}$$ must be decomposed by the Cholesky factorization [26] given by

where [TeX:] $$\mathbf{R} \in \mathbb{C}^{N \times N}$$ is an upper triangular matrix. Therefore, the condition in (31) can be expressed as

As a result of the structure of [TeX:] $$\mathbf{R},$$ the inequality (34) can be rewritten as [27]

Note that, because of the triangular structure of [TeX:] $$\mathbf{R},$$ the Nth element of (35) depends only on [TeX:] $$\hat{s}_N,$$ the (N − 1)th element depends only on [TeX:] $$\left\{\hat{s}_N, \hat{s}_{N-1}\right\},$$ and so on [23], [27]. Thus, the search for lattice points within the sphere becomes a tree search.

Since the ML solution can be approximated by (34) in SD, [TeX:] $$d^{\mathrm{ML}}$$ and [TeX:] $$d_{\nu, \mu}^{\overline{\mathrm{ML}}}$$ can be rewritten as

and

respectively.

As with the MLSE detector, to compute the LLRs in (29), the SD approach must first find the ML solution and, then, the minimum Euclidean distances of the ML antipodal solutions. To find [TeX:] $$d^{\mathrm{ML}}$$, the SD algorithm must explore a search tree with a depth of N + 1 levels and [TeX:] $$J^N$$ nodes at level ℓ = 1. To find all ML antipodal solutions, [TeX:] $$N \log _2 J$$ search trees with N + 1 levels and [TeX:] $$J^N / 2$$ nodes on level ℓ = 1 must be examined. Nevertheless, the number of nodes in each tree depends on the searched bit position in [TeX:] $$\hat{b}_{\nu, \mu}^\overline{\mathrm{ML}} .$$ Fig. 4 shows the search trees for N = 3 and binary phase-shift keying (BPSK) symbols. The search tree used to determine the ML solution, [TeX:] $$\hat{\mathbf{s}}^{\mathrm{ML}} \text {, }$$ is shown in Fig. 4a. Since [TeX:] $$\hat{\mathbf{b}}^{\mathrm{ML}}=\left[\begin{array}{lll} 1 & 1 & 0 \end{array}\right]^{\mathrm{T}}$$ in this example, Figs. 4b, 4c, and 4d show the search tree for each bit of the ML antipodal solution. However, the SD complexity depends on the number of nodes scanned. In the worst case, the SD algorithm must search the entire search tree, and its complexity becomes exponential, approaching that of MLSE. Although the SD algorithm is less complex than the MLSE detector, its computational complexity can be high for some practical applications where the devices are limited in computing power.

B. The Single Tree Search Algorithm

The soft-output single tree search (STS)-SD algorithm proposed in [20] ensures complexity minimization by jointly searching for the ML solution and the Euclidean distances of the ML antipodal solution. Partial distances are the intermediate distances when traversing levels in the search tree. In this strategy, the underlying branch of a node is only traversed if the partial Euclidean distance [TeX:] $$d(\hat{\mathbf{s}})$$ of this node leads to: i) An update of the ML solution, i.e., if [TeX:] $$d(\hat{\mathbf{s}})\lt d^{\mathrm{ML}}$$ or; ii) An update of the Euclidean distance of at least one ML antipodal solution, i.e., if [TeX:] $$d(\hat{\mathbf{s}})\lt d_{\nu, \mu}^{\overline{\mathrm{ML}}}.$$ Thus, STS-SD can be employed to reduce complexity, ensuring that the search tree nodes are visited at most once.

The STS-SD algorithm can be divided into two steps: i) List administration and; ii) Tree pruning [20]. The list administration step happens whenever the first level is reached, i.e., a leaf node of the search tree is reached (Algorithm 1 lines 26 to 40). If the Euclidean distance of s at a leaf node is smaller than the Euclidean distance of the current ML solution, i.e., [TeX:] $$d(\hat{\mathbf{s}})\lt d^{\mathrm{ML}},$$ a new ML solution has been found (Algorithm 1 line 28). Before updating the ML solution with the newly found [TeX:] $$\mathbf{s},$$ all [TeX:] $$d_{\nu, \mu}^{\overline{\mathrm{ML}}}$$ for which [TeX:] $$\hat{b}_{\nu, \mu}=\hat{b}_{\nu, \mu}^{\overline{\mathrm{ML}}}$$ are updated with the previous [TeX:] $$d^{\mathrm{ML}}$$ (Algorithm 1 line 29). This guarantees that for each bit in the ML solution that is changed in the update process, the Euclidean distance of the previous ML solution becomes the Euclidean distance of the new ML antipodal solution. Then, the symbol vector [TeX:] $$\hat{\mathbf{s}}^{\mathrm{ML}}$$ is assigned the new distance-minimizing vector [TeX:] $$\hat{\mathbf{s}}.$$ Correspondingly, the Euclidean distance [TeX:] $$d^{\mathrm{ML}}$$ is updated to [TeX:] $$d(\hat{\mathbf{s}})$$ (Algorithm 1 line 30).

However, if the Euclidean distance found in the leaf node is greater than the Euclidean distance of the ML solution, i.e., [TeX:] $$d(\hat{\mathbf{s}})\gt d^{\mathrm{ML}},$$ only the ML antipodal solution is checked. For all ν and μ simultaneously satisfying the bit sequence [TeX:] $$\hat{b}\overline{_{\nu, \mu}^{\mathrm{ML}}}$$ and [TeX:] $$d(\hat{\mathbf{s}})\lt d_{\nu, \mu}^{\overline{\mathrm{ML}}},$$ the Euclidean distances [TeX:] $$d\overline{_{\nu, \mu}^{\mathrm{ML}}}$$ must be updated to [TeX:] $$d(\hat{\mathbf{s}})$$ (Algorithm 1 line 32).

Tree pruning can happen while scanning a node at level ℓ, for ℓ > 1 (Algorithm 1 lines 8 to 25). The partial vector [TeX:] $$\hat{\mathbf{s}}^{\ell} \in \mathbb{C}^{(N-\ell+1) \times 1}$$ at level ℓ (corresponding to the sequence of symbols [TeX:] $$\left(\hat{s}_1, \cdots, \hat{s}_{\ell-1}\right)$$ of a sub-tree at level ℓ) is defined by the sequence of symbols [TeX:] $$\left(\hat{s}_{\ell}, \cdots, \hat{s}_N\right).$$

The pruning criterion for [TeX:] $$\hat{\mathbf{s}}^{\ell}$$ takes into account all Euclidean distances of the ML antipodal solution that can be updated. First, the corresponding bits of the partial vector, [TeX:] $$\hat{\mathbf{b}}^{\ell} \in \mathbb{R}^{\left((N-\ell+1) \log _2 J\right) \times 1} \text {, }$$ are compared to the corresponding bits of the current ML solution, i.e., [TeX:] $$\hat{\mathbf{b}}^{\mathrm{ML}} .$$

All Euclidean distances [TeX:] $$d_{\nu, \mu}^\overline{\mathrm{ML}}$$ that correspond to [TeX:] $$\hat{b}_{\nu, \mu}=\hat{b}_{\nu, \mu}^{\overline{\mathrm{ML}}},$$ [TeX:] $$\nu=\ell, \cdots, N,$$ can be updated by searching the sub-tree of [TeX:] $$\mathbf{s}^{\ell}.$$ Similarly, the Euclidean distances [TeX:] $$d_{\nu, \mu}^\overline{\mathrm{ML}}, \nu=1, \cdots, \ell-1,$$ corresponding to the bits of node [TeX:] $$\hat{\mathbf{s}}^{\ell}.$$ can also be updated. Therefore, the set of Euclidean distances that may be updated during the search in the sub-tree underlying the node [TeX:] $$\hat{\mathbf{s}}^{\ell}.$$ is given by

The node [TeX:] $$\hat{\mathbf{s}}^{\ell}.$$ and its sub-tree is pruned if the partial Euclidean distance, [TeX:] $$d\left(\hat{\mathbf{s}}^{\ell}\right),$$ satisfies

If the condition in (39) is not met, the search must continue at level (ℓ - 1).

The steps to implement the soft-output STS-SD detector can be seen in Algorithm 1. In order to avoid choosing an initial radius and still lead to an efficient tree pruning, the STS algorithm employs the radius reduction strategy, the main idea of which is to initiate the algorithm with [TeX:] $$d^{\mathrm{ML}} \leftarrow \infty$$ and update the radius according to [TeX:] $$d^{\mathrm{ML}} \leftarrow d(\hat{\mathbf{s}})$$ whenever a leaf [TeX:] $$\hat{\mathbf{s}}$$ has been reached.

The STS-SD pruning criterion ensures that a node and its sub-tree are only scanned if this can result in: i) an update of the ML solution or; ii) at least an update of one of [TeX:] $$d_{\nu, \mu}^{\overline{\mathrm{ML}}}.$$ This approach reduces the computational complexity when compared to other soft-output detection algorithms based on tree search [20], [21].

C. Computational Complexity

The complexity of tree search algorithms is dictated mainly by the number of nodes visited and the operational cost at each node. In SD, the number of nodes visited depends on search radius reduction and, consequently, on the SNR and the conditioning of [TeX:] $$\mathbf{G}$$. The operational costs of each node depend on the algorithm. Hence, finding an exact expression for the SD complexity is not a trivial task. For [TeX:] $$\mathbf{G}$$ with poorly conditioning or low SNR, the complexity of the SD can be exponential and, in the worst-case scenario, can be as high as the complexity of the ML detector.

The complexity of the proposed STS-SD is obtained by evaluating the partial Euclidean distance [TeX:] $$d_\ell$$ in line 7 of Algorithm 1. Because [TeX:] $$\mathbf{R}$$ is an upper triangular matrix, the number of operations required to compute [TeX:] $$d_\ell$$ increases as ℓ decreases. Therefore, it is necessary to count the number of visited nodes at the [TeX:] $$\ell \text{th}$$ level and weight them by the number of operations required to compute [TeX:] $$d_\ell$$. Assuming the worst-case scenario, where all nodes in the search tree are visited, the complexity SD is given by

where [TeX:] $$\mathcal{O}_\ell$$ is the number of operations required to compute [TeX:] $$d_\ell$$ on a node at the [TeX:] $$\ell \text{th}$$ level and [TeX:] $$M^{(N+1-\ell)}$$ is the number of nodes at the same level. Thus, [TeX:] $$\mathcal{O}_\ell$$ can be expressed in terms of the number of FLOPs:

Substituting (41) into (40) and applying some sum identities [28], the upper bound for the SD complexity is given by

The difference in complexity between the the soft-output and the hard-output SD relates to the number of nodes visited. As the soft-output SD requires finding the Euclidean distances of antipodal solutions, the number of nodes visited is higher than in hard-output SD, in which it is only necessary to find the minimum Euclidean distance of the ML solution.

IV. SIMULATION RESULTS

In this section, the simulation results are discussed. Subsection IV-A evaluates the performance in terms of BER, while subsection IV-B analyzes the computational complexity of the implemented algorithms.

The parameters of each block in the communication chain used for performance evaluation are presented in Tables I, II, and III. Table I presents polar code parameters. Two possible configurations (A and B) have been defined. These configurations are used in accordance with the data payload of the FTN-GFDM block, which may change according to the time or frequency compression.

Table II presents the FTN-GFDM system parameters used for performance evaluation. Two different configurations are defined, one being applied for time and the other for frequency compression. The parameters have been chosen to make the spectrum efficiency practically equal for both configurations.

Table III shows parameters of the simulated channels. In this paper, three channel models are considered. The first is an AWGN channel, with a flat and time-invariant frequency response. The second is a frequency-selective channel with a time-invariant impulse response, while the third is a doublydispersive channel, whose impulse response is randomly chosen for each FTN-GFDM block, remaining time-invariant during each block. Perfect channel state information (CSI) is assumed on the receiver side for all channel models, since our goal is to evaluate the performance of the proposed FTN-GFDM detectors without taking into account the losses resulting from channel estimation.

A. BER Performance Analysis

The BER performance of the soft-output SD detector is compared with the hard-output SD considering: i) time-compressed FTN-GFDM and; ii) frequency-compressed FTN-GFDM.

Fig. 5 shows BER versus [TeX:] $$\mathrm{E}_{\mathrm{b}} / \mathrm{N}_0$$ of hard and soft-output SD detectors for time-compressed FTN-GFDM. The waveform parameters are presented in Table II for time-compression and the three channels described in Table III have been considered. The time compression [TeX:] $$v_t=0.8$$ introduces intersymbol interference (ISI) and improves the spectrum efficiency by 25%. The uncoded BER performance of the proposed soft-output SD is equal to the theoretical optimum detector. Fig. 5 also displays the polar coded BER performance for soft and hard-output SD. The parametrization of the polar code assumes the values described for Config. A in Table I, because this configuration allows for the codeword to be split in an integer number of FTN-GFDM blocks. Fig. 5 shows that the polar decoder benefits from the soft information since the proposed detector provides significant performance gains when compared with the hard-output SD. Table IV presents the [TeX:] $$E_b / N_0$$ required by each detector to achieve the target BER of [TeX:] $$10^{-3}.$$ It also lists the performance gains of soft over hard outputs.

Fig. 6 presents the BER performance for the frequencycompressed FTN-GFDM. The waveform parameters are those in Table II for frequency-compression. Once again, the channels proposed in Table III have been considered. The polar code with Config. B (see Table I) is employed in this scenario. Fig. 6 shows that the 20% improvement in spectrum efficiency does not imply in any BER performance degradation when the proposed soft-output SD algorithm is used. Also, the proposed detector combined with the polar code is compared with the the polar-coded hard-output SD detector. Again, the polar decoder benefits from the soft output, providing significant BER performance gains, as highlighted in Table V.

B. Computational Complexity Analysis

Table VI presents the mean computational complexity in terms of FLOPs and the mean number of visited nodes for the hard and soft-output SD algorithms for SNR values of 0, 5, and 10 dB. These results are obtained using the frequency compression system parameters shown in Table II. The complexity is analyzed for the three channels shown in Table III. Feeding the system parameters into (42), the upper limit for the SD complexity is 7, 784, 628, 240 FLOPs, and the total nodes in the tree search is 33, 554, 430. Assuming an SNR of 10 dB, the hard-output SD complexity represents 8.85% of the softoutput SD complexity for the AWGN channel, 8.75% for the TIFS channel, and 43.15% for the TVF channel. This shows that the soft-output SD detector presents higher computational complexity than the hard-output detector. In the worst case, both can reach the upper bound. However, since the soft-output SD visits more nodes, the probability of it reaching the upper bound is higher.

Table VI shows that the number of visited nodes and the computational complexity decrease with increasing SNR. A 90.19% mean complexity reduction can be observed when comparing the SD soft-output detector for 10 and 0 dB in the AWGN channel. For the TIFS channel, the reduction was 90.78%, and for the TVF channel it was 84.88%. These results lead to the conclusion that the complexity of the SD softoutput detector might become affordable if the SNR takes on higher values.

Yet, since the soft-output SD detector requires finding the minimum Euclidean distances of the antipodal solutions, the number of visited nodes can be substantially higher than that for the hard-output SD detector. For SNR = 0 dB, the increase in the mean number of visited nodes is 966.85% for the AWGN channel, 845.77% for the TIFS channel, and 98.38% for the TVF channel. The number of nodes visited also increases with the deterioration of the system conditioning, i.e., the increase in distortion caused by the channel. The signal compression also increases the number of visited nodes for the hard and soft-output SD detectors. Therefore, the computational complexity is higher for the TIFS and TVF channels than for the AWGN channel.

Fig. 7 shows the number of nodes visited by the STS-SD algorithm as a function of the TVF channel gain, assuming an average SNR of 5 dB and the system parameters for frequency compression listed in Table II. As described in Table III, the TVF channel follows a complex Gaussian distribution; therefore, its power gain has an exponential distribution. Thus, most channel gain values concentrate on low values, close to zero. Additionally, histograms of visited nodes were generated for different ranges of channel gain values, as shown in Fig. 8. To improve the visualization of the visited nodes distribution, the axis related to the number of visited nodes in Fig. 8a is on a logarithmic scale. Table VII summarizes the maximum, minimum, and mean values of visited nodes obtained for each channel gain range. For gains less than 2, the maximum number of nodes in the tree was reached. This indicates that the TVF channel, combined with noise, compromised the FTN-GFDM signal to the extent that it required the STS-SD algorithm to traverse the entire search

tree. The joint analysis of Figs. 7 and 8, and Table VII provides a comprehensive understanding of the behavior of the STSSD algorithm concerning the TVF channel gain. In particular, it can be observed that lower channel gains result in a more extensive exploration of the search tree, indicating a significant sensitivity to the channel conditions. It is important to note that a TVF channel can lead to an outage state on the receiver side. In this scenario, the STS-SD will traverse many nodes but with a low probability of detecting the transmitted signal. In a practical system, this situation can be avoided by declaring an outage and dropping the content of the FTN-GFDM block, thereby reducing complexity and energy consumption.

V. CONCLUSION

In scenarios where massive MIMO and UDN are not feasible, spectral efficiency can be increased by the choice of the waveform. The FTN-GFDM waveform is flexible and capable of improving spectral efficiency over conventional GFDM and of increasing the data rate by compressing subsymbols or subcarriers without BER performance loss. The results obtained in this paper show that FTN-GFDM combined with polar codes improves waveform spectrum efficiency without introducing significant performance loss.

The SD detector can achieve BER performance similar to that achieved by the optimal detector but with less complexity and polar codes can be combined with FTN-GFDM to provide gains in BER performance with affordable complexity, improving the overall system performance with both soft and hard output SD detectors.

The soft-output SD outperforms the hard-output SD at the cost of the visitation of more nodes during tree search and, hence, higher computational complexity. Although more complex, the soft-output SD detector can have an affordable complexity mainly if the available SNR can assume high values. Thus, soft-output SD can be an interesting solution in scenarios that prioritize high spectral efficiency but the conventional high efficient techniques cannot be exploited. Also, when the complexity of soft-output cannot be supported, hard-output SD can be a good compromise. Therefore, SD allows implementations in practical systems with flexible tradeoffs between complexity and performance. In future work, we intend to analyze the integration of the soft decision SD with other state-of-the-art FEC schemes, such as low density parity check (LDPC), to achieve the best BER performance over several channel conditions. We also aim to develop other detectors that are sub-optimal and, therefore, cannot achieve the same BER performance as STS-SD or MLSE but have a very low complexity compared to these approaches.