Abdul Karim Gizzini
email: abdulkarim.gizzini@ensea.fr

Marwa Chafii
email: marwa.chafii@nyu.edu

Low Complex Methods for Robust Channel Estimation in Doubly Dispersive Environments

Keywords: Channel estimation, vehicular communications, DFT interpolation

Wireless communications play a significant role in facilitating several mobile applications like unmanned aerial vehicles, high-speed railway, and vehicular communications. Particularly, the concept of connected vehicles brings a new level of connectivity to vehicles. Along with novel on-board computing and sensing technologies, vehicular networks serve as a key enabler of intelligent transportation systems and smart cities. However, in such environments, the propagation medium between the network nodes is highly time-varying leading to considerable reliability challenges. Ensuring communication reliability by the means of accurate channel estimation in such environments is very important. Initially, vehicular communications standards apply the basic least square (LS) estimation that is not enough for the dynamic vehicular environment. Moreover, the frame structure has low pilot density, making channel tracking a difficult task to achieve, especially in high mobility scenarios. Conventional estimators either employ data subcarriers besides pilots in the estimation process, or the estimated channel and noise statistics. Therefore they suffer from significant performance degradation due to high error probability resulting from hard symbol demapping and the sensitivity against the change in the employed channel statistics. The motivation behind this paper is to overcome this challenge by proposing a low complex and robust channel estimation scheme based on truncated discrete Fourier transform (T-DFT) that updates the channel estimates using DFT interpolation without the need for data subcarriers decisions and the estimated channel statistics. Moreover, further performance improvement can be achieved by considering temporal averaging on top of T-DFT estimation. Analytical and simulation results carried out using different vehicular channel models reveal the performance superiority of the proposed schemes compared to conventional estimators while recording a significant decrease in computational complexity and execution time.

I. INTRODUCTION

V EHICULAR communications [1] have been introduced to facilitate several future smart city applications such as safety, infotainment, roadway information dissemination, and autonomous driving. By staying connected, vehicles can more efficiently communicate with each other, therefore mitigating traffic accidents that are considered one of the leading causes of death all over the world [START_REF] Rolison | What are the Factors that Contribute to Road Accidents? An Assessment of Law Enforcement Views, Ordinary Drivers' Opinions, and Road Accident Records[END_REF]. Two vehicular communications standards have been proposed: (i) WiFi-based where IEEE 802.11p initially proposed to manage vehicular communications [START_REF] Qu | Intelligent Transportation Spaces: Vehicles, Traffic, Communications, and Beyond[END_REF], [START_REF] Yang | Inter-vehicle Cooperation Channel Estimation for IEEE 802.11p V2I Communications[END_REF]. (ii) Cellular-based where LTE and 5G networks are employed in vehicular communications [START_REF] Yang | Markov Decision-Based Pilot Optimization for 5G V2X Vehicular Communications[END_REF].

In this work we focus on the IEEE 802.11p WiFi-based standard that have been proposed to meet vehicular communications needs, especially communication reliability that represents the most important feature in managing real-time applications. However, we note that the proposed work can be generalized to any other standard that manages wireless communications in doubly-dispersive channels.

Both vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communications suffer from a harsh signal propagation environment mainly due to the following two reasons: (i) One or both communications nodes i.e. the transmitter and the receiver are in motion. As a result, the vehicular channel VOLUME 4, 2016 variation raises as the vehicle velocity increases, leading to a short channel coherence time. (ii) There are fixed and mobile scatterers that introduce significant channel multipath components. Therefore, the vehicular channel becomes doubly selective, i.e. in time and frequency and its estimation is then challenging. IEEE 802.11p standard allocates two full preamble symbols at the beginning of each frame that are used for channel estimation at the receiver using the basic least square (LS) estimator [START_REF] Abdelgader | The Physical Layer of the IEEE 802.11 p WAVE Communication Standard: The Specifications and Challenges[END_REF]. Moreover, the channel is estimated once for each frame, and the estimated channel is used to equalize the whole frame. Due to the time-varying nature of the vehicular channel, the basic estimated channel can quickly become outdated, resulting in overall poor system performance. Therefore, to track the channel, four pilots are multiplexed with the data subcarriers in each transmitted symbol.

Conventional channel estimators that have been proposed for the IEEE 802.11p standard assume that the allocated pilot subcarriers are not sufficient for accurately tracking the vehicular channel, since they are not spaced closely enough to capture the variation of the channel in the frequency domain. Therefore, IEEE 802.11p conventional estimators are mainly based on the demapped data subcarriers, besides pilot subcarriers to update the channel estimate for each received symbol. This procedure is referred to as data-pilot aided (DPA) channel estimation. In order to improve the basic channel estimation performance, the spectral temporal averaging (STA) estimator [START_REF] Fernandez | Performance of the 802.11p Physical Layer in Vehicleto-Vehicle Environments[END_REF] applies averaging in both the time and the frequency domains as post-processing operations on top of DPA estimation. STA estimator outperforms other conventional estimators in low signal-to-noise ratio (SNR) region, while it suffers from significant performance degradation in high SNR region especially in high mobility vehicular scenarios. Constructed data pilots (CDP) estimator [START_REF] Zhao | Channel Estimation Schemes for IEEE 802.11p Standard[END_REF] assumes a high correlation between each two successive received symbols, thus the final estimated channels are updated over the received frame according to this assumption. CDP estimator outperforms STA estimator especially in high SNR region but still cannot perform well in high mobility scenarios when high modulation orders are employed. Improved CDP (iCDP) [START_REF] Wang | An Improved Channel Estimation Technique for IEEE 802.11p Standard in Vehicular Communications[END_REF] estimator combines both STA and CDP estimators, thus the overall performance in the whole SNR region is improved. In [START_REF] Kim | Time and Frequency Domain Channel Estimation Scheme for IEEE 802.11p[END_REF], the authors proposed the time domain reliable test frequency domain interpolation (TRFI) estimator that utilizes frequency domain interpolation in order to also improve the CDP estimator. Inspired by the conventional TRFI estimator, the authors in [START_REF] Han | Virtual Subcarrier Aided Channel Estimation Schemes for Tracking Rapid Time Variant Channels in IEEE 802.11p Systems[END_REF] proposed an enhanced TRFI E-TRFI estimator, where the employed interpolation utilizes all the subcarriers within the received symbol to improve the interpolation accuracy. After that, a noise attenuation step is employed leading to improved overall performance. E-TRFI outperforms STA, CDP, and TRFI estimators especially in the high SNR region, but similarly to the other conventional estimators, it suffers from considerable performance degradation in high mobility vehicular scenarios. Another conventional approach is to employ the linear minimum mean square error (LMMSE) estimator [START_REF] Choi | Low-Complexity 2D LMMSE Channel Estimation for OFDM Systems[END_REF] where the estimated channel and noise statistics are utilized in the channel estimation. The LMMSE estimator does not depend on the DPA estimation, therefore, it outperforms the conventional DPA-based estimators. However, LMMSE suffers from significant performance degradation when there is a mismatch between the estimated and real channel and noise statistics represented by the channel correlation matrices and the noise power. Therefore, making it impractical in such scenarios.

The performance degradation of the conventional estimators is mainly related to two reasons: (i) Conventional estimators are based initially on the basic LS channel estimation applied at the received preamble symbols. This basic estimation utilizes only the predefined preamble sequence in the frequency domain, without taking into consideration the LS estimation at the channel delay taps. Thus, it ignores the relationship between the channel taps, and the presence of noise in the estimation process. Therefore, basic LS estimation is noisy and unreliable to be considered as a starting point of the conventional estimators. (ii) Conventional estimators employ the DPA estimation, which is based on demapping the received data subcarriers and using them as pilots. This mechanism is also unreliable since the demapping error is enlarged from one symbol to another, hence leading to an additional error in the estimation process.

Therefore, in order to overcome the drawbacks of the conventional estimators, in this paper, we propose an estimation method that depends mainly on employing the tracking pilots without considering the basic LS estimation at the preamble, the DPA estimation, and the estimated channel and noise statistics. As a result, the data subcarriers demapping step is not required and the demapping error is completely eliminated, resulting in better estimation accuracy.

Based on the above context, in this paper, we propose a robust, low complex channel estimation scheme for IEEE 802.11p standard that is based on truncated discrete Fourier transform (T-DFT) interpolation, where the classical DFT interpolation is adapted to the IEEE 802.11p standard structure by employing the pilot subcarriers within each symbol to estimate the dominant vehicular channel taps. Moreover, we show that updating the estimated channels for the received symbols using time-averaged T-DFT leads to considerable noise alleviation throughout the frame, resulting in reducing the bit error rate (BER) and normalized mean-squared error (NMSE) performance. The contributions in this paper can be listed as follows only the tracking pilots without the DPA estimation step, thus, the enlarged DPA de-mapping error is totally eliminated. Moreover, they do not depend on the preestimated channel correlation matrices and SNR estimation. Therefore, achieving a considerable robustness superiority compared to conventional LMMSE estimator in case of mismatch between the pre-estimated and the real channel correlation matrices and SNR estimation. • A detailed computational complexity and execution time analysis is provided for the studied channel estimators, where we show that the proposed T-DFT-based schemes outperform conventional estimators with less computational complexity and execution time. The remainder of this paper is organized as follows: in Section II, the IEEE 802.11p standard and the system model are described. Section III provides a detailed description of the conventional channel estimations schemes. The proposed T-DFT and TA-TDFT schemes, as well as their analytical NMSE derivations, are described in Section IV. In Section V, simulation results are presented for different vehicular channel models conditions employing different modulation orders, where the performance of the proposed schemes is evaluated in terms of BER and NMSE. Detailed computational complexity and execution time analysis are provided in Section VI. Finally, the paper is concluded in Section VII.

Notations: Throughout the paper, vectors are defined with lowercase bold symbols x whose k-th element is x[k]. Time and frequency domain vectors are represented by x and x respectively. Matrices are written as uppercase bold symbols X. E [.] is the expectation operator. The trace of a square matrix X is trace {X}. The notation ⊙ and ⊘ denote the element-wise multiplication and division operations, respectively. Finally. the pseudo inverse and conjugate matrices of X are denoted by X † and X H respectively.

II. IEEE 802.11P SYSTEM MODEL

IEEE 802.11p is an approved upgrade of the IEEE 802.11a standard that adds wireless access in vehicular environments. This upgrade includes data exchange between high-speed vehicles (V2V) and between the vehicles and the roadside infrastructure (V2I) in the licensed intelligent transportation systems band [START_REF] Weidong | Wireless Access in Vehicular Environments[END_REF]. IEEE 802.11p supports sending data at different data rates employing different modulation orders, as described in Table 1. Moreover, it employs orthogonal frequency-division multiplexing (OFDM) transmission scheme with K = 64 total subcarriers. K on = 52 active subcarriers are used, and they are divided into K d = 48 data subcarriers and K p = 4 pilot subcarriers. The remaining K n = 12 subcarriers are used as a guard band. Compared to the IEEE 802.11a standard, the channel bandwidth is halved, resulting in a 10 MHz bandwidth instead of 20 MHz in 802.11a. Also, the carrier spacing is reduced by half. Moreover, all OFDM timing parameters used in the regular 802.11a are doubled. This enhances the system reliability required by vehicular communications applications since a larger guard interval reduces the inter-symbol interference caused by multi-path propagation. Table 2 shows the IEEE 802.11p physical layer specifications. A detailed discussion of the IEEE 802.p and its features are presented in [START_REF] Abdelgader | The Physical Layer of the IEEE 802.11 p WAVE Communication Standard: The Specifications and Challenges[END_REF].

