betaFeedback

WorksComputer Science

A polynomial-time decoding algorithm up to half the square-root bound for quadratic residue and generalized quadratic residue codes

Abstract

Binary quadratic residue (QR) codes, introduced by Prange in 1958, are cyclic codes of prime length p≡±1(mod8)p\equiv\pm1\pmod 8 and dimension (p+1)/2(p+1)/2 whose minimum distance satisfies the square-root bound d≥pd\ge\sqrt p. They include the Hamming code [7,4,3][7,4,3] and the Golay code [23,12,7][23,12,7], and were generalized by van Lint and MacWilliams to generalized quadratic residue (GQR) codes of prime-power length qq, for which the bound d≥qd\ge\sqrt q still holds and is attained when qq is a square. In coding theory, one usually first finds a lower bound on the minimum distance of a family of codes, and then a polynomial-time algorithm decoding up to half of this bound, as for BCH, Reed–Muller or Gabidulin codes. Until now, GQR codes had resisted this approach: no such algorithm was known, apart from individual short lengths. We give a deterministic algorithm which, for every odd prime power q≡±1(mod8)q\equiv\pm1\pmod 8, corrects every error pattern of weight at most ⌊(q−1)/2⌋\lfloor(\sqrt q-1)/2\rfloor in the binary GQR code of length qq, in O(q9/2)O(q^{9/2}) operations in \F_q. We start from a description of QR codes due to Helleseth, which we extend to GQR codes, and in which the syndrome gives the values of the quadratic character of the error-locator polynomial. We then recover this polynomial by adapting to GQR codes the tools that Kopparty developed for recovering polynomials from noisy character values, with the decoding of dual BCH codes as an application. Since the square-root bound is attained when qq is a square, this radius is the largest that can be guaranteed uniformly on the class of GQR codes.

Introduction

Quadratic residue codes

Quadratic residue (QR) codes were introduced by Prange in 1958 [30] and form one of the oldest families of algebraic error-correcting codes. The idea of the construction is elementary. Take a prime pp, index the pp coordinates of a binary word by the elements of Fp\mathbb{F}_p, and split the nonzero elements of Fp\mathbb{F}_p into the set QQ of squares and the set NN of non-squares. A binary cyclic code of length pp is determined by the set of exponents aa such that ζa\zeta^a is a root of all its codewords, where ζ\zeta is a primitive pp-th root of unity; the QR code is the cyclic code for which this set is QQ. The construction makes sense as soon as 2 is a square modulo pp, that is for p≡±1(mod8)p \equiv\pm1 \pmod{8}, and it gives a code of dimension (p+1)/2(p+1)/2, hence of rate just above 1/21/2. The precise definition is recalled in § 2.

Van Lint and MacWilliams [38] extended the construction from primes to prime powers q=pmq=p^m: the coordinates are now indexed by the elements of Fq\mathbb{F}_q, and the code is defined from the squares of Fq∗\mathbb{F}_q^*. These generalized quadratic residue (GQR) codes exist in the binary case for q≡±1(mod8)q \equiv\pm1 \pmod{8}, have dimension (q+1)/2(q+1)/2, and are invariant under the translations of Fq\mathbb{F}_q; they are no longer cyclic when m≥2m \ge2.

QR codes have been generalized in two other directions, which we only mention. Duadic codes [25] are the cyclic codes of odd length nn obtained by replacing the pair (Q,N)(Q,N) by any partition of the nonzero residues modulo nn into two unions of cyclotomic classes exchanged by a multiplication x↦axx \mapsto ax; they exist when 22 is a square modulo nn and still satisfy a square-root bound. Double circulant quadratic residue codes [21, 14] are the codes of length 2p2p and dimension pp with generator matrix [I∣W][I \mid W], where WW is the circulant matrix defined by the squares modulo pp; they exist for every odd prime pp, in particular for p≡±3(mod8)p \equiv\pm3 \pmod{8} where there is no QR code, and they also satisfy square-root bounds [6, 18]. In this paper we only consider QR and GQR codes.

Minimum distance of QR and GQR codes

The minimum distance dqd_q of a GQR code of length qq satisfies the square-root bound

dq2≥q,d_q^2 \ge q,

proved in [26], Ch. 16 for q=pq=p, where it is refined to dp2−dp+1≥pd_p^2-d_p+1 \ge p when p≡7(mod8)p \equiv7 \pmod{8}, and in [38] for general qq. How far this bound is from the truth depends on the case.

When qq is a square, the bound is attained: dq=qd_q=\sqrt{q}, the minimum being reached by a codeword whose support is the set of roots of Xq+XX^{\sqrt{q}}+X, a one-dimensional Fq\mathbb{F}_{\sqrt{q}}-subspace of Fq\mathbb{F}_q [38] (see also the final remark of [39]).

When q=pq=p is prime, the bound cannot be attained since p\sqrt{p} is not an integer. The refined bound is attained for p=7p=7, but for the next lengths the minimum distance is much larger, for instance 77 for p=23p=23, 1111 for p=47p=47 and 1717 for p=89p=89, whereas 89<10\sqrt{89}<10. Asymptotically very little is known. Only minor improvements of the lower bound are known [26, 18, 39], and it is not known whether there is an asymptotically good subfamily of QR codes [39]. For comparison, a random binary linear code of rate 1/21/2 and length nn has minimum distance close to the Gilbert–Varshamov value ≈0.11 n\approx0.11\,n, that is about n/9n/9 [26]. In the other direction, Voloch Voloch [39] proved that for infinitely many primes pp the QR code of length pp has minimum distance O(p/log⁡log⁡p)O(p/\log\log p), and O(p/log⁡p)O(p/\log p) under the generalized Riemann hypothesis; he also states, without proof, that there are infinitely many non-square prime powers qq for which dq=O(q/log⁡q)d_q=O(q/\log q).

The square-root bound is thus the only guarantee available for the whole family of GQR codes, and on the whole family it cannot be improved.

A remarkable family of codes

A bound in q\sqrt{q} may look modest, but QR codes are remarkable in five respects, which we recall in turn: their parameters, their symmetries, their weight enumerators, their connection with number theory and lattices, and their relation with quantum codes.

Parameters. At short lengths the parameters of QR codes are excellent: the Hamming code [7,4,3][7,4,3] and the Golay code [23,12,7][23,12,7], which are both perfect, and the [47,24,11][47,24,11] code are QR codes [26]. They remain good well beyond these lengths, and they exist for many lengths for which there is no BCH code. For instance the QR code of length 103103 has parameters [103,52,19][103,52,19], whereas shortening the BCH code [127,71,19][127,71,19] to the same length and the same minimum distance only gives a [103,47,19][103,47,19] code, and the QR code of length 199199 improved the best minimum distance known for its length and dimension [36]. Beyond length 200200, however, the minimum distances and estimates available [36] suggest that QR codes fall behind BCH codes of comparable length and rate.

Symmetries. Add an overall parity check to the QR code of length pp, and index the p+1p+1 coordinates of the extended code by the projective line Fp∪{∞}\mathbb{F}_p \cup\{\infty\}. By the Gleason–Prange theorem, the extended code is invariant under the group PSL⁡2(p)\operatorname{PSL}_2(p) acting on the projective line [26 Ch. 16]. This group is much larger than the group of cyclic shifts, and it is doubly transitive, so that all the coordinates of the extended code play the same role. For the lengths 24 and 48, the supports of the codewords of any given weight even form 5-designs [1].

