Hamming space

Last updated August 13, 2023

In statistics and coding theory, a Hamming space (named after American mathematician Richard Hamming) is usually the set of all $2^{N}$ binary strings of length N.^[1]^[2] It is used in the theory of coding signals and transmission.

More generally, a Hamming space can be defined over any alphabet (set) Q as the set of words of a fixed length N with letters from Q.^[3]^[4] If Q is a finite field, then a Hamming space over Q is an N-dimensional vector space over Q. In the typical, binary case, the field is thus GF(2) (also denoted by Z₂).^[3]

In coding theory, if Q has q elements, then any subset C (usually assumed of cardinality at least two) of the N-dimensional Hamming space over Q is called a q-ary code of length N; the elements of C are called codewords .^[3]^[4] In the case where C is a linear subspace of its Hamming space, it is called a linear code.^[3] A typical example of linear code is the Hamming code. Codes defined via a Hamming space necessarily have the same length for every codeword, so they are called block codes when it is necessary to distinguish them from variable-length codes that are defined by unique factorization on a monoid.

The Hamming distance endows a Hamming space with a metric, which is essential in defining basic notions of coding theory such as error detecting and error correcting codes.^[3]

Hamming spaces over non-field alphabets have also been considered, especially over finite rings (most notably over Z₄) giving rise to modules instead of vector spaces and ring-linear codes (identified with submodules) instead of linear codes. The typical metric used in this case the Lee distance. There exist a Gray isometry between $\mathbb {Z} _{2}^{2m}$ (i.e. GF(2^2m)) with the Hamming distance and $\mathbb {Z} _{4}^{m}$ (also denoted as GR(4,m)) with the Lee distance.^[5]^[6]^[7]

Related Research Articles

In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other. In a more general context, the Hamming distance is one of several string metrics for measuring the edit distance between two sequences. It is named after the American mathematician Richard Hamming.

<span class="mw-page-title-main">Coding theory</span> Study of the properties of codes and their fitness

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.

<span class="mw-page-title-main">Binary Golay code</span> Type of linear error-correcting code

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 coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists, mathematicians, and computer scientists to study the limitations of all block codes in a unified way. Such limitations often take the form of bounds that relate different parameters of the block code to each other, such as its rate and its ability to detect and correct errors.

In coding theory, the dual code of a linear code

In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although turbo codes can be seen as a hybrid of these two types. Linear codes allow for more efficient encoding and decoding algorithms than other codes.

In coding theory, the Singleton bound, named after Richard Collom Singleton, is a relatively crude upper bound on the size of an arbitrary block code $with block length, size and minimum distance . It is also known as the Joshibound . proved by Joshi (1958) and even earlier by Komamiya (1953).$

In mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere-packing bound or the volume bound from an interpretation in terms of packing balls in the Hamming metric into the space of all possible words. It gives an important limitation on the efficiency with which any error-correcting code can utilize the space in which its code words are embedded. A code that attains the Hamming bound is said to be a perfect code.

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.

Reed–Muller codes are error-correcting codes that are used in wireless communications applications, particularly in deep-space communication. Moreover, the proposed 5G standard relies on the closely related polar codes for error correction in the control channel. Due to their favorable theoretical and mathematical properties, Reed–Muller codes have also been extensively studied in theoretical computer science.

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 coding theory, a generator matrix is a matrix whose rows form a basis for a linear code. The codewords are all of the linear combinations of the rows of this matrix, that is, the linear code is the row space of its generator matrix.

The Hadamard code is an error-correcting code named after Jacques Hadamard that is used for error detection and correction when transmitting messages over very noisy or unreliable channels. In 1971, the code was used to transmit photos of Mars back to Earth from the NASA space probe Mariner 9. Because of its unique mathematical properties, the Hadamard code is not only used by engineers, but also intensely studied in coding theory, mathematics, and theoretical computer science. The Hadamard code is also known under the names Walsh code, Walsh family, and Walsh–Hadamard code in recognition of the American mathematician Joseph Leonard Walsh.

In coding theory, a covering code is a set of elements in a space, with the property that every element of the space is within a fixed distance of some codeword.

In coding theory, the Lee distance is a distance between two strings $and of equal length n over the q -ary alphabet {0, 1, \dots, q - 1} of size q \geq 2 . It is a metric defined as$

