We consider the quantum decoding problem. It consists in recovering a codeword given a superposition of noisy versions of this codeword. By measuring the superposition, we get back to the classical decoding problem. It appears for the first time in Chen, Liu and Zhandry’s work showing a quantum advantage for the Short Integer Solution (SIS) problem for thel∞norm. In a recent paper, Chailloux and Tillich proved that when we have a noise following a Bernoulli distribution, the quantum decoding problem can be solved in polynomial time and is therefore easier than classical decoding for which the best known algorithms have an exponential complexity. They also give an information theoretic limit for the code rate at which this problem can be solved which turns out to be above the Shannon limit. In this paper, we generalize the last result to all memoryless noise models. We also show similar results in the rank metric case which corresponds to a noise model which is not memoryless. We analyze the Pretty Good Measurement, from which we derive an information theoretic limit for this problem. By using the algorithm for the quantum decoding problem together with Regev’s reduction, we derive a quantum algorithm sampling codewords from the dual code according to a probability distribution which is the dual of the original noise. It turns out that at the information theoretic limit, we get the most likely nonzero codeword of the dual code. When the distribution is a decreasing function of the weight, we find minimal nonzero codewords. Note that Regev’s reduction used together with classical decoding is much less satisfying since it is not able to output those minimum weight codewords.

In the last years, Regev's reduction has been used as a quantum algorithmic tool for providing a quantum advantage for variants of the decoding problem. Following this line of work, the authors of [JSW+24] have recently come up with a quantum algorithm called Decoded Quantum Interferometry that is able to solve in polynomial time several optimization problems. They study in particular the Optimal Polynomial Interpolation (OPI) problem, which can be seen as a decoding problem on Reed-Solomon codes. In this work, we provide strong improvements for some instantiations of the OPI problem. The most notable improvements are for the $ISIS_{\infty}$ problem (originating from lattice-based cryptography) on Reed-Solomon codes but we also study different constraints for OPI. Our results provide natural and convincing decoding problems for which we believe to have a quantum advantage. Our proof techniques involve the use of a soft decoder for Reed-Solomon codes, namely the decoding algorithm from Koetter and Vardy [KV03]. In order to be able to use this decoder in the setting of Regev's reduction, we provide a novel generic reduction from a syndrome decoding problem to a coset sampling problem, providing a powerful and simple to use theorem, which generalizes previous work and is of independent interest. We also provide an extensive study of OPI using the Koetter and Vardy algorithm.

A long standing open question is whether the distinguisher of high rate alternant codes or Goppa codes from Faugère, Gauthier-Umaña, Otmani, Perret, and Tillich in 2011 can be turned into an algorithm recovering the algebraic structure of such codes from the mere knowledge of an arbitrary generator matrix of it. This would allow to break the McEliece scheme as soon as the code rate is large enough and would break all instances of the CFS signature scheme. We give for the first time a positive answer for this problem when the code isa generic alternant codeand when the code field sizeqis small:q∈ {2, 3} and forallregimes of other parameters for which the aforementioned distinguisher works. This breakthrough has been obtained by two different ingredients: (i) a way of using code shortening and the component-wise product of codes to derive from the original alternant code a sequence of alternant codes of decreasing degree up to getting an alternant code of degree 3 (with a multiplier and support related to those of the original alternant code); (ii) an original Gröbner basis approach which takes into account the non standard constraints on the multiplier and support of an alternant code which recovers in polynomial time the relevant algebraic structure of an alternant code of degree 3 from the mere knowledge of a basis for it.

We give a quantum reduction from finding short codewords in a random linear code to decoding for the Hamming metric. This is the first time such a reduction (classical or quantum) has been obtained. Our reduction adapts to linear codes the Stehlé-Steinfield-Tanaka-Xagawa’ re-interpretation of Regev’s quantum reduction from finding short lattice vectors to solving the Closest Vector Problem. The Hamming metric is a much coarser metric than the Euclidean metric and this adaptation has needed several new ingredients to make it work. For instance, in order to have a meaningful reduction it is necessary in the Hamming metric to choose a very large decoding radius and this needs in many cases to go beyond the radius where decoding is always unique. Another crucial step for the analysis of the reduction is the choice of the errors that are being fed to the decoding algorithm. For lattices, errors are usually sampled according to a Gaussian distribution. However, it turns out that the Bernoulli distribution (the analogue for codes of the Gaussian) is too much spread out and cannot be used, as such, for the reduction with codes. This problem was solved by using instead a truncated Bernoulli distribution.

