# Deep Learning based Channel Extrapolation for Large-Scale Antenna Systems:
Opportunities, Challenges and Solutions

Shun Zhang, _Senior Member, IEEE,_ Yushan Liu, Feifei Gao, _Fellow, IEEE,_
Chengwen Xing, _Member, IEEE,_ Jianping An, _Member, IEEE,_ and Octavia A.
Dobre, _Fellow, IEEE_ S. Zhang and Y. Liu are with the State Key Laboratory of
Integrated Services Networks, Xidian University, Xi’an 710071, P. R. China
(Email<EMAIL_ADDRESS>ysliu_97@stu.xidian.edu.cn). F. Gao is
with Department of Automation, Tsinghua University, State Key Lab of
Intelligent Technologies and Systems, Tsinghua University, State Key for
Information Science and Technology (TNList) Beijing 100084, P. R. China
(Email: feifeigao@ieee.org). C. Xing and J. An are with the School of
Information and Electronics, Beijing Institute of Technology, Beijing 100081,
China (e-mail<EMAIL_ADDRESS>an@bit.edu.cn). O. A. Dobre is with
Faculty of Engineering and Applied Science, Memorial University, St. John’s NL
AIC-5S7, Canada (e-mail: odobre@mun.ca).

###### Abstract

With the depletion of spectrum, wireless communication systems turn to exploit
large antenna arrays to achieve the degree of freedom in space domain, such as
millimeter wave massive multi-input multi-output (MIMO), reconfigurable
intelligent surface assisted communications and cell-free massive MIMO. In
these systems, how to acquire accurate channel state information (CSI) is
difficult and becomes a bottleneck of the communication links. In this
article, we introduce the concept of channel extrapolation that relies on a
small portion of channel parameters to infer the remaining channel parameters.
Since the substance of channel extrapolation is a mapping from one parameter
subspace to another, we can resort to deep learning (DL), a powerful learning
architecture, to approximate such mapping function. Specifically, we first
analyze the requirements, conditions and challenges for channel extrapolation.
Then, we present three typical extrapolations over the antenna dimension, the
frequency dimension, and the physical terminal, respectively. We also
illustrate their respective principles, design challenges and DL strategies.
It will be seen that channel extrapolation could greatly reduce the
transmission overhead and subsequently enhance the performance gains compared
with the traditional strategies. In the end, we provide several potential
research directions on channel extrapolation for future intelligent
communications systems.

##  I Introduction

With the rapid development of wireless technologies, we are entering the era
of the fifth generation (5G) wireless communications and are heading towards
the sixth generation (6G). Massive multi-input multi-output (MIMO) will
continue to serve as one of the key technologies for 6G, as it can provide
much more degrees of freedom than the conventional MIMO. In particular,
massive MIMO combined with millimeter wave (mmWave) communications can achieve
orders of magnitude enhancement in system throughput. For the cell-free
massive MIMO, the distributed systems can potentially reduce the inter-cell
interference through coherent cooperation between base stations (BSs) and
provide higher coverage than co-located massive MIMO. Besides, the
reconfigurable intelligent surface (RIS) with massive number of passive
antennas can effectively perform the desired beamforming and reconstruct the
radio scattering environment into an intelligent environment. Unfortunately,
as the number of antennas increases, all these promising wireless technologies
require a large amount of training overhead in order to achieve accurate
channel state information (CSI).

Traditionally, the channel reciprocity is utilized in time division duplex
(TDD) massive MIMO systems to reduce the cost of downlink channel estimation
as long as the uplink CSI is obtained. For frequency division duplex (FDD)
massive MIMO, the compressive algorithms that exploit the sparsity of channel
in angle domain have been used to estimate CSI. However, the performance of
compressive sensing is restricted with the linear sparsity assumption that
does not accurately match the complex nonlinear sparse characteristics of the
environment. Recently, Alkhateeb et al. revealed the deterministic
relationship among different channels at different antennas and frequency
bands, and introduced a new concept, namely the channel mapping in space and
frequency domain [1]. With a similar principle, Esswie et al. proposed a
spatial channel estimation scheme to reconstruct the downlink channel from
uplink channel measurements for FDD MIMO systems [2]. In [3], Ali et al.
constructed the channel covariance of the mmWave link from the spatial
characteristics of the sub-6 GHz band.

In fact, the essential principle of deterministic mapping among different
channels is that users at different spaces or different frequencies experience
the same electromagnetic environment. Utilizing such deterministic mapping,
the CSI at one space/frequency point can be used to predict the CSI at another
space/frequency point, which is referred to as $\mathrm{\it
channel~{}extrapolation}$. Clearly, channel extrapolation can be excitingly
useful to reduce the training cost over massive MIMO related systems. Inspired
by the universal approximation capability of deep learning (DL) [4, 5, 6], it
is possible to use DL to characterize the mapping among channels at different
space/frequency locations.

In this article, we introduce the mechanism for channel extrapolation and
analyze its major challenges over three scenarios: antenna domain
extrapolation, frequency domain extrapolation and physical terminal
extrapolation. Specifically, for the antenna extrapolation, we propose to use
the channel of a few uplink antennas to reconstruct the full downlink channel
for an FDD system, and present the corresponding DL-based solution. For the
frequency extrapolation, we consider two cases: the channel mapping between
two subcarrier sets within one frequency band and the channel mapping across
different frequency bands. For the terminal extrapolation, we consider the
channel mapping among different distributed users, where the sensors are
applied to provide additional information about the environment and DL is used
to achieve the transfer between neural networks (NNs) of distinct users.
Finally, we discuss several potential research directions on channel
extrapolation for future intelligent communications.

##  II Problem Formulation

###  II-A The Concept of Channel Extrapolation

From the propagation characteristics of the electromagnetic wave, we know that
when the user switches the frequency or moves in a short time, its surrounding
environment would not change much, which makes the channels at different
spaces or different frequencies to have certain mapping relationship. Many
efforts have been made to explore such mapping, and some effective mapping
models, e.g., the one between the uplink and downlink channels over the
massive MIMO systems, have been established. Nevertheless, channel mappings,
like the one between the sub-6 and mmWave bands or the one among different
distributed antennas, are difficult to describe mathematically. In [1], the
authors proved that the large-scale antenna arrays are able to assure the
_bijectiveness_ condition, which makes the channel mapping along the frequency
and space dimensions unique. Then, the authors utilized the DL approach to
successively approximate such channel mapping. The key idea of DL-based
channel extrapolation is illustrated in Fig. 1.

Figure 1: The opportunities of DL-based channel extrapolation.

###  II-B Challenges of DL-based Channel Extrapolation

In fact, channel extrapolation can be treated as a mapping from one parameter
subspace to another, which depends on three aspects: the acquisition of the
original subspace information, the choice of the original subspace, and the
mapping scheme from the original subspace to the targeted one. Notice that the
task of “the original subspace acquisition” is to estimate the sub-sampled
channel of small size and can be easily implemented through the conventional
Bayesian linear estimator, message passing algorithms, or DL-based algorithms.
Therefore, in the following, we will focus on the other two challenges:

  1. 1.

Subspace selection: For the given full space, the raw input information is
closely related with the selection of subspace. Different selections would
correspond to distinguished information compression rates and $\mathrm{\it
selection~{}patterns}$, where the selected space is marked as ‘1’ while the
others are marked as ‘0’. With the power, hardware, or performance
constraints, it is possible to optimize the selection pattern and to provide a
good start point for a specific extrapolation task. The sparser the selection
pattern is, the less the training costs and hardware power consumption are,
but the poorer the performance of the channel extrapolation will be. Thus,
with the DL-based channel extrapolation, it is important to determine the
selection pattern before starting the transmission. However, the core
operation of DL is the gradient descent algorithm that requires the mapping
function to be continuous and differentiable. Hence, the optimization of the
subspace selection is challenging for DL based channel extrapolation.

  2. 2.

