Kassem Saied
email: kassem.saied@liu.edu.lb.

Ali Chamas

Al Ghouwayel
email: ali.ghouwayel@liu.edu.lb.

Emmanuel Boutillon Senior
email: emmanuel.boutillon@univ-ubs.fr.

E Boutillon

Quasi Cyclic Short Packet for asynchronous preamble-less transmission in very low SNRs

Keywords: Frame synchronization, Modulation coding, Demodulation, Short frame, CCSK, Non-Binary Error-Correcting Code. I

come

IoT topic constitutes the center of interest of both academic and industrial sectors [START_REF] Mekki | A comparative study of LPWAN technologies for large-scale IoT deployment[END_REF]. Given that the number of connected devices is in constant increase, the design of the network carrying such IoT connections should be re-considered in order to support such a massive connectivity. In [START_REF] Durisi | Toward Massive, Ultrareliable, and Low-Latency Wireless Communication With Short Packets[END_REF], the authors defined some theoretical principles that govern the optimization of the transmission of control information in short packets. In an ALOHA protocol, the receiver has no information about the time of arrival of the frame. Moreover, low-cost sensor transceivers impose uncertainty on the modulation frequency. Thus, the frame is affected by a frequency offset. The problem of detection of a frame at low Signal to Noise Ratio (SNR) recently received more attention. In [START_REF] Polyanskiy | Asynchronous Communication: Exact Synchronization, Universality, and Dispersion[END_REF], Polyanskiy showed that asynchronism, even with short packets, does not affect the capacity of the channel: it means that classical methods that use coordination for synchronization and collision avoiding are far from the optimum, since the energy used for coordination is lost.

Moreover, the classical frame structure shown in Fig. 1 is also suboptimal since the header does not carry any information. It could be advantageously replaced by interweaved header-dataredundant bits frame structure. In [START_REF] Bana | Short Packet Structure for Ultra-Reliable Machine-Type Communication: Tradeoff between Detection and Decoding[END_REF], the authors study the trade-off between the energy spent for detection and for decoding using the superposition between the message and the preamble.

In [START_REF] Miyashiro | Improved Multiplierless Architecture for Header Detection in DVB-S2 Standard[END_REF], the structure of the Hadamard code of the Physical Layer Signaling item of a DVB-S2 (satellite TV broadcast standard) frame is used to help the detection of a new start of frame. Fig. 1: Classical vs Preamble-less proposed approach model for transmitting a frame.

In this paper, the authors propose to use the modulation presented in [START_REF] Abassi | Non-Binary Low-Density Parity-Check coded Cyclic Code-Shift Keying[END_REF] to transmit short packet without any additional symbol dedicated to detection and synchronization. This "Preamble-less frame" is hereby referred to as Quasi-Cyclic Short Packet (QCSP) frame. It is based on the use of Cyclic Code Shift Keying (CCSK) modulation scheme [START_REF] Wong | Code-phase-shift keying: a power and bandwidth efficient spread spectrum signaling technique for wireless local area network applications[END_REF] [START_REF] Dillard | Cyclic code shift keying: a low probability of intercept communication technique[END_REF] characterized by inherent correlation property that will help the frame detection and synchronization at the receiver side.

To the best of the authors' knowledge, this is the first paper that addresses the detection of short packets without relying on dedicated preamble symbols. This novel approach, that permits to save transmission power and to reduce the channel uses in a packet transmission, will contribute efficiently in the development of the future IoT networks. The key idea is to consider the whole frame composed of only payload symbols as preamble for detection and timing synchronization.

This idea is performed thanks to the cyclic property of the CCSK modulation that allows the design of efficient detection and synchronization algorithms based on the correlation of the received frame with the cyclically shifted versions of a predefined pseudo random sequence. In addition, this CCSK modulation is jointly designed with powerful Non-Binary (NB) forward error correction codes defined over Galois Field GF(q), where q > 2, such as NB-Low Density Parity Check (NB-LDPC) Codes [START_REF] Voicila | Low-complexity decoding for non-binary LDPC codes in high order fields[END_REF], NB-Turbo [START_REF] Liva | Short Turbo Codes over High Order Fields[END_REF] [START_REF] Klaimi | Low-complexity decoders for non-binary turbo codes[END_REF], NB Turbo Product Codes [START_REF] Zhou | Low-Complexity High-Rate Reed-Solomon Block Turbo Codes[END_REF], and NB-Polar codes [START_REF] Mori | Non-binary polar codes using Reed-Solomon codes and algebraic geometry codes[END_REF]. These non-binary codes offer a capability of error correction, thereby enabling a coding gain that allows the transmission at low power. This family of error correction codes has received the attention of considerable number of researchers in the digital communication community because of its good performance with short packet size and/or the high order modulation compatibility [START_REF] Davey | Low-density parity check codes over GF(q)[END_REF]. These codes benefit from better error-correcting performance than their binary counterpart due to their non-binary nature codes that directly mapped on high order modulation avoiding binary marginalization [START_REF] Pfletschinger | Getting Closer to MIMO Capacity with Non-Binary Codes and Spatial Multiplexing[END_REF]. This approach aims to associate the Direct-Sequence Spread-Spectrum (DSSS) technique using CCSK modulation with high-performance and energy-efficient low-rate channel coding techniques, based on advanced NB error correcting codes [START_REF] Abassi | Non-binary coded CCSK and Frequency-Domain Equalization with simplified LLR generation[END_REF].

The main contribution of this paper is the proposition of a practical detection algorithm of QCSP frame in the Additive White Gaussian Noise (AWGN) channel that does not require a priori knowledge on the time of arrival and on the frequency offset. Using the tools of detection theory, the paper derives the mathematical equations to express the probability of miss-detection and the probability of false alarm according to the QCSP structure and the channel conditions. The detection performance of the proposed system is assessed according to the different parameters being described. In addition, this work gives some insights on the synchronization approach and the joint transmission performance (detection and correction probabilities) that could be obtained with QCSP frame.

The rest of the paper is organized as follows. Section II introduces the system model and the detection problem. Section III describes in detail the detection method and the main metric, called score function. Sections IV gives the theoretical model of the proposed algorithm where the expressions of the correlation functions and Probability Density Functions (PDF) are derived.

In section V, the theoretical model is validated through a comparative study with experimental results obtained with Monte-Carlo simulations over complex AWGN channel, and the effect of different parameters that affect the CCSK-based system is discussed. Then, a detection-correction approachis analyzed using detection performance obtained and the estimated Shannon limit for small packet size done by Polyanskiy [START_REF] Polyanskiy | Channel Coding Rate in the Finite Blocklength Regime[END_REF]. A practical example is also given where the NB-LDPC is used as a decoder in the QCSP system. Finally, Section VI concludes the paper. Table I gives the list of operations and acronyms considered throughout the paper. NOTE: The bold case is used for vectors in the sequel.

X j i Sectioning X from index i to j R ∆ (X) Linear right shift of X by ∆ positions L ∆ (X) Linear left shift of X by ∆ positions X Y Hadamard product (term by term product) of X and Y X Y Concatenation of X and Y k=N -1 k=0 V k Concatenation of N vectors V k X, Y Complex
Q 1 () Marcum Q-function f X (x)

II. SYSTEM MODEL

In this section, we present the principle of a CCSK modulation in the context of its association with Non-Binary codes and the system model being considered. Then, we present the effect of the channel at the receiver side when no time and frequency information is available. Finally, we define the detection problem based on signal detection theory.

A. Association of CCSK and Non Binary Codes

Consider a NB code defined over GF(q), q = 2 p , with K symbols of information and a total length N . The code rate of the code is thus R c = K/N and a codeword contains Kp bits of information. Let P (X) be an irreducible polynomial of degree p over GF [START_REF] Durisi | Toward Massive, Ultrareliable, and Low-Latency Wireless Communication With Short Packets[END_REF], then by defining GF(q) as Z q (X)/P (X), it is possible to represent any element s of GF(q) as a binary vector

B(s) = (b p-1 , . . . , b 1 , b 0 ) where s = b 0 + b 1 X + . . . + b p-1 X p-1 .
Replacing X by 2 in this expression makes a bijection between GF(q) and Z q . In the sequel, an element of Z q refers implicitly to an element of GF(q) thanks to this bijection. Note other bijections can be used to map GF(q) to Z q .

As shown in Fig 2, the input of the NB-code is a binary message M of size m = K × p information bits, equivalently K Z q symobls. The encoder generates a codeword C of N GF(q) symbols. Using the bijection between GF(q) and Z q , the codeword C is represented as

C = [c 0 , c 1 , . . . , c N -1 ], with c k ∈ Z q , k = 0, 1, . . . , N -1. (1)
For the goal of DSSS technique, the CCSK modulation uses a pseudo-random binary sequence P 0 = {P 0 (i)} i=0,1,...,q-1 of length q, where P 0 (i) ∈ {0, 1}, with good auto-correlation properties.

