Baptiste Chatelier
email: baptiste.chatelier@insa-rennes.fr

Luc Le Magoarou

Getachew Redieteab

Efficient Deep Unfolding for SISO-OFDM Channel Estimation

Keywords: Deep Unfolding, Frugal AI, SISO-OFDM channel estimation, Sparse recovery

In modern communication systems, channel state information is of paramount importance to achieve capacity. It is then crucial to accurately estimate the channel. It is possible to perform SISO-OFDM channel estimation using sparse recovery techniques. However, this approach relies on the use of a physical wave propagation model to build a dictionary, which requires perfect knowledge of the system's parameters. In this paper, an unfolded neural network is used to lighten this constraint. Its architecture, based on a sparse recovery algorithm, allows SISO-OFDM channel estimation even if the system's parameters are not perfectly known. Indeed, its unsupervised online learning allows to learn the system's imperfections in order to enhance the estimation performance. The practicality of the proposed method is improved with respect to the state of the art in two aspects: constrained dictionaries are introduced in order to reduce sample complexity and hierarchical search within dictionaries is proposed in order to reduce time complexity. Finally, the performance of the proposed unfolded network is evaluated and compared to several baselines using realistic channel data, showing the great potential of the approach.

I. INTRODUCTION

Recently, machine learning techniques have emerged as a promising solution in many wireless communications areas [START_REF] Shea | An introduction to deep learning for the physical layer[END_REF], [START_REF] Wang | Deep learning for wireless physical layer: Opportunities and challenges[END_REF] such as beamforming [START_REF] Magoarou | Deep learning for location based beamforming with NLOS channels[END_REF], [START_REF] Alkhateeb | Deep learning coordinated beamforming for highly-mobile millimeter wave systems[END_REF], channel charting [START_REF] Yassine | Leveraging triplet loss and nonlinear dimensionality reduction for on-the-fly channel charting[END_REF]- [START_REF] Ferrand | Tripletbased wireless channel charting: Architecture and experiments[END_REF] or channel mapping [START_REF] Magoarou | Similarity-based prediction for channel mapping and user positioning[END_REF], [START_REF] Alrabeiah | Deep learning for TDD and FDD Massive MIMO: Mapping channels in space and frequency[END_REF]. The Deep Unfolding machine learning approach [START_REF] Shlezinger | Model-based deep learning[END_REF]- [START_REF] Balatsoukas-Stimming | Deep unfolding for communications systems: A survey and some new directions[END_REF] is very promising as it profits from both the controlled complexity of classical signal processing approaches and the flexibility of machine learning techniques. Indeed, this approach considers that iterative algorithms can be unfolded as neural networks, that can be trained, where each layer represents one iteration of the algorithm.

In the field of channel estimation, classical statistical estimation techniques such as the Least Squares (LS) or the Minimum Mean Squared Error (MMSE) have been extensively used in the past. However, those techniques suffer from several drawbacks: on one hand, for the LS estimator, there is a huge Mean Squared Error (MSE), on the other hand, for the MMSE estimator, there is a huge computational complexity. Other approaches have been envisioned to counter those drawbacks: one of them is the usage of sparse recovery algorithms. It is well known that propagation channels are dominated by a few strong propagation paths: the channel is then said to be sparse. It has been shown that one can use that sparsity notion to propose channel estimation strategies relying on sparse recovery algorithms such as Matching Pursuit (MP) [START_REF] Kang | Matching pursuits channel estimation for an underwater acoustic OFDM modem[END_REF]- [START_REF] Yassine | mpNet: variable depth unfolded neural network for massive MIMO channel estimation[END_REF]. However, those techniques rely on the knowledge of a physical wave propagation model, and it has been shown in [START_REF] Yassine | mpNet: variable depth unfolded neural network for massive MIMO channel estimation[END_REF] that a small uncertainty on system parameters could lead to high estimation performance losses. Contributions and related work. In [START_REF] Yassine | mpNet: variable depth unfolded neural network for massive MIMO channel estimation[END_REF], the Deep Unfolding approach was used to solve this performance loss issue, with the unfolded network mpNet, allowing to learn the physical imperfections of the system so as to enhance the estimation performance. However, this approach yields a high number of parameters to learn, leading to both a high sample complexity and a high time complexity. In this paper, mpNet is adapted to constrained dictionaries, which allows to drastically reduce sample complexity. Moreover, hierarchical search over dictionaries is introduced in order to reduce time complexity. Furthermore, the proposed method is illustrated on a Single Input Single Output Orthogonal Frequency Division Multiplexing (SISO-OFDM) system here instead of a Multi-User Multiple Input Multiple Output (MU-MIMO) system as in [START_REF] Yassine | mpNet: variable depth unfolded neural network for massive MIMO channel estimation[END_REF]. However, note that the contributions apply equally to both types of systems.

