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();
int m, n, k, t, d;
int length;
int p[6];
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);
for (i = 0; i < n; i++)
Mr[i] = 0;
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!
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
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!