The CCSK modulation maps an element s of Z q (which is implicitly an element of GF(q)) to the sequence P s defined as the circular right shift of P 0 by s positions: The CCSK modulation rate can be defined as R m = p/q, and the Spectral efficiency S e (i.e. the number of information bit sent by channel use) is given by S e = R c ×R m = (K ×p)/(N ×q). An example of a mapping is considered in Table II on each of the c k encoded symbols, such that P c k is the circularly right shifted sequence of P 0 by c k positions which corresponds to the GF(q) symbol c k , i.e. the element of Z q . So the CCSK frame F CCSK is defined as the concatenation of N CCSK symbols:

P s = {P 0 (i -s mod q)} i=0,1,...,q-1 . (2)
F CCSK = [P c 0 , P c 1 , . . . , P c N -1 ] = N -1 k=0 P c k , (3)
where represents the concatenation operation. Before transmission, the generated frame F is composed of N × q BPSK symbols, which is then shaped by a half raised cosine filter with oversampling factor O (typically between 4 and 8).

From the CCSK and NB-Code association, the demapping (i.e., demodulation) process is particularly simple [START_REF] Abassi | Non-Binary Low-Density Parity-Check coded Cyclic Code-Shift Keying[END_REF]. The input of a NB decoder can be given as the vector of log-likelihood values L = {L(s) log(P(P s |Y )) } s=0,1,...,q-1 , where Y is a block of length q of the received message y that passes through Gaussian channel, and P is the probability that the transmitted sequence is P s given that the received block message Y . For a given element s ∈ GF(q), L(s) can be expressed as the correlation between the received block message Y and expected message

P s , L(s) ∼ = Y , P s : L(s) ∼ = q-1 i=0 Y * (i)P s (i) = q-1 i=0 Y * (i)P 0 (i -s mod q), (4)
for s = 0, . . . , q -1. Hence, the log-likelihood vector L is the circular correlation between the received block message Y of length q and the spreading sequence P 0 . It can be efficiently computed in the frequency domain as

L = IFFT(FFT(Y ) * FFT(P 0 )). (5)
The value of L can then be shifted so that at least one of its element is equal to zero. It can be using L = L -L(0), or eventually, L = max(L) -L, to get only positive LLR values.

This vector, measuring the reliability of the different possible sequences, is fed directly to the NB-decoder to perform the decoding process expected to correct the errors encountered during transmission. The proposed coding scheme requires only XOR operations to generate the QCSP frame, which is particularly well-suited for very low cost IoT sensors.

To sum up, this concatenation is direct and adds no complexity to the system since the LLRs calculation at the receiver is efficiently performed by FFT and inverse FFT operations. The non-binary codes show great performance for short data packets transmission and no loss of information between the transmitter and receiver because the decoder fully benefits from the temporal diversity of CCSK sequences.

B. Channel model

In this paper, we assume a low cost sensor that sporadically transmits small messages in an ALOHA protocol, i.e., without prior time and frequency synchronization to the receiver. The message is thus transmitted in an unknown time, and affected by an unknown delay (depending on the distance between sensors and receiver) and an unknown (but limited) frequency offset.

It is thus convenient to express the time of arrival of the frame in the local time domain of the receiver.

Let T c and T (in second) be the duration of a chip and a CCSK symbol respectively, such that T = q × T c . The receiver will oversample the incoming signal with O samples per chip. In other words, the clock frequency F e of the receiver Analog Digital Converter (ADC) is equal to as a real x a = t a /T c and by decomposing x a as

F e = O/
x a = k a + r a /O + a , (6)
where k a = x a , the integer part of x a represent the time in number of chips, r a the closest index of the clock cycle within a chip (r a ∈ {0, 1, . . . , O -1}) and a is the residual timing synchronization error (with a ∈ [-1 2O , 1 2O ]). In the sequel, it is considered that the oversampling factor is high enough so a is negligible and can be considered equal to 0. Moreover, we will also assume that by testing in parallel all the O hypothesis of the r a value, we can always manage to set r a equals to 0. In summary, the frame will be received at chip index k a and affected by frequency offset f o .

C. Time and Frequency decomposition

The blind detection algorithm splits the time and frequency domain into a regular grid composed of bins, each bin defined by a time span and a frequency span of size T b and F b , respectively. Thus, each bin corresponds to an arrival hypothesis of the frame with a coarse time and frequency precision. The detection method is used in each bin to assess (hypothesis H1) or not (hypothesis H0) the arrival of a frame within the bin. Let be the number of chips inside the duration T b , thus T b = T c . We will assume the frequency offset f o varies between 0 and F max , thus the number of frequency bins is equal to N F = 2Fmax F b . Note that qT c F b = 1 means that the effect of frequency offset is equivalent to apply a single rotation between first chip of a CCSK symbol and first chip of the next CCSK symbol. It is thus convenient to replace f o by ω o = 2πf o T c q to directly translate the impact of frequency offset in a rotation effect on each CCSK symbol.

Every chips ( ≤ q typically), the last N × q received chips are extracted to form the vector y γ = (y(γ + i)) i=0,1,...,N ×q-1 (γ is thus a time index). Then, at the entry of the ρ th frequency detector, y γ,ρ = y γ E ρ , where E ρ = (e -jρω b n/q ) n=0,1,...,N -1 is computed in order to compensate the frequency offset before entering the detector, with ω b = 2πF b T c q.

Let us consider a frame arriving at chip index k a with a frequency offset f o . By decomposing

k a as k a = γ a + ∆, with -/2 < ∆ ≤ /2 and f o as f o = ρ a F b + f o , with -F b /2 < f o ≤ F b /2,
we can deduce that the frame will be optimally detectable in the bin (γ a , ρ a ) since in this bin, the locally time offset and frequency offset is minimized.

Note that several bins can be activated in case of an effective frame arrival. In that case, the precise determination of the actual bin and the fine time and frequency inside the bin should be processed. Those steps, called synchronization, are not described in this paper, and assumed that they can be optimally performed.

To alleviate notation, the frame y γ,ρ processed at bin (γ a , ρ a ) will be denoted as y defined as

y(n) = e j(ωon/q+ϕ) F (n -∆) + z(n), (7)
where z(n) are independent realizations of a complex Gaussian noise CN (0, σ 2 ) of zero mean and variance σ 2 , ϕ is initial phase offset, with ∆ ∈ {-/2, . . . , /2} and

ω 0 ∈ [-ω b /2, ω b /2].
The frame F (i) is assumed to be zero when i < 0 and i ≥ N q. Without loss of generality, ∆ will be assumed positive, i.e., ∆ ∈ {0, 1, . . . , /2}.

In case of reception of a frame in the optimal bin (hypothesis H1), the base band transmission model is thus a function of 3 parameters: the time offset ∆, the frequency offset ω o and the standard deviation σ of the AWGN.

In case of no reception (Hypothesis H0), the base band transmission model is simply

y(n) = z(n). (8)

D. Detection problem

The detection problem studied in the paper is how to decide, based on the observation of N × q received samples y = y(n) n=0,1,...,N ×q-1 , which hypothesis is achieved.

The problem is to develop a reliable score function (or match filter) S(y) that takes high values when H1 is fulfilled, and low values when H0 is true. Then, for a given observation, it is possible to take a decision by comparing S(y) to a threshold U 0 in order to decide whether a new frame is present (H1) or not (H0). Let us recall some basic notions in detection theory that will be helpful for the derivation of the theoretical model. In detection theory, the detector can give one of the four different cases:

• Miss Detection: P md = P(S(y) < U 0 | H1) takes an erroneous decision by signaling the absence of any frame while a frame in fact exists.

• Correct detection: P(S(y) ≥ U 0 | H1) correctly detects an existing frame (the probability of correct detection is equal to 1 -P md ).

• False alarm: P fa = P(S(y) ≥ U 0 | H0) takes an erroneous decision by signaling the existence of a frame while a frame in fact does not exist.

• Correct Absence: P(S(y) < U 0 | H0) correctly indicates the absence of a frame (the probability of correct absence is equal to 1 -P fa ).

Based on this definition, we obtain:

P fa = +∞ U 0 f H0 (x)dx, P md = U 0 -∞ f H1 (x)dx, (9)
where f H0 and f H1 are the probability density functions of the random variable S(y) given that H0 is true, H1 is true, respectively. Note that when only part of a frame is inside the detector filter, the output S(y) may become greater than U 0 , triggering potentially early or late detection.

Since S(y) is maximised under hypothesis H1, it is natural to consider only this hypothesis in the detection theory study. Note that once detected the synchronization task estimates the real time of arrival of the frame. between P fa and P md . In fact, in a perfect detector, both should be equal to zero to decide perfectly the presence or not of a new frame. In practice, high value of U 0 decreases P fa but increases P md , while low value of U 0 has the symmetrical effect. For example, at threshold value U 0 = 1200 that corresponds to P fa = 10 -4 , the probability of miss detection is approximately P md = 10 -4 . This value increases to P md = 5 × 10 -3 for U 0 corresponding to P fa = 10 -10 . The value of U 0 will be selected according to the system requirements, in the sequel P fa will be set to 10 -6 . We will try to minimize P md by proposing an efficient score function, i.e., a score function that is not computationally intensive to be calculated and allows to have low values of P md . The following sections describe first the proposed score function, then the probability density functions f H0 and f H1 are formally derived as a function of the numerous parameters of the problem: number of frame's symbols N , CCSK sequence P 0 and its length q, signal to noise ratio of the transmission (σ 2 ), time delay ∆ and the frequency offset f o .

