Y El Basri
email: yelbasri@laas.fr

M Gaetani-Liseo

C Carrejo

A Ramond

M Bressan

C Alonso

Study of DC-DC output serial connection for photovoltaic distributed systems

We present a study of work limits for two dc-dc converters associated in series. This type of structure is usually used to maximize the electrical energy production of a photovoltaic system when it is subjected to shading. We expose our study to research these limitations in the case of expensive shading.

DC-DC converters, series connections, photovoltaic systems, optimal matching in series connections

Study of DC-DC output serial connection ranges for photovoltaic distributed systems EL BASRI YOUSSEF

INTRODUCTION

Research on photovoltaic energy (PV) beyond improvements of cells efficiency have attracting significant attention in the field of power electronics and control algorithms associated in a perspective of maximizing the power generated by the modules. Thus, the development of control laws has recently taken an important place in the innovations made in terms of maximizing efficiency and safing operation. For this, control and electronics have become more complex and multitask. One trend is to approach the electronic interfaces close to the source by discretizing the control power architecture with several different power stages in cascade.

This approach induces research of better managements on differences energies produced. To illustrate our purpose, we have done compared studies on simple cases of connections. A comparison of various possible interconnections between a panel and its charge was proposed in Fig. 1. In the first configuration, PV modules are connected in serial in order to increase the output voltage to one DC-AC converters (Fig. 1.a). This configuration allow decreasing resistive losses, however this solution need the use of a bypass diode [START_REF] Petibon Stéphane | Nouvelles architectures distribuées de gestion et de conversion de l'énergie pour les applications photovoltaïques[END_REF]. That means that if a production between the PV modules is different, the faulty module will be shorted. This strategy prevents the failed module to work in his receiver mode but a part of the production will be lost.

In the Fig. 1.b and Fig. 1.c, the bypass diode is integrated inside on or more micro-converters. Thus the power generated by each generator can be managed independently and therefore high improved. The main difference of this two distributed structure resides in the interconnection of their output. In the case b, the outputs of the micro-converters are connected in parallel and therefore share the same voltage, the total current is the sum of each output current. This configuration has no structural limitation because there is no dependency between the gain conversion stages. However due to a low output voltage and a high current input, the wiring losses will be greater than in the centralized solution. In case c, the outputs are connected in series and this time sharing the same current [START_REF] Alonso | An innovative perturb, observe and check algorithm for partially shaded PV systems[END_REF], [START_REF] Ramos-Paja | A multivariable MPPT algorithm for granular control of photovoltaic systems[END_REF]. However, the output voltage of the power stages is then probable floating generating instabilities as voltage levels obtained. Robust control loops must constantly monitor that there is no drift [START_REF] Orduz | Analytical study and evaluation results of power optimizers for distributed power conditioning in photovoltaic arrays[END_REF]. This finding implies that the gains of the converters are connected. However, the advantage is that the currents are not added, minimizing the Joule losses.

PV models under shadow condition

To well understand the phenomena involved in a moving shadow on the PV modules we use an electrical model of the cells taking into account the Bishop effect that will allow us to represent the inverse characteristic. In sunny conditions optimal voltage V OPT of solar cells have a value between 0.5V and 0.7V. Therefore, the PV modules are most frequently made by connecting the cell in series in order to increase the voltage and facilitate the connection to the grid [START_REF] Protin | Convertisseurs photovoltaïques[END_REF]. Thus cell will add the voltages with the same current flowing through the cells (Fig. 2). In the same principle, even if this configuration is rarely used to scale of the cell it is possible to connect them in parallel to increase the current [START_REF] Caluianu | Photovoltaic energy generation under partially shading conditions[END_REF]. These types of associations can be made without association's difficulty but it is recommended to have very similar electrical cells characteristics to avoid disparity and loss of performance. The serial and parallel photovoltaic cells configurations forming the photovoltaic generator (GPV) have its electrical characteristics which vary across the cell involving a mismatch. In the case of the serial connection, the mismatch limits the current across chain of cells. An occultation of a cell under these conditions creates a significant loss of power. When the difference of current between normal cells and the covered cell is large, the voltage of the cell becomes negative and passes in receiver operation. We must then consider the inverse characteristic of the cell and its avalanche area. Fig. 2.b shows the association of three cells of which is shaded. We can see that for a given current, the shaded cell have its voltage becomes negative and approach the breakdown voltage V BR [START_REF] Caluianu | Photovoltaic energy generation under partially shading conditions[END_REF], [START_REF]Optimisation énergétique de l'étage d'adaptation électronique dédié à la conversion photovoltaïque[END_REF] a

V oc1 N s V oc Ns I SC V oc1 N s V oc Ns I SC V oc1 N s V oc Ns I SC Cell 1 Cell 2 Cell Ns V Cell1 V Cell2 V CellNs V cell x Ns Hidden cell Cell 1 Cell 2 Cell Ns V Cell1 V Cell2 V CellNs V cell x Ns Hidden cell Cell 1 Cell 2 Cell Ns V Cell1 V Cell2 V CellNs V cell x Ns
The photovoltaic cell in the receiving area will heat up and dissipate the excess temperature. This can lead to the deterioration of the cell. In the case where the current supplied by healthy cells allows polarizing the cell at a higher absolute value of V BR , there will be a breakdown of the junction. The length of the chains of cells in a photovoltaic module is defined by this critical case, that is to say, if one cell is in the dark and all the other cells discharge inside of her. We find chains of cells to the silicon modules of about 20 cells for a voltage V BR around-20V. To increase the voltage and thus the number of cells in series, a protection diode is added in parallel for each string in order to bypass the shaded string if the voltage becomes negative [START_REF] Nofuentes | Procedure to carry out quality checks in photovoltaic grid-connected systems: Six cases of study[END_REF], [START_REF] Hasyim | Shadow tolerance of modules incorporating integral bypass diode solar cells[END_REF].