Mapping scheme: The DL-based channel extrapolation is similar to the super-
resolution in the field of image processing, in which it is important to
properly exploit the correlation between data elements for information
completion. In order to improve the performance of the NN, we can increase the
number of data layers or modify the NN structure. However, more layers result
in heavier calculation, and when the number of layers reaches a certain
number, the degree of improvement becomes smaller. Sometimes, excessively
deepening the NN will even cause the gradient explosion and disappearance.
Thus, we aim to constructing a robust but simple NN structure to achieve
better extrapolation performance and faster convergence, which is another
challenge of the channel extrapolation.

In the following, we present the channel extrapolation over the antenna
dimension, the frequency dimension and the physical terminal separately, and
show the effectiveness of each type of extrapolation.

##  III Channel Extrapolation over Antenna Dimension

A practical way to implement large antenna arrays, e.g., massive MIMO, is to
use the hybrid analog and digital architecture, where a small number of radio
frequency (RF) chains are connected to massive antennas through the fully
connection or subarray connection structure. In this case, the limited number
of RF chains have to connect the active antennas in turn for the acquisition
of downlink CSI, which consumes significant time resources, especially when
physically switching the antennas costs non-ignorable time. Besides, over the
RIS communication network, the channel size is in scale with the number of RIS
elements, which is usually very large to achieve good electromagnetic
reconfiguring performance. Thus, the channel estimation in RIS-aided network
also requires significant time resources. With the new idea of channel
extrapolation, we can explore the mapping relation between the partial
antennas and the full one in an offline manner, and accurately infer the CSI
of full antennas from the partial antennas during the online transmission.
This type of channel extrapolation architecture is specifically referred to as
$\mathrm{\it antenna~{}extrapolation}$ and is illustrated in Fig. 2.

Figure 2: The channel extrapolation over antenna dimension for large-scale
antenna systems.

Recently, there are some preliminary results on implementing the antenna
extrapolation. In [7], the authors examined the antenna extrapolation for a
massive MIMO system based on the deep NN (DNN), which can capture the inherent
relationship between the uplink and downlink channel data sets and extrapolate
the downlink channels from a subset of the uplink CSI. In [8], Zhang et al.
realized the antenna extrapolation through a convolutional NN (CNN) in a RIS-
aided communication system. Moreover, the authors proposed an antenna
selection network that utilizes the probabilistic sampling theory to select
the optimal locations of those active antennas. In [9], we modify the NN
structure by ordinary differential equation (ODE) which can describe the
latent relations among different data layers and improve the performance gains
of the antenna extrapolation.

In Fig. 3, we provide evaluation results of the antenna extrapolation for the
traditional CNN structure and the ODE-based CNN structure in a RIS-aided
system. The parameter settings are: a $4\times 4$ uniform planar array (UPA)
at BS, $8\times 8$ UPA at RIS and single antenna at the user, where the
antenna spacing is half wavelength. The carrier frequency is $2.4$ GHz, the
system bandwidth is $20$ MHz, and the number of subcarriers is $64$. Moreover,
the number of active antennas at RIS is separately taken as $8$ and $16$. The
distribution of training and test users in the DeepMIMO dataset is the same as
in [7]. It can be seen from Fig. 3 that with the increase of iteration time,
the normalized mean square error (NMSE) curves decay fast first, and then slow
down after $110$ epochs. As the number of active antennas increases, the NMSEs
of the two structures decrease and the performance gap between the two
structures becomes larger. Hence, for a given number of active antennas, the
ODE-based CNN outperforms the traditional CNN and trains faster than the
traditional CNN.

Figure 3: The NMSE comparison of traditional CNN and ODE-based CNN against
epochs for antenna extrapolation in a RIS-assisted communication system. Note
that $r$ denotes the number of active antennas at RIS.

In fact, the DL-based algorithms should adapt to the environmental changes and
customize the antenna extrapolation schemes according to the environmental
information. Hence, once the environment changes, say when the users are
moving, the corresponding NNs should be re-trained. Thus, how to achieve a
good balance between the performance gains and the cost caused from retraining
the DNN is another challenge for the antenna extrapolation. A possible
solution could be the transfer and meta learning that has the ability to adapt
to the new environment quickly with a small amount of new training samples
[10].

##  IV Channel Extrapolation over Frequency

Along the frequency dimension, the channel extrapolation can use one set of
subcarriers to infer another set of subcarriers, which is named $\mathrm{\it
frequency~{}extrapolation}$. We present two typical applications for the
frequency extrapolation in Fig. 4. One is to implement the channel
extrapolation between two subcarrier sets within a given frequency band. The
other is to extrapolate channels among different frequency bands, being
suitable for the multi-band systems, say FDD massive MIMO system. As seen
later, the frequency extrapolation principle may even be feasible when the gap
between different frequency bands is large.

Figure 4: The channel extrapolation over frequency for multi-band MIMO
systems, including sub-6 GHz and mmWave.

###  IV-A Frequency Extrapolation Within A Frequency Band

The orthogonal frequency division multiplexing (OFDM) technology with a large
amount of subcarriers is usually adopted to capture the potential efficiency
of large bandwidth and deal with the frequency selective fading. Since the
mathematical channel modeling among different subcarriers is available, one
can sparsely place pilots at partial subcarriers, sound the incomplete
channels and reconstruct the entire CSI over the full band via a signal
processing approach. Although the performance of the signal processing
approach is very good in a stable environment, its effectiveness degrades in
more complicated scenarios. For example, in high mobility scenario, OFDM may
encounter significant inter-carrier interference due to the Doppler spread.
Moreover, when the length of the predefined cyclic prefix (CP) is smaller than
that of the channel’s delay spread, the inter-symbol interference appears and
destroys the signal modeling in the frequency domain. In addition, the
hardware impairments, such as the I/Q imbalance, phase noise and nonlinearity
of the power amplifier, would cause nonlinear distortion in received signals.

A possible solution is to utilizing the universal approximation capability of
DL to characterize the channel modeling in these complicated scenario and
continue to reconstruct the channels of all subcarriers from a small subset of
subcarriers. Another key problem is that the traditionally adopted uniform
pilot pattern cannot guarantee the optimal performance anymore and the design
of the pilot pattern should be carefully addressed.

In Fig. 5 (a), we offer the evaluation results of the frequency extrapolation
in mmWave band based on the CNN and conventional interpolation scheme [5]. The
antenna configuration is the same as that in Fig. 3. The carrier frequency is
$60$ GHz, and the subcarrier spacing is $60$ kHz. The number of subcarriers is
$1024$, and the number of selected subcarriers for partial channel estimation
is $256$. The curves labeled by ‘InCP’ correspond to the case of insufficient
CP, while the ones marked by ‘EnCP’ represent the case of enough CP. It can be
seen from the Fig. 5(a) that the NMSE curves decay with the increase of the
sample rate on the subcarrier. Meanwhile, the NMEs of CNN are always better
than those of conventional interpolation, especially in the case of
insufficient CP. Moreover, in the case of enough CP, the gap between CNN and
conventional interpolation becomes larger as the sample rate decreases.

Figure 5: The performance analysis of two frequency extrapolations in a multi-
band system (including sub-6 GHz and mmWave bands).

###  IV-B Frequency Extrapolation Between Different Frequency Bands

DL-based frequency extrapolation can also be used to infer the downlink
channel from the uplink one in FDD massive MIMO, which solves the problem
resulted from the fact that the channel is not reciprocal in the two different
frequency bands. In fact, the technology of multiple bands transmission is a
new trend, especially that recent communications systems are designed to work
at both sub-6 GHz and mmWave bands, simultaneously [3, 11, 12]. In the dual
band system, the mmWave spectrum would provide a high speed link and offer
gigabit-per-second data rates, but it would also face huge training overhead
and high sensitivity to blockages. Since the mmWave and sub-6 GHz links
experience the same scattering environment, it is possible to build a
deterministic relationship between their channels and extrapolate the CSI of
mmWave band from that of the sub-6 GHz band.

In [11], Li et al. used the sub-6 GHz spatial information to help beam
selection in a mmWave system by exploiting the feature that the support set of
the mmWave channels is a subset of that for the sub-6 GHz channels with the
same grid quantization. In [12], Alrabeiah et al. performed beam prediction at
mmWave band from the CSI at sub-6 GHz band with the aid of a DNN. Moreover,
the authors incorporated the materials’ dielectric coefficients at the sub-6
GHz and mmWave bands, which is critical information for the accurate mapping
between the sub-6 GHz and mmWave signals.

