HOME
*





Perfect Code
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. Background on error-correcting codes An original message and an encoded version are both composed in an alphabet of ''q'' letters. Each code word contains ''n'' letters. The original message (of length ''m'') is shorter than ''n'' letters. The message is converted into an ''n''-letter codeword by an encoding algorithm, transmitted over a noisy channel, and finally decoded by the receiver. The decoding process interprets a garbled codeword, referred to as si ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them. These objects consist of either abstractions from nature orin modern mathematicsentities that are stipulated to have certain properties, called axioms. A ''proof'' consists of a succession of applications of deductive rules to already established results. These results include previously proved theorems, axioms, andin case of abstraction from naturesome basic properties that are considered true starting points of ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Ball (mathematics)
In mathematics, a ball is the solid figure bounded by a ''sphere''; it is also called a solid sphere. It may be a closed ball (including the boundary points that constitute the sphere) or an open ball (excluding them). These concepts are defined not only in three-dimensional Euclidean space but also for lower and higher dimensions, and for metric spaces in general. A ''ball'' in dimensions is called a hyperball or -ball and is bounded by a ''hypersphere'' or ()-sphere. Thus, for example, a ball in the Euclidean plane is the same thing as a disk, the area bounded by a circle. In Euclidean 3-space, a ball is taken to be the volume bounded by a 2-dimensional sphere. In a one-dimensional space, a ball is a line segment. In other contexts, such as in Euclidean geometry and informal use, ''sphere'' is sometimes used to mean ''ball''. In the field of topology the closed n-dimensional ball is often denoted as B^n or D^n while the open n-dimensional ball is \operatorname B^n or \ope ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Graduate Texts In Mathematics
Graduate Texts in Mathematics (GTM) (ISSN 0072-5285) is a series of graduate-level textbooks in mathematics published by Springer-Verlag. The books in this series, like the other Springer-Verlag mathematics series, are yellow books of a standard size (with variable numbers of pages). The GTM series is easily identified by a white band at the top of the book. The books in this series tend to be written at a more advanced level than the similar Undergraduate Texts in Mathematics series, although there is a fair amount of overlap between the two series in terms of material covered and difficulty level. List of books #''Introduction to Axiomatic Set Theory'', Gaisi Takeuti, Wilson M. Zaring (1982, 2nd ed., ) #''Measure and Category – A Survey of the Analogies between Topological and Measure Spaces'', John C. Oxtoby (1980, 2nd ed., ) #''Topological Vector Spaces'', H. H. Schaefer, M. P. Wolff (1999, 2nd ed., ) #''A Course in Homological Algebra'', Peter Hilton, Urs Stammbac ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Oxford University Press
Oxford University Press (OUP) is the university press of the University of Oxford. It is the largest university press in the world, and its printing history dates back to the 1480s. Having been officially granted the legal right to print books by decree in 1586, it is the second oldest university press after Cambridge University Press. It is a department of the University of Oxford and is governed by a group of 15 academics known as the Delegates of the Press, who are appointed by the vice-chancellor of the University of Oxford. The Delegates of the Press are led by the Secretary to the Delegates, who serves as OUP's chief executive and as its major representative on other university bodies. Oxford University Press has had a similar governance structure since the 17th century. The press is located on Walton Street, Oxford, opposite Somerville College, in the inner suburb of Jericho. For the last 500 years, OUP has primarily focused on the publication of pedagogical texts and ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Johnson Bound
In applied mathematics, the Johnson bound (named after Selmer Martin Johnson) is a limit on the size of error-correcting codes, as used in coding theory for data transmission or communications. Definition Let C be a ''q''-ary code of length n, i.e. a subset of \mathbb_q^n. Let d be the minimum distance of C, i.e. :d = \min_ d(x,y), where d(x,y) is the Hamming distance between x and y. Let C_q(n,d) be the set of all ''q''-ary codes with length n and minimum distance d and let C_q(n,d,w) denote the set of codes in C_q(n,d) such that every element has exactly w nonzero entries. Denote by , C, the number of elements in C. Then, we define A_q(n,d) to be the largest size of a code with length n and minimum distance d: : A_q(n,d) = \max_ , C, . Similarly, we define A_q(n,d,w) to be the largest size of a code in C_q(n,d,w): : A_q(n,d,w) = \max_ , C, . Theorem 1 (Johnson bound for A_q(n,d)): If d=2t+1, : A_q(n,d) \leq \frac. If d=2t+2, : A_q(n,d) \leq \frac. Theorem 2 (Joh ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Plotkin Bound
In the mathematics of coding theory, the Plotkin bound, named after Morris Plotkin, is a limit (or bound) on the maximum possible number of codewords in binary codes of given length ''n'' and given minimum distance ''d''. Statement of the bound A code is considered "binary" if the codewords use symbols from the binary alphabet \. In particular, if all codewords have a fixed length ''n'', then the binary code has length ''n''. Equivalently, in this case the codewords can be considered elements of vector space \mathbb_2^n over the finite field \mathbb_2. Let d be the minimum distance of C, i.e. :d = \min_ d(x,y) where d(x,y) is the Hamming distance between x and y. The expression A_(n,d) represents the maximum number of possible codewords in a binary code of length n and minimum distance d. The Plotkin bound places a limit on this expression. Theorem (Plotkin bound): i) If d is even and 2d > n , then : A_(n,d) \leq 2 \left\lfloor\frac\right\rfloor. ii) If d is odd and ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Singleton Bound
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 C with block length n, size M and minimum distance d. It is also known as the Joshibound. proved by and even earlier by . Statement of the bound The minimum distance of a set C of codewords of length n is defined as d = \min_ d(x,y) where d(x,y) is the Hamming distance between x and y. The expression A_(n,d) represents the maximum number of possible codewords in a q-ary block code of length n and minimum distance d. Then the Singleton bound states that A_q(n,d) \leq q^. Proof First observe that the number of q-ary words of length n is q^n, since each letter in such a word may take one of q different values, independently of the remaining letters. Now let C be an arbitrary q-ary block code of minimum distance d. Clearly, all codewords c \in C are distinct. If we puncture the code by deleting the first d-1 letters of each code ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Griesmer Bound
In the mathematics of coding theory, the Griesmer bound, named after James Hugo Griesmer, is a bound on the length of linear binary codes of dimension ''k'' and minimum distance ''d''. There is also a very similar version for non-binary codes. Statement of the bound For a binary linear code, the Griesmer bound is: : n\geqslant \sum_^ \left\lceil\frac\right\rceil. Proof Let N(k,d) denote the minimum length of a binary code of dimension ''k'' and distance ''d''. Let ''C'' be such a code. We want to show that : N(k,d)\geqslant \sum_^ \left\lceil\frac\right\rceil. Let ''G'' be a generator matrix of ''C''. We can always suppose that the first row of ''G'' is of the form ''r'' = (1, ..., 1, 0, ..., 0) with weight ''d''. : G= \begin 1 & \dots & 1 & 0 & \dots & 0 \\ \ast & \ast & \ast & & G' & \\ \end The matrix G' generates a code C', which is called the residual code of C. C' obviously has dimension k'=k-1 and length n'=N(k,d)-d. C' has a ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Golay Code (other)
Golay code may refer to: * Binary Golay code, an error-correcting code used in digital communications * Ternary Golay code * (Golay) complementary sequences : ''For complementary sequences in biology, see complementarity (molecular biology) In molecular biology, complementarity describes a relationship between two structures each following the lock-and-key principle. In nature complementarity is ... {{mathdab fr:Code de Golay ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Hamming Code
In computer science and telecommunication, 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 possib ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]