The effect of the bypass diode will result in a discontinuity of the characteristic I PV (V PV ) and did appear in the case of partial shading, two maximum powers (Fig. 2.c). At low voltage (high current), the failed module cannot supply the current and is totally disconnected. At high voltage (low current), the current string is limited by the lowest cell. In the first case, the faulty module does not produce energy, in the second case the faulty module limits the energy of non-shaded modules. This protection solution adopted by manufacturers has several disadvantages, the main ones:

-Creation of several maxima in the characteristic P PV (V PV ) generator, -Power is lost during a shade of one cell of the string, -Power is limited by the hidden cells.

Another protection diode called non-return diode is used to protect GPV against negative currents that could be come from other modules connected in parallel or the load (eg battery). In this case, the voltage is limited by the lowest string causing a loss of power. Fig. 3 present the P(V) characteristic of a PV module composed of two groups, which one of the group is progressively shaded. We observe in the curve 1, the discontinuity due to the bypass diode activation. In curve 2, the power extracted in the case of discrete system. Finally, the distributed architecture is therefore useful when the powers differ between the modules.

Study of converter series connection

We analyze in our study the case of two DC-DC converters where the output is connect in series and then connect to a DC bus Vout (inverter input voltage or battery charger). Fig. 3 shows the schema where the currents Iout1 and Iout2 outputs are equal.

A simple analysis allows us to define the relationship between α1 and α2 as follows:

α α * i i α V !" # α * V (2)
From ( 1) and ( 2), then we find:

α V !" * i * * α V !" * i * * (3)
To define the limits of this interconnection, we perform an analytical study with the following change of variable and using as a reference the converter number 1: In the case of PV application, the variation of the irradiation impact principally the PV current due to the exponential behavior of PV panel according to the PV voltage. In the first approach we will take account just the current variation and fix V in2 =V in1 and therefore C=1.

Fig. 5. Conversion gain between the voltage ratio and the current ratio for Vin1 = Vin2.

Fig. 5 shows a 3D view of α1 and α2 according to A and B. We also represented the passage from the buck mode to the boost mode with the area define by α=1. We could see that there areas define four working zones where this converter operate in : "Buck-Buck", "Boost-Buck", "Buck-Boost" and "Boost-Boost". Thus, from the solution (4)=1 and (5)=1, it is possible to know the limit when the converter switching from the step down mode to the step up mode. Fig. 6 present the resolution evolution when Vin1=Vin2. We find that for Iin1=Iin2 a gain for the two stage equal to the half of the ratio voltage 'A'. In the other hand, if the ratio between the voltages is different (Vin1 ≠Vin2), this characteristic will be moved (Fig. 7), this phenomena implies that the size of each zones change. To define the limits of the system, we must then consider the minimum and maximum conversion gain of a classical converter. Fig. 8 shows the curve of the gain of the two converters when the conversion gain is 0.25 for the buck mode and 4.0 for the boost mode. The operation areas are then very small and the possibility to find an operating point then depends on the maximum and minimum gain, the report of the decoupling between the two input currents and finally the output voltage.

Experimental results

In this we present experimental results performed with a cascaded four switch DC-DC Buck-Boost converter (FSBB) [START_REF] Orellana | Four Switch Buck-Boost Converter for Photovoltaic DCDC power applications[END_REF]. This structure allows functioning as a step down voltage or as a step up voltage. FSBB is principally characterized by a common inductance between the two stages. There are three operating modes described in [START_REF] Orellana | Four Switch Buck-Boost Converter for Photovoltaic DCDC power applications[END_REF], [START_REF] Orellana | A High Efficiency Photovoltaic Conversion Chain based on a Four-Switch Buck-Boost Converter[END_REF] : the buck mode when the voltage gain is less than 0.95, the boost mode when the gain is greater than 1.05 and an intermediate mode when the gain is ± 5% of unity. Four switches are controlled via a 30F2020 microcontroller to generate four duty cycle signals D1 for the buck, D2 for the boost and their complementary signals working at a switching frequency of 200 kHz. During intermediate operation, all switches are switched; and duty cycles are given as D1 + D2 = 1. We can already say that in this mode the losses will be greater than when operating in boost or buck because all switches are switched during the cutting. Fig. 9 show the electrical schema of the converter, designed to respond to the limit Efficiency of the DC-DC converter according to the total duty cycle define as the addition of the duty cycle D1 of the buck converter and the duty cycle D2 of the boost converter is present Fig. 10.a. We can see that the maximum efficiency is around 93% for a duty cycle around 100%. Another analyze is realized in Fig. 10.b where the voltage gain is compare to the total duty cycle. Under these conditions, we can distinguish the mode buck from the mode boost when the gain is at 1. This curve allows seeing the maximal voltage gain of 4.5 for a boost duty cycle of 85%.