In this article we revisit smoothing bounds in parallel between lattices and codes. Initially introduced by Micciancio and Regev, these bounds were instantiated with Gaussian distributions and were crucial for arguing the security of many lattice-based cryptosystems. Unencumbered by direct application concerns, we provide a systematic study of how these bounds are obtained for both lattices and codes, transferring techniques between both areas. We also consider multiple choices of spherically symmetric noise distributions. We found that the best strategy for a worst-case bound combines Parseval’s Identity, the Cauchy-Schwarz inequality, and the second linear programming bound, and this holds for both codes and lattices and all noise distributions at hand. For an average-case analysis, the linear programming bound can be replaced by an expected value computation. This alone gives optimal results for spherically uniform noise over random codes and random lattices. This also improves prior Gaussian smoothing bounds for worst-case lattices, but surprisingly this provides even better results with uniform ball noise than for Gaussian (or Bernoulli noise for codes). This counterintuitive situation can be resolved by adequate decomposition and truncation of Gaussian and Bernoulli distributions into a superposition of uniform noise, giving further improvement for those cases, and putting them on par with the uniform cases.

Decoding a Reed-Solomon code can be modeled by a bilinear system which can be solved by Gröbner basis techniques. We will show that in this particular case, these techniques are much more efficient than for generic bilinear systems with the same number of unknowns and equations (where these techniques have exponential complexity). Here we show that they are able to solve the problem in polynomial time up to the Sudan radius. Moreover, beyond this radius these techniques recover automatically polynomial identities that are at the heart of improvements of the power decoding approach for reaching the Johnson decoding radius. They also allow to derive new polynomial identities that can be used to derive new algebraic decoding algorithms for Reed-Solomon codes. We provide numerical evidence that this sometimes allows to correct efficiently slightly more errors than the Johnson radius. Note A full version containing the proofs is accessible on arxiv at: https://arxiv.org/abs/2102.02544

We give an algorithm that is able to speed up the decoding of a code with a non-trivial automorphism group, by summing for the word that has to be decoded, all its entries belonging to a same orbit and decoding the resulting word in a reduced code. For a certain range of parameters, this results in a decoding that is faster by an exponential factor in the codelength when compared to the best algorithms for decoding generic linear codes. This algorithm is then used to break several proposals of public-key cryptosystems based on codes with a non-trivial automorphism group.

In this paper, we propose an improvement of the attack on the Rank Syndrome Decoding (RSD) problem found in [1], usually the best attack considered for evaluating the security of rank metric based cryptosystems. For H a full-rank (n-k)×n matrix over Fqmand e ∈ Fqnm of small norm r, the RSD problem consists in recovering e from s=HeT. In our case, the norm of a vector over Fqmis defined by the dimension of the Fq-subspace generated by its coordinates. This problem is very similar to the Syndrome Decoding problem in the Hamming metric (only the metric and the field of the coefficients are different) and the security of several cryptosystems relies on its hardness, like McEliece-based PKE [2], [3] or IBE [4]. Our attack is in O((n- k)3m3qw-⌈((k+1)m)/n]⌉-m) operations in Fqwhereas the previous best attacks are in O((n-k)3m3q(w-1)min(⌈((k+1)m)/n⌉,k+1)) [1], [5]. In particular in the case m ≤ n, our attack permits to obtain an exponential gain in qm(1-R)for R=k/n the rate of the code. We give examples of broken parameters for recently proposed cryptosystems based on LRPC codes or Gabidulin codes. Our attack does not fully break these cryptosystems but implies larger parameters for the same security levels.