Although the effectiveness of the above work has been verified, the frequency
extrapolation from sub-6 GHz to mmWave is practically inaccurate. This is
mainly because the mmWave signal propagation is highly sensitive to blockages,
and the electromagnetic microwave impinging on the arrays of two links have
different angular spread (AS). Therefore, the mmWave channel is a sub-category
of the sub-6 GHz channel [13], and the CSI of mmWave band could seriously
deviate from that in sub-6 GHz. In order to calibrate the CSI deviation, we
design a simple but tricky dual-input NN, referred to as FusionNet, to merge
the features of sub-6 GHz channels and a few inherent pilots at mmWave band to
improve the beam prediction [14]. It is worth mentioning that the number of
mmWave pilots is not enough to meet the channel estimation requirements;
however, it can help refine the mmWave beam direction on top of the CSI
information from the sub-6GHz band. Moreover, the balance between the
auxiliary pilot overhead and the extrapolation performance can be further
optimized, and the pilot pattern along the frequency dimension can be improved
through the probabilistic sampling theory.

In Fig. 5 (b) we display the evaluation results of the mmWave beam prediction
based on DNN and FusionNet, respectively. The parameter configuration and the
definition of top-1 accuracy $Acc_{top1}$ are the same as in [14]. The
‘baseline’ curve is the performance of the DNN, and the ‘active antennas’
represent the mmWave antennas that participate in the mmWave channel
estimation. The number of active antennas in the mmWave system is taken as
$2,4,8,16$ respectively, and the mmWave pilot signal-to-noise ratio (SNR) is
$20$ dB. It can be seen from the Fig. 5(b) that the prediction accuracy of the
FusionNet with any number of mmWave active antennas is always better than that
of the baseline method, especially at low SNR for the sub-6 GHz channel
estimation. Moreover, as the number of active mmWave antennas increases, the
beam prediction accuracy of FusionNet improves significantly but slows down
after the number of active mmWave antennas exceeds $8$.

##  V Channel Extrapolation over Physical Terminal

Inspired by the channel-to-channel mapping, the authors of [1] verified that
the channel extrapolation among different terminals at any position is
possible, and then applied this mapping concept to the distributed (cell-free)
massive MIMO. With the key idea of [1], one can employ a subset of terminals
to infer the information for the other terminals, which is named $\mathrm{\it
terminal~{}extrapolation}$; this is illustrated in Fig. 6. If the terminals
are close or are in a similar environment, then the terminal extrapolation is
feasible and provides enough accuracy. However, with the increase of the
distance between terminals, the number of common scattering objects becomes
smaller and the latent relation becomes weaker, which deteriorates the
performance of the terminal extrapolation. In addition, this mapping would be
closely related with the link conditions, such as physical position of
terminals and hardware states, which causes difficulties for terminal
extrapolation. Hence, unlike the antenna and frequency extrapolations, the
terminal extrapolation occurs among different parameter subspaces with large
differences and it is difficult to realize satisfactory extrapolation
performance only through NNs.

Figure 6: The channel extrapolation over the physical terminal for a cell-free
massive MIMO system. Note that the terminal can be antenna array and user.

Meanwhile, with the application of various types of sensors, the communication
systems can avail of diverse information, such as users’ positions and
mobility states. Hence, one can incorporate the information from sensors to
enhance the performance of terminal extrapolation [15]. Explicitly, the
terminals are equipped with sensors to detect the map of the static
environment. Then, they can be divided into groups of terminals that share
similar electromagnetic scattering environments. Similar to the frequency
extrapolation, we can resort to the FusionNet to merge a few pilots and
sensing information to achieve a good extrapolation among terminals in one
group. Nevertheless, the terminals’ channels in different groups are less
correlated, and thus, these groups cannot share the common extrapolation NN.
Separately designing and training the extrapolation NNs for different groups
would yield a large computation burden.

Inspired by the humans’ ability to transfer knowledge from previous
experience, transfer learning has become a promising technology in the field
of machine learning to solve similar tasks with limited labeled data. This
aims to improve the performance of target tasks by exploiting the knowledge
from source tasks. Recently, Yang et al. utilized a meta-learning scheme and
effectively adapted the CSI estimation NN to the new environment [10], which
provides a feasible way to apply transfer learning or meta-learning to the
terminal extrapolation. Given the constraints on the performance of the
terminal extrapolation, one should also determine which group should be
selected to infer the NNs of the other groups. Moreover, the size of the group
should be carefully designed to balance the performance of terminal
extrapolation and training cost.

##  VI Future Research Directions

Although channel extrapolation has been established in theory and some
preliminary results have been presented, there are still many open problems
that need to be investigated over the large-scale antenna systems. We
highlight several potential research directions as follows:

###  VI-A Joint Channel Extrapolation over Antenna, Frequency and Physical
Terminal

The previously introduced three different channel extrapolation can be
designed in a joint manner. For example, one can apply the OFDM system with
large bandwidth into RIS-assisted communications, i.e., the combination of
antenna and frequency extrapolation. In such case, one needs to implement 2D
sampling along the antenna-frequency domain, and then use the small 2D
subspace to construct the full 2D space over the antenna and frequency
dimensions.

###  VI-B Optimization of NN and Resource Deployment

The existing works mainly demonstrated the effectiveness of DL-based channel
extrapolations, while further effort is needed to optimize the parameters of
the NN, e.g., the number of layers, as well as to consider optimal resource
deployment, e.g., location of auxiliary mmWave pilots over frequency
extrapolation, and distributed antennas/users scheduling over terminal
extrapolation.

###  VI-C Model-Driven Channel Extrapolation

The previously discussed channel extrapolation mainly works in a data-driven
manner. If the link conditions are good, the mapping function among different
subspaces may be modeled mathematically, and a model-driven approach may be
designed to enhance the performance of channel extrapolation. We may also
design schemes that could intelligently switch between the data-driven and
model-driven manners according to the complexity requirement and the dynamic
environment.

###  VI-D Vision-based Channel Extrapolation

In general, the communication environment information, such as building
location, obstacle shape and material, dynamic pedestrian, and vehicle
distribution, would determine the propagation of the electromagnetic waves at
any location and any frequency band. Hence, one may resort to sensors such as
camera or radar to capture the 3D scene image of the environment and then
design the corresponding DL algorithm to assist all three types of channel
extrapolation.

##  VII Conclusion

In this article, we have presented the channel extrapolation concept and
analyzed its three major challenges, i.e., the acquisition of the original
subspace information, the selection of the original subspace and the mapping
scheme from the original subspace to the targeted one. We divided the channel
extrapolation into three typical types: antenna extrapolation, frequency
extrapolation and terminal extrapolation. For antenna extrapolation, we found
that the ODE-based NN outperforms the traditional NN model. For frequency
extrapolation, when the gap between different frequency bands is large, we
need a small number of pilots to refine the extrapolation. For terminal
extrapolation, due to subspaces with large difference, it is difficult to
achieve a good performance only though NNs. Hence, the utilization of sensory
data and transfer learning can improve the extrapolation performance. Finally,
we have introduced several potential research directions on channel
extrapolation.

In summary, channel extrapolation is a very promising and powerful tool to
handle the complicated transmission scenarios when the mathematical modeling
of the channel is inaccurate or even unavailable. This is especially
applicable to mmWave massive MIMO, RIS-assisted communications and cell-free
massive MIMO, and deserves a full investigation and exploitation for such
communications systems, which will incorporate intelligence in the future.

