|
Guruswami–Sudan List Decoding Algorithm
In coding theory, list decoding is an alternative to unique decoding of error-correcting codes in the presence of many errors. If a code has relative distance \delta, then it is possible in principle to recover an encoded message when up to \delta / 2 fraction of the codeword symbols are corrupted. But when error rate is greater than \delta / 2 , this will not in general be possible. List decoding overcomes that issue by allowing the decoder to output a short list of messages that might have been encoded. List decoding can correct more than \delta / 2 fraction of errors. There are many polynomial-time algorithms for list decoding. In this article, we first present an algorithm for Reed–Solomon (RS) codes which corrects up to 1 - \sqrt errors and is due to Madhu Sudan. Subsequently, we describe the improved Guruswami–Sudan list decoding algorithm, which can correct up to 1 - \sqrt errors. Here is a plot of the rate R and distance \delta for different algorithms. ... [...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 computer data storage, 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 detection and correction, Error control (or ''channel coding'') # Cryptography, Cryptographic coding # Line code, Line coding Data compression attempts to remove unwanted redundancy from the data from a source in order to transmit it more efficiently. For example, DEFLATE data compression makes files small ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
List Decoding
In coding theory, list decoding is an alternative to unique decoding of error-correcting codes for large error rates. The notion was proposed by Elias in the 1950s. The main idea behind list decoding is that the decoding algorithm instead of outputting a single possible message outputs a list of possibilities one of which is correct. This allows for handling a greater number of errors than that allowed by unique decoding. The unique decoding model in coding theory, which is constrained to output a single valid codeword from the received word could not tolerate a greater fraction of errors. This resulted in a gap between the error-correction performance for stochastic noise models (proposed by Shannon) and the adversarial noise model (considered by Richard Hamming). Since the mid 90s, significant algorithmic progress by the coding theory community has bridged this gap. Much of this progress is based on a relaxed error-correction model called list decoding, wherein the decoder out ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
RS Code
RS may refer to: Businesses and organizations * RS Group, entertainment & media company in Thailand * RS Group plc, British electronics & industrial distributor in England with brands including RS Components and RS Americas, Inc * RS Infotainment, Indian film production and distribution company * RS Productions, defunct Australian television and radio production company * Relief Society, an official auxiliary of The Church of Jesus Christ of Latter-day Saints (LDS Church) * République solidaire, a French political party * Roberval and Saguenay Railway (reporting mark RS) * Russian Party (Serbia) (''Ruska stranka''), a political party in Serbia Sport * RS Sailing, an international designer and builder of sailboats and dinghies * Queens Park Rangers F.C., a professional football club from Shepherd's Bush, London, commonly nicknamed 'The Rs' Places * Republic of Serbia (ISO 3166-1 code RS), country * Republic of Slovenia, country * Republika Srpska, one of the two politic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Madhu Sudan
Madhu Sudan (born 12 September 1966) is an Indian-American computer scientist. He has been a Gordon McKay Professor of Computer Science at the Harvard John A. Paulson School of Engineering and Applied Sciences since 2015. Career He received his bachelor's degree in computer science from IIT Delhi in 1987 and his doctoral degree in computer science at the University of California, Berkeley in 1992. The dissertation he wrote at the University of California, Berkeley is titled ''Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems''. He was a research staff member at the IBM Thomas J. Watson Research Center in Yorktown Heights, New York from 1992 to 1997 and became a researcher at the Massachusetts Institute of Technology (MIT) after that. From 2009 to 2015 he was a permanent researcher at Microsoft Research New England before joining the Harvard University faculty in 2015. Research contribution and awards In 1998, he received the Sloan Research ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Venkatesan Guruswami
Venkatesan Guruswami (born 1976) is a senior scientist at the Simons Institute for the Theory of Computing and Professor of EECS and Mathematics at the University of California, Berkeley. He did his high schooling at Padma Seshadri Bala Bhavan in Chennai, India. He completed his undergraduate in Computer Science from IIT Madras and his doctorate from Massachusetts Institute of Technology under the supervision of Madhu Sudan in 2001. After receiving his PhD, he spent a year at UC Berkeley as a Miller Fellow, and then was a member of the faculty at the University of Washington from 2002 to 2009. His primary area of research is computer science, and in particular on error-correcting codes. During 2007–2008, he visited the Institute for Advanced Study as a Member of School of Mathematics. He also visited SCS at Carnegie Mellon University during 2008–09 as a visiting faculty. From July 2009 through December 2020 he was a faculty member in the Computer Science Department in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Berlekamp–Welch Algorithm
The Berlekamp–Welch algorithm, also known as the Welch–Berlekamp algorithm, is named for Elwyn R. Berlekamp and Lloyd R. Welch. This is a decoder algorithm that efficiently corrects errors in Reed–Solomon error correction, Reed–Solomon codes for an RS(''n'', ''k''), code based on the Reed Solomon original view where a message m_1, \cdots, m_k is used as coefficients of a polynomial F(a_i) or used with Lagrange polynomial, Lagrange interpolation to generate the polynomial F(a_i) of degree < ''k'' for inputs and then is applied to to create an encoded codeword . The goal of the decoder is to recover the original encoding polynomial , using the known inputs and received codeword with possible errors. It also computes an error polynomial where cor ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Gaussian Elimination
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients. This method can also be used to compute the rank of a matrix, the determinant of a square matrix, and the inverse of an invertible matrix. The method is named after Carl Friedrich Gauss (1777–1855). To perform row reduction on a matrix, one uses a sequence of elementary row operations to modify the matrix until the lower left-hand corner of the matrix is filled with zeros, as much as possible. There are three types of elementary row operations: * Swapping two rows, * Multiplying a row by a nonzero number, * Adding a multiple of one row to another row. Using these operations, a matrix can always be transformed into an upper triangular matrix (possibly bordered by rows or columns of zeros), and in fact one that is in row echelon form. Once all of the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Reed–Solomon Error Correction
In information theory and coding theory, Reed–Solomon codes are a group of error-correcting codes that were introduced by Irving S. Reed and Gustave Solomon in 1960. They have many applications, including consumer technologies such as MiniDiscs, CDs, DVDs, Blu-ray discs, QR codes, Data Matrix, data transmission technologies such as DSL and WiMAX, Broadcasting, broadcast systems such as satellite communications, Digital Video Broadcasting, DVB and ATSC Standards, ATSC, and storage systems such as RAID 6. Reed–Solomon codes operate on a block of data treated as a set of finite field, finite-field elements called symbols. Reed–Solomon codes are able to detect and correct multiple symbol errors. By adding check symbols to the data, a Reed–Solomon code can detect (but not correct) any combination of up to erroneous symbols, ''or'' locate and correct up to erroneous symbols at unknown locations. As an erasure code, it can correct up to erasures at locations that are known and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
