|
Binary Golay 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. There are two closely related binary Golay codes. The extended binary Golay code, ''G''24 (sometimes just called the "Golay code" in finite group theory) encodes 12 bits of data in a 24-bit word in such a way that any 3-bit errors can be corrected or any 4-bit errors can be detected. The other, the perfect binary Golay code, ''G''23, has codewords of length 23 and is obtained from the extended binary Golay code by deleting one coordinate position (conversely, the extended binary Golay code is obtained from th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hamming Weight
The Hamming weight of a string (computer science), string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a given set of bits, this is the number of bits set to 1, or the digit sum of the Binary numeral system, binary representation of a given number and the Taxicab geometry, ''ℓ''₁ norm of a bit vector. In this binary case, it is also called the population count, popcount, sideways sum, or bit summation. History and usage The Hamming weight is named after the American mathematician Richard Hamming, although he did not originate the notion. The Hamming weight of binary numbers was already used in 1899 by James Whitbread Lee Glaisher, James W. L. Glaisher to give a formula for Gould's sequence, the number of odd binomial coefficients in a single row of Pascal's triangle. Irving S. Reed introduced a concept, equivalen ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hamming Code
In computer science and telecommunications, Hamming codes are a family of linear error-correcting codes. Hamming codes can detect one-bit and two-bit errors, or correct one-bit errors without detection of uncorrected errors. By contrast, the simple parity code cannot correct errors, and can detect only an odd number of bits in error. Hamming codes are perfect codes, that is, they achieve the highest possible rate for codes with their block length and minimum distance of three. Richard W. Hamming invented Hamming codes in 1950 as a way of automatically correcting errors introduced by punched card readers. In his original paper, Hamming elaborated his general idea, but specifically focused on the Hamming(7,4) code which adds three parity bits to four bits of data. In mathematical terms, Hamming codes are a class of binary linear code. For each integer there is a code-word with block length and message length . Hence the rate of Hamming codes is , which is the highest p ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
GF(2)
(also denoted \mathbb F_2, or \mathbb Z/2\mathbb Z) is the finite field with two elements. is the Field (mathematics), field with the smallest possible number of elements, and is unique if the additive identity and the multiplicative identity are denoted respectively and , as usual. The elements of may be identified with the two possible values of a bit and to the Boolean domain, Boolean values ''true'' and ''false''. It follows that is fundamental and ubiquitous in computer science and its mathematical logic, logical foundations. Definition GF(2) is the unique field with two elements with its additive identity, additive and multiplicative identity, multiplicative identities respectively denoted and . Its addition is defined as the usual addition of integers but modulo 2 and corresponds to the table below: If the elements of GF(2) are seen as Boolean values, then the addition is the same as that of the logical XOR operation. Since each element equals its opposite (m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cyclic Code
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. Definition Let \mathcal be a linear code over a finite field (also called '' Galois field'') GF(q) of block length n. \mathcal is called a cyclic code if, for every Code word (communication), codeword c=(c_1,\ldots,c_n) from \mathcal, the word (c_n,c_1,\ldots,c_) in GF(q)^n obtained by a circular shift, cyclic right shift of components is again a codeword. Because one cyclic right shift is equal to n-1 cyclic left shifts, a cyclic code may also be defined via cyclic left shifts. Therefore, the linear code \mathcal is cyclic precisely when it is invariant under all cyclic shifts. Cyclic codes have some additional structural constraint on the codes. They are based on Galois fields and because of their structural properti ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cyclic Group
In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, generated by a single element. That is, it is a set (mathematics), set of Inverse element, invertible elements with a single associative binary operation, and it contains an element g such that every other element of the group may be obtained by repeatedly applying the group operation to g or its inverse. Each element can be written as an integer Exponentiation, power of g in multiplicative notation, or as an integer multiple of g in additive notation. This element g is called a ''Generating set of a group, generator'' of the group. Every infinite cyclic group is isomorphic to the additive group \Z, the integers. Every finite cyclic group of Order (group theory), order n is isomorphic to the additive group of Quotient group, Z/''n''Z, the in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Quadratic Residue Code
A quadratic residue code is a type of cyclic code. Examples Examples of quadratic residue codes include the (7,4) Hamming code over GF(2), the (23,12) binary Golay code over GF(2) and the (11,6) ternary Golay code over GF(3). Constructions There is a quadratic residue code of length p over the finite field GF(l) whenever p and l are primes, p is odd, and l is a quadratic residue modulo p. Its generator polynomial as a cyclic code is given by :f(x)=\prod_(x-\zeta^j) where Q is the set of quadratic residues of p in the set \ and \zeta is a primitive pth root of unity in some finite extension field of GF(l). The condition that l is a quadratic residue of p ensures that the coefficients of f lie in GF(l). The dimension of the code is (p+1)/2. Replacing \zeta by another primitive p-th root of unity \zeta^r either results in the same code or an equivalent code, according to whether or not r is a quadratic residue of p. An alternative construction avoids roots of unity. Define :g(x)=c+ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lexicode
Lexicographic codes or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently by Vladimir Levenshtein and by John Horton Conway and Neil Sloane. The binary lexicographic codes are linear codes, and include the Hamming codes and the binary Golay codes. Construction A lexicode of length ''n'' and minimum distance ''d'' over a finite field is generated by starting with the all-zero vector and iteratively adding the next vector (in lexicographic order) of minimum Hamming distance In information theory, the Hamming distance between two String (computer science), strings or vectors of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number ... ''d'' from the vectors added so far. As an example, the length-3 lexicode of minimum distance 2 would consist of the vectors marked by an "X" in the following example: : Here is a ta ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Coset
In mathematics, specifically group theory, a subgroup of a group may be used to decompose the underlying set of into disjoint, equal-size subsets called cosets. There are ''left cosets'' and ''right cosets''. Cosets (both left and right) have the same number of elements (cardinality) as does . Furthermore, itself is both a left coset and a right coset. The number of left cosets of in is equal to the number of right cosets of in . This common value is called the index of in and is usually denoted by . Cosets are a basic tool in the study of groups; for example, they play a central role in Lagrange's theorem that states that for any finite group , the number of elements of every subgroup of divides the number of elements of . Cosets of a particular type of subgroup (a normal subgroup) can be used as the elements of another group called a quotient group or factor group. Cosets also appear in other areas of mathematics such as vector spaces and error-correcting code ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Quotient Space (linear Algebra)
In linear algebra, the quotient of a vector space V by a subspace N is a vector space obtained by "collapsing" N to zero. The space obtained is called a quotient space and is denoted V/N (read "V mod N" or "V by N"). Definition Formally, the construction is as follows. Let V be a vector space over a field \mathbb, and let N be a subspace of V. We define an equivalence relation \sim on V by stating that x \sim y iff . That is, x is related to y if and only if one can be obtained from the other by adding an element of N. This definition implies that any element of N is related to the zero vector; more precisely, all the vectors in N get mapped into the equivalence class of the zero vector. The equivalence class – or, in this case, the coset – of x is defined as : := \ and is often denoted using the shorthand = x + N. The quotient space V/N is then defined as V/_\sim, the set of all equivalence classes induced by \sim on V. Scalar multiplication and addition are defin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Group Action (mathematics)
In mathematics, a group action of a group G on a set (mathematics), set S is a group homomorphism from G to some group (under function composition) of functions from S to itself. It is said that G acts on S. Many sets of transformation (function), transformations form a group (mathematics), group under function composition; for example, the rotation (mathematics), rotations around a point in the plane. It is often useful to consider the group as an abstract group, and to say that one has a group action of the abstract group that consists of performing the transformations of the group of transformations. The reason for distinguishing the group from the transformations is that, generally, a group of transformations of a mathematical structure, structure acts also on various related structures; for example, the above rotation group also acts on triangles by transforming triangles into triangles. If a group acts on a structure, it will usually also act on objects built from that st ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Automorphism Group
In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the group of invertible linear transformations from ''X'' to itself (the general linear group of ''X''). If instead ''X'' is a group, then its automorphism group \operatorname(X) is the group consisting of all group automorphisms of ''X''. Especially in geometric contexts, an automorphism group is also called a symmetry group. A subgroup of an automorphism group is sometimes called a transformation group. Automorphism groups are studied in a general way in the field of category theory. Examples If ''X'' is a set with no additional structure, then any bijection from ''X'' to itself is an automorphism, and hence the automorphism group of ''X'' in this case is precisely the symmetric group of ''X''. If the set ''X'' has additional structu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