Conclusions and perspectives

Residential facilities are the most affected by shading, especially in urban areas, which may be faced with sometimes complex phenomena shading.

These phenomena are difficult to avoid, linked to other nearby homes and urban furniture. This represents the operating conditions where the impact of shading on the energy yield is the most important. Thus, the shade worn due to chimneys, antennas, trees, clouds, or any mobile shadow moving on the modules during the day cannot be avoided. Similarly, we can add to the list of localized shadows that will be fixed in one or more cells: those primarily related soiling, bowel movements of birds, the trees, or any other deposit made by the various weather conditions. These shades will primarily generate electric producible losses generating more or less gap from its theoretical potential, but if these obstacles to sunlight persist, they can also lead to premature deterioration of the PV generator.

In this paper we make a theoretical analysis of the connection limits of two DC-DC converters which their output are connected in series. Experimental results are realized thanks a FSBB converter which allows us to define the limitation due to DC-DC converter behavior and the limitation due to the efficiency. It can deduce for example that in the ideal case these kind of solution ensure the extraction of maximum power point of each PV modules. Therefore, in the real case, the limitation of the gain does not fully guarantee that this research is successful. Moreover the increasing of the number of stages greatly limits the allowable gap between modules. The MPPT controls operate independently and optimizing the input power of the converter, they can then stabilize at a different operating point of the PPM or even become unstable.

Fig. 1 .

 1 Fig. 1. Photovoltaic power architecture

)Fig. 2 :

 2 Fig. 2 : Serial connexion of PV cells under patial shading

Fig. 3 .

 3 Fig. 3. Potential PV power gain for discretized PV module

Fig. 4 .

 4 Fig. 4. Example of series of two DC-DC converters

  defines the ratio between the output voltage V out and the input voltage of the first converter. 'B' and 'C' represent reciprocally the ratio between the two inputs current and the ratio between the two inputs voltage. Equation of each gain α will be defined according a fraction of the voltage and of the current of the first converter.

Fig. 6 .

 6 Fig. 6. 2D section of the Fig. 4 for α=1 and Vin1=Vin2

Fig. 7 .

 7 Fig. 7. 2D section of the Fig. 4 for α=1 and Vin1≠Vin2

Fig. 8 .

 8 Fig. 8. 2D section of the Fig. 4 for α=1 for Vin1=Vin2 with gain limitation [0.25 et 4]

Fig. 9 .

 9 Fig. 9. Electrical schema of the Buck Boost converter

Fig. 10 .

 10 Fig. 10. Experimental resuls of the cascaded buck boost converter (FSBB)

Fig. 11 .

 11 Fig. 11. Conversion gain between the voltage ratio and the current ratio for Vin1 = Vin2.

EPE'14 ECCE EuropeISBN: 978-1-4799-3014-2 and 978-9-0758-1520-7 P.2

EPE'14 ECCE EuropeISBN: 978-1-4799-3014-2 and 978-9-0758-1520-7 P.4

EPE'14 ECCE EuropeISBN: 978-1-4799-3014-2 and 978-9-0758-1520-7 P.5

EPE'14 ECCE EuropeISBN: 978-1-4799-3014-2 and 978-9-0758-1520-7 P.6

EPE'14 ECCE EuropeISBN: 978-1-4799-3014-2 and 978-9-0758-1520-7 P.8


Arti D Yardi
email: artidilip.yardi@enseeiht.fr

Blind Reconstruction of Binary Cyclic Codes over Binary Erasure Channel

Given a sequence of noise-affected codewords of an unknown channel code, the problem of blind reconstruction of channel codes consists of identifying this unknown channel code. This problem has many applications in military surveillance and cognitive radios. In this paper, we study this problem for the case when the noise is introduced by the binary erasure channel (BEC) and the unknown channel code is a binary cyclic code of known length. We provide an algorithm to find the generator polynomial of the unknown cyclic code. We also provide an analysis of our algorithm where we provide a lower bound on the probability of correctly identifying the factors of the generator polynomial.

I. INTRODUCTION

In the problem of blind reconstruction of channel codes, the channel code that is used at the transmitter is not known at the receiver. Such situations may arise in military surveillance applications or in cognitive radios [START_REF] Moosavi | Fast blind recognition of channel codes[END_REF], where the channel code corresponding to the received data is not known. The receiver has access to the noise-affected sequence of this unknown channel code and the aim is to identify the channel code corresponding to it. This blind reconstruction problem is in general known to be NP-hard [START_REF] Valembois | Detection and recognition of a binary linear code[END_REF]. While identifying a particular channel code, it is typically assumed that the family of the code, such as convolutional or linear block code, is known. The underlying structure of this particular family is then used to identify the code. This problem has been studied for several families of channel codes such as convolutional codes [START_REF] Dingel | Parameter estimation of a convolutional encoder from noisy observations[END_REF], [START_REF] Marazin | Blind recovery of k/n rate convolutional encoders in a noisy environment[END_REF], linear block codes [START_REF] Valembois | Detection and recognition of a binary linear code[END_REF], [START_REF] Sicot | Blind detection of interleaver parameters[END_REF], LDPC codes [START_REF] Moosavi | Fast blind recognition of channel codes[END_REF], [START_REF] Cluzeau | Block code reconstruction using iterative decoding techniques[END_REF], and cyclic codes [START_REF] Chabot | Reconnaissance de codes, structure des codes quasicycliques[END_REF]- [START_REF] Zhou | Blind recognition of binary cyclic codes[END_REF].

