37.19.2 Finding the Error Location Polynomial Sigma(x)

The sample code below gives a Berlekamp iterative procedure for finding the value of the error location polynomial.

The input of the procedure is the si[] table defined in the remainder substitution procedure.

The output of the procedure is the error location polynomial named smu (sigma mu). The polynomial coefficients belong to the field. The smu[NB_ERROR+1][] is a table that contains all these coefficients.

NB_ERROR_MAX defines the maximum value of the error correcting capability.

NB_ERROR defines the error correcting capability selected at encoding/decoding time.

NB_FIELD_ELEMENTS defines the number of elements in the field.

int get_sigma()
    {
    int i;
    int j;
    int k;
    /* mu          */
    int mu[NB_ERROR_MAX+2];
    /* sigma ro   */
    int sro[2*NB_ERROR_MAX+1];
    /* discrepancy */
    int dmu[NB_ERROR_MAX+2];
    /* delta order   */
    int delta[NB_ERROR_MAX+2];
    /* index of largest delta */
    int ro;
    int largest;
    int diff;
    /*                   */
    /*     First Row     */
    /*                   */
    /* Mu */
    mu[0]  = -1; /* Actually -1/2  */
    /* Sigma(x) set to 1  */
    for (i = 0; i < (2*NB_ERROR_MAX+1); i++)
     smu[0][i] = 0;
    smu[0][0] = 1;
    /* discrepancy set to 1 */
    dmu[0] = 1;
    /* polynom order set to 0 */
    lmu[0] = 0;
    /* delta set to -1 */
    delta[0]  = (mu[0] * 2 - lmu[0]) >> 1;
    /*                  */
    /*     Second Row   */
    /*                  */
    /* Mu */
    mu[1]  = 0;
    /* Sigma(x) set to 1 */
    for (i = 0; i < (2*NB_ERROR_MAX+1); i++)
     smu[1][i] = 0;
    smu[1][0] = 1;
    /* discrepancy set to Syndrome 1 */
    dmu[1] = si[1];
    /* polynom order set to 0 */
    lmu[1] = 0;
    /* delta set to 0 */
    delta[1]  = (mu[1] * 2 - lmu[1])>> 1;
    for (i=1; i <= NB_ERROR; i++)
    {
     mu[i+1] = i << 1;
    /*************************************************/
     /*                                              */
     /*                                              */
     /*          Compute Sigma (Mu+1)                */
     /*          And L(mu)                           */
     /* check if discrepancy is set to 0 */
     if (dmu[i] == 0)
     {
     /* copy polynom */
     for (j=0; j<2*NB_ERROR_MAX+1; j++)
     {
      smu[i+1][j] =
      smu[i][j];
     }
     /* copy previous polynom order to the next */
     lmu[i+1] = lmu[i];
     }
     else
     {
     ro      = 0;
     largest = -1;
     /* find largest delta with dmu != 0 */
     for (j=0; j<i; j++)
      {
      if (dmu[j])
       {
       if (delta[j] > largest)
        {
        largest = delta[j];
        ro   = j;
        }
       }
      }
     /* initialize signal ro */
     for (k = 0; k < 2*NB_ERROR_MAX+1; k ++)
     {
      sro[k] = 0;
     }
     /* compute difference */
     diff = (mu[i] - mu[ro]);
     /* compute X ^ (2(mu-ro)) */
     for (k = 0; k < (2*NB_ERROR_MAX+1); k ++)
     {
      sro[k+diff] =  smu[ro][k];
     }
     /* multiply by dmu * dmu[ro]^-1 */
     for (k = 0; k < 2*NB_ERROR_MAX+1; k ++)
     {
      /* dmu[ro] is not equal to zero by definition */
      /* check that operand are different from 0    */
      if (sro[k] && dmu[i])
      {
       /* galois inverse  */
       sro[k] = gf_antilog[(gf_log[dmu[i]] + (NB_FIELD_ELEMENTS-gf_log[dmu[ro]]) + gf_log[sro[k]]) %
  NB_FIELD_ELEMENTS];
      }
     }
     /* multiply by dmu * dmu[ro]^-1 */
     for (k = 0; k < 2*NB_ERROR_MAX+1; k++)
     {
      smu[i+1][k] = smu[i][k] ^ sro[k];
      if (smu[i+1][k])
      {
       /* find the order of the polynom */
       lmu[i+1] = k << 1;
      }
     }
    }
    /*                                               */
    /*                                               */
    /*      End Compute Sigma (Mu+1)                 */
    /*      And L(mu)                                */
    /*************************************************/
    /* In either case compute delta  */
    delta[i+1]  = (mu[i+1] * 2 - lmu[i+1]) >> 1;
    /* In either case compute the discrepancy */
    for (k = 0 ; k <= (lmu[i+1]>>1); k++)
    {
     if (k == 0)
     dmu[i+1] = si[2*(i-1)+3];
     /* check if one operand of the multiplier is null, its index is -1 */
     else if (smu[i+1][k] && si[2*(i-1)+3-k])
     dmu[i+1] = gf_antilog[(gf_log[smu[i+1][k]] + gf_log[si[2*(i-1)+3-k]])%nn] ^ dmu[i+1];
    }
    }
    return 0;
    }