|
Second 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 (John ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Selmer Martin Johnson
Selmer Martin Johnson (21 May 1916 – 26 June 1996) was an American mathematician, a researcher at the RAND Corporation. Biography Johnson was born on May 21, 1916, in Buhl, Minnesota. He earned a B.A. and then an M.A. in mathematics from the University of Minnesota in 1938 and 1940 respectively. World War II interrupted Johnson's mathematical studies: he enlisted in the United States Air Force, earning the rank of major. While serving, he also earned an M.S. in meteorology from New York University in 1942. After the war, Johnson returned to graduate study in mathematics at the University of Illinois at Urbana–Champaign, finishing his doctorate in 1950; his dissertation, on the subject of number theory, was supervised by David Bourgin, a student of George David Birkhoff.Contributors, ''IRE Transactions on Information Theory'', April 1962, p. 261. This section may be seen attached to ; Johnson's paper, "A new upper bound for error-correcting codes", appears earlier in the same iss ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Error-correcting Code
In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is the sender encodes the message with redundant information in the form of an ECC. The redundancy allows the receiver to detect a limited number of errors that may occur anywhere in the message, and often to correct these errors without retransmission. The American mathematician Richard Hamming pioneered this field in the 1940s and invented the first error-correcting code in 1950: the Hamming (7,4) code. ECC contrasts with error detection in that errors that are encountered can be corrected, not simply detected. The advantage is that a system using ECC does not require a reverse channel to request retransmission of data when an error occurs. The downside is that there is a fixed overhead that is added to the message, thereby requiring a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 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. There are four types of coding: # Data compression (or ''source coding'') # Error control (or ''channel coding'') # Cryptographic coding # Line coding Data compression attempts to remove unwanted redundancy from the data from a source in order to transmit it more efficiently. For example, ZIP data compression makes data files smaller, for purposes such as to reduce Internet traffic. Data compression a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Data Transmission
Data transmission and data reception or, more broadly, data communication or digital communications is the transfer and reception of data in the form of a digital bitstream or a digitized analog signal transmitted over a point-to-point or point-to-multipoint communication channel. Examples of such channels are copper wires, optical fibers, wireless communication using radio spectrum, storage media and computer buses. The data are represented as an electromagnetic signal, such as an electrical voltage, radiowave, microwave, or infrared signal. Analog transmission is a method of conveying voice, data, image, signal or video information using a continuous signal which varies in amplitude, phase, or some other property in proportion to that of a variable. The messages are either represented by a sequence of pulses by means of a line code (''baseband transmission''), or by a limited set of continuously varying waveforms (''passband transmission''), using a digital modulat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Code
In communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for communication through a communication channel or storage in a storage medium. An early example is an invention of language, which enabled a person, through speech, to communicate what they thought, saw, heard, or felt to others. But speech limits the range of communication to the distance a voice can carry and limits the audience to those present when the speech is uttered. The invention of writing, which converted spoken language into visual symbols, extended the range of communication across space and time. The process of encoding converts information from a source into symbols for communication or storage. Decoding is the reverse process, converting code symbols back into a form that the recipient understands, such as English or/and Spanish. One reason for coding is to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hamming Distance
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. A major application is in coding theory, more specifically to block codes, in which the equal-length strings are vectors over a finite field. Definition The Hamming distance between two equal-length strings of symbols is the number of positions at which the corresponding symbols are different. Examples The symbols may be letters, bits, or decimal digits, among other possibilities. For example, the Hamming distance between: ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Floor Function
In mathematics and computer science, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least integer greater than or equal to , denoted or . For example, , , , and . Historically, the floor of has been–and still is–called the integral part or integer part of , often denoted (as well as a variety of other notations). Some authors may define the integral part as if is nonnegative, and otherwise: for example, and . The operation of truncation generalizes this to a specified number of digits: truncation to zero significant digits is the same as the integer part. For an integer, . Notation The ''integral part'' or ''integer part'' of a number ( in the original) was first defined in 1798 by Adrien-Marie Legendre in his proof of the Legendre's formula. Carl Friedrich Gauss introduced the square bracket notation in hi ... [...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] |
Hamming Bound
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] |
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] |
Elias Bassalygo Bound
The Elias Bassalygo bound is a mathematical limit used in coding theory for error correction during data transmission or communications. Definition Let C be a q-ary code of length n, i.e. a subset of n.Each q-ary block code of length n is a subset of the strings of \mathcal_q^n, where the alphabet set \mathcal_q has q elements. Let R be the ''rate'' of C, \delta the ''relative distance'' and :B_q(y, \rho n) = \left \ be the '' Hamming ball'' of radius \rho n centered at y. Let \text_q(y, \rho n) = , B_q(y, \rho n), be the ''volume'' of the Hamming ball of radius \rho n . It is obvious that the volume of a Hamming Ball is translation-invariant, i.e. indifferent to y. In particular, , B_q(y, \rho n), =, B_q(0, \rho n), . With large enough n, the ''rate'' R and the ''relative distance'' \delta satisfy the Elias-Bassalygo bound: :R \leqslant 1 - H_q ( J_q(\delta))+o(1), where : H_q(x)\equiv_\text -x\log_q \left ( \right)-(1-x)\log_q is the ''q''-ary entropy func ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Gilbert–Varshamov Bound
In coding theory, the Gilbert–Varshamov bound (due to Edgar Gilbert and independently Rom Varshamov.) is a limit on the parameters of a (not necessarily linear) code. It is occasionally known as the Gilbert– Shannon–Varshamov bound (or the GSV bound), but the name "Gilbert–Varshamov bound" is by far the most popular. Varshamov proved this bound by using the probabilistic method for linear codes. For more about that proof, see Gilbert–Varshamov bound for linear codes. Statement of the bound Let :A_q(n,d) denote the maximum possible size of a ''q''-ary code C with length ''n'' and minimum Hamming distance ''d'' (a ''q''-ary code is a code over the field \mathbb_q of ''q'' elements). Then: :A_q(n,d) \geqslant \frac. Proof Let C be a code of length n and minimum Hamming distance d having maximal size: :, C, =A_q(n,d). Then for all x\in\mathbb_q^n , there exists at least one codeword c_x \in C such that the Hamming distance d(x,c_x) between x and c_x satisfies :d(x, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