For the case of binary cyclic codes, this problem has been studied by Chabot [START_REF] Chabot | Reconnaissance de codes, structure des codes quasicycliques[END_REF], Lee et al. [START_REF] Lee | Reconstruction of BCH codes using probability compensation[END_REF], Yardi et al. [START_REF] Yardi | Blind reconstruction of binary cyclic codes[END_REF], [START_REF]Blind reconstruction of binary cyclic codes from unsynchronized bitstream[END_REF], and Zhou et al. [START_REF] Zhou | Blind recognition of binary cyclic codes[END_REF]. Chabot, Lee et al., and Yardi et al. consider the situation when the noise is introduced by the binary symmetric channel and the situation of additive white Gaussian noise is studied by Zhou et al. However, for several communication systems of practical interests, there are situations when the noise is modeled by BEC. In this paper, we study this blind reconstruction problem for BEC under the assumption that the unknown channel code is a binary cyclic code of known length.

For BEC, one can provide a simple blind reconstruction algorithm as follows. Consider the set of received vectors that have no erasures and take the greatest common divisor (gcd) of these received polynomials. For a cyclic code, since every codeword is a multiple of the generator polynomial g(X) of the code [START_REF] Lin | Error Control Coding[END_REF], this gcd will be equal to g(X) with high probability. However in the presence of erasures and with limited number of received polynomials, one might not be able to find the generator polynomial with this naive algorithm.

For BEC, while a variety of such blind reconstruction algorithms can be proposed, it may not be possible to analyze the performance of all such algorithms or analytically characterize metrics such as probability of correct identification of the unknown code. The main contributions of this paper are: [START_REF] Moosavi | Fast blind recognition of channel codes[END_REF] We first provide a blind reconstruction algorithm to identify the factors of g(X) (see Theorem 1). ( 2) We provide a theoretical analysis of our algorithm, where we provide a lower bound on correctly identifying the factors of g(X) (see Theorems 2 and 3). ( 3) Finally, we provide simulation results for the proposed algorithm for a variety of cyclic codes and also compare the lower bound versus its true value. Organization: In Section II, we describe the system model for the problem of blind reconstruction of cyclic codes over BEC. The proposed blind reconstruction method is given in Section III and a theoretical analysis of this method is discussed in Section IV. In Section V, we provide simulation results of the proposed algorithm for various cyclic codes and finally provide some future directions in Section VI.

Notation: The finite field with two elements 0 and 1 is denoted by F 2 and F 2 [X] denotes the polynomial ring with coefficients from F 2 . The set of natural numbers is denoted by N. We use boldface letters to denote the vectors and lower case letters for the components of a vector. For example, vector w = w 0 w 1 . . . w n-1 , where w i for i = 0, 1, . . . , n-1 are the components of w. The polynomial representation of vector w, is given by w

(X) = w 0 + w 1 X + . . . + w n-1 X n-1 . The sequence of M vectors w 1 , w 2 , . . . , w M is denoted by w M 1 .
The set of polynomials in F 2 [X] of degree strictly less than l is denoted by P l . The product of two polynomials f (X) and f (X) is denoted by f f . Random variables are denoted by capital letters and their realizations are indicated with lowercase letters. For example, the realization of a random variable X is denoted by x. The cyclic code of length n and generator polynomial g(X) is denoted by C(n, g).

II. SYSTEM MODEL AND NOTATION

Suppose the binary cyclic code C(n, g) of length n, dimension k, and generator polynomial g(X) is used at the transmitter. We assume that the length n of the code is known at the receiver but g(X) and k are not known. We assume that C(n, g) corrects at least one error, which implies that its minimum distance d min (C(n, g)) ≥ 3 [START_REF] Lin | Error Control Coding[END_REF]. Let

v M 1 = v 1 v 2 .
. . v M be the sequence of transmitted codewords, where M ∈ N. Each transmitted codeword is independent and identically distributed (i.i.d.) according to the uniform distribution over the set of codewords of C(n, g). The transmitted codewords are affected by the noise introduced by a BEC of erasure probability p to get the received sequence y M 1 = y 1 y 2 . . . y M . For BEC(p), each bit in the received sequence is erased with probability p. Let e j be the number of erasures in y j , for j = 1, 2, . . . , M . Since the transmitted codewords are i.i.d., the received vectors are also i.i.d. Hence, for the sake of simplicity we will drop parameters j from v j , y j , and e j whenever the arguments are applicable for any jth received vector. Using this notation, y is an erased version of v with e the number of erasures. For the blind reconstruction problem of the paper, the aim of the receiver is to identify g(X) of the code using the received sequence y M 1 .

III. PROPOSED BLIND RECONSTRUCTION METHOD

In this section, we propose a simple blind reconstruction method to find the generator polynomial g(X) of the code. The set of factors of X n +1 is the candidate set of polynomials for the factors of g(X) [START_REF] Lin | Error Control Coding[END_REF]. Suppose g(X) is factorized as

g(X) = i [f i (X)] mi , (1)
where f i (X) are irreducible factors of g(X) and m i are their respective multiplicities. We identify g(X) by identifying its irreducible factors and their multiplicities.