A. IEEE 802.11P FRAME STRUCTURE AND SIGNAL MODEL

An IEEE 802.11p frame consists mainly of three parts: (i) preamble, (ii) signal field, and (iii) OFDM data symbols. The preamble includes ten short training symbols (STS) t 1 to t 10 , each of duration 1.6 µs. The STS are used at the receiver for signal detection, diversity selection, coarse frequency offset estimation, and timing synchronization. The following two 6.4 µs long training symbols (LTS) are prepended with a cyclic prefix (CP) of duration 3.2 µs and used for channel estimation at the receiver. After that, the signal field is used to specify the rate and length information that is required for decoding the received OFDM data symbols. It consists of one CP-OFDM symbol that carries 24 bits divided into four fields as follows

• Rate: the first 4 bits convey information about the employed modulation and coding rate. • Length: 12 bits integer (6 to 17) that indicate the number of data octets requested in the transmission. • Reserved: bits 5 and 18 that are reserved for future use.

• Tail: the last 6 bits that are set to zeros and used to synchronize the descrambler at the receiver, and to return the convolutional encoder to the zero state.

Finally, the OFDM data symbols that carry the actually transmitted data bits are inserted. Figure 1 illustrates the IEEE 802.11p frame structure in the time domain. In this paper, we assume perfect synchronization at the receiver, and we ignore the signal field for simplicity. Therefore, we focus on a frame that consists of two LTS at the beginning followed by I OFDM data symbols. The i-th transmitted frequency- domain OFDM symbol xi [k], is partitioned as

xi [k] =    xdi [k], k ∈ K d . xp i [k], k ∈ K p . 0, k ∈ K n , (1)
where

0 ≤ k ≤ K -1.
x i [n] = 1 √ K K-1 k=0 xi [k]e j2π nk K . (2)

B. RECEIVED SIGNAL AND CHANNEL MODEL

After passing through the doubly-selective vehicular channel, the received OFDM symbol y i [n] can be expressed as

y i [n] = L-1 l=0 h i [l, n]x i [n -l] + v i [n] = 1 √ K K-1 k=0 hi [k, n] xi [k]e j2π nk K + v i [n], (3)
where h i [l, n] denotes the delay-time response of the discrete linear time-variant (LTV) channel of L taps at the i-th OFDM symbol, whereas hi [k, n] = L-1 l=0 h i [l, n]e -j2π lk K is the frequency-time response. Moreover, v i denotes the additive white Gaussian noise (AWGN) of variance σ 2 . The i-th received frequency-domain OFDM symbol is obtained from (3) by means of discrete Fourier transform (DFT), and thus

ỹi [k] = 1 K K-1 q=0 xi [q] K-1 n=0 hi [q, n]e -j2π n(k-q) K + ṽi [k]. (4)
Note that hi [q, n] is time-variant at the scale of the OFDM symbol duration and within the symbol itself. Accordingly

hi [q, n] = L-1 l=0 e -j2π lq K ν=ν d ν=-ν d h(l, ν)e j2πνni e j2πνn dν, (5)
where h(l, ν) = n h[l, n]e -j2πnν is the channel delay-Doppler response, ν denotes the normalized Doppler frequency,

n i = i(K + K cp ) + K cp . And ν d = f d Fs is the maximum Doppler frequency. Let hi [l, v] = 1 K K-1 q=0 K-1 n=0 hi [q, n]e -j2π nv K e j2π ql K = ν=ν d ν=-ν d h(l, ν)e j2πνni K-1 n=0 e -j2π(ν-v K )n dν, (6)
be the discrete delay-Doppler response at the i-th OFDM symbol. For simplicity, we assume h(l, ν) to be uncorrelated in both domains, such that

E h(l, ν) h * (l ′ , ν ′ ) = S h (l, ν)δ[l-l ′ ]δ(ν -ν ′ )
, where S h (l, ν) is the delay-Doppler spectrum [START_REF] Matz | Chapter 1 -Fundamentals of Time-Varying Communication Channels[END_REF], then using (6), we have

E hi [l, v] h * i [l, v ′ ] = ν=ν d ν=-ν d S h (l, ν) K-1 n=0 K-1 n ′ =0 e -j2πν(n-n ′ ) e -j2π n ′ v ′ -nv K dν. (7)
This correlation is independent of the index i, and it can be approximated as

E hi [l, v] h * i [l, v ′ ] ≈ K 2 ρ[l, v]δ[v -v ′ ], ρ[l, v] = S h (l, v N ). (8)
The time selectivity of the channel depends on mobility. In very low mobility, where

f d ≈ 0, hi [q, n] = h[q]
is constant during the whole frame. For moderate to high mobility, the channel variation within the duration of one OFDM symbol is negligible, and therefore, hi [q, n] = hi [q]. At very high mobility, the channel becomes variant within a single OFDM symbol. In this case, hi [q, n] = hi [q] + εi [q, n], where

hi [q] = 1 K K-1 n=0 hi [q, n], and εi [q, n] = hi [q, n] -hi [q]. (9)
Replacing this in (4), we get the full equation of the signal model represented by

ỹi [k] = hi [k] xi [k] + ẽi,d [k] + ṽi [k], k ∈ K on . ( 10
)
The term ẽi,d [k] represents the Doppler interference given by

ẽi,d [k] = 1 K K-1 q=0 q̸ =k K-1 n=0 hi [q, n]e -j2π n(k-q) K xi [q] = 1 K q∈Kon q̸ =k L-1 l=0 hi [l, k -q]e -j2π lq K xi [q]. (11)
K p {±7, ±21} K n {0, ±27, ±28, ±29, ±30, ±31, -32} K d K on \K p ∪ K n

Subcarrier spacing 156.25 KHz

The Doppler interference destroys the orthogonality of the subcarriers within the received OFDM symbol, resulting in a significant degradation in the overall system performance [START_REF] Ricklin | Time Varying Channels : Characterization, Estimation, and Detection[END_REF]. Assuming the subcarriers are uncorrelated with power E q , i.e. E xi [q] x * i [q ′ ] = E q δ[q -q ′ ] and using ( 8) then

E ẽi,d [k]ẽ * i,d [k ′ ] = L-1 l=0 q∈Kon q̸ =k E q ρ[l, k -q]δ[k -k ′ ] = σ 2 d [k]δ[k -k ′ ]. (12)
Thus, the Doppler interference is assumed uncorrelated. However, the variance

σ 2 d [k] = E |ẽ i,d [k]| 2 depends on the subcarrier index. Noting that hi [k] = 1 K L-1 l=0 hi [l, 0]e -j2π kl K , (13)
then, the channel gain and Doppler interference are uncorrelated, i.e.

E hi [k]ẽ * i,d [k] = 0. Moreover, hi [k] can be estimated from L uncorrelated taps defined by hi [l, 0].

C. IEEE 802.11P VEHICULAR CHANNEL MODELS

As we have discussed, the wireless channel in vehicular environments is considered a time-varying channel including multi-path propagation and large Doppler shift [START_REF] Mecklenbrauker | Vehicular Channel Characterization and Its Implications for Wireless System Design and Performance[END_REF]. Various studies that analyze the statistical characteristics of the wireless channel in vehicular environments are presented in [START_REF] Wang | Vehicle-to-Vehicle Channel Modeling and Measurements: Recent Advances and Future Challenges[END_REF], [START_REF] Karedal | A Geometry-based Stochastic MIMO Model for Vehicle-to-Vehicle Communications[END_REF], and [START_REF] Viriyasitavat | Vehicular Communications: Survey and Challenges of Channel and Propagation Models[END_REF]. In this paper, we consider the tapped delay line (TDL) vehicular channel models proposed in [START_REF] Acosta-Marum | Six Time and Frequency Selective Empirical Channel Models for Vehicular Wireless LANs[END_REF].

These TDL models include six vehicular channel models for different vehicular environments. They are obtained by a measurement campaign that was implemented in metropolitan Atlanta. Table 3 provides the different characteristics of these vehicular channel models. Moreover, further investigations and discussion concerning the detailed channel models measurement setups are shown in [START_REF] Acosta-Marum | Measurement, Modeling, and OFDM Synchronization for the Wideband Mobile-to-Mobile Channel[END_REF].

III. CONVENTIONAL CHANNEL ESTIMATION SCHEMES

In this section, conventional channel estimators that adhere to the IEEE 802.11p standard structure are presented and discussed. These estimators assume that the allocated four pilots within each OFDM symbol are insufficient for accurately tracking the time variations of the vehicular channel. Therefore, they employ the data subcarriers in the channel estimation. DPA estimation is considered as an initial estimation, where the previously estimated channel is considered as a preamble to estimate the channel for the current received symbol. The STA estimation applies frequency and time averaging to the DPA estimated channel, while the E-TRFI estimation considers frequency domain interpolation to improve the DPA estimation.

A. DPA ESTIMATOR

The DPA estimator is based on employing the demapped data subcarriers of the previously received OFDM symbol to estimate the channel for the current OFDM symbol according to the following steps 1) LS estimation: that is implemented using the two LTS received preambles denoted as ỹ(p)

1 [k], and
ỹ(p) 2 [k]
, and the predefined preamble sequence p[k] such that

ĥLS [k] = ỹ(p) 1 [k] + ỹ(p) 2 [k] 2 p[k] . (14)
2) Equalization: the i-th received OFDM symbol is equalized by the previously DPA estimated channel, such that

ỹeq i [k] = ỹi [k] ĥDPAi-1 [k] , ĥDPA0 [k] = ĥLS [k]. (15)
3) Demapping:

ỹeq i [k] is demapped to the nearest con- stellation point to obtain di [k]. 4
) Final DPA estimation: DPA updates the final estimated channel for the i-th received OFDM symbol by

ĥDPAi [k] = ỹi [k] di [k] . ( 16
)
DPA scheme is considered as the initial estimation process utilized by most IEEE 802.11p conventional estimators. However, DPA estimation has two main limitations. First, it is based on the basic ĥLS estimation suffering from noise enhancement. Second, the demapping step in DPA results in a significant demapping error mainly in low SNR region, and this error is enlarged in high mobility vehicular scenarios employing high modulation orders. Moreover, since the DPA estimated channels are updated iteratively over the received frame, the demapping error propagates through the frame leading to significant performance degradation.

B. STA ESTIMATOR

The STA estimator [START_REF] Fernandez | Performance of the 802.11p Physical Layer in Vehicleto-Vehicle Environments[END_REF] has been proposed to further improve the DPA estimation by applying two additional steps on top of the DPA estimation. The first step is by performing frequency domain averaging to the DPA estimated channel including the current and the neighboring subcarriers as follows

ĥFDi [k] = λ=β λ=-β ω λ ĥDPAi [k + λ], ω λ = 1 2β + 1 , (17)
After that, the final STA channel estimate is updated using time averaging between the previously STA estimated channel and the frequency averaged channel in [START_REF] Wang | Vehicle-to-Vehicle Channel Modeling and Measurements: Recent Advances and Future Challenges[END_REF], such that

