Lattice Reduction Aided Equalizers for Multicarrier Communication

Applying Lattice Reduction to OTFS

Disclaimers

  1. This is a research project I worked on duration spring and summer of 2022, and while the results look promising for publication, I have since put it on hold because the problem itself just doesn’t seem very interesting to me.

  2. This is a short non-academic introduction to a general topic I worked on, notations are very loose.

Motivations

It is widely known that linear equalizers only collect unit multipath diversity on a number of multicarrier systems compared to optimal decoder like sphere decoder, thus losing a lot of performance. The motivation is to apply lattice reduction technique to transform the basis of equivalent channel into near orthogonal ones such that the diversity of the aided linear equalizer can be improved. Such techniques have been applied and demonstrated to work in MIMO communication, and my research was the application on orthogonal time frequency space modulation, which is a 2-D modulation that modulates the signal into delay-doppler domain.

Model

We consider OTFS modulation where symbols are carved from a lattice constellation, where a vectorized \(MN\times 1\) symbol block \(\mathbf{x}\) in delay-doppler domain is expressed as \(\mathbf{x} = \mathrm{vec}(\mathbf{X}), \mathbf{X} \in \mathbb{Z}[j]^{M\times N}\). We assume rectangular pulse-shaping, and by adopting a vector-matrix notation, symbols are modulated into time domain with inverse symplectic discrete Fourier transform (ISDFT) followed by Heisenberg transform as: \(\begin{equation} \mathbf{s} = \mathbf{A}\mathbf{\Theta}\mathbf{x} = (\mathbf{F}N^\mathcal{H}\otimes \mathbf{I}M)\mathbf{\Theta}\mathbf{x}, \end{equation}\)

where \(\mathbf{\Theta}\) is a diagonal phase rotation precoding matrix with elements chosen from set of transcendental numbers. Though OTFS collects unit diversity, this transmission scheme provably enables full diversity. Assume a sparse representation of the doubly selective channel, \(\begin{equation} h(\tau,v) = \sum_{l = 1}^{L} h_l \delta(\tau - \tau_i)\delta(v-v_i), \end{equation}\) where \(L\) is the number of path and \(h_l, v_l, \tau_l\) are complex gain, doppler and time delay of the \(l\)th path. Further, \(\tau_l = t_l/(M\Delta f)\), \(v_l = k_l/(NT)\) with \(T\Delta f\), where \(t_l\) and \(k_l\) are integers on delay-doppler grid. The equivalent \(MN\times MN\) channel matrix can be expressed as: \(\begin{equation} \mathbf{H} = \sum_{l=1}^L h_l \mathbf{\Pi}^{t_l} \mathbf{\Delta}^{k_i}, \end{equation}\) where \(\mathbf{\Pi} =\) is \(MN \times MN\) circulant matrix with first row \([0,\dots,0,1]\), \(\mathbf{\Delta} = \mathrm{diag}[e^{-j2\pi n/(MN)}, n = 0,1,\dots, MN-1]\). At the receiver, the modulation process is reversed, resulting in an equivalent input-output relationship: \(\begin{equation} \label{4} \mathbf{y} = \mathbf{H}_{equ}\mathbf{\Theta}\mathbf{x} = (\mathbf{F}_N \otimes \mathbf{I}_M) \mathbf{H} (\mathbf{F}_N^\mathcal{H}\otimes \mathbf{I}_M)\mathbf{\Theta}\mathbf{x} + \mathbf{\bar{w}}, \end{equation}\) where \(\mathbf{\bar{w}} = \mathbf{F}_N \otimes \mathbf{I}_M \mathbf{w}\), \(\mathbf{w} \in \mathcal{CN}(\mathbf{0},\sigma^2 \mathbf{I})\) is independent and identically distributed white Gaussian noise. With the observation that minimum mean square estimator (MMSE) and zero-forcing (ZF) enable same diversity through an extended system, we consider the MMSE in the form: \(\begin{equation} \mathbf{G} = \mathbf{\Theta}^\mathcal{H}\mathbf{H}_{equ}^\mathcal{H}(\frac{\sigma^2}{E_s}\mathbf{I}_N+\mathbf{H}_{equ}\mathbf{\Theta}\mathbf{\Theta}^\mathcal{H}\mathbf{H}_{equ}^\mathcal{H})\mathbf{y}, \end{equation}\) where \(E_s\) is the symbol energy.

Example: Sketch Proof that Diversity is Improved