Recall that, y is an erased version of a transmitted codeword v with e number of erasures. For the cyclic codes, it is known that each bit is equally likely to be zero or one [START_REF] Lin | Error Control Coding[END_REF]. Hence we substitute 0 and 1 in all the erased entries in y and obtain a set of 2 e vectors denoted by w 2 e 1 = w 1 w 2 . . . w 2 e . In order to identify whether a given candidate factor f (X) of X n + 1 is a factor of g(X) or not, we study the properties of the set w 2 e 1 in the following theorem. Theorem 1. Suppose y is the erased version of a transmitted codeword of C(n, g) with e number of erasures. Let w 2 e 1 = w 1 w 2 . . . w 2 e be the set of vectors obtained by substituting all possible 2 e values in the erased bits of y. Let Y be the random vector corresponding to y. Then for a factor f (X) of X n + 1 we have the following two cases. (a) If f (X) is a factor of g(X), then for every realization y of Y, there exists w i , such that f (X) divides w i (X) for some i,

1 ≤ i ≤ 2 e . (b) If f (X)
is not a factor of g(X), then there exists a realization y of Y such that f (X) does not divide w i (X), for i = 1, 2, . . . , 2 e .

Proof: We first consider the case when f (X) is a factor of g(X). For any received vector y, the correct substitution will always be a multiple of g(X) and f (X) will divide this correct substitution. This completes the proof of part (a).

Let now consider the case when f (X) is not a factor of g(X). In this case, we need to show the existence of a received vector y that satisfies the condition of part (b). Note that the random vector Y is obtained by choosing a codeword v ∈ C(n, g) with probability 1/2 k and then erasing the coefficients of v independently with probability p. Thus with probability 1/2 k , codeword g corresponding to g(X) will be transmitted and with probability (1 -p) n none of the coefficient of g will get erased. The corresponding received vector y will be equal to g. Since f (X) is not a factor of g(X), this y satisfies the conditions of part (b) and the proof is complete.

Theorem 1 can be used to distinguish between the factors and non-factors of g(X). The basic idea of the algorithm consists of substituting all possible values in the erased bits of the received vectors y 1 , y 2 , . . . , y M and find the factors of g(X) using Theorem 1. When the number of received vectors M tend to infinity, Theorem 1 guarantees that the true generator polynomial g(X) will be identified with probability one. However with limited amount of data, we observe that some non-factors of g(X) may satisfy the condition (a) of Theorem 1 and may get wrongly decided as factors of g(X). Consider the following example to explain this observation.

Example 1. Suppose C(n, g), with n = 7 and g(X) = X 3 + X 2 + 1 is used at the transmitter. Suppose the number of received vectors M is equal to one. Suppose v = [1 0 1 1 0 0 0] and y = [1 0 ? ? 0 0 0], where ? denotes the erasure. The set of polynomials obtained by substituting

[0 0], [0 1], [1 0], [1 1] at the erased locations is {1, (X + 1)(X 2 + X + 1), (X + 1) 2 , (X 3 + X 2 + 1)}. The condition (a) of Theorem 1 is satisfied by the factors X + 1 and X 3 + X 2 + 1 of X 7 + 1.
In Example 1, since g(X) is a factor of X 7 + 1, we can remove the non-factors of X 7 + 1 from the set of substituted polynomials. The corresponding set will be {1, (X + 1), (X + 1), (X 3 +X 2 +1)}. Observe that the cyclic code corresponding to all the wrong substitutions has a minimum distance strictly less than three. Since for the true code d min (C(n, g)) ≥ 3, we can discard the substituted entry if the cyclic corresponding to it has the minimum distance strictly less than three. We use this idea to propose a blind reconstruction method in Algorithm 1.

IV. A THEORETICAL PERFORMANCE OF THE PROPOSED

ALGORITHM

In Algorithm 1, all factors of g(X) are always correctly identified. In order to study the performance of this algorithm, the key step is to find the probability that a given non-factor is correctly decided as a non-factor of g(X). Suppose f (X) is a factor of X n + 1 but it is not a factor of g(X). This f (X) is correctly declared as a non-factor if there exists a received vector y that satisfies the condition (b) of Theorem 1 in step (ii) of Algorithm 1. To find the probability of receiving such a y, one needs to condition over all possible 2 k codewords in C(n, g) and all possible 2 n erasure patterns. Since the number of codewords and erasure patterns are exponential in number, finding this probability is in general computationally intractable. Hence in this section, we find an lower bound on receiving such a y. Since all the received vectors are i.i.d., we find this lower bound when the number of received Algorithm 1 Proposed blind reconstruction algorithm (i) Preprocessing step: For the received vector y j with e j erasures, substitute 0 and 1 at each erased location to obtain the set of vectors w 2 e j j,1 , for j = 1, 2, . . . , M . Perform the following operations on the set w 2 e j j,1 . (a) Factorize each w j,i (X) = u j,i (X)h j,i (X) such that u j,i (X) is not a factor of X n + 1 and h j,i (X) is a factor of X n + 1. (b) Discard w j,i (X) if the cyclic code generated by h j,i (X) has minimum distance strictly less than three. Let w j,1 (X), w j,2 (X), . . . , w j,sj (X) be the set of non-discarded polynomials. (ii) Decision step: Declare f (X) as a non-factor of g(X)

