HOME

TheInfoList




In
statistics Statistics is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data Data (; ) are individual facts, statistics, or items of information, often numeric. In a more technical sens ...

statistics
and
coding theory 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 ...
, a
Hamming Hamming may refer to: * Richard Hamming Richard Wesley Hamming (February 11, 1915 – January 7, 1998) was an American mathematician whose work had many implications for computer engineering Computer engineering (CoE or CpE) is a branch o ...
space is usually the set of all 2^N
binary string In computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a particular task. Programming involves tasks such as analysis, ge ...
s of length ''N''. It is used in the theory of coding signals and transmission. More generally, a Hamming space can be defined over any
alphabet An alphabet is a standardized set of basic written symbols A symbol is a mark, sign, or word In linguistics, a word of a spoken language can be defined as the smallest sequence of phonemes that can be uttered in isolation with semanti ...
(set) ''Q'' as the set of
words In linguistics Linguistics is the scientific study of language A language is a structured system of communication used by humans, including speech (spoken language), gestures (Signed language, sign language) and writing. Most lang ...
of a fixed length ''N'' with letters from ''Q''.Cohen et al., ''Covering Codes'', p. 15 If ''Q'' is a
finite field In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
, then a Hamming space over ''Q'' is an ''N''-dimensional
vector space In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...
over ''Q''. In the typical, binary case, the field is thus
GF(2) (also denoted \mathbb F_2, or \mathbb Z/2\mathbb Z) is the finite field of two elements (GF is the initialism of ''Galois field'', another name for finite fields). Notations and \mathbb Z_2 may be encountered although they can be confused with ...
(also denoted by Z2). In coding theory, if ''Q'' has ''q'' elements, then any
subset In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

subset
''C'' (usually assumed of
cardinality In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
at least two) of the ''N''-dimensional Hamming space over ''Q'' is called a q-ary
code In communication Communication (from Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', mean ...

code
of length N; the elements of ''C'' are called
codeword In communication Communication (from Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning ...
s. In the case where ''C'' is a
linear subspace In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
of its Hamming space, it is called a
linear code In coding theory Coding theory is the study of the properties of s and their respective fitness for specific applications. Codes are used for , , , and . Codes are studied by various scientific disciplines—such as , , , , and —for the purpo ...
. A typical example of linear code is the
Hamming code In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , ...
. Codes defined via a Hamming space necessarily have the same length for every codeword, so they are called
block code In coding theory Coding theory is the study of the properties of s and their respective fitness for specific applications. Codes are used for , , , and . Codes are studied by various scientific disciplines—such as , , , , and —for the purpo ...

block code
s when it is necessary to distinguish them from
variable-length code In coding theory Coding theory is the study of the properties of s and their respective fitness for specific applications. Codes are used for , , , and . Codes are studied by various scientific disciplines—such as , , , , and —for the pur ...
s that are defined by unique factorization on a monoid. The
Hamming distance In information theory Information theory is the scientific study of the quantification, storage, and communication Communication (from Latin ''communicare'', meaning "to share" or "to be in relation with") is "an apparent answer to ...
endows a Hamming space with a
metric Metric or metrical may refer to: * Metric system, an internationally adopted decimal system of measurement Mathematics * Metric (mathematics), an abstraction of the notion of ''distance'' in a metric space * Metric tensor, in differential geomet ...
, which is essential in defining basic notions of coding theory such as error detecting and error correcting codes. Hamming spaces over non-field alphabets have also been considered, especially over
finite ring In mathematics, more specifically abstract algebra, a finite ring is a ring (mathematics), ring that has a finite number of elements. Every finite field is an example of a finite ring, and the additive part of every finite ring is an example of an a ...
s (most notably over Z4) giving rise to
module Module, modular and modularity may refer to the concept of modularity. They may also refer to: Computing and engineering * Modular design, the engineering discipline of designing complex devices using separately designed sub-components * Modul ...
s instead of vector spaces and ring-linear codes (identified with
submodule In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
s) instead of linear codes. The typical metric used in this case the
Lee distance In coding theory 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. ...
. There exist a
Gray isometry The reflected binary code (RBC), also known just as reflected binary (RB) or Gray code after Frank Gray (researcher), Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). ...
between \mathbb_2^ (i.e. GF(22m)) with the Hamming distance and \mathbb_4^m (also denoted as GR(4,m)) with the Lee distance.


References

Coding theory Linear algebra {{algebra-stub