BCH 21,31

• Download source files - 3.12 Kb

Introduction

BCH error correction codes are block-based error correcting codes with a wide range of applications in digital communications and storage. BCH codes are used to correct errors in many systems including:

• Storage devices (including tape, Compact Disk, DVD, barcodes etc.)
• Wireless or mobile communications (including cellular telephones, microwave links, pager etc.)
• Satellite communications
• Digital television / DVB
• High-speed modems such as ADSL, xDSL, etc.

The BCH encoder takes a block of digital data and adds extra "redundant" bits. Errors occur during transmission or storage due to a number of reasons (for example, noise or interference, scratches on a CD, etc.). The BCH decoder processes each block of data and attempts to correct the errors and recover the original data. The number and type of errors that can be corrected depends on the characteristics of the BCH code.

BCH encoding and decoding can be carried out either in software or in special-purpose hardware.

Finite (Galois) field arithmetic

BCH codes are based on a special area of mathematics known as Galois fields or finite fields. A finite field has the property that the arithmetic operations (+,-,x,/ etc.) on field elements always have a result in the field. A BCH encoder or decoder needs to carry out these arithmetic operations. These operations require special hardware or software functions to implement.

Generator polynomial

A BCH codeword is generated using a special polynomial. All valid codewords are exactly divisible by the generator polynomial. The general form of the generator polynomial is:

g(x) = (x - a<SUP>i</SUP>) (x - a<SUP>i+1</SUP>) .... (x - a<SUP>i+2t</SUP>)

and the codeword is constructed using:

c(x) = g(x) . i(x)

where g(x) is the generator polynomial, i(x) is the information block, c(x) is a valid codeword and a is a primitive element of the field.

BCH 21,31

One of my projects was to implement the POCSAG protocol that is used in pagers for a simple communication. The protocol requires some error correction codes that can easily recover lost data from redundant data. For this, the creators decided to use BCH ECC. The protocol consists of codewords. Every codeword contains 21 bits of data (original), 10 bits of redundant data (for error correcting) and 1 bit of parity. In this case, we use BCH 21,31 to implement codewords of POCSAG.

I have tried to give a brief introduction to BCH and you can find more useful information from articles and books on error correction codes, concepts, and the mathematics required. Also Dr. Dobbs journal published a very useful series of articles on Reed-Solomon and BCH. I found a few articles in this field such as those that are introduced in the "The Error Correcting Codes (ECC) Page", but unfortunately none of them works right. There are some bugs in the codes and they return wrong results. Then, I decided to write my own code.

Note that we have used binary BCH for POCSAG.

CBCHEncoder

CBCHEncoder is a simple class for computing BCH ECC for a set of data. You give the class a 32 bit integer or an array of integers for encoding. The class treats the first 21 bits as the original data and adds the encoded 10 bits at the end of the integer. Below is the class interface:

class CBCHEncoder  
{
public:
    int GetEncodedData();
    int* GetEncodedDataPtr();
    void SetData(int* pData);
    void SetData(int iData);
    void Encode();
    
    CBCHEncoder();
    virtual ~CBCHEncoder();

private:
    void InitializeEncoder();
    void ComputeGeneratorPolynomial();
    void GenerateGf();
    
    /*
    * m = order of the field GF(2**5) = 5
    * n = 2**5 - 1 = 31 = length 
    * t = 2 = error correcting capability 
    * d = 2*t + 1 = 5 = designed minimum distance 
    * k = n - deg(g(x)) = 21 = dimension 
    * p[] = coefficients of primitive polynomial 
    *       used to generate GF(2**5)
    * g[] = coefficients of generator polynomial, g(x)
    * alpha_to [] = log table of GF(2**5) 
    * index_of[] = antilog table of GF(2**5)
    * data[] = coefficients of data polynomial, i(x)
    * bb[] = coefficients of redundancy polynomial 
    *        ( x**(10) i(x) ) modulo g(x)
    * numerr = number of errors 
    * errpos[] = error positions 
    * recd[] = coefficients of received polynomial 
    * decerror = number of decoding errors 
    *            (in MESSAGE positions) 
    */
    
    int m, n, k, t, d;
    int    length;
    int p[6];        // irreducible polynomial 
    int alpha_to[32], index_of[32], g[11];
    int recd[32], data[21], bb[11];
    int Mr[31];
};

Using the class is very simple. Just create an instance of the class such as m_bch as follows:

CBCHEncoder  m_bch;
m_bch.SetData(0x23c5FFFF);
m_bch.Encode();
int iEncodedData=m_bch.GetEncodedData();

Note that the class itself generates the Galois Field GF(2**m) and then computes the generator polynomial of the BCH code (see InitializeEncoder(), private member function of the class).

Encode() is the heart of the class. Here is its body:

void CBCHEncoder::Encode()
{
    int    h, i, j=0, start=0, end=(n-k);
    
    // reset the M(x)+r array elements
    for (i = 0; i < n; i++)
        Mr[i] = 0;
    
    // copy the contents of data into Mr and add the zeros
    // use the copy method of arrays, its better :-)
    for (h=0; h < k; ++h)
        Mr[h] = data[h];
    
    
    while (end < n)
    {
        for (i=end; i>start-2; --i)
        {
            if (Mr[start] != 0)
            {
                Mr[i]^=g[j];
                ++j;
            }
            else
            {
                ++start;
                j = 0;
                end = start+(n-k);
                break;
            }
        }
    }
    
    
    j = 0;
    for (i = start; i < end; ++i)
    {
        bb[j]=Mr[i];
        ++j;
    }
}

Acknowledgements

I should thank my cousin Mohammad and also Mohammad Shahmohammadi one of my best friends who helped me in writing/debugging the code. Most of the code is taken from the Reed-Solomon implementation from the ECC Homepage.

Enjoy!