Weight enumerators. For p≡7(mod8)p \equiv7 \pmod{8} the extended QR code is self-dual and doubly even, that is, all its weights are divisible by 4 [26, 31]. A doubly-even self-dual code of length nn has minimum distance at most 4⌊n/24⌋+44\lfloor n/24 \rfloor+ 4, and is called extremal when this value is reached; by Gleason’s theorem, the weight enumerator of an extremal code is completely determined by its length [31]. The extended QR codes are extremal for all their lengths up to 48, namely 8, 24, 32 and 48, and again for the lengths 80 and 104 [31], so that their weight enumerators are known explicitly. The extended QR code of length 48 is moreover the only extremal doubly-even self-dual code of this length [20].

Connection with number theory and lattices. QR codes are arithmetic objects. Their weights are sums of Legendre symbols, which count the points of hyperelliptic curves over Fp\mathbb{F}_p, and this is how the Weil bound gives back the square-root bound [17, 18]; the asymptotically bad subfamilies of [39] are obtained from the Chebotarev density theorem. These very good codes are also connected to very good lattices: the extended Hamming code [8,4,4][8, 4, 4] gives the lattice E8E_8, the extended Golay code [24,12,8][24, 12, 8] gives the Leech lattice, and the extended ternary QR code of length 48 gives an extremal unimodular lattice in dimension 48 [10].

Quantum codes. Finally, for p≡7(mod8)p \equiv7 \pmod{8} the QR code of length pp contains its dual, which is its subcode of even weight words [26]. The Calderbank–Shor–Steane construction then gives a quantum code encoding one qubit into pp qubits with minimum distance dpd_p; for p=7p=7 and p=23p=23 these are the Steane code [[7,1,3]][[7,1,3]] and the quantum Golay code [[23,1,7]][[23,1,7]] [35].

Distance bounds and decoding

For most classical families of codes, a lower bound on the minimum distance has been followed by a polynomial-time algorithm decoding up to half of this bound. BCH codes were introduced by Hocquenghem [19] and by Bose and Ray-Chaudhuri [4] together with the BCH bound, which guarantees a minimum distance at least the designed distance δ\delta; Peterson [29] and Gorenstein and Zierler [15] then gave an algebraic decoder correcting ⌊(δ−1)/2⌋\lfloor(\delta-1)/2\rfloor errors, made efficient by the Berlekamp–Massey algorithm [3, 27]. Reed–Muller codes were defined by Muller [28], and Reed [32] gave the same year a majority-logic decoder correcting up to half their minimum distance. In rank metric, Delsarte [11] introduced maximum rank distance codes as spaces of bilinear forms, and Gabidulin [13] later decoded them up to half their minimum rank distance. Gabidulin’s codes are linear over an extension field, a point of view that Delsarte did not adopt, so the two families do not coincide exactly, but the sequence is the same: first a bound, then a decoder.

Until now, QR codes were an exception: no polynomial-time algorithm decoding up to half the square-root bound was known. The existing algebraic decoders treat one length at a time. They recover the syndromes that the code does not provide through Newton’s identities and then compute the error-locator polynomial; this was done by Elia [12] for the Golay code, and by Reed, Truong and their coauthors for the lengths 31, 41, 47, 71, 79, 89 and 97 [34, 33, 16, 8, 37]. Gröbner bases can automate the derivation of such formulas [9, 2], and permutation decoding uses the large automorphism group for selected parameters [5], but none of these methods comes with a complexity bound polynomial in the length. The BCH decoder does not help either: it needs consecutive elements in the defining set, and if the values of the quadratic character are modelled as independent balanced signs, the longest runs of consecutive squares modulo pp have length O(log⁡p)O(\log p), far below the square-root scale; this is only a heuristic, the arithmetic of such runs being itself a difficult problem [22]. Finally, generic decoders such as information-set decoding have a cost of the form 2Θ(n)2^{\Theta(\sqrt{n})} for Θ(n)\Theta(\sqrt{n}) errors at rate 1/21/2 [7].

There is one more reason to look for a decoder of QR codes. Kudekar, Kumar, Mondelli, Pfister, Şaşoğlu and Urbanke [24] proved that any sequence of binary linear codes of increasing lengths, whose rates converge and whose permutation groups are doubly transitive, achieves capacity on the binary erasure channel under bit-MAP decoding. By the Gleason–Prange theorem this applies to extended QR codes, as noted in [24]. QR codes are therefore asymptotically optimal for erasures, which are corrected by linear algebra, although nothing comparable is known for their minimum distance or for the correction of errors.

Contribution

We give the first polynomial-time decoding algorithm valid for the whole family of binary QR and GQR codes.

Main result (Theorem 3.1). For every odd prime power q≡±1(mod8)q \equiv\pm1 \pmod{8}, there is a deterministic algorithm that corrects any ⌊(q−1)/2⌋\lfloor(\sqrt{q}-1)/2\rfloor errors in the binary QR code of length qq when qq is prime, and more generally in the binary GQR code of length qq, in O(q9/2)O(q^{9/2}) operations in Fq\mathbb{F}_q.

The algorithm has two ingredients.

The first one is a description of QR codes due to Helleseth [17], different from the classical one, in which the error positions are elements of Fp\mathbb{F}_p and are the roots of a polynomial fEf_E with coefficients in Fp\mathbb{F}_p; in this description, the syndrome of the received word gives the value of the quadratic character of fEf_E at every point which is not an error position. Helleseth’s description is given for prime lengths, and we extend it to all GQR codes. Decoding then amounts to recovering a polynomial of small degree over Fq\mathbb{F}_q from the values of its quadratic character.

The second ingredient is the set of tools recently developed by Kopparty [23] for recovering low-degree polynomials from noisy character values, which he applied in particular to the decoding of dual BCH codes; they combine Hasse derivatives, multiplicity estimates and Stepanov’s polynomial method. We do not apply Kopparty’s algorithm as it stands: we adapt his method to the case of GQR codes, in which the character values are known exactly outside the roots of fEf_E and are not known at these roots. Kopparty’s algorithm recovers a monic squarefree polynomial of degree at most (ϵ/16)q(\epsilon/16)\sqrt{q} from the values of its quadratic character, a proportion 1/8−ϵ1/8-\epsilon of which may be wrong [23], Theorem 3.1. In our situation the polynomial is split and the only unknown values are at its roots; with parameters chosen for this case we reach the degree ⌊(q−1)/2⌋\lfloor(\sqrt{q}-1)/2\rfloor which is needed to decode up to half the square-root bound, and we do not need to factor polynomials. We write a linear system whose unknowns are a polynomial and its Hasse derivatives, we show that a suitable power of fEf_E is a nonzero solution, and that the error positions can be read on the multiplicities of the roots of any nonzero solution.

This result places GQR codes in the classical situation described above. The algorithm applies to the whole class of GQR codes and decodes up to half the square-root bound; since this bound is attained when qq is a square, no larger decoding radius can be guaranteed for the class as a whole, and for qq a square the algorithm corrects up to half the true minimum distance. To the best of our knowledge, the existence of a polynomial-time decoding algorithm valid for the whole family had been open since the introduction of QR codes, more than sixty years ago. For QR codes of prime length, where the minimum distance is a priori larger than p\sqrt{p} but no better bound is available, decoding beyond p/2\sqrt{p}/2 errors remains an open problem.

