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 and dimension whose minimum distance satisfies the square-root bound . They include the Hamming code and the Golay code , and were generalized by van Lint and MacWilliams to generalized quadratic residue (GQR) codes of prime-power length , for which the bound still holds and is attained when 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 , corrects every error pattern of weight at most in the binary GQR code of length , in 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 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 , index the coordinates of a binary word by the elements of , and split the nonzero elements of into the set of squares and the set of non-squares. A binary cyclic code of length is determined by the set of exponents such that is a root of all its codewords, where is a primitive -th root of unity; the QR code is the cyclic code for which this set is . The construction makes sense as soon as 2 is a square modulo , that is for , and it gives a code of dimension , hence of rate just above . The precise definition is recalled in § 2.
Van Lint and MacWilliams [38] extended the construction from primes to prime powers : the coordinates are now indexed by the elements of , and the code is defined from the squares of . These generalized quadratic residue (GQR) codes exist in the binary case for , have dimension , and are invariant under the translations of ; they are no longer cyclic when .
QR codes have been generalized in two other directions, which we only mention. Duadic codes [25] are the cyclic codes of odd length obtained by replacing the pair by any partition of the nonzero residues modulo into two unions of cyclotomic classes exchanged by a multiplication ; they exist when is a square modulo and still satisfy a square-root bound. Double circulant quadratic residue codes [21, 14] are the codes of length and dimension with generator matrix , where is the circulant matrix defined by the squares modulo ; they exist for every odd prime , in particular for 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 of a GQR code of length satisfies the square-root bound
proved in [26], Ch. 16 for , where it is refined to when , and in [38] for general . How far this bound is from the truth depends on the case.
When is a square, the bound is attained: , the minimum being reached by a codeword whose support is the set of roots of , a one-dimensional -subspace of [38] (see also the final remark of [39]).
When is prime, the bound cannot be attained since is not an integer. The refined bound is attained for , but for the next lengths the minimum distance is much larger, for instance for , for and for , whereas . 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 and length has minimum distance close to the Gilbert–Varshamov value , that is about [26]. In the other direction, Voloch Voloch [39] proved that for infinitely many primes the QR code of length has minimum distance , and under the generalized Riemann hypothesis; he also states, without proof, that there are infinitely many non-square prime powers for which .
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 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 and the Golay code , which are both perfect, and the 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 has parameters , whereas shortening the BCH code to the same length and the same minimum distance only gives a code, and the QR code of length improved the best minimum distance known for its length and dimension [36]. Beyond length , 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 , and index the coordinates of the extended code by the projective line . By the Gleason–Prange theorem, the extended code is invariant under the group 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 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 has minimum distance at most , 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 , 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 gives the lattice , the extended Golay code 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 the QR code of length 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 qubits with minimum distance ; for and these are the Steane code and the quantum Golay code [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 ; Peterson [29] and Gorenstein and Zierler [15] then gave an algebraic decoder correcting 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 have length , 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 for errors at rate [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 , there is a deterministic algorithm that corrects any errors in the binary QR code of length when is prime, and more generally in the binary GQR code of length , in operations in .
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 and are the roots of a polynomial with coefficients in ; in this description, the syndrome of the received word gives the value of the quadratic character of 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 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 and are not known at these roots. Kopparty’s algorithm recovers a monic squarefree polynomial of degree at most from the values of its quadratic character, a proportion 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 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 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 is a square, no larger decoding radius can be guaranteed for the class as a whole, and for 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 but no better bound is available, decoding beyond 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 is a prime with , and and are the sets of nonzero squares and non-squares of . A binary word of length is seen as a function , and is identified with the element of the group algebra , which is here the ring . For a subset of we denote by its indicator function.
The classical definition
We first recall how binary cyclic codes are described by cyclotomic classes. Let be a primitive -th root of unity in , where is the order of in . The Fourier transform of is the function defined by
so that is the value at of the polynomial associated with . The cyclotomic class of is the set . Since is binary, , hence the set of zeros of is a union of cyclotomic classes. A binary cyclic code of length is defined by a union of cyclotomic classes, called its defining set: it is the code
which has dimension .
The condition means that , so that the cyclotomic class of a square is contained in : the set is a union of cyclotomic classes, and so is . The binary QR codes of length are the cyclic codes with defining sets and ,
As , they have dimension , and they are equivalent through the permutation of the coordinates for any . For the cyclotomic classes are , and , and is the Hamming code . For the sets and are themselves cyclotomic classes, with 11 elements, and is the Golay code .
In this description, the natural syndromes of a received word , where and is the set of error positions, are the values for . They belong to the field , whose degree can be as large as , and the error positions appear as exponents of . The defining set contains no long sequence of consecutive integers, so the BCH bound and the BCH decoder give very little, and the values for , 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 , and one uses the arithmetic of itself instead of that of . This is the point of view from which we start.
We first need a description of the code that does not involve . Let , and let
be the matrix of the multiplication by in . Since , we have , hence . The ideal of generated by when , and by when , is a QR code [26 Ch. 16], namely or according to the choice of . As these elements are idempotents, a parity-check matrix of this code is
and the syndrome of a word is the binary vector , whose coordinates are indexed by .
Let now be a set of error positions, of size . We associate with the polynomial
Contrary to the classical error-locator polynomial, has its coefficients in , a field whose size is the length of the code. Let be the Legendre symbol modulo , and let . On the one hand, each factor of equals if and if . On the other hand, by definition of , the coordinate is the parity of the number of such that . Comparing the two gives Helleseth’s identity, in the pointwise form which appears in the proof of [18 Lemma 2],
Helleseth used this relation to express the weights of the words 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 at all the points of outside , and decoding amounts to recovering the polynomial , which is squarefree, split and of degree , 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 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 is replaced by , the functions by the additive characters of , and the Legendre symbol by the quadratic character of . For the definitions below are those of § 2, and the identity (1) becomes Proposition 4.1.
Let be a prime power, where is odd and is a square in , which is equivalent to assuming that . We denote by the set of squares of and by the set of non-squares of . Let denote the trace from to .
In this paper we investigate the decoding of the binary GQR-codes constructed as follows. Let us consider a primitive -th root of unity , where denotes the order of in , and associate with any function , its Fourier transform defined by
Let be the set of functions from , identified with hereafter, and those from . Consider the sub-vector spaces of
These two codes are equivalent. To see that, it suffices to consider an element and to associate with a function the function , whose Fourier transform is .
There is another way to view these codes. We consider elements and in the group algebra given by and , and the matrix of the multiplication (convolution) by :
where for squares and 0 otherwise. As , we see that . The matrix generates the code or if and generates the code or if . As , the control matrix is in the first case and in the second, that we denote by .
Main result
From these facts, it is sufficient to treat the case of the code in order to establish the following theorem.
Theorem 3.1. For any prime power , the code , which is the binary QR code of length when is prime and the binary GQR code of length in general, is a code with parameters
with , for which there is a deterministic decoding algorithm for correcting any error of weight
running in operations in .
Before proving the theorem, we note that we present a uniform algorithm for all generalized QR codes. For , the minimum distance is indeed and thus our algorithm decodes up to the error-correcting capability. Decoding QR codes ( 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 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 , 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 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 the quadratic character of and recall that for any . We use the following notation, for any subset of :
Our algorithm will be partly based on the following identities due to Helleseth [17] (stated in the case of , 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 , , , if and if . Then
Proof. Let . Then . Thus
Now let . Then . Thus
Note that these equalities give the lower bound 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 th-Hasse derivatives of , are the polynomial such that
Lemma 5.1. Let , such that , and with . Assume that for any , there is a polynomial of degree at most such that , where . Then for every ,
where is the multiplicity of as a root of and the integers modulo are identified with .
Let us prove this lemma which is about Hasse derivatives, polynomials and pseudopolynomials. It is a version at the points of of [23 Lemma 3.3], combined with the observation of [23 Section 5.1] that the conditions on the first derivatives bound the degrees of the .
Proof: Let be the polynomial . The condition on the degree of allows us to write as
where are polynomials of degree less than . As , it is clear that, if , if , if , and otherwise.
For , this computation and the Leibnitz rule on Hasse derivatives leads to
(see [23 Lemma 2.4]) with the convention that if . As , with , it follows by induction on that , as it equals modulo a polynomial of degree less or equal to and is of degree strictly less than .
Let . Recall that if is the largest integer such that for all , . We have
where
From the last inequality, we see that every term in the double sum has a different degree and that . Therefore, if is the smallest such that , we see immediately that , the latter being an integer smaller or equal to . The lemma follows. □
The algorithm
In this section, we explain how to decode a received word. Assume that we received where is a codeword. We compute where is unknown. Let be its support; for we write . Let 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 in the algorithm. We can compute the quantity
If , we have for any , and for any (see Proposition 4.1). We know that this system admits at least a solution with a split polynomial of degree at most (by hypothesis). But the are values of a polynomial of very large degree (it may be about ), so that recovering 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 .
Let so that for any , and any polynomial , . Let , and put
Consider the linear system with polynomial unknown (it is the system of [23 Algorithm A], with parameters adapted to our situation)
Proposition 6.1. If with , the system (2) admits
as a non zero solution, and . For any , if , every non zero solution of (2) satisfies .
Proof. Let . From the Leibnitz rule for Hasse derivatives, it is clear that , and therefore are polynomials vanishing on and satisfying . Moreover . If , then by Proposition 4.1, so that , and if , then . If is zero and , the polynomials have to be zero as they vanish on and are of degree .
Now that we know that the system has a solution, let us show how to get 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 , 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 and . Let and let be a non zero solution of (2). Let
Then
;
if with , then .
In particular, if with , then .
Proof. Note that , so that by Proposition 6.1. Let be a second non zero solution of (2), for the same , and let . We wish to apply Lemma 5.1 to , with . We have (as ), and (as , and ). We have to check that for any , there is a polynomial of degree at most such that . By the Leibnitz rule for Hasse derivatives, we get
Thus
where . The lemma leads us to
Proof of (i). We apply (3) with . Let and , so that . If , then , hence . As , we have , which contradicts (3). Therefore for every , and
As , we get .
Proof of (ii). Let . By Proposition 6.1, we can take for the solution , with . Let . We have . If , then , which contradicts (3). Thus for any and therefore .
Finally, if , then and , so that . □
Proposition 6.2 has the following consequence, on which the algorithm relies: a single interpolation, with , deals with all the error weights . Whatever the weight of the error, any non zero solution of (2) gives a set of at most positions which contains , 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 |
| Input : | , |
| Output: | error |
| 1 | ; |
| 2 | ; |
| 3 | if then |
| 4 | return ; |
| 5 | ; |
| 6 | Compute , the parameters , , , and solve (2). |
| 7 | if a non-zero solution exists then |
| 8 | For any , compute and deduce ; |
| 9 | Solve the system with (linear system over ); |
| 10 | if there is a solution then |
| 11 | return ; |
| 12 | return "Error is outside of our decoding radius"; |
Table 1.
Let us analyze why the algorithm returns the error if and give an upper bound on the required number of operations. From the choice of our parameters, the system (2) is a system with equations and unknowns. We solve it by dense Gaussian elimination, without using the structure of the system, in operations which is here operations as . It is solved only once. Finding roots and multiplicities of a polynomial of degree over costs operations by the naive Horner method. Finally, the last step is a linear system over with equations and unknowns (Proposition 6.2), so the overall cost of our algorithm is indeed .
Now, if there are at most errors, Proposition 6.1 applied with shows that a non zero solution of the system (2) exists, and Proposition 6.2 that any non zero solution satisfies : the vector is a solution of the system of the last step. It is the only one. Indeed, by Proposition 6.2, so that every solution of this system has weight at most ; two solutions differ by a codeword of weight at most , which is zero as the minimum distance is . The algorithm therefore returns the error. (When , that is , only the case is relevant.)
The bound does not depend on the syndrome. Hence, when there are more than errors, the algorithm either reports a failure or returns a vector of weight at most with : then is the unique codeword at distance at most from .
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]E. F. Assmus and H. F. Mattson, New 5-designs, J. Combin. Theory 6 (1969), 122–151.DOI
- [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]E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968.
- [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]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]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]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]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]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]J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, 3rd ed., Springer, New York, 1999.
- [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]M. Elia, Algebraic decoding of the (23, 12, 7) Golay code, IEEE Trans. Inform. Theory 33(1) (1987), 150–151.
- [13]E. M. Gabidulin, Theory of codes with maximum rank distance, Problems Inform. Transmission 21(1) (1985), 1–12.
- [14]P. Gaborit, Quadratic double circulant codes over fields, J. Combin. Theory Ser. A 97 (2002), 85–107.DOI
- [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]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]T. Helleseth, Legendre sums and codes related to QR codes, Discrete Appl. Math. 35(2) (1992), 107–113.DOI
- [18]T. Helleseth and J. F. Voloch, Double circulant quadratic residue codes, IEEE Trans. Inform. Theory 50(9) (2004), 2154–2155.DOI
- [19]A. Hocquenghem, Codes correcteurs d’erreurs, Chiffres 2 (1959), 147–156.
- [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]M. Karlin, New binary coding results by circulants, IEEE Trans. Inform. Theory 15(1) (1969), 81–92.
- [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]S. Kopparty, Recovering polynomials over finite fields from noisy character values, arXiv:2601.07137 (2026); to appear in Proc. FOCS 2026.
- [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]J. S. Leon, J. M. Masley and V. Pless, Duadic codes, IEEE Trans. Inform. Theory 30(5) (1984), 709–714.DOI
- [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]J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inform. Theory 15(1) (1969), 122–127.DOI
- [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]W. W. Peterson, Encoding and error-correction procedures for the Bose–Chaudhuri codes, IRE Trans. Inform. Theory 6(4) (1960), 459–470.
- [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]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]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]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]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]A. M. Steane, Simple quantum error-correcting codes, Phys. Rev. A 54 (1996), 4741–4751.pubmed.ncbi.nlm.nih.gov/9914038
- [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]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]J. H. van Lint and F. J. MacWilliams, Generalized quadratic residue codes, IEEE Trans. Inform. Theory 24(6) (1978), 730–737.
- [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.