Generalized minimum-distance decoding

From BitcoinWiki
This is the approved revision of this page, as well as being the most recent.
Jump to: navigation, search

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

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 maximum likelihood decoding (MLD) gives. In other words, in the naive algorithm, inner received codewords are treated the same regardless of the difference between their hamming distances. Intuitively, the outer decoder should place higher confidence in symbols whose inner encodings are close to the received word. David Forney 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 randomized algorithms while the last one will be a deterministic algorithm.


  • Hamming distance : Given two vectors u, v\in\Sigma^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 C\subseteq\Sigma^n be a code. The minimum distance of code C is defined to be d= \min\Delta(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 RS code, 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.
\mathbb{E}[X] = \sum_x \Pr[X = x].

Randomized algorithm[edit]

Consider the received word \mathbf{y} = (y_1,\ldots,y_N) \in [q^n]^N which was corrupted by a noisy channel. 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.

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 2\omega_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 codeword \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 naive decoding algorithm for concatenated codes 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} \qquad\qquad (1)

Next for every 1 \le i \le N, we define two indicator variables:

X{_i^?} = 1 &\Leftrightarrow y_i'' = ? \\
X{_i^e} = 1 &\Leftrightarrow C_\text{in}(y_i'') \ne c_i \ \text{and} \ y_i'' \neq ?

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}\qquad\qquad (2)

Clearly, by definition

e' = \sum_i X_i^e \quad \text{and} \quad s' = \sum_i X_i^?.

Further, by the linearity 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{2\omega_i}{d} implies \mathbb{E}[X_i^?] = \Pr[X_i^? = 1] = \tfrac{2\omega_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_i

Case 2: (c_i \ne C_\text{in}(y_i'))

In this case, \mathbb{E}[X_i^?] = \tfrac{2\omega_i}{d} and \mathbb{E}[X_i^e] = \Pr[X_i^e = 1] = 1 - \tfrac{2\omega_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 - {2\omega_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[edit]

Note that, in the previous version of the GMD algorithm in step "3", we do not really need to use "fresh" randomness 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.

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), {d\over2}).
  3. If \theta< \tfrac{2\omega_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 Lemma 1, we only use the randomness to show that

\Pr[y_i'' = ?] = {2\omega_i \over d}.

In this version of the GMD algorithm, we note that

\Pr[y_i'' = ?] = \Pr \left [\theta \in \left [0, \tfrac{2\omega_i}{d} \right ] \right ] = \tfrac{2\omega_i}{d}.

The second equality 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[edit]

Let Failed to parse (Missing <code>texvc</code> 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), {d\over2}) for every 1 \le i \le N.
  2. If \theta < {2\omega_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 polynomial time, 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[edit]

  1. Concatenated codes
  2. Reed Solomon error correction
  3. Welch Berlekamp algorithm