ĥSTAi [k] = (1 - 1 α ) ĥSTAi-1 [k] + 1 α ĥFDi [k]. (18)
STA estimator performs well in low SNR region. However, it suffers from a considerable error floor in high SNR region because of large DPA demapping error. It is worth mentioning that in order to improve the STA performance, the optimal values of the frequency and time averaging coefficients denoted by α and β should be estimated according to channel statistics so that α and β can be adapted to the channel model. Channel model statistics are hard to obtain in real case scenarios, therefore, α and β are considered as fixed values that are chosen experimentally to achieve the best acceptable performance.

C. E-TRFI ESTIMATOR

Recently, the authors in [START_REF] Han | Virtual Subcarrier Aided Channel Estimation Schemes for Tracking Rapid Time Variant Channels in IEEE 802.11p Systems[END_REF] proposed the E-TRFI estimator that is considered as an upgraded version of the conventional TRFI estimator [START_REF] Kim | Time and Frequency Domain Channel Estimation Scheme for IEEE 802.11p[END_REF]. The main E-TRFI upgrades are in the reliable and unreliable subcarriers selection algorithm, where the Euclidean distance between the demapped subcarriers is used as a reliability condition. Moreover, E-TRFI employs the estimated channels at the K n subcarriers in order to improve the cubic interpolation accuracy. The E-TRFI estimator proceeds as follows:

1) Enhanced LS estimation: The conventional LS estimation presented in [START_REF] Matz | Chapter 1 -Fundamentals of Time-Varying Communication Channels[END_REF] estimates the channel at K on subcarriers. However, the E-TRFI employs the estimated channel also at the remaining K n subcarriers that are interpolated as follows

ĥE-LS [k] = F 64 (F H 52 F 52 ) -1 F H 52 ĥLS [k], k ∈ K, (19)
where F 64 ∈ C K×L and F 52 ∈ C Kon×L denote the truncated DFT matrix obtained by selecting K, K on rows, and L columns from the K × K DFT matrix, respectively. Here, L represents the number of channel taps. 2) Equalization: The i-th received OFDM symbol is equalized by ĥE-TRFIi-1 [k], where

ỹ′ eq i [k] = ỹi[k] ĥE-TRFI i-1 [k] , k ∈ K d . (20)
Here, ĥE-TRFI0

[k] = ĥE-LS [k].
δ (m) i [k] = | ỹ′ eq i [k] -c (m) | 2 , m = 1, 2, . . . . , M. (21)
c (m) denotes the m-th constellation point with M standing for the employed modulation order. The obtained δ (m) i

[k] values are arranged in ascending order vector denoted as δ(m) i

[k], then the reliability ratio for each subcarrier R i [k] is calculated employing the first and second minimum distances as follows

Ri[k] = δ(1) i [k] δ(2) i [k] , k ∈ K d , (22)
where

0 < R i [k] < 1. Small R i [k] value indicates that the demapped subcarrier d′ i [k]
is close to actual transmitted modulated symbol. Therefore, the subcarrier is classified as a reliable subcarrier and inserted into the reliable subcarriers set RS i , otherwise, it is considered unreliable and inserted into the unreliable subcarriers set URS i . The extensive simulations performed in [START_REF] Han | Virtual Subcarrier Aided Channel Estimation Schemes for Tracking Rapid Time Variant Channels in IEEE 802.11p Systems[END_REF], show that R i [k] = 0.5 is the bestpredefined threshold for the reliability test. 4) Frequency domain cubic interpolation: After selecting the RS i and URS i sets, frequency-domain cubic interpolation [START_REF] Marsden | Cubic Spline Interpolation of Continuous Functions[END_REF] is applied by using the channel estimates in RS i to determine the channel estimates for the URS i , such that

ĥInt i [k] =        ỹi [k] / d′ i [k], k ∈ RSi. ỹi [k] /xp i [k], k ∈ Kp. ỹi [k] / ĥE-TRFI i-1 [k], k ∈ Kn. Cubic Interpolation, k ∈ URSi. (23)
5) Noise attenuation: The last step in the E-TRFI estimator is applying a noise attenuation as follows

ĥE-TRFI i [k] = Q ĥInt i [k], k ∈ K, (24)
where Q = F 64 F H 64 . We note that the computation of Q depends mainly on the L channel taps and it can be performed offline resulting in reducing the computational complexity.

The E-TRFI estimator outperforms other conventional estimators, however, it still suffers from a considerable performance degradation due to the enlarged demapping error in high mobility scenarios, and high computational complexity due to the matrix multiplication in [START_REF] Viriyasitavat | Vehicular Communications: Survey and Challenges of Channel and Propagation Models[END_REF] and [START_REF] Gizzini | Deep Learning Based Channel Estimation Schemes for IEEE 802.11p Standard[END_REF]. Moreover, the Euclidean distance reliability test threshold should be updated in a real-time manner in order to guarantee the best possible performance.

D. LMMSE ESTIMATOR

The LMMSE estimator [START_REF] Choi | Low-Complexity 2D LMMSE Channel Estimation for OFDM Systems[END_REF] aims to linearly minimize the mean squared error (MSE) error between the LMMSE estimated and real channel, given the LS estimated channel at the K p subcarriers defined as

ĥpi [k] = ỹpi[k] xpi [k] , k ∈ K p . (25)
Accordingly, the key element here is to find W LMMSEi where ĥLMMSEi = W LMMSEi ĥpi , so that ϵ LMMSE is minimized, such that

ϵ LMMSE = E ( ĥLMMSEi -hi ) 2 = E (W LMMSEi ĥpi -hi ) 2 . ( 26
)
The minimization of ϵ LMMSE results in the following expression

W LMMSEi = R hi hp i R hp i hp i + σ 2 I ′ -1 . (27)
R hi, hp i = E hi hH pi ∈ C K d ×Kp represents the cross correlation matrix of the real channel and the real channel vector at the K p pilot subcarriers within the i-th received OFDM symbol. Moreover, R hp i , hp i = E hpi hH pi ∈ C Kp×Kp denotes the autocorrelation matrix of hpi . I ′ Kp is the identity matrix, and σ 2 is the noise power. Therefore, the LMMSE estimated channel at the K d data subcarriers within the i-th received OFDM symbol can be simply obtained as

follows ĥLMMSEi = W LMMSEi ĥpi . ( 28
)
It is worth mentioning that the LMMSE performance highly depends on the pre-estimated W LMMSE matrix, where it suffers from considerable performance degradation in case the channel employed in the W LMMSE estimation changes. Therefore, it is impractical to be employed in real-time scenarios.

IV. PROPOSED DFT-BASED CHANNEL ESTIMATION SCHEMES

In this section, a detailed description of the time-variant channel estimation problem is first given. After that, the classical DFT based estimator, the proposed T-DFT, and TA-TDFT estimators which adhere to the IEEE 802.11p standard are presented. Moreover, the analytical NMSE expressions of the proposed estimators are derived and compared.

As discussed, the wireless channel in vehicular environment is considered as a doubly selective channel, it is time selective due to the vehicle's motion, and frequency selective due to the multi-path fading impact on the transmitted OFDM frames. Recall [START_REF] Kim | Time and Frequency Domain Channel Estimation Scheme for IEEE 802.11p[END_REF] ỹi

[k] = hi[k] xi[k] + ẽi,d[k] + ṽi[k], k ∈ Kon where, hi [k] = 1 K L-1 l=0 hi [l, 0]e -j2π kl
K . The goal is to estimate hi [k] at the data subcarriers based on the pilot subcarriers. Let h i,L ∈ C L×1 , defined by

h i,L [l] = 1 K hi [l, 0], l = 0 • • • L -1.
Accordingly, the vector model corresponding to the K p , and K d subcarriers can be expressed as follows

ỹp i = (Fphi,L) ⊙ xp i + ẽp i ,d + ṽp i , k ∈ Kp. ỹd i = (F d hi,L) ⊙ xd i + ẽd i ,d + ṽd i , k ∈ Kd. ( 29
)
where ⊙ denotes the element-wise multiplication. F d ∈ C K d ×L represents the truncated DFT matrix obtained by selecting K d rows, and L columns from the K × K DFT matrix. F p ∈ C Kp×L denotes the truncated DFT matrices at K p subcarriers. The pilot signal is used to estimate h i,L . First, by dividing over the pilots, we get

ĥp i = ỹp i ⊘ xp i + ẽp i ,d ⊘ xp i + ṽp i ⊘ xp i = hp i + ẽp i ,d ⊘ xp i + ṽp i ⊘ xp i , (30)
where ⊘ is the element wise division, and hpi = F p h i,L .

In our work, we consider that the transmitted pilots are equal to one for simplicity. Moreover, after estimating ĥi,L employing ĥpi , the final channel estimate at K d subcarriers of the i-th received OFDM symbol can be obtained according to the employed estimator as we will discuss in the next subsections, where hdi = F d h i,L .

A. CLASSICAL DFT ESTIMATOR

The classical DFT estimator employs DFT interpolation [START_REF] Biyyam | Optimal Channel Estimation Using DFT-Based Interpolation with Comb-Type Pilots for OFDM Systems[END_REF] in order to obtain the final channel estimates at K d subcarriers assuming that F p is either tall or square matrix, i.e. K p ≥ L. Therefore, ĥi,L can be estimated with the LS as

ĥi,L = F † p ĥp i = hi,L + F † p (ẽ p i ,d + ṽp i ). (31)
Here, F † p = (F H p F p ) -1 F H p is the pseudo inverse matrix of F p , and (•) H denotes the conjugate transpose. After that, the estimate at the data subcarrier denoted as ĥDFTi , is computed as follows

ĥDFT i = F d ĥi,L = F d hi,L + WDFTzDFT i , (32)
where W DFT = F d F † p denotes the DFT interpolation matrix and z DFTi = ẽpi,d + ṽpi . The DFT estimation MSE ϵ DFT can be expressed as

ϵDFT i = E ĥDFT i -hi,d 2 = trace WDFT Λ p,d + σ 2 IK p W H DFT , (33)
where σ 2 denotes the noise variance, Λ p,d = E ẽpi,d ẽH pi,d ∈ C Kp×Kp is the auto-correlation matrix of the Doppler error at K p subcarriers, and I Kp ∈ C Kp×Kp denotes the identity matrix. Based on [START_REF] Choi | Low-Complexity 2D LMMSE Channel Estimation for OFDM Systems[END_REF], Λ p,d is diagonal and independent of i.

B. PROPOSED TRUNCATED DFT ESTIMATOR FOR IEEE 802.11P STANDARD

Vehicular channel models consist of 12 taps, as discussed in [START_REF] Acosta-Marum | Six Time and Frequency Selective Empirical Channel Models for Vehicular Wireless LANs[END_REF], while the IEEE 802.11p standard allocates only four pilots for each transmitted OFDM symbol. However, considering the bandwidth of 10 MHz, the number of discrete significant taps is smaller as shown in Figure 2. Thus, classical DFT cannot be implemented in IEEE 802.11p standard, since the condition K p ≥ L is not satisfied.

L d ∪ L e = {0, • • • , L -1}. Accordingly, let h i,Ld ∈ C L d ×1
and h i,Le ∈ C Le×1 be the vectors corresponding to the significant and minor channel taps, then the pilot signal (30) can be rewritten as

ĥi,p = F d,p hi,L d + Fe,phi,L e + ẽp i ,d + ṽp i , (34)
where F d,p ∈ C Kp×L d , F e,p ∈ C Kp×Le denote the truncated DFT matrices at K p subcarriers, and L d , L e channel taps respectively, as shown in Figure 3. Similarly, the channel gain at the data subcarriers can be expressed as