The rest of the paper is organized as follows, Section II presents the SISO-OFDM channel estimation problem, the used physical wave propagation model, and the sparse recovery approach. Section III presents the unfolded neural network and the two contributions of this paper: the sample complexity reduction strategy, and the time complexity reduction strategy. Section IV presents simulation results. Finally, Section V concludes the paper and gives perspectives.

II. PROBLEM FORMULATION

A. System model

In this paper, a SISO-OFDM scenario with N subcarriers in the uplink is considered. Let g ∈ C N denote the antenna gain vector representing the Base Station (BS) antenna gain at each subcarrier frequency, and f ∈ R N denote a frequency vector containing the different subcarrier frequencies. Finally, a multipath channel with L p propagation paths is considered.

Let x ∈ C N be an LS channel estimate of the channel vector h ∈ C N . This estimate is noisy as it possesses a residual estimation error:

x = h + n, (1)
where n ∼ CN 0, σ 2 I N . Its Signal to Noise Ratio (SNR) can be computed as:

SNR in = h 2 2 N σ 2 . ( 2
)
The goal of this paper is to denoise this LS channel estimate using sparse recovery techniques and a physical model.

B. Physical model

For a given subcarrier f k , the channel coefficient can be written as:

h k = Lp l=1 α l g k e -j2πf k τ l , (3)
where α l and τ l respectively represent the complex attenuation coefficient and the propagation delay for the l th path. Under this model, the channel vector h ∈ C N can be expressed as:

h = Lp l=1 α l    g 1 e -j2πf1τ l . . . g N e -j2πf N τ l    = Lp l=1 α l ψ (τ l ) , (4)
where ψ (τ l ) is the frequency response vector (FRV) for the l th path. We can see that the channel vector can be defined as a linear combination of FRVs. The linear combination is said to be sparse when L p is small.

C. Sparse recovery approach

As the channel can be written as a linear combination of FRVs, it is possible to construct a fixed matrix Ψ C N ×A with A FRV columns, which amounts to the discretization of the delays, and a projection vector u ∈ C A such that the channel could be estimated as: ĥ = Ψu.