if there exists y j for some 1 ≤ j ≤ M such that f (X) does not divide w j,l (X) for l = 1, 2, . . . , s j , otherwise f (X) is declared as a factor of g(X) (see Theorem 1). (iii) Find multiplicity: If f (X) is declared as a factor of g(X) in step (ii), then we need to find its multiplicity (see [START_REF] Moosavi | Fast blind recognition of channel codes[END_REF]). Similar to step (ii), find an integer m such that [f (X)] m is a factor of g(X) but [f (X)] m+1 is not. This m will be the multiplicity of f (X). (iv) Repeat steps (ii) and (iii) for all irreducible factors of X n + 1 and obtain g(X) from equation [START_REF] Moosavi | Fast blind recognition of channel codes[END_REF].

vectors is equal to one, i.e., M = 1. For M > 1 received vectors, the desired y can be any one of the received vector. In Algorithm 1, we remove the substituted entry if the cyclic code corresponding to it has minimum distance strictly less than three. For a given non-factor f (X), depending on whether its minimum distance d min (C(n, f )) ≥ 3 or d min (C(n, f )) < 3, we provide bounds in Sections IV-A and IV-B respectively.

A. Lower Bound for non-factor f (X) with d min (C(n, f )) ≥ 3

Theorem 2. Suppose f (X) is an irreducible factor of X n + 1 such that f (X) not a factor of g(X) and d min (C(n, f )) ≥ 3.

Let A(f ) be the event that f (X) is declared as a non-factor in step (ii) of Algorithm 1, when the number of received vectors M is equal to one. Then a lower bound on P A(f ) is,

P A(f ) ≥ deg(f )-1 e=0 1 - 2 e 2 deg(f ) n e p e (1 -p) n-e .
Proof: We condition on the number of erasures and find a lower bound on P[A(f )]. Suppose the number of erasures in received y is equal to e. The probability of this event is equal to n e p e (1 -p) n-e . Let {l 1 , l 2 , . . . , l e } be the set of erasure locations in y, where 0 ≤ l 1 < l 2 < . . . < l e < n. The set of vectors obtained by substituting all possible 2 e values in these erasure locations is given by w 2 e 1 = w 1 w 2 . . . w 2 e . We first prove that for every w i , there exists a vector

d i = d i,1 d i,2 . . . d i,e ∈ F e 2 such that w i (X) = v(X) + d i,1 X l1 + d i,2 X l2 + . . . + d i,e X le (2) = v(X) + d i (X), (3)
where d i (X) := d i,1 X l1 + d i,2 X l2 + . . . + d i,e X le , for i = 1, 2, . . . , 2 e and v(X) is the transmitted codeword. Suppose w i is obtained by substituting c i = c i,1 c i,2 . . . c i,e ∈ F e 2 to the erased entries of y. For the transmitted codeword v, c = v l1 v l2 . . . v le ∈ F e 2 will be the correct substitution. By choosing a vector d i ∈ F e 2 such that d i = c i + c, we get [START_REF] Dingel | Parameter estimation of a convolutional encoder from noisy observations[END_REF]. Since all the substituted entries take all possible values in F e 2 , the corresponding set of vectors d 1 , d 2 . . . , d 2 e will also take all possible values in F e 2 . Let A(f ) c be the complement of event A(f ). We find an upper bound on P[A(f ) c ] which will provide a lower bound on P[A(f )]. The probability of event A(f ) c is given by,

P[A(f ) c ] = P w i (X) mod f (X) = 0 for some w i ∈ w 2 e 1 (a) = P v(X) + d i (X) mod f (X) = 0 for some d i ∈ F e 2 = P v(X) mod f (X) = d i (X) mod f (X) for some d i ∈ F e 2 , (4)
where equality in (a) is obtained from (3). From Proposition 3.1 of [START_REF] Yardi | Blind reconstruction of binary cyclic codes[END_REF], v(X) mod f (X) takes any value in P deg(f ) with probability 1/2 deg(f ) and using this in (4) we get,

P[A(f ) c ] = 1 2 deg(f ) b∈P deg(f ) P d i (X) mod f (X) = b(X) for some d i ∈ F e 2 . ( 5
)
Let D be the support set of d i (X) mod f (X) and |D| denotes the cardinality of set D. Depending on the number of erasures e, we now have the following two cases.

(1) Case when e < deg(f ):

In this case, d i (X) mod f (X) can take at most 2 e distinct values since d i can take at most 2 e distinct values in F e 2 , i.e., |D| ≤ 2 e . In [START_REF] Sicot | Blind detection of interleaver parameters[END_REF], P[d i (X) mod f (X) = a(X) for some d i ∈ F e 2 ] is equal to one if a(X) ∈ D and it is zero otherwise. This implies that,

P[A(f ) c ] = 1 2 deg(f ) |D| ≤ 2 e 2 deg(f ) . (6)
(2) Case when e ≥ deg(f ) :

In this case, d i (X) mod f (X) can take at most 2 deg(f )
possible values and hence |D| ≤ 2 deg(f ) . Using this in [START_REF] Sicot | Blind detection of interleaver parameters[END_REF] we have,

P[A(f ) c ] = 1 2 deg (f ) |D| ≤ 2 deg(f ) 2 deg(f ) = 1. (7)
The required lower bound is obtained from ( 6) and ( 7) by conditioning over E = e since P(A(f )) = 1 -P(A(f ) c ).