hi,d = F d hi,L d + Fehi,L e . (35)
Here F d ∈ C K d ×L d , and F e ∈ C K d ×Le denote the truncated DFT matrices obtained by selecting its K d rows and L d , L e columns respectively. First, h i,Ld is estimated using LS as

ĥi,L d = F † d,p ĥi,p = hi,L d + F † d,p Fe,phi,L e + F † d,p (ẽ p i ,d + ṽp i ), (36)
where F † d,p is the pseudo inverse matrix of F d,p . Therefore, the T-DFT estimator for IEEE 802.11p standard can be expressed as follows

ĥT-DFT i = F d ĥi,L d = F d hi,L d + WTDFTzTDFT i , (37)
where W TDFTi = F d F † d,p denotes the T-DFT interpolation matrix and z TDFTi = F e,p h i,Le + ẽpi,d + ṽpi . The overall estimation error between hi,d and ĥT-DFTi is denoted by êTDFT and it can be expressed as follows

eTDFT = ĥT-DFT i -hi,d = WL e hi,L e + WTDFT(ẽ p i ,d + ṽp i ), (38)
where W Le = W TDFT F e,p -F e . Therefore, the T-DFT MSE can be expressed as

ϵT-DFT = E eTDFT i 2 = trace WL e ΛL e W H Le + trace WTDFT Λ p,d + σ 2 IK p W H TDFT , (39)
where Λ Le = E h i,Le h i,Le H ∈ C Le×Le represents the auto-correlation matrix of the L e neglected channel taps, which is independent of i. Note that, Λ Le is diagonal and E ẽpi,d h H i,Le = 0 due to the uncorrelated Delay-Doppler assumption. The classical DFT estimation is a special case when all the taps are considered. Thus, the error term trace W Le Λ Le W H Le is null, and the interpolation matrix W TDFT becomes W DFT .

C. PROPOSED TEMPORAL AVERAGING T-DFT ESTIMATOR

Considering the high temporal correlation between the successive channels, hi,d and hi+1,d , averaging has the potential of improving the estimation gradually. To demonstrate that, let hi,d = hd + εi , where hd is static and εi denotes the variation. Similarly, h i,Le = h Le + ∆ i,Le . Thus, using (38), we get ĥT-DFT i = hd + WL e hL e c + εi + WL e ∆i,L e

z i + WTDFT(ẽ p i ,d + ṽp i ) η i Note that ẽpi,d ẽH pj ,d = δ[i -j]Λ p,d
, due to the assumption of uncorrelated data, and E ṽpi ṽH

pj = δ[i -j]σ 2 I Kp . Therefore, η i = W TDFT (ẽ pi,d + ṽpi )
is the error term that benefits from averaging. On the other hand, the term z i = εi + W Le ∆ i,Le is a correlated error term, whereas c = W Le h Le is a static error within the frame. Both terms do not benefit from the averaging.

The TA-TDFT can be achieved such that

ĥTA-TDFT i =    ĥT-DFT i , i = 1 γ ĥTA-TDFT i-1 + (1 -γ) ĥT-DFT i , 2 ⩽ i ⩽ I (40)
where γ defines the weights given to ĥTA-TDFTi-1 and ĥT-DFTi .

In our simulations we consider γ = 1 2 , therefore ĥTA-TDFTi can be rewritten in terms of the previous estimated T-DFT channels ĥT-DFTi as follows

ĥTA-TDFT i = 1 2 (i-1) ĥT-DFT 1 + i j=2 1 2 (i-j+1) ĥT-DFT j = hd + εi + c + zTA-TDFT i -εi + ηTA-TDFT i . (41)
Here, the overall error terms are given by zTA-TDFT i = 1 2

(i-1) z1 + i j=2 1 2 (i-j+1) zj ηTA-TDFT i = 1 2 (i-1) η1 + i j=2 1 2 (i-j+1) ηj (42)
The TA-TDFT overall estimation error depends on the i-th received OFDM symbol, the SNR, and the Doppler. At low SNR, the estimation error is highly influenced by the noise, where η i ≈ W TDFT ṽpi . In this case, the averaging reduces the noise power when i increases, such that

ϵ (1) TA-TDFT i ≤ NTA-TDFT i σ 2 trace WTDFTW H TDFT , (43)
where

NTA-TDFT i = 1 4
(i-1)

+ i j=2 1 4
(i-j+1)

= 4 i-1 + 2 3 × 4 i-1 . ( 44
)
At high SNR region and low mobility, the error is influenced by non-significant channel taps error c, and thus, ϵ

TA-TDFT i ≤ trace WTDFTΛ Le W H TDFT . (2)
At high mobility, the error is influenced by z TA-DFTi -εi , which leads to an increase of the averaging error because of the increase in ∥ε i ∥. Accordingly, the gain of averaging is notable at low SNR, not significant at high SNR with low mobility, and worse at very high SNR and very high mobility.

We note that ϵ

TA-TDFTi + ϵ

TA-TDFTi denotes the lower bound performance of the TA-TDFT estimator.

Figure 4 shows the analytical and simulated NMSE curves of the proposed estimators in low and high mobility vehicular scenarios. Moreover, the classical DFT and TA-DFT where the temporal averaging is employed with classical DFT estimation are also presented for better illustrating the performance degradation sources.

It can be noticed that the analytical results coincide with the simulated results, thus validating the derived NMSE expressions for the proposed estimators. It is clearly shown that applying temporal averaging on top of the T-DFT estimator improves the NMSE performance, especially in low SNR region, where the impact of noise is dominant. This is because adding the temporal averaging step to the T-DFT estimated channels, reduces the noise power iteratively over the frame, and thus the SNR increases resulting in improving the total channel estimation accuracy. On the other hand, the TA-TDFT estimator suffers from an error floor in high SNR region, due to the channel model error resulting from the neglected L e channel taps in low mobility scenario, Figure 4a, in addition to Doppler interference error in high mobility scenario, Figure 4b. Moreover, employing TA-DFT estimator with K p = L = 12 pilot subcarriers, leads to a significant NMSE performance improvement over the whole SNR region, especially in low mobility scenario, since L channel taps are estimated by the DFT estimator. However, it can be noticed that in high mobility scenario, the temporal averaging step is not helpful, especially in high SNR region even though the impact of noise is very low. But on the other hand, the dominant impact of Doppler interference error in high mobility scenarios affects the performance improvement caused by the temporal averaging step in high SNR region.

Finally, we note that if K p = 12 is considered, this requires a modification in the IEEE 802.11p standard structure, where 1Mbps loss in the transmission data rates is recorded, since the data subcarriers K d becomes 40 instead of 48 data subcarriers per OFDM symbol. However, in this paper, we focus on the estimators that adhere to the IEEE 802.11p standard, therefore, only T-DFT and TA-TDFT estimators will be considered in the simulations.

V. SIMULATION RESULTS

In this section, NMSE and BER simulations are conducted in order to evaluate the performance of the proposed estimators compared to IEEE 802.11p conventional estimators and the LMMSE estimator where three simulation scenarios are considered as follows Hz. This scenario is employed in order to further evaluate the robustness of the proposed schemes. We note that the NMSE is computed using the estimated channel hΨi , where Ψ ∈ {STA, CDP, . . . } and the power of the channel frequency-time response such that

NMSE Ψ = hΨi -hi 2 hi 2 . ( 46
)
Moreover, two modulation orders are employed in the three simulation scenarios, QPSK and 16QAM. Moreover, convolutional channel coding with a 1 2 code rate is used. The frame size is I = 100 OFDM symbols, and the SNR range ∈ [0 dB, 40 dB]. The NMSE and BER performance evaluation of the benchmarked estimators are performed over the chosen vehicular channel models according to three criteria: (i) Modulation order, (ii) Mobility, and (iii) frame length. Moreover, a robustness analysis is presented in order to evaluate the generalization ability of the proposed estimators in comparison to the LMMSE.

A. NMSE EVALUATION

As we can notice from Figure 6, the estimation error of the conventional DPA-based estimators are affected by the employed modulation order, where the estimation error increases for high modulation order. When short frame size is employed as shown in Figure 7a, the channel variation is negligible within the received OFDM frame. Therefore, we can notice that the performance degradation of the conventional DPA-based estimators is less than that when a longer frame is employed and the basic LS estimator still performs well, where it records similar performance as LMMSE especially in low SNR regions. However, in very high mobility scenarios, the impact of Doppler error is dominant, thus, affecting the performance of conventional DPA-based estimators. In contrast, we can notice that employing long frames leads to considerable performance challenges even in low mobility, where the basic LS estimator is not useful as shown in Figure 7b. On the other hand, since the LMMSE and the proposed estimators are linear and do not employ demapping, then, the estimation error is independent of the modulation order. In addition, as the estimation is performed in symbol-bysymbol fashion, only TA-TDFT experiences dependency on the frame length since it employs averaging. This behavior can be seen in Figure 7. In particular, when the frame length is I = 100, the estimation error of TA-TDFT is slightly reduced at low mobility and low SNRs compared with shorter frames, as expected. In comparison with LMMSE , the T-DFT only approaches LMMSE at high SNR, whereas TA-TDFT outperforms LMMSE when the averaging is sufficient, which is the case of using a long frame (I = 100) at low SNRs, or in medium SNR region with a short frame (I = 10). However, at high mobility and high SNRs, the estimation error is influenced by Doppler interference as well as the channel model mismatch resulting from neglecting L e channel taps in the estimation process for all of the presented estimators. Figure 5 shows the average Doppler interference as f d increases. For low mobility vehicular scenarios, where f d < 200 Hz, we can notice that ϵ d is almost negligible. However, for high and very high mobility vehicular scenarios, where f d > 500 Hz, Doppler interference starts recording a considerable impact on the overall performance.

We note that the proposed estimators adhere to the IEEE 802.11p standard structure, and the transmission data rates in all modulation orders are preserved. Moreover, employing T-DFT and TA-TDFT estimators outperform conventional estimators with a considerable performance improvement and a significant decrease in the overall computational complexity as shown in Section VI.

B. BER EVALUATION

Figure 8 shows the BER performance of the studied estimators employing QPSK and 16QAM modulations in low mobility, high mobility, and very high mobility scenarios.

For QPSK modulation order, the STA estimator outperforms other conventional estimators in low SNR regions due to the frequency and time averaging operations used in STA ( 17), [START_REF] Karedal | A Geometry-based Stochastic MIMO Model for Vehicle-to-Vehicle Communications[END_REF]. Whereas in high SNR regions, conventional estimators express a significant improvement over the STA estimator, where CDP and TRFI record similar performance. This is due to the fact that when the SNR is low, the impact of noise and interference is high and powerful enough to shift the equalized received OFDM symbol y eq i [k] to wrong regions and as a result, its demapping d i [k] is shifted to incorrect constellation points. The STA estimator averaging operations are able to alleviate the impact of the noise. However, as the SNR increases, the aforementioned influence is reduced, and thus, the superiority of the conventional estimators emerges over STA. It is worth mentioning that the STA estimator frequency-domain averaging window β, and the time-domain averaging coefficient α are fixed to 2 as discussed in [START_REF] Fernandez | Performance of the 802.11p Physical Layer in Vehicleto-Vehicle Environments[END_REF]. But, fixing these parameters instead of updating them according to the channel variation makes the smoothing in the time and frequency domains not effective under vehicular environment. Thus, the gradually accumulated demapping error of d i [k] cannot be well mitigated using fixed β and α. Hence the emergence of the error floor for STA in high SNR region. On the other hand, the iCDP estimator improves the STA estimator performance by considering both STA and DPA estimations in updating the final iCDP channel estimates. We can notice that employing the iCDP estimator alleviates the STA estimator error floor in high SNR regions while recording almost similar performance as STA in low SNR regions. When 16QAM modulation is employed, STA performance is severely degraded in the whole SNR region due to the huge DPA demapping error that increases as the modulation order increases. Moreover, we can notice the impact of employing the cubic interpolation in TRFI, where it outperforms CDP by around 2dB gain. On the other hand, E-TRFI is not able to improve the TRFI estimator performance due to fixing the E-TRFI reliability test threshold to 0.5 as provided in [START_REF] Han | Virtual Subcarrier Aided Channel Estimation Schemes for Tracking Rapid Time Variant Channels in IEEE 802.11p Systems[END_REF].