(

For the rest of this paper, the FRV matrix Ψ will be called dictionary and its columns will be called atoms, i.e. each atom will represent a FRV corresponding to a specific delay.

As the channel vector can be seen as a linear combination of a few FRVs, the channel vector is said to be sparse in a dictionary of FRVs. For a fixed dictionary Ψ, the sparse recovery optimization problem is:

min u h -Ψu 2 2 s.t. u 0 ≤ A (6)
The previous optimization problem makes sense only if the dictionary is correct, i.e. a sparse linear combination of dictionary columns can represent a channel vector. If this is not the case, the channel estimate won't be trustworthy. It is possible to find the optimal dictionary as:

Ψ = arg min Ψ E h min u, u 0 ≤A h -Ψu 2 2 . (7)
Solving Eq. ( 6) for a fixed FRV dictionary is possible through sparse recovery algorithm such as the MP algorithm [START_REF] Mallat | Matching pursuits with time-frequency dictionaries[END_REF]: this is the approach followed in this paper, as in [START_REF] Yassine | mpNet: variable depth unfolded neural network for massive MIMO channel estimation[END_REF]. The goal of this algorithm is to find the most correlated FRVs, i.e. atoms, of the dictionary with the noisy channel estimate and subtract their projections. After L p iterations of the algorithm, in a perfect scenario, as all the corresponding FRVs will have been subtracted to the residual, the residual will only be composed of noise.

Algorithm 1 MP algorithm for channel denoising

Input: Dictionary Ψ, Noisy LS estimate x, Tolerance level 1: Initialize the residual: r ← x 2: while r

2 2 > do 3:
Find the most correlated atom:

i ← arg max i ψ H i r 4:
Update the residual: r ← rψ i ψ H i r 5: end while Output: ĥ ← xr (Denoised LS estimate)

D. Hardware impairments

In reality, the FRVs are not exactly known as there exists a lot of hardware imperfections related to frequency generation/acquisition. More specifically, Carrier Frequency Offset (CFO) and Sampling Clock Offset (SCO) can offset the subcarrier frequencies. Let fi be the nominal i th subcarrier frequency, i.e. the non-offseted subcarrier frequency, and f i be the real i th subcarrier frequency, i.e. the potentially offseted subcarrier frequency. For the CFO, the frequency offset δf is common to all subcarriers:

∀i ∈ - N 2 , N 2
, f i = fi + δf. (8)
For the SCO, it has been shown in [START_REF] Kim | A new joint algorithm of symbol timing recovery and sampling clock adjustment for OFDM systems[END_REF], [START_REF] Speth | Optimum receiver design for wireless broad-band systems using OFDM. I[END_REF] that the frequency offset is dependent on the subcarrier index, on the oscillator part per million (ppm) value ξ, and on the subcarrier spacing ∆f :

∀i ∈ - N 2 , N 2
, f i = fi + iδf = fi + iξ∆f. (9)
Moreover, we consider an antenna gain imperfection. Let gi be the nominal antenna gain, and g i be the real antenna gain for the i th subcarrier. We obtain:

∀i ∈ - N 2 , N 2
, g i = gi + n gi , (10)
with n gi ∼ N 0, σ 2 g . For the rest of this paper, we will only consider SCO and antenna gain imperfections. We can then define the notions of nominal and real dictionaries. The nominal dictionary Ψ will represent the dictionary constructed from the nominal knowledge of the system parameters, which is unaware of impairments. On the other hand, the real dictionary will represent the dictionary constructed from the perfect knowledge of the system parameters, i.e. with full knowledge of the SCO and antenna gain imperfections. The proposed method consists in initializing a neural network using the nominal dictionary, and approaching the performance one would get using the real dictionary via learning.

III. PROPOSED APPROACH A. mpNet architecture

Using the same approach as in [START_REF] Yassine | mpNet: variable depth unfolded neural network for massive MIMO channel estimation[END_REF], we propose to use the unfolded neural network mpNet to achieve SISO-OFDM channel estimation while learning the physical imperfections. The network is the unfolded version of the MP iterative algorithm and is presented in Algorithm 2.

Algorithm 2 Forward pass of mpNet [START_REF] Yassine | mpNet: variable depth unfolded neural network for massive MIMO channel estimation[END_REF] Input:

Weight matrix W ∈ C N ×A , Noisy LS estimate x ∈ C N , Noise variance σ 2 , Number of subcarriers N 1: r ← x 2: ← σ 2 N x 2 2 3: while r 2 2 > do 4: r ← r -WHT 1 W H r 5: end while Output: ĥ ← x -r (Denoised LS estimate)
HT 1 is a non-linear hard-thresholding operator which keeps only its input of greatest modulus and sets all the others to zero. The weight matrix W is initialized with the nominal dictionary Ψ. This thoughtful initialization allows to reduce the cost function convergence time in comparison to a random initialization. The goal is to learn the optimal dictionary through gradient descent in the unfolded network. In brief, this network has two goals:

• The forward pass of mpNet performs the channel estimation/denoising operation as the architecture of mpNet is the unfolded MP algorithm. Each layer will estimate one path of the channel. • The backward pass of mpNet performs the dictionary learning. As the weight matrix of mpNet is initialized with the nominal dictionary, the goal of the backward pass is to update the weight matrix so that it tends towards the real dictionary. Moreover, the value in Algorithm 2 corresponds to a stopping criterion called SC 2 in [START_REF] Yassine | mpNet: variable depth unfolded neural network for massive MIMO channel estimation[END_REF]:

SC 2 : r 2 2 ≤ σ 2 x 2 2 N. ( 11
)
This stopping criterion allows the network to have an adaptive number of layers for given noise characteristics: in other words, SNR adaptability. However, it imposes the knowledge of the noise variance σ 2 at the BS side.

B. Reducing sample complexity: constrained dictionary

As we explained above, the learning parameters are the components of the weight matrix W ∈ C N ×A . As those components are complex, each entry of W possesses both a magnitude and a phase: as a result there are 2N A learning parameters. In the experimental setup that will be presented in Section IV, we will consider N = 256 subcarriers, and A = 990 atoms. In that setup, there are 2N A = 506, 880 learning parameters. The first important contribution of this paper is to reduce this number by using a constrained dictionary.

We know that the proposed SISO-OFDM system only considered imperfections that impacted the gains and frequencies of the dictionary. Moreover, gain and frequencies are expected to be independent of the propagation delays, meaning that they will be common for each atom of the dictionary. We can then propose the following definition for the constrained dictionary Ψ ∈ C N ×A :

Ψ =     g 1 e -j2π(f1-N 2 δf )τ1 • • • g 1 e -j2π(f1-N 2 δf )τA . . . . . . . . . g N e -j2π(fN + N 2 δf )τ1 • • • g N e -j2π(fN + N 2 δf )τA     (12)
Each column of the dictionary still represents an FRV, however each entry of this constrained matrix is no more learnable: the only learnable parameters are the complex antenna gains g and the SCO frequency offset δf . From 2N A parameters, we only have 2N + 1 learning parameters left. This is interesting as the number of learning parameters is now independent of the number of atoms. If we take the previous numerical example, we go from 2N A = 506, 880 to only 2N + 1 = 513 learning parameters. One of the other benefits of this constrained dictionary approach is its sample complexity, i.e. the number of required samples to achieve convergence of the network's cost function. Indeed, for the classical mpNet architecture, as each component of the weight matrix was independent, only the atoms selected in the forward pass were updated during backpropagation. For the proposed approach, as the frequency offset and gains are common over all atoms, the selection and update of one atom will result in the update of all other atoms. Consequently, the cost function convergence will be quicker with this constrained dictionary approach than with the classical mpNet architecture, as shown in the experimental part of this paper.

C. Reducing time complexity: hierarchical search

A quick complexity analysis allows us to state that the time complexity of the classical mpNet approach is O (DN A) where D represents the number of layers of the mpNet network. If we take the previously considered scenario with D = 10 layers, we obtain at least DN A = 2, 534, 400 arithmetic operations for the estimation of one SISO-OFDM channel. In order to reduce this time complexity, we propose a new unfolded network architecture based on hierarchical atom search.

The principle of the hierarchical atom search approach is presented in Fig. 1. The classical approach consists in finding the most correlated atom in a dictionary of A different atoms (represented as circles in Fig. 1): A different correlations are carried out. Our hierarchical approach consists in iteratively finding the most correlated atom in the dictionary. As in the SISO-OFDM scenario the atoms are Fig. 1: Hierarchical atom search parameterized with a propagation delay, the dictionary covers an interval in the delay domain. In the first step, we propose to construct two meta-atoms (represented as squares in Fig. 1) whose correlation responses separately cover the dictionaryassociated delay interval. We carry out the correlation with the two meta-atoms and choose the most correlated one. We then create two new meta-atoms that cover the delay interval associated with the most correlated meta-atom of the previous step. This process is repeated until the log 2 (A) th step. In the delay interval covered by the most correlated atom chosen in the log 2 (A) -1 th step, there are only 2 atoms from the original dictionary: we compute their correlations and then find the most correlated atom of the dictionary. In other words, rather than finding the most correlated atom in 1 step but with A correlations, we find the most correlated atom in log 2 (A) steps but with only 2 log 2 (A) correlations. The challenge of this approach is to propose a meta-atom structure that allows its correlation response to cover a specific delay interval. We can prove that using a sinc modulated FRV as a meta-atom allows this.

A Fourier Transform FT from the frequency domain to the delay domain is defined as:

x (τ ) = FT [x (f )] = R x (f ) e -j2πf τ df. ( 13
)
The correlation of a pure FRV of delay τ , e (f, τ ), and a generic meta-atom ψ i (f ) is considered. The bandwidth, central frequency, and subcarrier spacing of the system will respectively be denoted as γ, f 0 , and ∆f . The correlation response can be computed as:

χ ψi (τ ) = e (f, τ ) , ψ i (f ) (14) = R ψ * i (f ) g (f ) e -j2πf τ Π γ (f -f 0 ) X ∆f (f ) df. ( 15
)
The windowing Π γ (ff 0 ) allows to represent the bandlimited nature of the FRV and meta-atom, while the Dirac comb X ∆f (f ) allows the sampling at the subcarrier frequencies. We make the assumption that the antenna gains are quasiconstant over the bandwidth so that g (f ) = αΠ γ (ff 0 ). In order to simplify the following equations, we will deliberately omit the constant α. We then obtain:

χ ψi (τ ) = FT [ψ * i (f ) Π γ (f -f 0 ) X ∆f (f )] . ( 16
)
One can observe in Eq. ( 16) that the correlation response can be computed as a Fourier Transform. As we want it to be a constant over a certain delay interval (a rect function), it is then easy to see that using sinc modulated FRVs allows to fulfill that requirement. More specifically, we define the meta-atom ψ i (f ) as:

ψ i (f ) = sinc ( f ) e -j2πf τi . ( 17
)
The correlation response then becomes:

χ ψi (τ ) = FT sinc ( f ) e j2πf τi Π γ (f -f 0 ) X ∆f (f ) = 1 Π (τ -τ i ) γ sinc (γτ ) e -j2πf0τ 1 ∆f X 1 ∆f (f ). (18)
One can see in Eq. ( 18) that the proposed meta-atom expression allows to obtain a rectangular waveform in the delay domain, allowing the rect width control and τ i the rect central position control. This can be seen in Fig. 2 where we vary the values of and τ i . For two meta-atoms, the time complexity of the proposed hierarchical search can be evaluated as O (2 log 2 (A)). If we consider the partition of A > 1 atoms into n ∈ N, n > 1 intervals, the time complexity of the associated hierarchical search is O (n log n (A)). Minimizing the time complexity of this hierarchical approach is then equivalent to solving Eq. ( 19):

n = arg min n∈N, n>1 n log n (A) . (19)
It can be easily shown that solving Eq. ( 19) gives us n = 3.

A quick complexity analysis of all the unfolded networks presented so far is presented in Table I. We compare the classical mpNet as it was proposed in [START_REF] Yassine | mpNet: variable depth unfolded neural network for massive MIMO channel estimation[END_REF], mpNet with a constrained dictionary (C. mpNet), and mpNet with a constrained dictionary and hierarchical atom search with 3 meta-atoms (H.C.3 mpNet). As we stated earlier, the constrained dictionary approach allows to reduce the sample complexity and the hierarchical search approach was developed to reduce the time complexity. It is then interesting to merge the constrained and hierarchical search approach, as it allows to reduce both the sample and time complexities. For D = 10 layers, N = 256 subcarriers and A = 990 atoms, the time complexity of the forward pass goes from 2, 534, 400 arithmetic operations for the classical mpNet to around only 48, 220 arithmetic operations for the H.C.3 mpNet, which is a fifty-fold reduction. We propose to validate our contributions using realistic channel data, namely the "O1" outdoor DeepMIMO dataset [START_REF] Alkhateeb | DeepMIMO: A generic deep learning dataset for millimeter wave and massive MIMO applications[END_REF]. We consider a central frequency of 3.4GHz, and a bandwidth of 50MHz. Furthermore, we generate the channels with N = 256 subcarriers. The dictionary is composed of A = 990 atoms. We consider up to L p = 10 propagation paths. Regarding the physical imperfections, the oscillator ppm value for the SCO is ξ = 40ppm, and we consider two gain noise variance scenarios: σ 2 g = 0.36 (very high gain noise) and σ 2 g = 0.09 (high gain noise). We consider two SNR scenarios: SNR in = 10dB and SNR in = 5dB. In order to compute the stopping criterion for the network, we assume that the noise variance is known at the BS side.

We consider the same minibatch online learning strategy as in [START_REF] Yassine | mpNet: variable depth unfolded neural network for massive MIMO channel estimation[END_REF]. The network will see batches of 10 channels, and the estimation performance will be evaluated on 2000 test channels. More specifically, regarding the DeepMIMO parameters, we consider the BS represented with a red triangle in Fig. 3, and User Equipments (UEs) randomly generated in the blue zone. We will use the Adam optimizer [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] for the learning parameter update. The evaluation metric will be the Normalized Mean Squared Error (NMSE), defined as E ĥh 2 2 / h 2 2 .

Fig. 3: DeepMIMO channel generation configuration

We propose to evaluate the performance of the classical network (mpNet), the constrained dictionary mpNet (C. mpNet), the hierarchical search with 2 meta-atoms and constrained dictionary mpNet (H.C.2 mpNet) and the one with 3 meta-atoms (H.C.3 mpNet). We will compare those network performances against the LS estimator, the MP algorithm with nominal and real dictionaries, and the MMSE estimator with a substituted channel covariance matrix using the Low-Rank Approximation (LRA) presented in [START_REF] Savaux | LMMSE channel estimation in OFDM context: a review[END_REF]. We use the substituted covariance matrix, as, in reality, estimating the covariance matrix for each UE is too complex as it requires tracking each UE channel during several frames.

For all noise and hardware scenarios, it is possible to remark in Fig. 4 that dictionary learning is achieved as there is convergence of the NMSE performances. One can remark that at the end of the training, the proposed networks (C. mpNet, H.C.2 and H.C.3 mpNet) always outperform the LS and LRA-MMSE approaches.

One can see that, as exposed in Section III-B, the convergence of the constrained versions of mpNet (C. mpNet and H.C. mpNet) is quicker than the convergence of the classical mpNet. For all scenarios, only approximately 400 channels are needed to achieve convergence. Moreover, we can see that, after convergence, the estimation performances of the constrained networks are better than the one of the classical mpNet. This can be explained by the bias-variance decomposition of the estimation NMSE. In fact, the C./H.C. mpNet can be seen as an estimator with fewer parameters than the classical mpNet, so its variance will be lower than the classical mpNet one. As the dictionary structure is chosen wisely, the C./H.C. mpNet has the same bias as the classical mpNet. As a result, the estimation NMSE is lower for both the C. and H.C. mpNet architectures than for the classical one.

One can also remark in Fig. 4c that, if the hardware imperfections are too important, the model-based MP algorithm does not perform well. In that particular case, using the MP approach with nominal dictionary is worse than using LS.

It is noticeable that H.C.2 mpNet offer slightly worse performance than the C. mpNet. This can be explained by the hierarchical search approach: in the classical approach, the algorithm finds the most correlated atom of a dictionary with a residual. For the hierarchical approach, the algorithm will select the delay interval that has the most energy. As a result, for a fixed noisy LS estimate, the two approaches may not select the same atoms, leading to different channel estimation performance. It is then interesting to study the impact of the number of meta-atoms, as increasing the number of windows in the delay domain can improve the estimation performance for the hierarchical approach. This can be seen with the NMSE performance of H.C.3 mpNet: this network offers slightly better performance than the H.C.2 mpNet, while presenting a lower time complexity as shown in Table I.

It has been shown in Section III-C that the hierarchical approach with 3 meta-atoms was optimal in terms of time complexity. This can be seen in Table II where an execution time comparison of the MP algorithm to its hierarchical versions with 2 and 3 meta-atoms (MP H.2 and MP H.3) is proposed. One can see that the MP H.3 outperforms both the MP H.2 and classical MP algorithm: its mean execution time is up to a hundred time quicker than the classical MP.

V. CONCLUSION

In this paper, the unfolded neural network mpNet [START_REF] Yassine | mpNet: variable depth unfolded neural network for massive MIMO channel estimation[END_REF] was enhanced in two ways. Firstly, constrained dictionaries were The performance of the resulting network was assessed using realistic channel data with hardware impairments: it showed that our network outperforms classical approaches such as the LS estimator or the MMSE estimator with substituted covariance matrix, but also the classical mpNet network. This combined approach is really promising as it allows to enhance the estimation performance while reducing the overall complexity: this follows the efficiency philosophy of model-based deep learning [START_REF] Shlezinger | Model-based deep learning[END_REF]. Future work could for example consider the adaptation of the proposed techniques to MU-MIMO-OFDM scenarios.

Fig. 2 :

 2 Fig. 2: Influence of and τ i on the correlation waveform

Fig. 4 :

 4 Fig. 4: Channel estimation performance for various SNRs and model imperfections

TABLE I :

 I Unfolded network complexity analysis IV. EXPERIMENTAL RESULTS

TABLE II :

 II Average execution time for 10, 000 random UEs introduced to allow sample complexity reduction. Secondly, hierarchical atom search has been presented to reduce time complexity.