# Digital Modeling on Large Kernel Metamaterial Neural Network

Quan Liu, Hanyu Zheng, Brandon T. Swartz, Ho hin Lee, Zuhayr Asad, Ivan
Kravchenko
Jason G. Valentine, Yuankai Huo Yuankai Huo is the corresponding author,
Vanderbilt University, Nashville, TN 37212, USA. E-mail:
(yuankai.huo@vanderbilt.edu)Quan Liu, Hanyu Zheng, Brandon T. Swartz, Ho hin
Lee, Zuhayr Asad, Ivan Kravchenko and Jason G. Valentine are with the
Vanderbilt University, Nashville, TN 37212, USA. E-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>jason.g.valentine@vanderbilt.edu).Ivan Kravchenko
is with Oak Ridge National Laboratory, Oak Ridge, TN 37830, USA. E-mail:
<EMAIL_ADDRESS>
###### Abstract

Deep neural networks (DNNs) utilized recently are physically deployed with
computational units (e.g., CPUs and GPUs). Such a design might lead to a heavy
computational burden, significant latency, and intensive power consumption,
which are critical limitations in applications such as the Internet of Things
(IoT), edge computing, and the usage of drones. Recent advances in optical
computational units (e.g., metamaterial) have shed light on energy-free and
light-speed neural networks. However, the digital design of the metamaterial
neural network (MNN) is fundamentally limited by its physical limitations,
such as precision, noise, and bandwidth during fabrication. Moreover, the
unique advantages of MNN’s (e.g., light-speed computation) are not fully
explored via standard 3$\times$3 convolution kernels. In this paper, we
propose a novel large kernel metamaterial neural network (LMNN) that maximizes
the digital capacity of the state-of-the-art (SOTA) MNN with model re-
parametrization and network compression, while also considering the optical
limitation explicitly. The new digital learning scheme can maximize the
learning capacity of MNN while modeling the physical restrictions of meta-
optic. With the proposed LMNN, the computation cost of the convolutional
front-end can be offloaded into fabricated optical hardware. The experimental
results on two publicly available datasets demonstrate that the optimized
hybrid design improved classification accuracy while reducing computational
latency. The development of the proposed LMNN is a promising step towards the
ultimate goal of energy-free and light-speed AI.

###### Index Terms:

large convolution kernel, model compression, model re-parameterization, meta-
material fabrication adaptation.

##  I Introduction

Digital neural networks (DNN) are essential in modern computer vision tasks.
The convolutional neural network (CNN) is arguably the most widely used AI
approach for image classification [1, 2, 3], segmentation [4, 5], and
detection [6, 7]. Even for more recent Vision Transformer-based models,
convolution is still essential components for extracting local image features
[8, 9, 10, 11, 12]. Current CNNs are typically deployed with computational
units (e.g., CPUs and GPUs). Such a design might lead to a heavy computational
burden, significant latency, and intensive power consumption, which are
critical limitations in applications such as the Internet of Things (IoT),
edge computing, and the usage of drones. Therefore, the AI community has
started to seek DNN models with less energy consumption and lower latency.
However, we might never approach energy-free and light-speed DNN following the
current trends in research.

Fortunately, the recent advances in optical computational units (e.g.,
metamaterial) have shed light on energy-free and light-speed neural networks
(Fig. 1). At its current stage, the SOTA metamaterial neural network (MNN) is
implemented as a hybrid system, where the optical processors are used as a
light-speed and energy-free front-end convolutional operator with a digital
feature aggregator. Such design reduces the computational latency since the
convolution operations are implemented by optical units, which off-loads more
than 90 percent of the floating-point operations (FLOPs) in conventional CNN
backbones like VGG [13] and ResNet [14]. However, the digital design of the
MNN is fundamentally limited by its physical structures, namely (1) the optic
system can only take positive value; (2) non-linear computations are
challenging for free-space optic devices at low light intensity; (3) the
implementation of the optical convolution is restricted by limited kernel
size, channel number, precision, noise, and bandwidth. Furthermore,
limitations also exist in the current optic fabrication process: 1) only the
first layer of a neural network can be fabricated, and 2) limited layer
capacity and weight precision. Therefore, the unique advantages of the MNNs
(e.g., light-speed computation) are not fully explored via standard 3$\times$3
convolution kernels.

In this paper, we propose a novel large kernel metamaterial neural network
(LMNN) that maximizes the digital capacity of the state-of-the-art (SOTA) MNN
with model re-parametrization and network compression, while also considering
the optical limitation explicitly. Our model maximizes the advantage of the
light-speed natural of optical computing by implementing larger convolution
kernels (e.g., 7$\times$7, 11$\times$11). The proposed LMNN yields larger
reception fields, without sacrificing low computational latency and low energy
consumption. Furthermore, the aforementioned physical limitations of LMNNs are
explicitly addressed via optimized digital modeling. We evaluate our model on
image classification tasks using two public datasets: FashionMNIST [15] and
STL-10 [16]. The proposed LMNN achieved superior classification accuracy as
compared with the SOTA MNN and model re-parametrization methods. Overall, the
system’s contributions can be summarized in four-fold:

Figure 1: This study provides a digital modeling platform for designing and
optimizing a metamaterial neural network (MNN). The proposed large kernel
metamaterial neural network (LMNN) is able to maximize the performance of an
MNN without introducing extra computational complexity during the inference
stage.

  * •

We propose the large convolution kernel design for an LMNN to achieve a larger
reception field, lower computational latency, and less energy consumption.

  * •

We introduce the model re-parameterization and multi-layer compression
mechanism to compress the multi-layer multi-branch design to a single layer
for the LMNN implementation. This maximizes the model capacity without
introducing any extra burden during the optical inference stage.

  * •

The physical limitations of LMNNs (e.g., limited kernel size, channel number,
precision, noise, non-negative restriction, and bandwidth) are explicitly
addressed via optimized digital modeling.

  * •

We implemented a one-layer LMNN with real physical metamaterial fabrication to
demonstrate the feasibility of our hybrid design.

Figure 2: The upper panel (a) shows the conventional CNN model on the image
classification task. The lower panels (b) present our proposed LMNN method
with digital design and optic implementation. The large kernel re-
parameterization efficiently achieves a large receptive field with a multi-
branch multi-layer structure. Physical constraints are modeled via the meta-
optic adaptation. The multi-branch multi-layer model is further compressed to
a single-layer LMNN. (c) The digital design is fabricated as a real meta-optic
device for inference.

##  II Related work

###  II-A Models with large kernel convolution

For a decade, a common practice in choosing optimal kernel size in convolution
is to leverage 3$\times$3 kernel. In recent years, more attention has been put
into a larger kernel design. The Inception network proposes an early design of
adapting large kernels for vision recognition tasks [17]. After developing
several variations [18, 19], large kernel models became less popular. Global
Convolution Networks (GCNs) [20] employ the large kernel idea by utilizing
1$\times$K followed by K$\times$1 to achieve improvement in model performance
for semantic segmentation.

Current limitations of leveraging large kernel convolution kernel can be
divided in two aspects: (1) scaling up the kernel sizes lead to the
degradation of model performance, and (2) its high computational complexity.
According to the Local Relation Networks (LRNet) [21], the spatial aggregation
mechanism with dynamic convolution is used to substitute traditional
convolution operation. As compared with the traditional 3$\times$3 kernels,
the LRNet [21] leverage 7$\times$7 convolution to improve model performance by
a significant margin. However, the performance become saturated by scaling up
the kernel size to 9$\times$9\. Similar to RepLKNet [11], scaling up the
convolution kernel size to 31$\times$31 without prior structural knowledge
demonstrates the decrease of model performances.

###  II-B Model compression and re-parameterization

Though many complicated ConvNets [22, 23] deliver higher accuracy than more
simple ones, the drawbacks are significant. 1) The complicated multi-branch
designs (e.g., residual addition in ResNet [14] and branch-concatenation in
Inception [18]) make the model difficult to implement and customize, and slow
down the inference and reduce memory utilization. 2) Some components (e.g.,
depthwise convolution in Xception [17] and MobileNets [24], and channel
shuffle in ShuffleNets [25]) increase memory access costs and lack support for
various devices.

Model compression [26] aims to reduce the model size and computational
complexity [27, 28] while maintaining their performance including pruning and
quantization. Pruning has been widely used to compress deep learning models by
removing the unnecessary or redundant parameters from a neural network without
affecting its accuracy [29, 30, 31]. Quantization has two categories:
Quantization-Aware Training (QAT) [32, 33] and Post-Training Quantization
(PTQ). QAT applies quantization operation in the training stage. In contrast,
PTQ takes a full precision network for training and quantized it in the post
stage [34, 35, 36].

###  II-C Optical neural network

The Optical neural network has high band width [37], uses light instead of
electrical signals to perform matrix multiplications [38, 39] which can be
much faster and more energy-efficient than traditional digital neural
networks. Most optical neural networks (ONN) use a hybrid model structure:
implement linear computation with optic device and non-linear operation
digitally [40, 41, 42, 43]. Besides the use of optical devices, ONN has been
implemented on nanophotonic circuits [44, 45] and light-wave linear
diffraction [46, 47] to improve model efficiency. For the non-linear
computation, [48, 49] have proposed implementing the non-linear operation with
the optic device on ONN.

##  III Method

Problem statement. The goal of this study is to develop a new digital learning
scheme to maximize the learning capacity of MNN while modeling the physical
restrictions of meta-optic. With the proposed LMNN, the computation cost of
the convolutional front-end can be offloaded into fabricated optical hardware,
so as to get optimal energy and speed efficiency under current fabrication
limitations. We adapt our innovations with four aspects: (1) large kernel re-
parameterization, (2) meta-optic adaptation, and (3) model compression.

Figure 3: An overview of our proposed large convolution kernel block with re-
parameterization is presented. Learnable scaling factors are employed to mimic
the scaling function of batch normalization. In the inference stage, the block
can be converted to a single convolution layer.

###  III-A Large kernel re-parameterization

To tackle the limitation of only fabricating the first layer only in CNNs, we
need to maximize the performance of the first layer, while it is feasible to
adapt the fabrication processing. With the significant progress in Vision
Transformers (ViTs), the key contribution for the performance gained is
largely credited to the large effective receptive field, which can be
generated similarly by the depthwise convolution with large kernel sizes in
CNNs. Therefore, we explore the feasibility of adapting large kernel
convolution in 1) single-branch and 2) multi-branch setting.
Single Branch Design. Inspired by [11], a large depthwise convolution kernel
is equivalently to have the same receptive fields to a stack of small kernels.
With the intrinsic structure of depthwise convolution, such a stack of kernel
weights can be compressed into a single operator. It is thus essential for the
LMNN to maximize the model performance via a relatively simple meta-optic
design, with a single compressed convolution layer. The compressed design
further introduces fewer model FLOPs in the model inference stage. For
conventional convolution operation, the convolution weight matrix
$\textbf{W}\in\mathbb{R}^{C_{i}\times C_{o}\times K_{h}\times K_{w}}$. The
$C_{i}$ and $C_{o}$ are input channel and output channel of the convolution
layer. $K_{h}$ and $K_{w}$ are height and width of convolution kernel. Denote
we have an input patch $x$ in size of $H\times W$ and the output is $y$, we
have conventional convolution as equation 1.

$y=W*x$ (1)

where $y=\sum_{p=0}^{n_{i}}W_{p}*x_{p}$, $*$ represents convolution between
matrices. For the input $x$, the computation time complexity will be
$O(H\times W\times C_{i}\times C_{o}\times K_{h}\times K_{w})$. For the
depthwise convolution model, channels $C_{i}$ in the convolution layer are
separated along with the input data channels of $x$. The depthwise convolution
follows the equation. 2

