12,512,669 members (28,382 online)
alternative version

67.2K views
30 bookmarked
Posted

# BCH 21,31

, 20 Nov 2005
 Rate this:
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!

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

## About the Authors

 CEO Misbah3Com Iran (Islamic Republic of)
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 Acqusition 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 competetion, my articles are:

You can see list of my articles, by clicking here

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.
Currently in Edmonton, AB Canada!

## You may also be interested in...

 Pro Pro

## Comments and Discussions

 First Prev Next
 My vote of 5 manoj kumar choubey26-Feb-12 19:52 manoj kumar choubey 26-Feb-12 19:52
 About error correction / Detection MARK02430-May-11 1:03 MARK024 30-May-11 1:03
 This seems a little complicated... Ryan Binns30-Aug-10 19:48 Ryan Binns 30-Aug-10 19:48
 Re: This seems a little complicated... Member 408286023-Mar-11 22:04 Member 4082860 23-Mar-11 22:04
 BCH(31,21) decoding Stephen McGoldrick22-Jun-10 8:28 Stephen McGoldrick 22-Jun-10 8:28
 BCH code flytosky25-Apr-08 5:58 flytosky 25-Apr-08 5:58
 BCH code rakesh Patel11-Apr-08 4:44 rakesh Patel 11-Apr-08 4:44
 Building on vs 2005 imre_b22-Apr-07 19:59 imre_b 22-Apr-07 19:59
 BCH urfinebaby31-Mar-06 9:17 urfinebaby 31-Mar-06 9:17
 Bug info Mircea Puiu20-Nov-05 9:35 Mircea Puiu 20-Nov-05 9:35
 Re: Bug info A. Riazi20-Nov-05 23:25 A. Riazi 20-Nov-05 23:25
 Many Thanks... thompsons20-Nov-05 7:47 thompsons 20-Nov-05 7:47
 Re: Many Thanks... A. Riazi20-Nov-05 8:01 A. Riazi 20-Nov-05 8:01
 Last Visit: 31-Dec-99 18:00     Last Update: 1-Oct-16 8:55 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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