Organization. § 2 recalls the classical definition of QR codes and presents Helleseth’s description for prime lengths. § 3 extends this description to GQR codes and states the main result. Section 4 gives the identity between syndromes and character values, Section 5 the lemma on Hasse derivatives and multiplicities, and Section 6 the algorithm and its analysis.

Quadratic residue codes: the classical definition and Helleseth's description

In this section pp is a prime with p≡±1(mod8)p \equiv\pm1 \pmod{8}, and QQ and NN are the sets of nonzero squares and non-squares of Fp\mathbb{F}_p. A binary word of length pp is seen as a function f:Fp→F2f:\mathbb{F}_p \to\mathbb{F}_2, and is identified with the element ∑x∈Fpf(x)Xx\sum_{x\in\mathbb{F}_p} f(x)X^x of the group algebra R=F2[Fp]\mathcal{R}=\mathbb{F}_2[\mathbb{F}_p], which is here the ring F2[X]/(Xp−1)\mathbb{F}_2[X]/(X^p-1). For a subset EE of Fp\mathbb{F}_p we denote by 1E\mathbf{1}_E its indicator function.

The classical definition

We first recall how binary cyclic codes are described by cyclotomic classes. Let ζ\zeta be a primitive pp-th root of unity in F2r\mathbb{F}_{2^r}, where rr is the order of 22 in Fp∗\mathbb{F}_p^*. The Fourier transform of f:Fp→F2f:\mathbb{F}_p \to\mathbb{F}_2 is the function f^:Fp→F2r\widehat{f}:\mathbb{F}_p \to\mathbb{F}_{2^r} defined by

f^(a)=∑x∈Fpf(x)ζax,\widehat{f}(a)=\sum_{x\in\mathbb{F}_p}f(x)\zeta^{ax},

so that f^(a)\widehat{f}(a) is the value at ζa\zeta^a of the polynomial associated with ff. The cyclotomic class of a∈Fpa\in\mathbb{F}_p is the set {a,2a,4a,…}\{a,2a,4a,\ldots\}. Since ff is binary, f^(2a)=f^(a)2\widehat{f}(2a)=\widehat{f}(a)^2, hence the set of zeros of f^\widehat{f} is a union of cyclotomic classes. A binary cyclic code of length pp is defined by a union TT of cyclotomic classes, called its defining set: it is the code

{f:Fp→F2:f^(a)=0 for all a∈T},\{f:\mathbb{F}_p\to\mathbb{F}_2:\widehat{f}(a)=0\text{ for all }a\in T\},

which has dimension p−∣T∣p-|T|.

The condition p≡±1(mod8)p\equiv\pm1\pmod{8} means that 2∈Q2\in Q, so that the cyclotomic class of a square is contained in QQ: the set QQ is a union of cyclotomic classes, and so is NN. The binary QR codes of length pp are the cyclic codes with defining sets QQ and NN,

CQ={f:f^(a)=0 ∀a∈Q},CN={f:f^(a)=0 ∀a∈N}.C_Q=\{f:\widehat{f}(a)=0\ \forall a\in Q\},\qquad C_N=\{f:\widehat{f}(a)=0\ \forall a\in N\}.

As ∣Q∣=∣N∣=(p−1)/2|Q|=|N|=(p-1)/2, they have dimension (p+1)/2(p+1)/2, and they are equivalent through the permutation x↦sxx\mapsto sx of the coordinates for any s∈Ns\in N. For p=7p=7 the cyclotomic classes are {0}\{0\}, Q={1,2,4}Q=\{1,2,4\} and N={3,5,6}N=\{3,5,6\}, and CQC_Q is the Hamming code [7,4,3][7,4,3]. For p=23p=23 the sets QQ and NN are themselves cyclotomic classes, with 11 elements, and CQC_Q is the Golay code [23,12,7][23,12,7].

In this description, the natural syndromes of a received word y=c+1Ey=c+\mathbf{1}_E, where c∈CQc\in C_Q and EE is the set of error positions, are the values y^(a)=1E(a)\widehat{y}(a)=\mathbf{1}_E(a) for a∈Qa\in Q. They belong to the field F2r\mathbb{F}_{2^r}, whose degree rr can be as large as (p−1)/2(p-1)/2, and the error positions appear as exponents of ζ\zeta. The defining set QQ contains no long sequence of consecutive integers, so the BCH bound and the BCH decoder give very little, and the values 1E(a)\mathbf{1}_E(a) for a∈Na\in N, which would be needed to compute the error-locator polynomial by Newton's identities, are not available. This is the obstacle met by all the decoders of QR codes based on the classical description.

Helleseth's description

Helleseth [17] proposed to look at QR codes differently: the error positions are kept as elements of Fp\mathbb{F}_p, and one uses the arithmetic of Fp\mathbb{F}_p itself instead of that of F2r\mathbb{F}_{2^r}. This is the point of view from which we start.

We first need a description of the code that does not involve ζ\zeta. Let eQ=∑r∈QXr∈Re_Q=\sum_{r\in Q}X^r\in\mathcal{R}, and let

AQ=(1Q(x−y))x,y∈FpA_Q=(\mathbf{1}_Q(x-y))_{x,y\in\mathbb{F}_p}

be the matrix of the multiplication by eQe_Q in R\mathcal{R}. Since 2Q=Q2Q=Q, we have eQ2=eQe_Q^2=e_Q, hence AQ2=AQA_Q^2=A_Q. The ideal of R\mathcal{R} generated by eQe_Q when p≡7(mod8)p\equiv7\pmod{8}, and by 1+eQ1+e_Q when p≡1(mod8)p\equiv1\pmod{8}, is a QR code [26 Ch. 16], namely CQC_Q or CNC_N according to the choice of ζ\zeta. As these elements are idempotents, a parity-check matrix of this code is

Hp=δI+AQ,with δ=1 if p≡7(mod8) and δ=0 if p≡1(mod8),H_p=\delta I+A_Q,\qquad\text{with }\delta=1\text{ if }p\equiv7\pmod{8}\text{ and }\delta=0\text{ if }p\equiv1\pmod{8},

and the syndrome of a word y=c+1Ey=c+\mathbf{1}_E is the binary vector s=Hpy=Hp1Es=H_py=H_p\mathbf{1}_E, whose coordinates sxs_x are indexed by x∈Fpx\in\mathbb{F}_p.

Let now E⊂FpE\subset\mathbb{F}_p be a set of error positions, of size dd. We associate with EE the polynomial

fE(X)=∏a∈E(X−a)∈Fp[X].f_E(X)=\prod_{a\in E}(X-a)\in\mathbb{F}_p[X].

Contrary to the classical error-locator polynomial, fEf_E has its coefficients in Fp\mathbb{F}_p, a field whose size is the length of the code. Let χ\chi be the Legendre symbol modulo pp, and let x∈Fp∖Ex\in\mathbb{F}_p\setminus E. On the one hand, each factor χ(x−a)\chi(x-a) of χ(fE(x))\chi(f_E(x)) equals 11 if x−a∈Qx-a\in Q and −1-1 if x−a∈Nx-a\in N. On the other hand, by definition of AQA_Q, the coordinate sxs_x is the parity of the number of a∈Ea\in E such that x−a∈Qx-a\in Q. Comparing the two gives Helleseth’s identity, in the pointwise form which appears in the proof of [18 Lemma 2],

