International audience

In this paper, we deal with the problem of simultaneous reconstruction of a vector of rational numbers, given modular reductions containing errors (SRNRwE). Our methods apply as well to the simultaneous reconstruction of rational functions given evaluations containing errors (SRFRwE), improving known results [7, 9]. In the latter case, one can take advantage of techniques from coding theory [4, 10] and provide an algorithm that extends classical Reed-Solomon decoding. In recent works [7, 9], interleaved Reed-Solomon codes [3, 19] are used to correct beyond the unique decoding capability in the case of random errors at the price of positive but small failure probability. Our first contribution is to extend these works to the simultaneous reconstruction with errors of rational numbers instead of functions. Thus considering rational number codes [16], we provide an algorithm decoding beyond the unique decoding capability and, as a central result of this paper, we analyze in detail its failure probability. Our analysis generalizes for the first time the best known analysis for interleaved Reed-Solomon codes [19] to SRFRwE, improving on the existing bound [8], to interleaved Chinese remainder codes, also improving the known bound [1], and finally for the first time to SRNRwE.

To date, Li et al. have presented the only decoder for Interleaved Chinese Remainder (ICR) codes [1]. The core of their ICR decoder is to find a short vector in a lattice using the LLL algorithm [2]. However, their analysis of the decoding failure is partially heuristic. In this work, we present a new analysis of their LLL-based decoder that gives a proved upper bound on its decoding failure probability.

This paper deals with the polynomial linear system solving with errors (PLSwE) problem. More specifically, we solve linear systems with univariate polynomial coefficients via an evaluation-interpolation technique assuming that errors can occur before the interpolation step. In this framework, the number of evaluations needed to recover the solution depends on the parameters of the linear system (degrees, size) and on the number of errors.

This paper focuses on the problem of reconstructing a vector of rational functions given some evaluations, or more generally given their remainders modulo different polynomials. The special case of rational functions sharing the same denominator, a.k.a. Simultaneous Rational Function Reconstruction (SRFR), has many applications from linear system solving to coding theory, provided that SRFR has a unique solution. The number of unknowns in SRFR is smaller than for a general vector of rational function. This allows one to reduce the number of evaluation points needed to guarantee the existence of a solution, possibly losing its uniqueness. In this work, we prove that uniqueness is guaranteed for a generic instance.

In this paper we present a new algorithm for Polynomial Linear System Solving (via evaluation/interpolation) with errors. In this scenario, errors can occur in the black box evaluation step. We improve the bound on the number of errors that we can correct, using techniques inspired by the decoding procedure of Interleaved Reed-Solomon Codes.

A set of congruence relations is a z-covering if each integer belongs to at least one congruence class from that set. In this paper, we first show that most existing scalar multiplication algorithms can be formulated in terms of covering systems of congruences. Then, using a special form of covering systems called exact n-covers, we present a novel uniformly randomized scalar multiplication algorithm with built-in protections against most passive side-channel attacks. Our algorithm randomizes the addition chain using a mixed-radix representation of the scalar. Its reduced overhead and purposeful robustness could make it a sound replacement to several conventional countermeasures. In particular, it is significantly faster than Coron's scalar blinding technique for elliptic curves when the choice of a particular finite field tailored for speed compels to double the size of the scalar, hence the cost of the scalar multiplication.

Most bounds on the size of codes hold for any code, whether linear or not. Notably, the Griesmer bound holds only in the linear case and so optimal linear codes are not necessarily optimal codes. In this paper, we identify code parameters (q, d, k), namely, field size, minimum distance, and combinatorial dimension, for which the Griesmer bound also holds in the (systematic) nonlinear case. Moreover, we show that the Griesmer bound does not necessarily hold for a systematic code by explicit construction of a family of optimal systematic binary codes. On the other hand, we are able to provide some versions of the Griesmer bound holding for all the systematic codes.

We present some upper bounds on the size of nonlinear codes and their restriction to systematic codes and linear codes. These bounds are independent of other known theoretical bounds, e.g., the Griesmer bound, the Johnson bound, the Plotkin bound, and of linear programming bounds. One of the new bound is actually an improvement of a bound by Zinoviev, Litsyn, and Laihonen. Our experiments show that in the linear case our bounds provide the best value in a wide range, compared with all other closed-formula upper bounds. In the nonlinear case, we also compare our bound with the linear programming bound and with some improvements on it, show that there are cases where we beat these bounds. In particular, we obtain a new bound in Brouwer's table for A3(16,3).

In this paper bit loading algorithms that try to maximize the throughput, guaranteeing the overall BER below a fixed target, are investigated. In particular,the optimal solution is given and an approximation based on a probabilistic approach is detailed, providing a very simple implementation with negligible loss. The proposed solution is tested in the HPAV system, using a realistic power line channel model. Numerical results, in terms of throughput and complexity, show that the proposed solution is a good trade-off between performance and complexity.

In this paper channel estimation in the context of OFDM systems is investigated. In particular, a technique to improve the channel estimation in the current packet, by averaging out the channel estimates performed during previous packets, is proposed. However, when frame synchronization offset and/or sampling phase offset is present, the estimated channels differ by linear phase terms which have to be estimated and compensated. Therefore, to estimate the phase differences, a maximum likelihood estimator is suggested and a simplification based on the Taylor series, which noticeably reduces the computational load, is proposed. The performance of the algorithm is tested in the OFDM-based HomePlug AV system using the OPERA powerline channel models. Numerical results, in terms of BER versus signal-to-noise ratio, show that the simplified estimator based on the Taylor series achieves almost the same performance of the maximum likelihood estimator.

In this paper a new bit-loading algorithm for the OFDM-based turbo coded HomePlug AV system is proposed. To better exploit the error correction capabilities of the turbo code, this algorithm tries to maximize the throughput while guaranteeing a target BER over a set of sub-carriers using a new metric based on the LLRs. The performance of the considered system, in terms of throughput and BER, is evaluated, using a realistic power-line channel model. Furthermore, data- aided channel and SNR estimates are investigated and their performance compared with the ideal case.