B. Lower Bound for non-factor f (X) with d min (C(n, f )) < 3

In this section, we consider the case when d min (C(n, f )) < 3. We first introduce some notation that will be required in this section. Let F be the set of irreducible factors of X n + 1. For a given f (X) ∈ F that is not a factor of g(X), we define two sets F 1 and F 2 as follows,

F 1 := {f (X) ∈ F such that d min (C(n, f f )) ≥ 3 and f (X) does not divide g(X)} (8) F 2 := {f (X) ∈ F such that d min (C(n, f f )) ≥ 3 and f (X) divides g(X)}, (9)
where C(n, f f ) is the cyclic code generated by f (X)f (X).

Let w 1 (X), w 2 (X), . . . , w s (X) be the set of non-discarded polynomials in step (i)-(b) of Algorithm 1. Let B(f ) be the event that f (X) is declared as a non-factor in step (ii) of Algorithm 1. The probability of event B(f ) is given by,

P[B(f )] = P w i (X) mod f (X) = 0 for i = 1, . . . , s (10)
Remark 1. Without loss of generality suppose w 1 (X) in [START_REF]Blind reconstruction of binary cyclic codes from unsynchronized bitstream[END_REF] corresponds to the transmitted codeword of C(n, g). When f (X) divides w 1 (X), we have P[B(f )] = 0. Thus event B(f ) can occur only when f (X) does not divide w 1 (X).

In the following lemma, we find an upper bound on B(f

) c (complement of B(f )) when f (X) does not divide w 1 (X). Lemma 1. Let B(f ), f (X), F 1 ,
and, F 2 be as defined above. Suppose f (X) does not divide w 1 (X) in [START_REF]Blind reconstruction of binary cyclic codes from unsynchronized bitstream[END_REF]. Then under the condition the number of erasures in received vector y is equal to e, an upper bound on P B(f ) c E = e is given by

P B(f ) c E = e ≤ f ∈F1 2 e 2 deg(f ) + f ∈F2 β(f ),
where β(f ) is given by