The key encapsulation mechanism EDON-K was proposed in response to the call for post-quantum cryptography standardization issued by the National Institute of Standards and Technologies (NIST). This scheme is inspired by the McEliece scheme but uses another family of codes defined over F2128instead of F2and is not based on the Hamming metric. It allows significantly shorter public keys than the McEliece scheme. In this paper, we give a polynomial time algorithm that recovers the encapsulated secret. This attack makes the scheme insecure for the intended use. We obtain this result by observing that recovering the error in the McEliece scheme corresponding to EDON-K can be viewed as a decoding problem for the rank-metric. We show that the code used in EDON-K is in fact a super-code of a Low Rank Parity Check (LRPC) code of very small rank (1 or 2). A suitable parity-check matrix for the super-code of such low rank can be easily derived from for the public key. We then use this parity-check matrix in a decoding algorithm that was devised for LRPC codes to recover the error. Finally we explain how we decapsulate the secret once we have found the error.

Moderate Density Parity Check (MDPC) codes are defined here as codes which have a parity-check matrix whose row weight is O(√n) where n is the length n of the code. They can be decoded like LDPC codes but they decode much less errors than LDPC codes: the number of errors they can decode in this case is of order Θ(√n). Despite this fact they have been proved very useful in cryptography for devising key exchange mechanisms. They have also been proposed in McEliece type cryptosystems. However in this case, the parameters that have been proposed in [11] were broken in [9]. This attack exploits the fact that the decoding failure probability is non-negligible. We show here that this attack can be thwarted by choosing the parameters in a more conservative way. We first show that such codes can decode with a simple bit-flipping decoder any pattern of O([(√nloglogn)/logn]) errors. This avoids the previous attack at the cost of significantly increasing the key size of the scheme. We then show that under a very reasonable assumption the decoding failure probability decays almost exponentially with the codelength with just two iterations of bit-flipping. With an additional assumption it has even been proved that it decays exponentially with an unbounded number of iterations and we show that in this case the increase of the key size which is required for resisting to the [9] attack is only moderate.

In this paper we show how to attain the capacity of discrete symmetric channels with polynomial time decoding complexity by considering iterated (U | U + V) constructions with algebraic geometry (AG) code components. These codes are decoded with a recursive computation of the a posteriori probabilities of the code symbols together with decoding the AG components with the Koetter-Vardy algorithm. We show that, when the number of levels of the iterated (U | U + V) construction tends to infinity, we attain the capacity of any discrete symmetric channel. Moreover the error probability decays quasi-exponentially with the codelength in the case of Reed-Solomon code constituents and exponentially with Tsfasman-Vladuts-Zink code constituents.

The security of code-based cryptography relies primarily on the hardness of generic decoding with linear codes. The best generic decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoding techniques (ISD). A while ago a generic decoding algorithm which does not belong to this family was proposed: statistical decoding. It is a randomized algorithm that requires the computation of a large set of parity-check equations of moderate weight. We solve here several open problems related to this decoding algorithm. We give in particular the asymptotic complexity of this algorithm, give a rather efficient way of computing the parity-check equations needed for it inspired by ISD techniques and give a lower bound on its complexity showing that when it comes to decoding on the Gilbert-Varshamov bound it can never be better than Prange's algorithm.

We present a polynomial-time structural attack against the McEliece system based on Wild Goppa codes defined over a quadratic finite field extension. We show that such codes can be efficiently distinguished from random codes. The attack uses this property to compute a filtration, that is to say, a family of nested subcodes which will reveal their secret algebraic description.

Polar codes form a very powerful family of codes with a low complexity decoding algorithm that attains many information theoretic limits in error correction and source coding. These codes are closely related to Reed-Muller codes because both can be described with the same algebraic formalism, namely they are generated by evaluations of monomials. However, finding the right set of generating monomials for a polar code which optimises the decoding performances is a nontrivial task and is channel dependent. The purpose of this paper is to reveal some universal properties of these monomials. We will namely prove that there is a way to define a nontrivial (partial) order on monomials so that the monomials generating a polar code devised for a binary-input symmetric channel always form a decreasing set. We call such codes decreasing monomial codes. The fact that polar codes are decreasing monomial codes turns out to have rather deep consequences on their structure. Indeed, we show that decreasing monomial codes have a very large permutation group by proving that it contains a group called lower triangular affine group. Furthermore, the codewords of minimum weight correspond exactly to the orbits of the minimum weight codewords that are obtained from evaluations of monomials of the generating set. In particular, it gives an efficient way of counting the number of minimum weight codewords of a decreasing monomial code and henceforth of a polar code.

