Click here to Skip to main content
15,867,990 members
Articles / Programming Languages / C++
Article

BCH 21,31

,
Rate me:
Please Sign up or sign in to vote.
4.87/5 (23 votes)
20 Nov 20053 min read 98.5K   2.1K   30   14
Implementation of BCH Error Correcting Code (ECC).

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!

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
CEO Solaris Electronics LLC
United Arab Emirates United Arab Emirates
I was born in Shiraz, a very beautiful famous city in Iran. I started programming when I was 12 years old with GWBASIC. Since now, I worked with various programming languages from Basic, Foxpro, C/C++, Visual Basic, Pascal to MATLAB and now Visual C++.
I graduated from Iran University of Science & Technology in Communication Eng., and now work as a system programmer for a telecommunication industry.
I wrote several programs and drivers for Synthesizers, Power Amplifiers, GPIB, GPS devices, Radio cards, Data Acquisition cards and so many related devices.
I'm author of several books like Learning C (primary and advanced), Learning Visual Basic, API application for VB, Teach Yourself Object Oriented Programming (OOP) and etc.
I'm winner of January, May, August 2003 and April 2005 best article of month competition, my articles are:


You can see list of my articles, by clicking here


Written By
Product Manager AltaML
Canada Canada
I was born in Shiraz, Iran. A beautiful city that's famous for its weather, poets, ancient culture.
Got my high school diploma from QHS - Quebec High School.
Studied Computer Eng. at the University of New Brunswick (Canada) & Continued at Shiraz University.
Graduated from the University, school of Engineering: 2004.
Masters program, IT, e-Commerce at the electronic University of Shiraz.
Masters in IT Management at UTM, Malaysia.
Masters in Computer Science (Machine Learning) at University of Alberta
Currently in Edmonton, AB Canada!

Comments and Discussions

 
Questionbinary code Pin
Member 1409537319-Dec-18 13:21
Member 1409537319-Dec-18 13:21 
GeneralMy vote of 5 Pin
Manoj Kumar Choubey26-Feb-12 19:52
professionalManoj Kumar Choubey26-Feb-12 19:52 
QuestionAbout error correction / Detection Pin
MARK02430-May-11 1:03
MARK02430-May-11 1:03 
GeneralThis seems a little complicated... Pin
Ryan Binns30-Aug-10 19:48
Ryan Binns30-Aug-10 19:48 
GeneralRe: This seems a little complicated... Pin
Member 408286023-Mar-11 22:04
Member 408286023-Mar-11 22:04 
QuestionBCH(31,21) decoding Pin
Stephen McGoldrick22-Jun-10 8:28
Stephen McGoldrick22-Jun-10 8:28 
GeneralBCH code Pin
flytosky25-Apr-08 5:58
flytosky25-Apr-08 5:58 
GeneralBCH code Pin
rakesh Patel11-Apr-08 4:44
rakesh Patel11-Apr-08 4:44 
QuestionBuilding on vs 2005 Pin
imre_b22-Apr-07 19:59
imre_b22-Apr-07 19:59 
GeneralBCH Pin
urfinebaby31-Mar-06 9:17
urfinebaby31-Mar-06 9:17 
QuestionBug info Pin
Mircea Puiu20-Nov-05 9:35
Mircea Puiu20-Nov-05 9:35 
AnswerRe: Bug info Pin
Abbas_Riazi20-Nov-05 23:25
professionalAbbas_Riazi20-Nov-05 23:25 
GeneralMany Thanks... Pin
thompsons20-Nov-05 7:47
thompsons20-Nov-05 7:47 
AnswerRe: Many Thanks... Pin
Abbas_Riazi20-Nov-05 8:01
professionalAbbas_Riazi20-Nov-05 8:01 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.