We note that conventional estimators performance is limited due to their dependency on the DPA estimation and due to using fixed valued parameters. These two reasons are mainly responsible for the conventional estimators performance degradation in time-variant channel estimation as shown in Figure 6a and Figure 6b. In contrast, we can notice the performance superiority of the LMMSE over the conventional DPA-based estimators due to employing the channel and noise statistics in the channel estimation process. However, the robustness of the LMMSE estimator is limited in the online evaluation, when there is a significant mismatch between the estimated and real channel statistics. In contrast, the proposed T-DFT and TA-TDFT estimators do not depend on the DPA estimation and estimated channel statistics, thus the demapping error is totally eliminated, resulting in improving the overall estimation performance. Moreover, they record a robustness superiority over the LMMSE estimator as shown in Section V-C.

The impact of employing different frame lengths is illustrated in Figure 9. We can notice that the conventional DPAbased estimators perform better when shorter frame length is employed since the impact of the enlarged demapping error and channel variation is negligible compared to the case where long frames are employed. Moreover, the impact of employing temporal averaging on top of the T-DFT estimator to improve the overall performance can be observed, where the TA-TDFT estimator outperforms the T-DFT estimator by up to 3 dB gain in terms of SNR for a BER = 10 -3 for a long frame (I = 100), whereas the impact in a short frame (I = 10) is less significant.

It is worth mentioning that the impact of mobility and frame length can be observed in the significant decrease of BER when using long frames. This is due to the use of a long codeword and the harvested time diversity gain. The time diversity gain increases with the increase of the Doppler spread, as can be seen by comparing the case of high mobility (f d = 500) and very high mobility (f d = 1000). Nevertheless, as the channel estimation error increases with the increase of Doppler frequency, the net gain from the time diversity and channel estimation loss depends also on the frame length. For instance, assuming a perfect channel, there is a small net gain with (I = 100), when the Doppler shift increases from f d = 250 in low mobility to f d = 500 in high mobility, but it turns to a small loss for short frames (I = 10). The perfect estimation is only influenced by Doppler interference. With the induced estimation error, this impact becomes remarkable. The performance of the presented estimators is significantly degraded by the mobility increase, however, it is improved in high mobility for long frames. This observation is also valid for high modulation orders such as 16QAM, as shown in Figure 8.

C. ROBUSTNESS ANALYSIS

This section compares the robustness and generalization ability of the proposed T-DFT and TA-TDFT estimators with the LMMSE estimator. As discussed in III-D, the LMMSE estimator depends mainly on the pre-estimated W LMMSE matrix VOLUME 4, 2016 that is calculated offline. This offline pre-estimation affects the robustness and generalization ability of the LMMSE estimator when the channel changes in the online evaluation. To further illustrate this idea, we simulate the LMMSE estimator in four different cases, such that:

• Case 1 (Est: 12, Sim: 12): W LMMSE is pre-estimated using the 12 taps channel model and we consider that the number of taps is fixed also in the online testing. • Case 2 (Est: 12, Sim: Random): W LMMSE is preestimated using the 12 taps channel model. However, the number of channel taps changes randomly in the online testing. We note that the "Random" term means that the simulation is carried using a random number of paths, wherein each iteration, a random number of paths between 1 and 11 is eliminated from the channel power delay profile. Therefore, we obtain a generalized channel model where the number of taps varies. • Case 3 (Est: Random, Sim: 12): W LMMSE is preestimated where the number of channel taps varies randomly, while the channel taps are fixed to 12 in the online testing. • Case 4 (Est: Random, Sim: Random): Random number of channel taps are used in both offline estimation of W LMMSE and in the online testing. Figure 10 depicts the simulation results of these four cases in high mobility scenario employing both QPSK and 16QAM modulation orders. We can observe that the LMMSE performance is severely degraded when the channel changes in the online evaluation, whereas, the proposed TDFT and TA-TDFT estimators reveal good robustness since they are implemented without any dependency on the channel model statistics. Therefore, the proposed TDFT and TA-TDFT estimators are more robust than the LMMSE estimator.

VI. COMPLEXITY ANALYSIS

In this section, a detailed computational complexity and execution time analysis of the conventional and the proposed estimators are provided. The computational complexity analysis is performed according to the number of real-valued multiplication/division and summation/subtraction mathematical operations required to estimate the channel for one received OFDM symbol. Since we are working with complexvalued data, each complex-valued division requires 6 realvalued multiplications, 2 real-valued divisions, 2 real-valued summations, and 1 real-valued subtraction. Moreover, each complex-valued multiplication is equivalent to 4 real-valued multiplications, and 3 real-valued summations.

The least complex estimator is the basic LS estimator (14) where the received preamble symbols are added to each others, resulting in 2K on summations. After that, the summation result is divided by the predefined preamble, thus 2K on divisions are also required. Therefore, the total number of divisions and summations needed by the basic LS estimator is 2K on and 2K on respectively.

The DPA estimation requires two equalization steps [START_REF] Ricklin | Time Varying Channels : Characterization, Estimation, and Detection[END_REF], and [START_REF] Mecklenbrauker | Vehicular Channel Characterization and Its Implications for Wireless System Design and Performance[END_REF]. Each equalization step consists of K on complex-valued division, therefore the overall computational complexity of DPA is 16K on multiplications/divisions and 6K on summations/subtractions.

The STA estimator applies frequency and time-domain averaging on top of DPA. The frequency-domain averaging (17) coefficient is fixed (β = 2). Therefore, each subcarrier requires 5 complex-valued summations multiplied by a real-valued weight, which are equivalent to 10 realvalued summations and 2 real-valued multiplications. But the frequency averaging in the STA estimator is applied on K d since the subcarriers in the boundaries are excluded from the averaging operation. As a result, the STA frequencydomain averaging step requires 10K d real-valued summations and 2K d real-valued multiplications. Moreover, the STA time-domain averaging step (18) requires 4K on realvalued divisions, and 2K on real-valued summations. Therefore, the computational complexity of STA is 4K on + 2K d real-valued multiplications/divisions, and 2K on + 10K d realvalued summations/subtractions, and the accumulated overall computational complexity of STA estimator is 22K on + 2K d multiplications/divisions and 10K on + 10K d summations/subtractions.

For the E-TRFI estimator, it starts with the E-LS estimation step ( 19) that requires 4K on K real-valued multiplications and 5K on K -2K real-valued summations. Then equalization is employed only on K d subcarriers where 8K d multiplications/divisions and 3K d summations/subtractions are required. The Euclidean distance reliability test employs K d + 2M K d real-valued divisions and 4M K d subtractions. After that, frequency-domain cubic interpolation is performed. Our simulations show that for each OFDM symbol, K URS = 16 subcarriers needed to be interpolated. The frequency-domain cubic interpolation requires 26K URS multiplications/divisions and 30K URS summations/subtractions. Finally, the E-TRFI employs the noise attenuation step that requires 4K 2 real-valued multiplications and 5K 2 -2K realvalued summations. Hence, the E-TRFI estimator's overall computational complexity is 4K 2 + 4KK on + 9K d + 26K URS multiplications/divisions and 5K 2 +5KK on +3K d + 2M K d +30K URS -4K real-valued summations/subtractions.

The LMMSE estimator manipulates first the LS estimation at the pilot subcarriers within the received OFDM symbol which requires 2K p real-valued divisions. After that, the matrix inversion in (27) requires K 3 p complex-valued multiplication. Accordingly, the overall computational complexity of the conventional LMMSE estimator is 4K It is worth mentioning that the proposed estimators achieve better BER and NMSE performance than the studied conventional estimators, while reducing the computational complexity, by which TA-TDFT and T-DFT record 22.64% and 7.35% computational complexity decrease than the conventional LMMSE estimator, respectively. Moreover, the TA-TDFT estimator has a complexity higher than the T-DFT estimator by 17.56% as illustrated in 11.

Table 4 shows a detailed summary of the computational complexities for studied estimators. We note that the detailed calculation of TRFI, CDP, iCDP estimators is presented in [START_REF] Wang | An Improved Channel Estimation Technique for IEEE 802.11p Standard in Vehicular Communications[END_REF], [START_REF] Gizzini | Deep Learning Based Channel Estimation Schemes for IEEE 802.11p Standard[END_REF].

Figure 11 show a bar graph for the required multiplications/divisions, and summations/subtractions by the studied estimators. It can be noticed that employing both T-DFT and TA-TDFT instead of the studied conventional estimators leads to a significant decrease in the overall computational complexity compared to the conventional DPA-based and LMMSE estimators, while recording a considerable gain in BER and NMSE performance.

On the other hand, the proposed estimators record less execution time than the conventional estimators as can be observed in Table 5. We note that the simulations are performed using a 64-bit operating system with an Intel Core i7-8850H CPU processor (clock speed: 2.60 GHz).

VII. CONCLUSIONS AND PERSPECTIVES

In this paper, we have focused on overcoming the limitations of vehicular SoA conventional estimators represented by their dependency on the DPA estimation, where the demapping error and the noise are enlarged during the estimation process. To overcome these limitations, we have proposed low-complexity and robust channel estimators for vehicular communications, namely T-DFT and TA-TDFT. Unlike classical estimators, the proposed estimators are based on the truncated DFT-based interpolation and do not require the DPA estimation as an initial estimation step. Therefore, the enlarged DPA demapping error and the noise enhancement that results from the basic LS estimator are totally eliminated in the proposed estimators. In addition to that, the proposed As future work, we will extend our analysis to the IEEE 802.11bd standard as well as cellular-based vehicular communications settings. A detailed investigation in terms of performance, complexity and latency will be conducted. However, inspired by the work proposed in [START_REF] Karim Gizzini | CNN Aided Weighted Interpolation for Channel Estimation in Vehicular Communications[END_REF], [START_REF] Ehsanfar | Performance Comparison of IEEE 802.11p, 802.11bd-draft and a Unique Word-based PHY in Doubly-Dispersive Channels[END_REF], it is expected that the new features of the upcoming IEEE 802.11bd standard will significantly improve the channel estimation accuracy compared to the IEEE 802.11p standard. Moreover, it is worthwhile to see if the performance gain of employing the IEEE 802.11bd standard will be able to alleviate efficiently the DPA demapping error of the SoA estimators, or it will be the same case as the IEEE 802.11p standard.

