Locally decodable code
A locally decodable code (LDC) is an error-correcting code that allows a single bit of the original message to be decoded with high probability by only examining (or querying) a small number of bits of a possibly corrupted codeword.This property could be useful, say, in a context where information is being transmitted over a noisy channel, and only a small subset of the data is required at a particular time and there is no need to decode the entire message at once. Note that locally decodable codes are not a subset of locally testable codes, though there is some overlap between the two.
- Comment
- enA locally decodable code (LDC) is an error-correcting code that allows a single bit of the original message to be decoded with high probability by only examining (or querying) a small number of bits of a possibly corrupted codeword.This property could be useful, say, in a context where information is being transmitted over a noisy channel, and only a small subset of the data is required at a particular time and there is no need to decode the entire message at once. Note that locally decodable codes are not a subset of locally testable codes, though there is some overlap between the two.
- Date
- enDecember 2016
- Has abstract
- enA locally decodable code (LDC) is an error-correcting code that allows a single bit of the original message to be decoded with high probability by only examining (or querying) a small number of bits of a possibly corrupted codeword.This property could be useful, say, in a context where information is being transmitted over a noisy channel, and only a small subset of the data is required at a particular time and there is no need to decode the entire message at once. Note that locally decodable codes are not a subset of locally testable codes, though there is some overlap between the two. Codewords are generated from the original message using an algorithm that introduces a certain amount of redundancy into the codeword; thus, the codeword is always longer than the original message. This redundancy is distributed across the codeword and allows the original message to be recovered with good probability even in the presence of errors. The more redundant the codeword, the more resilient it is against errors, and the fewer queries required to recover a bit of the original message.
- Hypernym
- Code
- Is primary topic of
- Locally decodable code
- Label
- enLocally decodable code
- Link from a Wikipage to another Wikipage
- Affine geometry
- Bitwise XOR
- Category:Error detection and correction
- Codeword
- Computational complexity theory
- Concatenation
- Error-correcting code
- Forward error correction
- Function composition
- Hadamard
- Hadamard code
- Hamming distance
- Linear cryptanalysis
- Locally testable code
- Mariner 9
- Polynomial interpolation
- Private information retrieval
- Reed-Muller codes
- Union bound
- Reason
- enThis line is no outdated - there are many results since 2011
- SameAs
- 4qxoh
- m.080dvz3
- Q6664678
- Subject
- Category:Error detection and correction
- WasDerivedFrom
- Locally decodable code?oldid=1118808748&ns=0
- WikiPageLength
- 18528
- Wikipage page ID
- 24525188
- Wikipage revision ID
- 1118808748
- WikiPageUsesTemplate
- Template:Reflist
- Template:Update inline