β(f ) := e i=dmin(C(n,f ) A i (f ) n -i e -i n e ,
where the sequence of integers {A 0 (f ), A 1 (f ), . . . , A n (f )} is the weight distribution of C(n, f ).

Proof: In Algorithm 1, each w i (X) in (10) belongs to some cyclic code of length n with minimum distance greater than or equal to three. Since

d min (C(n, f )) < 3, w i (X) mod f (X) = 0 implies that w i (X) ∈ C(n, f f ), such that d min (C(n, f f )) ≥ 3. Note that it is sufficient to consider the case when f (X) ∈ F since when f (X) / ∈ F, f (X) can be written as f (X) = f 1 (X)f 2 (X) such that f 1 (X) ∈ F and w i (X) ∈ C(n, f f 1 ). Using this, P[B(f ) c E = e]
given by,

P[B(f ) c E = e] = P w i (X) mod f (X)f (X) = 0 for , some i, 2 ≤ i ≤ s and some f (X) ∈ F 1 ∪ F 2 (a) ≤ f ∈F1∪F2 P w i (X) ∈ C(n, f f ) for some i, 2 ≤ i ≤ s := f ∈F1 P[D(f f ) E = e] + f ∈F2 P[D(f f ) E = e], (11)
where the upper bound in (a) follows from the union bound. The event D(f f E = e) in [START_REF] Zhou | Blind recognition of binary cyclic codes[END_REF] correspond to w i (X) ∈ C(n, f f ) for some i, 2 ≤ i ≤ s. The equality in [START_REF] Zhou | Blind recognition of binary cyclic codes[END_REF] follows since the sets F 1 and F 2 are disjoint (see [START_REF] Lee | Reconstruction of BCH codes using probability compensation[END_REF], ( 9)). We find an upper bound on P[B(f ) c E = e] by finding an upper bound on each P[D(f f ) E = e] in [START_REF] Zhou | Blind recognition of binary cyclic codes[END_REF].

(i) Case when f ∈ F 1 :

In this case, the event w i (X) ∈ C(n, f f ) implies w i (X) ∈ C(n, f ). From ( 6) and ( 7) we have

P[D(f f ) E = e] ≤ 2 e /2 deg(f ) (see proof of Thm. 2). (ii) Case when f ∈ F 2 :
From (3) we have, w i (X) = v(X)+d i (X), where v(X) is the transmitted codeword, for i = 2, 3, . . . , s. Using this P[D(f f ) E = e] is given by,

P[D(f f ) E = e] = P [v(X) + d i (X)] ∈ C(n, f f ) for some i, 2 ≤ i ≤ s (a) ≤ P [v(X) + d i (X)] ∈ C(n, f ) for some 2 ≤ i ≤ s , = P d i (X) ∈ C(n, f ) for some i, 2 ≤ i ≤ s , (12)
where the upper bound in (a) is obtained since every codeword in C(n, f f ) also belongs to C(n, f ) and the equality in the last step follows since v(X) ∈ C(n, f ). As explained in the proof of Theorem 2, for the correct substitution d i (X) = 0 and for any incorrect substitution d i (X) = 0. Let {l 1 , l 2 , . . . , l e } be the set of erasure locations in y. From (3), each d i (X) = d i,1 X l1 +d i,2 X l2 +. . .+d i,e X le is obtained by substituting 0 and 1 in each d i,j , for j = 1, 2, . . . , e. If there exists a codeword v(X) in C(n, f ) whose support set is contained in the locations {l 1 , l 2 , . . . , l e } then the coefficients of d i (X) can be chosen to be equal to v(X) and in [START_REF] Lin | Error Control Coding[END_REF] we have P D(f f ) E = e = 1. Note that, the weight of this v(X) should be less than or equal to e. Using this the probability in ( 12) is given by

P D(f f ) E = e ≤ e i=dmin(C(n,f )) A i n -i e -i n e .
The upper bound of the theorem is obtained from [START_REF] Zhou | Blind recognition of binary cyclic codes[END_REF].

Using Lemma 1 and Remark 1, we now obtain a lower bound on P[B(f )] in the following theorem. Theorem 3. Suppose f (X) is an irreducible factor of X n + 1 such that f (X) not a factor of g(X) and d min (C(n, f )) < 3. Let B(f ) be the event that f (X) is declared as a non-factor in step (ii) of Algorithm 1, when the number of received vectors M is equal to one. When E = e, let α(e) be the upper bound obtained in Lemma 1. Let e be the largest number of erasures such that α(e) < 1. Then a lower bound on P[B(f )] is Proof: From Remark 1, event B(f ) can happen only when f (X) does not divide correct substitution w 1 (X) and its probability is equal to 1 -(1/2 deg(f ) ) (Proposition 3.1 of [START_REF] Yardi | Blind reconstruction of binary cyclic codes[END_REF]). The lower bound of the theorem follows Lemma 1 by conditioning over event E = e from e = 0, 1, . . . , e .

P[B(f )] ≥ 1 - 1 2 deg(f )
(X) = (X 8 + X 4 + X 3 + X + 1)(X 8 + X 5 + X 4 + X 3 + 1) and g 2 (X) = (X 2 + X + 1)(X 18 + X 16 + X 15 + X 14 + X 9 + X 4 + X 3 + X 2 +

V. SIMULATION RESULTS

For simulations, we generate a sequence of codewords v M 1 and every bit in this sequence is erased independently with probability p to get y M 1 . Algorithm 1 is applied to this y M 1 . Since Algorithm 1 consists of substituting all possible values at the erased locations, the cost of implementation increases with increase in the number of erasures in the received vectors. Hence we discard the received vector if the number of erasures are more than e max . For the simulations we have chosen e max = 7. Fig. 1 shows the plot of probability of detection (P D ) versus erasure probability p for various cyclic codes. Fig. 2 shows the plot of P D versus p for BCH(63, 39) for various M . Simulations are performed using SageMath [START_REF]The Sage Developers[END_REF].

We next compare the lower bound on correctly identifying the non-factors of the generator polynomial obtained using Theorems 2 or 3 versus its true value in Fig. 3. As explained in Section IV, finding the true value is computationally intractable and hence we find approximate true value via Monte Carlo simulations of Algorithm 1 with M = 1 and e max = 7.

VI. CONCLUSION AND FUTURE WORK

In this paper, we studied the problem of blind reconstruction of cyclic codes of known lengths, when the noise is introduced Fig. 3. For BCH(63, 39), lower bound on correctly identifying the nonfactors and their corresponding true values are plotted for f 1 (X) = X 6 + X 4 + X 3 + X + 1 and f 2 (X) = X + 1. For f 1 (X), lower bound (L.B.) obtained via Theorem 2 and f 2 (X) L.B. is obtained using Theorem 3.

by BEC. We proposed a blind reconstruction algorithm and provided a lower bound on correctly identifying the factors of the generator polynomial. To the best of our knowledge, this is the first time a blind reconstruction problem has been analyzed for the binary erasure channel. As part of future work, we plan to study this problem for the case when the length of cyclic code is not known. Studying this blind reconstruction problem over BEC for other families of channel codes such as convolutional, Turbo, linear block codes is also of interest.

( 1 -

 1 p) n-e .

Fig. 1 .

 1 Fig.1. Plot of P D versus p for BCH(31, 21), C(51, g 1 ), C(102, g 2 ), and BCH(255, 187) where g 1 (X) = (X 8 + X 4 + X 3 + X + 1)(X 8 + X 5 + X 4 + X 3 + 1) and g 2 (X) = (X 2 + X + 1)(X 18 + X 16 + X 15 + X 14 + X 9 + X 4 + X 3 + X 2 + 1) 2 when M = 30 vectors of true code are received.

1 ) 2 Fig. 2 .

 122 Fig.1. Plot of P D versus p for BCH(31, 21), C(51, g 1 ), C(102, g 2 ), and BCH(255, 187) where g 1 (X) = (X 8 + X 4 + X 3 + X + 1)(X 8 + X 5 + X 4 + X 3 + 1) and g 2 (X) = (X 2 + X + 1)(X 18 + X 16 + X 15 + X 14 + X 9 + X 4 + X 3 + X 2 + 1) 2 when M = 30 vectors of true code are received.

1

  Erasure probability of BEC (p) Probability of detection (P D ) P[A(f1)] L.B. on P[A(f2)] P[B(f2)] L.B. on P[B(f2)]

ACKNOWLEDGMENTS

This work is supported by ANR-11-LABEX-0040-CIMI within the program ANR-11-IDEX-0002-02 of Centre International de Mathématiques et Informatique de Toulouse, France.