Generalized minimum-distance decoding

In coding theory, generalized minimum-distance (GMD) decoding provides an efficient algorithm for decoding , which is based on using an -and- decoder for the .

A naive decoding algorithm for concatenated codes can not be an optimal way of decoding because it does not take into account the information that (MLD) gives. In other words, in the naive algorithm, inner received are treated the same regardless of the difference between their . Intuitively, the outer decoder should place higher confidence in symbols whose inner are close to the received word. in 1966 devised a better algorithm called generalized minimum distance (GMD) decoding which makes use of those information better. This method is achieved by measuring confidence of each received codeword, and erasing symbols whose confidence is below a desired value. And GMD decoding algorithm was one of the first examples of soft-decision decoders. We will present three versions of the GMD decoding algorithm. The first two will be while the last one will be a .

Setup

• : Given two u, vinSigma^n the Hamming distance between u and v, denoted by Delta(u, v), is defined to be the number of positions in which u and v differ.
• Minimum distance: Let CsubseteqSigma^n be a . The minimum distance of code C is defined to be d= minDelta(c_1, c_2) where c_1 ne c_2 in C
• Code concatenation: Given m = (m_1, cdots, m_K) in [Q]^K, consider two codes which we call outer code and inner code

C_text{out} = [Q]^K to [Q]^N, qquad C_text{in} : [q]^k to [q]^n, and their distances are D and d. A concatenated code can be achieved by 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)) where C_text{out}(m) = ((C_text{out} (m)_1, ldots, (m)_N)). Finally we will take C_text{out} to be , which has an errors and erasure decoder, and K = O(log N), which in turn implies that MLD on the inner code will be polynomial in N 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 D_{MLD} : Sigma^n to C is defined as follows. For every yinSigma^n, D_{MLD}(y) = arg min_{c in C}Delta(c, y).
• : A Pr on a sample space S is a mapping from events of S to such that Pr[A] ge 0 for any event A, Pr[S] = 1, and Pr[A cup B] = Pr[A] + Pr[B] for any two mutually exclusive events A and B
• : The expected value of a X is

mathbb{E}[X] = sum_x Pr[X = x].

Randomized algorithm

Consider the received word mathbf{y} = (y_1,ldots,y_N) in [q^n]^N which was corrupted by a . The following is the algorithm description for the general case. In this algorithm, we can decode y by just declaring an erasure at every bad position and running the errors and erasure decoding algorithm for C_text{out} on the resulting vector.

Randomized_Decoder
Given : mathbf{y} = (y_1,dots,y_N) in [q^n]^N.

