|
LT Code
In computer science, Luby transform codes (LT codes) are the first class of practical fountain codes that are near-optimal erasure correcting codes. They were invented by Michael Luby in 1998 and published in 2002. Like some other fountain codes, LT codes depend on sparse bipartite graphs to trade reception overhead for encoding and decoding speed. The distinguishing characteristic of LT codes is in employing a particularly simple algorithm based on the exclusive or operation (\oplus) to encode and decode the message.The ''exclusive or'' (XOR) operation, symbolized by ⊕, has the very useful property that ''A'' ⊕ ''A'' = 0, where ''A'' is an arbitrary string of bits. LT codes are ''rateless'' because the encoding algorithm can in principle produce an infinite number of message packets (i.e., the percentage of packets that must be received to decode the message can be arbitrarily small). They are ''erasure correcting codes'' because they can be used to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computer Science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (including the design and implementation of hardware and software). Computer science is generally considered an area of academic research and distinct from computer programming. Algorithms and data structures are central to computer science. The theory of computation concerns abstract models of computation and general classes of problems that can be solved using them. The fields of cryptography and computer security involve studying the means for secure communication and for preventing security vulnerabilities. Computer graphics and computational geometry address the generation of images. Programming language theory considers different ways to describe computational processes, and database theory concerns the management of repositories o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fountain Code
In coding theory, fountain codes (also known as rateless erasure codes) are a class of erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the original source symbols can ideally be recovered from any subset of the encoding symbols of size equal to or only slightly larger than the number of source symbols. The term ''fountain'' or ''rateless'' refers to the fact that these codes do not exhibit a fixed code rate. A fountain code is optimal if the original ''k'' source symbols can be recovered from any ''k'' successfully received encoding symbols (i.e., excluding those that were erased). Fountain codes are known that have efficient encoding and decoding algorithms and that allow the recovery of the original ''k'' source symbols from any ''k’'' of the encoding symbols with high probability, where ''k’'' is just slightly larger than ''k''. LT codes were the first practical realizati ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Erasure Correcting Code
In coding theory, an erasure code is a forward error correction (FEC) code under the assumption of bit erasures (rather than bit errors), which transforms a message of ''k'' symbols into a longer message (code word) with ''n'' symbols such that the original message can be recovered from a subset of the ''n'' symbols. The fraction ''r'' = ''k''/''n'' is called the code rate. The fraction ''k’/k'', where ''k’'' denotes the number of symbols required for recovery, is called reception efficiency. Optimal erasure codes Optimal erasure codes have the property that any ''k'' out of the ''n'' code word symbols are sufficient to recover the original message (i.e., they have optimal reception efficiency). Optimal erasure codes are maximum distance separable codes (MDS codes). Parity check Parity check is the special case where ''n'' = ''k'' + 1. From a set of ''k'' values \_, a checksum is computed and appended to the ''k'' source values: :v_= - \sum_^k v_i. The set of ''k'' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Michael Luby
Michael George Luby is a mathematician and computer scientist, CEO of BitRipple, Senior Research Scientist at the International Computer Science Institute (ICSI), former VP Technology at Qualcomm, co-founder and former Chief Technology Officer of Digital Fountain. In coding theory he is known for leading the invention of the Tornado codes and the LT codes. In cryptography he is known for his contributions showing that any one-way function can be used as the basis for private cryptography, and for his analysis, in collaboration with Charles Rackoff, of the Feistel cipher construction. His distributed algorithm to find a maximal independent set in a computer network has also been influential. Luby received his B.Sc. in mathematics from Massachusetts Institute of Technology in 1975. In 1983 he was awarded a Ph.D. in computer science from University of California, Berkeley. In 1996–1997, while at the ICSI, he led the team that invented Tornado codes. These were the first ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bipartite Graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the ''parts'' of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. The two sets U and V may be thought of as a coloring of the graph with two colors: if one colors all nodes in U blue, and all nodes in V red, each edge has endpoints of differing colors, as is required in the graph coloring problem.. In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another red, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color. One often writes G=(U,V,E) to denote a bipartite graph whose partition has the parts U and V, with E denot ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Exclusive Or
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , , , , , and . The negation of XOR is the logical biconditional, which yields true if and only if the two inputs are the same. It gains the name "exclusive or" because the meaning of "or" is ambiguous when both operands are true; the exclusive or operator ''excludes'' that case. This is sometimes thought of as "one or the other but not both". This could be written as "A or B, but not, A and B". Since it is associative, it may be considered to be an ''n''-ary operator which is true if and only if an odd number of arguments are true. That is, ''a'' XOR ''b'' XOR ... may be treated as XOR(''a'',''b'',...). Truth table The truth table of A XOR B shows that it outputs true whenever the inputs differ: Equivalences, elimination, and introdu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Binary Erasure Channel
In coding theory and information theory, a binary erasure channel (BEC) is a communications channel model. A transmitter sends a bit (a zero or a one), and the receiver either receives the bit correctly, or with some probability P_e receives a message that the bit was not received ("erased") . Definition A binary erasure channel with erasure probability P_e is a channel with binary input, ternary output, and probability of erasure P_e. That is, let X be the transmitted random variable with alphabet \. Let Y be the received variable with alphabet \, where \text is the erasure symbol. Then, the channel is characterized by the conditional probabilities: :\begin \operatorname X = 0 &= 1 - P_e \\ \operatorname X = 1 &= 0 \\ \operatorname X = 0 &= 0 \\ \operatorname X = 1 &= 1 - P_e \\ \operatorname X = 0 &= P_e \\ \operatorname X = 1 &= P_e \end Capacity The channel capacity of a BEC is 1-P_e, attained with a uniform distribution for X (i.e. half of the inputs ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Raptor Codes
In computer science, Raptor codes (''rapid tornado''; see Tornado codes) are the first known class of fountain codes with linear time encoding and decoding. They were invented by Amin Shokrollahi in 2000/2001 and were first published in 2004 as an extended abstract. Raptor codes are a significant theoretical and practical improvement over LT codes, which were the first practical class of fountain codes. Raptor codes, as with fountain codes in general, encode a given source block of data consisting of a number ''k'' of equal size source symbols into a potentially limitless sequence of encoding symbols such that reception of any ''k'' or more encoding symbols allows the source block to be recovered with some non-zero probability. The probability that the source block can be recovered increases with the number of encoding symbols received above ''k'' becoming very close to 1, once the number of received encoding symbols is only very slightly larger than ''k''. For example, with the l ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fountain Code
In coding theory, fountain codes (also known as rateless erasure codes) are a class of erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the original source symbols can ideally be recovered from any subset of the encoding symbols of size equal to or only slightly larger than the number of source symbols. The term ''fountain'' or ''rateless'' refers to the fact that these codes do not exhibit a fixed code rate. A fountain code is optimal if the original ''k'' source symbols can be recovered from any ''k'' successfully received encoding symbols (i.e., excluding those that were erased). Fountain codes are known that have efficient encoding and decoding algorithms and that allow the recovery of the original ''k'' source symbols from any ''k’'' of the encoding symbols with high probability, where ''k’'' is just slightly larger than ''k''. LT codes were the first practical realizati ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pseudorandom Number Generator
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's ''seed'' (which may include truly random values). Although sequences that are closer to truly random can be generated using hardware random number generators, ''pseudorandom number generators'' are important in practice for their speed in number generation and their reproducibility. PRNGs are central in applications such as simulations (e.g. for the Monte Carlo method), electronic games (e.g. for procedural generation), and cryptography. Cryptographic applications require the output not to be predictable from earlier outputs, and more elaborate algorithms, which do not inherit the linearity of simpler PRNGs, are needed. Good statis ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cyclic Redundancy Check
A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to digital data. Blocks of data entering these systems get a short ''check value'' attached, based on the remainder of a polynomial division of their contents. On retrieval, the calculation is repeated and, in the event the check values do not match, corrective action can be taken against data corruption. CRCs can be used for error correction (see bitfilters). CRCs are so called because the ''check'' (data verification) value is a ''redundancy'' (it expands the message without adding information) and the algorithm is based on ''cyclic'' codes. CRCs are popular because they are simple to implement in binary hardware, easy to analyze mathematically, and particularly good at detecting common errors caused by noise in transmission channels. Because the check value has a fixed length, the function that generates it is occasionally used ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Raptor Code
In computer science, Raptor codes (''rapid tornado''; see Tornado codes) are the first known class of fountain codes with linear time encoding and decoding. They were invented by Amin Shokrollahi in 2000/2001 and were first published in 2004 as an extended abstract. Raptor codes are a significant theoretical and practical improvement over LT codes, which were the first practical class of fountain codes. Raptor codes, as with fountain codes in general, encode a given source block of data consisting of a number ''k'' of equal size source symbols into a potentially limitless sequence of encoding symbols such that reception of any ''k'' or more encoding symbols allows the source block to be recovered with some non-zero probability. The probability that the source block can be recovered increases with the number of encoding symbols received above ''k'' becoming very close to 1, once the number of received encoding symbols is only very slightly larger than ''k''. For example, with the l ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