## References

  * [1] M. Alrabeiah and A. Alkhateeb, “Deep learning for TDD and FDD massive MIMO: Mapping channels in space and frequency,” in _Proc. IEEE Asilomar Conference on Signals, Systems, and Computers_ , 2019, pp. 1465-1470.
  * [2] A. A. Esswie, M. El-Absi, O. A. Dobre, S. Ikki, and T. Kaiser, “Spatial channel estimation-based FDD-MIMO interference alignment systems,” _IEEE Wireless Commun. Lett._ , vol. 6, no. 2, pp. 254-257, Apr. 2017.
  * [3] A. Ali, N. Gonzalez-Prelcic, and R. W. Heath, Jr., “Spatial covariance estimation for millimeter wave hybrid systems using out-of band information,” _IEEE Trans. Wireless Commun._ , vol. 18, no. 12, pp. 5471-5485, Dec. 2019.
  * [4] Y. Han, M. Li, S. Jin, C. -K. Wen, and X. Ma, “Deep learning-based FDD non-stationary massive MIMO downlink channel reconstruction,” _IEEE J. Sel. Areas Commun._ , vol. 38, no. 9, pp. 1980-1993, Sept. 2020.
  * [5] X. Yi and C. Zhong, “Deep learning for joint channel estimation and signal detection in OFDM systems,” _IEEE Commun. Lett._ , vol. 24, no. 12, pp. 2780-2784, Dec. 2020.
  * [6] S. Liu, Z. Gao, J. Zhang, M. D. Renzo, and M. -S. Alouini,, “Deep denoising neural network assisted compressive channel estimation for mmWave intelligent reflecting surfaces,” _IEEE Trans. Veh. Technol._ , vol. 69, no. 8, pp. 9223-9228, Aug. 2020.
  * [7] Y. Yang, S. Zhang, F. Gao, C. Xu, J. Ma, and O. A. Dobre, “Deep learning based antenna selection for channel extrapolation in FDD massive MIMO,” _arXiv:2009.01653_ , 2020. [Online]. Available: https://arxiv.org/abs/2009.01653.
  * [8] S. Zhang, S. Zhang, F. Gao, J. Ma, and O. A. Dobre, “Deep learning optimized sparse antenna activation for reconfigurable intelligent surface assisted communication,” _arXiv:2009.01607_ , 2020. [Online]. Available: https://arxiv.org/abs/2009.01607.
  * [9] M. Xu, S. Zhang, C. Zhong, J. Ma, and O. A. Dobre, “Ordinary differential equation-based CNN for channel extrapolation over RIS-assisted communication,” _arXiv:2012.11794_ , 2020. [Online]. Available: https://arxiv.org/abs/2012.11794.
  * [10] Y. Yang, F. Gao, Z. Zhong, B. Ai, and A. Alkhateeb, “Deep transfer learning based downlink channel prediction for FDD massive MIMO systems,” _IEEE Trans. Commun._ , pp. 1-1, Aug. 2020.
  * [11] B. Li, Z. Zhang, and Y. Chen, “Beam selection in multi-user millimeter wave system based on out-of-band spatial information,” in _Proc. IEEE Int. Conf. Comput. Commun. (ICCC)_ , 2019, pp. 871-876.
  * [12] M. Alrabeiah and A. Alkhateeb, “Deep learning for mmWave beam and blockage prediction using sub-6 GHz channels,” _IEEE Trans. Commun._ , vol. 68, no. 9, pp. 5504-5518, Sept. 2020.
  * [13] T. Jiang, J. Zhang, M. Shafi, L. Tian, and P. Tang, “The comparative study of S-V model between 3.5 and 28 GHz in indoor and outdoor scenarios,” _IEEE Trans. Veh. Technol._ , vol. 69, no. 3, pp. 2351-2364, Mar. 2020.
  * [14] C. Bian, Y. Yang, F. Gao, and G. Y. Li, “FusionNet: Enhanced beam prediction for mmWave communications using sub-6GHz channel and a few pilots,” _arXiv:2009.02655_ , 2020. [Online]. Available: https://arxiv.org/abs/2009.02655.
  * [15] Y. Yang, F. Gao, C. Xing, J. An, and A. Alkhateeb, “Deep multimodal learning: Merging sensory data for massive MIMO channel prediction,” _IEEE J. Sel. Areas Commun._ , pp. 1-1, 2020.


[1,2]Jenny Taylor

[1]Uppsala University, Uppsala, Sweden

[2]GSI Helmholtzzentrum für Schwerionenforschung GmbH, Darmstadt, Germany

3]Forschungszentrum Jülich GmbH, Jülich, Germany

4]Ruhr-Universität Bochum, Institut für Experimentalphysik I, Bochum, Germany

# 4D Track Reconstruction on Free-Streaming Data at PANDA at FAIR

On Behalf of the PANDA Collaboration