III. DETECTION METHOD: DESCRIPTION OF SCORE FUNCTION

This section discusses in details the score function S(y), which is the detection algorithm used to detect the CCSK frame. The received data stream y is split in the filter into consecutive segments or blocks Y k , of length q chips each:

y = y(n) n=0,1,...,N ×q-1 = N -1 k=0 Y k , (10)
where Y k = (y(n)) n=kq,...,kq+q-1 .

Thanks to FFT operations (see ( 5)), a cross correlation is performed between the current block

Y k and the reference sequence P 0 . Let ∆ ∈ [0, /2] as mentioned before, be the time shift (in number of chips) between the effective time of arrival of the frame and the receiver. q, symbols (c 0 , c 1 , c 2 , c 3 ) are associated to the four CCSK sequences (P c 0 , P c 1 , P c 2 , P c 3 ), and a distinct color is associated to each symbol. In vector Y 0 , there are q -∆ chips that are aligned with the first symbol of the received message of the frame, i.e.P c 0 , or the P 0 sequence circularly shifted by c 0 chips. Relatively to Y 0 and because of the delay ∆, the first ∆ chips are null, then the sequence starts at time c 0 + ∆ (mod q) which will be presented at the receiver as another sequence P c 0 +∆ . So q -∆ are aligned with the CCSK sequence P c 0 +∆ . Thus, the correlation vector L k (s) related to vector Y k will give for k = 0, L 0 that has a spike of height q -∆ at index c 0 + ∆ (mod q). Similarly, for vector Y 1 , there are ∆ chips that are aligned with the first symbol P c 0 with an offset of c 0 + ∆ chips (which is the sequence P c 0 +∆ ). Thus, the correlation vector L 1 will have a spike of height ∆ at index c 0 + ∆ (mod q). Moreover, Y 1 contains q -∆ chips aligned with the second symbol of the received message, which gives a spike of height q -∆ for L 1 in position c 1 + ∆ (mod q) (which is the correlation with the sequence P c 1 +∆ and so on).

So, the received block Y k will have q -∆ chips of correlation with the CCSK sequences P c k +∆ and ∆ chips with other sequence P c k-1 +∆ . Y 0 is a special case as it will have q -∆ correlation with the CCSK sequence P c 0 +∆ .

Thus, the Score function can be obtained using a detection filter S(y) of length N acting as forward accumulator:

S(y) = N -1 k=0 max(|L k |). (11)
In the absence of noise with optimized P 0 auto-correlation properties where P s , P s << q for s = s , the filter output gives S(y) = N × (q -∆).

In order to draw benefit from the second maximum shown in Fig 3, it is possible to sum two consecutive correlation vectors before taking its maximum (SC method, for Sum of Correlation).

The score function becomes

S SC (y) = N -2 k=0 max(|L k + L k+1 |). ( 12
)
This method is not studied in the paper due to lack of room, but it is worth mentioning that, compared to the score function S(y), S SC (y) gives a slight improvement of detection capacity when ∆ is closed to q/2, and gives a few dB penalty when ∆ is equal to 0. It is also more sensitive to a frequency offset, since the duration of coherent integration is multiplied by 2.

For a given observation received in presence of AWGN noise, the detector can take a decision whether a frame is present or not by comparing S(y) to a threshold T that is found based on the Probabilities of miss detection and false alarm as discussed in section II.

IV. THEORETICAL MODEL

In this section, we derive the formal performance model of the frame detection algorithm discussed in the previous section. This model allows to avoid costly estimation performance through Monte-Carlo simulation and gives insight to better analyze the impact of each parameter on the detection performance.

A. Correlation Expressions

Let us first express the exact expression of L k (s), see ( 4) for each value of s. Then, we derive the probability law of |L k (s)| with and without signal.

1) Definitions and notations: First, let us define the following associated operators, taking into consideration vectors g = [g 0 g 1 . . . g N -1 ], and h = [h 0 h 1 . . . h N -1 ]:

• Sectioning a vector from index p to q:

g q p = [g p g p+1 . . . g q ].

• Concatenation of two vectors g and h:

g h = [g 0 . . . g N -1 h 0 . . . h N -1 ].
• Linear Right and Left shifts of vector g by ∆ positions:

R ∆ (g) = 0 ∆-1 0 g N -∆-1 0 L ∆ (g) = g N -1 ∆ 0 ∆-1 0
, where 0 ∆-1 0 is a zero vector of length ∆.

• Hadamard product of g and h:

g h = [g 0 h 0 g 1 h 1 . . . g N -1 h N -1 ].
Based on the discussion in previous sections, y defined in ( 7) and ( 10) can be rewritten in vector-operational form as:

y = e jϕ R ∆ (F ) Φ + Z, ( 13
)
where ϕ is the initial phase offset, R ∆ (F ) the delayed CCSK frame by ∆ chips, and Φ = {e j2πfon } 0≤n≤N q-1 a vector representing the effect of frequency offset f o . Z is the complex AWGN vector: Z = Z I + jZ Q , where Z I and Z Q follow Normal distribution N (0, σ 2 2 ). Due to the specific structure of the CCSK modulation (all the sequences are cyclically shifted versions of the reference sequence P 0 ), the delayed Frame R ∆ (F ) in ( 13) can be expressed as:

R ∆ (F ) = 0 ∆-1 0 (P c 0 ) q-∆-1 0 N -1 k=1 (P c k-1 ) q-1 q-∆ (P c k ) q-∆-1 0 . (14)
Finally, the received vector Y 0 can be written as:

Y 0 =e jϕ R ∆ (P c 0 ) Φ q-1 0 + Z q-1 0 , (15)
and Y k , k > 0 as:

Y k =e jϕ L q-∆ P c k-1 + R ∆ (P c k ) Φ kq+q-1 kq + Z kq+q-1 kq . ( 16
)
2) Exact expression of L k (s): Taking into consideration the expression of Y k defined in [START_REF] Abassi | Non-binary coded CCSK and Frequency-Domain Equalization with simplified LLR generation[END_REF] and the linearity property of the scalar product, the correlation L k (s) = Y k , P s can be expressed as

L k (s) = L k (s) -+ L k (s) + + z k (s), (17)
where

L - k (s) = e jϕ L q-∆ P c k-1 Φ kq+q-1 kq , P s = e jψ k ∆-1 n=0 P (n -c k-1 -∆)P (n -s)e j2πfon , (18)
L + k (s) = e jψ k q-1 n=∆ P (n -c k -∆)P (n -s)e j2πfon , (19)
and

z k (s) = Z kq+q-1 kq , P s . (20)
The phase offset ψ k = ϕ + kq2πf o represents the sum of the initial phase shift ϕ and the contribution of the frequency offset f o on the k th received block Y k .

Let us analyze ( 17), ( 18) and ( 19) in particular useful cases.

a) When k = 0, (17) will be reduced to L 0 (s) = L + 0 (s) + z 0 (s). b) When s = c k-1 + ∆, [START_REF] Beaulieu | An infinite series for the computation of the complementary probability distribution function of a sum of independent random variables and its application to the sum of Rayleigh random variables[END_REF] gives

L - k (c k-1 + ∆) = e jψ k ∆-1 n=0 e j2πfon = e jψ - k sin (πf o ∆) sin (πf o ) , (21)
where

ψ - k = ψ k + πf o (∆ -1). c) When s = c k + ∆, (19) gives L + k (c k + ∆) = e jψ + k sin (πf o (q -∆)) sin (πf o ) , (22)
where ψ + k = ψ k + πf o (q + ∆ -1). d) In the particular case where c k-1 = c k = c, when s = c + ∆:

L k (c + ∆) = e j(ψ k +πfo(q-1)) sin(πf o q) sin(πf o ) + z k (s). (23)
e) It is worth adding that when there is no phase and frequency offset (ϕ = 0 and f o = 0), then ( 21), ( 22) and ( 23) give

L - k (c k-1 + ∆) = ∆, L + k (c k + ∆) = (q -∆) and L k (c + ∆) = q + z k (s), respectively.
From the formal expression of L k (s) for any value of s, it is possible to derive the exact probability law of max (|L k |) used to compute S(y) in [START_REF] Klaimi | Low-complexity decoders for non-binary turbo codes[END_REF].

Finally, according to [START_REF]Web site on Non-Binary LDPC[END_REF], z k (s) is the sum of q independent Complex Gaussian Random Variable (CGRV) CN (0, σ 2 ) multiplied by +1 or by -1. Thus, z k (s) is a realization of Complex Gaussian distribution of law CN (0, qσ 2 ).

3) Probability law of L k (s): Under the hypothesis H0 (no signal), the terms L - k and L + k of (17) are null and thus, for each s, L k (s) = z k (s) is a CGRV of law CN (0, qσ 2 ) as defined before.