(−1)sx=(−1)dχ(fE(x))for every x∈Fp∖E.(1)(-1)^{s_x}=(-1)^d\chi(f_E(x))\qquad\text{for every }x\in\mathbb{F}_p\setminus E. \tag*{(1)}

Helleseth used this relation to express the weights of the words AQ1EA_Q\mathbf{1}_E as sums of Legendre symbols, which gives back the square-root bound through the Weil bound.

For decoding, the consequence is the following: the syndrome gives the values of χ∘fE\chi\circ f_E at all the points of Fp\mathbb{F}_p outside EE, and decoding amounts to recovering the polynomial fEf_E, which is squarefree, split and of degree dd, from these values. This is a problem of reconstruction of a polynomial from character values, of the type considered by Kopparty [23]. The description involves neither the extension field F2r\mathbb{F}_{2^r} nor the cyclic structure.

Generalized quadratic residue codes and the main result

Extension of Helleseth’s description to GQR codes

Helleseth’s description is stated for prime lengths and does not cover GQR codes. Voloch states in [39] that Helleseth’s lemma has a generalization to the generalized quadratic residue codes of van Lint and MacWilliams, sketched in [18]; however [18] only deals with prime lengths, and to the best of our knowledge this generalization has not been written down. We do it in this section, with the notation of § 2: the field Fp\mathbb{F}_p is replaced by Fq\mathbb{F}_q, the functions x↦ζaxx\mapsto\zeta^{ax} by the additive characters x↦ζTr⁡(ax)x\mapsto\zeta^{\operatorname{Tr}(ax)} of Fq\mathbb{F}_q, and the Legendre symbol by the quadratic character of Fq\mathbb{F}_q. For q=pq=p the definitions below are those of § 2, and the identity (1) becomes Proposition 4.1.

Let q=pmq=p^m be a prime power, where pp is odd and 22 is a square in Fq\mathbb{F}_q, which is equivalent to assuming that q≡±1(mod8)q\equiv\pm1\pmod{8}. We denote by QQ the set of squares of Fq∗\mathbb{F}_q^* and by NN the set of non-squares of Fq∗\mathbb{F}_q^*. Let Tr⁡\operatorname{Tr} denote the trace from Fq\mathbb{F}_q to Fp\mathbb{F}_p.

In this paper we investigate the decoding of the binary GQR-codes constructed as follows. Let us consider a primitive pp-th root of unity ζ∈F2r\zeta\in\mathbb{F}_{2^r}, where rr denotes the order of 22 in Fp∗\mathbb{F}_p^*, and associate with any function f:Fq→F2f : \mathbb{F}_q \to\mathbb{F}_2, its Fourier transform f^:Fq→F2r\widehat{f} : \mathbb{F}_q \to\mathbb{F}_{2^r} defined by

f^(a)=∑x∈Fqf(x)ζTr⁡(ax).\widehat{f}(a) = \sum_{x \in\mathbb{F}_q} f(x)\zeta^{\operatorname{Tr}(ax)}.

Let F\mathcal{F} be the set of functions from Fq→F2\mathbb{F}_q \to\mathbb{F}_2, identified with F2q\mathbb{F}_2^q hereafter, and E\mathcal{E} those from Fq→F2r\mathbb{F}_q \to\mathbb{F}_{2^r}. Consider the sub-vector spaces of F\mathcal{F}

CQ={f∈F2q:f^(a)=0 ∀a∈Q},CN={f∈F2q:f^(a)=0 ∀a∈N}.C_Q = \{f \in\mathbb{F}_2^q : \widehat{f}(a) = 0\ \forall a \in Q\}, \qquad C_N = \{f \in\mathbb{F}_2^q : \widehat{f}(a) = 0\ \forall a \in N\}.

These two codes are equivalent. To see that, it suffices to consider an element s∈Ns \in N and to associate with a function f∈CQf \in C_Q the function f(s−1x)f(s^{-1}x), whose Fourier transform is f^(sx)\widehat{f}(sx).

There is another way to view these codes. We consider elements eQe_Q and eNe_N in the group algebra R=F2[Fq]\mathcal{R} = \mathbb{F}_2[\mathbb{F}_q] given by eQ=∑r∈QXre_Q = \sum_{r \in Q} X^r and eN=∑r∈NXre_N = \sum_{r \in N} X^r, and the matrix of the multiplication (convolution) by eQe_Q:

AQ=(1Q(x−y))x,y∈Fq,A_Q = (1_Q(x-y))_{x,y \in\mathbb{F}_q},

where 1Q(x)=11_Q(x) = 1 for squares and 0 otherwise. As eQ2=eQe_Q^2 = e_Q, we see that AQ2=AQA_Q^2 = A_Q. The matrix AQA_Q generates the code CQC_Q or CNC_N if q≡7(mod8)q \equiv7 \pmod{8} and I+AQI + A_Q generates the code CQC_Q or CNC_N if q≡1(mod8)q \equiv1 \pmod{8}. As AQ2=AQA_Q^2 = A_Q, the control matrix is I+AQI + A_Q in the first case and AQA_Q in the second, that we denote by HqH_q.

Main result

From these facts, it is sufficient to treat the case of the code C=ker⁡HqC = \ker H_q in order to establish the following theorem.

Theorem 3.1. For any prime power q≡±1(mod8)q \equiv\pm1 \pmod{8}, the code CQC_Q, which is the binary QR code of length qq when qq is prime and the binary GQR code of length qq in general, is a code with parameters

[q,q+12,dq],\left[q,\frac{q+1}{2},d_q\right],

with dq≥qd_q \ge\sqrt{q}, for which there is a deterministic decoding algorithm for correcting any error of weight

t(q)=⌊q−12⌋t(q) = \left\lfloor\frac{\sqrt{q}-1}{2}\right\rfloor

running in O(q9/2)O(q^{9/2}) operations in Fq\mathbb{F}_q.

Before proving the theorem, we note that we present a uniform algorithm for all generalized QR codes. For q=s2q = s^2, the minimum distance is indeed ss and thus our algorithm decodes up to the error-correcting capability. Decoding QR codes (qq prime) beyond this radius remains an open problem.

We also present the main ideas behind the algorithm which is based on Helleseth observation and the Kopparty algorithm for recovering polynomials from character values. We map a received codeword to its syndrome and try to find an error vector it comes from. To achieve this, we only use the bound t(q)t(q) on the weight of its support.

If we build the split separable polynomial whose set of roots matches the support of the error, that we call EE, and use a (slightly generalized) observation of Helleseth, we find that a large power of this polynomial is part of a solution of a linear system involving it and its Hasse derivatives. Thus we solve the linear system for d=t(q)d = t(q) and recover the support of the error from a solution. At the end, we know that if the number of errors is below the decoding radius, we will find the right one.

Character-syndrome identity