<EMAIL_ADDRESS>Michael Papenbrock  Tobias Stockmanns  Ralf Kliemt  Tord
Johansson  Adeel Akram  Karin Schönning  *  *  [  [

###### Abstract

A new generation of experiments is being developed, where the challenge of
separating rare signal processes from background at high intensities requires
a change of trigger paradigm. At the future PANDA experiment at FAIR, hardware
triggers will be abandoned and instead a purely software-based system will be
used. This requires novel reconstruction methods with the ability to process
data from many events simultaneously.

A 4D tracking algorithm based on the cellular automaton has been developed
which will utilize the timing information from detector signals. Simulation
studies have been performed to test its performance on the foreseen free-
streaming data from the PANDA detector. For this purpose, a quality assurance
procedure for tracking on free-streaming data was implemented in the PANDA
software. The studies show that at higher interaction rates, 4D tracking
performs better than the 3D algorithm in terms of efficiency, 84$\%$ compared
to 77$\%$. The fake track suppression is also greatly improved, compared to
the 3D tracking with roughly a 50$\%$ decrease in the ghost rate.

###### keywords:

4D Tracking, PANDA, Quality Assurance, Free-Streaming Data, Cellular Automaton

##  1 Introduction

The search for rare processes and previously unknown particles push the
frontier of modern experimental hadron physics to higher and higher reaction
intensities. We are even about to reach a point where our ability to produce
abundant data outpaces our ability to retain them. This fact is correlated
with the rapid increase in processing power of computing hardware, in contrast
to the slower evolution of data transport and storage. As a result of the
ever-improving accelerators and detectors world-wide, the past decades have
seen a remarkably rapid progress, with discoveries such as the Higgs boson [1,
2] and exotic multiquark states [3, 4, 5]. In order to solve current puzzles
in hadron and particle physics, a new generation of facilities is underway.
For all of these, a crucial component will be to discriminate between signals
of interest and background at an early stage.

For a long time, hardware triggers served this purpose very well, selecting
potentially interesting physics events by identifying specific signatures e.g.
high energy loss, and storing the corresponding events for reconstruction and
more refined filtering later. As more and more of the low-hanging fruits of
subatomic physics have been harvested, the hunting ground for unknown physics
has to a large extent become processes whose signatures are expected to be
very similar to those of background. Hence, more sophisticated data filtering
methods are required – and the hardware trigger paradigm falls short. The new
generation of facilities is responding to this challenge by moving to
different variations of a trigger-less data acquisition, having data streaming
continuously from the detectors and selecting the data only after they have
been reconstructed online during their acquisition. These approaches are
referred to as software triggers.

Currently operating and upcoming experiments are embracing the new paradigm in
various degrees. The high-level trigger of the ALICE experiment performs the
full event reconstruction, calibration and high-level data quality assurance
in almost real time [6]. The LHCb collaboration is currently making efforts to
implement full online analysis chains in the software trigger apart from
computing observables for the event filtering [7]. XENON1T has been collecting
data altogether with a software-trigger [8]. At the future Facility for
Antiproton and Ion Research (FAIR), the CBM [9] and PANDA [10] experiments
will also employ fully software-based trigger systems.

The introduction of software triggers calls for a different treatment of the
detector signals. In the traditional approach, data are processed event-by-
event in the form of contained data packages, containing all detector signals
collected within a pre-defined time-window as a response to the hardware
trigger. In the approach needed for free-streaming data, a continuous stream
of data is processed and organised based on spatial and timing information.
Tracks can then be formed e.g. by 4D track reconstruction where time is used
in addition to spatial coordinates. A 4D Cellular Automaton (CA) is e.g.
utilized at CBM [11] with excellent performance.

Track reconstruction algorithms are evaluated using Quality Assurance (QA)
methods. For tracking event-by-event, there are established methods such as
those used and outlined in Ref. [12]. However, QA methods for tracking on
free-streaming data are hard to find within hadron and HEP literature.

In this article, a 4D CA track finding algorithm developed for a continuous
stream of hit data from the PANDA experiment is presented. In addition, a
quality assurance method to evaluate the performance of the track finding was
developed which is the first of its kind and is outlined in detail in this
article.

##  2 The PANDA experiment

Figure 1: The PANDA detector. All subdetectors are labeled.

PANDA (antiProton ANnihilations at DArmstadt) [13] is a future multipurpose
detector designed to investigate QCD in the energy region where quarks form
hadrons. The broad physics program includes four main pillars: strangeness
physics, charm and exotics, nucleon structure and hadrons in nuclei [14].

The antiproton beam will be delivered by the High Energy Storage Ring (HESR),
a racetrack-shaped ring with a circumference of $575\text{\,}\mathrm{m}$. The
beam will cover a momentum range from 1.5 GeV/c to 15.0 GeV/c. In Fig. 1, the
beam enters from the left.

The detector, shown in Fig. 1, is divided into a target solenoid spectrometer
surrounding the interaction point and a forward dipole spectrometer to detect
particles emitted at small scattering angles. Both spectrometers comprise
subdetectors for tracking, particle identification and calorimetry. The track
reconstruction algorithm presented in this work treats signals from the
central Straw Tube Tracker (STT) [15] and can be extended to also include the
Micro Vertex Detector (MVD) [16], the Gas Electron Multipliers (GEM) [17] and
the Forward Tracking System (FTS) [18]. The coordinate system is defined with
the z-direction along the beam line and the xy-plane perpendicular to the beam
line.

###  2.1 The Straw Tube Tracker

The main tracking detector of the central part of PANDA is the STT, Fig. 2. It
consists of 4224 closely packed single-channel readout drift tubes placed in a
hexagonal pattern. The detector has a cylindrical shape with roughly 27 tube
layers in the radial direction, 19 parallel layers for xy-reconstruction and 8
central layers of tilted tubes, $\pm$2.9∘ with respect to the beam line, for
z-reconstruction. The detector will be placed between
$15.0\text{\,}\mathrm{cm}$ and $41.8\text{\,}\mathrm{cm}$ in radial direction
and the tubes are $140.0\text{\,}\mathrm{cm}$ long with a diameter of
$1.0\text{\,}\mathrm{cm}$. The tubes will be filled with a 90/10 gas mixture
of $\text{Ar/CO}_{\text{2}}$. The walls consist of a
$27\text{\,}\mathrm{\SIUnitSymbolMicro m}$ thick layer of aluminized mylar
foil and the tubes will have $20\text{\,}\mathrm{\SIUnitSymbolMicro m}$ thick
anode wires in the center that are made of gold-plated tungsten.

When a charged particle traverses a tube, the gas will be ionized and free
electrons are created along the trajectory of the particle. An applied
electric field will make the electrons accelerate towards the anode wire. By
measuring the arrival time of the signal precisely and in combination with
other detectors it is possible to determine the drift time of the electrons.
Based on that the isochrone radius is calculated, a circle centered at the
tube wire and going through the point of closes approach of the particle to
the wire. The maximum drift time, i.e. the time it takes the electron to drift
to the wire, is around $250\text{\,}\mathrm{ns}$ for electrons created close
to the tube wall.

Figure 2: Cutaway view of the Straw Tube Tracker. The detector surrounds the
beamline and has vertical cavities for the target beamline.

###  2.2 Free-streaming detector data

The HESR antiproton beam will be quasi-continuous, and give rise to Poisson
distributed instantaneous interaction rates when interacting with the fixed
internal proton or nuclear target. The revolution time of the beam is around
$2000\text{\,}\mathrm{ns}$, corresponding to a frequency of
$500\text{\,}\mathrm{kHz}$, but the exact number depends on the beam momentum.
The beam will be active during 80$\%$ of the time and a gap with no beam
during 20$\%$. This structure creates natural separation for data packaging.

During the first phase of operation, the luminosity will be 2 $\times$
10${}^{\text{31}}$ cm${}^{\text{-1}}$s${}^{\text{-1}}$ resulting in an average
interaction rate of 2.0 MHz. The final design luminosity of PANDA is 2
$\times$ 10${}^{\text{32}}$ cm${}^{\text{-1}}$s${}^{\text{-1}}$ resulting in
an average interaction rate of $20.0\text{\,}\mathrm{MHz}$. The raw data rate
before the software trigger will be around 200 GB/s. This needs to be reduced
by a factor of 1000.

The HESR beam structure in combination with the foreseen high intensities
implies that signals originating from different physics reactions will overlap
in time. At an average interaction rate of $2.0\text{\,}\mathrm{MHz}$, the
average time between the start of two consecutive events will be
$500\text{\,}\mathrm{ns}$. In Fig. 3, it is however shown that many
consecutive events are separated by much less than $500\text{\,}\mathrm{ns}$.
At the PANDA design interaction rate of $20.0\text{\,}\mathrm{MHz}$, the
average time between two events will be $50\text{\,}\mathrm{ns}$.

Figure 3: The time between the start of two consecutive events at 2.0 MHz. The
average time is 500 ns at this interaction rate. Many events occur closer in
time as well as more separated.

Figure 4: Detector occupancy of the PANDA Straw Tube Tracker at low
intensities, where events do not overlap in time (left) and high intensities,
where up to 40 events overlap (right).

Each subdetector at PANDA will be self-triggering so the detector information
is read out independently of other subdetectors. The information is then
synchronized and sorted in time by using the time-stamp each detector has to
assign to its data. The reconstruction and event building can subsequently
take place. This, combined with the Poisson distributed interaction rates,
means that the hits from several events will be processed simultaneously.
Since the STT has a dift-time of up to 250 ns, signals from different events
will have a higher tendency to overlap in time in this detector compared to
others, as illustrated in Fig. 4.

####  2.2.1 Simulations for Free-Streaming Data

The free-streaming data is simulated in FairRoot [19] upon which the PANDA
software PandaRoot [20] builds. Fig. 5 illustrates the difference between
time-sorted and event-sorted simulations. In both cases, the events are
generated one-by-one at the simulation stage. This is followed by the
digitization stage where the output from the simulation is converted to
signals that realistically mimics the detector output, including spatial
resolution, detector granularity, timestamps and pulse shapes. At this stage,
event-sorted and time-sorted simulations differ: while in the first case, the
digitized hits are sorted event-wise, in the time-sorted case, the digitized
hits are sorted according to time instead, and passed on to the next
reconstruction stage in pre-defined time intervals into bursts. Hence, the
event-sorted simulation chain is synchronous while the time-sorted chain is
asynchronous. The latter means that data reconstruction operates on detector
hits coming from several events simultaneously.

Figure 5: The event-sorted simulation (left) compared to the time-sorted
simulation (right). The event-sorted simulation is synchronous until the
software trigger and the time-sorted simulation is asynchronous until the
reconstruction and synchronous following that. One burst of data corresponds
to events within a certain time-interval and a superburst consists of a number
of bursts

When processing time-sorted data, a time interval for obtaining the hits must
be chosen. In the PANDA STT detector, the time structure of the hits is shown
in Fig. 6 for two cases. At an interaction rate of 2.0 MHz (left panel), the
events are fairly well separated in time since the average time between two
events exceeds the maximum drift time of the electrons. However, at 20.0 MHz
(right panel), signals from different events are overlapping in time. The
larger gaps at around 2000, 4000, 6000, 8000 and 10000 ns reflect the time
structure of the beam.

In the reconstruction of free-streaming data, the data can be grouped in
certain time intervals. For this purpose, two methods are available in
PandaRoot. The first method is to retrieve all data within a fixed time
interval. This leads to a structure of bursts of data of the same length in
time. The second method is to retrieve all data between two time gaps in the
data stream have been found. This leads to bursts of varying length in time
and assumes that the data of one event is close in time and that larger time
gaps in the data stream can be used to separate events from each other. In an
event-by-event simulation the data is retrieved already grouped into the
correct event structure.

Figure 6: Time-stamps of the hits in the STT at 2.0 MHz (left) and 20.0 MHz
(right). The time-stamp peaks at 2.0 MHz correspond roughly to one event.

##  3 4D track reconstruction

The advent of fast silicon detectors has led to the introduction of 4D track
reconstruction, where a timestamp is assigned to each point (or hit) along the
track. In environments with high track multiplicity, timing information is
expected to help distinguishing between hits from different particles.

In the following, an algorithm is presented that was originally developed to
operate on event-sorted data but later updated for time-sorted data. This
track finder combines a CA [21] for pattern recognition with a Riemann
paraboloid fitting procedure [22] for track parameter estimation. The
algorithm is based on pattern recognition in the PANDA STT, and is general in
the sense that it does not require tracks to originate from the beam-target
interaction point. Hence, it should be able to reconstruct tracks from
secondary vertices, such as tracks from hyperon decay products. In this work,
the algorithm was developed to perform tracking in 4D, utilizing the timestamp
of each hit and to work on time-sorted data.

###  3.1 Track reconstruction event-by-event

The CA-based tracking algorithms operate on a grid of cells, which can have
e.g. a 1D or a 2D/3D rectangular or hexagonal layout. The state of a cell is
determined by the state of its neighbours. Since CA algorithms are inherently
local, they are suitable for parallelization which has made them popular for
track reconstruction purposes.

Given the tightly packed, hexagonal layout of the STT, CA algorithms are
suitable for track finding in this detector and was first applied in Refs [23,
24]. Here, each STT tube translates into a cell.

In CA algorithms, the state of a cell is either active or inactive. In this
case with the STT tracker, active means that a hit is read out from the
corresponding straw. Whether an active cell is a part of a pattern or not is
uniquely determined by the states of its neighbours.

The procedure is illustrated in Fig. 7. After particles traverse the detector
(Fig. 7(7(a))), the cells that correspond to detector hits are activated (Fig.
7(7(b))). All activated cells are categorized as unambiguous (blue), if they
have one or two neighboring activated cells, or ambiguous (yellow), if they
have more activated neighboring cells (Fig. 7(7(c))). All unambiguous cells
are assigned to one tracklet, a preliminary track segment, and all ambiguous
cells are assigned to the best matching track after a track fitting is
performed (Fig. 7(7(d))). The algorithm for selecting the neighborhood is
shown in Alg. 1. The reasoning behind the hit classifications is the
following. If a hit is surrounded by no other hits, it is not considered to be
part of a track or tracklet, but rather a random background hit. However,
being surrounded by one or two other hits suggests that the hit is part of a
track or tracklet that either ends in this hit or passes through. Any
additional neighbours beyond two are usually caused by several tracks crossing
each other or a random background hit occurring close to a track, hence the
ambiguity. However, the classification is made independently of any cells
outside of the neighborhood. In case of ambiguous hits within a track
candidate, the algorithm produces separate track segments which are
disconnected at the point of the ambiguous hit. Consequently, the algorithm
creates many track segments that still have to be connected. Track segments
that are connected via ambiguous hits can be connected using a preliminary
parameter estimation of the tracks in the $xy$-plane by the Riemann fit. Based
on these parameters, track segments are combined into common tracks.

(a)

(b)

(c)

(d)

Figure 7: Illustration of the Cellular Automaton workflow. (7(a)) Particles
traverse the detector. (7(b)) Cells corresponding to detector hit are marked
as active. (7(c)) Active cells are classified as unambiguous (blue) or
ambiguous (yellow). (7(d)) Track fits are used to resolve ambiguities and
merge tracklets.

Data: STT hits

Result: clustered STT hits

begin

for  _each STT hit_ do

if  _STT hit is neighbouring another STT hit_ then

accept hits as neighbours

else

reject hits as neighbours

return _clustered hits_

Algorithm 1 3D Cellular Automaton

###  3.2 Track reconstruction of free-streaming data

To adapt the reconstruction algorithms that work event-by-event to also work
well for the free-streaming data with event-mixing, spatial information from
the hits alone will not be sufficient to perform the pattern recognition (see
Sec. 2.2). The timing information of the electronic signals has to be taken
into account as well.

In PandaRoot simulations, the time-stamp of a hit in the STT, $t_{hit}$, is
calculated by the time at which a reaction occurred $t_{event}$, the travel
time of a particle from its point of creation to the detector element that was
hit $t_{travel}$, and the drift time of the electrons inside a straw tube from
the point of closest approach between the particle trajectory and the tube’s
anode wire i.e. the time it takes the first electrons to arrive, $t_{drift}$.
The final expression becomes

$t_{hit}=t_{event}+t_{travel}+t_{drift}.$ (1)

Under realistic conditions in the PANDA experiment, the orders of magnitude
for these values would be quite different. While $t_{event}$ would be
continuously increasing, the difference between adjacent events varies because
of the Poisson distributed time between two consecutive events with a high
probability of very short time intervals between events (see Fig. 3). The
travel time of a particle is considerably shorter with
$\mathcal{O}(t_{travel})=0.01-1\,\text{ns}$. It becomes negligible when
compared to the drift time of the electrons, i.e.
$\mathcal{O}(t_{drift})=100\,\text{ns}$. However, with the mean time between
events being of a similar or even smaller order of magnitude than the drift
time, mixing of hit signal between two or more events becomes possible and
even common.

Data: STT hits, threshold time

Result: clustered STT hits

begin

for  _each STT hit_ do

if  _STT hit is neighbouring another STT hit_ then

if  _time stamps of both STT hits ¡ threshold time_ then

accept hits as neighbours

else

reject hits as neighbours

return _clustered hits_

Algorithm 2 4D Cellular Automaton

To perform tracking in this high occupancy environment, the approach in Sec.
3.1 was modified to include the hit time stamps as given in Eq. 1. The
resulting algorithm is shown in Alg. 2. If spatially neighboring hits occur
closer in time than 250 ns, they are classified as neighbors, otherwise
discarded and cannot be contained in the same tracklet.

##  4 Quality assurance for track reconstruction on free-streaming data

A class for evaluating the efficiency and other quality variables is available
in PandaRoot in order to have a common basis for evaluating the performance of
the PANDA tracking algorithms. The quality of the reconstruction algorithms is
assessed by comparing the contents of the reconstructed tracks with their
generated counterparts. It is not known, a priori, which generated track
corresponds to the reconstructed track. The true track is therefore defined as
that to which the majority of the hits in the reconstructed track belong.

A reference track set must be chosen in order to have relevant generated
tracks to compare the reconstructed tracks to. This is done using an ideal
track finder that uses the generated track with the hits to create a
reconstructed track object from this. The performance is then only limited by
the detector acceptance and efficiency. One benefit of creating such an object
is that the hits in the ideal track and the realistically reconstructed track
can be directly compared since it has the same data structure. Another benefit
is that different hit conditions, that correspond to a minimum hit requirement
in different detectors for a track to be reconstructed, can be imposed on the
ideal track. This is needed since the efficiency should be normalized to those
tracks that can be reconstructed in the relevant subdetectors. The condition
used for this study is $\geq$ 6 STT hits.

The matching of the ideal track to the realistically reconstructed track is
performed through a system of links that contain the information about where
an object is stored and to which objects it relates to. For example, a hit
contains links to the monte-carlo particles that created it.

The hit finding efficiency is defined as

$\epsilon_{hit}=\frac{N_{correct}}{N_{gen}},$ (2)

where $N_{gen}$ is the number of hits in the generated track and $N_{correct}$
is the number of found hits in the reconstructed track from the generated
track. If $\epsilon_{hit}$ = 1, all hits from the generated track were found.
The hit purity within a track is defined as

$p_{hit}=\frac{N_{correct}}{N_{found}},$ (3)

where $N_{found}$ is the total number of found hits from any generated track
and $N_{correct}$ is the number of found hits from the true generated track.
If $p_{hit}$ = 1, only hits from the true generated track were found and if
$p_{hit}$ $<$ 1, hits from additional generated tracks were found. If hits
from generated tracks that are not the true track are included in the
reconstructed track, these hits are referred to as impurities. No noise hits
were included in this study.

Track categories are defined in terms of the hit finding efficiency and
purity:

  1. 1.

Fully, purely, found: all hits from a generated track were found and there are
no impurities in the reconstructed track. $\epsilon_{hit}$ = 1 and $p_{hit}$ =
1.

  2. 2.

Fully, impurely, found: all hits from a generated track were found and at
least 70$\%$ of all hits are from the true track. $\epsilon_{hit}$ = 1 and 0.7
$<$ $p_{hit}$ $<$ 1.

  3. 3.

Partly, purely, found: not all hits from a generated track were found and
there are no impurities in the reconstructed track. 0.7 $<$ $\epsilon_{hit}$
$<$ 1 and $p_{hit}$ = 1.

  4. 4.

Partly, impurely, found: not all hits from a generated track were found and at
least 70$\%$ of all hits are from the true track. 0.7 $<$ $\epsilon_{hit}$ $<$
1 and 0.7 $<$ $p_{hit}$ $<$ 1.

  5. 5.

Ghost: no true generated track could be identified. $p_{hit}$ $<$ 0.7.

  6. 6.

Clone: one generated track was reconstructed more than once. The track with
the most hits from the true generated track is referred to as the real track
and other reconstructed tracks which have been created from the same generated
track are referred to as clones.

The tracks in the first four categories constitute the set of correctly
reconstructed tracks whereas the tracks in the final two categories are
referred to as wrongly reconstructed or false tacks.

The track finding efficiency is defined as

$\epsilon_{track}=\frac{N_{Reco}}{N_{Gen}},$ (4)

where $N_{Gen}$ is the number of generated tracks and $N_{Reco}$ is the number
of reconstructed tracks. Ghost and clone tracks are not included in the
calculation of the track finding efficiency.

The two main differences between the event-sorted and time-sorted tracking
quality assurance is 1) the way the data is read (see Sec. 2.2.1) and 2) the
way the matching between tracks is carried out. In the simulation for free-
streaming data, the matching between the realistically reconstructed track and
the ideal track is performed by matching a unique link to each track of the
tracks to each other. In the event-by-event reconstruction, this is done using
an index.

