Generalized minimum-distance decoding

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.

Setup

edit
  • Hamming distance : Given two vectors   the Hamming distance between   and  , denoted by  , is defined to be the number of positions in which   and   differ.
  • Minimum distance: Let   be a code. The minimum distance of code   is defined to be   where  
  • Code concatenation: Given  , consider two codes which we call outer code and inner code
 
and their distances are   and  . A concatenated code can be achieved by   where   Finally we will take   to be RS code, which has an errors and erasure decoder, and  , which in turn implies that MLD on the inner code will be polynomial in   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   is defined as follows. For every  .
  • Probability density function : A probability distribution   on a sample space   is a mapping from events of   to real numbers such that   for any event  , and   for any two mutually exclusive events   and  
  • Expected value: The expected value of a discrete random variable   is
 

Randomized algorithm

edit

Consider the received word   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   on the resulting vector.

Randomized_Decoder
Given :  .

  1. For every  , compute  .
  2. Set  .
  3. For every  , repeat : With probability  , set   otherwise set  .
  4. Run errors and erasure algorithm for   on  .

Theorem 1. Let y be a received word such that there exists a codeword   such that  . Then the deterministic GMD algorithm outputs  .

Note that a naive decoding algorithm for concatenated codes can correct up to   errors.

Lemma 1. Let the assumption in Theorem 1 hold. And if   has   errors and   erasures (when compared with  ) after Step 1, then  

Remark. If  , then the algorithm in Step 2 will output  . 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   define   This implies that

  Next for every  , we define two indicator variables:

  We claim that we are done if we can show that for every  :

  Clearly, by definition

  Further, by the linearity of expectation, we get

  To prove (2) we consider two cases:  -th block is correctly decoded (Case 1),  -th block is incorrectly decoded (Case 2):

Case 1:  

Note that if   then  , and   implies   and  .

Further, by definition we have

  Case 2:  

In this case,   and  

Since  . This follows another case analysis when   or not.

Finally, this implies

  In the following sections, we will finally show that the deterministic version of the algorithm above can do unique decoding of   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  . Now we come up with another randomized version of the GMD algorithm that uses the same randomness for every  . This idea follows the algorithm below.

Modified_Randomized_Decoder
Given :  , pick   at random. Then every for every  :

  1. Set  .
  2. Compute  .
  3. If  , set   otherwise set  .
  4. Run errors and erasure algorithm for   on  .

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

  In this version of the GMD algorithm, we note that

  The second equality above follows from the choice of  . The proof of Lemma 1 can be also used to show   for version2 of GMD. 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  .

Deterministic algorithm

edit

Let  . Since for each  , we have

  where   for some  . Note that for every  , the step 1 of the second version of randomized algorithm outputs the same  . Thus, we need to consider all possible value of  . This gives the deterministic algorithm below.

Deterministic_Decoder
Given :  , for every  , repeat the following.

  1. Compute   for  .
  2. Set   for every  .
  3. If  , set   otherwise set  .
  4. Run errors-and-erasures algorithm for   on  . Let   be the codeword in   corresponding to the output of the algorithm, if any.
  5. Among all the   output in 4, output the one closest to  

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   errors takes   time. Finally, the runtime of the algorithm above is   where   is the running time of the outer errors and erasures decoder.

See also

edit

References

edit