33.5.2 Find 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;
    }