The benefit of the method for free-streaming data is that it is more general
than the event-by-event method and works for both ways of retrieving the data.
The disadvantage is that it is considerably slower using the full link system.
However, since the quality assurance is run offline, this is not problematic.

##  5 Results

###  5.1 Data Samples

In order to benchmark the algorithms, a data sample of 1000 hadronic
background events based on the Fritiof Model (FTF) [25, 26] was generated with
PandaRoot. This was done at four different interaction rates: 0.5, 1.0, 2.0
and 4.0 MHz. The intervals are chosen around 2.0 MHz to include the double
interaction rate at 4.0 MHz and narrower intervals closer to 0.5 MHz where the
behavior of the 4D algorithm is expected to be similar to that of the 3D
algorithm. The interaction rates were chosen within an interval around 2.0 MHz
which is the expected average interaction rate at the start of PANDA. The beam
time structure and Poisson distributed interaction rate is included in the
simulations. A beam momentum of 6.2 GeV/c was chosen as a mid-range point to
benchmark the algorithm. For a reference track set, the ideal track finder is
used with the requirement that $\geq$ 6 STT hits are present in the track.
Moreover, the data is sorted in time and then retrieved in bursts of 2000 ns
for both the ideal and realistic tracking. The time interval mimics the beam
revolution time.