$y_{i}^{\prime}=W_{i}*x_{i}$ (2)

where $y_{i}$ is the $i$th channel of output $y$, $W_{i}$ and $x_{i}$ are the
$i$th channel from Convolution weight $W$ and input data $x$, respectively.
The time complexity is $O(H\times W\times C_{i}\times K_{h}\times K_{w})$.
Normally, the input channel number equals to the output channel number. We can
infer the theoretical speed-up ratio $r$ on model FLOPs between convention
convolution and depthwise convolution following the equation.3

$r=\frac{O(H\times W\times C_{i}\times C_{o}\times K_{h}\times
K_{w})}{O(H\times W\times C_{i}\times K_{h}\times K_{w})}=O(C_{i})$ (3)

where $C_{i}$ is the channel number of the convolution layer. Depthwise
convolution has $C_{i}=C_{o}=C$. The depthwise convolution operation saves
more FLOPs when the channel number is large compared with convention
convolution.
Multi-branch design. Inspired by RepVGG [50] and RepLKNet [11], the multi-
branch design demonstrates the feasibility of adapting large kernel
convolutions (e.g., $31\times 31$) with optimal convergence using a small
kernel convolution in parallel. The addition of the encoder output enhances
the large kernel convolution in the locality. According to the properties of
convolution operation, the abstracted feature map from the parallel
convolution path can be overlapped by learning different features. By using
different convolution kernel sizes, the features from different scales of view
are abstracted simultaneously.

We denote that output $y^{\prime}$ and input patch $x$ use a two-branch
convolution block $W$.

$y_{i}^{\prime}=W_{1}*x+W_{2}*x$ (4)

where $W_{1}$ and $W_{2}$ is two different convolution layer with different
kernel size. For multiple parallel paths, the $N$-branch convolution can be
generated as equation 5.

$y=\sum_{q=0}^{N}W_{q}*x$ (5)

According to the equation 5, output $y$ has the feature map from multiple
scales of views. The overlap of convolution output from different scale
redistributes the feature map which is proved by [11] to have better
performance.

###  III-B Meta-optic adaptation

As to integrate the large kernel convolution design into meta-optic devices,
we need to consider and model the physical restrictions explicitly in our
model design, beyond the conventional digital training (Fig. 2). First, the
weight in convolution kernel should be positive for fabrication. Second, the
convolution layer that substitutes by metalens should be the first layer of
the model. Third, metalens can only take single-channel images. Thus, all RGB
images are transferred to grayscale images. Fourth, due to the optic
implementation purpose, the size of the convolution kernel is limited. Last,
the channel number of the convolution layer is limited by the size of the
optic device capacity.

Split kernel. To keep the model convolution kernel weight positive for the
optic device implementation, we split the convolution kernel into two part:
positive weight and negative weight. As shown in Fig.4, the final convolution
kernel results are the subtraction of the two feature map from the positive
and negative convolution kernel respectively.

Remove non-linear layer. In traditional convolution operation, non-linear
layer is typically added between the convolution layers. The non-linear layer,
including batch normalization and activation layers (eg. ReLU) introduce the
non-linear transformation to the model. However, they are not able to be
implemented with our meta-optic device. As shown in Fig.4, the non-linear
layers are removed from the parallel convolution branch and connected behind
the large kernel convolution layer.

Non-negative weight in optic kernel In traditional deep learning model, both
positive weights and negative weights are stored. The meta-optic model
implementation can only take positive kernel weights. Adaptation methods are
applied to convolution model training to constrain model weight to a positive
value. Four methods are introduced in model training: square of trigonometric
functions, mask out the negative value, add non-negative loss, and our
proposed kernel split.

Square of trigonometric function: instead of directly updating the weight, we
define weight as equation 6. The weight $W_{i}$ keeps positive and in range
$[0,1]$ whatever the value of $\theta$.

$W_{i}=Sin^{2}(\theta_{i})$ (6)

Mask out the negative value: in the training process, the weight smaller than
0 is assigned as 0 manually after each iteration update.

Add non-negative loss: to maintain the model weight positive, a non-negative
weight loss is add to the loss function, which is defined as equation 7.

$loss=\sum(model.weight<0)$ (7)

Figure 4: Adaptation for meta-optic implementation. (a) To implement the
kernel with negative weight, we split the kernel into the positive kernel and
negative kernel and subtract from their feature map. (b) The non-linear layer
needs to be removed from the parallel convolution path.

Bandwidth and precision. Due to the accuracy of the current fabrication of
meta-optic, the optical inference might lose precision. As a result, the model
bandwidth and weight precision should also be modeled during the training
process. For example, PyTorch has a default 32-bit precision, which is not
feasible for the LMNN. Thus, the quantize is employed to simulate the model
performance when all digital neural networks are implemented with optic
devices. Taking the noise in optic implementation into consideration, which
will affect the model weights precision, we add the Gaussian noise to the
digital convolution weight.

###  III-C Model compression

The stacked depthwise convolution and re-parameterization can potentially
improve the model performance by learning with variance. The multilayer
structure can be regarded as multiple stacked depthwise convolution layers
which make the model deeper. The multi-branch structure will make the model
wider. It is obvious the designed model is in a complex structure. To save
image processing time in the inference stage, the multiplayer structure can be
squeezed into a single layer. In this paper, we only explore the squeezed
convolution layer. To get the equivalent squeezed layer, a non-linear
component should be eliminated. The non-linear layers such as activation
function and batch normalization are moved out of our squeezed block. The
stacked convolution kernel follows the equation 8.

$\displaystyle y=$
$\displaystyle(W_{N}*(W_{N-1}*\dots\dots\dots(W_{2}*W_{1})))*x$ (8)
$\displaystyle=$ $\displaystyle W^{*}*x$

$W^{*}=(W_{N}*(W_{N-1}*\dots\dots\dots(W_{2}*W_{1})))$ (9)

$W^{*}$ is the equivalent weight to the stacked setting in equation 9. As the
number of stacked convolution layers increases, the equivalent convolution
kernel is larger. The equivalent kernel size k and the number of stacked
$3\times 3$ convolution layer n follow equation 10.

$k=2\times n+1$ (10)

For example, two 3$\times$3 convolution kernels are equivalent to a 5$\times$5
convolution kernel. The multi-branch convolution layer can be compressed as
shown in Fig 3.

Since the convolution kernel value from the different parallel branches is
equivalent to a single kernel by overlapping kernel, a multi-parallel
convolution branch can be compressed into a single path.

##  IV Data and experimental design

Figure 5: The meta-optic devices simulation and implementation platform. (a)
Optic system for meta-optic lens test. The components in the figure are: Light
source: Tungsten Lamp; filter: Wavelength filter; Pol: Polarizer; SLM: Spatial
light modulator; Condenser: Lens to focus light on the SLM; MSs: Metasurfaces;
Ob: Objective lens. (b) Measured meta-optic kernel weight point spread
function, used for optical convolution with the imaged object. (c) Theoretical
meta-optic kernel weight point spread function by simulation.

###  IV-A Data description

Two public datasets, FashionMNIST [15] and STL10 [16], were employed to
evaluate the performance of the proposed method on image classification tasks.
For the FashionMNIST dataset, we employed 60,000 images for training and
10,000 images for testing. The images were grayscale images in the size of 28
$\times$ 28\. FashionMNIST was inspired by the MNIST dataset, which classified
clothing images rather than digits. We employed STL-10 as another cohort with
a larger input image size (96$\times$96). In our experiments, the RGB images
in STL-10 were transferred to grayscale images due to the physical limitation
in the LMNN.

###  IV-B Large kernel re-parameterization

We proposed the large re-parameterized convolution kernel design in our LMNN
network to maximize the computational performance of the precious single
metamaterial layer by (1) taking advantage of high-speed light computation,
and (2) overcoming the physical limitations in an MNN implementation.

To evaluate the large re-parameterized convolution kernel on FashionMNIST, we
constructed a naive model that consisted of a large re-parameterized
convolution kernel block, a single fully connected layer, as well as non-
linear components (ReLU activation, batch normalization, and the softmax
function). Different re-parameterization model structures were evaluated. To
demonstrate the impacts of the size, the kernel was tested from 3$\times$3 to
31$\times$31\. Besides the kernel size, we evaluated multiple numbers of
parallel branches: from a single path to four paths.

###  IV-C Meta-optic model adaptation

The performance of the LMNN is fundamentally limited by physical restrictions.
We provide the model simulation by modeling optic system limitations. In
regards to the model limitations, the convolution kernel is implemented with
optical devices that can only have limited channels. To include the meta-optic
devices in our network, the layer that is to be substituted should be the
first layer of our model. The following model structure can be designed
digitally. To validate model design on different sizes, deep neural networks
with multiple convolution layers are implemented.

To simulate the noise in real meta-optic fabrication, we add random noise
following the Gaussian distribution. To test the impact of noise level, we
simulate the noise amplitude range from 0.05 to 0.2. Considering the meta-
optic implementation on the whole model for further research, we quantize the
model weight in 8-bit instead of the default 32-bit.

In order to evaluate the non-negative weight effect, three methods are
evaluated to constrain the model weight positive. ’Sin’ in Fig. 8(a) means
weights are defined by square of sin function. ’Mask out’ is to eliminate the
negative weight by screening out. Loss function is also used to define model
with positive weights, which results is shown in Fig. 8(a) as ’Non-neg’ loss.

The large kernel convolution design is validated on fabricated meta-optic
devices. Based on the well-trained digital convolution kernel weight, meta-
optic lenses are implemented and tested in real optic systems shown in Fig. 5.

###  IV-D Model compression efficiency

Through model compression, the model in the inference stage alleviates the
computation load with lighter weights. The fabricated convolution kernel by a
meta-optic lens with the digital backend is assembled as the hybrid model. We
test the model’s inference time by feeding the same image and recording the
model’s processing time.

To test the optimal LMNN structure under the meta-optic fabrication
limitation, the combination of layer numbers from one to five and channel
numbers from nine to twenty. The model digital computation load (FLOPs) and
the ratio of meta-optic is computed to find the model structure achieves
optimal efficiency.

##  V Result

In this section, we first evaluate our proposed large kernel network with a
simple model structure, using the FashionMNIST dataset and STL-10 dataset. We
then evaluate the large kernel capability on complex convolution neural
networks with the same dataset.

TABLE I: Large re-parameterized convolution experiment results

| FashionMNIST | STL-10
---|---|---
| Model Conv | Test | Model Conv | Test
Naive model | 3$\times$3 | 0.8495 | 3$\times$3 | 0.4500
RepLKNet [11] | 7$\times$7 | 0.9015 | 7$\times$7 | 0.4993
|  |  | 11$\times$11 | 0.5241
RepVGG [50] | 7+5+3 | 0.9081 | 7+5+3 | 0.5341
|  |  | 11+9+7 | 0.5650
Depthwise conv [17] | 3 dwc | 0.9084 | 3 dwc | 0.5509
|  |  | 5 dwc | 0.5935
LMNN (Ours) | 3 dwc + 2 dwc + 1 dwc | 0.9115 | 5 dwc + 3 dwc + 1 dwc | 0.6120

11footnotetext: ’dwc’ refer to the depthwise convolution layer, convolution
kernel size is $3\times 3$

###  V-A Large re-parameterized convolution performance

We evaluate the large re-parameterized convolution model on two datasets:
FashionMNIST and STL-10. As shown in Table. I, the naive model with 7$\times$7
convolution kernels has demonstrated better performance than that with
$3\times 3$. With structural reparameterization, the model prediction accuracy
further improves. Meanwhile, the model implemented with a depthwise
convolution layer outperformed the baselines with both small and large
convolution kernels.