FIGURE 1 :

 1 FIGURE 1: IEEE 802.11p transmitted frame structure in the time domain.

  To overcome this limitation, we propose a T-DFT estimator that targets the estimation of only L d = K p dominant channel taps out of L. The indexes of those dominant taps are denoted as L d , L d = |L d |, and they are selected based on the maximum values of the channel impulse response amplitude denoted as ρ[l, 0] according to the measured channel profile as shown in Figure 2. The remaining minor taps are represented by the set L e , L e = |L e | and they are considered as noise. Thus,

FIGURE 2 :

 2 FIGURE 2: Vehicular channel dominant taps selection.

FIGURE 3 :

 3 FIGURE 3: Proposed T-DFT truncated DFT matrices.

  Low mobility vehicular channel model. (b) High mobility vehicular channel model.

FIGURE 4 :

 4 FIGURE 4: NMSE analytical and simulation results for low and mobility vehicular channel models respectively.

FIGURE 5 :

 5 FIGURE 5: Doppler spectrum Interference.

•

  Low mobility vehicular scenario, where the VTV-UC channel model is employed using V = 45 Kmph which is equivalent to F d = 250 Hz as a maximum Doppler NMSE performance employing 16QAM.

FIGURE 6 :

 6 FIGURE 6: NMSE performance employing three scenarios: (i) first column -low mobility (v = 45 Kmph, f d = 250 Hz) (ii) second column -high mobility (v = 100 Kmph, f d = 500 Hz) (iii) third column -very high mobility (v = 200 Kmph, f d = 1000 Hz).

  NMSE performance with I = 100.

FIGURE 7 :

 7 FIGURE 7: NMSE performance employing three scenarios: (i) first column -low mobility (v = 45 Kmph, f d = 250 Hz) (ii) second column -high mobility (v = 100 Kmph, f d = 500 Hz) (iii) third column -very high mobility (v = 200 Kmph, f d = 1000 Hz).

  BER performance employing 16QAM.

FIGURE 8 :

 8 FIGURE 8: BER performance employing three scenarios: (i) first column -low mobility (v = 45 Kmph, f d = 250 Hz) (ii) second column -high mobility (v = 100 Kmph, f d = 500 Hz) (iii) third column -very high mobility (v = 200 Kmph, f d = 1000 Hz).

  BER performance with I = 100.

FIGURE 9 :

 9 FIGURE 9: BER performance employing three scenarios: (i) first column -low mobility (v = 45 Kmph, f d = 250 Hz) (ii) second column -high mobility (v = 100 Kmph, f d = 500 Hz) (iii) third column -very high mobility (v = 200 Kmph, f d = 1000 Hz).

  BER performance employing QPSK. (b) NMSE performance employing QPSK. BER performance employing 16QAM. (d) NMSE performance employing 16QAM.

FIGURE 10 :

 10 FIGURE 10: Robustness analysis of the proposed DFT-based estimators versus the LMMSE estimator in high mobility channel model (f d = 500 Hz).

  3 p + 4K p K d + 2K p real-valued multiplications/divisions and 3K 3 p + 2K 2 p + 5K p K d -2K d real-valued summations.Compared to the conventional estimators, the T-DFT estimator does not require the DPA as a pre-estimation step. It only requires the LS estimated channel at pilot subcarriers ĥi,p that requires 2K p divisions. It is worth mentioning that W MDFT is computed offline, thus the computational complexity of the T-DFT estimator lies in multiplying W MDFT with ĥi,p which requires K p K d -K d complex-

  TDFT T-DFT Execution time 1.23 ms 0.93 ms 0.76 ms 0.68 ms 0.24 ms 1.24 µs 0.46 µs 0.38 µs estimators do not depend on the pre-estimated channel statistics as it is the case for LMMSE estimator, thus, they are insensitive against channel model changes. Therefore, they are more suitable to be employed in practical systems. Simulation and analytical results have shown the performance superiority of the proposed T-DFT and TA-TDFT estimators over conventional estimators in low and high mobility vehicular scenarios with a significant computational complexity and execution time decrease.

TABLE 1 :

 1 IEEE 802.11p modulation orders and data rates.

  xdi [k] and xp i [k] denote the modulated data symbols and the predefined pilot symbols allocated at a set of subcarriers denoted K d and K p , respectively. The other guard band subcarriers are allocated at the set of subcarriers K n . x i [k] is converted to the time domain by applying the inverse discrete Fourier transform, such that

TABLE 2 :

 2 IEEE 802.11p physical layer specifications.

	Parameter	IEEE 802.11p
	Bandwidth	10 MHz
	Carrier frequency	5.9 GHz
	CP duration	1.6 µs
	Symbol duration	8 µs
	STS duration	1.6 µs
	LTS duration	6.4 µs
	Overall STS duration	16 µs
	Overall LTS duration	16 µs
	Total subcarriers	64
	Pilot subcarriers	4
	Data subcarriers	48
	Null subcarriers	12

TABLE 3 :

 3 Vehicular channel models characteristics following Jake's Doppler spectrum.

	Channel model	Channel taps	Vehicle velocity [kmph]	Max Doppler shift [Hz]	Average path gains [dB]	Path delays [ns]
						[0, 1, 100, 101, 200, 201,
	RTV-SS	12	32-48	500		300,301, 400,
						500, 600, 700]
					[0, 0, 0, -9.3, -9.3, -9.3,	[0, 1, 2, 100, 101, 102,
	RTV-EX	12	104	700	-20.3, -20.3, -21.3,	200, 201, 300,
					-21.3, -28.8, -28.8]	301, 400, 401]
					[0, 0, 0, -11.5, -11.5, -11.5,	[0, 1, 2, 100, 101, 102,
	RTV-UC	12	32-48	300	-19, -19, -25.6,	200, 201, 300,
					-25.6, -28.1, -28.1]	301, 500, 501]
					[0, 0, 0, -6.3, -6.3, -25.1,	[0, 1, 2, 100, 101, 200,
	VTV-EX	11	104	1200	-25.1, -25.1, -22.7,	201, 202, 300,
					-22.7, -22.7]	301, 302]
					[0, 0, -10, -10, -10, -17.8,	[0, 1, 100, 101, 102, 200,
	VTV-UC	12	32-48	500	-17.8, -17.8, -21.1,	201, 202, 300,
					-21.1, -26.3, -26.3]	301, 400, 401]
					[0, 0, -11.2, -11.2, -19, -21.9,	[0, 1, 100, 101, 200, 300,
	VTV-SDWW	12	104	1150	-25.3, -25.3, -24.4,	400, 401, 500,
					-28, -26.1, -26.1]	600, 700, 701]

[0, 0, -9.3, -9.3, -14, -14, -18, -18, -19.4, -24.9, -27.5, -29.8]

TABLE 4 :

 4 Computational complexity analysis of the SoA SBS channel estimators.+ 4K on K + 2M K d + 26K URS 5K 2 + 5K on K + 3K d + 4M K d + 30K URS -4K LMMSE ĥpi , R hi, hp i , R hp i , hp i 4K 3 p + 4K p K d + 2K p 3K 3 p + 2K2 p + 5K p K d -2K d Detailed computational complexity of the SoA SBS channel estimators in terms of real-valued operations. valued summations, and K p K d complex-valued multiplications, that are equivalent to 5K p K d -2K d real-valued summations, and 4K p K d real-valued multiplications. Therefore the overall computational complexity of the T-DFT estimator is 2K p + 4K p K d real-valued multiplications/divisions, and 5K p K d -2K d real-valued summations. On the other hand, the TA-TDFT estimator applies simple time averaging on top of the T-DFT estimator that requires additional 4K d realvalued multiplications, and 2K d real-valued summations. As a result, TA-TDFT estimator requires 2K p + 4K d + 4K p K d real-valued multiplications/divisions, and 5K p K d real-valued summations.

	Est.	Pre-Est.	Mul. / Div.	Sum. / Sub.
	LS	-	2K on	2K on
	DPA	LS	18K on	8K on
	STA	DPA	22K on + 2K d	10K on + 10K d
	CDP	DPA	34K d	14K d
	TRFI	DPA	34K on + 26K URS	14K on + 30K URS
	iCDP	DPA , STA	58K on + 2K d	26K on + 10K d
	E-TRFI 10 0 10 1 10 2 Real-Valued Operations	DPA 4K 2 E-TRFI iCDP TRFI Multiplications/Divisions Summations/Subtractions CDP STA LMMSE TA-TDFT T-DFT	LS

FIGURE 11:

TABLE 5 :

 5 CPU execution time analysis of the studied estimators.

VOLUME 4, 2016

 VOLUME 4, 2016

 VOLUME 4, 2016

 VOLUME 4, 2016

 VOLUME 4, 2016


Alexandre Bazin
email: alexandre.bazin@u-montpellier.fr

Giacomo Kahn
email: giacomo.kahn@univ-lyon2.fr

Camille Noûs

Some Notes on Polyadic Concept Analysis

Keywords: Formal Concept Analysis, Polyadic Concept Analysis, Conceptual Structures

published or not. The documents may come   L'archive ouverte pluridisciplinaire

1 Unde Venis Et Quo Vadis?

Formal Concept Analysis (FCA [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]) is a formalism that establishes a connection between classical binary data (crosstables) and the structure of concepts and rules that can be found in said data. It is very powerful, if underutilised, as it offers well-studied mathematical structures to be exploited by algorithms.

As crosstables are a rather limiting way of representing data, various extensions of the formalism have been proposed to deal with more complex data, such as Pattern Structures [START_REF] Ganter | Pattern Structures and Their Projections[END_REF], Relational Concept Analysis [START_REF] Rouane-Hacene | Relational Concept Analysis: Mining Concept Lattices from Multi-Relational Data[END_REF], fuzzy FCA [START_REF] Poelmans | Fuzzy and Rough Formal Concept Analysis: a Survey[END_REF] or graph FCA [START_REF] Ferré | Graph-fca: An extension of formal concept analysis to knowledge graphs[END_REF]. Just like FCA, they are based on lattice theory [START_REF] Birkhoff | Lattice Theory[END_REF].

Triadic Concept Analysis [START_REF] Lehmann | A Triadic Approach to Formal Concept Analysis[END_REF] and Polyadic Concept Analysis (PCA) [START_REF] Voutsadakis | Polyadic Concept Analysis[END_REF] aim to extend FCA to data in the form of n-ary relations (i.e. multidimensional crosstables) and have the peculiarity of involving n-lattices instead of lattices. Such structures are considerably less known and studied, and results that would be considered basic in lattice theory are missing. While some would consider this an opportunity to pioneer a whole new field, the heavy notations and lack of clear definitions and impressive applicative results repels researchers.The opportunities are however numerous as multidimensional data is now ubiquitous: RDF datasets, folksonomies, pharmacogenomical knowledge are all inherently at least triadic and transforming them to fit dyadic crosstables only results in lost information. As such data are also understudied in data mining in general, this is a unique occasion to position FCA and its extensions as a leading formalism. Some work has already been done in this direction in the field of multidimensional association rule mining [START_REF] Missaoui | Computing triadic generators and association rules from triadic contexts[END_REF][START_REF] Bazin | Condensed representations of association rules in n-ary relations[END_REF].

In this paper, we aim at promoting Polyadic Concept Analysis by discussing the differences with FCA introduced by n-lattices, suggesting future research directions, and presenting recent results and open questions on the size of n-lattices. Section 2 contains definitions, including a proposition for a stable definition of implications. Section 3 discusses the impact of the loss of duality between orders in n-lattices on the relation between FCA structures, as well as a suggestion for a multidimensional generalisation of Boolean lattices. Section 4 presents recent results on the maximal size of concept n-lattices found in cubic contexts.

