Quadratic Residue Code

A quadratic residue code is a type of cyclic code.

There is a quadratic residue code of length over the finite field whenever and are primes, is odd and is a quadratic residue modulo . Its generator polynomial as a cyclic code is given by

where is the set of quadratic residues of in the set and is a primitive th root of unity in some finite extension field of . The condition that is a quadratic residue of ensures that the coefficients of lie in . The dimension of the code is

Replacing by another primitive -th root of unity either results in the same code or an equivalent code, according to whether or not is a quadratic residue of .

An alternative construction avoids roots of unity. Define

for a suitable . When choose to ensure that while if is odd where or according to whether is congruent to or modulo . Then also generates a quadratic residue code; more precisely the ideal of generated by corresponds to the quadratic residue code.

The minimum weight of a quadratic residue code of length is greater than ; this is the square root bound.

Adding an overall parity-check digit to a quadratic residue code gives an extended quadratic residue code. When (mod ) an extended quadratic residue code is self-dual; otherwise it is equivalent but not equal to its dual. By a theorem of Gleason and Prange, the automorphism group of an extended quadratic residue code has a subgroup which is isomorphic to either or .

Examples of quadratic residue codes include the Hamming code over, the binary Golay code over and the ternary Golay code over .

Famous quotes containing the words residue and/or code:

    Every poem of value must have a residue [of language].... It cannot be exhausted because our lives are not long enough to do so. Indeed, in the greatest poetry, the residue may seem to increase as our experience increases—that is, as we become more sensitive to the particular ignitions in its language. We return to a poem not because of its symbolic [or sociological] value, but because of the waste, or subversion, or difficulty, or consolation of its provision.
    William Logan, U.S. educator. “Condition of the Individual Talent,” The Sewanee Review, p. 93, Winter 1994.

    Many people will say to working mothers, in effect, “I don’t think you can have it all.” The phrase for “have it all” is code for “have your cake and eat it too.” What these people really mean is that achievement in the workplace has always come at a price—usually a significant personal price; conversely, women who stayed home with their children were seen as having sacrificed a great deal of their own ambition for their families.
    Anne C. Weisberg (20th century)