Our large kernel model is evaluated on the STL10 dataset with a larger image
size (96$\times$96). As compared with performance on FashionMNIST (image size
30$\times$30), the large kernel convolution model reveals greater
improvements, as shown in Table. I. The model with 11$\times$11 kernel size
has better accuracy (0.5341) compared with that of using 3$\times$3 and
7$\times$7\. By integrating the depthwise convolution design, the model
performance boosts from 0.5241 to 0.5935. Our proposed large kernel block
outperforms all SOTA approaches and achieves the best accuracy of 0.6015 with
teacher model supervised training.

To further validate our large kernel with depthwise convolution design, we
conduct experiments on more sophisticated models by replacing all convolution
layers with the large re-parameterized convolution layers. Briefly,
WideResNet-101 is used as complex model backbone [51]. Model performance is
shown in Table. 6. By substituting the first convolution layer with a larger
kernel size, the model performance improves from 0.94 to 0.96 with utilizing
larger images (256$\times$256 RGB).

Figure 6: Large convolution WideResNet-101 model performance on STL-10. Figure
7: (a) The large re-parameterized convolution model performance with different
layer numbers and channel numbers. (b) Large convolution kernel efficiency
evaluation. The circle in different colors shows different convolution layer
structures. The shadow area is the model structure that can be fabricated. The
circle area shows the FLOPs ratio of the layer implemented by meta-optic
material. x-axis is the model FLOPs except the layer to be fabricated. (c)
Model inference time between the digital model and hybrid model. The orange
shadow area in the figure shows the time used by the model rest part except
the large convolution kernel layer.

###  V-B Performance of model adaptation

To validate our large kernel design on the real metasurface fabrication model
shown in Fig. 5, we implement a model trained on FashionMNIST with a large
kernel design, utilizing a digital design for comparison. The digital
convolution layer has 12 channels 7$\times$7 convolution kernel which is the
optimal kernel design under the current meta-optic implement limitation. As
shown in Table.II, the Metamaterial Neural Network demonstrates excellent
consistency with the theoretical performance of a digital neural network.

TABLE II: Metasurface fabrication Method | Test
---|---
Digital Neural Network (DNN) | 0.9015
Large Kernel MNN (LMNN) | 0.8760

Due to the meta-optic implementation limitation, four adaptation methods are
applied to constrain kernel weights to positive. According to the model
performance, our proposed kernel split method shows superior performance over
the common training strategies.

###  V-C Ablation studies

To validate our model bandwidth and weight precision limit simulation, the
results of the experiment are shown in Table 8.

To evaluate the upper bound performance on FashionMNIST, a deep model
structure is implemented and tested on FashionMNIST. The number of convolution
layers in our model range from 1 to 5, and the channel number ranges from 9 to
30. The model performance is shown in Fig. 7 (a). The model with more
parameters shows a higher accuracy. Regardless of the meta-optic fabrication
limitation, the meta-optic hybrid model achieves better performance.

Figure 8: Plot of ablation study on LMNN. (a) Evaluating non-negative weight
effect on model performance. (b) Measuring the effect of model bandwidth and
weight precision effect on model prediction accuracy. ’Pr’ in Figure (b) means
precision.

###  V-D LMNN efficiency and speed evaluation

To evaluate the model on both speed and computation load, we compute the model
FLOPs except the large convolution layer and the FLOPs ratio of the layer
implemented by meta-optic material. The model performance with different
structure is shown in Fig. 7 (b). The optimal model structure should at top
left corner in shadow area. As shown, the model with 1 large re-parameterized
convolution layer and 12 channels is the optimal structure. To show the speed
advantage of our LMNN, the model inference time is recorded. From Fig. 7 (c),
the hybrid model shows a speed twice fast as compared to the digital
convolution model.

##  VI Discussion

In this work, we present a convolution block with a large kernel design that
generates larger receptive fields to maximize the digital capacity of LMNN. To
validate the large kernel convolution design, we further applied the block to
a complex model such as WideResNet-101. From the experiments, two important
components contribute to the improvement of large kernel design from
traditional 3$\times$3 kernel size. First, the larger convolution kernel can
get larger receptive fields. According to the target image size, the
convolution kernel size is not the larger the better. For the FashionMNIST in
size of 30$\times$30, 7$\times$7 is the best kernel size. For the images from
STL-10 dataset in size of 96$\times$96, 11$\times$11 kernel performed the
best. Another interesting point is the stacked depthwise convolution layers
have equivalent computing operations to the single convolution layer with a
larger kernel size. The multi-layer depthwise convolution and multi-branch
structure expand the model capacity without parameter increase.

Since the large convolution kernel achieved superior performance on image
classification task, more computer vision tasks have the improvement
potential. For the image segmentation task, it can be regarded as a pixel-
level classification problem. The large convolution design can be applied on
segmentation tasks. Object detection can be another choice for large
convolution kernel application. Different size of convolution kernel provides
multiple field of views. The views from multiple scale can abstract
representation with more spatial information.

##  VII Conclusion

In this paper, we present a large-kernel convolution block and implementation
on meta-optic lens. The evaluation is conducted on FashionMNIST and STL-10
dataset. We revisit the model design of a metamaterial neural network by
modeling the physical restrictions explicitly. Our proposed LMNN outperformed
the benchmarks on both datasets. Moreover, the computational latency is
reduced by using light-speed optical convolution.

## Acknowledgment

HZ BTS and JGV acknowledge support from DARPA under contract HR001118C0015,
NAVAIR under contract N6893622C0030 and ONR under contract N000142112468. YH
and QL acknowledge support from NIH under contract R01DK135597. YH is the
corresponding author.

## References

  * [1] Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel, “Backpropagation applied to handwritten zip code recognition,” _Neural computation_ , vol. 1, no. 4, pp. 541–551, 1989.
  * [2] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” _Communications of the ACM_ , vol. 60, no. 6, pp. 84–90, 2017.
  * [3] Q. Li, W. Cai, X. Wang, Y. Zhou, D. D. Feng, and M. Chen, “Medical image classification with convolutional neural network,” in _2014 13th international conference on control automation robotics & vision (ICARCV)_. IEEE, 2014, pp. 844–848.
  * [4] D. Jha, M. A. Riegler, D. Johansen, P. Halvorsen, and H. D. Johansen, “Doubleu-net: A deep convolutional neural network for medical image segmentation,” in _2020 IEEE 33rd International symposium on computer-based medical systems (CBMS)_. IEEE, 2020, pp. 558–564.
  * [5] O. Ronneberger, P. Fischer, and T. Brox, “U-net: Convolutional networks for biomedical image segmentation,” in _Medical Image Computing and Computer-Assisted Intervention–MICCAI 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part III 18_. Springer, 2015, pp. 234–241.
  * [6] R. Chauhan, K. K. Ghanshala, and R. Joshi, “Convolutional neural network (cnn) for image detection and recognition,” in _2018 first international conference on secure cyber computing and communication (ICSCCC)_. IEEE, 2018, pp. 278–282.
  * [7] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi, “You only look once: Unified, real-time object detection,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 779–788.
  * [8] Z. Liu, Y. Lin, Y. Cao, H. Hu, Y. Wei, Z. Zhang, S. Lin, and B. Guo, “Swin transformer: Hierarchical vision transformer using shifted windows,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 10 012–10 022.
  * [9] W. Wang, E. Xie, X. Li, D.-P. Fan, K. Song, D. Liang, T. Lu, P. Luo, and L. Shao, “Pyramid vision transformer: A versatile backbone for dense prediction without convolutions,” in _Proceedings of the IEEE/CVF international conference on computer vision_ , 2021, pp. 568–578.
  * [10] Z. Liu, H. Mao, C.-Y. Wu, C. Feichtenhofer, T. Darrell, and S. Xie, “A convnet for the 2020s,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 11 976–11 986.
  * [11] X. Ding, X. Zhang, J. Han, and G. Ding, “Scaling up your kernels to 31x31: Revisiting large kernel design in cnns,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 11 963–11 975.
  * [12] S. Liu, T. Chen, X. Chen, X. Chen, Q. Xiao, B. Wu, M. Pechenizkiy, D. Mocanu, and Z. Wang, “More convnets in the 2020s: Scaling up kernels beyond 51x51 using sparsity,” _arXiv preprint arXiv:2207.03620_ , 2022.
  * [13] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” _arXiv preprint arXiv:1409.1556_ , 2014.
  * [14] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [15] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” _arXiv preprint arXiv:1708.07747_ , 2017.
  * [16] A. Coates, A. Ng, and H. Lee, “An analysis of single-layer networks in unsupervised feature learning,” in _Proceedings of the fourteenth international conference on artificial intelligence and statistics_. JMLR Workshop and Conference Proceedings, 2011, pp. 215–223.
  * [17] F. Chollet, “Xception: Deep learning with depthwise separable convolutions,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 1251–1258.
  * [18] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich, “Going deeper with convolutions,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 1–9.
  * [19] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna, “Rethinking the inception architecture for computer vision,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 2818–2826.
  * [20] C. Peng, X. Zhang, G. Yu, G. Luo, and J. Sun, “Large kernel matters–improve semantic segmentation by global convolutional network,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 4353–4361.
  * [21] H. Hu, Z. Zhang, Z. Xie, and S. Lin, “Local relation networks for image recognition,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2019, pp. 3464–3473.
  * [22] F. Iandola, M. Moskewicz, S. Karayev, R. Girshick, T. Darrell, and K. Keutzer, “Densenet: Implementing efficient convnet descriptor pyramids,” _arXiv preprint arXiv:1404.1869_ , 2014.
  * [23] G. Huang, S. Liu, L. Van der Maaten, and K. Q. Weinberger, “Condensenet: An efficient densenet using learned group convolutions,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 2752–2761.
  * [24] A. G. Howard, M. Zhu, B. Chen, D. Kalenichenko, W. Wang, T. Weyand, M. Andreetto, and H. Adam, “Mobilenets: Efficient convolutional neural networks for mobile vision applications,” _arXiv preprint arXiv:1704.04861_ , 2017.
  * [25] X. Zhang, X. Zhou, M. Lin, and J. Sun, “Shufflenet: An extremely efficient convolutional neural network for mobile devices,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 6848–6856.
  * [26] Y. Cheng, D. Wang, P. Zhou, and T. Zhang, “Model compression and acceleration for deep neural networks: The principles, progress, and challenges,” _IEEE Signal Processing Magazine_ , vol. 35, no. 1, pp. 126–136, 2018.
  * [27] V. Vanhoucke, A. Senior, and M. Z. Mao, “Improving the speed of neural networks on cpus,” 2011.
  * [28] W. Chen, J. Wilson, S. Tyree, K. Weinberger, and Y. Chen, “Compressing neural networks with the hashing trick,” in _International conference on machine learning_. PMLR, 2015, pp. 2285–2294.
  * [29] S. Srinivas and R. V. Babu, “Data-free parameter pruning for deep neural networks,” _arXiv preprint arXiv:1507.06149_ , 2015.
  * [30] S. Han, J. Pool, J. Tran, and W. Dally, “Learning both weights and connections for efficient neural network,” _Advances in neural information processing systems_ , vol. 28, 2015.
  * [31] Y. He, X. Zhang, and J. Sun, “Channel pruning for accelerating very deep neural networks,” in _Proceedings of the IEEE international conference on computer vision_ , 2017, pp. 1389–1397.
  * [32] Y. Gong, L. Liu, M. Yang, and L. Bourdev, “Compressing deep convolutional networks using vector quantization,” _arXiv preprint arXiv:1412.6115_ , 2014\.
  * [33] J. Wu, C. Leng, Y. Wang, Q. Hu, and J. Cheng, “Quantized convolutional neural networks for mobile devices,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 4820–4828.
  * [34] Z. Liu, Y. Wang, K. Han, W. Zhang, S. Ma, and W. Gao, “Post-training quantization for vision transformer,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 28 092–28 103, 2021.
  * [35] J. Fang, A. Shafiee, H. Abdel-Aziz, D. Thorsley, G. Georgiadis, and J. H. Hassoun, “Post-training piecewise linear quantization for deep neural networks,” in _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part II 16_. Springer, 2020, pp. 69–86.
  * [36] Y. Li, R. Gong, X. Tan, Y. Yang, P. Hu, Q. Zhang, F. Yu, W. Wang, and S. Gu, “Brecq: Pushing the limit of post-training quantization by block reconstruction,” _arXiv preprint arXiv:2102.05426_ , 2021.
  * [37] G. Zhou and D. Z. Anderson, “Acoustic signal recognition with a photorefractive time-delay neural network,” _Optics letters_ , vol. 19, no. 9, pp. 655–657, 1994.
  * [38] L. Larger, M. C. Soriano, D. Brunner, L. Appeltant, J. M. Gutiérrez, L. Pesquera, C. R. Mirasso, and I. Fischer, “Photonic information processing beyond turing: an optoelectronic implementation of reservoir computing,” _Optics express_ , vol. 20, no. 3, pp. 3241–3249, 2012.
  * [39] F. Duport, B. Schneider, A. Smerieri, M. Haelterman, and S. Massar, “All-optical reservoir computing,” _Optics express_ , vol. 20, no. 20, pp. 22 783–22 795, 2012.
  * [40] S. Jutamulia and F. Yu, “Overview of hybrid optical neural networks,” _Optics & Laser Technology_, vol. 28, no. 2, pp. 59–72, 1996.
  * [41] Y. Paquot, F. Duport, A. Smerieri, J. Dambre, B. Schrauwen, M. Haelterman, and S. Massar, “Optoelectronic reservoir computing,” _Scientific reports_ , vol. 2, no. 1, p. 287, 2012.
  * [42] D. Woods and T. J. Naughton, “Photonic neural networks,” _Nature Physics_ , vol. 8, no. 4, pp. 257–259, 2012.
  * [43] T. W. Hughes, M. Minkov, Y. Shi, and S. Fan, “Training of photonic neural networks through in situ backpropagation and gradient measurement,” _Optica_ , vol. 5, no. 7, pp. 864–871, 2018.
  * [44] Y. Fang and M. Sun, “Nanoplasmonic waveguides: towards applications in integrated nanophotonic circuits,” _Light: Science & Applications_, vol. 4, no. 6, pp. e294–e294, 2015.
  * [45] Y. Shen, N. C. Harris, S. Skirlo, M. Prabhu, T. Baehr-Jones, M. Hochberg, X. Sun, S. Zhao, H. Larochelle, D. Englund _et al._ , “Deep learning with coherent nanophotonic circuits,” _Nature photonics_ , vol. 11, no. 7, pp. 441–446, 2017.
  * [46] Y. B. Ovchinnikov, J. Müller, M. Doery, E. Vredenbregt, K. Helmerson, S. Rolston, and W. Phillips, “Diffraction of a released bose-einstein condensate by a pulsed standing light wave,” _Physical review letters_ , vol. 83, no. 2, p. 284, 1999.
  * [47] X. Lin, Y. Rivenson, N. T. Yardimci, M. Veli, Y. Luo, M. Jarrahi, and A. Ozcan, “All-optical machine learning using diffractive deep neural networks,” _Science_ , vol. 361, no. 6406, pp. 1004–1008, 2018.
  * [48] J. George, R. Amin, A. Mehrabian, J. Khurgin, T. El-Ghazawi, P. R. Prucnal, and V. J. Sorger, “Electrooptic nonlinear activation functions for vector matrix multiplications in optical neural networks,” in _Signal Processing in Photonic Communications_. Optica Publishing Group, 2018, pp. SpW4G–3.
  * [49] M. Miscuglio, A. Mehrabian, Z. Hu, S. I. Azzam, J. George, A. V. Kildishev, M. Pelton, and V. J. Sorger, “All-optical nonlinear activation function for photonic neural networks,” _Optical Materials Express_ , vol. 8, no. 12, pp. 3851–3863, 2018.
  * [50] X. Ding, X. Zhang, N. Ma, J. Han, G. Ding, and J. Sun, “Repvgg: Making vgg-style convnets great again,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 13 733–13 742.
  * [51] H. D. Kabir, M. Abdar, A. Khosravi, S. M. J. Jalali, A. F. Atiya, S. Nahavandi, and D. Srinivasan, “Spinalnet: Deep neural network with gradual input,” _IEEE Transactions on Artificial Intelligence_ , 2022.