The Basics of Boxes

We assume that the reader is at least somewhat familiar with FCA. If this is not the case, we refer the reader to the usual book [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]. Polyadic concept analysis is a natural extension of FCA in which the underlying relation is n-ary. It was first introduced in its triadic form by Lehman and Wille [START_REF] Lehmann | A Triadic Approach to Formal Concept Analysis[END_REF], and then generalised to the n-dimensional case by Voutsadakis [START_REF] Voutsadakis | Polyadic Concept Analysis[END_REF]. In this setting, an n-context is an (n + 1)-tuple (S 1 , . . . , S n , R) where the S i are sets called dimensions and R ⊆ n i=1 S i is an n-ary relation between them. We shall call objects the elements of the first dimension S 1 while the (n -1)tuples (s 2 , . . . , s n ) such that (s 1 , s 2 , . . . , s n ) ∈ R form the description of the object s 1 . An example of a triadic context is depicted in Fig. 1.

a b c a b c a b c 1 × × × × 2 × × 3 × × × × × α β γ
Fig. 1: A triadic context ({α, β}, {1, 2, 3}, {a, b, c}, R).

An n-concept is then a maximal n-dimensional box full of crosses, i.e. an n-tuple

(X 1 , . . . , X n ) such that n i=1 X i ⊆ R and no X i is such that i-1 j=1 S j × X i ∪ {x} × n k=i+1 S k ⊆ R with x ∈ X i .
For instance, ({α, β}, {1, 2}, {a}) is an n-concept in Fig. 1. The set C of all n-concepts in an n-context together with the n quasi-orders induced by the inclusion relation on their n components form an n-lattice L = (C, 1 , . . . , n ). Note that an nlattice is an n-ordered set, i.e. it respects:

if ∀i ∈ {1, . . . , n} \ {j}, A i B then A j B (antiordinal dependency) and if ∀i ∈ {1, . . . , n}, A ∼ i B, then A = B (uniqueness condition).

Different definitions of implications in triadic and polyadic contexts have been proposed through the years such as "Biedermann's implications" [START_REF] Biedermann | How Triadic Diagrams Represent Conceptual Structures[END_REF], attribute×condition, conditional attribute or attributional condition implications [START_REF] Ganter | Implications in Triadic Formal Contexts[END_REF]. In [START_REF] Bazin | On Implication Bases in n-Lattices[END_REF], it was proposed to consider all the implications that hold in dyadic contexts resulting from combinations of two transformations of an n-context C (see Fig. 2): Note that possible implications include those in C ({greek,numbers},{latin}) whose support is in a Cartesian product of dimensions. Such rules (under the more general umbrella of association rules) are already under consideration in the data mining community [START_REF] Kim-Ngan T Nguyen | Multidimensional Association Rules in Boolean Tensors[END_REF][START_REF] Bazin | Condensed Representations of Association Rules in n-ary Relations[END_REF]. Additionally, if one is only interested in implications that do not contain the first dimension -the objects -these implications are all derivable from the implications of C ({S1},{S2,...,Sn}) through the application of Armstrong's axioms plus two other axioms, as discussed in [START_REF] Bazin | On Implication Bases in n-Lattices[END_REF]. This means that one only has to reason on a single type of implication.

-C (A,B) = ( A, B, R (A,B) ),
) ∈ R D iff ∀x ∈ D, (s 1 , . . . , s d-1 , x, s d+1 , . . . , s n ). (1, a) (1, b) (1, c) (2, a) (2, b) (2, c) (3, a) (3, b) (3, c) α × × × × β × × × × γ × × × 1 2 3 α × × × β × × γ a b c α × β γ ×
Just as in the dyadic case, the set of all the implications that do not involve the first (object) dimension and that hold in an n-context (or any its implication bases) can be used to reconstruct the set of n-concepts restricted to their last n -1 components [START_REF] Bazin | On Implication Bases in n-Lattices[END_REF].

We conclude this first section with a small digression about graphical representation. In two dimensions, both partial orders of the concept lattice (T (C), ⊆ 1 , ⊆ 2 ) have the decency of being dual, and thus one can be omitted, allowing a concept lattice to be graphically represented by a Hasse diagram. Starting from three dimensions, concepts are ordered differently. In n dimensions, there are classes of equivalent concepts with the same ith component, and those concepts can then be differentiated in the n-1 other quasi-orders. A graphical representation that clearly shows the equivalence classes and the quasi-order relations is -at best -hard to attain. This is a first open question offered by PCA.

In three dimensions, a tentative graphical representation exists [7, Section 3], that combines a geometric representation of equivalence classes together with Hasse-like representation for each quasi-order. The few graphical representations of 4-lattices, for example in [8, figures 1 and 2] can only make one hope for another type of graphical representation, possibly via Virtual Reality, as is already proposed for FCA [START_REF] Sȃcȃrea | Improving User's Experience in Navigating Concept Lattices: An Approach Based on Virtual Reality[END_REF][START_REF] Breckner | Improving User's Experience in Exploring Knowledge Structures: A Gamifying Approach[END_REF].

3 Loss of Duality and the FCA Trinity

Structural Equivalences

In the dyadic case, the formal context, the concept lattice and the set of implications are equivalent in the sense that they can be computed from one another. This is the reason why the FCA formalism is so useful for data analysis. In the multidimensional case, this equivalence softens, which introduces new challenges, constraints and open questions. Let us consider the two triadic contexts depicted in Fig. 3 in which the Greek letters form the first dimension (the objects), and their triadic concepts.

We observe that the concepts differ only on their first components. Hence, the second and third quasi-orders of both triadic concept lattices are isomorphic while the first quasi-orders are not. This is a most significant change from the bidimensional case: the knowledge of n -1 quasi-orders is not enough to know the last one. Let us call the last n -1 components of a concept its feature and the first component its extent, as usual. Then, given a set of concepts known only by their features, there are multiple non-isomorphic ways objects can belong to the extents. This clashes with the usual notions of subsumption.

Let us say that two concept n-lattices are equivalent if and only if their kth quasiorders are isomorphic for all k ∈ {2, . . . , n}. We denote by [L] the equivalence class of the concept n-lattice L. As mentioned in the previous section, implications in ncontexts can be used to construct (exactly) the features of the associated n-concepts. Hence, all the implication bases of all the n-contexts of the lattices in [L] allow for the construction of the same features. These implications can, however, differ from ncontext to n-context. For instance, the implication {(2, a)} → {(1, b)} holds in Fig. 3's first triadic context (as both crosses appear together in the description of the object α) but not in the second. From this, we deduce that some implications have no influence on the construction of the features. We thus propose to identify two types of implications:

a b c a b c 1 × × × × 2 × × 3 × α β a b c a b c a b c 1 × × × × × 2 × × 3 × α β γ (∅,
-Structural implications that are used to construct the features of all the n-concepts of an n-context -Contextual implications that are not structural but still hold in an n-context Structural implications carry information about the features of n-concepts while contextual implications carry information about the distribution of the objects in the n-concepts. Thus, structural implications are common to all the n-contexts in an equivalence class [L] while contextual implications are not. In Fig. 3 (1,c)} is contextual in the first context only. In [START_REF] Bazin | On Implication Bases in n-Lattices[END_REF] is explained in an overly formal way, for which the author is very sorry, that constructing the features of all the n-concepts of an n-context only requires implications between "boxes", i.e. implications of the form

n k=2 X k → n k=2 Y k with X k ⊆ Y k ⊆ S k .
The structural implications are all the implications entailed by these implications between "boxes".

In an equivalence class [L], there is one n-lattice/n-context that seems to be of particular interest as it minimises the number of contextual implications with a nonempty support, which could have some use in data mining. It is fairly easy to construct this n-context: if two n-concept features are such that their intersection is not the feature of an n-concept, then the two features must appear in the descriptions of the same objects. This defines equivalence classes of features. Then, each such equivalence class of features is used to describe a different object. Fig. 4 illustrates this. The rectangles ({1}, {a, b}) and ({1, 2}, {a}) are features of triadic concepts while ({1}, {a}), their intersection, is not so both rectangles have to appear in the description of the same object. The intersection ({3}, {c}) of the rectangles ({2, 3}, {c}) and ({3}, {b, c}) is the feature of the triadic concept ({α, β}, {3}, {c}) so the three rectangles are put in the descriptions of different objects.

a b c a b c 1 × × 2 × × 3 × × × α β =⇒ a b c a b c a b c a b c 1 × × 2 × × 3 × × × × α β γ δ
Fig. 4: Transformation of a triadic context in a way that minimises the number of contextual implications with a non-empty support without changing the equivalence class of the associated concept lattice.

A Generalisation of Boolean Concept Lattices