There is no pre-filtering of tracks on e.g. transverse momentum or point of
origin in the simulations presented in this study. This means that challenging
cases such as particles that are trapped in the magnetic field and curl as
well as decay products from long-lived particles are included.

The number of reconstructed tracks within 1000 bursts at the different
interaction rates can be seen in Fig. 8. The number of ideal tracks scales
linearly with the interaction rate. This is because of the increase in number
of tracks contained within one burst when increasing the interaction rate
allows for more data within the same interval due to the Poisson statistics.
In order to reduce the runtime of the QA, 8557 tracks from 400 bursts are used
in this data point to evaluate the efficiency of the reconstruction. This
number is sufficient since the errors in the efficiencies are so small they
are not visible in the graphs.

Figure 8: The number of reconstructed ideal tracks in 1000 bursts. Each burst
contains data within a 2000 ns time interval.

###  5.2 Varying interaction rates

The efficiency is presented for both the 3D version of the CA as well as the
4D version for different interaction rates in the left panel of Fig. 9. The
efficiencies for the four track categories, fully pure, fully impure,
partially pure and partially impure as well as the full efficiency are shown.
At 0.5 MHz there is little temporal overlap between the events in the STT and
the 3D and 4D version of the CA are expected to have a similar efficiency. It
can be seen from the figure that this is also the case. However, at higher
interaction rates the 4D version yields a larger total efficiency. The largest
contribution to the full efficiency comes from partly pure tracks. The impure
tracks contribute with almost 20$\%$ for the 3D CA at 4.0 MHz, but contributes
with around 10$\%$ over the full range for the 4D CA.

The fake rate (ghost and clone rate) is presented for varying interaction
rates in the left panel of Fig. 9 for both the 3D and 4D version of the CA.
The time-cut is 250 ns (see Sec. 3.2). The number of fake tracks in each
category is normalised to the number of ideal true tracks. It is clear that
including the time information decreases the fake rate and the effect is most
prominent at higher interaction rates.

###  5.3 Varying time-cut

The effect of the time-cut value on the efficiency for the 4D CA is presented
in Fig 10, left panel. The interaction rate is 2.0 MHz in all data points. The
efficiency is evaluated at a time-cut of the nominal 250 ns as well as 50,
100, 150, 200 and 300 ns. If the time-cut is below 250 ns, the number of fully
pure tracks decrease while the number of partially pure tracks increase.
Hence, the full efficiency remains stable. At a time-cut less than 100 ns, the
full efficiency starts to drop since too few hits are allowed to form a
tracklet. This is because the time-cut is so tight, true hits start to get
discarded from the track.

The fake rate as a function of the value of the time-cut in the 4D CA at 2.0
MHz interaction rate can be seen in Fig. 10, right panel. The fake rate, for
both ghosts and clones, is reduced for stricter time-cuts. Therefore, a 250 ns
time-cut is a good choice to keep the efficiency high while simultaneously
suppressing the fake tracks. This value also corresponds to the maximum drift
time of the electrons.

Figure 9: Efficiency (left) and the fake rate (right) for the 3D CA (dashed,
gray, lines) and the 4D CA (solid, black, lines) vs the interaction rate. The
time-cut for the 4D CA is 250 ns.

Figure 10: Efficiency (left) and fake rate (right) for the 4D CA vs the time-
cut at 2.0 MHz interaction rate.

###  5.4 Run-Time Performance

Since the reconstruction algorithm is being developed to operate online, speed
is a consideration. The computational performance for the full reconstruction
is shown in Fig. 11 for the different interaction rates. The tests were
performed on a laptop with the following hardware specifications:

  * •

Processor: Intel Core i7-1185G7, 3.00 GHz

  * •

Memory: 32 GB RAM

The time is calculated as the average processing time for 100 data bursts for
each interaction rate. The increasing number of hits per burst makes the
processing time per event longer at higher interaction rates. There is a
linear dependence between the processing time and the interaction rate.

The time-cut inclusion in Alg. 2 is the only part that separates the 4D
version from the 3D version. The run-time for this specific part of the code
was therefore examined more closely. The increase in run-time when moving from
the 3D version to the 4D is negligible compared to the full time for the
reconstruction at all interaction rates. A larger increase occurs when going
from the event-sorted reconstruction to the time-sorted and processing more
data simultaneously in bunches.

Figure 11: The time per event for running the full reconstruction for
different interaction rates.

##  6 Conclusions and Outlook

A Cellular Automaton-based track reconstruction algorithm and the tracking
quality assurance procedure in PandaRoot has been adjusted to work for time-
sorted data. The tracking algorithm has also been developed to work in 4D,
taking into account both the spatial dimensions and time. A comparison between
the 3D method and 4D method shows that at 4.0 MHz interaction rate, the
efficiency is higher for the 4D version, 83$\%$, than for the 3D version with
a 73$\%$ efficiency. In addition, the 4D method yields a much lower fake rate
of tracks at higher interaction rates.

