|
==Setup==
#* [[Hamming distance]] : Given two [[Euclidean vector|vector]]s <math>u, v\in\sumSigma^n</math> the Hamming distance between <math>u</math> and <math>v</math>, denoted by <math>\Delta(u, v)</math>, is defined to be the number of positions in which <math>u</math> and <math>v</math> differ.
#* Minimum distance : Let <math>C\subseteq\sumSigma^n</math> be a [[code]]. The minimum distance of code <math>C</math> is defined to be <math>d = \min{\Delta(c_1, c_2)}</math> where <math>c_1 \ne c_2 \in C </math>
#* Code concatenation : Given <math>m = (m_1, \ldotscdots, m_K) \in [Q]^K</math>, consider two codes which we call outer code and inner code
::<math>C_\text{out} = [Q]^K \rightarrowto [Q]^N, \qquad C_\text{in} : [q]^k \rightarrowto [q]^n,</math>,
:and their distances are <math>D</math> and <math>d</math>. A concatenated code can be achieved by <math>C_\text{out} \circ C_\text{in} (m) = (C_\text{in} (C_\text{out} (m)_1), \ldots, C_\text{in} (C_\text{out} (m)_N ))</math> where <math>C_\text{out}(m) = ((C_\text{out} (m)_1, \ldots, (m)_N )).</math>. Finally we will take <math>C_\text{out}</math> to be [[Reed Solomon|RS code]], which has an errors and erasure decoder, and <math>K = O(\log{ N})</math>, which in turn implies that MLD on the inner code will be poly(polynomial in <math>N</math>) time.
#* Maximum likelihood decoding (MLD) : MLD is a decoding method for error correcting codes, which outputs the codeword closest to the received word in Hamming distance. The MLD function denoted by <math>D_{MLD} : \sumSigma^n \rightarrowto C</math> is defined as follows. For every <math>y\in\sum_n</math>Sigma^n, <math>D_{MLD}(y) = \arg \min_{c \in C}\Delta(c, y)</math>.
#* [[Probability density function]] : A [[probability distribution]] <math>\Pr[\bullet]</math> on a sample space <math>S</math> is a mapping from events of <math>S</math> to [[real number]]s such that <math>\Pr[A] \ge 0</math> for any event <math>A</math>, <math>\Pr[S] = 1</math>, and <math>\Pr[A \cup B] = \Pr[A] + \Pr[B]</math> for any two mutually exclusive events <math>A</math> and <math>B</math>
#* [[Expected value]] : The expected value of a [[discrete random variable]] <math>X</math> is
::<math>\mathbb{E}[X] = \sum_x \Pr[X = x].</math>.
==Randomized algorithm==
'''Randomized_Decoder'''
<br />'''Given : '''<math>\mathbf{y} = (y_1,\dots,y_N) \in [q^n]^N</math>.
# For every <math>1 \le i \le N</math>, compute <math>y_i^\prime' = MLD_{C_\text{in}}(y_i)</math>.
# Set <math>\omega_i = \min(\Delta(C_\text{in}(y_i^\prime'), y_i), \tfrac{d\over2}{2})</math>.
# For every <math>1 \le i \le N</math>, repeat : With probability <math>2\omega_i \over d</math>, set <math>y_i^{\prime\prime}'' \leftarrow ?,</math> ?, otherwise set <math>y_i^{\prime\prime}'' = y_i'</math>.
# Run errors and erasure algorithm for <math>C_\text{out}</math> on <math>\mathbf{y}^{\prime\prime}'' = (y_1^{\prime\prime}'', \ldots, y_N^{\prime\prime}'')</math>.
'''Theorem 1.''' ''Let y be a received word such that there exists a [[codeword]]'' <math>\mathbf{c} = (c_1,\ldotscdots, c_N) \in C_\text{out}\circ{C_\text{in}} \subseteq [q^n]^N</math> ''such that'' <math>\Delta(\mathbf{c}, \mathbf{y}) < \fractfrac{Dd}{2}</math>. ''Then the deterministic GMD algorithm outputs'' <math>\mathbf{c}</math>.
Note that a [[Concatenated codes|naive decoding algorithm for concatenated codes]] can correct up to <math>Dd \over tfrac{Dd}{4}</math> errors.
:'''Lemma 1.''' ''Let the assumption in Theorem 1 hold. And if'' <math>\mathbf{y^{\prime\prime}}''</math> ''has'' <math>e'</math> ''errors and'' <math>s'</math> ''erasures (when compared with'' <math>\mathbf{c}</math>'') after'' '''Step 1''', ''then'' <math>\mathbb{E}[2e' + s'] < D.</math>.
''Remark.'' If <math>2e' + s' < D</math>, then the algorithm in '''Step 2''' will output <math>\mathbf{c}</math>. The lemma above says that in expectation, this is indeed the case. Note that this is not enough to prove '''Theorem 1''', but can be crucial in developing future variations of the algorithm.
'''Proof of lemma 1.''' For every <math>1 \le i \le N,</math>, define <math>e_i = \Delta(y_i, c_i).</math>. This implies that
:<math>\sum_{i=1}^N e_i < \frac{Dd}{2} \qquad\qquad (1)</math>
Next for every <math>1 \le i \le N</math>, we define two [[indicator variable]]s:
: <math>\begin{align}
: <math>X{_i^?} = 1</math> iff <math>y_i^{\prime\prime} = ?,</math>
X{_i^?} = 1 &\Leftrightarrow y_i'' = ? \\
X{_i^e} = 1 &\Leftrightarrow C_\text{in}(y_i'') \ne c_i \ \text{and} \ y_i'' \neq ?
\end{align}</math>
We claim that we are done if we can show that for every <math>1 \le i \le N</math>: ▼and
: <math>X\mathbb{E} \left [2X{_i^e} =+ 1</math>X{_i^?}} iff\right ] <math>C_\textleqslant {in2e_i \over d}(y_i^{\primeqquad\prime})qquad \ne c_i(2)</math>
Clearly, by definition
and
: <math>y_ie' = \sum_i X_i^{e \primequad \primetext{and} \nequad s' = \sum_i X_i^?.</math>
Further, by the [[linear]]ity of expectation, we get
▲We claim that we are done if we can show that for every <math>1 \le i \le N</math>:
: <math>\mathbb{E}[2X{_i^e2e' + X{_i^?}}s'] \leleqslant \frac{2}{2e_i} \over d}\qquad\qquadsum_ie_i (2)< D.</math>
Clearly,To byprove definition <math>e' = \sum_{i}X{_i^e}</math> and <math>s' = \sum_{i}X{_i^?}</math>. Further, by the [[linear]]ity of expectation,(2) we get <math>\mathbb{E}[2e' + s'] \le {2 \over d}\sum_ie_i < D</math>. We consider two cases to prove (2) : <math>i'th</math>-th block is correctly decoded ('''Case 1'''), <math>i'th</math>-th block is incorrectly decoded ('''Case 2'''):
'''Case 1:''' <math>(c_i = C_\text{in}(y_i'))</math>
Note that if <math>y_i^{\prime\prime}'' = ?</math> then <math>X_i^e = 0</math>, and <math>\Pr[y_i^'' = ?] = \tfrac{2\primeomega_i}{d}</math> implies <math>\primemathbb{E}[X_i^?] = \Pr[X_i^? = 1] = \tfrac{2\omega_i \over }{d},</math> impliesand <math>\mathbb{E}[X_i^e] = \Pr[X_i^e = 1] = 0</math>.
<math>\mathbb{E}[X_i^?] = \Pr[X_i^? = 1] = {2\omega_i \over d}</math>, and <math>\mathbb{E}[X_i^e] = \Pr[X_i^e = 1] = 0</math>. ▼
Further, by definition we have
: <math>\omega_i = \min \left (\Delta(C_\text{in}(y_i'), y_i), \tfrac{d}{2} \overright 2}) \leleqslant \Delta(C_\text{in}(y_i'), y_i) = \Delta(c_i, y_i) = e_i</math>
'''Case 2:''' <math>(c_i \ne C_\text{in}(y_i'))</math>
▲In this case, <math>\mathbb{E}[X_i^?] = \ Pr[X_i^? = 1] = tfrac{2\omega_i \over }{d}</math> , and <math>\mathbb{E}[X_i^e] = \Pr[X_i^e = 1] = 01 - \tfrac{2\omega_i}{d}.</math> .
In this case,
: <math>\mathbb{E}[X_i^?] = {2\omega_i \over d}</math>and <math>\mathbb{E}[X_i^e] = \Pr[X_i^e = 1] = 1 - {2\omega_i \over d}.</math>
Since <math>c_i \ne C_\text{in}(y_i')</math>, <math>e_i + \omega_i \gegeqslant d</math>. This follows [http://www.cse.buffalo.edu/~atri/courses/coding-theory/lectures/lect28.pdf another case analysis] when <math>(\omega_i = \Delta(C_\text{in}(y_i'), y_i) < \tfrac{d \over }{2})</math> or not.
Finally, this implies
'''Modified_Randomized_Decoder'''
<br />'''Given : '''<math>\mathbf{y} = (y_1, \ldots,y_N) \in [q^n]^N</math>, pick <math>\theta \in [0, 1]</math> at random. Then every for every <math>1 \le i \le N</math>:
# Set <math>y_i^\prime' = MLD_{C_\text{in}}(y_i)</math>.
# Compute <math>\omega_i = \min(\Delta(C_\text{in}(y_i^\prime'), y_i), {d\over2})</math>.
# If <math>\theta</math> < <math>\tfrac{2\omega_i \over }{d}</math>, set <math>y_i^{\prime\prime}'' \leftarrow ?,</math> ?, otherwise set <math>y_i^{\prime\prime}'' = y_i'</math>.
# Run errors and erasure algorithm for <math>C_\text{out}</math> on <math>\mathbf{y}^{\prime\prime}'' = (y_1^{\prime\prime}'',\ldots, y_N^{\prime\prime}'')</math>.
For the proof of '''[[Lemma (mathematics)|Lemma 1]]''', we only use the randomness to show that
: <math>\Pr[y_i^{\prime\prime}'' = ?] = {2\omega_i \over d}.</math>
In this version of the GMD algorithm, we note that
: <math>\Pr[y_i^{\prime\prime}'' = ?] = \Pr \left [\theta \in \left [0, \tfrac{2\omega_i}{d} \overright d}] \right ] = \tfrac{2\omega_i \over }{d}.</math>
The second [[Equality (mathematics)|equality]] above follows from the choice of <math>\theta</math>. The proof of '''Lemma 1''' can be also used to show <math>\mathbb{E}[2e' + s'] < D</math> <for version2 of GMD. In the next section, we will see how to get a deterministic version of the GMD algorithm by choosing <math>D\theta</math> forfrom version2a ofpolynomially GMDsized set as opposed to the current infinite set <math>[0, 1]</math>.
In the next section, we will see how to get a deterministic version of the GMD algorithm by choosing θ from a polynomially sized set as opposed to the current infinite set <math>[0, 1]</math>.
==Deterministic algorithm==
: <math>Q = \{0, 1\} \cup \{q_1, \ldots,q_m\}</math>
where <math>q_1 < q_2 < \cdots < q_m</math> for some <math>m \le \left \lfloor \frac{d}{2} \right \rfloor</math>. Note that for every <math>\theta \in [q_i, q_{i+1}]</math>, the step 1 of the second version of randomized algorithm outputs the same <math>\mathbf{y^{\prime\prime}}''.</math>. Thus, we need to consider all possible value of <math>\theta \in Q</math>. This gives the deterministic algorithm below.
'''Deterministic_Decoder'''
<br />''' Given : '''<math>\mathbf{y} = (y_1,\ldots,y_N) \in [q^n]^N</math>, for every <math>\theta \in Q</math>, repeat the following.
# Compute <math>y_i^\prime' = MLD_{C_\text{in}}(y_i)</math> for <math>1 \le i \le N</math>.
# Set <math>\omega_i = \min(\Delta(C_\text{in}(y_i^\prime'), y_i), {d\over2})</math> for every <math>1 \le i \le N</math>.
# If <math>\theta</math> < <math>{2\omega_i \over d}</math>, set <math>y_i^{\prime\prime}'' \leftarrow ?,</math> ?, otherwise set <math>y_i^{\prime\prime}'' = y_i'</math>.
# Run errors-and-erasures algorithm for <math>C_\text{out}</math> on <math>\mathbf{y^{\prime\prime}}'' = (y_1^{\prime\prime}'', \ldots, y_N^{\prime\prime}'')</math>. Let <math>c_\theta</math> be the codeword in <math>C_\text{out} \circ C_\text{in}</math> corresponding to the output of the algorithm, if any.
# Among all the <math>c_\theta</math> output in 4, output the one closest to <math>\mathbf{y}</math>
Every loop of 1~4 can be run in [[polynomial time]], the algorithm above can also be computed in polynomial time. Specifically, each call to an errors and erasures decoder of <math><dD/2</math> errors takes <math>O(d)</math> time. Finally, the runtime of the algorithm above is <math>O(NQn^{O(1)} + NT_\text{out})</math> where <math>T_\text{out}</math> is the running time of the outer errors and erasures decoder.
Specifically, each call to an errors and erasures decoder of <math><dD/2</math> errors takes <math>O(d)</math> time. Finally, the runtime of the algorithm above is <math>O(NQn^{O(1)} + NT_\text{out})</math> where <math>T_\text{out}</math> is the running time of the outer errors and erasures decoder.
==See also==
| 