# Truncated Turbo Equalizer with SIC for OTFS

Sanoopkumar P. S., Stephen McWade, Arman Farhang  Department of Electronic &
Electrical Engineering, Trinity College Dublin, Ireland
{pungayis, smcwade<EMAIL_ADDRESS>
###### Abstract

Orthogonal time frequency space (OTFS) is a promising candidate waveform for
the next generation wireless communication systems. OTFS places data in the
delay-Doppler (DD) domain, which simplifies channel estimation in high-
mobility scenarios. However, due to the 2-D convolution effect of the time-
varying channel in the DD domain, equalization is still a challenge for OTFS.
Existing equalizers for OTFS are either highly complex or they do not consider
intercarrier interference present in high-mobility scenarios. Hence, in this
paper, we propose a novel two-stage detection technique for coded OTFS
systems. Our proposed detector brings orders of magnitude computational
complexity reduction compared to existing methods. At the first stage, it
truncates the channel by considering only the significant coefficients along
the Doppler dimension and performs turbo equalization. To reduce the
computational load of the turbo equalizer, our proposed method deploys the
modified LSQR (mLSQR) algorithm. At the second stage, with only two successive
interference cancellation (SIC) iterations, our proposed detector removes the
residual interference caused by channel truncation. To evaluate the
performance of our proposed truncated turbo equalizer with SIC (TTE-SIC), we
set the minimum mean squared error (MMSE) equalizer without channel truncation
as a benchmark. Our simulation results show that the proposed TTE-SIC
technique achieves about the same bit error rate (BER) performance as the
benchmark.

##  I Introduction

In recent years, orthogonal time frequency space modulation (OTFS) has emerged
as a highly promising candidate waveform for the next generation wireless
communication systems [1]. OTFS is an attractive candidate due to its high
resilience to the Doppler spread in high-mobility environments, where the
wireless channel is time-varying. In contrast to orthogonal frequency division
multiplexing (OFDM), which multiplexes the modulated data symbols in the time-
frequency (TF) domain, OTFS transmits data symbols in delay-Doppler (DD)
domain [2]. The channel in the DD domain varies much more slowly than in the
TF domain, which allows for channel estimation to be performed with a small
pilot overhead, even in high-mobility scenarios [3]. Despite this, channel
equalization and data detection for OTFS are challenging tasks due to the 2D
convolution effect of the time-varying channel [4].

There exists a large body of literature on equalization and detection for OTFS
[5, 6, 7, 8, 9, 10, 11]. However, only a small number of these works consider
a coded system [9, 10, 11], which is the topic of interest to this paper. With
regards to coded OTFS, the authors of [9] developed an iterative parallel
interference cancellation (PIC) detection scheme applicable to orthogonal
precoded TF modulations. An iterative linear minimum mean squared error with
PIC (LMMSE-PIC) equalizer was developed in [10]. This method makes use of
component-wise conditionally unbiased LMMSE estimator (CWCU-LMMSE) and first
order Neumann series approximation. However, in [9] and [10], the channel is
assumed to be locally time invariant across a block of samples. In high-
mobility scenarios, where the channel is highly time-varying, due to the
presence of inter-carrier interference (ICI), this assumption becomes invalid.
Therefore, these methods suffer from performance penalty or MMSE equalization
becomes highly complex in tackling the ICI issue. In [11], the authors
investigated the performance of low-density parity check (LDPC) coded OTFS.
However, the technique proposed in [11] relies on hard decision output from
the LDPC decoder, and is therefore prone to error propagation. The authors of
[12] proposed a turbo receiver which uses a sparsified correlation matrix to
implement MMSE equalization with reduced complexity. However, this method uses
the computationally complex factorized sparse approximate inverse (FSPAI)
algorithm which limits its use in practical scenarios.

Figure 1: Block diagram of the proposed TTE-SIC receiver.

Hence, the existing methods in the literature do not provide a low complexity
practical data detection method in high-mobility scenarios. To address this
shortcoming, we propose a novel low-complexity truncated turbo equalizer with
successive interference cancellation (TTE-SIC) for coded OTFS. Our proposed
method has two stages; in the first stage, we reduce the equalization
complexity by truncating the channel. For channel truncation, we introduce a
criterion based on the maximum Doppler shift. To further reduce complexity, we
utilize the low-complexity modified LSQR (mLSQR) algorithm from [13]. With
this approach, we obtain the soft estimate of the transmitted symbols and the
post-equalization signal to interference noise ratio (SINR) information. Using
the output from mLSQR, we derive expressions for the log-likelihood ratios
(LLRs) for soft-output detection. In the second stage, we compensate for the
performance loss due to channel truncation with a low-complexity SIC procedure
using the channel coefficients remaining after truncation. We evaluate our
proposed method via simulations and show that after only two SIC iterations,
it achieves similar bit error rate (BER) performance as our benchmark, i.e.,
MMSE equalization without channel truncation. We analyze and compare the
computational complexity of our proposed technique with the existing
literature. We calculate expressions for computational load in terms of the
number of complex multiplications (CMs). We show that our proposed technique
has around $10^{4}$ and $10$ times lower complexity than our benchmark and the
simplest method in the literature, respectively.

The rest of this paper is organized as follows. In Section II, we introduce
the system model under consideration. The proposed TTE-SIC and its
computational complexity analysis are provided in Section III. The simulation
results are presented in Section IV and the paper is concluded in Section V.

Notations: Superscripts ${(\cdot)^{\rm{T}}}$ and ${(\cdot)^{\rm{H}}}$ denote
transpose and Hermitian, respectively. Bold lower-case characters are used to
denote vectors and bold upper-case characters are used to denote matrices.
$x[n]$ denotes the $n$-th element of the vector $\mathbf{x}$. The function
$\rm{vec}(\mathbf{X})$ vectorizes the matrix $\mathbf{X}$ by stacking its
columns to form a single column vector, and $\otimes$ represents the Kronecker
product. The $p\times{p}$ identity matrix and $p\times q$ all-zero matrix are
denoted by $\mathbf{I}_{p}$ and $\mathbf{0}_{p\times{q}}$, respectively.

##  II System Model

We consider a coded OTFS system with $M$ delay bins, $N$ Doppler bins, and a
$\frac{k}{r}$ rate forward error correction (FEC) code. At the transmitter,
the FEC encoder converts the information bits,
${\mathbf{b}}\in\\{0,1\\}^{MNk}$ to ${\mathbf{c}}\in\\{0,1\\}^{MNr}$ coded
bits. After bit-wise interleaving, the coded bits are mapped onto
$Q=2^{r}-$QAM modulation constellation to form the DD domain transmit data
symbols ${\mathbf{x}}\in\mathbb{C}^{MN\times 1}$. After symbol-wise
interleaving, the DD domain data symbols are rearranged as the $M\times N$
matrix $\mathbf{X}$. In this paper, we consider the full cyclic prefix (CP)
OTFS system in which a CP is appended at the beginning of each block of $M$
samples in the delay-time (DT) domain. The DT domain transmit signal is formed
by taking $N$-point IDFT across the Doppler dimension, i.e., the rows of
$\mathbf{X}$. Therefore, the OTFS transmit signal is given by
$\mathbf{S}={\mathbf{A}_{\rm{cp}}}\mathbf{X}\mathbf{F}_{N}^{\rm{H}},$ where
$\mathbf{F}_{N}$ is the $N$-point unitary discrete Fourier transform (DFT)
matrix with $(l,k)$ elements $\frac{1}{\sqrt{N}}e^{-j\frac{2\pi}{N}lk}$ for
$l,k=0,\ldots,N-1$.
${\mathbf{A}_{\rm{cp}}}=\left[\mathbf{J}_{\rm{cp}},\mathbf{I}_{M}\right]$ is
the CP addition matrix where $\mathbf{J}_{\rm{cp}}$ is composed of the last
$M_{\mathrm{cp}}$ rows of $\mathbf{I}_{M}$. After parallel to serial
conversion, the time-domain signal is represented in vectorized form as

$\mathbf{s}={\rm
vec}(\mathbf{S})=(\mathbf{F}_{N}^{\rm{H}}\otimes\mathbf{A}_{\rm{cp}})\mathbf{x},$
(1)

where $\mathbf{x}=\rm{vec}(\mathbf{X})$. The transmit signal then undergoes
analog to digital conversion and is transmitted through the LTV channel. The
continuous time received signal is thus represented by $r(t)=\int\int
h(\tau,\nu)s(t-\tau)e^{j2\pi\nu(t-\tau)}d\tau d\nu+\eta(t)$, where
$h(\tau,\nu)=\sum_{p=0}^{P-1}h_{p}\delta(\tau-\tau_{p})\delta(\nu-\nu_{p}),$
is the DD domain channel impulse response (CIR), which consists of $P$ channel
paths, and $\eta(t)$ is the complex additive white Guassian noise (AWGN) with
variance $\sigma^{2}$. The parameters $h_{p}$, $\tau_{p}$ and $\nu_{p}$
represent the channel gain, delay and Doppler shift associated with path $p$
of the channel, respectively.

The received signal is then sampled with sampling period $T_{\rm{s}}$ to
obtain the discrete-time received signal, given by

$\mathbf{r}=\mathbf{H}_{\rm{DT}}\mathbf{s}+\boldsymbol{\eta}_{\rm{DT}},$ (2)

where $\boldsymbol{\eta}_{\rm{DT}}$ is the $MN\times 1$ AWGN vector and
$\mathbf{H}_{\rm{DT}}$ is the $MN\times MN$ DT domain channel matrix. The
received signal is then demodulated and converted back to the DD domain by
performing an $N$-point DFT operation across the time-domain samples. Thus,
the received signal is given by
$\mathbf{y}=(\mathbf{F}_{N}\otimes\mathbf{R}_{\mathrm{cp}})\mathbf{r}.$ This
can be alternatively expressed as

$\mathbf{y}_{\rm
DD}=\mathbf{H}_{\rm{DD}}\mathbf{x}+\boldsymbol{\eta}_{\rm{DD}},$ (3)

where
$\mathbf{H}_{\rm{DD}}=(\mathbf{F}_{N}\otimes\mathbf{R}_{\rm{cp}})\mathbf{H}_{\rm{DT}}(\mathbf{F}_{N}^{\rm{H}}\otimes\mathbf{A}_{\rm{cp}})$
is the effective DD domain channel matrix,
$\mathbf{R}_{\rm{cp}}=\left[\mathbf{0}_{M\times
M_{\rm{cp}}},\mathbf{I}_{M}\right]$ is the CP removal matrix and
$\boldsymbol{\eta}_{\rm{DD}}=(\mathbf{F}_{N}\otimes\mathbf{R}_{\rm{cp}})\boldsymbol{\eta}_{\rm{DT}}$
is the DD domain noise vector.

##  III Proposed Joint Equalization and Decoding

In this section, we present our proposed equalization and detection technique,
as shown in Fig. 1. Our proposed technique has two-stages. In the first stage,
we reduce the equalization complexity by truncating the DD domain channel
matrix along the Doppler dimension to only include the significant Doppler
coefficients. In the second stage, we deploy SIC to remove the residual
interference caused by the channel truncation. Furthermore, in the first
stage, we use the low-complexity mLSQR algorithm from [13] to equalize the
channel, obtain the soft estimate of the transmitted symbols and find the
post-equalization SINR information. We use the output of the mLSQR algorithm
to derive expressions for the extrinsic log-likelihood ratios for soft-output
detection. In the following subsections, we provide a detailed explanation of
the stages of our proposed technique, beginning with the channel truncation.

###  III-A Channel truncation

At the OTFS receiver, linear equalization techniques such as least square (LS)
and MMSE can be performed in either the DT, TF or DD domains. However, these
methods are not viable solutions for practical implementation due to the
computational complexity of computing the inverse of the $MN\times MN$ channel
matrix. To reduce the equalization complexity, we truncate the channel along
the Doppler dimension. This truncation naturally results in performance loss
for the linear equalizer which we compensate for with interference
cancellation later in the procedure using the soft output from the decoder.

The DD domain channel matrix ${\bf H}_{\rm DD}$, as seen in Fig. 2(a), is a
block circulant matrix with $M\times M$ subblocks. In Fig. 2 each small square
represents a $M\times M$ submatrix. In low-mobility scenarios, ${\bf H}_{\rm
DD}$ can be assumed to be a block circulant matrix with circulant blocks
(BCCB). Furthermore, the structure of ${\bf H}_{\rm DD}$ can be viewed as a
block banded matrix where the diagonal subblocks have the most significant
magnitude and the magnitude of elements in off-diagonal subblocks reduces as
we move away from the main diagonal submatrices.

(a) ${\mathbf{H}}_{\mathbf{DD}}$

(b) $\widetilde{{\bf H}}_{\rm DD}$

Figure 2: Blockbanded structure ${\mathbf{H}}_{\mathbf{DD}}$ and
$\widetilde{{\bf H}}_{\rm DD}$.

We define the significant subblocks of ${\bf H}_{\rm DD}$ as the subblocks at
each Doppler index which are contained within the truncation bandwidth,
$B=\lceil f_{\rm Dmax}MNT_{\rm s}\rceil$, where $f_{\rm Dmax}$ is the maximum
Doppler shift and $T_{\rm s}$ is the sampling period. Thus, with the channel
truncation, we consider only $2B+1$ significant Doppler coefficients for
channel equalization. The insignificant subblocks of ${\bf H}_{\rm DD}$ are
defined as those not contained within the truncation bandwidth. Hence, we
decompose ${\bf H}_{\rm DD}$ as ${\bf H}_{\rm DD}=\widetilde{{\bf H}}_{\rm
DD}+\mbox{\boldmath$\Delta$}_{\rm DD}$, where $\widetilde{{\bf H}}_{\rm DD}$
and $\mbox{\boldmath$\Delta$}_{\rm DD}$ are the DD domain channel matrices
with significant and insignificant Doppler indices, respectively. We now
rewrite (3) as

$\mathbf{y}_{\rm DD}=\widetilde{{\bf H}}_{\rm
DD}{\mathbf{x}}+\mbox{\boldmath$\Delta$}_{\rm
DD}{\mathbf{x}}+\boldsymbol{\eta}_{\rm{DD}}.$ (4)

In the proposed receiver, we use SIC to remove the interference caused by
$\mbox{\boldmath$\Delta$}_{\rm DD}$ based on the soft output from the decoder.
Based on the assumption that the soft output becomes more accurate after every
iteration, we can approximate (4) as,

$\mathbf{y}_{\rm DD}\approx\widetilde{{\bf H}}_{\rm
DD}{\mathbf{x}}+\boldsymbol{\eta}_{\rm{DD}}.$ (5)

Based on (5), in our proposed method, we use the mLSQR algorithm to equalize
the truncated channel and to obtain the soft output based on the MMSE criteria
[14]. The computational complexity of mLSQR is directly related to the number
of non-zero elements in the channel matrix. By utilising the truncated channel
matrix, we reduce the computational complexity of equalization further by
using the LSQR algorithm.

###  III-B Modified LSQR Algorithm

The proposed method uses the mLSQR algorithm to equalize the channel, which is
listed in Algorithm 1. LSQR is a well-known iterative algorithm for solving
problems of the form $\mathbf{y}_{\rm DD}=\widetilde{{\bf H}}_{\rm
DD}{\mathbf{x}}+\boldsymbol{\eta}_{\rm{DD}}$, [15]. At each iteration, $k$,
LSQR uses Golub-Kahan bidiagonalization and QR decomposition to obtain an
estimate of the transmitted symbol $\mathbf{x}_{k}$ [15]. A simple recursive
method for updating this estimate within each iteration was proposed in [16].
The iterative process continues until either the norm of the residual reaches
a pre-determined tolerance, $\epsilon$, or the maximum number of iterations
$I_{\rm LSQR}$ is reached. LSQR can also be regularized by including the noise
variance $\sigma^{2}$ as a damping parameter to improve the semi-convergence
property of the algorithm. After several iterations, LSQR provides a
performance similar to MMSE but with a substantially lower complexity [15].

Algorithm 1 Modified LSQR Algorithm

1:Input: $\widetilde{{\bf H}}_{\rm DD}$, $\mathbf{y}_{\rm DD}$ and
$\sigma^{2}$

2:Initialize: $\bar{\mathbf{y}}=[\mathbf{y}_{\rm
DD}^{\rm{T}},\mathbf{0}^{\rm{T}}]^{\rm{T}}$, $\mathbf{A}_{\rm
DD}=[\widetilde{{\bf
H}}_{\rm{DD}}^{\rm{T}},\sigma\mathbf{I}_{MN}^{\rm{T}}]^{\rm{T}}$,
$\beta_{0}=\|\bar{\mathbf{y}}\|$, $\mathbf{u}_{0}=\bar{\mathbf{y}}/\beta_{0}$,
$a_{0}=\|\mathbf{A}_{\rm DD}^{\mathrm{H}}\mathbf{u}_{0}\|$,
$\mathbf{v}_{0}=\mathbf{A}_{\rm DD}^{\mathrm{H}}\mathbf{u}_{0}/a_{0}$,
$\mathbf{w}_{0}=\mathbf{v}_{0}$, $\bar{\phi}_{0}=\beta_{0}$,
$\bar{\rho}_{0}=a_{0}$, $\mathbf{x}_{0}=\mathbf{0}_{MN\times 1}$,
$\mathbf{W}_{1}=\frac{\zeta_{1}}{\bar{\rho}_{0}\bar{\phi}_{0}}\mathbf{I}_{\mathrm{MN}}$,
$\mathbf{W}_{0}=\mathbf{0}_{MN\times MN}$, $\zeta_{0}=1$ and
$\bar{\phi}_{k}=\bar{\rho}_{k}=1$ for $k<0$

3:for $k=1:I_{\rm LSQR}$ do

4: $\beta_{k}=\|\mathbf{A}_{\rm DD}\mathbf{v}_{k-1}-a_{k-1}\mathbf{u}_{k-1}\|$

5: $\mathbf{u}_{k}=(\mathbf{A}_{\rm
DD}\mathbf{v}_{k-1}-a_{k-1}\mathbf{u}_{k-1})/\beta_{k}$

6: $a_{k}=\|\mathbf{A}_{\rm
DD}^{\mathrm{H}}\mathbf{u}_{k}-\beta_{k}\mathbf{v}_{k-1}\|$

7: $\mathbf{v}_{k}=(\mathbf{A}_{\rm
DD}^{\mathrm{H}}\mathbf{u}_{k}-\beta_{k}\mathbf{v}_{k-1})/a_{k}$

8: $\rho_{k}=\|[\bar{\rho}_{k-1}\ \ \beta_{k}]\|$,
$z_{k}=\frac{\bar{\rho}_{k-1}}{\rho_{k}}$, $s_{k}=\frac{\beta_{k}}{\rho_{k}}$,
$\theta_{k}=s_{k}a_{k}$

9: $\phi_{k}=z_{k}\bar{\phi}_{k-1}$, $\zeta_{k}=\frac{\phi_{k}}{\rho_{k}}$,
$\psi_{k}=\frac{\theta_{k}}{\rho_{k}}$

10: $\bar{\phi}_{k}=-s_{k}\bar{\phi}_{k-1}$,
$\bar{\rho}_{k}=-z_{k}\bar{\mathbf{y}}_{k}$

11: $\mathbf{x}_{k}=\mathbf{x}_{k-1}+\zeta_{k}\mathbf{w}_{k-1}$

12: $\mathbf{w}_{k}=\mathbf{v}_{k}-\psi_{k}\mathbf{w}_{k-1}$

13: Compute $\mathbf{\Omega}_{k}$ using (7)

14: if $||\mathbf{y}-\widetilde{{\bf H}}_{\rm
DD}\mathbf{x}_{k}||\leq\epsilon$, break

15:end for

16:Compute $\mu_{\hat{{\mathbf{x}}}}[n]$ and $\nu_{\hat{{\mathbf{x}}}}[n],\ $
$\forall n$ using (8) and (9)

17:Output: $\hat{{\mathbf{x}}}=\mathbf{x}_{k}$,
$\mbox{\boldmath$\mu$}_{\hat{{\mathbf{x}}}}$ and
$\mbox{\boldmath$\nu$}_{\hat{{\mathbf{x}}}}$

We note that the conventional LSQR algorithm does not provide the post-
equalization SINR information which is required for computing the LLRs.
Therefore, we use the modified LSQR algorithm from [13], to obtain this
information. LSQR computes $\mathbf{x}_{k}$ at each iteration using a simple
recursion. However, similar to the conjugate gradiant method in [17],
$\mathbf{x}_{k}$ can also be computed using an LSQR equivalent equalization
matrix which depends on the iteration index $k$. The LSQR equivalent
equalization matrix at iteration $k$ is defined as
$\mathbf{W}_{k}\widetilde{{\bf H}}_{\rm DD}^{\mathrm{H}}$, and
$\mathbf{x}_{k}$ can be written as
$\mathbf{x}_{k}=\mathbf{W}_{k}\widetilde{{\bf H}}_{\rm
DD}^{\mathrm{H}}\mathbf{y}$. From [13], $\mathbf{W}_{k}$ can be obtained
recursively as

$\begin{split}&\mathbf{W}_{k}=\mathbf{W}_{k-1}+\frac{\psi_{k-2}^{2}\zeta_{k}\bar{\rho}_{k-3}\bar{\phi}_{k-3}}{\zeta_{k-2}\bar{\rho}_{k-1}\bar{\phi}_{k-1}}\left(\mathbf{W}_{k-2}-\mathbf{W}_{k-3}\right)+\\\
&\left(\frac{\zeta_{k}\bar{\rho}_{k-2}\bar{\phi}_{k-2}(1+\psi_{k-1}^{2})}{\zeta_{k-1}\bar{\rho}_{k-1}\bar{\phi}_{k-1}}\mathbf{I}_{MN}-\frac{\zeta_{k}}{\bar{\rho}_{k-1}\bar{\phi}_{k-1}}\mathbf{A}_{\rm
DD}^{\mathrm{H}}\mathbf{A}_{\rm DD}\right)\\\
&\times\left(\mathbf{W}_{k-1}-\mathbf{W}_{k-2}\right),\end{split}$ (6)

where $\mathbf{A}_{\rm DD}=[\widetilde{{\bf
H}}_{\rm{DD}}^{\rm{T}},\sigma\mathbf{I}_{MN}^{\rm{T}}]^{\rm{T}}$,
$\mathbf{W}_{1}=\frac{\zeta_{1}}{\bar{\rho}_{0}\bar{\phi}_{0}}\mathbf{I}_{MN}$,
$\mathbf{W}_{k}=\mathbf{0}_{MN\times MN}$ for $k\leq 0$, $\zeta_{0}=1$ and
$\bar{\phi}_{k}=\bar{\rho}_{k}=1$ for $k<0$. Once $\mathbf{W}_{k}$ is
obtained, the post-equalization SINR on each symbol in $\mathbf{x}_{k}$ can be
calculated.

Let $\mathbf{G}_{\rm DD}=\mathbf{W}_{k}\widetilde{{\bf H}}_{\rm
DD}^{\mathrm{H}}\widetilde{{\bf H}}_{\rm DD}$. The post-equalization channel
gain on element $n$ of $\mathbf{x}_{k}$ is given by the diagonal elements
$\mathbf{G}_{\rm DD}$, i.e., $\mu_{\hat{{\mathbf{x}}}}[n]=G_{\rm DD}[n,n]$.
The variance of the interference-plus-noise on element $n$ of $\mathbf{x}_{k}$
is calculated using the off-diagonal elements of $\mathbf{G}_{\rm DD}$ and is
given by $\nu_{\hat{{\mathbf{x}}}}[n]=\sum_{m,m\not=n}|G_{\rm
DD}[n,m]|^{2}+C_{\rm DD}[n,n]\sigma^{2}$,where $\mathbf{C}_{\rm
DD}=\mathbf{G}_{\rm DD}\mathbf{W}_{k}^{\mathrm{H}}.$

While this method provides the exact post-equalization SINR information, it is
computationally expensive due to the $MN\times MN$ matrix multiplication in
(6). We can reduce the complexity of this computation by making the assumption
that the channel matrix has a BCCB structure. Under this assumption,
$\widetilde{{\bf H}}_{\rm DD}$ can be converted to a diagonal matrix in the TF
domain via $\widetilde{{\bf H}}_{\rm
TF}=(\mathbf{F}_{N}\otimes\mathbf{F}_{M})\widetilde{{\bf H}}_{\rm
DD}(\mathbf{F}_{N}\otimes\mathbf{F}_{M})^{\mathrm{H}}$. By using the
properties of BCCB matrices [5], we can also easily obtain the TF domain
equivalent of $\mathbf{A}_{\rm DD}^{\rm{H}}\mathbf{A}_{\rm DD}$ as
$\mathbf{A}_{\rm TF}^{\rm{H}}\mathbf{A}_{\rm TF}=\widetilde{{\bf H}}_{\rm
TF}^{*}\widetilde{{\bf H}}_{\rm TF}+\sigma^{2}\mathbf{I}.$

Note that $\mathbf{W}_{1}$ is initialized as a diagonal matrix and hence,
$\mathbf{W}_{k}$ retains the BCCB structure of the $\mathbf{A}_{\rm
DD}^{\mathrm{H}}\mathbf{A}_{\rm DD}$ for $k>2$. This means that the entire
recursion can be performed in the TF domain with diagonal matrices only. The
recursion in (6) can now be formulated in the TF domain as

$\begin{split}&\mathbf{\Omega}_{k}=\mathbf{\Omega}_{k-1}+\frac{\psi_{k-2}^{2}\zeta_{k}\bar{\rho}_{k-3}\bar{\phi}_{k-3}}{\zeta_{k-2}\bar{\rho}_{k-1}\bar{\phi}_{k-1}}\left(\mathbf{\Omega}_{k-2}-\mathbf{\Omega}_{k-3}\right)+\\\
&\left(\frac{\zeta_{k}\bar{\rho}_{k-2}\bar{\phi}_{k-2}(1+\psi_{k-1}^{2})}{\zeta_{k-1}\bar{\rho}_{k-1}\bar{\phi}_{k-1}}\mathbf{I}_{{MN}}-\frac{\zeta_{k}}{\bar{\rho}_{k-1}\bar{\phi}_{k-1}}\mathbf{A}_{\rm
TF}^{\rm{H}}\mathbf{A}_{\rm TF}\right)\\\
&\times\left(\mathbf{\Omega}_{k-1}-\mathbf{\Omega}_{k-2}\right),\end{split}$
(7)

where $\mathbf{\Omega}_{k}$ is the TF domain equivalent of $\mathbf{W}_{k}$
and is initialized with
$\mathbf{\Omega}_{1}=\frac{\zeta_{1}}{\bar{\rho}_{0}\bar{\phi}_{0}}\mathbf{I}_{MN}$
and $\mathbf{\Omega}_{k}=\mathbf{0}_{MN\times MN}$ for $k<1$. Since this
recursion only involves diagonal matrices, it can be performed with a low
complexity.

We can now use $\mathbf{\Omega}_{k}$ to calculate the approximate post-
equalization SINR information. To this end, we calculate the TF domain
equivalents of $\mathbf{G}_{\rm DD}$ and $\mathbf{C}_{\rm DD}$ as
$\mathbf{G}_{\rm{TF}}={\mathbf{\Omega}_{k}}\widetilde{{\bf H}}_{\rm
TF}^{\rm{H}}\widetilde{{\bf H}}_{\rm TF}$ and
$\mathbf{C}_{\rm{TF}}=\mathbf{\Omega}_{k}\widetilde{{\bf H}}_{\rm
TF}^{\rm{H}}\widetilde{{\bf H}}_{\rm TF}{\mathbf{\Omega}_{k}^{\rm{H}}}$,
respectively. The reverse process in obtaining $\widetilde{{\bf H}}_{\rm TF}$
from $\widetilde{{\bf H}}_{\rm DD}$ can then be used to calculate
approximations of the DD domain matrices $\mathbf{G}_{\rm DD}$ and
$\mathbf{C}_{\rm DD}$, i.e., $\widetilde{\mathbf{G}}_{\rm
DD}=(\mathbf{F}_{N}\otimes\mathbf{F}_{M})^{\mathrm{H}}\mathbf{G}_{\rm{TF}}(\mathbf{F}_{N}\otimes\mathbf{F}_{M})$
and $\widetilde{\mathbf{C}}_{\rm
DD}=(\mathbf{F}_{N}\otimes\mathbf{F}_{M})^{\mathrm{H}}\mathbf{C}_{\rm{TF}}(\mathbf{F}_{N}\otimes\mathbf{F}_{M}).$
Since $\widetilde{\mathbf{G}}_{\rm DD}$ and $\widetilde{\mathbf{C}}_{\rm DD}$
are BCCB matrices, their respective rows are simply shifted versions of each
other. Therefore, under this approximation, each symbol experiences the same
SINR, the post-equalization channel gain is given by

$\tilde{\mu}_{\hat{{\mathbf{x}}}}[n]=\widetilde{G}_{\rm
DD}[1,1],\vspace{-1ex}$ (8)

and the variance of the interference-plus-noise is given by

$\tilde{\nu}_{\hat{{\mathbf{x}}}}[n]=\sum_{m=2}^{MN-1}|\widetilde{G}_{\rm
DD}[1,m]|^{2}+\widetilde{C}_{\rm DD}[1,1]\sigma^{2}.\vspace{-1ex}$ (9)

###  III-C LLR Computation

After performing symbol-wise de-interleaving upon the estimated symbol vector
output from the mLSQR algorithm, the soft symbol demapper computes the
extrinsic information of the coded bits in terms of log-likelihood ratio. The
extrinsic LLR, $L_{\rm ext}[c_{n,k}],\,0\leq n\leq MN-1,\,0\leq k\leq Q-1$, is
the information of the coded bits $c_{n,k}$ contained in $\mathbf{Y}$ and the
a-priori information of $c_{n^{\prime},k}$, $\forall n^{\prime}\neq n$. This
extrinsic information is then fed to the decoder which computes the
a-posteriori information. During the $i^{\text{th}}$ iteration of TTE-SIC, the
mLSQR algorithm computes the estimate
$\hat{{\mathbf{x}}}^{i}\in\mathbb{C}^{MN\times 1}$, the mean
$\tilde{\mbox{\boldmath$\mu$}}^{i}_{\hat{{\mathbf{x}}}}\in\mathbb{C}^{MN\times
1}$ and the variance
$\tilde{\mbox{\boldmath$\nu$}}^{i}_{\hat{{\mathbf{x}}}}\in\mathbb{C}^{MN\times
1}$. Using the output from mLSQR, we can compute the extrinsic information of
the coded bits as

$\displaystyle L^{i}_{\rm ext}\left[c_{n,k}|\hat{x}^{i}[n]\right]=$
$\displaystyle{\rm
ln}\left(\frac{\underset{\begin{subarray}{c}\forall\mbox{\boldmath$\alpha$}_{l}:\\\
\alpha_{l,k}=0\end{subarray}}{\sum}P(\hat{x}^{i}[n]|{\mathbf{c}}_{n}=\mbox{\boldmath$\alpha$}_{l})\underset{\begin{subarray}{c}\forall
k^{\prime}:k^{\prime}\neq
k\end{subarray}}{\prod}P(c_{nm^{\prime}}=\alpha_{lm^{\prime}})}{\underset{\begin{subarray}{c}\forall\mbox{\boldmath$\alpha$}_{l}:\\\
\alpha_{l,k}=1\end{subarray}}{\sum}P(\hat{x}^{i}[n]|{\mathbf{c}}_{n}=\mbox{\boldmath$\alpha$}_{l})\underset{\begin{subarray}{c}\forall
k^{\prime}:k^{\prime}\neq
k\end{subarray}}{\prod}P(c_{nm^{\prime}}=\alpha_{lm^{\prime}})}\right),\vspace{-0.5ex}$
(10)

where ${\mathbf{c}}_{n}=[c_{n0},c_{n1},\ldots,c_{nm},\ldots,c_{nQ-1}]^{\rm
T}$,
$\mbox{\boldmath$\alpha$}_{l}=[\alpha_{l0},\alpha_{l1},\ldots,\alpha_{lm},\ldots,\alpha_{lQ-1}]^{\rm
T}$ with $c_{nm},\alpha_{lm}\in\\{0,1\\},\,0\leq l\leq 2^{Q}-1$ [14]. In order
to simplify the LLR derivation, we assume
$P(\hat{x}^{i}[n]|{\mathbf{c}}_{n}=\mbox{\boldmath$\alpha$}_{l})\sim\mathcal{CN}(q_{l}\tilde{\mu}^{i}_{\hat{x}}[n],\tilde{\nu}^{i}_{\hat{x}}[n])$,
where $q_{l}$ is the modulated symbol in symbol constellation corresponding to
the binary vector $\mbox{\boldmath$\alpha$}_{l}$. This assumption is widely
used in turbo equalization methods [18]. Hence, (10) is simplified as

$\displaystyle L^{i}_{\rm ext}\left[c_{n,k}|\hat{x}[n]\right]=$
$\displaystyle{\rm
ln}\\!\left(\frac{\underset{q\in\mathcal{Z}_{k}^{0}}{\sum}{\rm
exp}\\!\left(-\frac{|\hat{x}^{i}[n]-q\tilde{\mu}^{i}_{\hat{x}}[n]|^{2}}{\tilde{\nu}^{i}_{\hat{{\mathbf{x}}}}[n]}\right)\\!\\!+\\!\\!\\!\underset{\begin{subarray}{c}\forall
k^{\prime}\\\ k^{\prime}\neq
k\end{subarray}}{\sum}\\!\frac{1-2\alpha_{q,k^{\prime}}}{2}L[c_{n,k^{\prime}}]}{\underset{q\in\mathcal{Z}_{k}^{1}}{\sum}{\rm
exp}\\!\left(-\frac{|\hat{x}^{i}[n]-q\tilde{\mu}^{i}_{\hat{{\mathbf{x}}}}[n]|^{2}}{\tilde{\nu}^{i}_{\hat{{\mathbf{x}}}}[n]}\right)\\!\\!+\\!\\!\\!\underset{\begin{subarray}{c}\forall
k^{\prime}\\\ k^{\prime}\neq
k\end{subarray}}{\sum}\\!\frac{1-2\alpha_{q,k^{\prime}}}{2}L[c_{n,k^{\prime}}]}\right)\\!,$
(11)

where $\mathcal{Z}_{k}^{0}$ and $\mathcal{Z}_{k}^{1}$ are the sets of
modulated symbols corresponding to input signal vector with $0$ and $1$ in the
$k^{\text{th}}$ position, respectively. In (11), $\alpha_{q,k^{\prime}}$ is
the bit $k^{\prime}$ in the input vector which is mapped to $q$. Furthermore,
using max-log approximation, [19], and omitting the constant terms,
$L^{i}_{\rm ext}\left[c_{n,k}|\hat{x}[n]\right]$ can be computed as,

$\displaystyle L^{i}_{\rm ext}$
$\displaystyle\left[c_{n,j}|\hat{x}^{i}[n]\right]\\!\\!=\\!\\!\\!\\!\\!\\!$
$\displaystyle\gamma_{n}\\!\\!\left(\underset{q\in\mathcal{Z}_{k}^{0}}{\rm
min}|\hat{x}^{i}[n]-q|^{2}\\!\\!-\\!\\!\underset{q\in\mathcal{Z}_{k}^{1}}{\rm
min}|\hat{x}^{i}[n]-q|^{2}\right)$ (12)

where the SINR at the output of equalizer is defined as
$\gamma_{n}=\frac{(\tilde{\mu}^{i}_{\hat{{\mathbf{x}}}}[n])^{2}}{\tilde{\nu}^{i}_{\hat{{\mathbf{x}}}}[n]}$.
This extrinsic information is fed to the decoder, which computes the
a-posteriori information of the coded bits,
$\lambda^{i}[c_{n,k}|\hat{x}^{i}[n]]$. The a-priori information of each code
bit can then be calculated as

$\displaystyle\lambda^{i}[c_{n,k}]=\lambda^{i}\left[c_{n,k}|\hat{x}^{i}[n]\right]-L^{i}_{\rm
ext}\left[c_{n,k}|\hat{x}^{i}[n]\right].$ (13)

The a-priori information of all encoded bits is then collected in a vector
${\mbox{\boldmath$\lambda$}}^{i}\in\mathbb{R}^{MNr}$ to perform interference
cancellation.

Algorithm 2 Proposed TTE-SIC Technique

1:Input: $\mathbf{y}_{\rm DD}$, $\widetilde{{\bf H}}_{\rm DD}$ and
$\mbox{\boldmath$\Delta$}_{\rm DD}$

2:Initialize:
$\mbox{\boldmath$\mu$}^{0^{\prime}}_{\hat{{\mathbf{x}}}}=\mathbf{0}$ and
$\mathbf{y}_{\rm DD}^{0}=\mathbf{y}_{\rm DD}$

3:for $i=1:I_{\rm SIC}^{\rm Prop.}$ do

4: Calculate $\mathbf{y}_{\rm DD}^{i+1}$ using (16)

5: Obtain $\hat{{\mathbf{x}}}^{i}$,
$\tilde{\mbox{\boldmath$\mu$}}_{\hat{{\mathbf{x}}}}^{i}$ and
$\tilde{\mbox{\boldmath$\nu$}}_{\hat{{\mathbf{x}}}^{i}}$ using Algorithm 1

6: Calculate $L^{i}_{\rm ext}\left[c_{n,k}|\hat{x}^{i}[n]\right]$ as in (12)

7: Calculate $\lambda^{i}[c_{n,k}]$ using (13)

8: Obtain the soft output, $\mu_{\hat{{\mathbf{x}}}}^{i^{\prime}}[n]$ using
(14)

9:end for

10:Output: Obtain $\hat{\mathbf{b}}$ from decoder output

###  III-D Interference Cancellation

Using the a-priori information of the codewords, the soft symbol estimates can
be obtained. After performing bitwise deinterleaving on
${\mbox{\boldmath$\lambda$}}^{i}$, the soft symbol mapper calculates the new
refined soft symbol estimates as

$\displaystyle\mu_{\hat{{\mathbf{x}}}}^{i^{\prime}}[n]=\sum_{q\in\mathcal{Z}}qP(\hat{x}^{i}[n]=q),$
(14)

where
$P(\hat{x}^{i}[n]=q)\\!=\\!\prod_{j=0}^{Q-1}\frac{1}{2}\left(1\\!+\\!(\tilde{\alpha}_{q,j}){\rm
tanh}(\frac{\lambda^{i}[c_{n,j}]}{2})\right)$, with
$\tilde{\alpha}_{q,j}=2\alpha_{q,j}\\!-\\!1$. We then use the soft symbol
estimates from (14) to remove the interference caused by the insignificant DD
domain channel coefficients which remains in the received signal. The received
signal at iteration $i+1$ after interference cancellation is expressed as

$\displaystyle\mathbf{y}^{i+1}_{\rm DD}=\mathbf{y}^{i}_{\rm
DD}-\mbox{\boldmath$\Delta$}_{\rm
DD}\mbox{\boldmath$\mu$}^{i^{\prime}}_{\hat{{\mathbf{x}}}},$ (15)

where
$\mbox{\boldmath$\mu$}^{i^{\prime}}_{\hat{{\mathbf{x}}}}=[\mu^{i^{\prime}}_{\hat{{\mathbf{x}}}}[0],\ldots,\mu^{i^{\prime}}_{\hat{{\mathbf{x}}}}[MN-1]]^{\rm
T}$. The computational complexity of this interference cancellation procedure
can be reduced by implementing it in the TF domain. Since
$\mbox{\boldmath$\Delta$}_{\rm DD}$ has a BCCB structure, each of the
$N-B^{\prime}$ circulant $M\times M$ sub-matrices can be diagonalized using an
$M-$ point DFT, where $B^{\prime}=2B+1$. Therefore, the interference
cancellation in (15) can be performed in TF domain as

$\displaystyle\mathbf{y}^{i+1}_{\rm TF}=\mathbf{y}_{\rm
TF}^{i}-{\mbox{\boldmath$\Delta$}}_{\rm
TF}\tilde{\mbox{\boldmath$\mu$}}^{i^{\prime}}_{\hat{{\mathbf{x}}}}$ (16)

where ${\mathbf{y}}^{i}_{\rm TF}$, $\mbox{\boldmath$\Delta$}_{\rm TF}$ and
$\tilde{\mbox{\boldmath$\mu$}}^{i^{\prime}}_{\hat{{\mathbf{x}}}}$ are obtained
from ${\mathbf{y}}^{i}_{\rm DD}$, $\mbox{\boldmath$\Delta$}_{\rm DD}$ and
$\mbox{\boldmath$\mu$}^{i^{\prime}}_{\hat{{\mathbf{x}}}}$ respectively by
multiplying them with $({\bf F}_{N}\otimes{\bf F}_{M})$ from left and $({\bf
F}_{N}\otimes{\bf F}_{M})^{\rm H}$ from right. Since
$\mbox{\boldmath$\Delta$}_{\rm TF}$ can be pre-computed, the interference
cancellation at iteration $i$ can be performed with $MN(N-B^{\prime})$
element-wise complex multiplications and ${\mathbf{y}}^{i+1}_{\rm DD}=({\bf
F}_{N}\otimes{\bf F}_{M})^{\rm H}{\mathbf{y}}_{\rm TF}^{i+1}({\bf
F}_{N}\otimes{\bf F}_{M})$. Finally, our proposed technique is summarized in
Algorithm 2.

###  III-E Computational Complexity

In this section, we analyze and compare the complexity of the proposed TTE-SIC
with the existing methods in literature in terms of the number of CMs. We
consider the full MMSE equalizer without channel truncation followed by a
decoder as a benchmark which has the computational load of
$\mathcal{O}(M^{3}N^{3})$. The computational complexity order for mLSQR is
$\mathcal{O}(MNP^{\prime}I_{\rm LSQR})$, where $P^{\prime}$ is the number of
non-zero elements in a column of ${\bf H}_{\rm DD}$ and $I_{\rm LSQR}$ is the
number of LSQR iterations[15]. In a scattering rich environment with
fractional Doppler shifts, $P^{\prime}=NL$, and hence, the complexity order
will be $\mathcal{O}(MN^{2}LI_{\rm LSQR})$. Using the truncated channel, LSQR
complexity in step 5 of TTE-SIC in Algorithm 2 is $\mathcal{O}(MNBLI_{\rm
LSQR})$. The soft symbol mapping and demapping in steps 6, 7 and 8 of
Algorithm 2 require a total of $2(Q+1)MN$ CMs. Furthermore, by performing the
interference cancellation in TF domain, step 4 requires
$(N-B^{\prime})\mathcal{O}(M\log_{2}(M))+MN(N-B^{\prime})+\mathcal{O}(MN\log_{2}(MN))$
CMs. The MP equalizer in [6] and the LSMR with SIC receiver in [8] require
$\mathcal{O}(MN^{2}LQI_{\rm MP})$ and $\mathcal{O}(MN^{2}LI_{\rm LSMR}I_{\rm
SIC}^{\rm LSMR.})$ CMs, respectively. The MP detector requires $I_{\rm MP}$
iterations and LSMR with SIC receiver requires $I_{\rm LSMR}$ iterations for
LSMR and $I_{\rm SIC}^{\rm LSMR}$ iterations for SIC. The computational
complexities of different techniques are summarised in Table I. It should be
noted that, the equalizers in [6] and [8] do not consider the soft information
available at the output of the decoder. Therefore, for a fair comparison, the
computational complexity associated with the decoders are not included. Fig. 3
shows the computational load of the proposed TTE-SIC receiver compared to
different methods from the literature as a function of $N$. For this
comparison, we consider $L=7$, $Q=4$, $I_{\rm MP}=30$, $I_{\rm LSMR}=I_{\rm
LSQR}=20$, $I_{\rm SIC}^{\rm LSMR}=5$ [8]. For the proposed TTE-SIC technique,
we used $B=2$, and $I_{\rm SIC}^{\rm Prop.}=3$ for SIC. As seen in Fig. 3, our
proposed technique is around $10^{4}$ and $10$ times simpler than full MMSE
and LSMR-SIC equalizers, respectively.

Figure 3: Computational complexity comparison of our proposed TTE-SIC
technique with the existing methods. TABLE I: Computational Complexity
Comparison

Equalization Methods | Complexity Order
---|---
Full MMSE | $\mathcal{O}(M^{3}N^{3})$
MP [6] | $\mathcal{O}(MN^{2}LQI_{\rm MP})$
LSMR with SIC [8] | $\mathcal{O}(MN^{2}LI_{\rm lSMR}I_{\rm SIC}^{\rm LSMR})$
Proposed TTE-SIC |  $\mathcal{O}(MNI_{\rm SIC}^{\rm Prop.}(B^{\prime}LI_{\rm LSQR}+2Q+N-B^{\prime}+4-\frac{B^{\prime}}{N}\log_{2}M+\log_{2}N))$

##  IV Simulation Results

(a) $B=2$

(b) $B=3$

Figure 4: BER performance of the proposed TTE-SIC technique at a relative
velocity of $500$ km/h.

In this section, we evaluate the performance of our proposed TTE-SIC technique
via simulations. We consider an OTFS system with $M=64$ and $N=16$. At the
transmitter, the information bits are encoded using a $1/2$ rate convolutional
encoder with $(2,1,3)$ configuration and are mapped on to $4-$QAM
constellation. In our simulations, we use the extended vehicular A (EVA)
channel model, [20], with a carrier frequency of $f_{c}=5.9$ GHz, a sampling
period of $T_{s}=370.3$ ns and a relative velocity of $500$ km/h between the
transmit and receive antennas which corresponds to $f_{\rm Dmax}=2.73$ kHz. We
set the MMSE equalizer with the full channel, i.e., no truncation, as a
benchmark in our evaluations.

Fig. 4 shows the BER performance of our proposed TTE-SIC method versus SNR for
different values of SIC iterations and the parameter $B$. Fig. 4(a) shows the
BER performance for the channel truncation bandwidth given by the criterion
described in Section III-A, which corresponds to $B=\lceil f_{\rm
Dmax}MNT_{\rm s}\rceil=2$. It can be seen that, only 2 iterations are
sufficient for our proposed technique to provide about the same performance as
that of our benchmark. In Fig. 4(b), we repeat our evaluations for $B=3$ to
asses the validity of our channel truncation criterion. This analysis reveals
that increasing $B$ brings only marginal performance gain when $I^{\rm
Prop.}_{\rm SIC}=1$ and negligible gain when $I^{\rm Prop.}_{\rm SIC}\geq 2$.
This confirms that our criterion defines sufficient level of channel
truncation. Based on the results in Fig. 4 and Section III-E, our proposed
TTE-SIC technique achieves a similar BER performance to the benchmark with
several orders of magnitude lower computational load.

##  V Conclusion

In this paper, we have proposed a novel low-complexity TTE-SIC receiver for
coded OTFS systems in high-mobility scenarios. In our proposed technique, we
exploit the block-banded structure of the DD domain channel to truncate the
channel and reduce the complexity of equalization. Our proposed TTE-SIC
technique deploys the low-complexity mLSQR algorithm for both channel
equalization and to obtain the post-equalization SINR necessary for computing
the LLRs for soft-output detection. To compensate for the performance loss due
to the channel truncation, we take a low-complexity interference cancellation
approach using the decoder output and insignificant Doppler coefficients left
over from the truncation. Our simulation results demonstrate that, after only
2 iterations, the proposed TTE-SIC technique offers about the same performance
as the full-channel MMSE benchmark with orders of magnitude lower
computational load.

## References

  * [1] R. Hadani, S. Rakib, M. Tsatsanis, A. Monk, A. J. Goldsmith, A. F. Molisch, and R. Calderbank, “Orthogonal Time Frequency Space Modulation,” in _IEEE Wireless Commun. Netw. Conf._ , 2017, pp. 1–6.
  * [2] A. Farhang, A. RezazadehReyhani, L. E. Doyle, and B. Farhang-Boroujeny, “Low Complexity Modem Structure for OFDM-Based Orthogonal Time Frequency Space Modulation,” _IEEE Wireless Commun. Lett._ , vol. 7, no. 3, pp. 344–347, 2018.
  * [3] S. PS and A. Farhang, “A Practical Pilot for Channel Estimation of OTFS,” _to appear in Proc. of Int. Commun. Conf. (ICC)_ , 2023.
  * [4] Z. Zhang, H. Liu, Q. Wang, and P. Fan, “A Survey on Low Complexity Detectors for OTFS Systems,” _ZTE Commun._ , vol. 19, no. 4, pp. 3–15, 2022.
  * [5] G. D. Surabhi and A. Chockalingam, “Low-Complexity Linear Equalization for OTFS Modulation,” _IEEE Commun. Lett._ , vol. 24, no. 2, pp. 330–334, 2020\.
  * [6] P. Raviteja, K. T. Phan, Y. Hong, and E. Viterbo, “Interference cancellation and iterative detection for orthogonal time frequency space modulation,” _IEEE Trans. Wireless Commun._ , vol. 17, no. 10, pp. 6501–6515, 2018.
  * [7] S. Li, W. Yuan, Z. Wei, J. Yuan, B. Bai, D. W. K. Ng, and Y. Xie, “Hybrid MAP and PIC Detection for OTFS Modulation,” _IEEE Trans. Veh. Technol._ , vol. 70, no. 7, pp. 7193–7198, 2021.
  * [8] H. Qu, G. Liu, L. Zhang, S. Wen, and M. A. Imran, “Low-Complexity Symbol Detection and Interference Cancellation for OTFS System,” _IEEE Trans. Commun._ , vol. 69, no. 3, pp. 1524–1537, 2021.
  * [9] T. Zemen, M. Hofer, D. Löschenbrand, and C. Pacher, “Iterative Detection for Orthogonal Precoding in Doubly Selective Channels,” in _IEEE Pers., Ind. Mob. Radio Commun. (PIMRC)_ , 2018, pp. 1–7.
  * [10] F. Long, K. Niu, C. Dong, and J. Lin, “Low Complexity Iterative LMMSE-PIC Equalizer for OTFS,” in _IEEE Int. Conf. Commun. (ICC)_ , 2019, pp. 1–6.
  * [11] S. S. Das, S. Tiwari, V. Rangamgari, and S. C. Mondal, “Performance of iterative Successive interference cancellation receiver for LDPC coded OTFS,” in _IEEE Int. Conf. Ad. Netw. Tele. Sys. (ANTS)_ , 2020, pp. 1–6.
  * [12] H. Li and Q. Yu, “Doubly-Iterative Sparsified MMSE Turbo Equalization for OTFS Modulation,” _IEEE Trans. Commun._ , vol. 71, no. 3, pp. 1336–1351, 2023.
  * [13] S. McWade, A. Farhang, and M. F. Flanagan, “Low-Complexity Reliability-Based Equalization and Detection for OTFS-NOMA,” 2023, Available: arXiv:2304.13607v1.
  * [14] M. Tuchler, A. Singer, and R. Koetter, “Minimum mean squared error equalization using a priori information,” _IEEE Trans. Signal Process._ , vol. 50, no. 3, pp. 673–683, 2002.
  * [15] T. Hrycak, S. Das, G. Matz, and H. G. Feichtinger, “Low Complexity Equalization for Doubly Selective Channels Modeled by a Basis Expansion,” _IEEE Trans. Signal Process._ , vol. 58, no. 11, pp. 5706–5719, 2010.
  * [16] C. C. Paige and M. A. Saunders, “LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares,” _ACM Trans. Math. Softw._ , vol. 8, no. 1, p. 43–71, mar 1982.
  * [17] B. Yin, M. Wu, J. R. Cavallaro, and C. Studer, “Conjugate gradient-based soft-output detection and precoding in massive MIMO systems,” in _IEEE Glob. Commun. Conf._ , 2014, pp. 3696–3701.
  * [18] X. Wang and H. Poor, “Iterative (turbo) soft interference cancellation and decoding for coded CDMA,” _IEEE Trans. Commun._ , vol. 47, no. 7, pp. 1046–1061, 1999.
  * [19] C. Studer, S. Fateh, and D. Seethaler, “ASIC Implementation of Soft-Input Soft-Output MIMO Detection Using MMSE Parallel Interference Cancellation,” _IEEE J. Solid-State Circuits_ , vol. 46, no. 7, pp. 1754–1765, 2011.
  * [20] 3GPP, “Evolved universal terrestrial radio access (E-UTRA); base station (BS) radio transmission and reception (Release 12 ),” _3rd Generation Partnership Project (3GPP)_ , TS 36.104 V15.3.0, 2018.