In this paper we present a modification of Reed-Solomon codes that beats the Guruswami-Sudan 1 − √R decoding radius of Reed-Solomon codes at low rates R. The idea is to choose Reed-Solomon codes U and V with appropriate rates in a (U | U + V ) construction and to decode them with the Koetter-Vardy soft information decoder. We suggest to use a slightly more general version of these codes (but which has the same decoding performance as the (U | U + V )-construction) for being used in code-based cryptography, namely to build a McEliece scheme. The point is here that these codes not only perform nearly as well (or even better in the low rate regime) as Reed-Solomon codes, but also that their structure seems to avoid the Sidelnikov-Shestakov attack which broke a previous McEliece proposal based on generalized Reed-Solomon codes.

The main practical limitation of the McEliece public-key encryption scheme is probably the size of its key. A famous trend to overcome this issue is to focus on subclasses of alternant/Goppa codes with a non-trivial automorphism group. Such codes display then symmetries allowing compact parity-check or generator matrices. For instance, a key-reduction is obtained by taking quasi-cyclic (QC) or quasi-dyadic (QD) alternant/Goppa codes. We show that the use of such symmetric alternant/Goppa codes in cryptography introduces a fundamental weakness. It is indeed possible to reduce the key-recovery on the original symmetric public-code to the key-recovery on a (much) smaller code that has no symmetry anymore. This result is obtained thanks to an operation on codes called folding that exploits the knowledge of the automorphism group. This operation consists in adding the coordinates of codewords which belong to the same orbit under the action of the automorphism group. The advantage is twofold. The reduction factor can be as large as the size of the orbits, and it preserves a fundamental property: folding the dual of an alternant (respectively, Goppa) code provides the dual of an alternant (respectively, Goppa) code. A key point is to show that all the existing constructions of alternant/Goppa codes with symmetries follow a common principal of taking codes whose support is globally invariant under the action of affine transformations (by building upon prior works of Berger and Dür). This enables not only to present a unified view but also to generalize the construction of QC, QD, and even quasi-monoidic Goppa codes. Finally, our results can be harnessed to boost up any key-recovery attack on McEliece systems based on symmetric alternant or Goppa codes, and in particular algebraic attacks.

We present an efficient decoding algorithm for constant rate quantum hyper graph-product LDPC codes which provably corrects adversarial errors of weight proportional to the code minimum distance, or equivalently to the square-root of the block length. The algorithm runs in time linear in the number of qubits, which makes its performance the strongest to date for linear-time decoding of quantum codes. The algorithm relies on expanding properties, not of the quantum code's factor graph directly, but of the factor graph of the original classical code it is constructed from.

We consider the decoding problem or the problem of finding low weight codewords for rank metric codes. We show how additional information about the codeword we want to find under the form of certain linear combinations of the entries of the codeword leads to algorithms with a better complexity. This is then used together with a folding technique for attacking a McEliece scheme based on LRPC codes. It leads to a feasible attack on one of the parameters suggested in [11].

We suggest in this paper a new method for detecting whether a given binary sequence is a noisy convolutional codeword obtained from an unknown convolutional code. It basically consists in forming blocks of the sequence which are big enough to contain the support of a codeword in the dual of the convolutional code and to count the number of blocks which are equal. This detection process is quite efficient and presents the advantage over all previously known methods to achieve this goal even in the case of an unknown modulation. Moreover, this method can also be used to reconstruct the unknown convolutional code when the modulation is known.

We propose a simple decoding algorithm for CSS codes taking into account the correlations between the X part and the Z part of the error. Applying this idea to surface codes, we derive an improved version of the perfect matching decoding algorithm which uses these X/Z correlations.

The main practical limitation of the McEliece cryptosystem is probably the size of its public-key. To overcome this issue, a famous trend is to decrease the public-key size by focusing on subclasses of alternant/Goppa codes which admit a compact parity-check or generator matrix. For instance, a key-size reduction is obtained by taking alternant/Goppa codes which have quasi-cyclic (QC) or quasi-dyadic (QD) generator matrices. We show that the use of such compact alternant/Goppa codes introduced a fundamental weakness. It is possible to reduce the key-recovery on the original public-code C to the key-recovery on a (much) smaller code C'. To this end, we use a new operation on codes which exploits the automorphism group.