1. For every 1 le i le N, compute y_i' = MLD_{C_text{in}}(y_i).
2. Set omega_i = min(Delta(C_text{in}(y_i'), y_i), tfrac{d}{2}).
3. For every 1 le i le N, repeat : With probability 2omega_i over d, set y_i leftarrow ?, otherwise set y_i = y_i'.
4. Run errors and erasure algorithm for C_text{out} on mathbf{y} = (y_1, ldots, y_N).

Theorem 1. Let y be a received word such that there exists a mathbf{c} = (c_1,cdots, c_N) in C_text{out}circ{C_text{in}} subseteq [q^n]^Nsuch that Delta(mathbf{c}, mathbf{y}) < tfrac{Dd}{2}. Then the deterministic GMD algorithm outputs mathbf{c}.

Note that a can correct up to tfrac{Dd}{4} errors.

Lemma 1. Let the assumption in Theorem 1 hold. And if mathbf{y} has e' errors and s' erasures (when compared with mathbf{c}) after Step 1, then mathbb{E}[2e' + s'] < D.Remark. If 2e' + s' < D, then the algorithm in Step 2 will output mathbf{c}. 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 1 le i le N, define e_i = Delta(y_i, c_i). This implies that

sum_{i=1}^N e_i < frac{Dd}{2} qquadqquad (1)Next for every 1 le i le N, we define two :

begin{align} 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}We claim that we are done if we can show that for every 1 le i le N:

mathbb{E} left [2X{_i^e + X{_i^?}} right ] leqslant {2e_i over d}qquadqquad (2)Clearly, by definition

e' = sum_i X_i^e quad text{and} quad s' = sum_i X_i^?.Further, by the of expectation, we get

mathbb{E}[2e' + s'] leqslant frac{2}{d}sum_ie_i < D.To prove (2) we consider two cases: i-th block is correctly decoded (Case 1), i-th block is incorrectly decoded (Case 2):

Case 1: (c_i = C_text{in}(y_i'))

Note that if y_i = ? then X_i^e = 0, and Pr[y_i = ?] = tfrac{2omega_i}{d} implies mathbb{E}[X_i^?] = Pr[X_i^? = 1] = tfrac{2omega_i}{d}, and mathbb{E}[X_i^e] = Pr[X_i^e = 1] = 0.

Further, by definition we have

omega_i = min left (Delta(C_text{in}(y_i'), y_i), tfrac{d}{2} right ) leqslant Delta(C_text{in}(y_i'), y_i) = Delta(c_i, y_i) = e_iCase 2: (c_i ne C_text{in}(y_i'))

In this case, mathbb{E}[X_i^?] = tfrac{2omega_i}{d} and mathbb{E}[X_i^e] = Pr[X_i^e = 1] = 1 - tfrac{2omega_i}{d}.

Since c_i ne C_text{in}(y_i'), e_i + omega_i geqslant d. This follows another case analysis when (omega_i = Delta(C_text{in}(y_i'), y_i) < tfrac{d}{2}) or not.

Finally, this implies

mathbb{E}[2X_i^e + X_i^?] = 2 - {2omega_i over d} le {2e_i over d}.In the following sections, we will finally show that the deterministic version of the algorithm above can do unique decoding of C_text{out} circ C_text{in} up to half its design distance.

Modified randomized algorithm

Note that, in the previous version of the GMD algorithm in step "3", we do not really need to use "fresh" for each i. Now we come up with another randomized version of the GMD algorithm that uses the same randomness for every i. This idea follows the algorithm below.

Modified_Randomized_Decoder
Given : mathbf{y} = (y_1, ldots,y_N) in [q^n]^N, pick theta in [0, 1] at random. Then every for every 1 le i le N:

1. Set y_i' = MLD_{C_text{in}}(y_i).
2. Compute omega_i = min(Delta(C_text{in}(y_i'), y_i), {dover2}).
3. If theta< tfrac{2omega_i}{d}, set y_i leftarrow ?, otherwise set y_i = y_i'.
4. Run errors and erasure algorithm for C_text{out} on mathbf{y} = (y_1,ldots, y_N).

For the proof of ', we only use the randomness to show that

Pr[y_i = ?] = {2omega_i over d}.In this version of the GMD algorithm, we note that

Pr[y_i = ?] = Pr left [theta in left [0, tfrac{2omega_i}{d} right ] right ] = tfrac{2omega_i}{d}.The second above follows from the choice of theta. The proof of Lemma 1 can be also used to show mathbb{E}[2e' + s'] < D for version2 of GMD. In the next section, we will see how to get a deterministic version of the GMD algorithm by choosing theta from a polynomially sized set as opposed to the current infinite set [0, 1].

Deterministic algorithm

Let Failed to parse (Missing texvc executable. Please see math/README to configure.): Q = {0,1} cup (y_i) for 1 le i le N.

1. Set omega_i = min(Delta(C_text{in}(y_i'), y_i), {dover2}) for every 1 le i le N.
2. If theta < {2omega_i over d}, set y_i leftarrow ?, otherwise set y_i = y_i'.
3. Run errors-and-erasures algorithm for C_text{out} on mathbf{y} = (y_1, ldots, y_N). Let c_theta be the codeword in C_text{out} circ C_text{in} corresponding to the output of the algorithm, if any.
4. Among all the c_theta output in 4, output the one closest to mathbf{y}

Every loop of 1~4 can be run in , the algorithm above can also be computed in polynomial time. Specifically, each call to an errors and erasures decoder of <dD/2 errors takes O(d) time. Finally, the runtime of the algorithm above is O(NQn^{O(1)} + NT_text{out}) where T_text{out} is the running time of the outer errors and erasures decoder.

See Also on BitcoinWiki

3. Welch Berlekamp algorithm

Source

http://wikipedia.org/