Assume \(\mathbb{L} \in \mathbb{C}^{MN\times 1}\) is a lattice formed from set of basis \(\mathbf{H}_{equ}\mathbf{\Theta}\) with complex integer coefficients. Let \(\mathbf{h}_a = \mathbf{H}_{equ}\mathbf{\Theta}\mathbf{a}\) be a \(MN\times 1\) vector in \(\mathbb{L}\), where \(\mathbf{a} \in \mathbb{Z}[j]^{MN\times 1}\). To simplify the objective further, we use the fact that equation (\ref{4}) can be expressed as: \(\begin{align} \mathbf{y} & = \sum_{l=1}^{L} h_l (\mathbf{F}_N \otimes \mathbf{I}_M) \mathbf{\Pi}^{t_l}\mathbf{\Delta}^{k_l} (\mathbf{F}_N^\mathcal{H}\otimes \mathbf{I}_M)\mathbf{\Theta}\mathbf{x} + \mathbf{\bar{w}} \\ & = \mathbf{\Phi}(\mathbf{\Theta x}) \mathbf{h} +\mathbf{\bar{w}}, \end{align}\) where \(\mathbf{\Phi}(\mathbf{\Theta x})\) is \(MN\times L\) matrix given by \(\begin{equation} \mathbf{\Phi}(\mathbf{\Theta x}) = \begin{pmatrix} \boldsymbol{\phi}_1\mathbf{\Theta}\mathbf{x} & \boldsymbol{\phi}_2\mathbf{\Theta}\mathbf{x} & \dots & \boldsymbol{\phi}_L\mathbf{\Theta}\mathbf{x} \end{pmatrix} \end{equation}\) with \(\boldsymbol{\phi}_l = (\mathbf{F}_N \otimes \mathbf{I}_M) \mathbf{\Pi}^{t_l}\mathbf{\Delta}^{k_l} (\mathbf{F}_N^\mathcal{H}\otimes \mathbf{I}_M)\) and \(\mathbf{h}\) is the \(L \times 1\) channel impulse response with full rank covariance matrix \(\mathrm{rank}(\mathbf{hh}^\mathcal{H}) = L\) Use the above relation and let \(\mathbf{\Theta a} = \mathbf{\Theta}_a\), we have \(\begin{equation} ||\mathbf{h}_a||^2 = ||\mathbf{\Phi}(\mathbf{\Theta a})\mathbf{h}||^2 = \mathbf{h}^\mathcal{H}\mathbf{\Phi}(\mathbf{\Theta a})^\mathcal{H}\mathbf{\Phi}(\mathbf{\Theta a})\mathbf{h} \end{equation}\) Use the singular value decomposition of \(\mathbf{\Phi}(\mathbf{\Theta a})^\mathcal{H}\mathbf{\Phi}(\mathbf{\Theta a}) = \mathbf{U}\mathbf{\Lambda}\mathbf{U}^\mathcal{H}\). Given that the system collects full diversity, \(\mathrm{rank}(\mathbf{\Phi}(\mathbf{\Theta a})) = \mathrm{rank}(\mathbf{\Lambda}) = L\), and assuming \(MN > L\), we have \(\begin{equation} ||\mathbf{h}_a||^2 = \tilde{\mathbf{h}} \mathbf{\Lambda}\tilde{\mathbf{h}}^\mathcal{H} = \sum_{l = 1}^L \lambda_l^2 |\tilde{h}_l|^2, \end{equation}\) where \(\lambda_l\), \(\tilde{h}_l\) are \(l\)th eigenvalue of \(\mathbf{\Lambda}\) and \(l\)th element of \(\tilde{\mathbf{h}} = \mathbf{h}\mathbf{U}^\mathcal{H}\), respectively. Given that \(\mathrm{rank}(\mathbf{\Lambda}) = L\), \(\lambda_i \neq 0, \forall i\). Define \(\mathbf{h}_{min} = \underset{\mathbf{h} \in \mathbb{L}}{\mathrm{min}} ||\mathbf{h}||_2\), and we can subsequently bound \(||\mathbf{h}_{min}||^2\) as : \(\begin{equation} ||\mathbf{h}_{min}||^2 \geq (\underset{\mathbf{a} \in \mathbb{Z}[j]^{MN\times 1}, \mathbf{a}\neq \mathbf{0}}{\mathrm{min}} \lambda_l)(\sum_{l=1}^L |\bar{h}_l|^2) \end{equation}\) \(\begin{equation} P(||\mathbf{h}_{min}||^2 \leq \epsilon) \leq \frac{1}{2^L L!}(\underset{\mathbf{a} \in \mathbb{Z}[j]^{MN\times 1}, \mathbf{a}\neq \mathbf{0}}{\mathrm{min}} \lambda_l)^{-L} \epsilon^L \end{equation}\) Given that the probability of \(||\mathbf{h}_{min}||^2\) less than some \(\epsilon\) can be bounded exponentially with \(c \epsilon^L\), where \(c = \frac{1}{2^L L!}(\underset{\mathbf{a} \in \mathbb{Z}[j]^{MN\times 1}, \mathbf{a}\neq \mathbf{0}}{\mathrm{min}} \lambda_l)^{-L}\) is a constant, the average pairwise error probability of LR-aided LEs can be upper bounded by : \(\begin{equation} P_e \leq c (\frac{1}{c_\delta^2})^L \frac{(2L-1)!}{(L-1)!} (\frac{1}{\sigma^2})^{-L}, \end{equation}\)