We give here an efficient algorithm for recovering the permutation of an unknown turbo-code when several noisy codewords are given. The algorithm presented here uses the same information as some other algorithms given previously for this problem but in an optimal fashion. This paper also clarifies the link between this problem and the BCJR decoding algorithm.

The current best asymptotic lower bound on the minimum distance of quantum LDPC codes with a fixed non-zero rate is logarithmic in the blocklength. We propose a construction of quantum LDPC codes with fixed non-zero rate and prove that the minimum distance grows proportionally to the square root of the blocklength.

We propose here a new construction of quantum codes combining an improved version of a family of spatially coupled quantum LDPC codes, suggested in [1], with a family of error reducing turbo-codes of [2]. This new construction displays outstanding performances under iterative decoding for noise levels very close to the hashing bound, without needing qubits, protected from noise as in [1].

In this work, we propose two McEliece variants: one from Moderate Density Parity-Check (MDPC) codes and another from quasi-cyclic MDPC codes. MDPC codes are LDPC codes of higher density (and worse error-correction capability) than what is usually adopted for telecommunication applications. However, in cryptography we are not necessarily interested in correcting many errors, but only a number which ensures an adequate security level. By this approach, we reduce under certain hypotheses the security of the scheme to the well studied decoding problem. Furthermore, the quasi-cyclic variant provides extremely compact-keys (for 80-bits of security, public-keys have only 4801 bits).

The Goppa Code Distinguishing (GD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. The hardness of this problem is an assumption to prove the security of code-based cryptographic primitives such as McEliece's cryptosystem. Up to now, it is widely believed that the GD problem is a hard decision problem. We present the first method allowing to distinguish alternant and Goppa codes over any field. Our technique can solve the GD problem in polynomial time provided that the codes have sufficiently large rates. The key ingredient is an algebraic characterization of the key-recovery problem. The idea is to consider the rank of a linear system which is obtained by linearizing a particular polynomial system describing a key-recovery attack. It appears that this dimension depends on the type of code considered. Explicit formulas derived from extensive experimentations for the rank are provided for “generic” random, alternant, and Goppa codes over any field. Finally, we give theoretical explanations of these formulas in the case of random codes, alternant codes over any field of characteristic two and binary Goppa codes.

We generalize a construction of non-binary quantum LDPC codes over F2mdue to [KHIK11] and apply it in particular to toric codes. We obtain in this way not only codes with better rates than toric codes but also improve dramatically the performance of standard iterative decoding. Moreover, the new codes obtained in this fashion inherit the distance properties of the underlying toric codes and have therefore a minimum distance which grows as the square root of the length of the code for fixed m.

We propose here a new construction of spatially coupled quantum LDPC codes using a small amount of entangled qubit pairs shared between the encoder and the decoder which improves quite significantly all other constructions of quantum LDPC codes or turbo-codes with the same rate.

This paper deals with the design of low-rate sparse-graph codes, having a linear minimum distance d_{min} in the blocklength n. Its main contributions are: a) a necessary condition on a general family of sparse-graph codes with linear d_{min}; b) a justification of having degree-1 bits in the low-rate code structure; c) a new, efficient ensemble of low-rate sparse-graph codes with bits of degree 1, designed so that the necessary condition (a) is satisfied.

We construct here a new family of quantum codes related to serial turbo-codes which are excellent error-reducing codes under iterative decoding for very large channel noise values. Moreover we also show that this family of codes has unbounded minimum distance.