Some improvements to the algorithm will be made in the future. The signal from
a straw tube is characterized by two timestamps, the leading edge time,
$t_{LE}$, when the signal in the readout electronics reaches above threshold
and the trailing edge time, $t_{TE}$ when the signal drops below threshold.
Currently, the procedure is used with $t_{LE}$. However, in the future it will
be used with $t_{TE}$, when this is implemented in the software. This is
because $t_{TE}$ is independent of the isochrone radius and therefore
contributes with less uncertainty.

This is the first time the quality of a track reconstruction algorithm that
works on free-streaming data for PANDA has been evaluated with the standard
quality assurance of PandaRoot. Therefore, this marks an important step
towards a realistic track reconstruction for PANDA. The quality assurance
procedure will be useful for the developments of further algorithms for free-
streaming data at PANDA.

##  7 Conflict of Interest

The authors declare that we have no conflicts of interest.

##  8 Acknowledgments

The authors would like to thank Peter Wintz and Gabriela Pérez Andrade for
fruitful discussions about the STT readout.

## References

  *   * The ATLAS collaboration [2012] The ATLAS collaboration: Observation of a new particle in the search for the Standard Model Higgs boson with the ATLAS detector at the LHC. Physics Letters B 716, 1–29 (2012) https://doi.org/10.1016/j.physletb.2012.08.020
  * The CMS collaboration [2012] The CMS collaboration: Observation of a new boson at a mass of 125 GeV with the CMS experiment at the LHC. Physics Letters B 716, 30–61 (2012) https://doi.org/10.1016/j.physletb.2012.08.021
  * The Belle Collaboration [2003] The Belle Collaboration: Observation of a narrow charmoniumlike state in exclusive ${B}^{\pm{}}\rightarrow{K}^{\pm{}}{\pi}^{+}{\pi}^{-}j/\psi$ decays. Phys. Rev. Lett. 91, 262001 (2003) https://doi.org/10.1103/PhysRevLett.91.262001
  * Aubert [2005] Aubert, B.t.: Observation of a broad structure in the ${\pi}^{+}{\pi}^{-}j/\psi$ mass spectrum around $4.26\text{ }\text{ }\mathrm{GeV}/{c}^{2}$. Phys. Rev. Lett. 95, 142001 (2005) https://doi.org/10.1103/PhysRevLett.95.142001
  * Ablikim [2013] Ablikim, M.t.: Observation of a charged charmoniumlike structure in ${e}^{\mathbf{+}}{e}^{\mathbf{-}}\rightarrow{\pi}^{\mathbf{+}}{\pi}^{\mathbf{-}}j/\psi$ at $\sqrt{s}\mathbf{=}4.26\text{ }\text{ }\mathrm{GeV}$. Phys. Rev. Lett. 110, 252001 (2013) https://doi.org/10.1103/PhysRevLett.110.252001
  * Acharya et al. [2019] Acharya, S., et al.: Real-time data processing in the ALICE High Level Trigger at the LHC. Comput. Phys. Commun. 242, 25–48 (2019) https://doi.org/10.1016/j.cpc.2019.04.011 arXiv:1812.08036 [physics.ins-det]
  * Aaij et al., [2019] Aaij et al.,: Design and performance of the LHCb trigger and full real-time reconstruction in Run 2 of the LHC. JINST 14(04), 04013 (2019) https://doi.org/10.1088/1748-0221/14/04/P04013 arXiv:1812.10790 [hep-ex]
  * Aprile et al. [2019] Aprile, E., et al.: The XENON1T Data Acquisition System. JINST 14(07), 07016 (2019) https://doi.org/%****␣sn-article.bbl␣Line␣150␣****10.1088/1748-0221/14/07/P07016 arXiv:1906.00819 [physics.ins-det]
  * Höhne, C. et al., [2011] Höhne, C. et al.,: The CBM Physics Book: Compressed Baryonic Matter in Laboratory Experiments, pp. 849–972. Springer, Berlin, Heidelberg (2011). https://doi.org/10.1007/978-3-642-13293-3_7 . https://doi.org/10.1007/978-3-642-13293-3_7
  * Lutz et al. [2009] Lutz, M.F.M., et al.: Physics Performance Report for PANDA: Strong Interaction Studies with Antiprotons (2009) arXiv:0903.3905 [hep-ex]
  * Akishina [2016] Akishina, V.: Four-dimensional event reconstruction in the CBM experiment. PhD Dissertation, Frankfurt am Main, Germany (2016)
  * Ikegami Andersson, W. et al. [2021] Ikegami Andersson, W., et al.: A Generalized Approach to Longitudinal Momentum Determination in Cylindrical Straw Tube Detectors. Comput. Softw. Big Sci. 5 (2021) https://doi.org/10.1007/s41781-021-00064-0
  * The PANDA Collaboration [2005] The PANDA Collaboration: Technical Progress Report for PANDA - Strong Interaction Studies with Antiprotons. FAIR-ESAC (2005)
  * Barucca et al. [2021] Barucca, G., et al.: PANDA Phase One. The European Physical Journal A 57 (2021) https://doi.org/10.1140/epja/s10050-021-00475-y
  * Erni et al. [2013] Erni, W., et al.: Technical design report for the PANDA (AntiProton Annihilations at Darmstadt) Straw Tube Tracker. Eur. Phys. J. A 49, 25 (2013) https://doi.org/10.1140/epja/i2013-13025-8 arXiv:1205.5441 [physics.ins-det]
  * Erni et al. [2012] Erni, W., et al.: Technical Design Report for the: PANDA Micro Vertex Detector (2012) arXiv:1207.6581 [physics.ins-det]
  * Divani Veis et al. [2018] Divani Veis, N., Ehret, A., Firoozabadi, M.M., Karabowicz, R., Maas, F., Saito, N., Saito, T.R., Voss, B.: Implementation of the $\bar{P}$ANDA Planar-GEM tracking detector in Monte Carlo simulations. Nucl. Instrum. Meth. A 880, 201–209 (2018) https://doi.org/10.1016/j.nima.2017.10.036
  * Smyrski et al. [2017] Smyrski, J., et al.: Design of the forward straw tube tracker for the PANDA experiment. JINST 12(06), 06032 (2017) https://doi.org/10.1088/1748-0221/12/06/C06032
  * Stockmanns [2015] Stockmanns, T.: Continuous-readout simulation with fairroot on the example of the panda experiment. Journal of Physics: Conference Series 664, 072046 (2015) https://doi.org/10.1088/1742-6596/664/7/072046
  * S. Spataro for the PANDA Collaboration [2011] S. Spataro for the PANDA Collaboration: The PandaRoot framework for simulation, reconstruction and analysis. J. Phys.: Conf. Ser. 331(032031) (2011) https://doi.org/10.1088/1742-6596/331/3/032031
  * Wolfram [1983] Wolfram, S.: Statistical Mechanics of Cellular Automata. Rev. Mod. Phys. 55, 601 (1983) https://doi.org/10.1103/RevModPhys.55.601
  * A. Strandlie, J. Wroldsen and R. Frühwirth [2002] A. Strandlie, J. Wroldsen and R. Frühwirth: Treatment of multiple scattering with the generalized Riemann sphere track fit. Nucl. Instrum. Meth. A 488(1-2), 332–341 (2002) https://doi.org/10.1016/S0168-9002(02)00465-
  * Schumann [2013] Schumann, J.: Entwicklung eines schnellen Algorithmus zur Suche von Teilchenspuren im “Straw Tube Tracker” des PANDA-Detectors. Bachelor Thesis, FZ Jülich, Germany (2013)
  * Schumann [2015] Schumann, J.: Beschleunigung eines Spurfindealgorithmus für den Straw Tube Tracker des PANDA-Detektors durch Parallelisierung mit CUDA C. Master Thesis, FZ Jülich, Germany (2015)
  * B. Andersson et al. [1987] B. Andersson, et al.: A model for low-pT hadronic reactions with generalizations to hadron-nucleus and nucleus-nucleus collisions. Nucl. Phys. B 281, 289–309 (1987)
  * Nilsson-Almquist and Stenlund [1987] Nilsson-Almquist, B., Stenlund, E.: Interactions between hadrons and nuclei: The Lund Monte Carlo - FRITIOF version 1.6 -. Comp. Phys. Commun. 43, 387–397 (1987)