Under the hypothesis H1 (signal exists), when k > 0, L k (s) = L - k (s)+L + k (s)+z k (s). The first two terms are deterministic. Their sum can be expressed in polar coordinate as L - k (s) + L + k (s) = ρ k (s)e jθ k (s) , and thus L k (s) is a CGRV of law CN (ρ k (s)e jθ k (s) , qσ 2 ). Since we are interested in the absolute value of L k (s), the phase θ k (s) has no impact. The value of ρ k (s) = |L - k (s)+L + k (s)| takes particular values for s = c k-1 and s = c k , as shown in IV-A2.

For the first symbol, when k = 0, L 0 (s) = L + 0 (s) + z 0 (s), and thus ρ 0 (s) = |L + 0 (s)|. In next subsections, the distributions of of the absolute values |L k (s)|, s = 0, 1, . . . , q -1, the absolute value of each of the CGRVs are derived.

B. Probability distributions of |L k (s)| and maximum of |L k (s)|

In this section we discuss the Probability Density Function (PDF) as well as the Cumulative Distribution Function (CDF) of |L k (s)| the absolute value of each of the CGRVs representing the elements of the correlation vector L k (s), s = 0, 1, . . . , q -1, defined in previous section.

Then we derive the PDF of the maximum value of |L k (s)| in both hypothesis H0 and H1. | is a Rician distribution with the following PDF and CDF [START_REF] Beaulieu | An infinite series for the computation of the complementary probability distribution function of a sum of independent random variables and its application to the sum of Rayleigh random variables[END_REF]:

f |L (a,b) (s)| (x) = 2x qσ 2 e (- x 2 +ρ (a,b) (s) 2 qσ 2 ) I 0 2xρ (a,b) (s) qσ 2 , F |L (a,b) (s)| (x) = 1 -Q 1 ρ (a,b) (s) σ q/2 , x σ q/2 , ( 24
)
where x ∈ [0, +∞[, I 0 (z) is the modified Bessel function of the first kind with order zero and This hypothesis will be assumed in the rest of the paper since the sequence P 0 is carefully selected so that s = s ⇒ P s , P s q. In others words, variables z k (s) will be considered as independent to each others. denoted by F M (a,b) is defined as the product of the elementary CDFs of each element given by marginalizing F M (a,b) (x) over all possible couples, i.e.,

Q 1 is the Marcum Q-function.
F |L (a,b) (s)| , s = 0, 1, ..., q -1 F M (a,b) (x) = q-1 s=0 F |L (a,b) (s)| (x) (25
F M k (x) = 1 q 2 (a,b) F M (a,b) (x), (26)
F M 0 (x) = 1 q (b) q-1 s=0 F |L (b) (s)| (x). ( 27
)
The PDF of the maximum value of the absolute correlation vector denoted by f M k can be obtained by taking the derivative of

F M k . f M k (x) = dF M k (x) dx . ( 28
)
The detection filter described in [START_REF] Klaimi | Low-complexity decoders for non-binary turbo codes[END_REF] takes the sum of N maximum values over a window of N blocks Y k . Thus the score function can be expressed as:

S = N -1 k=0 M k . ( 29
)
In the sequel, we will assume that the M k , k = 0, 1, . . . , N -1, are independent and identically distributed random variables with common probability density function f M k . This If N is not too small, the space is explored almost randomly. Thus, the PDF of the random variable S can be defined as the convolution of f M k , k = 0, 1, . . . , N -1:

f S (x) = f M 0 (x) * f M 1 (x) * • • • * f M N -1 (x) = f M 0 (x) * f * (N -1) M k (x), (30)
where

f N -1 M k (x) is the (N -1)-fold convolution power of f M k (x) and x ∈ [0, +∞[.
It is worth mentioning that as the number of symbols N in a packet increases, f S converges to normal distribution according to central limit theorem. Under the hypothesis H1, f S (x) will be denoted as f H1 S (x). 3) CDF and PDF of the Maximum value of |L k (s)| for H0: The distribution of L k (s) when no frame has been transmitted was given as complex GRV CN (0, qσ 2 ). In this case, the absolute value of the complex number L k (s) is a random variable following the Rayleigh distribution [START_REF] Beaulieu | An infinite series for the computation of the complementary probability distribution function of a sum of independent random variables and its application to the sum of Rayleigh random variables[END_REF], where the CDF and PDF of |L k (s)| are given in (31) for x ∈ [0, +∞[:

F |L k (s)| (x) = 1 -e (-x 2 qσ 2 ) , f |L k (s)| (x) = 2x qσ 2 e (-x 2 qσ 2 ) . (31)
Note that (31) is just a particular case of (24) when ρ = 0. The analysis done in section IV-B2 can be applied again. The PDF of the maximum value of |L k (s)| can be obtained by calculating first its CDF,

F M k (x) = q-1 s=0 F |L k (s)| (x) = 1 -e (-x 2 qσ 2 ) q , (32)
for x ∈ [0, +∞[, that is also illustrated in Fig 4, and then finding its derivative f M k (x) such that,

f M k (x) = 2x σ 2 e (-x 2 qσ 2 ) 1 -e (-x 2 2qσ 2 ) q-1 . (33)
Finally, under hypothesis H0 the PDF of the random variable S, sum of M k , can be defined as the convolution of f M k , k = 0, 1, . . . , N -1:

f H0 S (x) = f * N M k (x), (34)
which is the N -fold convolution power of f M k (x).

V. RESULTS AND DISCUSSIONS

The design of the QCSP system relies on the following set of parameters as shown in the theoretical model: Galois field order q, coding rate R c , number of CCSK symbols in a frame N and the time and frequency offsets. In this section, after the validation of the theoretical approach, first we assess the detection performance of the system according to the parameters based on the detection probabilities P md and P fa under low SNRs. Then, we study the effect of the time and frequency offsets in an asynchronized channel on the system performance. After that, a Detection-Correction approach is analyzed based on the detection results obtained and the frame error-correction rates using the normal approximation equation which is used by Polyanskiy in [START_REF] Polyanskiy | Channel Coding Rate in the Finite Blocklength Regime[END_REF] as the definition of maximal achievable coding rate in the finite code-length regime. Finally, a practical example is given using the NB-LDPC as a decoder to minimize the probability of errors due to transmission of the frame.

A. Confirmation of the Theoretical Model by Monte Carlo Simulation

In the previous section we derived the PDFs f H1 S (x) P(X = S(y)| H1) in (30) and f H0 S (x) P(X = S(y)| H0) in (34) over AWGN channel when the CCSK frame exist or is absent, respectively. In order to check the validity of the hypothesis taken to build the theoretical

B. Performance Analysis: Effect of Galois Field Order

In this section we study the effect of the length of the spreading sequence, i. e, the order of Galois Field q. Hereafter, we define set of parameters for generating a QCSP frame and illustrating the effect of q on detection performance:

• Number of information bits: m = 120.

• NB-Code rate: R c = 1/3.

• Threshold value U 0 : is determined for a P fa = 10 -6 as discussed in II-D.

• Perfect time and frequency synchronization: ∆ = 0, w 0 = 0.

Fig 6 shows the simulations results of P md versus SNR for q ranging from 64 up to 4096, and for a U 0 value corresponding to P fa = 10 -6 . For q = 64, P md is plotted for three different values of P fa : 10 -4 , 10 -6 and 10 -10 . As expected, P md increases when P fa decreases, i.e., when the U 0 value increases. As previously discussed, the value of U 0 is selected based on the desired trade-off P fa -P md . This observation is valid for q > 64, but the corresponding curves of P md are omitted for the sake of figure simplicity. As shown, the SNR required to obtain an acceptable P md of the order of 10 -4 is -11.05 dB when q = 64, and decreases as q increases to go down to -25.8 dB when q = 4096. This is a very important result that shows that the proposed detector can operate reliably at very low SNR. P md and P fa can be chosen depending on the target application.

Fig. 6: P md and P fa as function of SNR for a CCSK frame of m = 120 bits, R c = 1/3 and different GF(q) orders, in an ideally synchronized channel. Also, P as in (38) as function of SNR for the same frame.

C. Performance Analysis: Effect of time and frequency offset

The effect of both time and frequency shifts on the detector performance is discussed in this section. We consider a frame of length m = 120 bits over GF(64) with R c = 1/3. We can figure out that the rotation of a CCSK frame during q chips by ω o = π/2 radian degrades the minimum SNR by less than 1 dB, while a half rotation when ω o = π is more than 3 dB. For that, in a case where the frequency offset has the effect of ω o ≥ π/2, several filters, one for each frequency offset hypothesis, needs to be performed in parallel. To reduce the overall complexity, we propose to use a similar method to the one proposed by Akopian in [START_REF] Akopian | Fast FFT based GPS satellite acquisition methods[END_REF] for the detection of a GPS signal. An important result to note is the big effect of the time offset ∆. For ∆ = 0, the minimal SNR required is -11.1 dB. This value increases with the increase of |∆| to attain its maximum value, SNR= -7.35 dB at |∆|= 32. The gap between |∆|= 0 and |∆|= q/2 is approximately 3.7 dB.

With the previous defined system parameters, QCSP frame can be reliably detected at -7.2 dB with time shift up to |∆|= q/2, and frequency offset up to π/2. Following this GF(64) system, we can detect also at minimal SNR by changing the values of time and frequency decomposition (time and frequency span for the grids) that discussed before in II-C. For example, we can work at SNR -8.9 dB by limiting the deviation to q/4 = 16 chips at most, but we need 2 filters in parallel. Another solution can be taken at the side, a detection filter that considered every q/2 instead of = q chips, so the last N q chips are extracted the stream of sample and the maximum time synchronization error will be limited to q/4. Also, at -10.1 dB for example, we can tolerate a deviation of q/8 = 8 at most. For that, it will be necessary to have 4 filters in parallel to guarantee the reliable detection needed or at the receiver side the detection filter is considered every = q/4.

Based on the application requirements we can adjust the system either to work on lower SNR with higher complexity due to the decrease in the time and frequency span, or it will be sufficient to work on the minimal SNR for worst case scenario where ∆ = q/2 and ω o = π/2.

D. Detection-Correction approach and a practical example

At very low SNR, the successful transmission of short frames as targeted by the NB-code and CCSK association in QCSP system is a challenging problem. In fact, the overall joint probability of successful transmission in an asynchronous ALOHA system can be expressed as P = P d × P s × P c/s , where P d the probability of detection of the frame, P s is the probability of correct estimation of the synchronization parameters, and P c/s is the probability of correction of all transmission errors by the NB-code which is conditioned by the synchronization accuracy.

Aiming to maximize the probability of successful transmission, we must maximize the probability of detection, synchronization and decoding. Then assuming perfect synchronization, one gets P = P d × P c . The challenge here is to minimize the energy cost of the frame for reliable transmission for finite frame length. In order to interpret this challenge, we need first to find the minimum CCSK frame length N for a given probability of detection P d , where P d = 1 -P md -P fa . Fig 8 shows the minimum CCSK frame length N q = N × q in chips as function of SNR, for p = 6

(right-most curve) to p = 12 (left-most curve), needed for P md = 10 -4 and P fa = 10 -6 , in an ideally synchronized channel (no frequency and no time offset).

At different SNR values, we can find the minimum size of the code in chips to guarantee target probabilities of detection (P md ≤ 10 -4 and P fa ≤ 10 -6 ) that corresponds to each order of CCSK modulation p. It is worth noticing that a QCSP frame contains at least one CCSK symbol, i.e., q chips. It explains the flat region at high SNRs, where a unique CCSK symbol is able to guarantee both (P md ≤ 10 -4 and P fa ≤ 10 -6 ). Fig. 8: Minimum CCSK frame length in chips, needed for P md ≤ 10 -4 and P fa ≤ 10 -6 , for different p values in an ideally synchronized channel.

On the other side, the maximum achievable coding rate, denoted by R * c , for error correction codes with error probability P (where P c = 1 -P ), can be tightly approximated as in [START_REF] Polyanskiy | Channel Coding Rate in the Finite Blocklength Regime[END_REF] by

R * c ≈ R - V N Q -1 (P ) (35)
where R is the channel capacity (maximum rate achievable in the asymptotic regime), V is the channel dispersion (defined in [START_REF] Polyanskiy | Channel Coding Rate in the Finite Blocklength Regime[END_REF]) and Q -1 the inverse Q function where Q

(x) = 1 √ 2π ∞ x exp -u 2 2
du. We use the above approximation (known as the normal approximation)

as a definition of the maximum achievable coding rate in the finite code-length regime. In [START_REF] Polyanskiy | Channel Coding Rate in the Finite Blocklength Regime[END_REF] the channel dispersion parameter is defined as

V = H 2 (U |Y ) -H(U |Y ) 2 , (36)
where H(U |Y ) is the conditional entropy of the channel input U given the channel output Y , and

H 2 (U |Y ) E Y   - s∈Zq L(s)(log q (L(s)) 2   (37)
where L(s) P(U = s|Y ) as in (4) denotes the conditional probability distribution of U given Y . Hence, H 2 (U |Y ) can be conveniently estimated by Monte-Carlo simulation.

In practice, we fix the NB-Code rate R c in QCSP system to R c = 1/3 so we can use (35) to find the error probability defined as:

P = Q - R * c -R V /N (38)
where R * c = R c = 1/3. Let us consider a QCSP frame over GF(q) with payload of m = 120 bits of information. Also, we assume a perfectly synchronized reception (∆ = 0, ω o = 0). Fig. 6 shows both the evolution of P and P md as a function of the SNR for several values of the Galois Field order q. One can note that, as q increases, detection becomes more problematic than correction.

Finally, as a practical case study, P for q = 6 in Fig. 6 is replaced by real simulation results where the ideal code is replaced by the GF(64)-LDPC code of rate 1/3, m = 120 defined in [START_REF]Web site on Non-Binary LDPC[END_REF].

Two types of decoding algorithm are used: the Belief Propagation (BP) [START_REF] Davey | Low density parity check codes over GF(q)[END_REF] with 50 decoding iterations and the Extended Mean Sum (EMS) with 30 decoding iterations and n m = 20 (see [START_REF] Boutillon | Design of a GF(64)-LDPC Decoder Based on the EMS Algorithm[END_REF] for the definition of the EMS algorithm). The resulting probabilities of error P are given in Fig. 9. This figure shows also the joint effect of miss detection and probability of error of the decoder, giving the overall probability of miss-reception defined as P mr = P md + (1 -P md )P , where P md is obtained with ∆ = q/8 and ω o = 0, and P the probability of error of the EMS-based decoder.

As can be seen, P mr is mainly impacted by P md at SNRs bellow -10 dB, then by P at SNRs higher than -10 dB. It should be noted that the SNR gap between Polyanskiy's bound and actual performance (abeilt perfect synchronization) is bounded by 1.2 dB for FER greater than 10 -5 .

In the general case, finding for a given SNR and a given payload the optimal QCSP structure (code rate, q size) that minimize P mr for a given receiver complexity is still an open problem.

VI. CONCLUSION

The paper proposed a new frame structure called Quasi Cyclic Short Packet for transmission of short packets in low power wide area network. QCSP frame relies on the combination of CCSK modulation and non-binary error control codes. The whole frame can be considered either as a preamble sequence to perform detection and synchronization, or as a noisy codeword to perform the non-binary error correcting process. Thanks to this structure, QCSP frame offers the capability of blind detection and self-synchronization without additional overhead.

A formal performance model of the frame detection algorithm has been derived. This model gave some insight on the impact of each parameter on detection performance according to the QCSP frame structure (size and GF order) and the time and frequency offset. The trade-off between detection performance and correction performance has been presented. Finally, as a case study, it is shown that a QCSP frame over GF(64) with a payload of 120 bits can be received (detection and correction) correctly with frame error rate of 10 -4 at an SNR of -9.75 dB, just 1.2 dB from Polyanskiy bound.

The work will be extended in several directions. First, the synchronization process will be studied and its impact on performance be evaluated (some preliminary results let us predict that synchronization is not a critical issue). Second, the discussion of Detection-Correction approach in section V.D opens an interesting theoretical question on the optimal frame structure to fulfil the requirement of an application with the minimum energy cost at the transmission side. Finally, the paper deals only with the AWGN channel, future work will extend the study to multipath channels.

To conclude, we believe that QCSP scheme can be useful in many applications. It could challenge existing solutions such as LORA, SIGFOX of NB-LTE solutions in a low power wide area network. It could be also used to establish a communication link in an ALOHA protocol between a terminal and a communication infrastructure (constellation of low earth orbital satellites, base station of a mobile network, etc).

  scalar product between X and Y Px Probability of an event x U 0 Detection Threshold x represents the greatest integer less than or equal to x I 0 () Modified Bessel function of the first kind of order zero

Fig. 2 :

 2 Fig. 2: CCSK-based System Model

  T c , with O the over-sampling factor (typically between 4 up to 8). Indexing the time by duration T c of a chip (i.e. O clock cycles), it is possible to determine the time of arrival t a

Fig 5 (

 5 Fig 5 (a) illustrates three different threshold values that correspond to various probabilities of false alarm P fa = 10 -4 , 10 -6 and 10 -10 versus the output of the correlation filter over a Gaussian channel. It can be clearly inferred from Fig 5 (a) that the threshold value U 0 allows a trade-off

Fig. 3 :

 3 Fig. 3: Illustration of frame detection principle

1 )

 1 PDF and CDF of the absolute value of L k (s), |L k (s)|: The dependency of |L k (s)| on the index k > 0 depends only on the couple (c k-1 , c k ). It is thus convenient to replace k by the couple (c k-1 , c k ), or simply by (a, b) to lighten notation. With this notation, L (a,b) (s) is CGRV of law CN (ρ (a,b) (s)e jθ (a,b) (s) , qσ 2 ), where ρ (a,b) (s) and θ (a,b) (s) are the module and the phase of L - (a,b) (s)+L + (a,b) (s), respectively. Thus, |L (a,b) (s)

  For a given couple a = c k-1 and b= c k , F |L (a,b) (s)| (x) is plotted in Fig 4 for s = c k-1 + ∆, s = c k + ∆ and the other q -2 cases when s = c k-1 + ∆, s = c k + ∆.2) PDF and CDF of the Maximum value of |L k (s)| for H1: Let us define our first hypothesis of the proposed theoretical model. According to[START_REF]Web site on Non-Binary LDPC[END_REF], for any couple (s, s ), we have the intercorrelation E[z k (s), z k (s )] between z k (s) and z k (s ) equal to P s , P s . Since z k (s) and z k (s ) are both Gaussian variables of zero mean, they are independent if, and only if, E[z k (s), z k (s )] = 0.

  Let us first consider k > 0 and let defined M (a,b) as the maximum of the absolute values of L (a,b) (s), i.e. M (a,b) = max{|L (a,b) (s)|, s ∈ GF (q)}. The independence hypothesis of the z (a,b) (s) variables also implies the independence of the |z (a,b) (s)| variables. Thus, the CDF of the M (a,b)

Fig. 4 :

 4 Fig. 4: Illustration of different CDF equations for a given GF(64) received block Y k at SNR=-7 dB, ∆ = 24 chips and ω o = π/4.

  as shown in Fig 4 also. When k = 0, M 0 depends only on c 0 and we can replace the index 0 by the value (b) to be consistent with the previous notation, i.e., M 0 = M (b) . Thus

  is an approximation because two consecutive values |L k (s)| and |L k+1 (s)| are not necessarily uncorrelated since the same c k value is used in both of them. Nevertheless, considering the set of couple L 2k , k = 1..N/2 are thoroughly random, as for the set L 2K+1 , k = 0, ..., N/2 -1.

Fig. 5 :

 5 Fig. 5: MC and Theoretical PDFs in both hypothesis H0 and H1, for a CCSK frame of N=20 symbols in GF(64) for the first scenario (a) SNR = -10 dB, ∆ = 0, no frequency offset and for the second scenario (b) SNR = -10 dB, ∆ = 16, ω o = π/2.

  model, we compare it with the Monte Carlo (MC) simulation, when 10 6 CCSK frames are transmitted, in case of a frame length N = 20 GF(64) symbols over AWGN channel of SNR = -10 dB. Two different scenarios are tested, the first one (see Fig 5.a) assesses perfect synchronization conditions (∆ = 0, w o = 0), and the second case (see Fig 5.b) is considered for ∆ = q/4 and w o = π/2. As we can see in both cases, the probability distribution functions in the theoretical model fit exactly the Monte-Carlo simulation. It is worth noting that in the theoretical modelwe can go through very small numbers in probabilities (here 10 -10 ) without the need to run 10 10 iterations for a MC simulation for transmitting 10 10 CCSK frames for example. Thus, the detection performance can be found through the derived theoretical model without the need to conduct extensive MC simulations.

  Fig 7 plots the minimum SNR needed, for predefined probabilities (P fa = 10 -6 and P md = 10 -4 ), as a function of temporal offsets ∆ for different frequency offsets ω o .

Fig. 7 :

 7 Fig. 7: Minimum SNR required as function of different ∆ and ω 0 values, for defined probabilities (P fa = 10 -6 and P md = 10 -4 ), in a CCSK frame of q = 64, m = 120 bits and R c = 1/3.

Fig. 9 :

 9 Fig.9: Joint frame error rates due to P , P md and to P fa = 10 -6 for m = 120, R c = 1/3 and GF(2 6 ).

TABLE I :

 I Notations

		Operations
	GF(q)	Galois Field of order q
	P 0	Pseudo random binary sequence
	FFT/IFFT	Fast Fourier Transform and Inverse FFT
	N (µ, σ 2 )	Normal distribution of mean µ and variance σ 2
	CN (µ, σ 2 )	Complex normal distribution of mean µ and variance σ 2
	mod	modulo operation
	max(X)	Maximum element in the vector of real elements X
	|X|	Absolute value of X
	X

*

Conjugate of vector X.

  over Z 8 . The CCSK modulation is constructed from a basic sequence of length 8 with P 0 = {11101000}. Then CCSK modulation is applied

TABLE II

 II

		: CCSK codes of GF(8)
	c k ∈ Z8 CCSK sequence P k
	0	11101000
	1	01110100
	2	00111010
	3	00011101
	4	10001110
	5	01000111
	6	10100011
	7	11010001

ACKNOWLEDGMENT

The research leading to these results received funding from the French National Research Agency ANR-19-CE25-0013-01 within the frame of the project QCSP (website: https://qcsp.univubs.fr/).

The authors would like to thank Cédric Marchand and Camille Monière for their corrections and suggestions. A special thank to Valentin Savin for his explanation on the Polyanskiy's bound and to Xavier Giraud for his early reading of the paper and his nice formalism's suggestions.


Julien Broisin
email: julien.broisin@irit.fr

Clément Hérouard
email: clement.herouard@ens-rennes.fr

Design and evaluation of a semantic indicator for automatically supporting programming learning

Keywords: Programming learning, Semantic analysis, Educational data mining, Edit distance, Levenshtein algorithm

for the acquisition of 21st century skills, which include programming learning. In France, for example, an educational reform of High School curricula that will be operational next year offers a Digital and Computer Science option that includes more than 350 hours of programming learning. This interest in integration of programming learning skills early in the curriculum requires not only prepared teachers, but also technological solutions to support them and their students in their daily practices.

With this purpose, the Technology-Enhanced Learning research community has been interested in designing systems dedicated to support learning of programming, as evidenced by different efforts intended to analyze learners' behaviour [START_REF] Spacco | Analyzing student work patterns using programming exercise data[END_REF][START_REF] Sharma | Identifying styles and paths toward success in moocs[END_REF]. One of the most common approaches in prior works consists in designing systems that analyze learners' programming codes from a syntactical perspective. These systems make a syntactic evaluation of students' codes to detect grammatical errors and provide appropriate and constructive support to learners to avoid misconception errors [START_REF] Taherkhani | Beacon-and schema-based method for recognizing algorithms from students' source code[END_REF]. However, delivering feedback about syntactical errors falls short on providing meaningful information about how students approach the programming problem. Yet, one of the key learning outcomes of programming relates to the development of an individual's ability to solve a problem [START_REF] Saeli | Teaching programming in secondary school: A pedagogical content knowledge perspective[END_REF]. One approach to achieve this goal is to design systems able to analyze source codes from a semantic perspective, i.e., able to show how the problem has been solved. Although there have been some initiatives approaching code evaluation from a semantic perspective [START_REF] Bey | A comparison between two automatic assessment approaches for programming: An empirical study on moocs[END_REF], works on this line are still scarce and very few solutions have been proposed. Thus, more solutions based on semantic analysis are needed to better understand the potential of this approach in supporting learning of programming.

To advance on semantic analysis-based solutions, this article introduces the design of an indicator revealing the semantic proximity of two distinct source codes in order to express the correctness of a learner's code regarding a given problem, and tackles the following research questions: Research question 1: How to design a semantic indicator revealing learner's ability to solve a problem? Research question 2: Is the semantic quality of a learner's production correlated with his/her academic performance?

To answer the first question, we adopt an approach based on the comparison of abstract syntax trees. We adapt the edit distance established by Levenshtein, an algorithm that ABSTRACT How to support students in programming learning has been a great research challenge in the last years. To address this challenge, prior works have mainly focused on proposing solutions based on syntactic analysis to provide students with personalized feedback about their grammatical programming errors and misconceptions. However, syntactic analysis falls short on informing learners how they solve the programming problem, even if one key learning outcome of programming relates to the development of an individual's ability to solve a problem. In this article, we introduce an indicator to analyze beginners' code based on semantic proximity. This indicator adapts an edit distance algorithm (i.e., the Levenshtein distance) to express the proximity of the students' code with the expected solution provided by the teacher, in order to express the learners' capacity to solve the given problem. To process our indicator, we applied ma-chine learning techniques to a dataset from an introductory programming course with a sample of 166 students. The first results are encouraging. On the one hand, the semantic indicator can be used to automatically classify source codes as semantically correct or incorrect in 58% of the cases. On the other hand, the indicator is correlated with teachers' summative evaluations of students' codes. Even if further investigations must be conducted to improve the indicator's accuracy, the results of this study make it possible to use our approach as the foundations for future research in semanticbased intelligent and awareness programming systems.

INTRODUCTION

Computer literacy is currently booming. In Europe, particularly in Germany and the United Kingdom, profound educational transformations have been initiated since 2016 to promote digital learning in schools and prepare learners has proven effective in comparing and correcting strings of characters. Then, we propose a machine learning method to determine some of the factors required to process the semantic proximity using source codes produced by 166 students. For the second research question, and with the objective of evaluating the precision of the indicator in relation to human perception, we conduct a set of statistical analysis with source codes gathered from an authentic learning context. In particular, we analyze the correlation between the value of our indicator automatically processed, and the teachers' scores manually assigned to students' source codes.

In the following section we review what current approaches dedicated to automatic source code analysis are currently available in the literature, and highlight a lack of semanticdriven proposals. Then, in Section 3, we present how the semantic indicator was designed; as stated above, the indicator stands on the Levenshtein distance adapted to source codes comparison, and depends on a set of parameters leading to its calculation. Section 4 then introduces the machine learning method we used to assign values to these different parameters, whereas Section 5 describes the dataset used to actually determine the values of the parameters. Section 6 gives the results we obtained, and evaluates the quality of the indicator at two different levels: its capacity to act as a semantic classifier, and its correlation with human perception. Finally, we discuss the results of this study as well as the main conclusions of the work.

APPROACHES FOR AUTOMATIC SOURCE CODE ANALYSIS

In the context of programming learning, automatic source code analysis is used to achieve different objectives such as improving feedback provided to learners [START_REF] Denny | Enhancing syntax error messages appears ineffectual[END_REF][START_REF] Karam | Assisting students with typical programming errors during a coding session[END_REF], predicting their performance [START_REF] Ahadi | Performance and consistency in learning to program[END_REF][START_REF] Watson | Predicting performance in an introductory programming course by logging and analyzing student programming behavior[END_REF], or monitoring their activities [START_REF] Alammary | Implementation of a smart lab for teachers of novice programmers[END_REF].

These automatic analyses are performed by compiling the code [START_REF] Carter | A tutoring system for debugging: status report[END_REF], by searching for typical errors within a source code [START_REF] Karam | Assisting students with typical programming errors during a coding session[END_REF], or by running unit tests provided by teachers [START_REF] Sharma | Evidence for programming strategies in university coding exercises[END_REF]. These various works guide learners in the production of syntactically correct programs, but they do not allow the source code to be evaluated at a semantic level: syntactic evaluation is not sufficient to reflect the relevance of a learner's production regarding a problem given by the teacher.

In the meta-review proposed by Ihantola et al. [START_REF] Ihantola | Educational data mining and learning analytics in programming: Literature review and case studies[END_REF] who studied no less than 118 research articles in the field of educational data mining for programming, the word semantics is missing from the paper. Also, a search for the terms "semantic analysis programming" in Google Scholar and Web of Science returns a large number of results, but no scientific articles really deal with semantic analysis of code.

The works we have identified that are close to a semantic analysis are those proposed by Bey et al. [START_REF] Bey | A comparison between two automatic assessment approaches for programming: An empirical study on moocs[END_REF]. In order to propose an automated assessment of learners' code in a Massive Open Online Course (MOOC), the authors propose to compare the control flow graph matching with the code produced by the learner, with a set of graphs stored in a database and manually assessed by experts [START_REF] Aiouni | An automated assessment tool of flowchart programs in introductory programming course using graph matching[END_REF]. If the learner's graph is recognized among the graphs of the database, then the matching score is returned to the learner; if it is not recognized, then the learner's production is manually assessed by a human expert to enrich the database of graphs.

The lack of work addressing automatic analysis of source code from a semantic perspective can be explained by the fact that the semantics of a program can not be calculated.

Our research try to go beyond this limitation and propose the design of an indicator that reveals the relevance of a source code regarding a given problem.

SPECIFICATION OF THE SEMANTIC INDICATOR

Our objective is to design an indicator able to evaluate the distance between two source codes from a semantic perspective and fulfilling the following requirements: (i) teachers should only produce a solution to the problems delivered to students, in contrast, for example, to methods based on unit tests which are time consuming; (ii) the distance should decrease as the student approaches the solution, so that an incomplete script can be evaluated even if it does not fully address the problem posed. Therefore, if the solution of a problem is provided by the teacher, then the distance between this source code and the learners' productions should give insights about their ability to solve the problem.

The field of natural language processing has for a long time studied problems related, for example, to spelling correction where semantics is naturally taken into account [START_REF] Beijering | Predicting intelligibility and perceived linguistic distance by means of the levenshtein algorithm[END_REF]. To design our semantic indicator, we studied algorithms capable of processing the edit distance between two sequences of characters, and built our proposal upon the Levenshtein algorithm which has been shown very useful for calculating the distance between two strings of characters.

Levenshtein distance

The edit distance between two strings of characters, or Levenshtein distance [START_REF] Levenshtein | Binary codes capable of correcting deletions, insertions, and reversals[END_REF], is defined by a cost calculated from the minimum number of operations (i.e., insertion and deletion of a character, and substitution of one character by another) required to move from one string to another. In the case of character strings comparison, the costs associated with each of these operations are all set to 1, but the cost of the substitution of a character by itself which is 0. To apply this algorithm to source code, two challenges must be tackled: (i) the design of a formal representation of the source code in order to make it comparable at a high abstraction level, and (ii) the assignment of a specific cost to each elementary operation according to the importance of the modifications to be made to move from one source code to another. Indeed, substituting two instructions implementing the same functionality should not have the same cost than replacing an instruction with another one characterized by a very different functionality.

Formal representation of source code

Our proposal for building a formal representation of source code relies on two steps: transformation of the source code as an Abstract Syntax Tree (AST), and transformation of the AST into a string of elementary instructions.

Production of the abstract syntax tree

We have adopted abstract syntax trees to formally represent a source code as they do not represent nodes and branches that do not affect the semantics of a program. We rely on a parser written in JavaScript that reads a script and returns the matching abstract syntax tree formatted as a JSON object; an example illustrating the conversion of a Bash source code to an AST is given in Figure 1.

With the formal representation proposed above, the measurement of our indicator corresponds to the edit distance between two abstract syntax trees. However, in order to adapt Levenshtein distance to our context, we need to convert the AST generated from the source code into a string of characters; from a terminology point of view, we name tokens the characters resulting from the AST transformation process so as not to confuse them with those contained in the source code. Thus, we carry out an in-depth exploration of the AST to create the string of tokens.

Production of the string of tokens

The Bash language, the subject of our study, proposes 17 control structures, each corresponding to a different token. The Levenshtein distance between two strings of tokens is therefore characterized by a number of costs, or parameters, matching with the different elementary operations of insertion, deletion and substitution of each token. The 17 tokens of the Bash language lead to the definition of 308 costs: 17+17 costs to create and delete a token, 16x17 costs to substitute one token by another, 1 cost to substitute a token Command by another characterized by a different command name, and finally 1 cost to substitute a token Command by another characterized by identical names and different arguments. This number of parameters is too high to implement an effective machine learning method, as it decreases the density of tests and makes more difficult the search for "good" values of parameters.

Reduction of the number of parameters

A first operation to reduce the number of parameters to be trained consists in ignoring the tokens Until, Subshell and Pipeline because the matching control structures do not appear in the dataset used for this study (see Section 5).

We also propose to symmetrisize the problem by assigning equal costs to the insertion and deletion operations of a token; similarly, the substitution of the token A by the token B has a cost equal to the substitution of B by A. This symmetrization makes the distance between the scripts S1 and S2 equal to the distance between S2 and S1, and reduces the number of parameters to 107.

Finally, we assume a stronger hypothesis by considering that only certain tokens can replace others. Thus, only the following groups of tokens can substitute each other: {Command, Assignation}, {If, Case}, {Then, Else, CaseItem}, and {For, While}. Indeed, it is possible that a script contains a Case where another script uses a If, but it is unlikely that a substitution of a For by a If appears frequently, these two instructions having very different objectives.

These simplifications considerably reduce the number of costs, since 23 parameters must now be calculated. Let us note θ the vector containing these 23 costs. Our indicator, noted d(S, C, θ), is then defined by the edit distance, under the 23 parameters θ, between the string of tokens representing the script S and the one matching with the script C. The next section introduces the machine learning criterion leading to the optimal values of θ.

MACHINE LEARNING METHOD

To train the correct values of the 23 costs of the θ parameter, we define the machine learning criterion Score(θ) to be minimized such that:

Score(θ) = (S,C)∈Correct d(S, C, θ) (S,C)∈Incorrect d(S, C, θ) (1)
where Correct (resp. Incorrect) is the set of pairs composed of the correct (resp. incorrect) scripts of the learning dataset (see next section) and the associated corrections.

The Score function is low when the correct scripts are associated to short distances, and the incorrect scripts to long distances. We add the square roots of the distances to reduce the influence of high values.

We can notice a property of the function d:

∀λ ∈ R * + , d(S, C, λ.θ) = λ.d(S, C, θ) (2)
Then it is obvious that Score(λθ) = Score(θ). This means that the Score function is constant on all rays from 0, and that exploring the different costs of the θ parameter, noted θi such as 0.01 < θi ≤ 1, is sufficient to find the values of θi minimizing Score. The dataset built from an authentic learning situation and that was used to determine the θi is described in the next section.

DATASET FOR CALCULATING COST

The dataset was obtained in an IT department of Higher Education Institute of Technology (HEIT) during an introductory course on Bash programming attended by 166 first year students. Learners discover common commands such as echo, ls, read or cat, variable management, as well as some control structures of the Bash language (e.g., for, while, if, case). Students then put these concepts into practice during hands-on sessions where they produce Bash scripts to try to solve a series of problems.

The dataset includes the students' scripts produced during five practical sessions of one hour and a half. Each time a student saves the modifications of her Bash script, a copy of the script together with its timestamp and the identifier of the student is saved in a directory to enrich the dataset. Thus, our sample includes 19232 scripts. However, a number of nomenclature errors or file numbering made 18% of these scripts unusable: the dataset is composed of 15794 scripts.

This sample includes, for the same exercise, several scripts produced by the same student. However, machine learning methods are effective when they are based on independent data. We thus only consider, per exercise and per student, the last script produced by the learner because we assume that it is the most complete. This choice allows to obtain an independent dataset, but reduces the sample to 2540 scripts.

Finally, we want to be able to manually classify each script of the dataset into two distinct categories (i.e., Correct and Incorrect) expressing their semantic accuracy, in order to evaluate the accuracy of our indicator as a semantic classifier (see next section). However, some exercises suggested by the teachers of this course do not allow for a semantic analysis of students' productions. For example, some problems are related to the understanding of the execution of a script provided in the statement, while others have instructions that are too open to assess whether a script represents a solution to the problem. After this classification process, the final sample includes 733 scripts spread over 11 different exercises; 397 scripts are semantically correct, the others being semantically incorrect.

This dataset was randomly divided into a learning dataset whose objective is to identify the values of the θ parameter that minimize the machine learning criterion, and a test dataset that aims at evaluating the relevance of the results obtained during the machine learning phase. These two samples contain the same number of scripts for each exercise, and the proportion of semantically correct and incorrect scripts is preserved. In addition, let us note that a solution was provided by a teacher for each of the exercises.

RESULTS AND EVALUATION 6.1 Values of costs

The learning dataset was used to initialize the gradient descent minimization algorithm. The vector minimizing the Score function, noted θ, admits values of 0.01 (i.e., the minimum value we have set) almost everywhere except for three parameters: (1) the creation or deletion of a token Command, whose cost is 1; (2) the creation or deletion of a token If, whose cost is 0.112; (3) the creation or deletion of a token Function, whose cost is 0.022.

At this stage, we have the parameter θ which contains the values of the 23 costs that were obtained by our learning method. The objective of the tests conducted in the following section with the parameter θ on the test dataset is twofold: to study the ability of our indicator to distinguish a semantically correct script from an incorrect script ; to study the correlation between our indicator and manual scores assigned to scripts by teachers.

Study of prediction

A first approach to assess the relevance of our indicator under the parameter θ is to evaluate its ability to automatically classify a script as correct or incorrect from a semantics point of view. In a first step, we calculate the distance d(S, C, θ) between each script S of the test dataset and the correction C of the matching problem, in order to obtain a value of our indicator for each correct and incorrect script.

The next step consists in evaluating the prediction model resulting from the different values of the indicator. To do this, we use the ROC metric, which is widely used to observe the performance of a binary classifier. When the classifier calculates a metric m that is compared to a σ threshold to predict the class, the idea of the ROC curve is to vary σ from 1 to 0 and, for each σ value, plot the false positive rate on the abscissa and the true positive rate on the ordinate. The area under the curve (AUC) then indicates the probability that the classifier will place a positive in front of a negative. A classifier that is never wrong has an AUC equal to 1, while a random classifier has an AUC equal to 0.5.

In our study, if d(S, C, θ) < σ, then the script is classified in the category Correct ; otherwise it is classified in the category Incorrect. The ROC curve in Figure 3 illustrates the ratio of true positives (i.e., fraction of correct scripts that are actually detected as correct by the classifier) according to the ratio of false positives (i.e., fraction of incorrect scripts that are detected as correct by the classifier). The curve is moderately above the bisector, the area under this curve is equal to 0.585. Our classifier is therefore slightly better than a random classifier, but its performance is not very high; we make assumptions to explain these results in Section 7.

Study of the correlation with human notation

One of the objectives of our indicator is to reflect the learner's progress towards the solution to the problem, which means that its value is assumed to decrease as a script moves towards the solution. We therefore study the correlation between the value of our indicator under the parameter θ for a given script and the matching correction, and the score assigned to this script by a human tutor.

This study is performed using a second dataset obtained after the final exam of the course described in Section 5. Of the 166 students enrolled in this course, 163 participated in the final exam where learners had to produce a script addressing a given problem. A teacher then assigned a score out of 10 to each of the 163 scripts. After eliminating grammatically incorrect scripts, this second dataset comprises 105 scripts.

Figure 4 shows, for each script, the value of the indicator according to the score assigned by the teacher. This graph shows a negative correlation: the (non-linear) Kendall correlation has a value equal to -0.319 (p value less than ). We therefore have a correlation between the score given by a human tutor and the value of our indicator. This correlation is not extremely high, but it may be sufficient to automatically estimate a student's progress towards solving a problem.

DISCUSSION

Our indicator is able to distinguish a semantically correct script from a semantically incorrect script, but its performance is slightly better than that of a random classifier only.

A hypothesis to explain these results stems from the heterogeneous nature of the learning dataset, especially regarding the size of the scripts it contains. Indeed, the distance calculated by our indicator tends to increase with each token of a script. So the longer a script is, the more likely it is that the indicator will return a high value (even if the script approaches the solution), while a short and incorrect script is evaluated with a low value due to the low number of tokens.

The correlation study carried out on the second set of data gives indications about a certain capability of generalization of our approach. Indeed, unlike the test dataset extracted from the first dataset, the set of scripts obtained after the terminal exam corresponds to an exercise that is missing from the learning dataset. Therefore, our method seems to apply to exercises that were not used during the learning phase. However, this correlation is not extremely high, and scripts that are very poorly evaluated by human tutors are assigned a value of our indicator that is almost zero. This can also be explained by the hypothesis formulated above, since almost empty and therefore incorrect scripts are poorly rated by the human teacher, while our indicator returns a low value. Tests should be carried out to investigate how to adjust the algorithm to process the indicator, in particular according to the number of tokens comprised in the script representing the solution to the problem.

Developments have been initiated to return this indicator to learners during the programming activity. A first visualization reflects, as a graphical gauge, the value of the indicator each time a learner executes a script. A second visualization shows the learner's progress in solving the problem from the successive values of the indicator for the same script; it gives the variation of the indicator in the form of a gradient of colors ranging from green (for a short distance) to red (for a long distance). The student is thus provided with a real time and easy to interpret view of the evolution of the accuracy of his script from a semantic point of view. These tools to support learners will be experimented in the next academic year with a new group of first-year students from HEIT. This experimentation will also make it possible to repeat the work presented in this study using a new dataset, and thus to improve the quality of our indicator.

CONCLUSION

In this paper, we conducted a study to design an indicator whose objective is to act as a foundation for intelligent guidance systems and awareness tools intended for both learners and teachers during a practical activity dedicated to learning programming. While a large variety of research is focused on the syntactic quality of the code produced by learners to support these learning activities, our originality lies in studying the semantic quality of the code, i.e., in evaluating the degree to which a program solves a given problem.

Thus, our main contribution relates on the design of an indicator that reflects a learner's ability to solve a problem.

To answer the first research question asked in the introduction, we adapted the Levenshtein distance: from two strings of tokens representing the abstract syntax tree of the corresponding programs, the indicator returns an estimated value of the edit distance between the two scripts. To train and test this indicator, we used a dataset composed of scripts produced by students in authentic learning situations. The tests revealed that when it comes to differentiating between semantically correct and incorrect scripts, our indicator has slightly better performance than a random classifier. On the other hand, we observed an inverse correlation between the value of the indicator and the score assigned by a human tutor: the higher the human score of a program formulating a solution to a problem, the smaller the distance between that program and the solution of the problem.

These encouraging results suggest the opportunity to develop new models and tools dedicated to the semantic analysis of programming learning. However, many improvements need to be explored to improve the quality of our indicator.

In addition to big amount of data required to refine the parameters of our indicator, the generalization of our approach to different programming languages must be checked, as well as the consideration of more complex programs.

  A token can be of the type Command, of the type Assignation, or of the type While, Do or Done to indicate the beginning, body or end of a loop respectively. Note that the tokens Command keep the name of their command and arguments.The transformation of the AST represented in Figure 1 into a string of tokens is illustrated in Figure 2.

Figure 1 :

 1 Figure 1: Converting a source code into an abstract syntax tree.

Figure 2 :

 2 Figure 2: Converting an abstract syntax tree into a string of tokens.

Figure 3 :

 3 Figure 3: ROC curve of our classifier (in blue) and random bisector (in red).

Figure 4 :

 4 Figure 4: Value of our indicator according to score assigned by a human tutor.


Cornelis Jacominus Van Der Beek

Panayotis Spathis

Feng Yang

Sylvain Colson

Piotr Gierlowski

Takasada Shibauchi

Yuji Matsuda

Marat Gaifullin

Ming Li

Peter H Kes

Disorder and c-axis quasiparticle dynamics in underdoped Bi2Sr2CaCu2O8

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