The Goppa Code Distinguishing (GCD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. Up to now, it is widely believed that the GCD problem is a hard decisional problem. We present the first technique allowing to distinguish alternant and Goppa codes over any field. Our technique can solve the GCD problem in polynomial-time provided that the codes have rates sufficiently large. The key ingredient is an algebraic characterization of the key-recovery problem. The idea is to consider the dimension of the solution space of a linearized system deduced from a particular polynomial system describing a key-recovery. It turns out that experimentally this dimension depends on the type of code. Explicit formulas derived from extensive experimentations for the value of the dimension are provided for “generic” random, alternant, and Goppa code over any alphabet. Finally, we give explanations of these formulas in the case of random codes, alternant codes over any field and binary Goppa codes.

We present two new algorithms for the reconstruction of turbo codes from a noisy intercepted bitstream. With these algorithms, we were able to reconstruct various turbo codes with realistic parameter sizes. To the best of our knowledge, these are the first algorithms able to recover the whole permutation of a turbo code in the presence of high noise levels.

The current best asymptotic lower bound on the minimum distance of quantum LDPC codes with fixed non-zero rate is logarithmic in the block length. We build quantum LDPC codes with fixed non-zero rate and prove that their minimum distance grows proportionally to the square root of the block length.

In this paper, we present a theory of quantum serial turbo codes, describe their iterative decoding algorithm, and study their performances numerically on a depolarization channel. Our construction offers several advantages over quantum low-density parity-check (LDPC) codes. First, the Tanner graph used for decoding is free of 4-cycles that deteriorate the performances of iterative decoding. Second, the iterative decoder makes explicit use of the code's degeneracy. Finally, there is complete freedom in the code design in terms of length, rate, memory size, and interleaver choice. We define a quantum analogue of a state diagram that provides an efficient way to verify the properties of a quantum convolutional code, and in particular, its recursiveness and the presence of catastrophic error propagation. We prove that all recursive quantum convolutional encoders have catastrophic error propagation. In our constructions, the convolutional codes have thus been chosen to be noncatastrophic and nonrecursive. While the resulting families of turbo codes have bounded minimum distance, from a pragmatic point of view, the effective minimum distances of the codes that we have simulated are large enough not to degrade the iterative decoding performance up to reasonable word error rates and block sizes. With well-chosen constituent convolutional codes, we observe an important reduction of the word error rate as the code length increases.

This article deals with the problem of quantifying how many noisy codewords have to be eavesdropped in order to reverse engineer a code. The main result of this paper is a lower bound on this quantity and the proof that this number is logarithmic in the length for LDPC codes.

We present a theory of quantum serial turbo-codes and study their performance numerically on a depolarization channel. These codes can be considered as a generalization of classical serial turbo-codes. As their classical cousins, they can be iteratively decoded and with well chosen constituent convolutional codes, we observe an important reduction of the word error rate as the number of encoded qubits increases. Our construction offers several advantages over quantum LDPC codes. First, the Tanner graph used for decoding can be chosen to be free of 4-cycles that deteriorate the performances of iterative decoding. Secondly, the iterative decoder makes explicit use of the code's degeneracy. Finally, there is complete freedom in the code design in terms of length, rate, memory size, and interleaver choice. We address two issues related to the encoding of convolutional codes that are directly relevant for turbo-codes, namely the character of being recursive and non-catastrophic. We define a quantum analogue of a state diagram that provides an efficient way to verify these properties on a given quantum convolutional encoder. Unfortunately, we also prove that all recursive quantum convolutional encoder have catastrophic error propagation. In our constructions, the convolutional codes have thus been chosen to be non-catastrophic and non-recursive. While the resulting families of turbo-codes have bounded minimum distance, from a pragmatic point of view the effective minimum distances of the codes that we have simulated are large enough for not degrading iterative decoding performance up to reasonable word error rates and block sizes.

We generalize the results about how to compute iterative decoding thresholds over the binary erasure channel of non-binary LDPC code ensembles of [16] to non-binary TLDPC codes [2], [3]. We show in this case how density evolution can be performed in order to calculate iterative decoding thresholds and find several families with a very simple regular structure and thresholds close to the Shannon limit. To check the performances of these codes over other channels we have tested one of the simplest codes over F4which has rate 1/2 on the Gaussian channel. For the (binary) length 1008 for instance, without any optimization on the permutation structure of the code, it matches the performances of the best binary codes of the same length up to the word-error rate 10-3. We also notice that all LDPC codes (binary or not) having at least two symbols of degree 2 per parity-check equation can be represented as a special kind of TLDPC codes. We show that this representation and the associated decoding algorithm leads in the case of cycle codes to a significant reduction of the number of iterations which are needed for iterative decoding.

A generic method for constructing quantum LDPC codes is presented. We first explain how to overcome the difficulty of finding a set of low weight generators for the stabilizer group of the code. Our approach is based on a graph representation of the generators of the stabilizer group and on a simple local rule to ensure commutativity. We provide several specific examples of quantum LDPC codes obtained by our method, together with numerical simulations over the depolarizing channel and the erasure channel.

We study necessary conditions which have to be satisfied in order to have LDPC codes with linear minimum distance. We give two conditions of this kind in this paper. These conditions are not met for several interesting code families: this shows that they are not asymptotically good. The second one concerns LDPC codes that have a Tanner graph in which there are cycles linking variable nodes of degree 2 together and provides some insight about the combinatorial structure of some low-weight codewords in such a case. When the LDPC code family is obtained from the lifts of a given protograph and if there are such cycles in the protograph, the second condition seems to capture really well the linear minimum distance character of the code. This is illustrated by a code family which is asymptotically good for which there is a cycle linking all the variable nodes of degree 2 together. Surprisingly, this family is only a slight modification of a family which does not satisfy the second condition.

We investigate a new class of codes which is in a sense a hybrid between LDPC codes and turbo-codes. Some members of this new class have been shown to be asymptotically good and we conjecture that such a behavior holds for all classes of codes presented here. They all display excellent iterative decoding performances with no error floor at block error rates up to 10-6 for lengths of several thousand together with low average decoding complexity.

We investigate the minimum distance of structured LDPC codes with two variable nodes of degree 2 per parity-check equation and show that their minimum distance is a sub-linear power function of the code length

We investigate a new class of codes which is in some senses a hybrid between LDPC codes and turbo-codes. We show that when the parameters of this class are well chosen they have very good iterative decoding performances and at the same time a minimum distance which is typically linear in the code length

In this paper we describe several theorems that give lower bounds on the second eigenvalue of any quotient of a given size of a fixed graph, G. These theorems generalize Alon--Boppana-type theorems, where G is a regular (infinite) tree. When G is a hypercube, our theorems give minimum distance upper bounds on linear binary codes of a given size and information rate. Our bounds at best equal the current best bounds for codes and apply only to linear codes. However, it is of interest to note that (1) one very simple Alon--Boppana argument yields nontrivial code bound, and (2) our Alon--Boppana argument that equals a current best bound for codes has some hope of improvement. We also improve the bound in sharpest known Alon--Boppana theorem (i.e., when G is a regular tree).

This paper computes the asymptotic average weight distribution of Tanner code ensembles. The result obtained generalizes formulas, which were known for LDPC code ensembles. Also derive sufficient conditions ensuring that such a family contains a subfamily, which is asymptotically good and a ways to modify them to improve their weight distribution.

The Gaussian isoperimetric inequality states that among all sets in /spl Ropf//sup n/ with prescribed Gaussian measure, the half-spaces have minimal Gaussian perimeter. We apply this result to Voronoi regions of codes in Euclidean space and obtain a surprisingly precise description of how the maximum-likelihood decoding error probability varies as a function of the minimum Euclidean distance.

We aim here to show how some known Ramanujan Cayley graphs yield error-correcting codes that are asymptotically optimal in the class of cycle codes of graphs. The main reason why known constructions of Ramanujan graphs yield good cycle codes is that the number of their cycles of a given length behaves essentially like that of random regular graphs. More precisely, we show that for actual constructions of Ramanujan graphs of degree $\Delta$ which are bipartite, and for the double cover of known Ramanujan graphs which are not bipartite,the number of cycles of length 2l is $\BigOe(\Delta-1+\varepsilon)^{2l}$ (for every $\varepsilon > 0$), which is about what one could expect from a random regular graph of degree $\Delta$. Furthermore, it is possible to show that this property guarantees the highest possible error probability p that the corresponding cycle codes can sustain, among the class of cycle codes of $\Delta$-regular graphs. This gives a constructive answer to an early problem in coding theory, namely, determining what is asymptotically the best possible performance of cycle codes of graphs when submitted to the binary symmetric channel.