In coding theory, Justesen codes form a class of error-correcting codes that have a constant rate, constant relative distance, and a constant alphabet size.

A locally decodable code (LDC) is an error-correcting code that allows a single bit of the original message to be decoded with high probability by only examining a small number of bits of a possibly corrupted codeword. This property could be useful, say, in a context where information is being transmitted over a noisy channel, and only a small subset of the data is required at a particular time and there is no need to decode the entire message at once. Note that locally decodable codes are not a subset of locally testable codes, though there is some overlap between the two.

DNA code construction refers to the application of coding theory to the design of nucleic acid systems for the field of DNA–based computation.

The Gilbert–Varshamov bound for linear codes is related to the general Gilbert–Varshamov bound, which gives a lower bound on the maximal number of elements in an error-correcting code of a given block length and minimum Hamming weight over a field $. This may be translated into a statement about the maximum rate of a code with given length and minimum distance. The Gilbert-Varshamov bound for linear codes asserts the existence of q -ary linear codes for any relative minimum distance less than the given bound that simultaneously have high rate. The existence proof uses the probabilistic method, and thus is not constructive. The Gilbert-Varshamov bound is the best known in terms of relative distance for codes over alphabets of size less than 49. For larger alphabets, algebraic geometry codes sometimes achieve an asymptotically better rate vs. distance tradeoff than is given by the Gilbert-Varshamov bound.$

References

↑ Baylis, D. J. (1997), Error Correcting Codes: A Mathematical Introduction, Chapman Hall/CRC Mathematics Series, vol. 15, CRC Press, p. 62, ISBN 9780412786907
↑ Cohen, G.; Honkala, I.; Litsyn, S.; Lobstein, A. (1997), Covering Codes, North-Holland Mathematical Library, vol. 54, Elsevier, p. 1, ISBN 9780080530079
1 2 3 4 5 Derek J.S. Robinson (2003). An Introduction to Abstract Algebra. Walter de Gruyter. pp. 254–255. ISBN 978-3-11-019816-4.
1 2 Cohen et al., Covering Codes, p. 15
↑ Marcus Greferath (2009). "An Introduction to Ring-Linear Coding Theory". In Massimiliano Sala; Teo Mora; Ludovic Perret; Shojiro Sakata; Carlo Traverso (eds.). Gröbner Bases, Coding, and Cryptography. Springer Science & Business Media. ISBN 978-3-540-93806-4.
↑ "Kerdock and Preparata codes - Encyclopedia of Mathematics".
↑ J.H. van Lint (1999). Introduction to Coding Theory (3rd ed.). Springer. Chapter 8: Codes over ℤ₄. ISBN 978-3-540-64133-9.

This linear algebra-related article is a stub. You can help Wikipedia by expanding it.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Baylis, D. J. (1997), Error Correcting Codes: A Mathematical Introduction, Chapman Hall/CRC Mathematics Series, vol. 15, CRC Press, p. 62, ISBN 9780412786907

[2] Cohen, G.; Honkala, I.; Litsyn, S.; Lobstein, A. (1997), Covering Codes, North-Holland Mathematical Library, vol. 54, Elsevier, p. 1, ISBN 9780080530079

[Robinson2003-3] 1 2 3 4 5 Derek J.S. Robinson (2003). An Introduction to Abstract Algebra. Walter de Gruyter. pp. 254–255. ISBN 978-3-11-019816-4.

[cc15-4] 1 2 Cohen et al., Covering Codes, p. 15

[Greferath2009-5] Marcus Greferath (2009). "An Introduction to Ring-Linear Coding Theory". In Massimiliano Sala; Teo Mora; Ludovic Perret; Shojiro Sakata; Carlo Traverso (eds.). Gröbner Bases, Coding, and Cryptography. Springer Science & Business Media. ISBN 978-3-540-93806-4.

[6] "Kerdock and Preparata codes - Encyclopedia of Mathematics".

[Lint1999-7] J.H. van Lint (1999). Introduction to Coding Theory (3rd ed.). Springer. Chapter 8: Codes over ℤ₄. ISBN 978-3-540-64133-9.

[1]

[2]

[3]

[4]

[5]

[6]

[7]