Content deleted Content added
Add definition for notation e_i; consistent use of full stops in list. |
Missing full stop. |
||
Line 186:
By lemma 1, <math>c_j+c_k = c_{j+k} = x\cdot g_{j+k} = x\cdot e_i = x_i</math>. Since <math>j</math> and <math>k</math> are picked uniformly, the probability that <math>y_j \not = c_j</math> is at most <math>\delta</math>. Similarly, the probability that <math>y_k \not = c_k</math> is at most <math>\delta</math>. By the [[union bound]], the probability that either <math>y_j</math> or <math>y_k</math> do not match the corresponding bits in <math>c</math> is at most <math>2\delta</math>. If both <math>y_j</math> and <math>y_k</math> correspond to <math>c</math>, then lemma 1 will apply, and therefore, the proper value of <math>x_i</math> will be computed. Therefore, the probability <math>x_i</math> is decoded properly is at least <math>1-2\delta</math>. Therefore, <math>\epsilon = \frac{1}{2} - 2\delta</math> and for <math>\epsilon</math> to be positive, <math>0 \leq \delta \leq \frac{1}{4}</math>.
Therefore, the Walsh–Hadamard code is <math>(2, \delta, \frac{1}{2}-2\delta)</math> locally decodable for <math>0\leq \delta \leq \frac{1}{4}</math>.
==Optimality==
| |||