The first ingredient of our proof is an identity that links syndrome and character values of separable split polynomials. Let us denote by χ\chi the quadratic character of Fq\mathbb{F}_q and recall that χ(x)=xq−12\chi(x)=x^{\frac{q-1}{2}} for any x∈Fqx\in\mathbb{F}_q. We use the following notation, for any subset EE of Fq\mathbb{F}_q:

fE(X)=∏a∈E(X−a).f_E(X)=\prod_{a\in E}(X-a).

Our algorithm will be partly based on the following identities due to Helleseth [17] (stated in the case of q=pq=p, see also the proof of Lemma 2 in [18]). We are only going to use the first one in our algorithm.

Proposition 4.1. Let E⊂FqE\subset\mathbb{F}_q, d=∣E∣d=|E|, s=Hq1Es=H_q\mathbf{1}_E, δ=0\delta=0 if q≡1(mod8)q\equiv1\pmod8 and δ=1\delta=1 if q≡7(mod8)q\equiv7\pmod8. Then

∀x∉E, (−1)sx=(−1)dχ(fE(x))and∀x∈E, (−1)sx=(−1)d+δ−1χ(fE′(x)).\forall x\notin E,\ (-1)^{s_x}=(-1)^d\chi(f_E(x)) \qquad\text{and}\qquad\forall x\in E,\ (-1)^{s_x}=(-1)^{d+\delta-1}\chi(f'_E(x)).

Proof. Let x∉Ex\notin E. Then sx=∑y∈Fq(δI+AQ)x,y1E(y)=∑y∈E1Q(x−y)s_x=\sum_{y\in\mathbb{F}_q}(\delta I+A_Q)_{x,y}\mathbf{1}_E(y)=\sum_{y\in E}\mathbf{1}_Q(x-y). Thus

(−1)sx=∏y∈E(−1)1Q(x−y)=∏y∈E(−χ(x−y))=(−1)dχ(fE(x)).(-1)^{s_x}=\prod_{y\in E}(-1)^{\mathbf{1}_Q(x-y)}=\prod_{y\in E}(-\chi(x-y))=(-1)^d\chi(f_E(x)).

Now let x∈Ex\in E. Then sx=∑y∈Fq(δI+AQ)x,y1E(y)=δ+∑y∈E∖{x}1Q(x−y)s_x=\sum_{y\in\mathbb{F}_q}(\delta I+A_Q)_{x,y}\mathbf{1}_E(y)=\delta+\sum_{y\in E\setminus\{x\}}\mathbf{1}_Q(x-y). Thus

(−1)sx=(−1)δ∏y∈E∖{x}(−1)1Q(x−y)=(−1)δ∏y∈E∖{x}(−χ(x−y))=(−1)δ+d−1χ(fE′(x)).\begin{aligned} (-1)^{s_x} &=(-1)^\delta\prod_{y\in E\setminus\{x\}}(-1)^{\mathbf{1}_Q(x-y)} =(-1)^\delta\prod_{y\in E\setminus\{x\}}(-\chi(x-y))\\ &=(-1)^{\delta+d-1}\chi(f'_E(x)). \end{aligned}

Note that these equalities give the lower bound q\sqrt{q} through an application of the Weil bounds.

The second ingredient is an application of the Kopparty algorithm for reconstructing a polynomial from character values of evaluation of this polynomial. As we need here a stronger error-free version of this algorithm, let us use directly Kopparty’s ideas and recover this algorithm in our setting.

Hasse derivatives and multiplicities

Let us start with a technical lemma on Hasse derivatives allowing to deal with multiplicities of roots of polynomials.

Recall that the jjth-Hasse derivatives of P∈Fq[X]P\in\mathbb{F}_q[X], are the polynomial P[j]P^{[j]} such that

P(X+T)=∑j≥0P[j](X)Tj.P(X+T)=\sum_{j\geq0}P^{[j]}(X)T^j.

Lemma 5.1. Let M≥1M\geq1, K≥0K\geq0 such that K+M≤qK+M\leq q, and 0≠W∈Fq[X]0\ne W\in\mathbb{F}_q[X] with deg⁡W<Mq\deg W<Mq. Assume that for any 0≤j<M0\leq j<M, there is a polynomial Pj∈Fq[X]P_j\in\mathbb{F}_q[X] of degree at most KK such that W[j]=Pj(modΛ)W^{[j]}=P_j\pmod{\Lambda}, where Λ=Xq−X\Lambda=X^q-X. Then for every a∈Fqa\in\mathbb{F}_q,

mult⁡a(W)(modq)≤K+M−1.\operatorname{mult}_a(W)\pmod q\leq K+M-1.

where mult⁡a\operatorname{mult}_a is the multiplicity of aa as a root of WW and the integers modulo qq are identified with {0,…,q−1}\{0,\ldots,q-1\}.

Let us prove this lemma which is about Hasse derivatives, polynomials and pseudopolynomials. It is a version at the points of Fq\mathbb{F}_q of [23 Lemma 3.3], combined with the observation of [23 Section 5.1] that the conditions on the first MM derivatives bound the degrees of the AiA_i.

Proof: Let Λ\Lambda be the polynomial Xq−XX^q-X. The condition on the degree of WW allows us to write WW as

W=∑i=0M−1AiΛi,W=\sum_{i=0}^{M-1} A_i\Lambda^i,

where AiA_i are polynomials of degree less than qq. As Λ(X+T)=Tq−T+Xq−X\Lambda(X+T)=T^q-T+X^q-X, it is clear that, Λ[j]=Λ\Lambda^{[j]}=\Lambda if j=0j=0, −1-1 if j=1j=1, 11 if j=qj=q, and 00 otherwise.

For k<M(≤q)k<M(\leq q), this computation and the Leibnitz rule on Hasse derivatives leads to

W[k]=∑i=0M−1(AiΛi)[k]=∑i=0M−1(−1)iAi[k−i](modΛ)W^{[k]}=\sum_{i=0}^{M-1}(A_i\Lambda^i)^{[k]}=\sum_{i=0}^{M-1}(-1)^iA_i^{[k-i]}\pmod{\Lambda}

(see [23 Lemma 2.4]) with the convention that Ai[k−i]=0A_i^{[k-i]}=0 if k−i<0k-i<0. As W[j]=Pj(modΛ)W^{[j]}=P_j\pmod{\Lambda}, with deg⁡Pj≤K\deg P_j\leq K, it follows by induction on ii that deg⁡Ai≤K\deg A_i\leq K, as it equals modulo Λ\Lambda a polynomial of degree less or equal to KK and is of degree strictly less than qq.

Let a∈Fqa\in\mathbb{F}_q. Recall that mult⁡a(W)=r\operatorname{mult}_a(W)=r if rr is the largest integer such that for all 0≤ℓ<r0\leq\ell<r, W[ℓ](a)=0W^{[\ell]}(a)=0. We have

∑i=0deg⁡WW[i](a)Ti=W(a+T)=∑i=0M−1Ai(a+T)(Tq−T)i=∑j=0M−1TqjCj(T).\sum_{i=0}^{\deg W}W^{[i]}(a)T^i=W(a+T)=\sum_{i=0}^{M-1}A_i(a+T)(T^q-T)^i=\sum_{j=0}^{M-1}T^{qj}C_j(T).

where

Cj(T)=∑i=jM−1(−1)i−j(ij)Ti−jAi(a+T),anddeg⁡Cj≤K+M−1−j≤q−1−j.C_j(T)=\sum_{i=j}^{M-1}(-1)^{i-j}\binom{i}{j}T^{i-j}A_i(a+T),\qquad\text{and}\qquad\deg C_j\leq K+M-1-j\leq q-1-j.

From the last inequality, we see that every term in the double sum has a different degree and that qj≤deg⁡TqjCj(T)≤q(j+1)−1−jqj\leq\deg T^{qj}C_j(T)\leq q(j+1)-1-j. Therefore, if j0j_0 is the smallest jj such that Cj≠0C_j\ne0, we see immediately that mult⁡a(W)=qj0+ord⁡TCj0\operatorname{mult}_a(W)=qj_0+\operatorname{ord}_T C_{j_0}, the latter being an integer smaller or equal to K+M−1−j0K+M-1-j_0. The lemma follows. □

The algorithm

In this section, we explain how to decode a received word. Assume that we received m=c+em=c+e where cc is a codeword. We compute s=Hqm=Hqes=H_qm=H_qe where ee is unknown. Let EE be its support; for T⊂FqT\subset\mathbb{F}_q we write eT=1Te_T=1_T. Let d≥0d\geq0 be an integer. It is a parameter of the interpolation below: it is fixed once and for all, and it will be taken equal to t(q)t(q) in the algorithm. We can compute the quantity

rd(x)=(−1)sx+d.r_d(x)=(-1)^{s_x+d}.

If ∣E∣=e|E|=e, we have χ(fE(x))=(−1)d−erd(x)\chi(f_E(x))=(-1)^{d-e}r_d(x) for any x∉Ex\notin E, χ(fE′(x))=(−1)d−e+δ−1rd(x)\chi(f'_E(x))=(-1)^{d-e+\delta-1}r_d(x) and χ(fE(x))=0\chi(f_E(x))=0 for any x∈Ex\in E (see Proposition 4.1). We know that this system admits at least a solution with a split polynomial of degree at most t(q)t(q) (by hypothesis). But the χ(fE(x))\chi(f_E(x)) are values of a polynomial of very large degree (it may be about q3/2/4q^{3/2}/4), so that recovering fEf_E from this system seems hopeless. This is why we use the ideas of Kopparty and build an other system taking into account the multiplicities of roots of fEf_E.

Let h=q−12h=\frac{q-1}{2} so that for any x∈Fqx\in\mathbb{F}_q, and any polynomial P∈Fq[X]P\in\mathbb{F}_q[X], Ph(x)=χ(P(x))P^h(x)=\chi(P(x)). Let d≥1d\geq1, and put

M=d+1,u=d2+d,D=dh+d2+d,rd(x)=(−1)d+sx.M=d+1,\qquad u=d^2+d,\qquad D=dh+d^2+d,\qquad r_d(x)=(-1)^{d+sx}.

Consider the Fq\mathbb{F}_q linear system with polynomial unknown (F,U0,…,UM−1)(F,U_0,\ldots,U_{M-1}) (it is the system of [23 Algorithm A], with parameters adapted to our situation)

{F[j](x)=rd(x)Uj(x)(∀x∈Fq, ∀0≤j<M),deg⁡F≤D,deg⁡Uj≤u(∀0≤j<M).(2)\begin{cases} F^{[j]}(x)=r_d(x)U_j(x) & (\forall x\in\mathbb{F}_q,\ \forall0\le j<M),\\ \deg F\le D,\\ \deg U_j\le u & (\forall0\le j<M). \tag*{(2)} \end{cases}

Proposition 6.1. If s=HqeEs=H_q e_E with ∣E∣=e≤d|E|=e\le d, the system (2) admits

F=fEh+M,Uj=(−1)d−eF[j]/fEhF=f_E^{h+M},\qquad U_j=(-1)^{d-e}F^{[j]}/f_E^h

as a non zero solution, and deg⁡Uj≤eM−j\deg U_j\le eM-j. For any s∈F2qs\in\mathbb{F}_2^q, if u<qu<q, every non zero solution of (2) satisfies F≠0F\ne0.

Proof. Let j<Mj<M. From the Leibnitz rule for Hasse derivatives, it is clear that fEh+M−j∣F[j]f_E^{h+M-j}\mid F^{[j]}, and therefore UjU_j are polynomials vanishing on EE and satisfying deg⁡Uj≤e(h+M)−j−eh=eM−j≤u\deg U_j\le e(h+M)-j-eh=eM-j\le u. Moreover deg⁡F=e(h+M)≤D\deg F=e(h+M)\le D. If x∉Ex\notin E, then rd(x)=(−1)d−eχ(fE(x))=(−1)d−efE(x)hr_d(x)=(-1)^{d-e}\chi(f_E(x))=(-1)^{d-e}f_E(x)^h by Proposition 4.1, so that F[j](x)=(−1)d−efE(x)hUj(x)=rd(x)Uj(x)F^{[j]}(x)=(-1)^{d-e}f_E(x)^hU_j(x)=r_d(x)U_j(x), and if x∈Ex\in E, then F[j](x)=0=rd(x)Uj(x)F^{[j]}(x)=0=r_d(x)U_j(x). If FF is zero and u<qu<q, the polynomials UjU_j have to be zero as they vanish on Fq\mathbb{F}_q and are of degree ≤u<q\le u<q.

Now that we know that the system has a solution, let us show how to get EE out of a solution. The argument follows the alternate analysis of [23 Section 5.6]: the product of two solutions behaves like a polynomial of low degree on Fq\mathbb{F}_q, together with its derivatives. We apply this to the product of an arbitrary solution by the particular one, and to the square of an arbitrary solution.

Proposition 6.2. Assume d≥1d\ge1 and q≥(2d+1)2q\ge(2d+1)^2. Let s∈F2qs\in\mathbb{F}_2^q and let (G,V0,…,VM−1)(G,V_0,\ldots,V_{M-1}) be a non zero solution of (2). Let

S(G)={a∈Fq:mult⁡a(G)≥q−h−M}.S(G)=\{a\in\mathbb{F}_q:\operatorname{mult}_a(G)\ge q-h-M\}.

Then

  1. ∣S(G)∣≤d|S(G)|\le d;

  2. if s=HqeEs=H_qe_E with ∣E∣≤d|E|\le d, then E⊂S(G)E\subset S(G).

In particular, if s=HqeEs=H_qe_E with ∣E∣=d|E|=d, then S(G)=ES(G)=E.

Proof. Note that u=d2+d<qu=d^2+d<q, so that G≠0G\ne0 by Proposition 6.1. Let (G∗,V0∗,…,VM−1∗)(G^*,V_0^*,\ldots,V_{M-1}^*) be a second non zero solution of (2), for the same ss, and let W=GG∗W=GG^*. We wish to apply Lemma 5.1 to WW, with K=2uK=2u. We have M+K=2d(d+1)+d+1≤h+M≤12(q+q+1)≤q−1M+K=2d(d+1)+d+1\le h+M\le\frac{1}{2}(\sqrt q+q+1)\le q-1 (as q≥7q\ge7), and deg⁡W≤2D<Mq\deg W\le2D<Mq (as deg⁡G≤D\deg G\le D, deg⁡G∗≤D\deg G^*\le D and Mq−2D=q−2d2−d≥2d2+3d+1>0Mq-2D=q-2d^2-d\ge2d^2+3d+1>0). We have to check that for any 0≤j<M0\le j<M, there is a polynomial Pj∈Fq[X]P_j\in\mathbb{F}_q[X] of degree at most 2u2u such that W[j]=Pj(modΛ)W^{[j]}=P_j\pmod{\Lambda}. By the Leibnitz rule for Hasse derivatives, we get

∀x∈Fq,W[j](x)=∑i=0jG[i](x)G∗[j−i](x)=∑i=0jrd(x)2Vi(x)Vj−i∗(x).\forall x\in\mathbb{F}_q,\quad W^{[j]}(x)=\sum_{i=0}^{j}G^{[i]}(x)G^{*[j-i]}(x)=\sum_{i=0}^{j}r_d(x)^2V_i(x)V_{j-i}^*(x).

Thus

W[j]=∑i=0jViVj−i∗(modΛ),W^{[j]}=\sum_{i=0}^{j}V_iV_{j-i}^*\pmod{\Lambda},

where deg⁡ViVj−i∗≤2u=K\deg V_iV_{j-i}^*\le2u=K. The lemma leads us to

∀a∈Fqmult⁡a(GG∗) mod q≤K+M−1<h+M.(3)\forall a\in\mathbb{F}_q\quad\operatorname{mult}_a(GG^*)\bmod q\le K+M-1<h+M. \tag*{(3)}

Proof of (i). We apply (3) with G∗=GG^*=G. Let a∈S(G)a \in S(G) and m=mult⁡a(G)m=\operatorname{mult}_a(G), so that m≥q−h−M=h−dm \ge q-h-M=h-d. If m≤hm \le h, then 2h−2d≤2m≤2h=q−12h-2d \le2m \le2h=q-1, hence mult⁡a(G2) mod q=2m≥2h−2d\operatorname{mult}_a(G^2)\bmod q=2m \ge2h-2d. As h≥2d2+2d>3dh \ge2d^2+2d>3d, we have 2h−2d>h+d=h+M−12h-2d>h+d=h+M-1, which contradicts (3). Therefore m≥h+1m \ge h+1 for every a∈S(G)a \in S(G), and

(h+1)∣S(G)∣≤deg⁡G≤D=d(h+1)+d2.(h+1)|S(G)| \le\deg G \le D=d(h+1)+d^2.

As d2<h+1d^2<h+1, we get ∣S(G)∣≤d|S(G)|\le d.

Proof of (ii). Let ∣E∣=e≤d|E|=e\le d. By Proposition 6.1, we can take for G∗G^* the solution F=fEh+MF=f_E^{h+M}, with Uj=(−1)d−eF[j]/fEhU_j=(-1)^{d-e}F^{[j]}/f_E^h. Let a∈Ea\in E. We have mult⁡a(GF)=h+M+mult⁡a(G)\operatorname{mult}_a(GF)=h+M+\operatorname{mult}_a(G). If mult⁡a(G)<q−h−M\operatorname{mult}_a(G)<q-h-M, then h+M≤mult⁡a(GF)<qh+M\le\operatorname{mult}_a(GF)<q, which contradicts (3). Thus mult⁡a(G)≥q−h−M\operatorname{mult}_a(G)\ge q-h-M for any a∈Ea\in E and therefore E⊆S(G)E\subseteq S(G).

Finally, if ∣E∣=d|E|=d, then E⊆S(G)E\subseteq S(G) and ∣S(G)∣≤d|S(G)|\le d, so that S(G)=ES(G)=E. □

Proposition 6.2 has the following consequence, on which the algorithm relies: a single interpolation, with d=t(q)d=t(q), deals with all the error weights e≤t(q)e\le t(q). Whatever the weight e≤de\le d of the error, any non zero solution GG of (2) gives a set S(G)S(G) of at most dd positions which contains EE, and the error is then determined by the syndrome.

We can now state our algorithm and compute its complexity.

Algorithm 1:Decoding algorithm for an entry mm
Input :mm, Fq\mathbb{F}_q
Output:error ee
1t←⌊q−12⌋t\leftarrow\left\lfloor\frac{\sqrt{q}-1}{2}\right\rfloor;
2s←Hq(m)s\leftarrow H_q(m);
3if s=0s=0 then
4return e=0e=0;
5d←td\leftarrow t;
6Compute rdr_d, the parameters hh, MM, uu, DD and solve (2).
7if a non-zero solution FF exists then
8For any a∈Fqa\in\mathbb{F}_q, compute mult⁡a(F)\operatorname{mult}_a(F) and deduce S(F)S(F);
9Solve the system Hqe=sH_q e=s with Supp⁡(e)⊆S(F)\operatorname{Supp}(e)\subseteq S(F) (linear system over F2\mathbb{F}_2);
10if there is a solution ee then
11return ee;
12return "Error is outside of our decoding radius";

Table 1.

Let us analyze why the algorithm returns the error if ∣E∣≤t|E|\le t and give an upper bound on the required number of operations. From the choice of our parameters, the system (2) is a system with q(d+1)q(d+1) equations and d22+d2+d+1+(d+1)(d2+d+1)\frac{d^2}{2}+d^2+d+1+(d+1)(d^2+d+1) unknowns. We solve it by dense Gaussian elimination, without using the structure of the system, in O(q2d2(d3+dq))O(q^2d^2(d^3+dq)) operations which is here O(q9/2)O(q^{9/2}) operations as d≪qd\ll\sqrt q. It is solved only once. Finding roots and multiplicities of a polynomial of degree O(q3/2)O(q^{3/2}) over Fq\mathbb{F}_q costs O(q3)O(q^3) operations by the naive Horner method. Finally, the last step is a linear system over F2\mathbb{F}_2 with qq equations and ∣S(F)∣≤t|S(F)|\le t unknowns (Proposition 6.2), so the overall cost of our algorithm is indeed O(q9/2)O(q^{9/2}).

Now, if there are at most t(q)t(q) errors, Proposition 6.1 applied with d=td=t shows that a non zero solution of the system (2) exists, and Proposition 6.2 that any non zero solution FF satisfies E⊆S(F)E\subseteq S(F): the vector eEe_E is a solution of the system of the last step. It is the only one. Indeed, ∣S(F)∣≤t|S(F)|\le t by Proposition 6.2, so that every solution of this system has weight at most tt; two solutions differ by a codeword of weight at most t<qt<\sqrt q, which is zero as the minimum distance is ≥q\ge\sqrt q. The algorithm therefore returns the error. (When t=0t=0, that is q=7q=7, only the case s=0s=0 is relevant.)

The bound ∣S(F)∣≤t|S(F)| \le t does not depend on the syndrome. Hence, when there are more than t(q)t(q) errors, the algorithm either reports a failure or returns a vector ee of weight at most tt with Hqe=sH_q e = s: then m+em + e is the unique codeword at distance at most tt from mm.

Acknowledgment

AI tools (Claude, Anthropic, and ChatGPT, OpenAI) were used during the preparation of this manuscript for language editing, LaTeX assistance, and exploratory discussions. All mathematical statements, proofs, and conclusions were independently verified by the authors, who take full responsibility for the content.

References

  1. [1]E. F. Assmus and H. F. Mattson, New 5-designs, J. Combin. Theory 6 (1969), 122–151.DOI
  2. [2]D. Augot, M. Bardet and J.-C. Faugère, On formulas for decoding binary cyclic codes, in Proc. IEEE Int. Symp. Inform. Theory (ISIT 2007), 2646–2650.
  3. [3]E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968.
  4. [4]R. C. Bose and D. K. Ray-Chaudhuri, On a class of error correcting binary group codes, Inform. Control 3 (1960), 68–79.
  5. [5]H. Boualame, M. Belkasmi and I. Chana, Efficient decoding algorithm for binary quadratic residue codes using reduced permutation sets, J. Comput. Sci. 19(4) (2023), 526–539.DOI
  6. [6]R. Calderbank, A square root bound on the minimum weight in quasi-cyclic codes, IEEE Trans. Inform. Theory 29(3) (1983), 332–337.DOI
  7. [7]R. Canto Torres and N. Sendrier, Analysis of information set decoding for a sub-linear error weight, in Post-Quantum Cryptography (PQCrypto 2016), Lecture Notes in Comput. Sci. 9606, Springer, 2016, 144–161.DOI
  8. [8]Y. Chang, T.-K. Truong, I. S. Reed, H. Y. Cheng and C. D. Lee, Algebraic decoding of (71, 36, 11), (79, 40, 15), and (97, 49, 15) quadratic residue codes, IEEE Trans. Commun. 51(9) (2003), 1463–1473.DOI
  9. [9]X. Chen, I. S. Reed, T. Helleseth and T.-K. Truong, Use of Gröbner bases to decode binary cyclic codes up to the true minimum distance, IEEE Trans. Inform. Theory 40(5) (1994), 1654–1661.DOI
  10. [10]J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, 3rd ed., Springer, New York, 1999.
  11. [11]P. Delsarte, Bilinear forms over a finite field, with applications to coding theory, J. Combin. Theory Ser. A 25 (1978), 226–241.DOI
  12. [12]M. Elia, Algebraic decoding of the (23, 12, 7) Golay code, IEEE Trans. Inform. Theory 33(1) (1987), 150–151.
  13. [13]E. M. Gabidulin, Theory of codes with maximum rank distance, Problems Inform. Transmission 21(1) (1985), 1–12.
  14. [14]P. Gaborit, Quadratic double circulant codes over fields, J. Combin. Theory Ser. A 97 (2002), 85–107.DOI
  15. [15]D. Gorenstein and N. Zierler, A class of error-correcting codes in $p^m$ symbols, J. Soc. Indust. Appl. Math. 9 (1961), 207–214.DOI
  16. [16]R. He, I. S. Reed, T.-K. Truong and X. Chen, Decoding the (47, 24, 11) quadratic residue code, IEEE Trans. Inform. Theory 47(3) (2001), 1181–1186.DOI
  17. [17]T. Helleseth, Legendre sums and codes related to QR codes, Discrete Appl. Math. 35(2) (1992), 107–113.DOI
  18. [18]T. Helleseth and J. F. Voloch, Double circulant quadratic residue codes, IEEE Trans. Inform. Theory 50(9) (2004), 2154–2155.DOI
  19. [19]A. Hocquenghem, Codes correcteurs d’erreurs, Chiffres 2 (1959), 147–156.
  20. [20]S. K. Houghten, C. W. H. Lam, L. H. Thiel and J. A. Parker, The extended quadratic residue code is the only (48, 24, 12) self-dual doubly-even code, IEEE Trans. Inform. Theory 49(1) (2003), 53–59.
  21. [21]M. Karlin, New binary coding results by circulants, IEEE Trans. Inform. Theory 15(1) (1969), 81–92.
  22. [22]S. V. Konyagin and I. E. Shparlinski, Quadratic non-residues in short intervals, Proc. Amer. Math. Soc. 143(10) (2015), 4261–4269.arxiv.org/abs/1311.7016
  23. [23]S. Kopparty, Recovering polynomials over finite fields from noisy character values, arXiv:2601.07137 (2026); to appear in Proc. FOCS 2026.
  24. [24]S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. Şaşoğlu and R. L. Urbanke, Reed–Muller codes achieve capacity on erasure channels, IEEE Trans. Inform. Theory 63(7) (2017), 4298–4316.
  25. [25]J. S. Leon, J. M. Masley and V. Pless, Duadic codes, IEEE Trans. Inform. Theory 30(5) (1984), 709–714.DOI
  26. [26]F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Mathematical Library 16, North-Holland, Amsterdam, 1977.
  27. [27]J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory 15(1) (1969), 122–127.DOI
  28. [28]D. E. Muller, Application of Boolean algebra to switching circuit design and to error detection, IRE Trans. Electron. Comput. EC-3 (1954), 6–12.
  29. [29]W. W. Peterson, Encoding and error-correction procedures for the Bose–Chaudhuri codes, IRE Trans. Inform. Theory 6(4) (1960), 459–470.
  30. [30]E. Prange, Some cyclic error-correcting codes with simple decoding algorithms, Technical Note AFCRC-TN-58-156, Air Force Cambridge Research Center, Bedford, MA, April 1958.
  31. [31]E. M. Rains and N. J. A. Sloane, Self-dual codes, in V. S. Pless and W. C. Huffman (eds.), Handbook of Coding Theory, vol. 1, Elsevier, Amsterdam, 1998, 177–294.
  32. [32]I. S. Reed, A class of multiple-error-correcting codes and the decoding scheme, Trans. IRE Prof. Group Inform. Theory 4 (1954), 38–49.
  33. [33]I. S. Reed, T.-K. Truong, X. Chen and X. Yin, The algebraic decoding of the (41, 21, 9) quadratic residue code, IEEE Trans. Inform. Theory 38(3) (1992), 974–985.
  34. [34]I. S. Reed, X. Yin and T.-K. Truong, Algebraic decoding of the (32,16,8) quadratic residue code, IEEE Trans. Inform. Theory 36(4) (1990), 876–880.DOI
  35. [35]A. M. Steane, Simple quantum error-correcting codes, Phys. Rev. A 54 (1996), 4741–4751.pubmed.ncbi.nlm.nih.gov/9914038
  36. [36]M. Tomlinson, C. J. Tjhai, M. A. Ambroze, M. Ahmed and M. Jibril, Error-Correction Coding and Decoding: Bounds, Codes, Decoders, Analysis and Applications, Springer, 2017.DOI
  37. [37]T.-K. Truong, P.-Y. Shih, W.-K. Su, C.-D. Lee and Y. Chang, Algebraic decoding of the (89, 45, 17) quadratic residue code, IEEE Trans. Inform. Theory 54(11) (2008), 5005–5011.
  38. [38]J. H. van Lint and F. J. MacWilliams, Generalized quadratic residue codes, IEEE Trans. Inform. Theory 24(6) (1978), 730–737.
  39. [39]J. F. Voloch, Asymptotics of the minimal distance of quadratic residue codes, preprint, https://web.ma.utexas.edu/users/voloch/Preprints/asyquad2.pdf; also in Oberwolfach Reports.

Paper details

vlnc:W_8jfghvjn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude, ChatGPT

View statement
Looking for related papers…
Contents