Examples
Examples of quadratic residue codes include the Hamming code over , the binary Golay code over and the ternary Golay code over .
A quadratic residue code is a type of cyclic code.
Examples of quadratic residue codes include the Hamming code over , the binary Golay code over and the ternary Golay code over .
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 . If is odd, choose , 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 the Gleason–Prange theorem (named for Andrew Gleason and Eugene Prange), the automorphism group of an extended quadratic residue code has a subgroup which is isomorphic to either or .
Since late 1980, there are many algebraic decoding algorithms were developed for correcting errors on quadratic residue codes. These algorithms can achieve the (true) error-correcting capacity of the quadratic residue codes with the code length up to 113. However, decoding of long binary quadratic residue codes and non-binary quadratic residue codes continue to be a challenge. Currently, decoding quadratic residue codes is still an active research area in the theory of error-correcting code.
In mathematics, a finite field or Galois field is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are given by the integers mod p when p is a prime number.
In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.
Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mathematics is the queen of the sciences—and number theory is the queen of mathematics." Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers, or defined as generalizations of the integers.
In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:
Reed–Solomon codes are a group of error-correcting codes that were introduced by Irving S. Reed and Gustave Solomon in 1960. They have many applications, including consumer technologies such as MiniDiscs, CDs, DVDs, Blu-ray discs, QR codes, Data Matrix, data transmission technologies such as DSL and WiMAX, broadcast systems such as satellite communications, DVB and ATSC, and storage systems such as RAID 6.
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied by various scientific disciplines—such as information theory, electrical engineering, mathematics, linguistics, and computer science—for the purpose of designing efficient and reliable data transmission methods. This typically involves the removal of redundancy and the correction or detection of errors in the transmitted data.
In mathematics, the Leech lattice is an even unimodular lattice Λ24 in 24-dimensional Euclidean space, which is one of the best models for the kissing number problem. It was discovered by John Leech. It may also have been discovered by Ernst Witt in 1940.
In mathematics and electronics engineering, a binary Golay code is a type of linear error-correcting code used in digital communications. The binary Golay code, along with the ternary Golay code, has a particularly deep and interesting connection to the theory of finite sporadic groups in mathematics. These codes are named in honor of Marcel J. E. Golay whose 1949 paper introducing them has been called, by E. R. Berlekamp, the "best single published page" in coding theory.
In mathematics, in the area of number theory, a Gaussian period is a certain kind of sum of roots of unity. The periods permit explicit calculations in cyclotomic fields connected with Galois theory and with harmonic analysis. They are basic in the classical theory called cyclotomy. Closely related is the Gauss sum, a type of exponential sum which is a linear combination of periods.
In cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece. It was the first such scheme to use randomization in the encryption process. The algorithm has never gained much acceptance in the cryptographic community, but is a candidate for "post-quantum cryptography", as it is immune to attacks using Shor's algorithm and – more generally – measuring coset states using Fourier sampling.
In mathematics, the Dedekind zeta function of an algebraic number field K, generally denoted ζK(s), is a generalization of the Riemann zeta function (which is obtained in the case where K is the field of rational numbers Q). It can be defined as a Dirichlet series, it has an Euler product expansion, it satisfies a functional equation, it has an analytic continuation to a meromorphic function on the complex plane C with only a simple pole at s = 1, and its values encode arithmetic data of K. The extended Riemann hypothesis states that if ζK(s) = 0 and 0 < Re(s) < 1, then Re(s) = 1/2.
Algebraic geometry codes, often abbreviated AG codes, are a type of linear code that generalize Reed–Solomon codes. The Russian mathematician V. D. Goppa constructed these codes for the first time in 1982.
In coding theory, decoding is the process of translating received messages into codewords of a given code. There have been many common methods of mapping messages to codewords. These are often used to recover messages sent over a noisy channel, such as a binary symmetric channel.
In coding theory, the ternary Golay codes are two closely related error-correcting codes. The code generally known simply as the ternary Golay code is an -code, that is, it is a linear code over a ternary alphabet; the relative distance of the code is as large as it possibly can be for a ternary code, and hence, the ternary Golay code is a perfect code. The extended ternary Golay code is a [12, 6, 6] linear code obtained by adding a zero-sum check digit to the [11, 6, 5] code. In finite group theory, the extended ternary Golay code is sometimes referred to as the ternary Golay code.
In number theory, the law of quadratic reciprocity, like the Pythagorean theorem, has lent itself to an unusually large number of proofs. Several hundred proofs of the law of quadratic reciprocity have been published.
In coding theory, a cyclic code is a block code, where the circular shifts of each codeword gives another word that belongs to the code. They are error-correcting codes that have algebraic properties that are convenient for efficient error detection and correction.
In number theory, a cyclotomic field is a number field obtained by adjoining a complex root of unity to Q, the field of rational numbers.
In mathematics and computer science, the binary Goppa code is an error-correcting code that belongs to the class of general Goppa codes originally described by Valerii Denisovich Goppa, but the binary structure gives it several mathematical advantages over non-binary variants, also providing a better fit for common usage in computers and telecommunication. Binary Goppa codes have interesting properties suitable for cryptography in McEliece-like cryptosystems and similar setups.
Eugene August Prange was an American coding theorist, a researcher at the Air Force Cambridge Research Laboratory (AFCRL) in Massachusetts who "introduced many of the early fundamental ideas of algebraic coding theory" and was the first to investigate cyclic codes in 1957. With Andrew Gleason, he is the namesake of the Gleason–Prange theorem on the symmetries of the extended quadratic residue code.
Introduction to the Theory of Error-Correcting Codes is a textbook on error-correcting codes, by Vera Pless. It was published in 1982 by John Wiley & Sons, with a second edition in 1989 and a third in 1998. The Basic Library List Committee of the Mathematical Association of America has rated the book as essential for inclusion in undergraduate mathematics libraries.