We believe that studying such equivalence classes of concept n-lattices, instead of individual n-context/n-lattice pairs, is the way to go. We suggest to start with classes that seem to be particularly interesting as they generalise Boolean concept lattices. Let B j1,...,jn-1 be the class of concept n-lattices such that every possible feature on n -1 dimensions of size j 1 , . . . , j n-1 appear in an n-concept. For instance, Fig. 5 depicts the 3-context and 3-concepts of a member of B 3,3 . All rectangles in a 3 × 3 table appear as the feature of a 3-concept (the empty rectangle appears twice as ({1, 2, 3}, ∅) and (∅, {a, b, c}).

The n-lattices in B j1,...,jn-1 contain ( n-1 i=1 2 ji -1) + n -1 concepts. They generalise the Boolean concept lattices B j1 as they are extremal in the sense that all possible features appear in concepts, they do not contain any structural implications (contextual implications may exist) and one of the corresponding n-contexts resembles the contranominal scale as, for each object, an element of a dimension is completely missing (see Fig 5). As such, it is always possible, in a context in which the number of objects is at least equal to the sum of the sizes of all the other dimensions, to produce such an extremal n-lattice. It appears that B 2,2 can exist on 3 objects (Fig 6) while B 3,3 cannot exist on 5 (see Fig. 7 for another such extremal 3-context on 6 objects). It is currently unknown whether B 2,2 is an exception or other extremal n-lattices can exist on one less object. This problem of finding "maximally compact" n-contexts producing specific n-lattices seems relevant as it is tied to other potentially interesting problems such as finding the maximal number of n-concepts in an n-context of a given size or maximising the number of contextual implications.

× × × × × × × × × × × × 2 × × × × × × × × × × × × 3 × × × × × × × × × × × × α β γ δ ζ ({α, β, γ, δ, , ζ}, ∅, {a, b, c}) ({α, β, γ, δ, , ζ}, {1, 2, 3}, ∅) ({α, β, δ, }, {1}, {a}) ({α, γ, δ, }, {1}, {b}) ({β, γ, δ, }, {1}, {c}) ({α, δ, }, {1}, {a, b}) ({β, δ, }, {1}, {a, c}) ({γ, δ, }, {1}, {b, c}) ({δ, }, {1}, {a, b, c}) ({α, β, δ, ζ}, {2}, {a}) ({α, γ, δ, ζ}, {2}, {b}) ({β, γ, δ, ζ}, {2}, {c}) ({α, δ, ζ}, {2}, {a, b}) ({β, δ, ζ}, {2}, {a, c}) ({γ, δ, ζ}, {2}, {b, c}) ({δ, ζ}, {2}, {a, b, c}) ({α, β, , ζ}, {3}, {a}) ({α, γ, , ζ}, {3}, {b}) ({β, γ, , ζ}, {3}, {c}) ({α, , ζ}, {3}, {a, b}) ({β, , ζ}, {3}, {a, c}) ({γ, , ζ}, {3}, {b, c}) ({ , ζ}, {3}, {a, b, c}) ({α, β, δ}, {1, 2}, {a}) ({α, γ, δ}, {1, 2}, {b}) ({β, γ, δ}, {1, 2}, {c}) ({α, δ}, {1, 2}, {a, b}) ({β, δ}, {1, 2}, {a, c}) ({γ, δ}, {1, 2}, {b, c}) ({δ}, {1, 2}, {a, b, c}) ({α, β, }, {1, 3}, {a}) ({α, γ, }, {1, 3}, {b}) ({β, γ, }, {1, 3}, {c}) ({α, }, {1, 3}, {a, b}) ({β, }, {1, 3}, {a, c}) ({γ, }, {1, 3}, {b, c}) ({ }, {1, 3}, {a, b, c}) ({α, β, ζ}, {2, 3}, {a}) ({α, γ, ζ}, {2, 3}, {b}) ({β, γ, ζ}, {2, 3}, {c}) ({α, ζ}, {2, 3}, {a, b}) ({β, ζ}, {2, 3}, {a, c}) ({γ, ζ}, {2, 3}, {b, c}) ({ζ}, {2, 3}, {a, b, c}) ({α, β}, {1, 2, 3}, {a}) ({α, γ}, {1, 2, 3}, {b}) ({β, γ}, {1, 2, 3}, {c}) ({α}, {1, 2, 3}, {a, b}) ({β}, {1, 2, 3}, {a, c}) ({γ}, {1, 2, 3}, {b, c}) (∅, {1 , 2, 3}, {a, b, c})
× × × × × × × × × × × × × × × 2 × × × × × × × × × × × × × × × 3 × × × × × × × × × × × × × × × α β γ δ ζ
Fig. 7: Another 3-context producing a member of B 3,3 with six objects.

The Counter-Curse of Dimensionality

A natural question one can ask themself about such structures as lattices and n-lattices is their maximal size. As discussed in the previous subsection, n-contexts in which a dimension is as big as the sum of all the others can contain an extremal n-lattice, the size of which is known. The question remains open for all other n-contexts.

Given an n-context (S 1 , . . . , S n , R) with dimensions of equal size s, how many nconcepts might that context contain, at most? We call that number f n (s). In this section, we discuss this question, first in the bidimensional case where it is already elegantly solved, and then in the general case where it is not. The state of the art on this question is presented in Fig. 11, at the end of the section.

All is Clear in 2 Dimensions

It is well known that 2-lattices with 2 s elements -powerset lattices, or Boolean lattices -can be constructed from 2-contexts of size s × s, (2-)contranominal scales. The 2contranominal scale with s objects and s attributes is denoted N c 2 (s). An example of N c 2 (4) and its concept lattice is shown in Figure 8. In [START_REF] Albano | Why Concept Lattices Are Large: Extremal Theory for Generators, Concepts, and VC-Dimension[END_REF], Albano and Chornomaz show that not only do 2-dimensional contranominal scales N c 2 (s) give rise to powerset lattices, but that they are the sole culprit in the large size a concept 2-lattice can have. A large 2-lattice has as standard context a context in which lurks a large contranominal scale. In their paper, Albano and Chornomaz quantify exactly what large means in both its uses.

a b c d a × × × b × × × c × × × d × × ×

General Case: What About Dimension n?

First, we can identify a naive upper bound on the maximal number of concept in a ncontext of size s × • • • × s. A n-concept is always uniquely described by (n -1) of its components, and as such (2 s -1) n-1 + n -1 is an upper bound for f n (s).

Before giving a lower bound for f n (s), it is necessary to recall some information on the construction of contexts.

The direct sum of two contexts C 1 = (S 1 1 , . . . , S 1 n , R 1 ) and C 2 = (S 2 1 , . . . , S 2 n , R 2 ) where the S 1 i , S 2 i are disjoint is the context C = (S 1 , . . . , S d , R) constructed in the following way:

S i = S 1 i ∪ S 2 i , ∀i ∈ {1, . . . , n} and R = R 1 ∪R 2 ∪{(x 1 , . . . , x d ) | ∃i, j ∈ {1, . . . , n}, i = j such that x i ∈ S 1 i , x j ∈ S 2 j }.
The number of concepts in C is then the product of the number of concepts in C 1 and in C 2 . This construction is illustrated in two and three dimensions in Fig. 9.

S 1 2 S 2 2 S 1 1 S 2 1 C 1 C 2 C 1 C 2 S 1 1 S 2 1 S 1 2 S 2 2 S 1 3 S 2 3
Fig. 9: Illustration of a combination of concepts under a direct sum of two contexts C 1 and C 2 in two dimensions (left) and three dimensions (right). Any two concepts of C 1 and C 2 -a maroon and a green one -can be extended into a new concept of C -through the gray areas -, thus multiplying their number of concepts.

An empty one-cell n-context C ell = (1, . . . , 1, ∅) gives rise to exactly n n-concepts. Adding together s such empty n-contexts gives rise to the n-contranominal scale N c n (s), that is an n-context of the form (S, . . . , S, R) with R = S \ {(x, . . . , x) | x ∈ S} that has n |S| concepts. This is a lower bound for f n (s).

Those two bounds are identical in two dimensions, but are increasingly distant with higher dimensions.

In Three Dimensions

There is no clear answer yet for the value of f 3 (s). The two bounds discussed in the previous section amount to looking for f 3 (s) between 3 s and 4 s .

The well known triadic contranominal scale and the associated powerset trilattice were studied by Biedermann [START_REF] Biedermann | Powerset Trilattices[END_REF]. Powerset trilattices are presented as a triadic generalisation of powerset lattices, can be constructed from 3-contranominal scales N c 3 (s) = (S, S, S, =) and have 3 s elements. No explicit claim that this class of 3lattices is extremal is made, other than the use of the name powerset 4 .

Although the 3-contexts responsible for powerset trilattices are good generalisations of contranominal scales, the 3-lattices themselves are not that good of a generalisation of the extremal 2-dimensional case, since they are not extremal w.r.t. the size. This is discussed in Section 3.2.

In [START_REF] Bazin | Bounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs[END_REF], the authors present bounds for the maximum number of 3-concepts in a 3context of size s×s×s. Using a small example of a 5×5×5 3-context that contains more 3-concepts than a 3-contranominal scale and the direct sum of contexts, they provide a construction of arbitrarily large contexts with 3.359 s concepts. Using a measure and conquer approach, they also provide an upper bound of 3.384 s for 3-contexts of that size. The improvement from the naive bounds is represented in Figure 10. Fig. 10: While either naive bounds would be a satisfying answer for the maximum number of 3-concepts in a 3-context, the real answer seems to be in a small corner near 3.36 s .

In Four Dimensions

Now, we extend the work presented in [START_REF] Bazin | Bounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs[END_REF] and provide a lower bound on f 4 (s). The two bounds discussed in the previous section amount, in four dimensions, to looking for f 4 (s) between 4 s and 8 s . Using the same intuition as in [START_REF] Bazin | Bounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs[END_REF], we build a 3 × 3 × 3 × 3 4context where the "holes" are a solution to the chess rook problem in 4 dimensions [START_REF] He Dudeney | The Eight Rooks[END_REF]. This context5 is shown in Table 1.

Using the context C rook depicted in Table 1, we can build arbitrarily large 4-contexts that have c4.82 s concepts, with c a constant.

Let s be a integer greater than 3. Then, there exists two integers k and r such that s = 3k + r, with r ∈ [0, 2]. To build a 4-context C of size s × s × s × s, we add k versions of C rook with the aforementioned procedure, and then add a 4-dimensional contranominal scale of size r. The resulting context has 4 r ×4.82 s-r = ( 4 4.82 ) r ×4.82 s concepts. By setting c = ( 4 4.82 ) 2 , we have that f 4 (s) ≥ c4.82 s .

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3

1 × × × × × × × × × × × × × × × × × × 2 × × × × × × × × × × × × × × × × × × 3 × × × × × × × × × × × × × × × × × × 1 2 3 1 2 3 1 2 3 1 2 3
Table 1: This is a 3 × 3 × 3 × 3 4-context that we call C rook . Empty cells are coloured blue for readability. This 4-context has 112 4-concepts. This amounts to around 4.82 3 concepts. This is, just as in the three dimensional case, a solution to a multidimensional chess rook problem.

Summary

Figure 11 summarises the known results related to the size of n-lattices, taking into account the contexts from Section 3.2 and Section 4. (2 s -1) n-1 + n -1

Fig. 11: "Old Tom Bombadil is a merry fellow! Bright Blue his jacket is, and his boots are yellow!". In the general case, we do not really know where the maximum number of n-concepts lives. This uncertainty is represented here by a dancing Tom Bombadil. This figures summarizes the known bounds for f n (s). In two dimensions the bound is well known and reachable, in three dimension the gap is small.

Fig. 2 : 2 C-→ A 2 1 A-→ C 2

 22212 Fig. 2: Transformations C ({greek},{numbers,latin}) (top), C {a} (bottom left) and C {1,3} (bottom right) of Fig. 1's triadic context C.

Fig. 3 :

 3 Fig. 3: Two formal contexts ({α, β, γ}, {1, 2, 3}, {a, b, c}, R 1 ) (left) and ({α, β}, {1, 2, 3}, {a, b, c}, R 2 ) (right) and their associated 3-concepts.

  's contexts, the implications {(1, b), (1, c)} → {(1, a)} and {(2, a)} → {(3, a)} are structural while {(2, b)} → {(1, a)} is contextual in both contexts and {(1, b), (2, a)} → {(3, a),

  a b c a b c a b c a b c a b c a b c 1

Fig. 5 :Fig. 6 :

 56 Fig. 5: 3-context and 3-concepts of a concept 3-lattice in B 3,3 .

Fig. 8 :

 8 Fig. 8: The contranominal scale N c 2 (4) and its associated 2-lattice, a tesseract (only the extents are represented).

2 s log 2 2 2 s - 1 | 2 s

 12 log 2 n

  where A and B form a bipartition of the set of all dimensions and ((s a1 , . . . , s a k ), (s b1 , . . . ,s b l )) ∈ R (A,B) iff (s 1 , . . . , s n ) ∈ R with {a 1 , . . . , a k } ∪ {b 1 , . . . , b l } = {1, . . . , n} -C D = (S 1 , . . . , S d-1 , S d+1 , . . . , S n , R D ),where D ⊆ S d and (s 1 , . . . , s d-1 , s d+1 , . . . , s n

In[START_REF] Biedermann | Powerset Trilattices[END_REF], the name powerset trilattice is justified by some algebraic properties of the powerset trilattice.

A data file containing the complement of this contexts (its holes) is available at http:// giacomo.kahn.science/resources/Crook.dat


Etienne Jacquemart

Nicolas Combes

Guillaume Duthoit

Francis Bessière

Magalie Ladouceur

Laurence Iserin

Mikael Laredo

Charlène Bredy

Alice Maltret

Sylvie Di Filippo

Cardiac Resynchronization Therapy in Congenital Heart Disease Patients with Systemic Right Ventricle

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.