Content deleted Content added
per MOS:HEAD, headers take ordinary sentence case |
|||
| (10 intermediate revisions by 8 users not shown) | |||
Line 1:
{{Short description|Type of error-correcting 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 [[Code word (communication)|codeword]].<ref name=LDCSurvey>{{cite web|url=http://research.microsoft.com/en-us/um/people/yekhanin/papers/survey_iwcc.pdf
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.
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.
Line 8:
More formally, a <math>(q, \delta, \epsilon)</math>-locally decodable code encodes an <math>n</math>-bit message <math>x</math> to an <math>N</math>-bit codeword <math>C(x)</math> such that any bit <math>x_i</math> of the message can be recovered with probability <math>1 - \epsilon</math> by using a randomized decoding algorithm that queries only <math>q</math> bits of the codeword <math>C(x)</math>, even if up to <math>\delta N</math> locations of the codeword have been corrupted.
Furthermore, a perfectly smooth local decoder is a decoder such that, in addition to always generating the correct output given access to an uncorrupted codeword, for every <math>j \in [q]</math> and <math>i \in [n]</math> the <math>j^{th}</math> query to recover the <math>i^{th}</math> bit is uniform over <math>[N]</math>.<ref name=AppCodingTheory>{{cite web|url=http://theory.stanford.edu/~trevisan/pubs/codingsurvey.pdf
(The notation <math>[y]</math> denotes the set <math>\{1,\ldots, y\}</math>). Informally, this means that the set of queries required to decode any given bit are uniformly distributed over the codeword.
Line 19:
| year=2009
| isbn=978-0-521-42426-4
}}</ref>
Locally decodable codes can also be concatenated, where a message is encoded first using one scheme, and the resulting codeword is encoded again using a different scheme. (Note that, in this context, [[concatenation]] is the term used by scholars to refer to what is usually called [[function composition|composition]]
== Length of codeword and query complexity ==
The rate of a code refers to the ratio between its message length and codeword length: <math>\frac{|x|}{|C(x)|}</math>, and the number of queries required to recover 1 bit of the message is called the query complexity of a code.
The rate of a code is inversely related to the query complexity, but the exact shape of this tradeoff is a major [[open problem]].<ref name=LDC1>{{cite web|url=http://research.microsoft.com/en-us/um/people/yekhanin/Papers/LDC_now.pdf
== Applications ==
Line 33 ⟶ 32:
=== Data transmission and storage ===
Locally decodable codes are especially useful for data transmission over noisy channels. The [[Hadamard code]] (a special case of Reed Muller codes) was used in 1971 by [[Mariner 9]] to transmit pictures of Mars back to Earth. It was chosen over a 5-repeat code (where each bit is repeated 5 times) because, for roughly the same number of bits transmitted per pixel, it had a higher capacity for error correction. (The Hadamard code falls under the general umbrella of [[forward error correction]], and just happens to be locally decodable; the actual algorithm used to decode the transmission from Mars was a generic error-correction scheme.)<ref>{{cite web |title=Combinatorics in Space The Mariner 9 Telemetry System |url=http://www-math.ucdenver.edu/~wcherowi/courses/m7409/mariner9talk.pdf
LDCs are also useful for data storage, where the medium may become partially corrupted over time, or the reading device is subject to errors. In both cases, an LDC will allow for the recovery of information despite errors, provided that there are relatively few. In addition, LDCs do not require that the entire original message be decoded; a user can decode a specific portion of the original message without needing to decode the entire thing.<ref name=PIR>{{cite web|url=http://research.microsoft.com/pubs/141305/cacm_2010.pdf |title=Private Information retrieval |author=Sergey Yekhanin}}</ref>
Line 73 ⟶ 72:
The main idea behind local decoding of [[Reed-Muller codes]] is [[polynomial interpolation]]. The key concept behind a Reed-Muller code is a multivariate polynomial of degree <math>d</math> on <math>l</math> variables. The message is treated as the evaluation of a polynomial at a set of predefined points. To encode these values, a polynomial is extrapolated from them, and the codeword is the evaluation of that polynomial on all possible points. At a high level, to decode a point of this polynomial, the decoding algorithm chooses a set <math>S</math> of points on a line that passes through the point of interest <math>x</math>. It then queries the codeword for the evaluation of the polynomial on points in <math>S</math> and interpolates that polynomial. Then it is simple to evaluate the polynomial at the point that will yield <math>x</math>. This roundabout way of evaluating <math>x</math> is useful because (a) the algorithm can be repeated using different lines through the same point to improve the probability of correctness, and (b) the queries are uniformly distributed over the codeword.
More formally, let <math>\mathbb{F}</math> be a [[finite field]], and let <math>l, d</math> be numbers with <math>d < |\mathbb{F}|</math>. The Reed-Muller code with parameters <math>\mathbb{F}, l, d</math> is the function RM : <math>\mathbb{F}^{\binom{l+d}{d}} \rightarrow \mathbb{F}^{|\mathbb{F}|^l}</math> that maps every <math>l</math>-variable polynomial <math>P</math> over <math>\mathbb{F}</math> of total degree <math>d</math> to the values of <math>P</math> on all the inputs in <math>\mathbb{F}^l</math>. That is, the input is a polynomial of the form
<math>P(x_1, \ldots, x_l) = \sum\limits_{i_1+\ldots+i_l\le d}c_{i_1,\ldots,i_l}x_1^{i_1}x_2^{i_2}\cdots x_l^{i_l}</math>
specified by the interpolation of the <math>\binom{l+d}{d}</math> values of the predefined points and the output is the sequence <math>\{P(x_1, \ldots, x_l)\}</math> for every <math>x_1, \ldots, x_l \in \mathbb{F}</math>.<ref name=AB1942>{{harvnb|Arora|Barak|2009|loc=Section 19.4.2}}</ref>
| |||